вариант 4. Решение Шаг 1

• Название: Решение Шаг 1
• Дата: 26.04.2018
• Размер: 0.65 Mb.
• Имя файла: вариант 4.doc
• Тип: Решение; #42260
• страница: 3 из 8

x₁, x₂, x₃, s₁, s₂, r₁, r₂ ≥ 0

с базисными переменными r₁,r₂. Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r₁,r₂). Для этого сформируем вспомогательную целевую функцию :

G =

r1

+

r2

и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.

Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого: 
  - вычтем из функции G уравнение 1 
  - вычтем из функции G уравнение 2 

Функция G примет вид : 

G =

-

3

x1

-

x2

-

2

x3

+

s1

+

s2

+

5

Теперь мы можем сформировать начальную симплекс-таблицу.

Шаг:3
Начальная симплекс-таблица

БП	x1	x2	x3	s1	s2	r1	r2	Решение	Отношение
r1	2	-1	1	-1	0	1	0	2	2 / 2 = 1
r2	1	2	1	0	-1	0	1	3	3 / 1 = 3
Q	1	5	2	0	0	0	0	0	--
G	-3	-1	-2	1	1	0	0	-5	--

Итерация 1

БП	x1	x2	x3	s1	s2	r2	Решение	Отношение
x1	1	-1 2	1 2	-1 2	0	0	1	--
r2	0	5 2	1 2	1 2	-1	1	2	2 / 5 2 = 4 5
Q	0	11 2	3 2	1 2	0	0	-1	--
G	0	-5 2	-1 2	-1 2	1	0	-2	--

Итерация 1-a

БП	x1	x2	x3	s1	s2	Решение	Отношение
x1	1	0	3 5	-2 5	-1 5	7 5	--
x2	0	1	1 5	1 5	-2 5	4 5	4 5 / 2 = 4
Q	0	0	2 5	-3 5	11 5	-27 5	--
G	0	0	0	0	0	0	--

Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"


Итерация 2

БП	x1	x2	x3	s1	s2	Решение	Отношение
x1	1	0	3 5	-2 5	-1 5	7 5	--
x2	0	1	1 5	1 5	-2 5	4 5	4 5 / 1 5 = 4
Q	0	0	2 5	-3 5	11 5	-27 5	--

Итерация 3

БП	x1	x2	x3	s1	s2	Решение	Отношение
x1	1	2	1	0	-1	3	--
s1	0	5	1	1	-2	4	--
Q	0	3	1	0	1	-3	--

Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.

Ответ:

Оптимальное значение функции Q(x)=

3

достигается в точке с координатами:

x1=	3
x2=	0
x3=	0
s1=	4
s2=	0