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

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

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

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

(9.7)

(9.8)

. (9.9)

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

Таблица 9.9

	В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 к значениям в клетках со знаком «+» и вычитая из значений в клетках со знаком «–» В результате приходим к таблице 9.10.

Таблица 9. 10

	В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. Значит, решение неоптимальное и строим в таблице 12 новый цикл пересчета для клетки (3,4). Так как min(170,40)=40=Х₃₁,то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком «+» и вычитая из значений в клетках со знаком «–». В результате получаем таблицу 9. 11.

Таблица 9. 11

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

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

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

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

Таблица 9.12

	В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.13.

Таблица 9.13

	В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 ед. потребителю В₄.

Вопросы для подготовки к экзамену