Находим верхнюю и нижнюю границу параметра x, при котором данное решение будет оставаться постоянным

Ищем оптимальное решение задачи при xравном минимальной границе

Тогда исходные данные можно представить в виде:

ai	bj					Ai
Bj

2.1 Нахождение опорного плана методом минимального тарифа.

ai	bj					Ai
Bj

F (x) = 100*7 + 80 + 70*2 + 50*4 + 50 + 50 = 1220

4+3-1=6 6=6, следовательноопорный план не вырожденный.

Запишем задачу в математической форме

Найти: F (х) → min = 5х₁₁ + 4х₁₂ + 7х₁₃ + 3х₁₄ + 1х₂₁ + 2х₂₂ + 4х₂₃ + 7х₂₄ + 2х₃₁ + 1х₃₂ + 8х₃₃ + 1х₃₄

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

5х₁₁ + 4х₁₂ + 7х₁₃ + 3х₁₄ = 100

1х₂₁ + 2х₂₂ + 4х₂₃ + 7х₂₄ = 200

2х₃₁ + 1х₃₂ + 8х₃₃ + 1х₃₄ = 100

5х₁₁ + 1х₂₁ + 2х₃₁ = 80

4х₁₂ + 2х₂₂ + 1х₃₂ = 120

7х₁₃ + 4х₂₃ + 8х₃₃ = 150

3х₁₄ + 7х₂₄ + 1х₃₄ = 50

Составим оптимальный план, используя метод потенциалов

Находим потенциалы по загруженным клеткам, предав значение одному из потенциалов равное 0.

ai	bj					Ai
		70
		50			-1
Bj

Затем находим оценки свободных клеток из условия Δ _ij= (α _i+ β _j) – с_ij

Есть две положительные оценки Δ ₁₂ = +1 и Δ ₁₄ = +2 следовательно, план не оптимальный и необходимо перераспределение поставок. Для этого выбираем свободную клетку с максимальной положительной оценкой (в данном случае клетку a₁b₄) и, принимая ее за исходную, строим замкнутый контур. Вершинам контура, начиная со свободной клетки, присваиваем поочередно знаки «+» и «-». Из клеток с минусовой загрузкой выбираем минимальную (min {50; 70; 100} = 50). Затем отнимаем эту загрузку от загрузки в клетках с «-» и прибавляем к загрузкам в клетках с «+».

Получаем новый план:

ai	bj					Ai
		4	50
		20
					-1
Bj

Снова находим оценки свободных клеток из условия Δ _ij= (α _i+ β _j) – с_ij

Среди оценок по-прежнему есть положительная Δ ₁₂ = +1, следовательно, повторяем операцию.

Получаем новый план:

ai	bj					Ai
					-3
					-3
Bj

Снова находим оценки свободных клеток из условия Δ _ij= (α _i+ β _j) – с_ij

Проверяем условие 4+3-1=6 6=6

Среди оценок свободных клеток нет положительных, следовательно план оптимальный!

F(x) = 80*1 + 20*4 + 30*7 + 50*3 + 120*4 + 100 = 1100

План является оптимальным, так как нет положительных оценок для свободных клеток, и все условия и ограничения выполняются. F (х) = 1100

Находим верхнюю и нижнюю границу параметра x, при котором данное решение будет оставаться постоянным

Условие оптимальности С_ij – (a_i+ b_j) ≥ 0

ai	bj					Ai
	5+2x	4-x		3+x
			4+2x	7-x	-3+2x
				1+3x	-3+x
Bj	4-2x	4-x		3+x

Находим оценки свободных клеток

Δ _{11 =}5+2x – (4-2x) = 1+4x max

Δ _{22 =}2 – (4-x-3+2x) = 1-x

Δ _{24 =}7-x – (3+x-3+2x) = 7-4x

Δ _{31 =}2 – (4-2x-3+x) = 1+x max

Δ _{33 =}8 – (7-3+x) = 4-x

Δ _{34 =}1+3x – (3+x-3+x) = 1+xmax

Решение будет оставаться постоянным, когда x₁≤ x≤ x₂

X₁ = max 0

∞ Vij ≤ 0

X₂ = min 0

∞ Vij ≥ 0

max (- ; -1) = 0

min (1; ; 4;) = 1

Данное решение будет оставаться постоянным, когда 0≤ x≤ 1

План будет оптимальным при данной границе
F (x) = 1100+270x

При x> 1, Δ ₂₂становится отрицательной, поэтому делаем перераспределение поставок

Новый план:

ai	bj					Ai
	5+2x	4-x	50	3+x	3-2x
		20	4+2x	7-x
				1+3x	-1
Bj			4+2x	3x

Находим оценки свободных клеток

Δ _{11 =} 5+2x – (1+3-2x) = 1+4x

Δ _{12 =} 4-x– (2+3-2x) = -1+x

Δ _{24 =} 7-x – (3x) = 7-4x

Δ _{31 =} 2 – (1-1) = 2

Δ _{33 =} 8 – (4+2x-1) = 5-2x

Δ _{34 =} 1+3x – (3x-1) = 2

max (- ; 1)

min (; )

Данное решение будет оставаться постоянным, когда 1≤ x≤

План оптимальный при данной границе

F(x) = 1120 + 250x

При x> , Δ ₂₄ становится отрицательной, поэтому делаем перераспределение поставок.

Новый план:

ai	bj					Ai
	5+2x	4-x	100	3+x	3-2x
			4+2x 50	7-x
				1+3x	-1
Bj			4+2x	7-x

Находим оценки свободных клеток

Δ _{11 =} 5+2x – (1+3-2x) = 1+4x

Δ _{12 =} 4-x– (2+3-2x) = -1+x

Δ _{14 =} 3+x – (7-x+3-2x) = -7+4x

Δ _{31 =} 2 – (1-1) = 2

Δ _{33 =} 8 – (4+2x-1) = 5-2x

Δ _{34 =} 1+3x – (7-x-1) = -5+4x

max (- ; 1; ; )

min ()

Данное решение будет оставаться постоянным, когда ≤ x≤

План оптимальный при данной границе

F (x) = 1470 + 50x

При x> , Δ ₃₃становится отрицательной, поэтому делаем перераспределение поставок.

Новый план:

ai	bj					Ai
	5+2x	4-x		3+x	-2
		70	4+2x	7-x
		50		1+3x	-1
Bj				7-x

Находим оценки свободных клеток

Δ _{11 =} 5+2x – (1-2) =6+2x

Δ _{12 =} 4-x– (2-2) = 4-x

Δ _{14 =} 3+x – (7-x-2) = -2+2x

Δ _{23 =} 4+2x – (9) = -5+2x

Δ _{31 =} 2 – (1-1) = 2

Δ _{34 =} 1+3x – (7-x-1) = -5+4x

max (-3; 1; ; ;)

min (4)

Данное решение будет оставаться постоянным, когда ≤ x≤ 4

Но у нас есть условие 0 ≤ x ≤ 3! Поэтому дальнейшее перераспределение поставок не требуется
Нас интересует граница ≤ x ≤ 3, В ней все оценки свободных клеток положительны, следовательно план оптимальный

F (x) = 1720 – 50x

Вывод:
Таким образом, все условия ограничения выполняются, определены границы изменения параметра x, при которых оптимальные решения будут оставаться постоянными, найдены целевые функции.