Решение. Согласно указанию 1) требуется минимизировать стоимость перевозок (суммарные затраты) S = S dijxij. Далее расстояние dij будем обозначать через cij и называть тарифом.

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

П Б						a_i
	7 50	1 40	7	4	9
	4	3 20	2 50	1 0	5	2
	5	6	8	6 40	2 70	7
b_j	7	1	0	-1	-5

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

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

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 – (2+7)= - 5;

s₃₁ = 5 – (7+7)= - 9; s₃₂ = 6 – (7+1)= - 2.

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

Выбираем клетку ( 3 , 1 ) с наименьшей из отрицательных алгебраических сумм тарифов - 9 и строим цикл пересчета для получения нового базисного решения.

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

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

П Б						a_i
	7 30	1 60	7	4	9
	4	3	2 50	1 20	5	-7
	5 20	6	8	6 20	2 70	- 2
b_j	7	1	9	8	4

s₁₃ = 7 – (0+9)= - 2; s₁₄ = 4 – (0+8)= - 4;

П Б						a_i
	7 10	1 60	7	4 20	9
	4	3	2 50	1 20	5	-3
	5 40	6	8	6	2 70	-2
b_j	7	1	5	4	4

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

Наименьшие суммарные затраты S_min = S c_ijx_ij = 10 · 7 + 60 · 1 + 20 · 4 + 50 ·2 + 20 · 1 + 40 · 5 + 70 · 2 = 670

Замечание. Данное решение не является единственным , так как клетка (2, 1 ) имеет

s₂₁ = 4 – (-3+7)= 0 .

- нулевая алгебраическая сумма тарифов.

С помощью цикла пересчета клетки (2, 1 ) можно получить еще одно оптимальное решение.

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

⇐ Предыдущая 1 234 5 Следующая ⇒