§4. Алгебраический метод решения задач лп (Симплекс метод)

В его основу положен тот факт, что оптимальное решение – угловая точка ОДР. Проводится вычислительная процедура, которая носит итерационный характер, т.е. выполняются последовательно однотипные вычисления до тех пор, пока не будет найдено оптимальное решение.

Начиная с некоторой угловой точки, осуществляются переходы к другим угловым точкам. Число итераций не может превосходить числа угловых точек. Рассмотрим пример из предыдущего параграфа.

Пример.

при ограничениях

Исходной точкой (см.рисунок) в методе станет точка О. Решение в этой точке называется начальным. От точки О можно переходить к точке А или Е. При x₂ коэффициент больше, чем при x₁ , Поэтому выгодно увеличиватьx₂, т.е. двигаться к Е.

Выбор каждой последующей угловой точки определяется следующими правилами:

1. Каждая последующая угловая точка должна быть смежной с предыдущей

2. Обратный переход к последующей точке производиться не может

Сначала приведем к стандартному виду:

У нас 6 неизвестных, 4 уравнения, 6-4=2, приравниваем двух переменных к нулю и получаем базисное решение. В общем случае, если число неизвестных n , уравнений m, то n-m переменным придаем нулевые значения, и из ограничений получаем базисное решение. Если базисное решение удовлетворяет условию неотрицательности правых частей, то решение будет допустимым. Переменные, имеющие нулевые значения, называются не базисными. Остальные – базисные.

Следующая итерация означает взаимную замену: одну переменную из состава базисных выводим, одну базисную приравниваем к нулю, т.е. из базиса исключаем.

Включаемая переменная – небазисная в данный момент, которая будет включена в базис в следующей итерации.

Исключаемая переменная – та базисная, которая на следующей итерации подлежит исключению из базиса.

Вычислительные процедуры "Симплекс-метода".

Состоит из следующих шагов:

1. Определение начального допустимого базисного решения. (Путем приравнивания к нулю n-m переменных)

В нашем примере: x₁=x₂=0.

Это базисное решение соответствует точке О

x₁=x₂=0. – небазисные, - базисные

2. Из числа текущих небазисных выбирается включаемая в новый базис переменная. Если такой переменной нет, то вычисления прекращаются. Текущее базисное решение – оптимальное .

Включаемая в базис переменная определяется условием оптимальности.

Условие оптимальности:

В задаче максимизации (минимизации) вводимая в базис переменная будет та, которая имеет в  - уравнении наибольший (по абс.вел) отрицательный (положительный) коэффициент. В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно.

В нашем примере x₂ . Столбец с x₂ включаемой переменной называется ведущим столбцом_.

Если все коэффициенты при небазисных переменных в  - уравнении неотрицательны (неположительны), то полученное решение является оптимальным.

3.Из числа переменных текущего базиса выбирается из условия допустимости исключаемая переменная, которая должна принять нулевое значение при введение в состав небазисных. Условие допустимости: в задачах max и min в качестве исключаемой выбирается та базисная переменная, для которой отношение постоянной правой части соответствующего ограничения к положительному коэффициенту при включаемой переменной минимально (в том же ограничении). В случае равенства выбор делается произвольно. Осуществляется поиск нового базисного решения методом Гаусса-Жордана. Этот процесс изменения базиса включает вычислительные процедуры двух типов.

Тип 1. (Формирование нового ведущего уравнения)

где ведущим называется элемент, находящийся в пресечении ведущего столбца и строки.

Тип 2. (Формирование остальных уравнений)

Продемонстрируем на нашем примере.

Составим начальную симплекс-таблицу.

Базисные переменные	x1	x2	s1	s2	s3	s4	Решение
s1	2	1	1	0	0	0	6	(1)
s2	1	2	0	1	0	0	8	(2)
s3	1	-1	0	0	1	0	1	(3)
s4	1	0	0	0	0	1	2	(4)
	-2	-3	0	0	0	0	0

Найдем включаемую переменную.

Ведущий столбец – x₂ (включаемая).

, т.е. s₂ исключаемая переменная

Тип 1. (2)

Тип 2.(1)

(3)

(4)– такое же, т.к коэффициент = 0

()

Базисные переменные	x1	x2	s1	s2	s3	s4	Решение
s1	3/2	0	1	-1/2	0	0	2	(1)
x2	1/2	1	0	1/2	0	0	4	(2)
s3	3/2	0	0	1/2	1	0	5	(3)
s4	1	0	0	0	0	1	2	(4)
	-1/2	0	0	3/2	0	0	12	()

Включаемая в базис переменная - x₁

исключаемая s₁

Аналогичным путем получаем следующую таблицу.

Базисные переменные	x1	x2	s1	s2	s3	s4	Решение
x1	1	0	2/3	-1/3	0	0	4/3	(1)
x2	0	1	-1/3	2/3	0	0	10/3	(2)
s3	0	0	-1	1	1	0	3	(3)
s4	0	0	-2/3	1/3	0	1	2/3	(4)
	0	0	1/3	4/3	0	0	38/3	()

Коэффициенты при небазисных – неотрицательные.

По условию оптимальности решение оптимальное.

Теорема (об улучшении оптимального решения)

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

2. Если среди переменных в  - уравнении окажется хотя бы один отрицательный коэффициент (в задаче max) и в таком столбце все элементы отрицательны, то задача имеет неограниченную область ДР.

3. Ели все коэффициенты в  - уравнении неотрицательны, то полученное решение оптимальное.