. Транспортная задача линейного программирования 1. Составить математическую модель транспортной задачи. 2. Найти оптимальный план перевозок, минимизирующий общие затраты на перевозки (тарифы на перевозку единицы продукции, объёмы запасов продукции на складах, а также объёмы заказанной продукции представлены в таблице). (Решение → 10536)

заказ №38669

. Транспортная задача линейного программирования 1. Составить математическую модель транспортной задачи. 2. Найти оптимальный план перевозок, минимизирующий общие затраты на перевозки (тарифы на перевозку единицы продукции, объёмы запасов продукции на складах, а также объёмы заказанной продукции представлены в таблице). Магазин Склад “Росстек” “Шер” “Ткани” “Мода” “Вита” Запасы на складе (ед.прод) Иваново 12 14 32 20 3 54 Москва 8 10 12 24 12 32 268 Новгород 6 8 12 24 8 85 Серпухов 10 18 4 8 9 162 Объём заказа (ед.прод) 100 70 30 45 50

Решение

: 1. Построим экономико-математическую модель представленной транспортной задачи. Переменными транспортной задачи являются xij – объемы перевозов от каждого i-го поставщика каждому j-му потребителю. Так как запасы всех поставщиков вывозятся полностью, то этот факт можно описать следующими уравнениями: 162 85 32 54 41 42 43 44 45 31 32 33 34 35 21 22 23 24 25 11 12 13 14 15                     x x x x x x x x x x x x x x x x x x x x Общий объем запасов 54+32+85+162 = 333. Так как требуется полностью удовлетворить запросы всех потребителей, то составим следующие уравнения: 50 45 30 70 100 15 25 35 45 14 24 34 44 13 23 33 43 12 22 32 42 11 21 31 41                     x x x x x x x x x x x x x x x x x x x x Общие потребности 100+70+30+45+50=295. Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести дополнительное ограничение: 0 ij x  269 Целевая функция задачи выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов: 6 8 12 24 8 10 18 4 8 9 min 12 14 32 20 3 8 10 12 24 12 31 32 33 34 35 41 42 43 44 45 11 12 13 14 14 21 22 23 24 25                       x x x x x x x x x x F x x x x x x x x x x Итак, мы получили задачу минимизации транспортных затрат: 6 8 12 24 8 10 18 4 8 9 min 12 14 32 20 3 8 10 12 24 12 31 32 33 34 35 41 42 43 44 45 11 12 13 14 14 21 22 23 24 25                       x x x x x x x x x x F x x x x x x x x x x 0 50 45 30 70 100 162 85 32 54 15 25 35 45 14 24 34 44 13 23 33 43 12 22 32 42 11 21 31 41 41 42 43 44 45 31 32 33 34 35 21 22 23 24 25 11 12 13 14 15                                                         ij x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x Задача имеет открытую форму (объем поставок не равен спросу), то введем фиктивной магазин с объемом заказа 333 – 295 = 38 и нулевыми стоимостями перевозки. Найдем оптимальный план методом наименьшей стоимости. Количество заполненных клеток должно быть равно m+n – 1 = 4+6 – 1 = 9. 270 Магазин Склад “Росстек” “Шер” “Ткани” “Мода” “Вита” Фикт. Запасы  Иваново 12 4 14 32 20 50 3 0 54 1 =–4 Москва 15 – 8 17 + 10 12 24 12 0 32 2 = –8 Новгород 85 6 8 12 24 8 0 85 3 =–10 Серпухов + 10 49 – 18 30 4 45 8 9 38 0 162 4= 0 Заказ 100 70 30 45 50 38 =333 β β1= 16 β2= 18 β3= 4 β5= 8 β5= 7 β5=0 Вычислим затраты на перевозку при этом плане: F1 = 4∙14+50∙3+15∙8+17∙10+85∙6+49∙18+30∙4+45∙8= 2368 Проверим на оптимальность методом потенциалов найденный план. Введем потенциалы , β и найдем их. Для заполненных клеток должно выполняться условие: i + βj = cij, положим 4=0 1 1 2 2 1 5 3 2 1 4 2 2 1 3 1 2 4 2 3 4 3 4 4 4 5 4 6 6 4 14 8 3 10 8 0 10 16 6 18 18 4 4 8 8 7 0 0                                                                                 Проверим условие для пустых клеток по теореме двойственности: i j ij     c с11 = –4+16 = 12 с24 = –8+8 < 24 с34 = –10+8 < 24 271 с13 = –4+4 < 32 с25 = –8+7 < 12 с35 = –10+7 < 8 с14 = –4+8 < 20 с26 = –8+0 < 0 с36 = –10+0 < 0 с16 = –4+0 < 0 с32 = –10+18 < 8 с41 = 0+16 > 10 с23 = –8+4 < 12 с33 = –10+4 < 12 с45 = 0+7 < 9 Найденный план не является оптимальным. В клетку (4,1) поставим знак «+» и построим цикл. В итоге получим новый план: Магазин Склад “Росстек” “Шер” “Ткани” “Мода” “Вита” Фикт. Запасы  Иваново 12 4 14 32 20 50 3 0 54 1 =–4 Москва 8 32 10 12 24 12 0 32 2 = –8 Новгород 85 – 6 + 8 12 24 8 0 85 3 =–4 Серпухов 15 + 10 34 – 18 30 4 45 8 9 38 0 162 4= 0 Заказ 100 70 30 45 50 38 =333 β β1= 10 β2= 18 β3= 4 β5= 8 β5= 7 β5=0 Вычислим затраты на перевозку при этом плане: F2 = 4∙14+50∙3+32∙10+85∙6+15∙10+34∙18+30∙4+45∙8= 2278