Определение базисных и небазисных переменных

1.

z 3x1 6 x2 2 x3 max
3x1 4 x2 x3 2
x1 3x2 2 x3 1
x1 0, x2 0, x3 0
Приводим к каноническому виду систему ограничений
3x1 4 x2 x3 x4 2
x1 3x2 2 x3 x5 1
x1 0, x2 0, x3 0, x4 0, x5 0

2.

Определение базисных и небазисных переменных
Переменная является базисной, если она входит только в одно из
уравнений системы с единичным коэффициентом
=
3x1 4 x2 x3 x4 2
x1 3x2 2 x3 x5 1
x4 2 3x1 4 x2 x3
x5 1 x1 3x2 2 x3
z 3x1 6 x2 2 x3
x4 , x5
x1 , x2 , x3

3.

Базисное решение
Частное решение, полученное путем приравнивания небазисных переменных к
нулю и нахождение значений базисных переменных, называется базисным
решением.
0
0
0
2
1
0

4.

Критерий оптимальности
Критерий оптимальности (максимум): если в выражении целевой
функции через небазисные переменные отсутствуют положительные
коэффициенты, то решение оптимально.
т.к. в целевой функции при небазисных переменных коэффициенты
положительные → критерий оптимальности не выполняется

5.

Выбор нового базиса
x2
2
Небазисные переменные полагаем равные 0, кроме новой базисной
переменной. Тогда система ограничений будет иметь вид
2 4 x2 0
1 3x2 0
x4 2 4 x2
x5 1 3x2
1
3
1
2
1
x2
3
3x2 1 x1 2 x3 x5
1
x
2 2
x 1
2 3
2-е неравенство, переменную выражаем
из 2-го уравнения системы ограничений
x2
1 1
2
1
x1 x3 x5
3 3
3
3

6.

Определение базисных и небазисных переменных
x4 2 3x1 4 x2 x3
x5 1 x1 3x2 2 x3
1 1
2
1
x2 x1 x3 x5
3 3
3
3
Базисные переменные
Небазисные переменные

7.

Базисное решение
0
1/3 0
2/3
0
2
Критерий оптимальности
т.к. в целевой функции при переменной x1
положительный коэффициент

8.

Выбор нового базиса
x1
2/5
1
1
1-е неравенство, переменную выражаем из 1го уравнения системы ограничений (п.6)

9.

Определение базисных и небазисных переменных
5
2 5
4
x1 x3 x4 x5
3
3 3
3
z 2
2
3
4
12
3
6
x3 x4 x5 2 x3 2 x5 x3 x4 x5
5
5
5
5
5
5
x1 , x2
x3 , x4 , x5

10.

Базисное решение
2/5
1/5
0
0
0
12/5
Критерий оптимальности
т.к. в целевой функции при небазисных переменных отсутствуют
положительные коэффициенты