На трех складах (I, II, III) имеются соответственно 12, 18, 25 тонн однородного груза,

На трех складах (I, II, III) имеются соответственно 12, 18, 25 тонн однородного груза, который надо перевезти пяти потребителям (1,2,3,4,5) соответственно в количестве 13, 15, 12, 10, 5 тонн. Необходимо составить оптимальный план перевозки груза, если стоимость 1 тонны потребителям 1,2,3,4,5 со склада I равна соответственно 20, 10, 30, 22, 28 рублей, со склада II – 20, 31, 35, 19, 25 рублям, со склада III – 32, 35, 24, 18, 20 рублей.

Таблица 2
B1 B2 B3 B4 B5 ai (Запасы)
A1 20
10 30 22 28 12
A2 20
31 35 19 25 18
A3 32
35 24 18 20 25
Bj (Потребности) 13 15 12 10 5

a=12+18+25=55;
b= 13+15+12+10+5=55 .
a =b= 55.
Следовательно, модель задачи – закрытая. Заполним первоначальную таблицу методом минимального элемента.
x12 = min(12,15) = 12;
x34 = min(25,10) = 10;
x21 = min(18,13) = 13;
x35 = min(15,5) = 5;
x33 = min(10,12) = 10;
x22 = min(5,3) = 3;
x23 = min(2,2) = 2.
Получим первый опорный план:
Таблица 3
B1 B2 B3 B4 B5 ai (Запасы)
A1 20
10
12 30 22 28 12
A2 20
13 31
3 35
2 19 25 18
A3 32
35 24
10 18
10 20
5 25
Bj (Потребности) 13 15 12 10 5 55
Таким образом, все потребности удовлетворены и все запасы исчерпаны. Проверим, является ли план, составленный методом минимального элемента опорным, т.е. число базисных (заполненных) клеток должно быть m+n-1 = 7. Действительно, решение является опорным, так как базисных клеток в таблице 7.
Минимальные затраты при первом опорном плане составят:
F1= 12*10+13*20+3*31+2*35+10*24+10*18+5*20 = 1063 руб.
Рассмотрим метод потенциалов для проверки плана перевозок на оптимальность и поиск перевозок с минимальной суммарной стоимостью

.
Проверим план на оптимальность методом потенциалов и при необходимости улучшим его.
Ui+Vj=CBij (Заполненные клетки)
u1 + v2 = 10; u1 = 0; v1 = -1;u2 + v1 = 20; u2 = 21; v2 = 10;
u2 + v2 = 31; u3 = 10; v3 = 14;u2 + v3 = 35; v4 = 8;u3 + v3 = 24; v5 = 10;
u3 + v4 = 18;
u3 + v5 = 20.
Занесем значения u1, u2, u3, v1, v2, v3, v4, v5 в таблицу 4 и посчитаем оценки.
Таблица 4
B1 B2 B3 B4 B5 ai (Запасы) ai (Потенциалы)
A1 20
10
12 30 22 28 12 0
A2 20
13 31
3 35
2 19 25 18 21
A3 32
35 24
10 18
10 20
5 25 10
Bj (Потребности) 13 15 12 10 5 55
Bj (Потенциалы) -1 10 14 8 10
∆Cij=Ui+Vj-CBij ≤ 0 (Пустые клетки)
11 = 0 - 1 – 20 = – 21 <0;
13 = 0 + 14 – 30 = -16 <0;
14 = 0 + 8 – 22 = -14 <0;
15 = 0 + 10 – 28 = -18 <0;
24 = 21 + 8 – 19 = 10 > 0;
25 = 21 + 10 – 25 = 6 > 0;
31 = 10 - 1 – 32 = -23 <0;
32 = 10 + 10 – 35 = -15 <0.
План не оптимален, т.к