Транспортная задача линейного программирования
На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.
Таблица 4
Поставщик Потребитель Запасы
B1 B2 B3 B4
A1 1 1 2 4 20
A2 5 4 1 3 40
A3 2 6 4 1 70
Потребность 10 25 58 37
Решение:
Проверим балансовое условие:
i=13Ai=20+40+70=130;
i=14Bi=10+25+58+37=130.
Балансовое условие выполняется. Следовательно, задача является закрытой.
Исходные данные введем в таблицу:
Таблица 5
Поставщики -565151841600Bj
Ai Потребители
B1 =10 B2 = 25 B3 = 58 B4 = 37
A1 = 20 1 1 2 4
A2 = 40 5 4 1 3
A3 = 70 2 6 4 1
Начальный опорный план перевозок построим методом минимальной стоимости затрат на перевозку.
Начальный опорный план
Таблица 6
B1 =10 B2 = 25 B3 = 58 B4 = 37
A1 = 20 10 10 – –
A2 = 40 – – 40 –
A3 = 70 – 15 18 37
Из табл. 6 виден опорный план перевозок
X1=101000004000151837
Проверим на оптимальность составленный план перевозок. Для этого составим систему уравнений:
u1 + v1 = 1;
u1 + v2 = 1;
u2 + v3 = 1; u3 + v2 = 6; u3 + v3 = 4; u3 + v4 = 1.
Находим решение данной системы:
u1 = 0 v1 = 1 v2 = 1 u3 = 5 v3 = -1 v4 = -4 u2 = 2.
Т.е u1 = 0, u2 = 2, u3 = 5, v1 = 1, v2 = 1, v3 = -1, v4 = -4.
Для каждой свободной клетки табл. 5 вычислим разности:
∆ij=Vj-Ui-Сij
13 = -1-0-2= -3 <0; 22 = 1-2-4= -7 <0;
14 = -4-0-4= -9 <0 ; 24 = -4-2-3= -9 <0;
21 = 1-2-5= -6 <0 ; 31 = 1-5-2= -8 <0.
Т. к. все ∆ij≤0, то полученный опорный план является оптимальным.
Вычисляем для него значение целевой функции:
Z = 1*10 + 1*10 + 1*40 + 6*15 + 4*18 + 1*37 = 259 у.е
т.е. наименьшие затраты равны 410 у.е.
