Транспортная задача
Юридический техникум Рассмотрено и одобрено ПЦК
г. Кропоткин программирования
Председатель ПЦК
Покалицына О.В.
План чтения лекции по учебной дисциплине
«Математические методы»
Раздел № 2. Линейное программирование. Тема № 2.5. Транспортная задача.
Место проведения: аудитория.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001
Учебные вопросы и расчет времени
№п/п | Учебные вопросы | Время, мин | Методические указания |
1. 2. 3. |
Постановка транспортной задачи. Математическая модель транспортной задачи. Методы решения транспортной задачи. |
Вводная часть. Организационный момент. План занятия. Основные требования.
Основная часть.
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. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.
- Методы решения транспортной задачи.
Транспортная задача может быть решена симплекс методом. Однако специфическая форма системы ограничений позволяет упростить симплекс метод.
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. Заполнение клеток происходит последовательно по следующему алгоритму: сначала вывозится груз из пункта А1 и завозится в пункт В1, и этой перевозке х11 присваивается максимально возможное значение. Если заявка пункта В1 выполнена, а в пункте А1 еще остается груз, то он вывозится в пункт В2 и т.д. Если в пункте А1 недостаточно было груза для В1, то недостающий груз берется из А2 и т.д.
После того как спрос потребителя А1 удовлетворен, он выпадает из рассмотрения и т.д.
В1 | В2 | В3 | В4 |
Запасы |
|
А1 |
15 5 |
5 7 |
6 | 8 |
20 |
А2 | 6 |
25 7 |
8 | 5 |
25 |
А3 | 5 |
5 4 |
25 6 |
7 |
30 |
А4 | 6 | 5 |
10 7 |
5 4 |
15 |
А5 | 5 | 6 | 6 |
10 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 |
Запасы |
|
А1 |
15 5 |
7 |
5 6 |
8 |
20 |
А2 | 6 | 7 |
25 8 |
5 |
25 |
А3 | 5 |
30 4 |
6 | 7 |
30 |
А4 | 6 | 5 | 7 |
15 4 |
15 |
А5 | 5 |
5 6 |
5 6 |
6 |
10 |
Заявки |
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)
При переносе по циклу к единиц груза, стоимость цикла и стоимость плана перевозок измениться на к единиц. Для улучшения плана перевозок нужно найти «-» цикл и переместить по нему максимально возможное количество груза, до тех пор пока таких циклов не останется. Количество груза, которое можно переместить определяется минимальным значением перевозок в «-» вершинах цикла.