Не единственность оптимального решения

Рассмотрим задачу:

Геометрическое решение задачи показано на рисунке 3. Из него следует, что линия уровня с максимальным уровнем совпадает с граничной линией АВ области допустимых решений ABCD, т.е. с линией

Замечание. Данная ситуация возможна только в том случае, если коэффициенты целевой функции пропорциональны коэффициентам какой-либо прямой ограничений. Это условие является только необходимым, но не является достаточным.

Следовательно, на всем отрезке АВ целевая функция z принимает одно и то же оптимальное значение. Это означает, что задача имеет бесконечное множество оптимальных решений (их задают координаты отрезка АВ), среди которых базисных оптимальных решений два -соответственно в угловых точках и (точки находятся как решения соответствующих уравнений). Точки отрезка АВ задаются как линейная комбинация точек А и В:

Максимальное значение целевой функции можно найти, подставив координаты любой точки отрезка АВ в уравнение целевой функции.

В рассматриваемом случае .

Основы симплекс-метода линейного программирования

Симплекс - метод представляет собой итеративную процедуру решения задач ЛП, в каноническом виде (любую задачу ЛП можно привести к каноническому виду):

(11)

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

Будем считать, что решается задача на максимум (задачу на минимум можно свести к задаче на максимум, умножив целевую функцию на -1).

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

I. После введения добавочных переменных, система уравнений записывается в виде, который называется расширенной системой (11). Предполагается, что все добавочные переменные имеют тот же знак, что и свободные члены.

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

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

IV. По оценочной строке выбираем переменную, вводимую в базис. Находим наибольший по модулю отрицательный коэффициент в оценочной строке. Соответствующая этомустолбцу переменная будет вводимой в базис, а сам столбец называется разрешающим.

V. Находим переменную, выводимую из базиса. Для этого составляем оценочные отношения (они заносятся в столбец для оценочных отношений) по следующим правилам:

1) , если и имеют разные знаки;

2) , если и ;

3) ли ;

4) 0, если и ;

5) , если и имеют одинаковые знаки.

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

VI. Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана):

1) В левом столбце записываем новый базис: вместо основной переменной - переменную ,

2) В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 - на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 - во всех других позициях столбцов базисных переменных.

3) Новую строку получаем из старой делением на разрешающий элемент .

4) Все остальные элементы вычисляем по правилу прямоугольника:

(12)

Далее переходим к шагу III.

Пример. Решить задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Целевую функцию представим в виде

Базисными переменными будут являться дополнительные переменные .

Заполняем первую симплекс-таблицу:

Базис	Свободный	Переменные	Оценочные
	член			отношения

				18/3



		-2	-3

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

Находим оценочные отношения и выбираем из них минимальное (5). Следовательно, , переменная является вводимой в базис, а соответствующая ей строка - разрешающей.

Переходим к новой симплекс-таблице:

а) в новом базисе основные переменные ;

б) расставляем 0 и 1; например, на пересечении столбца и строки, соответствующих переменной ставим 1, а остальные элементы столбца равны 0 и т.д. Третья строка получается делением на разрешающий элемент . Остальные клетки таблицы заполняем по формулам (12). Например:

Получаем вторую симплекс-таблицу:

Базис	Свободный	Переменные	Оценочные
	член				отношения

				-3
				-1	11/2


		-2

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и - вводимая переменная. Считаем оценочные отношения и находим разрешающую строку - первая и выводимую из базиса переменную - .Разрешающий элемент .

Переходим к новой симплекс-таблице:

Базис	Свободный	Переменные	Оценочные
	член					отношения

					-3
				-2		5/5
						5/1
				-3		12/9
					-3

и на этот раз критерий оптимальности не выполнен.

Выводимая переменная ; вводимая переменная- . Переходим к новой таблице.

Базис	Свободный	Переменные	Оценочные
	член					отношения

				-1/5	3/5
				-2/5	1/5
				2/5	-1/5
				3/5	-9/5
				4/5	3/5

Критерий оптимальности выполнен. Следовательно, Оптимальное решение

⇐ Предыдущая 1 234 Следующая ⇒