2. Методические указания по решению задач транспортного типа
1. Задача о перевозке груза (транспортная задача)
В трех пунктах производства производится некоторый продукт в количествах а1 = 118, а2 = 18, а3 = 98 единиц соответственно. Этот продукт необходимо доставить в пять пунктов потребления, заявки которых составляют b1 = 68, b2 = 68, b3 = 90, b4 = 31, b5 = 87 единиц соответственно.
Известны
транспортные расходы (тарифы) cij
(i =
,
j =
)
на перевозку единицы продукции от i-го
поставщика j-му потребителю:
15 16 14 11 17
С = 15 16 13 11 14
21 22 16 16 23 .
Требуется найти план перевозок продукции, при котором суммарные транспортные расходы будут минимальными.
Решение
Решение
любой транспортной задачи должно
начинаться с проверки того, выполняется
ли условие ее закрытости, гарантирующее
существование оптимального плана
перевозок. Для нашей задачи это условие
имеет вид:
=
.
Вычислим = 118 + 18 + 98 = 234 и = 68 + 68 + 90 + 31 + 87 = 344.
Так как < , то исходная транспортная задача не является закрытой. Прежде чем приступить к нахождению оптимального плана перевозок, нужно сделать ее закрытой. Для этого следует выполнить такие действия:
Ввести четвертого (фиктивного) поставщика с объемом предложения а4 = 344 – 234 = 110 единиц;
Положить транспортные тарифы на перевозку грузов от этого поставщика ко всем потребителям равными нулю, т. е. с4j = 0, j = .
Замечание. Если окажется, что > , то в исходной задаче следует ввести шестого (фиктивного) потребителя с заявкой b6 = – и положить тарифы на перевозку грузов от всех поставщиков к этому потребителю равными нулю, т. е. сi6 = 0, i = .
После добавления фиктивного поставщика
получена закрытая транспортная задача,
в которой число поставщиков m
= 4, а число потребителей n
= 5. Обозначим хij –
объем поставки от i-го
поставщика к j-му потребителю
(i =
,
j =
).
Тогда модель новой транспортной задачи
имеет вид:
x11 + x12 + x13 + x14 + x15 = 118, (1.1)
x21 + x22 + x23 + x24 + x25 = 18, (1.2)
x31 + x32 + x33 + x34 + x35 = 98, (1.3)
x41 + x42 + x43 + x44 + x45 = 110, (1.4)
x11 + x21 + x31 + x41 = 68 (1.5)
x12 + x22 + x32 + x42 = 68 (1.6)
x13 + x23 + x33 + x43 = 90 (1.7)
x14 + x24 + x34 + x44 = 31 (1.8)
x15 + x25 + x35 + x45 = 87 (1.9)
хij
0,
i
=
,
j =
.
(1.10)
S = 15x11 + 16x12 + 14x13 + 11x14 + 17x15 + 15x21 + 16x22 + 13x23 + 11x24 +
+ 14x25 + 21x31 + 22x32 + 16x33 + 16x34 + 23x35 → min. (1.11)
Для нахождения оптимального плана этой задачи ее следует представить в виде транспортной таблицы (см. табл. 1.0), строки которой соответствуют поставщикам, а столбцы – потребителям.
Таблица 1.0
bj ai |
68 |
68 |
90 |
31 |
87 |
118 |
15 x11 |
16 x12 |
14 x13 |
11 x14 |
17 x15 |
18 |
15 x21 |
16 x22 |
13 x23 |
11 x24 |
14 x25 |
98 |
21 х31 |
22 х32 |
16 x33 |
16 х34 |
23 x35 |
110 |
0 х41 |
0 х42 |
0 х43 |
0 х44 |
0 х45 |
В левом верхнем углу каждой клетки (i, j) помещается тариф данной перевозки cij, а сама клетка предназначается для размещения величины поставки xij из i-го пункта назначения в j-й пункт потребления. В клетки этой таблицы следует занести объемы перевозок, соответствующие начальному опорному плану. Этот план перевозок должен быть допустимым, т.е. составлен таким образом, чтобы выполнялись балансовые условия: общая сумма всех поставок от каждого поставщика (сумма по строке) равна объему его производства, а общая сумма поставок каждому потребителю (сумма по столбцу) — его спросу.
Клетки, в которые помещены какие-то перевозки, считаются занятыми, а остальные клетки — свободными. Занятые клетки транспортной таблицы соответствуют базисным, а свободные — небазисным компонентам опорного плана. Поскольку этот план должен быть опорным, то число занятых клеток в нем должно равняться m + n – 1 = 8. Проще всего построить такой план методом северо-западного угла.