Идея симплекс метода.

Симплекс метод является универсальным.

Симплекс метод – аналитический метод.

1. Находятся первоначальное, опорное решение. А)система ограничений должна быть записана в виде равенств (каноническая форма)

Б)Преобразовать что бы bi >=0 i=1,m

С)Привести систему к единичному базисному виду с неотрицательной правой частью.

Поэтому за разрешающий элемент выбирается строго положительный элемент.

Д)Приравниваем свободные к 0 , получаем первоначальное базисное неотрицательное

решение, которое является опорным решением данной задачи и соответствует вершине.

2. Рассматривая функцию цели выясняем является ли полученное решение оптимальным.

3. Если полученное решение не является оптимальным , то необходимо перейти к следующей вершине (опорному решению) Переход осуществляется по определенному правилу по которому : только одна изи базисных переменных должна перейти в свободную и только одна из свободных перейти в базисную.

Алгебра симплекс метода.

Х1	Х2	Х3	Х4	Х5	св.чл
1	0	1	6	2	8
0	1	1	0	3	9
0	0	7	-1	-3	-0
1	-2/3	1/3	6	0	2
0	1/3	1/3	0	1	3
0	1	8	-1	0	9
1/6	-2/18	1/18	1	1/3
			0	1	-9
1/6	8/9	8 1/8	0	0	1/3

Особенность выделенная клетка.

1. Чтобы решать симплекс методом необходимо Z->min (перейти к min)

2. В строке Z записываются коэффициенты ф-ии цели, а свободный член записывается в выделенную клетку св.чл. с противоположным знаком.

3. Сделаем свободные члены неотрицательными.

4. Приводим систему ограничений к единичному базису методом Гауса, выбирая за разрешающий элемент положительный элемент.

5. Функция цели должна быть выражена только через свободные неизвестные , чтобы определить оптимален ли полученный опорный план. Для определения опорного плана свободные элементы =0 r=(7;-1;-3} Среди них выбираем самый отрицательный и делаем разрешающий столбец. Для выбора разрешающей строки находится min-ое из отношений свободных членов системы ограничений к положительным коэффициентам разрешающего столбца

6. Для выбора разрешающей строки находится min-ое из отношений свободных членов системы ограничений к положительным коэффициентам разрешающего столбца.

Альтернативный оптимум.

Предположим найдено оптимальное решение. r>=0. Признаком альтернативного оптимума в этом случаи является равенство 0, хотя бы одной из компонент вектора r. Покажем что если компонента rj =0 , для найденого оптимального плана (Х^*₁) то можно найти еще одно оптимальное решение Х^*₂ , значение в котором будет таким же как и значение в Х^*₁. Z(Х^*₂)= Z (Х^*₁₎=Zmin

За разрешающий столбец берем rj =0 Zmin=Z(X^*₁)=-Q (свободный член в Z) Q¹=aij*Q-bi*rj/aij = Q-(bi*rj/aij)=Q bi>0 aij>=0

Сделав шаг метода Гауса , получим новое решение , а значение функции в т Х^*₂ будет точно таким же как и в Х^*₂ – т.е. задача Альтернативного оптимума.