Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Отсутствие конечного оптимума.



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

 

При геометрическом решении убеждаемся, что оптимум отсутствует. Рассмотрим симплекс-метод на очередном шаге:

 

 

Базис Свободный Переменные Оценочные
  член           отношения
   
5/3 -1/3 -1/3
7/3 -2/3 1/3
-1
-1/3 -2/3 4/5  

 

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

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

§7. Метод искусственных переменных (М-метод)

 

В рассматриваемой вычислительной схеме симплекс-метода для получения начального базисного решения используются дополнительные переменные. Допустимое базисное решение получается в случае, когда ограничения вида « ». Однако для ограничений вида « » или «=» начальное базисное решение может быть недопустимым.

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

Справедливы следующие утверждения.

1) . Если в оптимальном решение Т-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи.

2) . Если имеется оптимальное решение Т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

3) . Если максимум Т-функции равен бесконечности, то исходная задача неразрешима (либо система несовместна, либо максимум неограничен).

На практике, как правило, Т -задачу разбивают на две задачи и решают с помощью двухэтапного симплек-метода.

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

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

Пример.

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

Преобразуем систему ограничений, умножив первое и второе уравнение на .

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

 

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

 

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

 

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

 

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

 

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

 


Поделиться:



Популярное:

  1. F73.04 Умственная отсталость глубокая с указанием на отсутствие или слабую выраженность нарушения поведения, связанная с хромосомными нарушениями
  2. Алгебры с делением конечного ранга
  3. Вопрос: 3 Нужно ли проводить проверку отсутствия напряжения, если стационарные сигнализирующие устройства показывают его отсутствие?
  4. Господство натурального хозяйства и отсутствие прочных экономических связей между русскими землями
  5. Даже небольшая физическая активность лучше, чем ее полное отсутствие.
  6. Метод конечного использования
  7. Наличие или отсутствие полезных ископаемых
  8. Общая особенность в том, что действуют в составе ферментов, являясь их коферментом. Их отсутствие в пище значительно нарушает процессы метаболизма.
  9. Описание модели управления доступом в системе как конечного автомата Этапы разработки модели управления доступом.
  10. Определение валового внутреннего продукта по методу конечного использования
  11. Отсутствие собственной идентичности


Последнее изменение этой страницы: 2016-03-17; Просмотров: 988; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.018 с.)
Главная | Случайная страница | Обратная связь