11-20. Имеются три пункта отправления однородного груза и пять пунктов его назначения. На пунктах

11-20. Имеются три пункта отправления однородного груза и пять пунктов его назначения. На пунктах груз находится в количестве единиц соответственно. В пункты требуется доставить соответственно единиц груза. Тарифы на перевозку груза между пунктами отправления и назначения приведены в матрице . Составить план перевозок, при котором общие затраты на перевозку грузов будут минимальными. Указание: для решения задачи использовать методы минимальной стоимости и потенциалов.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 B4 B5 Запасы
A1 9 1 1 7 6 90
A2 6 4 7 8 9 30
A3 2 9 3 5 3 110
Потребности 10 60 50 40 70
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 90 + 30 + 110 = 230
∑b = 10 + 60 + 50 + 40 + 70 = 230
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Этап I. Поиск первого опорного плана.
Наименьший элемент равен c12=1. Для этого элемента запасы равны 90, потребности 60. Поскольку минимальным является 60, то вычитаем его.
x12 = min(90,60) = 60.
9 1 1 7 6 90 - 60 = 30
6 x 7 8 9 30
2 x 3 5 3 110
10 60 - 60 = 0 50 40 70
Наименьший элемент равен c13=1. Для этого элемента запасы равны 30, потребности 50. Поскольку минимальным является 30, то вычитаем его.
x13 = min(30,50) = 30.
x 1 1 x x 30 - 30 = 0
6 x 7 8 9 30
2 x 3 5 3 110
10 0 50 - 30 = 20 40 70
Наименьший элемент равен c31=2. Для этого элемента запасы равны 110, потребности 10. Поскольку минимальным является 10, то вычитаем его.
x31 = min(110,10) = 10.
x 1 1 x x 0
x x 7 8 9 30
2 x 3 5 3 110 - 10 = 100
10 - 10 = 0 0 20 40 70
Наименьший элемент равен c33=3

. Для этого элемента запасы равны 100, потребности 20. Поскольку минимальным является 20, то вычитаем его.
x33 = min(100,20) = 20.
x 1 1 x x 0
x x x 8 9 30
2 x 3 5 3 100 - 20 = 80
0 0 20 - 20 = 0 40 70
Наименьший элемент равен c35=3. Для этого элемента запасы равны 80, потребности 70. Поскольку минимальным является 70, то вычитаем его.
x35 = min(80,70) = 70.
x 1 1 x x 0
x x x 8 x 30
2 x 3 5 3 80 - 70 = 10
0 0 0 40 70 - 70 = 0
Наименьший элемент равен c34=5. Для этого элемента запасы равны 10, потребности 40. Поскольку минимальным является 10, то вычитаем его.
x34 = min(10,40) = 10.
x 1 1 x x 0
x x x 8 x 30
2 x 3 5 3 10 - 10 = 0
0 0 0 40 - 10 = 30 0
Наименьший элемент равен c24=8. Для этого элемента запасы равны 30, потребности 30. Поскольку минимальным является 30, то вычитаем его.
x24 = min(30,30) = 30.
x 1 1 x x 0
x x x 8 x 30 - 30 = 0
2 x 3 5 3 0
0 0 0 30 - 30 = 0 0
B1 B2 B3 B4 B5 Запасы
A1 9 1[60] 1[30] 7 6 90
A2 6 4 7 8[30] 9 30
A3 2[10] 9 3[20] 5[10] 3[70] 110
Потребности 10 60 50 40 70
В результате получен первый опорный план, который является допустимым.
F(x) = 1 · 60 + 1 · 30 + 8 · 30 + 2 · 10 + 3 · 20 + 5 · 10 + 3 · 70 = 670
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана