Математическое программирование для студентов сельхозакадемии

СИМПЛЕКСНЫЙ МЕТОД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1. Общая характеристика симплексного метода
Поскольку система линейных уравнений изучается в курсе элементарной алгебры, остановимся лишь на основных определениях, необходимых для понимания дальнейшего материала.
Если система имеет хотя бы одно решение, она называется совместной. Несовместные системы не имеют ни одного решения.

Допустимым решением называется совокупность значений n-переменных, удовлетворяющая системе ограничений и условиям не отрицательности.

Широко используемым на практике методом решения задач линейного программирования является симплексный. Этот метод решения задачи линейного программирования основан на переходе от одного опорного решения к другому, при котором значение целевой функции улучшается (на максимум — увеличивается, на минимум — уменьшается или остается на прежнем уровне), при условии, что дан­ная задача имеет оптимальный план.

При решение задачи симплексным методом можно выделить следующие стадии:

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

2. Решение задачи линейного программирования в симплексных таблицах. Правила построения симплексных таблиц
Рассмотрим схему построения на примере.
Пример 1:
3Х1 + Х2 ? 4
Х1 + 3Х2 ? 4
Хj ? 0, j = 1,…,4
Zmax = 2+ Х1+2Х2.

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

Как видим, задача не приведена к канонической форме и к единич­ному базису. Поэтому вводим дополнительные переменные Х3 и Х4.
3Х1 + Х2 + Х3 = 4
Х1 + 3Х2 + Х4 = 4
Хj ? 0, j = 1,…,4
Zmax = 2+ Х1+2Х2 + 0 * Х3 +0 * Х4

Составим первую симплексную таблицу. Она представляет собой форму выражения первого опорного плана. Коэффициенты, стоящие в Z-строке, показывают, как изменяется значение целевой функции при единичном изменении соответствующей свободной переменной. И на­зываются эти коэффициенты оценкой или индексом этой свободной пе­ременной. А сама строка Z называется индексной или оценочной.

Заполнение таблицы

• В первом столбце перечисляют базисные переменные.
• Во второй столбец записывают оценки базисных переменных, указанные в целевой функции.
• В третьем столбце указывают свободные члены.
• В остальных столбцах таблицы записывают коэффициенты при свободных переменных по соответствующим уравнениям.
• Над рабочей частью таблицы перечисляют свободные пере­менные.
• Сверху над свободными переменными помещают оценки сво­бодных переменных, указанные в целевой функции. Над столбцом свободных членов записывают свободный член целевой функции (если таковой имеется) с противоположным знаком.

Оценки Z-строки рассчитывают по формуле

(1)m
                  m
a0j = ?Ciaij – Cj
                i=1

где j = 1, 2, …, n;
аij — коэффициенты j-ого столбца;
Сi— коэффициенты при базисных переменных в уравнении Z;
Сj— коэффициенты при свободных переменных в уравнении Z.

Определение оптимальности плана. Построение новой симплексной таблицы.

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

Ключевая теорема симплексного метода (Z на максимум):

Если после выполнения очередной итерации:

• найдется хотя бы одна отрицательная оценка, а в столбце, где она стоит, есть хотя бы один положительный элемент, то опорное решение можно улучшить, выполнив следующую итерацию;
• найдется хотя бы одна отрицательная оценка, столбец кото­рой не содержит положительных элементов, то функция Zнеогра­ничена в области допустимых решений (Zmax > +?);
• все оценки окажутся неотрицательными, то достигнуто опти­мальное решение.

Согласно данной теореме:

• Просматриваются оценки Z — строки. Если они все неотрица­тельны, то получено оптимальное решение при решении на максимум целевой функции, если все оценки ? 0, то получено оптимальное ре­шении при решении на минимум целевой функции.
• Если оптимальное решение не получено, то выбирается разре­шающий столбец по наибольшей по абсолютной величине отрицатель­ной оценке Z-строки — при решении на максимум и по наибольшей по­ложительной оценке — при решении на минимум целевой функции.
• Составляются симплексные отношения — отношения свобод­ных членов к положительным коэффициентам разрешающего столб­ца. Минимальное из этих отношений (min{аi0,/аip}) определит раз­решающую строку. Коэффициент, находящийся на пересечении раз­решающей строки и разрешающего столбца, называется разрешаю­щим элементом.

Если в разрешающем столбце нет ни одного положительного ко­эффициента, то задача не имеет решения по причине неограниченно­сти целевой функции (Zmax > +?, Zmin > -?).

• Осуществляется переход к новой таблице, где базисная пере­менная заменяется на свободную, соответствующую разрешающему столбцу.
• Бывший разрешающий элемент заменяется обратным по вели­чине (1/ аqp).
• Все остальные элементы бывшего разрешающего столбца делят­ся на разрешающие элементы и меняют знаки на противоположные.

Если в бывшем разрешающем столбце в какой-то строке стоял «0», то эта строка переносится в следующую таблицу без изменений.

7. Все остальные элементы бывшей разрешающей строки делятся на разрешающий элемент.

Если в бывшей разрешающей строке в каком-то столбце стоял «0», то этот столбец переносится в следующую таблицу без изменений.

8. Остальные элементы таблицы пересчитываются по правилу прямоугольника:

коэф. разрешающей строки * коэф. разрешающего столбца
aij? = исходный коэффициент —                                 разрешающий элемент

9. Осуществляется контроль за правильностью расчетов для эле­ментов 2-строки по формуле (1).

10. Если ошибок нет, то алгоритм повторяется с пункта 1 .

В первой симплексной таблице нашего примера все коэффициен­ты оценочной строки отрицательны. Следовательно, согласно теоре­ме, план (на максимум целевой функции) не является оптимальным и требует улучшения. В последнем столбце рассчитывают симплексные отношения (табл. 2.1).

Таблица 2. 1
Симплексная таблица (исходное опорное решение)

Св.П Б.П.	Сj Ci	-2	1	2
		ai0	X1	X2	ai0/aip
X3	0	4	3	1	4
X4	0	4	1	(3)	4/3<
Z		2	-1	-2 ^

Исходное опорное решение: X1 (0,0,4,4); Zmax = 2.

Во второй симплексной таблице (табл. 2.2.) меняем местами ба­зисную переменную Х4 и свободную Х2.

На месте бывшего разрешающего элемента запишем обратную величину, то есть 1/3.

Все остальные элементы разрешающей строки в новой таблице вычислим путем деления на разрешающий элемент: 4/3; 1/3.

Все остальные элементы бывшего разрешающего столбца опре­делим путем деления на разрешающий элемент. Результат запишем в новую таблицу с противоположным знаком: -1/3; 2/3.

Все остальные элементы таблицы вычислим по правилу прямо­угольника.

Первая строка:                                                        Оценочная строка:
4-4*1/3=8/3                                                              2-4*(-2)/3=14/3
3-1*1/3=8/3                                                              -1-1*(-2)/3=-1/3

Таблица 2. 2
Вторая симплексная таблица

Св.П Б.П.	Сj Ci	-2	1	0
		ai0	X1	X4	ai0/aip
X3	0	8/3	(8/3)	-1/3	1 <
X2	2	4/3	1/3	1/3	4
Z		14/3	-1/3 ^	2/3

Проверим правильность заполнения  Z-строки по формуле (1).
а00 = 0*8/3+2*4/3-(-2)=14/3
а01 = 0*8/3+2*1/3-1=-1/3
а02 = 0*(-1/3)+2*1/3-0=2/3.
Так как в оценочной строке есть еще отрицательные оценки, оптимальное решение не получено, можем записать только опорное решение:
Х2 (0,4/3,8/3,0)  Zmax =14/3.
По тому же алгоритму пересчитываем коэффициенты третьей таблицы.

Таблица 2. 3
Третья симплексная таблица

Св.П Б.П.	Сj Ci	-2	0	0
		ai0	X3	X4
X1	1	1	3/8	-1/8
X2	2	1	-1/8	3/8
Z		5	1/8	5/8

Все оценки неотрицательны, следовательно, получено оптималь­ное решение: Хопт (1,1,0,0) Zmax = 5.

Пример 2:
Задача решалась на максимум функции (Z —> мах). На последнем шаге была получена следующая таблица.

Таблица 2.4
Последняя симплексная таблица

Св.П Б.П.	Сj Ci	0	1	0
		ai0	X3	X2
X1	2	2	1	-1
X4	0	1	1	-1/2
Z		4	1	-2  ^

В разрешающем столбце нет ни одного положительного элемен­та, следовательно, Zmax >+?, то есть задача линейного программи­рования не имеет решения по причине неограниченности целевой функции Z сверху.

3. Альтернативный оптимум
Если среди оценок свободных переменных в последней сим­плексной таблице есть хотя бы одна оценка, равная нулю, то задача имеет альтернативное решение, то есть хотя бы два оптимальных ре­шения. Для этих решений экстремальное значение функции будет одинаковое. Чем больше будет нулевых оценок, тем больше опти­мальных решений.

Пример 3:
Представим последнюю симплексную таблицу:

Таблица 2.5
Последняя симплексная таблица

Св.П Б.П.	Сj Ci	0	1	5
		ai0	X1	X2
X3	1	6	3	(5)
X4	0	8	2	4
Z		6	2	0  ^

Х?опт (0,0,6,8)    Zmax = 6
Разрешающий столбец выбираем по нулевой оценке.

Таблица 2.6
Альтернативная симплексная таблица

Св.П Б.П.	Сj Ci	0	1	1
		ai0	X1	X3
X2	5	6/5	3/5	1/5
X4	0	26/5	-2/5	-4/5
Z		6	2	0  ^

Х??опт (0,6/5,0,26/5)    Zmax = 6

4. Вырождение основной задачи линейного программирования
Если в опорном решении задачи хотя бы одна базисная перемен­ная принимает нулевое значение, то это решение называется вырож­денным, а задача линейного программирования, имеющая хотя бы одно вырожденное решение, — вырожденной задачей.

Вырождение наступает в тех случаях, когда при выборе разре­шающего элемента получается несколько одинаковых минимальных симплексных отношений. В этом случае в следующей симплексной таблице в столбце свободных членов появится хотя бы один нуль. Вырождение в больших задачах может привести к зацикливанию, то есть через некоторое число шагов мы можем прийти к опорному ре­шению, которое было уже получено раньше. Чтобы избежать зацик­ливания, разрешающий элемент нужно выбирать по определенному правилу, а именно: для тех строк разрешающего столбца, где получи­лись одинаковые минимальные симплексные отношения нужно со­ставить отношения элементов, стоящих в столбце за разрешающим столбцом, к элементам разрешающего столбца. Наименьшее отноше­ние с учетом знака даст разрешающую строку.

Пример 4:
Х1 + 2Х2 ? 4
2Х1 + Х2 ? 4
Х1 ? 2
Х2 ? 2
Хj ? 0, j = 1,2
Zmax = Х1+Х2.
Приводим к канонической форме
Х1 + 2Х2 + Х3 = 4
2Х1 + Х2 + Х4 = 4
Х1 + Х5 = 2
Х2 + Х6 = 2
Хj ? 0, j = 1,…,6
Zmax = Х1 + Х2 + 0*Х3 + 0*Х4 + 0*Х5 + 0*Х6.
Заполняем первую симплексную таблицу по алгоритму симплексного метода (табл. 2.7).

В оценочной строке две одинаковые отрицательные оценки, поэтому разрешающий столбец выбираем тот, который ближе к столбцу свободных членов. Минимальных симплексных отношений два, по­этому находим отношение элементов столбца Х2 к элементам столбца X1. После пересчета минимальное отношение находится в третьей строке и равно 0, следовательно, разрешающий элемент равен 1. Да­лее идет обычный пересчет.

Таблица 2.7
Первая симплексная таблица

Св.П Б.П.	Сj Ci	0	1	1	ai0/aip
		ai0	X1	X2
X3	0	4	1	2	4 (2)
X4	0	4	2	1	2 (1/2)
X5	0	2	(1)	0	2 (0) <
X6	0	2	0	1	—
Z		0	-1 ^	-1