3. Транспортная задача
Транспортная задача – задача о наиболее экономичном плане перевозок однородного или взаимозаменяемого продукта из пункта производства в пункт потребления.
Постановка задачи
Некоторый однородный продукт изготавливается в m пунктах производства (А1, А2, А3, А4 … Аm), задан объем производства ai → Ai (i = 1,m).
Произведенный продукт должен быть перевезен в n пунктов потребления (B1, B2, B3, B4 … Bn), имеется спрос bj → Bj (j = 1,2,3…n).
Транспортные издержки Сij, связанные с перевозкой единицы продукта из пункта производства Ai в пункт потребления Bj.
Требуется определить план перевозки, обеспечивающий при минимальных транспортных издержках Сij удовлетворение потребностей во всех пунктах потребления за счет продукта, произведенного во всех пунктах производства.
Таблица 1
Исходные данные
Поставщики |
Потребители |
Запасы |
||||||
B1 |
B2 |
… |
… |
Bj |
… |
Bn |
||
A1 |
C11 X11 |
C12 X12 |
|
|
C1j X1j |
|
C1n X1n |
a1 |
A2 |
C21 X21 |
C22 X22 |
|
|
C2j X2j |
|
C2n X2n |
a2 |
… |
|
|
|
|
|
|
|
… |
Ai |
Ci1 Xi1 |
Ci2 Xi2 |
|
|
Cij Xij |
|
Cin Xin |
ai |
… |
|
|
|
|
|
|
|
… |
Am |
Cm1 Xm1 |
Cm2 Xm2 |
|
|
Cmj Xmj |
|
Cmn Xmn |
am |
Потребности |
b1 |
b2 |
… |
… |
bj |
… |
bn |
Σai Σbj |
После заполнения таблицы можно сформулировать транспортную задачу, необходимо написать целевую функцию: z = ΣΣ СijXij → min.
Тогда имеются два ограничения:
-
ограничение по запасам: ΣXij = aij;
-
ограничение по потребностям: ΣXij = bij.
Различают открытые и закрытые модели транспортной задачи:
-
закрытые: Σai = Σbj;
-
открытые: Σai ≠ Σbj.
Если Σai > Σbj, то вводится фиктивный (1+n)-й пункт назначения с потребностью bn+1 = Σai – Σbj, при этом Ci,(n+1) = 0.
Если Σai < Σbj, то вводится фиктивный (m+1)-й пункт отправления с объемом потребления am+1 = Σbij – Σaij, при этом C(m+1),j = 0.
Математическая модель транспортной задачи относится к задачам линейного программирования (ЗЛП). Для ее решения имеется несколько способов, самым распространенным является метод потенциалов:
-
определение начального допустимого базисного решения (первого опорного плана);
-
построение последовательных итераций (шагов), улучшающих опорные планы;
-
повторение п.2 до тех пор, пока план не станет оптимальным.
Определение первоначального опорного плана
План составляется последовательным заполнением таблицы перевозок, так, чтобы каждый раз либо полностью удовлетворить потребность потребителя, либо полностью вывезти груз от поставщика.
Существует два метода определения опорного плана:
-
диагональный (метод «северо-западного угла») – при этом на каждом шаге построения заполняется левая верхняя клетка;
-
метод наименьшей стоимости – на каждом шаге заполняется клетка с наименьшей величиной Cij, если такая клетка не единственная, лучше заполнить ту по вертикали или горизонтали, которая встречается чаще.
Оптимальность базисного решения
Получив первый опорный план, следует проверить его оптимальность и если требуется перейти к новому опорному плану.
Каждому поставщику Aij и каждому потребителю Bij подставляются следующие величины Ui и Vj – потенциалы этих пунктов. Для того, чтобы опорный план был оптимальным необходимо и достаточно, чтобы ему соответствовала система из (m+n) чисел, удовлетворяющая условию:
-
Cij – (Ui + Vj) = 0; (1)
-
Δ Cij = Cij – (Ui + Vj) ≥ 0 (2)
Для всех Xij ≥ 0 (для занятых клеток – (1); для свободных клеток – (2)) Ui,Vj – потенциалы производителей и потребителей.
Поскольку число неизвестных потенциалов (m+n) на 1 больше числа уравнений (числа заполненных клеток), то выбираем строку, где есть занятая клетка и для этой строки назначаем потенциал равный 0 (U1 = 0) и находим последовательность уравнений Cij – (Ui + Vj) = 0 для нахождения остальных потенциалов.
Затем для всех свободных клеток определяем величину Δ Cij, если все значения Δ Cij > 0, то оптимальный план получен, если одно из них отрицательное – план следует улучшить.
Улучшение плана перевозок
Среди пустых клеток с отрицательными значениями выбирается та, у которой Cij наименьшее, эта клетка рекомендуется к заполнению, в результате которого одна из заполненных клеток станет пустой.
Процедура перепланировки соответствует смене роли переменной в симплекс методе.
Для свободной клетки строиться замкнутая ломаная линия (цикл). Цикл состоит из горизонтальных и вертикальных отрезков прямых, одна из вершин находиться в свободной клетке ○, остальные в занятых - ●; число вершин – четное, на каждой стороне могут находиться две заполненные вершины. Свободной вершине присваивается знак «+», остальные знаки чередуются. Значение наименьшей отрицательной величины прибавляется к положительным значениям и отнимается от отрицательных, получается новый контур перевозок.
После этого строиться новый опорный план.
Задача №3.
Завод выпускает продукцию в четырех цехах: A1, A2, A3, A4, расположенных на разных территориях. Свою продукцию завод поставляет в пять магазинов города. Цех A1 – 125 тыс. изделий, A2 – 105 тыс., A3 – 95 тыс., A4 – 130 тыс. изделий. Плановая потребность магазинов в продукции завода следующая:
B1 – 120 тыс. изделий;
B2 – 70 тыс;
B3 – 55 тыс;
B4 – 85 тыс;
B5 – 125 тыс.
Составьте такой план перевозки изделий, при котором расходы на перевозку были бы наименьшими. Стоимость перевозки 1 тыс. изделий из цехов в магазины приведена в таблице:
-
2
3
6
8
2
8
1
2
3
9
7
6
4
1
5
2
10
8
5
9