Имеется m поставщиков А1, А2,…, Аm , располагающих некоторым однородным грузом в объемах по аi единиц ( ), и n потребителей В1, В2,…, Вn с объемами потребления по bj единиц ( ). Задана матрица C=||cij||, где cij– стоимость перевозки единицы груза от i-го поставщика j-му потребителю. Требуется составить план перевозок Х=||хij||, где хij( ; ) – количество единиц груза, поставляемое от i-го поставщика j-му потребителю, при котором суммарные транспортные издержки будут минимизированы.Предполагается, что xij ³ 0 ( ; ). Условие задачи записано в виде таблицы.
Поставщики
Потребители
Запасы
груза аi
B1
B2
B3
B4
A1
а1 = 90
A2
а2= 110
A3
а3 = 160
Потребность
в грузе bj
b1 = 140
b2 = 50
b3 = 110
b4 = 60
Суммарные запасы поставщиков равны суммарному спросу потребителей, что составляет 360 единиц (т. е. выполняется условие общего баланса ). Следовательно, данная задача является задачей закрытого типа.
Математическую модель транспортной задачи сформулируем следующим образом.
Требуется найти план перевозок
при котором суммарные затраты на перевозку груза от поставщиков к потребителям будут минимальными:
на спрос потребителей, который должен быть полностью удовлетворен:
x11 + x21 + x31 = 140; x12 + x22 + x32 = 50;
x13 + x23 + x33 = 110; x14 + x24 + x34 = 50;
условия неотрицательности, исключающие обратные перевозки
Построим начальный план перевозок методом минимальной стоимости (таблица 1). Назначение перевозок начинаем с клетки (1; 4), имеющей минимальную стоимость перевозки. В клетку (1; 4) записываем наименьшее из значений a1 и b4х14 = min (90, 60) = 60 и исключаем из дальнейшего рассмотрения четвертый столбец. Вычеркнув четвертый столбец, корректируем запасы первого поставщика на величину x14 = 60, a1 = 90 – 60 = 30.
В оставшейся таблице снова выбираем клетку с минимальной стоимостью перевозки. Это клетка (3; 3). От третьего поставщика к третьему потребителю назначаем перевозку х33 =min (160; 110) = 110. Из дальнейшего рассмотрения исключаем третьего потребителя. Корректируем запасы третьего поставщика a3 = 160 – 110 = 50.
Таблица 1 – План перевозок, построенный методом минимальной стоимости
Поставщики
Потребители
Мощность
поставщиков
а1 = 90, 30
а2 = 110, 90
а3 = 160, 50
Спрос
потребителей
b1 = 140, 90
b2 = 50, 20
b3 = 110
b4 = 60
Построенный начальный план перевозок является базисным, так как число назначенных перевозок xij равно m+n–1=6. Значение целевой функции при начальном плане перевозок:
Построение оптимального плана методом потенциалов.
Вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках.
Если известен ui, то vj = cij+ ui, если известен vj, то ui = vj – cij. Положим, например, u1 = 0. Тогда будут вычислены и остальные потенциалы строк и столбцов (таблица 2).
Таблица 2– Начальный план перевозок
vj ui
v1= 12
v2= 8
v3= 9
v4= 5
u1= 0
u2= –2
–
+
u3= 3
+
–
Для незагруженных клеток вычислим величины превышения стоимости Dij = vj – ui – cij :
Поскольку среди оценок Dij имеются положительные, то полученный план неоптимален. Выбираем клетку с наибольшим значением Dij. Это клетка (2; 3). От клетки (2, 3) строим замкнутый контур: (2; 3), (2; 1), (3; 1), (3; 3). Начиная с клетки (2, 3), разметим вершины контура попеременно знаками плюс «+», минус «–», обходя замкнутый контур в любом направлении. Из клеток, помеченных знаком «–», выбираем наименьшее значение объема перевозки l = min (90, 110) = 90. Сформируем новый улучшенный план перевозок: на 80 единиц увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком « – ».
Новый улучшенный план перевозок представлен в таблице 3.
Таблица 3 – Улучшенный методом потенциалов план перевозок
vj ui
v1= 9
v2= 8
v3= 6
v4= 4
u1= 0
u2= –2
u3= 0
Значение целевой функции при улучшенном плане перевозок:
Среди оценок свободных клеток нет положительных, следовательно, построенный план перевозок является оптимальным:
Значение целевой функции при оптимальном плане z(X*) = 2840 д.е.
Для того чтобы общие затраты на перевозки были минимальными, рекомендуется придерживаться полученного оптимального плана X* (см. таблицу 3). В этом случае суммарные затраты будут минимальны и составят 2840 д.е.
), и n потребителей В1, В2,…, Вn с объемами потребления по bj единиц ( 
). Задана матрица C=||cij||, где cij– стоимость перевозки единицы груза от i-го поставщика j-му потребителю. Требуется составить план перевозок Х=||хij||, где хij( 
; 
). Следовательно, данная задача является задачей закрытого типа.
