Исследование операций Пример решения транспортной задачи (закрытая модель)

запасами 30, 48, 24 т в четыре пункта назначения с

потребностями 18, 27, 42, 15 т. Тарифы перевозок сij (в ден/ед.) из (i= 1,2,3) в (j=l,..,4) приведены в матрице

него min(a1b1). Если min совпадает с A1, то запасы пункта

A1 считают исчерпанными и переходят к удовлетворению потребностей b1 начиная с ячейки А2В1.
Затем переходят к заполнению клетки А2В2. Перемещаясь так по диагонали, доходят до последней клетки АmВn. При этом все грузы будут исчерпаны, и потребности пунктов удовлетворены.
Замечание: если на некотором шаге исчерпаны запасы, то переходим к удовлетворению потребностей как это было описано выше. Если же были удовлетворены потребности, то приступают к исчерпыванию запасов аналогичным способом.

наименьшими тарифами (даже если они одинаковые) во всех строках и

столбцах, записывая их в дополнительные столбец и строку таблицы;
2. Из найденных разностей выбирают максимальную и заполняют клетку, которой соответствует данная разность.
Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям.

шаг
5
1
1
2
2
1
3
6
В
2
1
1
15
В
4
5
2
В
21
В
В
В
В
11
13
12

шаге клеток с минимальным тарифом, что даст, очевидно, меньшие суммарные

затраты на перевозку груза.

шаг
Х
15
6
12
36
36

должно выполняться условие:
Для незаполненных ячеек условие:
(причем количество заполненных ячеек в

опорном плане должно быть равно n+m-1, где m – число поставщиков, n – число потребителей)

быть заполнено 6 ячеек.
Реально заполненных ячеек тоже 6.

v4 = 5
u2 + v2 = 8
u2 + v3 =

13
u3 + v1 = 6
u3 + v3 = 12

Полагая u1 = 0, найдем:

Так как v2 = 7, то

v2 = 7

v4 = 5

u2 = 1

Так как u2 = 1, то

v3 = 12

Так как v3 = 12, то

u3 = 0

Так как u3 = 0, то

v1 = 6

Итак, u1 = 0, u2 = 1, u3 = 0, v1 = 6, v2 = 7, v3 = 12, v4 = 5

≤ C11 = 13 +
План X1 не оптимальный, поэтому

необходимо перераспределение грузов

u1 = 0, u2 = 1, u3 = 0,
v1 = 6, v2 = 7, v3 = 12, v4 = 5

u1 + v3 = 12 > C13 = 11 (1)

u2 + v1 = 7 ≤ C21 = 11 +

u2 + v4 = 6 ≤ C24 = 7 +

u3 + v2 = 7 ≤ C32 = 10 +

u3 + v4 = 5 ≤ C34 = 9 +

находятся в заполненных ячейках, кроме одной. Это одна вершина должна

находиться в незаполненной ячейке, для которой ui + vj > Cij.

При этом звенья ломанной должны удовлетворять следующим условиям:
Параллельность строкам и столбцам
В каждой строке и каждом столбце не более двух вершин

11
Всем вершинам ломанной припишем + или –, начиная с проблемной ячейки:

из всех чисел в отрицательных клетках цикла.
Циклический сдвиг
Min (15,36)=15
Новый план:
Сдвиг

по циклу: Во все положительные клетки прибавляем , из отрицательных – вычитаем .

Проверим новый план на оптимальность

v4 = 5
u2 + v2 = 8
u2 + v3 =

13
u3 + v1 = 6
u3 + v3 = 12

Полагая u1 = 0, найдем:

Так как v3 = 11, то

v3 = 11

v4 = 5

u2 = 2

Так как u2 = 2, то

v2 = 6

Так как v3 = 11, то

u3 = 1

Так как u3 = 1, то

v1 = 5

Итак, u1 = 0, u2 = 2, u3 = 1, v1 = 5, v2 = 6, v3 = 11, v4 = 5

≤ C11 = 13 +
План X2 оптимальный
u1 = 0,

u2 = 2, u3 = 1,
v1 = 5, v2 = 6, v3 = 11, v4 = 5

u1 + v2 = 6 ≤ C12 = 7 +

u2 + v1 = 7 ≤ C21 = 11 +

u2 + v4 = 7 ≤ C24 = 7 +

u3 + v2 = 7 ≤ C32 = 10 +

u3 + v4 = 6 ≤ C34 = 9 +

- Математическое моделирование: учебное пособие/ВолгГТУ, - Волгоград, 2008.
Конюховский П.В. Математические

методы исследования операций в экономике – СПб: Питер, 2000.