На трех базах А1 А2 А3 имеется однородный груз в количестве
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
На трех базах А1, А2, А3, имеется однородный груз в количестве: 280 т – на базе А1, 220 т – на базе А2, 300 т – на базе А3. Полученный груз требуется перевезти в пять пунктов: 190 т – в пункт B1, 140 т – в пункт B2, 180 т – в пункт B3, 120 т – в пункт B4, 170 т – в пункт B5.
Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С:
С = 73915353101220461511161946.
где Сij – стоимость перевозки 1 т груза от поставщика под номером i (i=1,2,3) к потребителю под номером j (j=1,2,3,4,5), в тыс. руб.
Составить математическую модель задачи. Спланировать перевозки так, чтобы их общая стоимость была минимальной. При нахождении оптимального плана использовать метод потенциалов.
Нужно полное решение этой работы?
Ответ
минимальные затраты составят 12220 тыс. руб. при оптимальном плане:
0110 0 0 170190030 0 0030150120 0.
Решение
Построим математическую модель
Целевая функция:
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.
План не оптимален, т.к
Задать вопрос
на новый заказ в Автор24.
