Решение. Составим развернутую экономико-математическую модель данной задачи

Составим развернутую экономико-математическую модель данной задачи. Модель задачи открытая. Чтобы привести ее к закрытому виду, вводим фиктивный севооборот №5 с потребностью в минеральных удобрениях 125 тонн (600-475=125). Себестоимость перевозок для фиктивного севооборота принимается равной нулю.

В результате получена следующая задача линейного программирования.

Найти минимум функции:

F = 4*X11+2*X12+3*X13+1*X14+0*X15+3*X21+6*X22+2*X23+

+5X24+0*X25+6*X32+4*X33+2*X34+0*X35

при условиях:

А) ограничения по запасам

X11+X12+X13+X14+X15=200

X21+X22+X23+X24+X25=150

X31+X32+X33X34+X35=250

Б) ограничения по потребностям

X11+X21+X31=100

X12+X22+X32=150

X13+X23+X33=150

X14+X24+X34=75

X15+X25+X35=125

В) условие неотрицательности

X11, X12, ….,X35 >=0

Первый опорный план для решения транспортной задачи можно составить несколькими способами. Наиболее распространенным для машинного счета является диагональный метод, или метод северно-западного угла.

-6-

Первый план

Склад	Севооборот	Запасы мин.уд, тонн
	№1	№2	№3	№4	№5
Vj Ui			-2	-4	-6
№1		4 100 -	100 +
№2		+	50 -
№3
Потребность, тонн

Особенность этого метода заключается в том, что распределение начинается с левой верхней, то есть северо-западной, клетки (1-1) независимо от величины удельных издержек по маршрутам. В этой задаче в первую клетку записывают 100 тонн. Это тот объем минеральных удобрений, который требуется для озимых первого севооборота. На первом складе после этого осталось еще 100 тонн, которые планируется вывезти на поля второго севооборота (записывают в клетку (1-2)). Запасы первого склада использованы полностью и в то же время потребность полей второго севооборота не удовлетворена. Поэтому недостающие 50 тонн можно перевезти со второго склада (записывают в клетку (2-2)). Теперь потребности второго севооборота полностью удовлетворены, но на втором складе осталось в наличии еще 100 тонн удобрений, которые передаются третьему севообороту и записываются в клетку (2-3). Запасы второго склада исчерпаны, а третьему севообороту требуется еще 50 т удобрений, которые планируется доставить с третьего склада. За счет запасов этого же склада удовлетворяются потребности четвертого севооборота в количестве 75 тонн, после чего там остается в избытке еще 125 тонн, которые записываются в фиктивный севооборот в клетку (3-5).

Таким образом, все запасы распределены и все потребности удовлетворены. Получен первый допустимый план при следующих значениях неизвестных:

Х11=100, Х12=100, Х22=50, Х23=100, Х33=50, Х34=75, Х35=125

Значение остальных неизвестных равно нулю.

Значение ЦФ при этом равно:

F = 4*100+2*100+6*50+2*100+4*50+2*75+0*125=1450 руб.

Для проверки правильности распределения ресурсов и удовлетворения потребностей необходимо суммировать объем перевозок как по строкам, так и по столбцам. После этого план проверяют на оптимальность. Для этого необходимо иметь количество клеток равным (m+n-1). В случае, когда их оказывается меньше, план является вырожденным. Для преодоления вырожденности одну из свободных клеток считают условно занятой и проставляют в ней перевозки Xij=0. При этом надо следить за тем, чтобы условно занятая клетка не образовывала с другими занятыми клетками замкнутых контуров. В данной задаче число занятых клеток равно 7 (3+5-1).

-7-

Для определения оптимального плана транспортной задачи будем использовать метод потенциалов.

Рассчитаем потенциалы клеток Ui и Vj, которые для занятых клеток определяются по формуле Ui + Vj = Сij и записываются в специальный столбец и строку таблицы.

Задав одной из неизвестных Ui или Vj произвольное значение (например, Ui=0), находим все Ui и Vj. Так, U1+V1=С11, откуда V1=C11-U1=4-0=4 и т.д.

После определения потенциалов план исследуется на оптимальность. Для этого по свободным клеткам рассчитывают величину Lij=Cij-(Vj+Ui), которая указывает экономию или перерасход по сравнению с предыдущим планом при перемещении единицы груза в данную клетку. Если все величины Lij будут положительными или равными нулю, то план оптимален, если же имеются и отрицательные величины, то план не оптимален и его надо улучшать.

Рассчитаем Lij для нашей задачи:

L21 = C21 - (V1+U2) = 3-(4+4) = -5;

L31 = C31 - (V1+U3) = 6-(4+6) = -4;

L32 = C32 - (V2+U3) = 3-(2+6) = -5;

L13 = C13 - (V3+U1) = 3-(-2+0) = 5;

L14 = C14 - (V4+U1) = 1-(-4+0) = 5;

L24 = C24 - (V4+U2) = 5-(-4+4) = 5;

L15 = C15 - (V5+U1) = 0-(-6+0) = 6;

L25 = C25 - (V5+U2) = 0-(-6+4) = 2.

План не оптимален. Для его улучшения среди отрицательных значений Lij берут клетку с наибольшим по абсолютной величине значением и строят из нее замкнутый контур или цепочку. В данном примере можно взять или клетку (2-1), или (3-2), в которых значения Lij равны –5. Одна вершина контура должна лежать в этой свободной клетке, остальные – только в занятых клетках. Число вершин всегда должно быть четное. В вершине свободной клетки всегда ставится «+», в остальных клетках знаки «+» и «-» чередуются.

В клетках с отрицательными вершинами выбирается наименьший объем перевозок, который вычитается из всех объемов перевозок по клеткам, имеющим отрицательные вершины контура, и прибавляется к объемам перевозок по клеткам с положительными вершинами контура. Отрицательные вершины контура расположены в клетках (1-1) с объемом перевозок равным 100 т и (2-2) – с объемом перевозок равным 50 т. Следовательно, меньший объем в клетках с отрицательными вершинами контура равен 50. Этот объем вычитаем из клеток (1-1) и (2-2), прибавляем к клеткам (2-1) и (1-2) и записываем в новую таблицу.

В новой таблице проверяется объем ограничений по строкам и столбцам.

Суммарные издержки на перевозку при таком плане равны:

F=4*50+2*150+3*50+2*100+4*50+2*75+0*125=1200 руб., что на 250 руб. меньше, чем в первоначальном плане.

Составленный таким образом план снова проверяется на оптимальность и вся вычислительная процедура повторяется. Приравняв U1 к нулю, рассчитывают все Ui и Vj для занятых клеток и записывают в таблицу.

-8-

Второй план

Склад	Севооборот	Запасы мин.уд, тонн
	№1	№2	№3	№4	№5
Vj Ui					-1
№1		4 50 -		+
№2	-1	50 +		100-
№3
Потребность, тонн

Затем проверяют план на оптимальность путем определения Lij для свободных клеток:

L31 = C31 - (V3+U1) = 6-(4+1) = 1;

L22 = C22 - (V2+U2) = 6-(2-1) = 5;

L32 = C32 - (V2+U3) = 3-(2+1) = 0;

L13 = C13 - (V3+U1) = 3-(3+0) = 0;

L14 = C14 - (V4+U1) = 1-(1+0) = 0;

L24 = C24 - (V4+U2) = 5-(1-1) = 5;

L15 = C15 - (V5+U1) = 0-(-1+0) = 1;

L25 = C25 - (V5+U2) = 0-(-1-1) = 2.

Все значения Lij неотрицательны. Следовательно, план оптимален.

Вывод. По оптимальному плану на поля первого севооборота 50 т должны поступить с первого склада и 50 т - со второго. Потребности полей второго севооборота должны полностью удовлетворяться за счет первого склада. Для третьего севооборота 100 т должны поступить со второго склада и 50 т – с третьего. Потребности четвертого севооборота полностью удовлетворяются за счет поставок с третьего склада. Кроме того, на третьем складе остаются неиспользованными 125 т минеральных удобрений, которые записаны по фиктивному севообороту.

При анализе оптимального решения видно, что не везде соблюдены минимальные издержки для отдельных севооборотов. Так, для первого севооборота только половина потребности удовлетворена за счет наименьших издержек на перевозки – 3 руб/т. Вторая же половина потребности удовлетворена при более высоких издержках – 4 руб/т. Для четвертого севооборота была бы желательной перевозка с первого склада – 1 руб/т, однако его потребности полностью удовлетворены за счет третьего склада – по 2 руб/т. Это оказалось выгодным с точки зрения общих затрат на перевозку удобрений.

-9-

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

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

В оптимальном плане данной задачи четыре свободные клетки имеют нулевые значения Lij. Возьмем одну из них – клетку (1-3), построим для нее контур и сделаем изменения в плане по общему правилу. Получим новый план перевозок, у которого общая сумма транспортных затрат не изменилась.

F=3*100+2*150+3*50+2*50+4*50+2*75+0*125=1200 руб.

Третий план