Первое базисное решение найдем по методу минимальной стоимости.

П Б						ai
		50 1
		0 4	50 5	20 5
	50 3	4		30 7	30 9
bj	-2

 

I) В клетку с минимальным тарифом c₁₂ = 1 помещаем наибольший возможный груз x₁₂ = 50, далее выбираем клетку с минимальным тарифом 3 и т.д. При распределении грузов следим за тем, чтобы на каждом шаге, кроме последнего, из рассмотрения выбывали только одна строка или столбец. В данном случае в одном из выбывающих рядов (в строке или в столбце) ставим ноль (в клетку с наименьшим тарифом 4).

II) Проверим с помощью метода потенциалов является ли полученное базисное решение оптимальным.

Составим следующие уравнения для всех базисных (загруженных) клеток:

c_ij = a_i + b_j (1)

 

Так как число уравнений m + n – 1 = 3 + 5 –1 = 7, а число потенциалов a_i, b_j равно m + n = 8, можно принять a₁ = 0. Далее находим потенциалы из следствий уравнений (1):

 

b_j = c_ij - a_i или a_i = c_ij - b_j.

 

Результаты заносим в таблицу.

Находим алгебраические суммы тарифов s_ij для всех свободных клеток из уравнений:

 

s_ij = c_ij – (a_i + b_j ) (2)

 

Запишем только s_{ij <} 0, - нарушение условия оптимальности:

 

S₃₂ = 4 – (5+1) = - 2

 

Так как не все s_ij ³ 0, то базисное решение не является оптимальным.

Выбираем клетку (3, 2) и строим цикл пересчета

0 - 20 + 20

 

 

+ 30 - 0 30

Перераспределяемый груз x_ij = min (0; 30) = 0

 

 

III) Запишем новое базисное решение в таблицу и проделаем процедуры пунктов I-II до тех пор пока не получим для всех свободных клеток s_ij ³ 0.

П Б						ai
		50 1			5
			50 5	20 5
	50 3	0 4		30 7	30 9
bj

Нарушение условия оптимальности:

S₁₅ = 5 – (0+6) = - 1

строим цикл пересчета

50- + 20 30

 

0+ 30- 30

 

Перераспределяемый груз x_ij = min (50; 30) = 30

 

 

П Б						ai
		20 1			30 5
			50 5	20 5
	50 3	30 4		30 7
bj

 

Так как для всех свободных клеток s_ij ³ 0, то последнее базисное решение является оптимальным.

Оптимальное решение не является единственным, так как

 

S₃₃ = 7 – (3+4) = 0

 

и, следовательно, с помощью клетки (3; 3) можно перейти к другому оптимальному решению.

Наименьшие суммарные затраты

 

S_min = S c_ijx_ij = 20 · 1 + 30 · 5 +50 · 5+ 20 · 5 + 50 · 3 + 30· 4 + 30· 7 =1000

 

21 - 30. Дана задача выпуклого программирования. Требуется: