Сделай Сам Свою Работу на 5

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

1.9.1 Вырожденное оптимальное решение

 

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

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

 

Пример 2. в стандартной форме

 

 

Б с  
8:4=2 Признак вырожденного решения
4:2=2
    -3 -9  
- вырожденная оптимальная точка.    
- 0 - min
  -  
-   - оптимальная точка.    
-1  
   

 

 

 


опт
избыточная

 

Вырожденная точка = оптимальной точке

 

Значение целевой функции не меняется

 

 

1.9.2 Промежуточное вырожденное решение

 

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

 

В стандартной форме

(1)

, (2)

, (3) ,

, (4)

(5)

 

 

 
 


Б с Замечания
    Признак вырожденности
-1
  -3 -2  
- вырожденное неоптимальное решение
-1 2-min
-2 -1 отр
  -  
-   - оптимальное вырожденное решение.
-  
-2  
   
                     



 

 

 

 

1.9.3 Бесконечное множество решений

 

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

Пример 3. В стандартной форме

Б с Замечания
5/2-min  
  -2 -4  
Появление лишнего нуля для небазисной переменной – признак бесконечного множества решений. Начальная точка (0; 5/2)
- 3-min
   
-1   Конечная точка (3: 1) . Решение между этими точками на прямой.
-1  
   

z
А
В

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

 

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

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

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

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

 

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

 

В стандартной форме

(1)

(2)

(3)

(4)

 
 


Б с Замечания
-1 10-min  
    -2 -1  
-1 отр  
-1 30-min
    -3  
Отсутствие - признак неограниченности решения. Присутствие отрицательного числа в результирующей строке признак неограниченности целевой функции.
-1 отр
    -1  

z

Замечание: признак неограниченности решения можно было заметить еще при первой итерации, а именно, в столбце для уже отсутствовало неотрицательное min , а присутствие отрицательного значения в результирующей строке этого столбца (-1) свидетельствовало о неограниченности целевой функции при максимизации.

 

Пример 5. (Пространство решений не ограничено, а оптимальное значение целевой функции

конечно)

В стандартной форме

(1)

(2)

(3)

(4)

 

Б с -2 Замечания
-1 1-min  
  -6  
- отр  
- 6- min
  -1  
 
-2 -1  
   

 

 

Замечание: признак неограниченности решения можно было заметить еще при первой итерации, а именно, в столбце для уже отсутствовало неотрицательное min , а присутствие положительного значения в результирующей строке этого столбца (2) свидетельствовало о том, что целевая функция конечна при максимизации.

 

1.9.5 Отсутствие допустимых решений

 

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

 

Пример 6. В стандартной форме

(1)

(2)

(3)

(4)

 

Б с Замечания
2-min  
-1
    -12M -3M-3 -4M-2 M  
  Отсутствие отрицательных значений в результирующей строке и присутствие искусственной переменной в базе свидетельствует об отсутствии решения
-M -5 -4 -1  
    -4M+4 5M+1 4M+2 M  

 

 



©2015- 2018 stydopedia.ru Все материалы защищены законодательством РФ.