Задача минимизации транспортных расходов
Пусть имеется три пункта А 1, А 2, А 3, на которых сосредоточены запасы товара в количестве соответственно 250, 400 и 350 условных единиц. Имеется пять пунктов потребления В 1, В 2, В 3, В 4 и В 5, подавшие заявки соответственно на 300, 160, 220, 180 и 140 единиц товара. Известны стоимости Сi,j перевозки единицы товара от каждого пункта отправления Аi до каждого пункта назначения Вj.
Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы - вывезти весь хранящийся на базах запас товара; - все заявки были выполнены; - общая стоимость всех перевозок была минимальна.
Обозначим через xij количество товара, направляемого из пункта Аi в пункт Вj (i = 1,2,3; j = 1,2,3,4,5). Таким образом, в задаче имеется 3 x 5 оптимизируемых переменных, и план в транспортной задаче имеет вид х = (х 11, х 12,…, х 35 ).
Составим уравнения, определяющие множество допустимых планов
Построим критериальную функцию : Е(х) = с 11 х 11 + с 12 х 12 + с 13 х 13 + с 14 х 14 + с 15 х 15. Е(х) min
Условия задачи зададим таблицей : В1В1 В2В2 В3В3 В4В4 В5В5 Запас ы а i А1А А2А А3А Заявки b j
В1 В1 В2 В2 В3 В3 В4В4 В5В5 Запасы а i А А А Заявки b j Будем заполнять таблицу, используя метод минимальной стоимости по строке.
План перевозок: Х 1 = (110,0,0,0,140,0,0,220,180,0,190,160,0,0,0 ) Стоимость плана Х 1 : Е 1 (х) = = 9* * * * * *160 =
В1 В1 В2 В2 В3 В3 В4В4 В5В5 Запасы а i А А А Заявки b j Способ минимальной стоимости по столбцу аналогичен предыдущему способу.
План перевозок Х 2 = (250,50,0,0,0,160,0,220,0,0,130,50,0,0,140) Стоимость плана Х 2 : Е 2 (х) = = 9* * * * * *50+ 25*140 =
В1 В1 В2 В2 В3 В3 В4В4 В5В5 Запас ы а i А А А Заявки b j Способ минимальной стоимости по всей таблице аналогичен предыдущим способам:
План перевозок Х 3 = (250,0,0,0,0,0,0,80,180,140,50,160,140,0,0) Стоимость плана Х 3 : Е 3 (х) = = 9* * * * * * *140 = =15 470
План, составленный способами минимальных стоимостей, обычно близок к оптимальному решению. В нашем примере общие затраты на транспортировку по плану, составленному первым способом Е 1 (х) = , по второму Е 2 (х) = 14360, по третьему Е 3 (х) = Выбираем план Е 2 (х) =