Решите транспортную задачу линейного программирования Имеются три пункта поставки однородного груза А1, А2, А3 и

Решите транспортную задачу линейного программирования Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов потребления этого груза B1, B 2, B 3, B 4, B 5. На пунктах поставки Аi, i=1,3 находится груз соответственно в количествах а1, а2 и а3 тонн. В пункты потребления Bj, j=1,5 требуется доставить соответственно b1, b 2, b3, b4, b5 тонн груза. Расходы на перевозку единицы груза между пунктами поставки и пунктами потребления приведены в таблице. Найти такой план закрепления потребителей за поставщиками однородного груза xij, i=1,3; j=1,5, чтобы общие затраты по перевозкам были минимальными. Таблица 1 B1 B2 B3 B4 B5 Запасы A1 15 8 5 21 15 150 A2 4 12 7 8 10 200 A3 11 20 13 4 5 200 Потребности 100 180 40 120 110 550

A=150+200+200=550;
b= 100+180+40+120+110=550 .
a =b= 550.
Следовательно, модель задачи – закрытая. Заполним первоначальную таблицу методом минимального элемента.
x21 = min(200;100) = 100;
x34 = min(200;120) = 120;
x13 = min(150;40) = 40;
x35 = min(80;110) = 80;
x12 = min(110;180) = 110;
x25 = min(100;30) = 30;
x22 = min(70;70) = 70.
Получим первый опорный план:
Таблица 2
B1 B2 B3 B4 B5 Запасы
A1 15
8
110 5
40 21 15 150
A2 4
100 12
70 7 8 10
30 200
A3 11
20 13 4
120 5
80 200
Потребности 100 180 40 120 110 550
Таким образом, все потребности удовлетворены и все запасы исчерпаны. Проверим, является ли план, составленный методом минимального элемента опорным, т.е. число базисных (заполненных) клеток должно быть m+n-1 = 7.
Действительно, решение является опорным, так как базисных клеток в таблице - 7.
Минимальные затраты при первом опорном плане составят:
F(x) = 110*8 + 40*5 + 100*4 + 70*12 + 30*10 + 120*4 + 80*5 = 3500 ден.ед.
Рассмотрим метод потенциалов для проверки плана перевозок на оптимальность и поиск перевозок с минимальной суммарной стоимостью.
Проверим план на оптимальность методом потенциалов и при необходимости улучшим его.
Ui+Vj=CBij (Заполненные клетки)
u1 + v2 = 8; u1 = 0; v1 = 0;u1 + v3 = 5; u2 = 4; v2 = 8;
u2 + v1 = 4; u3 = -1; v3 = 5;u2 + v2 = 12; v4 = 5;u2 + v5 = 10; v5 = 6;
u3 + v4 = 4;
u3 + v5 = 5.
Занесем значения u1, u2, u3, v1, v2, v3, v4, v5 в таблицу 3 и посчитаем оценки.
Таблица 3
B1 B2 B3 B4 B5 Запасы ai (Потенциалы)
A1 15
+40-127014351082551435108
110 -40685801435105
40 21 15 150 0
A2 4
100 -1778018351512
-40 70 7
+40 8 10
30 200 4
A3 11
20 13 4
120 5
80 200 -1
Потребности 100 180 40 120 110 550
Bj (Потенциалы) 0 8 5 5 6
∆Cij=Ui+Vj-CBij ≤ 0 (Пустые клетки)
11 = 0 + 0 – 15 = -15 <0;
14 = 0 + 5 – 21 = -16 <0;
15 = 0 + 6 – 15 = -9 <0;
23 = 4 + 5 – 7 = 2 >0;
24 = 4 + 5 – 8 = 1 >0;
31 = -1 + 0 – 11 = -12 <0;
32 = -1 + 8 – 20 = -13 <0;
33 = -1 + 5 – 13 = -9<0.
План не оптимален, т.к

. есть значение ij >0. Следовательно, улучшим план.
Выбираем максимальное значение из полученных оценок: max(2;1) = 2. Следовательно, выбираем клетку x23. Ставим в этой клетке «+» и рисуем цикл.
Цикл пересчета (2;3) → (2;2) → (1;2) → (1;3).
Отобразим цикл в таблице 3.
372808531242040 5
0040 5
366649022606000
17678408889900129603429908500920115-43180110 8
00110 8
834390-12001500 +40 -40
41598844127500
36823652781300083439027813000
375856511430- 7
00- 7
1767840179069009201154508570 12
0070 12
-40 +40
Min(70,40) = 40. (Смотрим на значения в минусовых клетках и выбираем из них наименьшее значение).
Прибавляем и вычитаем «40» в ячейках цикла и формируем новую таблицу 4.
Таблица 4
B1 B2 B3 B4 B5 Запасы ai (Потенциалы)
A1 15
8
150 5
21 15 150 0
A2 4
100 12
30 7
40 -2349517906900+30-44451485908 -301219201581150010
30 200 4
A3 11
20 13 -42545174624004
-30 120 5
+30 80
200 -1
Потребности 100 180 40 120 110 550
Bj (Потенциалы) 0 8 3 5 6
Проверим план на оптимальность методом потенциалов и при необходимости улучшим его