Линейное и нелинейное программирование (стр. 2 из 5)

2.1.3 Графический метод

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

F_A = 1

F_B = -8

F_C = -14

F_D = 0

F_E = 3

C(2, 4)

F = -14

2.1.4 Алгебраический метод

x₂, x₄, x₅, x₆ – базисные переменные, x₁, x₃ – свободные переменные

x₁↑F↑ x₃↑F↓ Выбираем x₃ ↔ x₄

x₂, x₃, x₅, x₆ – базисные переменные, x₁, x₄ – свободные переменные

x₁↑F↓ x₄↑F↑ Выбираем x₁ ↔ x₅

x₁, x₂, x₃, x₆ - базисные переменные, x₄, x₅ – свободные переменные

x₁↑F↑ x₄↑F↑

X=(2, 4, 7, 0, 0, 5)

F = -14

2.1.5 Метод симплекс-таблицы

Приведем к каноническому виду:

x₂, x₄, x₅, x₆ – базисные переменные, x₁, x₃ – свободные переменные

↑
b		x1		x3
x2	1	2	-1
	1	-3	1
←	x4	1	-3	1	1
		1	-3	1
x5	12	-1	2	6
	-2	6	-2
x6	4	3	-1
	1	-3	1
F	-4	-9	4
	-4	12	-4

↑
b		x1		x4
x2	2	-1	1
	2	1/5	-2/5
x3	1	-3	1
	6	3/5	-6/5
←	x5	10	5	-2	2
		2	1/5	-2/5
x6	5	0	1
	0	0	0
F	-8	3	-4
	-6	-3/5	6/5

b		x5		x4
x2	4	1/5	3/5
	x3	7	3/5	-1/5
x1		2	1/5	-2/5
	x6	5	0	1
F		-14	-3/5	-14/5

X = (2, 4, 7, 0, 0, 5)

F = -14

2.1.6 Метод допустимого базиса

↑
b		x1		x2		x3		x4		x5		x6
F	0	-1	4	0	0	0	0
	1/2	1/2	1/2	-1/2	0	0	0
←	ξ1	1	2	1	-1	0	0	0	1/2
		1/2	1/2	1/2	-1/2	0	0	0
ξ2	2	-1	1	0	1	0	0	14/3
	1/2	1/2	1/2	-1/2	0	0	0
ξ3	14	3	2	0	0	1	0	3
	-3/2	-3/2	-3/2	3/2	0	0	0
ξ4	3	1	-1	0	0	0	1
	-1/2	-1/2	-1/2	1/2	0	0	0
f	20	5	3	-1	1	1	1
	-5/2	-5/2	-5/2	5/2	0	0	0

↑
b		ξ1		x2		x3		x4		x5		x6
F	1/2	1/2	9/2	-1/2	0	0	0
	5/2	-1/2	-3/2	1	0	0	1
x1	1/2	1/2	1/2	-1/2	0	0	0
	5/2	-1/2	-3/2	1	0	0	1
ξ2	5/2	1/2	3/2	-1/2	1	0	0
	5/2	-1/2	-3/2	1	0	0	1
ξ3	25/2	-3/2	1/2	3/2	0	1	0	25/3
	-15/2	3/2	9/2	-3	0	0	-3
←	ξ4	5/2	-1/2	-3/2	1/2	0	0	1	5
		5	-1	-3	2	0	0	2
f	35/2	-5/2	1/2	3/2	1	1	1
	-15/2	3/2	9/2	-3	0	0	-3

↑
b		ξ1		x2		ξ4		x4		x5		x6
F	3	0	3	1	0	0	1
	-3	0	-3/5	9/5	0	-3/5	9/5
x1	3	0	-1	1	0	0	1
	1	0	1/5	-3/5	0	1/5	-3/5
ξ2	5	0	0	1	1	0	1
	0	0	0	0	0	0	0
←	ξ3	5	0	5	-3	0	1	-3	1
		1	0	1/5	-3/5	0	1/5	-3/5
x3	5	-1	-3	2	0	0	2
	3	0	3/5	-9/5	0	3/5	-9/5
f	10	-1	5	-3	1	1	-2
	-5	0	-1	3	0	-1	3

↑
b		ξ1		ξ3		ξ4		x4		x5		x6
F	0	0	-3/5	14/5	0	-3/5	14/5
	-14	0	0	-14/5	-14/5	0	-14/5
x1	4	0	1/2	2/5	0	1/5	2/5	10
	-2	0	0	-2/5	-2/5	0	-2/5
←	ξ2	5	0	0	1	1	0	1	5
		5	0	0	1	1	0	1
x2	1	0	1/5	-3/5	0	1/5	-3/5
	3	0	0	3/5	3/5	0	3/5
x3	8	-1	3/5	1/5	0	3/5	1/5	40
	-1	0	0	-1/5	-1/5	0	-1/5
f	5	-1	-1	0	1	0	1
	-5	0	0	-1	-1	0	-1

b		ξ1		ξ3		ξ4		x4		x5		ξ2
F	-14	0	-3/5	0	-14/5	-3/5	-14/5
	x1	2	0	1/5	0	-2/5	1/5	-2/5
x6		5	0	0	1	1	0	1
	x2	4	0	1/5	0	3/5	1/5	-3/5
x3		7	-1	3/5	0	-1/5	3/5	-1/5
		f	0	-1	-1	-1	0	0	-1

b	x4	x5
F	-14	-14/5	-3/5
x6	5	1	0
x2	4	3/5	1/5
x3	7	-1/5	3/5
x1	2	-2/5	1/5

Допустимое базисное оптимальное решение:

X = (2, 4, 7, 0, 0, 5)

F = -14

2.1.7 Решение двойственной задачи

Прямая задача:

Двойственная задача:

Приводим к каноническому виду:

y₁, y₃ – базисные переменные, y₂, y₄, y₅, y₆ – свободные переменные