Решить двухэтапную производственно-транспортную задачу

Составляем рабочую таблицу представления числовых данных нашей транспортной задачи:
Склады Базы потребителя
D1 D2 B1 B2 B3 B4
d1=50 d2=50 b1=20 b2=40 b3=10 b4=30
Пункты производства A1 a1=10
5
2
M
M
M
M
A2 a2=40
3
6
M
M
M
M
A3 a3=50
4
3
M
M
M
M
Склады D1 d1=50
0
M
2
4
5
3
D2 d2=50
M
0
5
7
2
6
Рабочая таблица состоит из четырёх блоков. В первом блоке (слева вверху) отражаются связи предприятий, производящих продукцию, со складами, где хранится изготовленная продукция перед отправкой ее потребителю. Во втором блоке (справа вверху) отражаются связи предприятий с базами потребителя готовой продукции. Поскольку потребителям необходима только готовая продукция, эти связи запрещаются тарифами М → ∞. Третий блок (слева внизу) образуется строками и столбцами, относящимися к складам. Продукция между складами не перевозится, поэтому связи складов друг с другом блокируются запретительными тарифами М. При этом диагональ третьего блока заполняется нулевыми тарифами. Благодаря этому перевозки, которые здесь могут появиться, будут означать размер неиспользованной мощности соответствующего склада. Фактически перевозки, указанные в этой диагонали, не осуществляются, то есть они являются фиктивными (поэтому и сама диагональ называется фиктивной). В четвёртом блоке (справа внизу) отражаются связи складов с базами потребителя готовой продукции.
Выполняем первоначальное распределение перевозок X(0) методом минимального тарифа .
Начинаем с четвертого блока.
а). Наименьший тариф 2 в ячейках (D1, B1) и (D2, B3). Выбираем произвольно и назначаем xD1B1 = 20. Столбец B1 исключаем. Остаток d1 = 30.
б). Наименьший тариф 2 в ячейке (D2, B3). Назначаем xD2B3 = 10. Столбец B3 исключаем. Остаток d2 = 40.
в). Наименьший тариф 3 в ячейке (D1, B4). Назначаем xD1B4 = 30. Столбец B4 исключаем. Остаток d1 = 0.
г). Заполняем незаполненную ячейку (D2, B2) остатком xD2B2 = 40. Остаток d2 = 0.
Теперь заполняем фиктивную диагональ. Так как остатки d1 = 0 и d2 = 0, то есть мощности складов использованы полностью, то назначаем xD1D1 = 0 и xD2D2 = 0.
Переходим к первому блоку.
а). Наименьший тариф 2 в ячейке (A1, D2). Назначаем xA1D2 = 10. Строку A1 исключаем. Остаток d2 = 40.
б). Наименьший тариф 3 в ячейках (A2, D1) и (A3, D2). Выбираем произвольно и назначаем xA2D1 = 40. Строку A2 исключаем. Остаток d1 = 10.
в). Заполняем оставшиеся незаполненными ячейки (A3, D1) и (A3, D2) остатками xA3D1 = 10, xA3D2 = 40.
Все перевозки распределены.
Первоначальное распределение перевозок X(0) транспортной задачи, составленное по методу минимального тарифа, имеет вид:
Склады Базы потребителя
X(0)
D1 D2 B1 B2 B3 B4
d1=50 d2=50 b1=20 b2=40 b3=10 b4=30
Пункты производства A1 a1=10
5
2
M
M
M
M
10
A2 a2=40
3
6
M
M
M
M
40
A3 a3=50
4
3
M
M
M
M
10
40
Склады D1 d1=50
0
M
2
4
5
3
0
20
30
D2 d2=50
M
0
5
7
2
6
0
40
10
Распределение перевозок содержит m + n – 1 = 5 + 6 – 1 = 10 занятых клеток, следовательно, опорное решение – невырожденное