Пример III

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

= .

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

РЕШЕНИЕ

Строим математическую модель задачи. Через Х_ij обозначим объем продукции, доставленной от поставщика A_i (i=l,2,3) потребителю B_j (). Отметим, что в данном случае сумма количества продукции, которую могут отгрузить все поставщики, совпадает с суммой потребностей потребителей:

310+360+230=140+190+180+170+220 = 900.

Значит, задача закрытого типа и имеет решение. Математическая модель задачи принимает вид:

(1)

(2)

. (3)

Строим начальную распределительную таблицу:

Таблица 5

	В1	В2	Вз	В4	В5	аi	Ui
А1							-4
А2	+ 3 *	– 8
A3	– 1	+ 2					-6

Построенному опорному решению отвечают затраты:

Z₁ = 90∙2+220∙1+100∙8+90∙6+170∙10+140∙1+90∙2 = 3760.

Проверим полученный опорный план на оптимальность. Для этого i-й строке и j-му столбцу ставим в соответствие числа U_i и V_j (потенциалы). Для каждой базисной переменной Х_ij потенциалы должны удовлетворять условию

Получаем систему:

U_i +V_j = С_ij.

U₁+V₃ = 2, Так как система состоит из 7 уравнений, а неизвестных

U₁+V₅ = l, 8, то, чтобы найти численное решение этой системы, U₂+V₂ = 8, одно из неизвестных зададим произвольно, тогда

U₂+V₃ = 6, остальные переменные найдутся из системы однозначно.

U₂+V₄ = 10,

U₃+V₁ = 1,

U₃+V₂ = 2.

Пусть U₂ = 0, тогда V₂ = 8, V₃ = 6, V₄ = 10, U₁ = -4, U₃ = -6, V₁ = 7, V₅ = 5.

Теперь для небазисных переменных (свободных клеток) найдем оценки

Sij = Сij –(Ui +Vj):
S11 = 5 - (-4 + 7) = 2	S21 = 3 - (0 + 7) = -4
S12 = 3 - (-4 + 8) = -1	S25 = 5 - (0 + 5) = 0
S14 = 4 - (-4 + 10) = -2	S33 = 3 - (-6 + 6) = 3
S35 = 4 - (-6 + 5) = 5	S34= 5 - (-6 + 10) = l

В силу критерия оптимальности опорного плана (все оценки S_ij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введем переменную Х₂₁ (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки " + " и " – ", начиная с (2,1), которой присваиваем знак " + ". Выбираем наименьшее значение из клеток со знаком

" – " (min (140,100) = 100) и перераспределим продукцию вдоль контура: прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком " – ". В результате приходим к таблице 6.

Таблица 6

	В1	В2	Вз	В4	В5	аi	Ui
А1							-4
А2	+ 3 100			– 10
A3	– 1			+ 5 *			-2

Полученному решению отвечают затраты:

Z₂ = 90∙2+220∙1+100∙3+90∙6+170∙10+40∙1+190∙2=3360.

Проверяем полученный план на оптимальность и получаем, что S₃₄ = -3 < 0. Значит, решение не оптимальное и строим в таблице 6 новый цикл пересчета для клетки (3,4). Так как min(170,40)=40=Х₃₁,то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком " + " и вычитая из значений в клетках со знаком " – ". В результате получаем таблицу 7.

Таблица 7

	В1	В2	Вз	В4	В5	аi	Ui
А1			– 2 –	+ 4 *			-4
А2			+ 6	– 10 130
A3		190					-5

Полученному решению отвечают затраты:

Z₃ = 90∙2+220∙l+140∙3+90∙6+130∙10+190∙2+40∙5=3240.

Аналогично предыдущему проверяем полученный план на оптимальность. Получаем, что S₁₄ = - 2 < 0. Теперь для улучшения плана загрузим клетку (1,4). В итоге приходим к таблице 8.

Таблица 8

	В1	В2	Вз	В4	В5	аi	Ui
А1				+ 4	– 1		-6
А2			б	– 10	+ 5 *
A3							-5

Z₄ = 90∙4+220∙l+140∙3+180∙6+40∙10+190∙2+40∙5=3060.

Среди оценок свободных клеток имеем S₂₅ = -2<0, следовательно, полученный план перевозок не является оптимальным, и для его улучшения необходимо загрузить клетку (2,5). В итоге вычислений приходим к таблице 9.

Таблица 9

	В1	В2	Вз	В4	В5	аi	Ui
А1							-4
А2			б
A3							-3

Z₅ = 130∙4+180∙l+140∙3+180∙6+40∙5+190∙2+40∙5=2980.

Полученный план оказывается оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану перевозок 1–й поставщик отправляет 130 ед. продукции потребителю В₄ и 180 ед. – B₅; 2–й поставщик – 140 ед. потребителю В₁, 180 ед. потребителю B₃ и 40 ед. потребителю В₅; 3–й поставщик – 190 ед. потребителю B₂ и 40 ед. потребителю В₄.