У компании «Транспо» есть пять складов, с которых она отгружает продукцию в пять торговых точек. В приведенных ниже таблице указан спрос на продукцию, запас продукции для каждого склада и стоимость транспортировки одной единицы продукции со складов в торговые точки:
Транспортные издержки
D1 D2 D3 D4 D5
S1 14 6 5 12 17
S2 13 10 3 15 14
S3 15 13 11 7 9
S4 12 17 4 12 14
S5 18 12 11 4 8
Заказы потребителей
Заказчик D1 D2 D3 D4 D5
Кол- во 90 50 180 200 210
Запасы на складах
Поставщик S1 S2 S3 S4 S5
Кол-во 250 350 300 450 150
Сбалансируйте задачу и сформулируйте математическую модель задачи. Постройте начальный опорный план методом северо-западного угла и методом наименьшей стоимости. Какой из планов лучше? (Объясните ответ). Решите задачу методом потенциалов.
Ответ
Минимальные затраты на перевозку составляют 4760 у.ед при оптимальном плане:
Xопт0500 0 0 20000180 0 0 1700900000000 50 0 150210 40 0 3600 0.
Решение
Проверим баланс задачи:
i=0nSi=250+350+300+450+150=1500;
j=0mDj=90+50+180+200+210=730;
i=0nSi≠j=0mDj→задача является несбалансированной.
Суммарные запасы превышают суммарные потребности. Тогда необходимо добавить дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть:
Dф=i=0nSi-j=0mDj=1500-730=770.
Следовательно, добавляем фиктивный столбец D6 с количеством заказов потребителей в размере 770.
Составим экономико-математическую модель задачи:
Переменные:x11 – количество груза с 1-го склада в 1-ю торговую точку;x12 – количество груза с 1-го склада во 2-ю торговую точку;x13 – количество груза с 1-го склада в 3-ю торговую точку;x14 – количество груза с 1-го склада в 4-ю торговую точку;x15 – количество груза с 1-го склада в 5-ю торговую точку;
x16 – количество груза с 1-го склада в 6-ю торговую точку;x21 – количество груза со 2-го склада в 1-ю торговую точку;x22 – количество груза со 2-го склада во 2-ю торговую точку;x23 – количество груза со 2-го склада в 3-ю торговую точку;x24 – количество груза со 2-го склада в 4-ю торговую точку;x25 – количество груза со 2-го склада в 5-ю торговую точку;
x26 – количество груза со 2-го склада в 6-ю торговую точку;x31 – количество груза с 3-го склада в 1-ю торговую точку;x32 – количество груза с 3-го склада во 2-ю торговую точку;x33 – количество груза с 3-го склада в 3-ю торговую точку;x34 – количество груза с 3-го склада в 4-ю торговую точку;x35 – количество груза с 3-го склада в 5-ю торговую точку;
x36 – количество груза с 3-го склада в 6-ю торговую точку;
x41 – количество груза с 4-го склада в 1-ю торговую точку;x42 – количество груза с 4-го склада во 2-ю торговую точку;x43 – количество груза с 4-го склада в 3-ю торговую точку;x44 – количество груза с 4-го склада в 4-ю торговую точку;x45 – количество груза с 4-го склада в 5-ю торговую точку;
x46 – количество груза с 4-го склада в 6-ю торговую точку;x51 – количество груза с 5-го склада в 1-ю торговую точку;x52 – количество груза с 5-го склада во 2-ю торговую точку;x53 – количество груза с 5-го склада в 3-ю торговую точку;x54 – количество груза с 5-го склада в 4-ю торговую точку;x55 – количество груза с 5-го склада в 5-ю торговую точку;
x56 – количество груза с 5-го склада в 6-ю торговую точку.
Целевая функция:
F(x) = 14x11 + 6x12 + 5x13 + 12x14 + 17x15 + 13x21 + 10x22 + 3x23 + 15x24 + 14x25 +15x31 + 13x32 + 11x33 + 7x34 + 9x35 +12x41 + 17x42 + 4x43 + 12x44 + 14x45 + 18x51 + 12x52 + 11x53 + 4x54 + 8x55 → min
Ограничения по запасам на складах:x11 + x12 + x13 + x14 + x15 + x16 = 250 (для 1-го склада);x21 + x22 + x23 + x24 + x25 + x26 = 350 (для 2-го склада);x31 + x32 + x33 + x34 + x35 + x36 = 300 (для 3-го склада);
x41 + x42 + x43 + x44 + x45 + x46 = 450 (для 4-го склада);x51 + x52 + x53 + x54 + x55 + x56 = 150 (для 5-го склада).
Ограничения по заказам потребителей:x11 + x21 + x31 + x41 + x51 = 90 (для 1-й торговой точки);x12 + x22 + x32 + x42 + x52 = 50 (для 2-ой торговой точки);x13 + x23 + x33 + x43 + x53 = 180 (для 3-ей торговой точки);x14 + x24 + x34 + x44 + x54 = 200 (для 4-ой торговой точки);x15 + x25 + x35 + x45 + x55 = 210 (для 5-ой торговой точки);
x16 + x26 + x36 + x46 + x56 = 770 (для 6-ой торговой точки).
Условия неотрицательности:
xij≥0,j=1,5, i=1,6
.
Таким образом, математическая модель примет вид:
F(x) = 14x11 + 6x12 + 5x13 + 12x14 + 17x15 + 13x21 + 10x22 + 3x23 + 15x24 + 14x25 +15x31 + 13x32 + 11x33 + 7x34 + 9x35 +12x41 + 17x42 + 4x43 + 12x44 + 14x45 + 18x51 + 12x52 + 11x53 + 4x54 + 8x55 → min
При ограничениях:
x11 + x12 + x13 + x14 + x15 + x16 = 250; x21 + x22 + x23 + x24 + x25 + x26 = 350; x31 + x32 + x33 + x34 + x35 + x36 = 300;
x41 + x42 + x43 + x44 + x45 + x46 = 450; x51 + x52 + x53 + x54 + x55 + x56 = 150;
x11 + x21 + x31 + x41 + x51 = 90;
x12 + x22 + x32 + x42 + x52 = 50; x13 + x23 + x33 + x43 + x53 = 180; x14 + x24 + x34 + x44 + x54 = 200; x15 + x25 + x35 + x45 + x55 = 210;
x16 + x26 + x36 + x46 + x56 = 770.
xij≥0,j=1,5, i=1,6.
Представим исходные данные в виде таблицы
D1 D2 D3 D4 D5 D6 Запасы
S1 14 6 5 12 17 0 250
S2 13 10 3 15 14 0 350
S3 15 13 11 7 9 0 300
S4 12 17 4 12 14 0 450
S5 18 12 11 4 8 0 150
Потребности 90 50 180 200 210 770
Выполним построение опорного плана методом северо-западного угла
D1 D2 D3 D4 D5 D6 Запасы
S1 14
90 6
50 5
110 12
17
0
250;160;110;0
S2 13
10
3
70 15
200 14
80 0
350;280;80;0
S3 15
13 11
7
9
130 0
170 300;170;0
S4 12
17
4
12
14
0
450 450;0
S5 18
12
11
4
8
0
150 150;0
Потребности 90;0 50;0 180;70;0 200;0 210;130;0 770;600;
150;0
x11 = min(250,90) = 90;
x12 = min(160,50) = 50;
x13 = min(110,180) = 110;
x23 = min(350,70) = 70;
x24 = min(280,200) = 200;
x25 = min(80,210) = 80;
x35 = min(300,130) = 130;
x36 = min(170,770) = 170;
x46 = min(450,600) = 450;
x56 = min(150,150) = 150.
Таким образом, все потребности удовлетворены и все запасы исчерпаны
Задать вопрос
на новый заказ в Автор24.
