Особые случаи применения симплекс-метода

 

 

Содержание

Задание 1. Особые случаи применения симплекс-метода……………………...3

1. Вырожденность…………………………………………………..3
2. Альтернативные оптимальные решения………………………..7
3. Неограниченные решения……………………………………...10
4. Отсутствие допустимых решений……………………………..14

Задание 2…………………………………………………………………………16

Задание 3…………………………………………………………………………18

Задание 4…………………………………………………………………………27

Список литературы………………………………………………………………30

 

 

Задание 1. Изложить материал по выбранной теме. Проиллюстрировать теоретические положения примерами

Особые случаи применения симплекс-метода

Выделяют следующие особые случаи, встречающиеся при использовании симплекс-метода:

5. вырожденность;
6. альтернативные оптимальные решения;
7. неограниченные решения;
8. отсутствие допустимых решений.

Основное внимание уделять  причинам возникновения таких ситуаций и их интерпретации применительно  к практическим задачам.

Для наглядности используется графический метод решения задач  ЛП.

1. Вырожденность

Пример1. (Вырожденное оптимальное решение).

Дано: максимизировать целевую функцию

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

                                                                                                               (1)

                                                                                                               (2)

                                                                                                                       (3)

                                                                                                                       (4)

Таблица 1.1

Итерация	Базисные переменные	x1	x2	x3	x4	Решение	Отношение
0 (начало вычислений) х2 вводится х3 исключается	Z	-3	-9	0	0	0
	x3	1	4	1	0	8	2
	x4	1	2	0	1	4	2
1 х1 вводится х4 исключается	Z	-3/4	0	9/4	0	18
	x2	1/4	1	1/4	0	2	8
	x4	1/2	0	-1/2	1	0	0
2 оптимум	Z	0	0	3/2	3/2	18
	x2	0	1	1/2	-1/2	2
	x1	1	0	-1	2	0
0 (начало вычислений) х2 вводится х3 исключается	Z	-3	-9	0	0	0
	x3	1	4	1	0	8	2
	x4	1	2	0	1	4	2
1 х1 вводится х4 исключается	Z	-3/4	0	9/4	0	18

 

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

Наличие вырожденного решения  не свидетельствует о какой-либо «опасности» для исследователя  и вызывает лишь некоторое неудобство в теоретическом отношении. С  практической точки зрения специфика  ситуации целиком объясняется наличием в модели, по крайней мере, одного избыточного ограничения.

Что же практически обусловливает вырожденность решения?

                                                 Рис. 1.1.

Рассмотрим рисунок, иллюстрирующий графический способ решения задачи. Через точку оптимума (х₁=0, х₂=2) проходят три прямые. Задача содержит только две переменные, поэтому такую точку обычно называют переопределенной, так как для ее идентификации необходимы только две прямые. Отсюда следует вывод, что одно из ограничений модели является избыточным. Информация такого рода позволяет также выявить возможные неточности в формулировке задачи.

Важный в теоретическом  отношении второй фактор можно обнаружить, сравнивая итерации 1 и 2. Хотя состав базисных и небазисных переменных на этих итерациях различен, значения всех переменных и целевой функции  не изменяются:

x₁ = 0, x₂ = 2, x₃ = 0, x₄ = 0, Z = 18.

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

Пример2. (Промежуточное вырожденное решение).

    Дано: максимизировать целевую функцию

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

         (1)

          (2)

          (3)

           (4)

           (5)

Таблица 1.2

Итерация	Базисные переменные	x1	x2	x3	x4	x5	Решение
0 (начало вычислений) х1 вводится х4 исключается	Z	-3	-2	0	0	0	0
	x3	4	3	1	0	0	12
	x4	4	1	0	1	0	8
	x5	4	-1	0	0	1	8
1 х2 вводится х3 исключается	Z	0	-5/4	0	3/4	0	6
	x3	0	2	1	-1	0	4
	x1	1	1/4	0	1/4	0	2
	x5	0	-2	0	-1	1	0
2 оптимум	Z	0	0	5/8	1/8	0	17/2
	x2	0	1	1/2	-1/2	0	2
	x1	1	0	-1/8	3/8	0	3/2
	x5	0	0	1	-2	1	4

 

В таблице, содержащей результаты всех итераций, вырожденность впервые  обнаруживается на итерации 1. В отличие  от предыдущего примера в данном случае на итерации 2 вырожденность  уже не имеет места, причем значение целевой функции улучшается, возрастая  с Z=6 (итерация 1) до Z= 17/2 (итерация 2). Это связано с тем, что переменная x₂, вводимая в базис на итерации 1, имеет отрицательный коэффициент (—2) в ограничении, соответствующем нулевой базисной переменной x₅. В соответствии с условием допустимости х₅ не может быть переменной, исключаемой из базиса.

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

 

Рис. 1.2.

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

2. Альтернативные  оптимальные решения

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

Пример 3. (Бесконечное множество решений).

Дано: максимизировать целевую функцию

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

          (1)

          (2)

           (3)

           (4)

Таблица 2.1

Итерация	Базисные переменные	x1	x2	x3	x4	Решение
0 (начало вычислений) х2 вводится х3 исключается	Z	-2	-4	0	0	0
	x3	1	2	1	0	5
	x4	1	1	0	1	4
1 х1 вводится х4 исключается	Z	0	0	2	0	10
	x2	1/2	1	1/2	0	5/2
	x4	1/2	0	-1/2	1	3/2
2 оптимум	Z	0	0	2	0	10
	x2	0	1	1	-1	1
	x1	1	0	-1	2	3

 

Рисунок 2.1 иллюстрирует условия данной задачи ЛП, особенность которой состоит в том, что прямая, представляющая целевую функцию, параллельна прямой, соответствующей одному из связывающих ограничений. Это обусловливает наличие альтернативных оптимальных решений. Любая точка отрезка ВС представляет собой альтернативный оптимум, причем в каждой из этих точек целевая функция имеет одно и то же значение Z=10.

                       

                                             Рис. 2.1.

Каким образом по результатам  этой итерации, содержащимся в таблице, можно узнать о наличии альтернативных оптимальных решений? Рассмотрим значения коэффициентов при небазисных переменных в Z-уравнении, полученном на данной итерации.

Нулевое значение коэффициента (небазисной) переменной x₁ свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению значений других переменных. Именно это и происходит на итерации 2, когда переменная x₁ вводится в базис вместо x₄. В результате получается новое оптимальное решение, соответствующее точке С, в которой x₁=3, x₂=1 и Z=10.

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

B: x₁ = 0, x₂ = 5/2,

C: x₁ = 3, x₂ = 1

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

x₁' = a(0) + (1 - a)(3) = 3 - 3a,

x₂' = a(5/2) + (1 -a)(1) = 1 - 3a/2.

Заметим, что при a=0 имеем (x₁', x₂') = (3, 1), что соответствует точке С. Если a=1, то (x₁, x₂)= (0, 5/2), т. е. получаем точку В. При значениях a, заключенных между 0 и 1, точка (x₁', x₂') располагается на отрезке ВС.

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

3. Неограниченные  решения

Пример 4. (Неограниченная целевая функция).

Дано: максимизировать целевую функцию

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

          (1)

          (2)

           (3)

           (4)

Начальная итерация

Таблица 3.1

Базисные переменные	x1	x2	x3	x4	Решение
Z	-2	-1	0	0	0
x3	1	-1	1	0	10
x4	2	0	0	1	40

Рис. 3.1.

Условия некоторых задач ЛП могут допускать бесконечное увеличение значений переменных без нарушения наложенных ограничений. Это свидетельствует о том, что пространство решений, по крайней мере, в одном направлении не ограничено. Следовательно, в таких случаях целевую функцию можно сделать сколь угодно большой (задача максимизации) или сколь угодно малой (задача минимизации). Характеризуя такую ситуацию, обычно говорят, что и пространство решений, и оптимальное значение целевой функций не ограничены.

Неограниченность решения  задачи ЛП свидетельствует только об одном: разработанная модель недостаточно точна. Бессмысленность использования  модели, прогнозирующей «бесконечную»  прибыль, вполне очевидна. Наиболее типичные ошибки, приводящие построению моделей  такого рода, состоят в том, что 

1) не учтено одно (или несколько) ограничение, не являющееся избыточным;

2) неточно оценены параметры (постоянные), фигурирующие в не которых ограничениях.

Анализ начальной симплекс-таблицы  показывает, что в качестве переменной, включаемой в базис, можно выбрать  либо x₁, либо x₂. Переменная x₁ имеет наибольший по абсолютной величине отрицательный коэффициент в z-уравнении, и именно такая переменная обычно вводится в базис. Заметим, однако, что во всех ограничениях коэффициенты при x₂ либо отрицательны, либо равны 0. Это означает, что x₂ можно бесконечно увеличивать, не нарушая ни одного из ограничений модели. Так как прирост переменной x₂ на единицу приводит к такому же увеличению функции Z, становится ясно, что при неограниченном возрастании x₂ будет неограниченно увеличиваться и значение целевой функции Z. Поэтому, не проводя дальнейших вычислений, можно заключить, что решение сформулированной задачи не ограничено. Иллюстрацией рассмотренной ситуации служит рисунок, из которого видно, что в направлении оси х₂ пространство решений не ограничено и значение Z может быть сделано сколь угодно большим.