На трех базах А1 А2 А3 имеется однородный груз в количестве

Построим математическую модель
Целевая функция:
F(x) = 7x11 + 3x12 + 9x13 + 15x14 + 35x15 + 3x21 + 10x22 + 12x23 + 20x24 + 46x25 + 15x31 + 11x32 + 16x33 + 19x34 + 46x35 → min
Переменные:x11 – количество груза с 1-ой базы в 1-й пункт.x12 – количество груза с 1-ой базы во 2-й пункт.x13 – количество груза с 1-ой базы в 3-й пункт.x14 – количество груза с 1-ой базы в 4-й пункт.x15 – количество груза с 1-ой базы в 5-й пункт.x21 – количество груза со 2-ой базы в 1-й пункт.x22 – количество груза со 2-ой базы во 2-й пункт.x23 – количество груза со 2-ой базы в 3-й пункт.x24 – количество груза со 2-ой базы в 4-й пункт.x25 – количество груза со 2-ой базы в 5-й пункт.x31 – количество груза с 3-ей базы в 1-й пункт.x32 – количество груза с 3-ей базы во 2-й пункт.x33 – количество груза с 3-ей базы в 3-й пункт.x34 – количество груза с 3-ей базы в 4-й пункт.x35 – количество груза с 3-ей базы в 5-й пункт.
Ограничения по запасам:x11 + x12 + x13 + x14 + x15 = 280 (для 1 базы)x21 + x22 + x23 + x24 + x25 = 220 (для 2 базы)x31 + x32 + x33 + x34 + x35 = 300 (для 3 базы)
Ограничения по потребностям:x11 + x21 + x31 = 190 (для 1-го пункта)x12 + x22 + x32 = 140 (для 2-го пункта)x13 + x23 + x33 = 180 (для 3-го пункта)x14 + x24 + x34 = 120 (для 4-го пункта)x15 + x25 + x35 = 170 (для 5-го пункта)
Запишем условия в виде таблицы:
Таблица 8
B1 B2 B3 B4 B5 ai (Запасы)
A1 7
3 9 15 35 280
A2 3
10 12 20 46 220
A3 15
11 16 19 46 300
Bj (Потребности) 190 140 180 120 170 800
a=280+220+300=800;
b= 190+140+180+120+170=800 .
a =b= 800.
Следовательно, модель задачи – закрытая. Заполним первоначальную таблицу методом минимального элемента.
x12 = min(280,140) = 140;
x21 = min(220,190) = 190;
x13 = min(140,180) = 140;
x23 = min(30,40) = 30;
x33 = min(300,10) = 10;
x34 = min(290,120) = 120;
x35 = min(170,170) = 170.
Получим первый опорный план:
Таблица 9
B1 B2 B3 B4 B5 ai (Запасы)
A1 7
3
140 9
140 15 35 280
A2 3
190 10 12
30 20 46 220
A3 15
11 16
10 19
120 46
170 300
Bj (Потребности) 190 140 180 120 170 800
Таким образом, все потребности удовлетворены и все запасы исчерпаны . Проверим, является ли план, составленный методом минимального элемента опорным, т.е. число базисных (заполненных) клеток должно быть m+n-1 = 7. Действительно, решение является опорным, так как базисных клеток в таблице 7.
Минимальные затраты при первом опорном плане составят:
F(x) = 3*140 + 9*140 + 3*190 + 12*30 + 16*10 + 19*120 + 46*170 = 12870 тыс. руб.
Рассмотрим метод потенциалов для проверки плана перевозок на оптимальность и поиск перевозок с минимальной суммарной стоимостью.
Проверим план на оптимальность методом потенциалов и при необходимости улучшим его.
Ui+Vj=CBij (Заполненные клетки)
u1 + v2 = 3; u1 = 0; v1 = 0;u1 + v3 = 9; u2 = 3; v2 = 3;
u2 + v1 = 3; u3 = 7; v3 = 9;u2 + v3 = 12; v4 = 12;u3 + v3 = 16; v5 = 39;
u3 + v4 = 19;
u3 + v5 = 46.
Занесем значения u1, u2, u3, v1, v2, v3, v4, v5 в таблицу 10 и посчитаем оценки.
Таблица 10
B1 B2 B3 B4 B5 ai (Запасы) ai (Потенциалы)
A1 7
3
140 9
140 15 35 280 0
A2 3
190 10 12
30 20 46 220 3
A3 15
11 16
10 19
120 46
170 300 7
Bj (Потребности) 190 140 180 120 170 800
Bj (Потенциалы) 0 3 9 12 39
∆Cij=Ui+Vj-CBij ≤ 0 (Пустые клетки)
11 = 0 + 0 – 7 = -7 <0;
14 = 0 + 12 – 15 = -3 <0;
15 = 0 + 39 – 35 = 4 >0;
22 = 3 + 3 -10 = -4 <0;
24 = 3 + 12 -20 = -5 <0;
25 = 3 + 39 -46 = -4 <0;
31 = 7 + 0 – 15 = -8<0;
32 = 7 + 3 – 11 = -1<0.
План не оптимален, т.к