Баланса )

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

Следовательно, число независимых (базисных) переменных в модели:

r = m + n – 1 = 3 + 2 – 1 =4

Число свободных переменных:

k = m*n – (m + n – 1) = (m – 1)(n – 1) = 1*2 = 2

Это задача линейного программирования, когда a_ij = 1 (или 0).Задачи такого типа называют транспортными задачами линейного программирования.

Общий вид транспортной задачи

Минимизировать целевую функцию: Транспортная задача при

Организации

тылового обеспечения.

(1)

При условии баланса:

При ограничениях:

i=1,m Полный вывоз ресурсов

От всех отправителей.

(2)

j=1,n Полное обеспечение всех

Получателей

При всех (3)

I и j

МЕТОД ПОТЕНЦИАЛОВ. Часть I.

(Построение начального плана Х₀

по правилу северо - западного угла )

МЕТОД ПОТЕНЦИАЛОВ. Часть II.

(Итерации: Х₀ ® Х₁ ® Х₂ ®...® Х^* )

1) Расчет потенциалов V_j и U_i для базисных переменных текущего плана:

	Vj - Ui = Ci j

 

2) Расчет оценок свободных переменных текущего плана:

	Dks = Cks + Uk - Vs

 

3) Ответ на вопрос “План оптимален?”

“Да”, если все D_ks >= 0; “Нет” - переход к пункту 4.

 

4) Определение вводимой в базис свободной переменной

(среди свободных переменных выбирается переменная с min D_ks).

Выделение (+) и штриховкой клетки вводимой свободной переменной.

 

5) Построение замкнутого цикла через вводимую свободную переменную.

Цикл начинается и заканчивается в клетке вводимой свободной переменной.

Состоит из горизонтальных и вертикальных прямых, которые в клетках

базисных переменных меняют свое направление на 90 градусов.

 

6) В точках излома цикла ставятся (+) или (-).

 

7) Определение выводимой базисной переменной

(среди базисных переменных с (-) выбирается переменная с min значением).

М = min (из значений переменных с “-”).

 

8) Переход к следующему плану:

- переменным цикла с (+) + М;

- переменным цикла с (-) - М.

 

9) Расчет целевой функции нового плана.

 

Решение задачи методом потенциалов

Часть I. Построение начального плана (Х₀ ).

Часть II. Итерации (Х₁ → Х₂ → Х₃ →... → Х^*).

 

Часть I. Построение начального плана по правилу северо-западного угла.

 

План № 1	ПОЛУЧАТЕЛИ	Базисные переменные:
			X11, X12, X22, X23,
		V1=10	V2=12	V3=10	Свободные переменные:
								X13, X21,
ПОС
ТАВ	U1 = 0	X11		X12		X13		a1=17 / 2 / 0
ЩИ
КИ
	U2 = 5	X21		X22		X23		a2=23 / 10 / 0
		b1=15 / 0	b2=15/	b3=10 / 0
			13 / 0

Начальный (опорный) план № 1: L₁ = 15*10 + 2*12 + 13*7 + 10*5 = 315

V_j, U_i – оценочные величины (потенциалы), связанные со стоимостями перевозок. Позволяют определить – какую свободную переменную лучше ввести в базисное решение, а какую старую базисную переменную вывести из базисного решения.

Часть II. Итерации. < 1 итерация > (Х₁ → Х₂).

План № 1	ПОЛУЧАТЕЛИ	Базисные переменные:
	V1=10	V2=12	V3=10	X11, X12, X22, X23,
						Свободные переменные:
ПОС								X13, X21,
ТАВ	U1 = 0	X11		X12		X13		a1=17
ЩИ
КИ
	U2 = 5	X21		X22		X23		a2=23
	b1=15	b2=15	b3=10

Vj – Ui = Cij

1) Расчет потенциалов V_j, U_i для базисных переменных плана № 1.

U₁ = 0^*

V₁ – U₁ = 10 V₁ = 10 Переменных - 5

V₂ – U₁ = 12 V₂ = 12 Уравнений - 4

V₁, V₂, V₃, U₁, U₂ V₂ – U₂ = 7 U₂ = 5 *( Любую из переменных

V₃ – U₂ = 5 V₃ = 10 можем приравнять к 0 )

 

Dks = Crs + Uks -Vs

2) Расчет оценок свободных переменных текущего плана

D₁₃ = 8 + 0 – 10 = -2

D₂₁ = 4 + 5 – 10 = -1