РЕШИТЕ ЗАДАЧИ ГЕОМЕТРИЧЕСКИМ МЕТОДОМ

2.12

	B1	B2	B3	B4	Запасы
A1
A2
A3
A4
Потребности

∑a = 280 + 175 + 125 + 130 = 710
∑b = 90 + 180 + 310 + 130 = 710

Поиск первого опорного плана.
c₁₁=4
x₁₁ = min(280,90) = 90

				280 - 90 = 190
x
x
x
90 - 90 = 0

 

c₁₂=5
x₁₂ = min(190,180) = 180

				190 - 180 = 10
x	x
x	x
x	x
	180 - 180 = 0

 

c₁₃=3
x₁₃ = min(10,310) = 10

			x	10 - 10 = 0
x	x
x	x
x	x
		310 - 10 = 300

 

c₂₃=2
x₂₃ = min(175,300) = 175

			x
x	x		x	175 - 175 = 0
x	x
x	x
		300 - 175 = 125

 

c₃₃=9
x₃₃ = min(125,125) = 125

			x
x	x		x
x	x		x	125 - 125 = 0
x	x
		125 - 125 = 0

 

c₄₄=6

x₄₄ = min(130,130) = 130

			x
x	x		x
x	x		x
x	x			130 - 130 = 0
			130 - 130 = 0

 

c₁₄=7, но т.к. ограничения выполнены, то x₁₄=0.

 

	B1	B2	B3	B4	Запасы
A1	4[90]	5[180]	3[10]	7[0]
A2			2[175]
A3			9[125]
A4				6[130]
Потребности

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 4*90 + 5*180 + 3*10 + 2*175 + 9*125 + 6*130 = 3545
Улучшение опорного плана.
u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5
u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3
u₂ + v₃ = 2; 3 + u₂ = 2; u₂ = -1
u₃ + v₃ = 9; 3 + u₃ = 9; u₃ = 6
u₁ + v₄ = 7; 0 + v₄ = 7; v₄ = 7
u₄ + v₄ = 6; 7 + u₄ = 6; u₄ = -1

	v1=4	v2=5	v3=3	v4=7
u1=0	4[90]	5[180]	3[10]	7[0]
u2=-1			2[175]
u3=6			9[125]
u4=-1				6[130]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij
(3;1): 6 + 4 > 1; ∆₃₁ = 6 + 4 - 1 = 9 > 0
(3;2): 6 + 5 > 3; ∆₃₂ = 6 + 5 - 3 = 8 > 0
(3;4): 6 + 7 > 8; ∆₃₄ = 6 + 7 - 8 = 5 > 0
(4;1): -1 + 4 > 2; ∆₄₁ = -1 + 4 - 2 = 1 > 0
max(9,8,5,1) = 9

 

					Запасы
	4[90][-]	5[180]	3[10][+]	7[0]
			2[175]
	1[+]		9[125][-]
				6[130]
Потребности

 

	B1	B2	B3	B4	Запасы
A1		5[180]	3[100]	7[0]
A2			2[175]
A3	1[90]		9[35]
A4				6[130]
Потребности

u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5
u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3
u₂ + v₃ = 2; 3 + u₂ = 2; u₂ = -1
u₃ + v₃ = 9; 3 + u₃ = 9; u₃ = 6
u₃ + v₁ = 1; 6 + v₁ = 1; v₁ = -5
u₁ + v₄ = 7; 0 + v₄ = 7; v₄ = 7
u₄ + v₄ = 6; 7 + u₄ = 6; u₄ = -1

	v1=-5	v2=5	v3=3	v4=7
u1=0		5[180]	3[100]	7[0]
u2=-1			2[175]
u3=6	1[90]		9[35]
u4=-1				6[130]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij
(3;2): 6 + 5 > 3; ∆₃₂ = 6 + 5 - 3 = 8 > 0
(3;4): 6 + 7 > 8; ∆₃₄ = 6 + 7 - 8 = 5 > 0
max(8,5) = 8

 

 

					Запасы
		5[180][-]	3[100][+]	7[0]
			2[175]
	1[90]	3[+]	9[35][-]
				6[130]
Потребности

 

	B1	B2	B3	B4	Запасы
A1		5[145]	3[135]	7[0]
A2			2[175]
A3	1[90]	3[35]
A4				6[130]
Потребности

u₁ + v₂ = 5; 0 + v₂ = 5; v₂ = 5
u₃ + v₂ = 3; 5 + u₃ = 3; u₃ = -2
u₃ + v₁ = 1; -2 + v₁ = 1; v₁ = 3
u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3
u₂ + v₃ = 2; 3 + u₂ = 2; u₂ = -1
u₁ + v₄ = 7; 0 + v₄ = 7; v₄ = 7
u₄ + v₄ = 6; 7 + u₄ = 6; u₄ = -1

	v1=3	v2=5	v3=3	v4=7
u1=0		5[145]	3[135]	7[0]
u2=-1			2[175]
u3=-2	1[90]	3[35]
u4=-1				6[130]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 5*145 + 3*135 + 2*175 + 1*90 + 3*35 + 6*130 = 2455

Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 2-й магазин (145 ед.), в 3-й магазин (135 ед.)
Из 2-го склада необходимо весь груз направить в 3-й магазин.
Из 3-го склада необходимо груз направить в 1-й магазин (90 ед.), в 2-й магазин (35 ед.)
Из 4-го склада необходимо весь груз направить в 4-й магазин.
Задача имеет множество оптимальных планов, поскольку оценка для (1;4) равна 0.

2.13

	B1	B2	B3	B4	Запасы
A1
A2
A3
Потребности

∑a = 510 + 90 + 120 = 720
∑b = 270 + 140 + 200 + 110 = 720

 

	B1	B2	B3	B4	Запасы
A1
A2
A3
Потребности

Поиск первого опорного плана.
c₁₁=1
x₁₁ = min(510,270) = 270

				510 - 270 = 240
x
x
270 - 270 = 0

 

c₁₂=4
x₁₂ = min(240,140) = 140

				240 - 140 = 100
x	x
x	x
	140 - 140 = 0

 

c₁₃=7
x₁₃ = min(100,200) = 100

			x	100 - 100 = 0
x	x
x	x
		200 - 100 = 100

 

c₂₃=8
x₂₃ = min(90,100) = 90

			x
x	x		x	90 - 90 = 0
x	x
		100 - 90 = 10

 

c₃₃=4
x₃₃ = min(120,10) = 10.

			x
x	x		x
x	x			120 - 10 = 110
		10 - 10 = 0

 

c₃₄=8
x₃₄ = min(110,110) = 110

			x
x	x		x
x	x			110 - 110 = 0
			110 - 110 = 0

 

	B1	B2	B3	B4	Запасы
A1	1[270]	4[140]	7[100]
A2			8[90]
A3			4[10]	8[110]
Потребности

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 1*270 + 4*140 + 7*100 + 8*90 + 4*10 + 8*110 = 3170

Улучшение опорного плана.

u₁ + v₁ = 1; 0 + v₁ = 1; v₁ = 1
u₁ + v₂ = 4; 0 + v₂ = 4; v₂ = 4
u₁ + v₃ = 7; 0 + v₃ = 7; v₃ = 7
u₂ + v₃ = 8; 7 + u₂ = 8; u₂ = 1
u₃ + v₃ = 4; 7 + u₃ = 4; u₃ = -3
u₃ + v₄ = 8; -3 + v₄ = 8; v₄ = 11

	v1=1	v2=4	v3=7	v4=11
u1=0	1[270]	4[140]	7[100]
u2=1			8[90]
u3=-3			4[10]	8[110]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij
(1;4): 0 + 11 > 3; ∆₁₄ = 0 + 11 - 3 = 8 > 0
(2;4): 1 + 11 > 9; ∆₂₄ = 1 + 11 - 9 = 3 > 0
max(8,3) = 8

 

					Запасы
	1[270]	4[140]	7[100][-]	3[+]
			8[90]
			4[10][+]	8[110][-]
Потребности

 

 

	B1	B2	B3	B4	Запасы
A1	1[270]	4[140]		3[100]
A2			8[90]
A3			4[110]	8[10]
Потребности

 

u₁ + v₁ = 1; 0 + v₁ = 1; v₁ = 1
u₁ + v₂ = 4; 0 + v₂ = 4; v₂ = 4
u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3
u₃ + v₄ = 8; 3 + u₃ = 8; u₃ = 5
u₃ + v₃ = 4; 5 + v₃ = 4; v₃ = -1
u₂ + v₃ = 8; -1 + u₂ = 8; u₂ = 9

	v1=1	v2=4	v3=-1	v4=3
u1=0	1[270]	4[140]		3[100]
u2=9			8[90]
u3=5			4[110]	8[10]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij
(2;1): 9 + 1 > 5; ∆₂₁ = 9 + 1 - 5 = 5 > 0
(2;2): 9 + 4 > 6; ∆₂₂ = 9 + 4 - 6 = 7 > 0
(2;4): 9 + 3 > 9; ∆₂₄ = 9 + 3 - 9 = 3 > 0
(3;2): 5 + 4 > 2; ∆₃₂ = 5 + 4 - 2 = 7 > 0
max(5,7,3,7) = 7

 

					Запасы
	1[270]	4[140][-]		3[100][+]
		6[+]	8[90][-]
			4[110][+]	8[10][-]
Потребности

 

	B1	B2	B3	B4	Запасы
A1	1[270]	4[130]		3[110]
A2		6[10]	8[80]
A3			4[120]
Потребности

u₁ + v₁ = 1; 0 + v₁ = 1; v₁ = 1
u₁ + v₂ = 4; 0 + v₂ = 4; v₂ = 4
u₂ + v₂ = 6; 4 + u₂ = 6; u₂ = 2
u₂ + v₃ = 8; 2 + v₃ = 8; v₃ = 6
u₃ + v₃ = 4; 6 + u₃ = 4; u₃ = -2
u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

	v1=1	v2=4	v3=6	v4=3
u1=0	1[270]	4[130]		3[110]
u2=2		6[10]	8[80]
u3=-2			4[120]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 1*270 + 4*130 + 3*110 + 6*10 + 8*80 + 4*120 = 2300

Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (270 ед.), в 2-й магазин (130 ед.), в 4-й магазин (110 ед.)
Из 2-го склада необходимо груз направить в 2-й магазин (10 ед.), в 3-й магазин (80 ед.)
Из 3-го склада необходимо весь груз направить в 3-й магазин.

 

1.32

 

x+2y-14=0

-5x+3y-15=0

4x+6y-24=0

Ответ: 14 при (14:0)

Область допустимых значений

 

1.33

4x-2y-12=0

-x+3y-6=0

2x+4y-16=0

Ответ: 13 при (4,8:3,6)

Область допустимых значений

2.23

 

	B1	B2	B3	B4	Запасы
A1
A2
A3
Потребности

∑a = 160 + 140 + 60 = 360
∑b = 80 + 80 + 60 + 80 = 300

 

	B1	B2	B3	B4	B5	Запасы
A1
A2
A3
Потребности

Поиск первого опорного плана.
c₃₁=1
x₃₁ = min(60,80) = 60

	x	x	x	x	60 - 60 = 0
80 - 60 = 20

c₂₂=2
x₂₂ = min(140,80) = 80

	x
					140 - 80 = 60
	x	x	x	x
	80 - 80 = 0

c₁₃=3
x₁₃ = min(160,60) = 60

	x				160 - 60 = 100
		x
	x	x	x	x
		60 - 60 = 0

c₂₁=3
x₂₁ = min(60,20) = 20

x	x
		x			60 - 20 = 40
	x	x	x	x
20 - 20 = 0

c₁₄=4
x₁₄ = min(100,80) = 80

x	x				100 - 80 = 20
		x	x
	x	x	x	x
			80 - 80 = 0

c₁₅=0
x₁₅ = min(20,60) = 20

x	x				20 - 20 = 0
		x	x
	x	x	x	x
				60 - 20 = 40

 

c₂₅=0
x₂₅ = min(40,40) = 40.

x	x
		x	x		40 - 40 = 0
	x	x	x	x
				40 - 40 = 0

 

	B1	B2	B3	B4	B5	Запасы
A1			3[60]	4[80]	0[20]
A2	3[20]	2[80]			0[40]
A3	1[60]
Потребности

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*60 + 4*80 + 0*20 + 3*20 + 2*80 + 0*40 + 1*60 = 780

Улучшение опорного плана.
u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3
u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4
u₁ + v₅ = 0; 0 + v₅ = 0; v₅ = 0
u₂ + v₅ = 0; 0 + u₂ = 0; u₂ = 0
u₂ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₃ + v₁ = 1; 3 + u₃ = 1; u₃ = -2
u₂ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

	v1=3	v2=2	v3=3	v4=4	v5=0
u1=0			3[60]	4[80]	0[20]
u2=0	3[20]	2[80]			0[40]
u3=-2	1[60]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 3*60 + 4*80 + 0*20 + 3*20 + 2*80 + 0*40 + 1*60 = 780
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 3-й магазин (60 ед.), в 4-й магазин (80 ед.)
Из 2-го склада необходимо груз направить в 1-й магазин (20 ед.), в 2-й магазин (80 ед.)
Из 3-го склада необходимо весь груз направить в 1-й магазин.
На 1-ом складе остался невостребованным груз в количестве 20 ед.
Оптимальный план является вырожденным, так как базисная переменная x₁₅=0.
На 2-ом складе остался невостребованным груз в количестве 40 ед.
Оптимальный план является вырожденным, так как базисная переменная x₂₅=0.

 

2.24

 

	B1	B2	B3	B4	Запасы
A1
A2
A3
Потребности

∑a = 80 + 100 + 70 = 250
∑b = 80 + 50 + 50 + 70 = 250

 

	B1	B2	B3	B4	Запасы
A1
A2
A3
Потребности

Поиск первого опорного плана.

c₁₄=1
x₁₄ = min(80,70) = 70

				80 - 70 = 10
			x
			x
			70 - 70 = 0

 

 

c₁₂=2
x₁₂ = min(10,50) = 10

x		x		10 - 10 = 0
			x
			x
	50 - 10 = 40

c₃₂=2
x₃₂ = min(70,40) = 40.

x		x
	x		x
			x	70 - 40 = 30
	40 - 40 = 0

 

c₃₁=3
x₃₁ = min(30,80) = 30

x		x
	x		x
		x	x	30 - 30 = 0
80 - 30 = 50

 

c₂₃=5
x₂₃ = min(100,50) = 50

x		x
	x		x	100 - 50 = 50
		x	x
		50 - 50 = 0

c₂₁=6
x₂₁ = min(50,50) = 50.

x		x
	x		x	50 - 50 = 0
		x	x
50 - 50 = 0

 

	B1	B2	B3	B4	Запасы
A1		2[10]		1[70]
A2	6[50]		5[50]
A3	3[30]	2[40]
Потребности

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*10 + 1*70 + 6*50 + 5*50 + 3*30 + 2*40 = 810

Улучшение опорного плана.

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2
u₃ + v₂ = 2; 2 + u₃ = 2; u₃ = 0
u₃ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₂ + v₁ = 6; 3 + u₂ = 6; u₂ = 3
u₂ + v₃ = 5; 3 + v₃ = 5; v₃ = 2
u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v1=3	v2=2	v3=2	v4=1
u1=0		2[10]		1[70]
u2=3	6[50]		5[50]
u3=0	3[30]	2[40]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij
(2;2): 3 + 2 > 3; ∆₂₂ = 3 + 2 - 3 = 2 > 0

 

					Запасы
		2[10]		1[70]
	6[50][-]	3[+]	5[50]
	3[30][+]	2[40][-]
Потребности

 

	B1	B2	B3	B4	Запасы
A1		2[10]		1[70]
A2	6[10]	3[40]	5[50]
A3	3[70]
Потребности

 

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2
u₂ + v₂ = 3; 2 + u₂ = 3; u₂ = 1
u₂ + v₁ = 6; 1 + v₁ = 6; v₁ = 5
u₃ + v₁ = 3; 5 + u₃ = 3; u₃ = -2
u₂ + v₃ = 5; 1 + v₃ = 5; v₃ = 4
u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v1=5	v2=2	v3=4	v4=1
u1=0		2[10]		1[70]
u2=1	6[10]	3[40]	5[50]
u3=-2	3[70]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij
(1;1): 0 + 5 > 4; ∆₁₁ = 0 + 5 - 4 = 1 > 0
(1;3): 0 + 4 > 3; ∆₁₃ = 0 + 4 - 3 = 1 > 0
max(1,1) = 1

 

					Запасы
	4[+]	2[10][-]		1[70]
	6[10][-]	3[40][+]	5[50]
	3[70]
Потребности

 

	B1	B2	B3	B4	Запасы
A1	4[10]			1[70]
A2	6[0]	3[50]	5[50]
A3	3[70]
Потребности

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₂ + v₁ = 6; 4 + u₂ = 6; u₂ = 2
u₂ + v₂ = 3; 2 + v₂ = 3; v₂ = 1
u₂ + v₃ = 5; 2 + v₃ = 5; v₃ = 3
u₃ + v₁ = 3; 4 + u₃ = 3; u₃ = -1
u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v1=4	v2=1	v3=3	v4=1
u1=0	4[10]			1[70]
u2=2	6[0]	3[50]	5[50]
u3=-1	3[70]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 4*10 + 1*70 + 3*50 + 5*50 + 3*70 = 720

Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (10 ед.), в 4-й магазин (70 ед.)
Из 2-го склада необходимо груз направить в 2-й магазин (50 ед.), в 3-й магазин (50 ед.)
Из 3-го склада необходимо весь груз направить в 1-й магазин.
Задача имеет множество оптимальных планов, поскольку оценка для (2;1) равна 0.

 

РЕШИТЕ ЗАДАЧИ ГЕОМЕТРИЧЕСКИМ МЕТОДОМ