Минимизировать расходы на доставку продукции заказчикам со складов фирмы

Обозначим через Xij – количество груза, которое необходимо перевезти от i-го поставщика (склада) к j-му потребителю (магазину).
i = 1, 2, 3;
j = 1, 2, 3, 4.
Составим экономико-математическую модель задачи.
Переменные:
X11 – объем груза, перевозимого c I склада в магазин № 1, ед.;
Х12 – объем груза, перевозимого c I склада в магазин № 2, ед.;
Х13 – объем груза, перевозимого c I склада в магазин № 3, ед.;
X14 – объем груза, перевозимого c I склада в магазин № 4, ед.;
X21 – объем груза, перевозимого cо II склада в магазин № 1, ед.;
Х22 – объем груза, перевозимого cо II склада в магазин № 2, ед.;
Х23 – объем груза, перевозимого cо II склада в магазин № 3, ед.;
X24 – объем груза, перевозимого cо II склада в магазин № 4, ед.;
X31 – объем груза, перевозимого c III склада в магазин № 1, ед.;
Х32 – объем груза, перевозимого c III склада в магазин № 2, ед.;
Х33 – объем груза, перевозимого c III склада в магазин № 3, ед.;
X34 – объем груза, перевозимого c III склада в магазин № 4, ед.;
Ограничения:
по возможности I склада, ед. х11 + х12 + х13+ х14 = 400;
по возможности II склада, ед. х21 + х22 + х23+ х24 = 1200;
по возможности III склада, тх31 + х32 + х33+ х34 = 500.
по потребности магазина № 1, ед. х11 + х21+ х31 = 1000;
по потребности магазина № 2, ед. х12 + х22+ х32 = 550;
по потребности магазина № 3, ед. х13 + х23+ х33 = 490;
по потребности магазина № 4, ед. х14 + х24+ х34 = 60.
Целевая функция:
F(x) = 15х11 + 7х12 + 11х13 + 4х14 + 6х21 + 4х22 + 12х23 + 8х24 +
+ 7х31 + 11х32 + 5х33 + 10х34→min.
Вначале определяется исходный вариант перевозок, а затем последовательно производится его улучшение до получения оптимального плана.
Для получения исходного плана перевозок используем правило «северо-западного» угла. Заполнение клеток таблицы ведём в направлении от верхней левой до нижней правой (таблица 6). То есть, за счёт ресурсов первого поставщика удовлетворяются потребности первого потребителя (заполняется клетка 1.1). Если ресурс больше, чем потребность первого потребителя, то за счёт остатка удовлетворяются потребности второго потребителя (заполняется клетка 1.2). Если же ресурса первого поставщика недостаточно, то недостающая часть берётся у второго поставщика (заполняется клетка 2.1). Так постепенно распределяются ресурсы всех поставщиков. Следуя этому правилу, получим опорный план, представленный в таблице 6.
Таблица 6 – Исходный план перевозок
Склады Магазины Запас
Qi
№ 1 № 2 № 3 № 4
I 15
400 7
х 11
х 4
х 400
II 6
600 4
550 12
50 8
х 1200
III 7
х 11
х 5
440 10
60 500
Спрос bj
1000 550 490 60 2100=2100
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
х11 = 400 ед.; х21 = 600 ед.; х22 = 550 ед.; х23 = 50 ед.; х33 =440 ед.; х34 = 60 ед.
F(x) = 15*400 + 6*600 + 4*550 + 12*50 + 5*440 + 10*60 = 15200 ден . ед.
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
По алгоритму решения следует каждую свободную клетку проверить на оптимальность. Для этого по каждой строке и столбцу определяют потенциалы занятых клеток по формуле:
Ui +Vj = Cij, (2)
гдеVj – потенциал столбца
Ui – потенциал строки
Cij – тариф (показатель) занятой клетки
Расчёт потенциалов начинаем с того, что один из них приравниваем к нулю (U1 = 0).
U1 + V1 = 15; 0 + V1 = 15; V1 = 15;
U2 + V1 = 6; 15 + U2 = 6; U2 = -9;
U2 + V2 = 4; -9 + V2 = 4; V2 = 13;
U2 + V3 = 12; -9 + V3 = 12; V3 = 21;
U3 + V3 = 5; 21 + U3 = 5; U3 = -16;
U3 + V4 = 10; -16 + V4 = 10; V4 = 26.
Для свободных клеток определяются характеристики по формуле (3):
Dij = Cij - (Ui+ Vj),(3)
где Dij – характеристика свободной клетки.
D12 = 7-(0+13) = -6;
D13 = 11-(0+21) = -10;
D14 = 4-(0+26) = -22;
D24 = 8-(-9+26) = -9;
D31 = 7-(-16+15) = 8;
D32 = 11-(-16+13) = 14.
Отрицательные характеристики при решении задач на min указывают на то, что транспортные расходы могут быть снижены, т.е. план не оптимальный. Улучшается план за счет клетки с отрицательной характеристикой. Так как получено несколько отрицательных характеристик, то выбирается клетка, имеющая наименьшую отрицательную характеристику:
max(-6,-10,-22,-9) = -22
Выбираем свободную клетку (1;4). Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 7 – Исходный план перевозок
Склады Магазины Запас
Qi
№ 1 № 2 № 3 № 4
I 15
400 [-] 7
х 11
х 4
х [+] 400
II 6
600 [+] 4
550 12
50 [-] 8
х 1200
III 7
х 11
х 5
440 [+] 10
60 [-] 500
Спрос bj
1000 550 490 60 2100=2100
Просматривая объемы в отрицательных вершинах (60; 50; 400) выбираем наименьший (50). Далее производим сдвиг по циклу. Выбранный объем (50) к объемам в положительных вершинах прибавляем, а от объемов в отрицательных вершинах вычитаем.
Таблица 8 – Второй план перевозок
Склады Магазины Запас
Qi
№ 1 № 2 № 3 № 4
I 15
350 7
х 11
х 4
50 400
II 6
650 4
550 12
х 8
х 1200
III 7
х 11
х 5
490 10
10 500
Спрос bj
1000 550 490 60 2100=2100
х11 = 350 ед.; х14 = 50 ед.; х21 = 650 ед.; х22 = 550 ед.; х33 =490 ед.; х34 = 10 ед.
F(x) = 15*350 + 4*50 + 6*650 + 4*550 + 5*490 + 10*10 = 14 100 ден