Реферат: Транспортная задача
Юридическийтехникум Рассмотренои одобрено ПЦК
г.Кропоткин программирования
ПредседательПЦК
ПокалицынаО.В.
План чтения лекции поучебной дисциплине
«Математическиеметоды»
Раздел№ 2.Линейное программирование. Тема № 2.5.Транспортнаязадача.
Место проведения: аудитория.
Литература:
1. Венцель Е.С.Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И.Математические методы и модели в экономике, финансах, бизнесе. – М.: ЮНИТИДАНА,2001
Учебные вопросы и расчет времени
№п/п Учебные вопросы Время, мин Методические указания1.
2.
3.
Постановка транспортной задачи.
Математическая модель транспортной задачи.
Методы решения транспортной задачи.
1. Вводная часть. Организационныймомент. План занятия. Основные требования.
2. Основная часть.
1. Постановка транспортной задачи.
Важнымчастным случаем задачи линейного программирования является транспортная задача.
Постановказадачи: Пусть имеется mпоставщиков и n потребителей. Мощность поставщиков и спросы потребителей, а так же затраты наперевозку груза для каждой пары «поставщик – потребитель» заданы таблицей.
поставщики
потребители
В1
В2
…
Вj
…
Bn
Мощность поставщиков
A1
С11
С12
С1j
С1n
a1
A2
С21
С22
С2j
С2n
a2
…
…
…
…
…
Ai
Сij
Сij
Сij
Сin
ai
…
…
…
…
…
Am
Cm1
Cm2
Cmj
Cmn
am
Спрос потребителей
b1
b2
bj
bn
Найти объемыперевозок каждой пары «поставщик –потребитель» так, чтобы: мощности всех поставщиков были реализованы; спросывсех потребителей были удовлетворены; суммарные затраты на перевозку были бымаксимальны.
Особенностиматематической модели транспортной задачи:
üсистема ограничений есть системауравнений, то есть задача ЛП в каноническом виде;
üкоэффициенты при неизвестныхсистемы ограничений равны единицы или нулю;
üкаждая переменная входит в системуограничений два раза: один раз в систему ограничений поставок, второй раз – всистему ограничений спроса.
2. Математическая модель транспортной задачи.
Пусть хij – количествогруза, перевозимого с i-го в j-й пункт.
Целевая функция: />
Система ограничений:
/>
Для решения задачисоставляется таблица. В клетки таблицы записывается стоимость соответствующихперевозок сij и в них же заносятся значения перевозок xij,удовлетворяющих поставленным ограничениям. Клетки с не нулевыми перевозкаминазываются базисными, а с нулевыми – свободными. В зависимости от соотношениямежду запасами и заявками транспортная задача называется сбалансированной илинесбалансированной.
Сбалансированная ТЗ:/>
Несбалансированная ТЗ: />
Для сбалансированной ТЗограничения принимают вид равенств, то есть получаем m+nограничений, в которых все переменные линейно зависимы. В результате допустимоерешение сбалансированной ТЗ может быть получено, если заполнять клеткитранспортной таблицы таким образом, чтобы сумма перевозок в каждой строке /> должна быть равна запасам ai, асумма перевозок в каждом столбце /> равнасоответствующей заявке вj. Вариантов заполнения транспортной таблицы множество,поэтому искомым решением является то из допустимых решений, для которых общаястоимость перевозок будет минимальной.
3. Методы решения транспортнойзадачи.
Транспортнаязадача может быть решена симплекс методом. Однако специфическая форма системыограничений позволяет упростить симплекс метод.
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. Заполнениеклеток происходит последовательно по следующему алгоритму: сначала вывозитсягруз из пункта А1 и завозится в пункт В1, и этой перевозке х11 присваиваетсямаксимально возможное значение. Если заявка пункта В1 выполнена, а в пункте А1еще остается груз, то он вывозится в пункт В2 и т.д. Если в пункте А1недостаточно было груза для В1, то недостающий груз берется из А2 и т.д.
После тогокак спрос потребителя А1 удовлетворен, он выпадает из рассмотрения и т.д.
В1 В2 В3 В4Запасы
А115 5
5 7
6 820
А2 625 7
8 525
А3 55 4
25 6
730
А4 6 510 7
5 4
15
А5 5 6 610 6
10
Заявки
15
35
35
15
100
Стоимостьперевозки: W=5*15+5*7+25*7+5*4+25*6+10*7+5*4+10*6=605
Существенным недостаткомметода северо-западного угла является то, что он построен без учета стоимостиперевозок.
МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА. Заполнениеклеток транспортной таблицы начинается с той клетки, в которой значениеминимально. В нее записывается максимально возможное значение перевозки хij,которое может быть равно либо запасу аi, либо заявке вj.Если заявка вj выполнена полностью, то j-й столбецбольше не рассматривается. Если не вывезенный груз еще остался, то он вывозитсяв пункт с наименьшим тарифом.
В1 В2 В3 В4Запасы
А115 5
75 6
820
А2 6 725 8
525
А3 530 4
6 730
А4 6 5 715 4
15
А5 55 6
5 6
610
Заявки
15
35
35
15
100
Стоимостьперевозки: W = 30*4+5*6+15*4+15*5+5*6+25*8+5*6 = 545.
РАСПЕРЕДЕЛЕННЫЙ МЕТОДУЛУЧШЕНИЯ ПЛАНА ПЕРЕВОЗОК. Для улучшения плана используют цикл транспортнойтаблицы. Цикл – это несколько клеток, соединенных замкнутой ломанной с прямымиуглами.
Изобразим два цикла: А1В1,А1В2, А2В2, А2В1; А1В3, А1В4, А2В4, А2В6, А1В5, А4В5, А4В3.
поставщики
потребители
В1
В2
В3
В4
В5
B6
Мощность поставщиков
A1
С11
С12
С13
С14
С15
С16
a1
A2
С21
С22
С23
С24
С25
С26
a2
A3
С31
С32
С33
С34
С35
С36
a3
А4
С41
С42
С43
С44
С45
С46
а4
A5
С51
С52
С53
С54
С55
С56
a5
Спрос потребителей
b1
b2
в3
b4
в5
b6
Каждый цикл имеет четноечисло вершин и ребер, то есть в таблице в каждой строке или столбце можетнаходтся только четное число клеток, содержащих вершины. Поэтому вклетках-вершинах можно менять значения петевозки так, что в сумма по строкам истолбцам не изменяется. Вершины цикла, в которых увеличиваем перевозки «+», а вкоторых уменьшаем перевозки «-». Величину изменения обозначим ∆, ее будемперемещать по циклу. Максимальное значение ∆, на которое можно уменьшитьперевозку, определяется условием неотрицательности перевозок.
Цена цикла q – это изменение стоимостиперевозок при перемещении ∆ по циклу, которая равна разности между суммойстоимостей перевозок, соответствующих «+»-ым вершинам и суммой стоимостей «-»-ых вершин.
Q1= (с11+с22)-(с12+с21)
Q2 = (с13+с24+с16+с45)-(с14+с26+с15+с43)
При переносе по циклу кединиц груза, стоимость цикла и стоимость плана перевозок измениться на кединиц. Для улучшения плана перевозок нужно найти «-» цикл и переместить понему максимально возможное количество груза, до тех пор пока таких циклов неостанется. Количество груза, которое можно переместить определяется минимальнымзначением перевозок в «-» вершинах цикла.