Методика расчета транспортной задачи линейного программирования

Постановка задачи. Имеется   т  поставщиков   однородного   груза:   А1, А2, .. Аi,   где   i=1,   2,...,   т.   Груз перевозится  потребителям. В1, B2,…Bj, гдеj=1, 2,..., n.

Каждый поставщик производит продукцию в количестве аi, каждому потребителю необходимо привести груз в количестве вj; поставщики и потребители соединяются между собой транспортными связями, с известной стоимостью перевозки от i-того поставщика j-тому потребителю.

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

Фактически требуется определить объёмы перевозок -хij.   от i-того поставщика к j-тому потребителю:

F=Sm.i=1*Sn.j=1Cij*xij==min. 2 знака сумм сразу перед С …где m,n – пишутся снизу, i=1, j=1 снизу под значками сумм

Целевая функция ограничена следующими условиями:

- потребности потребителей должны полностью удовлетворяться;

- по поставщикам:   Sm.i=1xij=вj, где j=1,2,…,n;

от каждого поставщика груз должен вывозитсяполностью: Sm.i=1xij=аi, где i=1,2,…,m;

объёмы производства в сумме должны быть равны объёму потребления:

Sm.i=1аi=Sn.j=1вj, (где перед а и в значки сумм, м и n пишутся сверху i=1,j=1  пишется снизу)

Это ограничение является условием задачи закрытого типа. В случае когда это условие не выполняется, задача называется транспортной задачей линейного программирования открытого типа и она сводится к задаче закрытого типа путём введения дополнительного или фиктивного поставщика или потребителя. Стоимость перевозки от таких поставщиков (потребителей) или к ним принимается равной нулю.

Рассмотрим решение ТЗЛП методом потенциалов.

1.   Наиболее   простой   метод   построения   начального плана перевозок - метод „северо-западного угла".

2.   Проверить получившийся план на оптимальность:

F1=100*2+20*3+120*6+10*8+90*9+110*5=2420 (S- ые затраты на перевозки(значок суммы))

Для проверки плана строится система потенциалов условное число, которое присваивается каждой строке и каждому столбцу матрицы (каждому поставщику, каждому потребителю). Первый нулевой потенциал присваивается строке, содержащей занятую ячейку с максимальной стоимостью среди всех занятых клеток.

Остальные потенциалы рассчитываются по формуле:

Vj=Ui+Cij, где Vj - потенциал столбца (потребителя); Ui - потенциал строки (поставщика); Cij - стоимость перевозки в занятой клетке.

Ui=Vj-Cij,

Потенциал рассчитывается только для занятых клеток.

3.  Просчитать положительную сдвижку для свободных клеток

yij=Vj-Ui-Cij,

Если для всех свободных клеток получена отрицательная или равная нулю сдвижка, т.е. у < 0,то это будет означать, что получен оптимальный план, в противном случае требуется улучшение плана до оптимального.

Для этого выберем клетку с максимальной положительной сдвижкой. В нашем случае имеются две свободные клетки с положительными сдвижками: y12=7-2-4=1и y13=9-3-2 = 4.

Остальные сдвижки  будут отрицательными: y14=5-6-2 =-3,  у24= 5-7 -1 = -3,

y31 =4-5-0 = -1,   у32  =7-10-0 = -3. (вместо y писать греческую гамму) Выбирается  клетка  с  максимальной  положительной сдвижкой. Из найденной клетки построим замкнутый контур по двум условиям (в данном примере такая клетка 1.3):

1.   вершины контура должны находится в занятых клетках;

2.   рёбра контура должны быть параллельны строке и столбцам матрицы.

Обозначить вершины контура попеременно „+" и „-" начиная с исходной вершины. Среди отрицательных вершин найти минимальный объём перевозок и вычесть его из отрицательных вершин, и прибавить к положительным. В результате перераспределения перевозок получаем новый план.

Эти операции необходимо выполнять до тех пор, пока не будет получен оптимальный план перевозок.

F2 =90*2+ 10*3+ 70*3 + 120*6+ 90*9 +110*5 = 2380

y12=11-4-6=1;    y14=5-6-6= -7

y23=9-8-5=-4;      y24=5-7=-7

y31=8-5-0=3;        y32=11-10-0=1 (вместо y писать греческую гамму)

F3=100*3+30*3+ 120*6 + 90*5+110*5 = 2110

y11=5-2-3=0;   y12=8-4-3=1;     y14=5-6-3=-4

y23=6-8-2= -4; y24=5-7-5=-7;    y32=8-10-0=-2

y33=6-9-0=-3

Если затруднительно построить потенциалы для строк и столбцов ставят фиктивную перевозку для которой известен потенциал строки или столбца в которой объём перевозок минимален, перераспределение (фиктивной нулевой перевозки не приведёт к изменению перевозок, следовательно полученный план является оптимальным).