Решение транспортной задачи симплекс методом

Решение Транспортной задачи симплекс методом

Количество груза у поставщиков (ai):

Начало формы

a1= a2= a3= a4=

Потребности потребителей (bi):

b1= b2= b3=

Матрица транспортных издержек перевозки из i-го пункта отправления в j-й пункт потребления



C1,1= C2,1= C3,1=

C1,2= C2,2= C3,2=

C1,3= C2,3= C3,3=

C1,4= C2,4= C3,4=

Решение Транспортной задачи симплекс методом

Исходные данные:

Запас груза в i-м пункте отправления ai: a1=300, a2=350, a3=150, a4=200.

Потребность j-го пункта назначения в грузе bj: b1=400, b2=400, b3=200.

Матрица тарифов (транспортных расходов) Ci,j:

Составим математическую модель задачи транспортного типа. Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функцией

Переменные Xk должны удовлетворять ограничениям по запасам (1), по потребностям (2), и условиям неотрицательности. В математической записи это можно представить так:

Целевая функция:

4X1+1X2+2X3+3X4+4X5+2X6+1X7+3X8+1X9+1X10+4X11+3X12→min

Условия:

1X1+1X2+1X3+0X4+0X5+0X6+0X7+0X8+0X9+0X10+0X11+0X12=300
0X1+0X2+0X3+1X4+1X5+1X6+0X7+0X8+0X9+0X10+0X11+0X12=350
0X1+0X2+0X3+0X4+0X5+0X6+1X7+1X8+1X9+0X10+0X11+0X12=150
0X1+0X2+0X3+0X4+0X5+0X6+0X7+0X8+0X9+1X10+1X11+1X12=200
1X1+0X2+0X3+1X4+0X5+0X6+1X7+0X8+0X9+1X10+0X11+0X12=400
0X1+1X2+0X3+0X4+1X5+0X6+0X7+1X8+0X9+0X10+1X11+0X12=400
0X1+0X2+1X3+0X4+0X5+1X6+0X7+0X8+1X9+0X10+0X11+1X12=200

Транспортная задача разрешима только в случае, если соблюдается условие баланса Σai=Σbi. В нашем случае оно выполняется, так как:

Σai=300+350+150+200=1000
Σbi=400+400+200=1000
Следовательно задача является закрытой (сбалансированой).

Приведем систему ограничений к каноническому виду, для этого введем в каждое условие искусственную переменную R. Тогда система запишется в виде:

1X1+1X2+1X3+0X4+0X5+0X6+0X7+0X8+0X9+0X10+0X11+0X12+R1=300
0X1+0X2+0X3+1X4+1X5+1X6+0X7+0X8+0X9+0X10+0X11+0X12+R2=350
0X1+0X2+0X3+0X4+0X5+0X6+1X7+1X8+1X9+0X10+0X11+0X12+R3=150
0X1+0X2+0X3+0X4+0X5+0X6+0X7+0X8+0X9+1X10+1X11+1X12+R4=200
1X1+0X2+0X3+1X4+0X5+0X6+1X7+0X8+0X9+1X10+0X11+0X12+R5=400
0X1+1X2+0X3+0X4+1X5+0X6+0X7+1X8+0X9+0X10+1X11+0X12+R6=400
0X1+0X2+1X3+0X4+0X5+1X6+0X7+0X8+1X9+0X10+0X11+1X12+R7=200

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции.

Так как среди исходного набора условий были равенства, мы ввели искуственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой расчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.

Из данных задачи составляем исходную симплекс таблицу.

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решениеВ строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 1.

В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R5, а ведущий элемент: 1.

В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R2, а ведущий элемент: 1.