Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Отсутствие конечного оптимума. ⇐ ПредыдущаяСтр 4 из 4
Рассмотрим задачу:
При геометрическом решении убеждаемся, что оптимум отсутствует. Рассмотрим симплекс-метод на очередном шаге:
Условие оптимальности целевой функции не выполнено, так как в строке целевой функции коэффициент при . При попытке ввести в базис получаем . Уравнения не ограничивают рост следовательно, min не ограничен (не достигается). Вывод: если на каком либо шаге получается, что во всех уравнениях системы (строках симплекс-таблице) бесконечные оценочные отношения той переменной, которая переводится в основные, то задача не имеет конечного оптимума. §7. Метод искусственных переменных (М-метод)
В рассматриваемой вычислительной схеме симплекс-метода для получения начального базисного решения используются дополнительные переменные. Допустимое базисное решение получается в случае, когда ограничения вида « ». Однако для ограничений вида « » или «=» начальное базисное решение может быть недопустимым. Для получения системы в каноническом виде, обладающей допустимым базисным решением, существует специальный метод. Сначала задача ЛП приводится к канонической форме, в которой все переменные неотрицательные. Затем для каждого ограничения проверяется существование соответствующей базисной переменной. Если ее нет, то вводится новая искусственная переменная с тем же знаком, что и свободный член (искусственных переменных столько, сколько ограничений дающих отрицательную компоненту в первоначальном базисе), играющая роль базисной для данного ограничения. После проверки всех ограничений получается расширенная система в каноническом виде и появляется возможность заполнить начальную симплексную таблицу. Так как введенные переменные не имеют отношения к существу задачи ЛП в исходной постановке, то необходимо добиться обращения в нуль искусственных переменных. для этого составляем новую целевую функцию где - произвольное, большое по отношению задаче число; k - количество искусственных переменных, и ищем максимальное значение Т-функции. Справедливы следующие утверждения. 1) . Если в оптимальном решение Т-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи. 2) . Если имеется оптимальное решение Т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна. 3) . Если максимум Т-функции равен бесконечности, то исходная задача неразрешима (либо система несовместна, либо максимум неограничен). На практике, как правило, Т -задачу разбивают на две задачи и решают с помощью двухэтапного симплек-метода. Этап 1. Рассматривается искусственная целевая функция которая максимизируется при помощи симплекс-метода. Другими словами, производится исключение искусственных переменных. Если максимальное значение вспомогательной задачи равно нулю, то все искусственные переменные обращаются в нуль, и получается допустимое базисное решение начальной задачи. Далее реализуется этап 2. Если максимальное значение вспомогательной задачи положительное, то, по крайней мере, одна из искусственных переменных также положительная, что свидетельствует о противоречивости начальной задачи, и вычисления прекращаются. Этап 2. Допустимое базисное решение, найденное на первом этапе, улучшается в соответствии с целевой функцией исходной задачи ЛП на основе симплекс-метода, т.е. оптимальная таблица первого этапа превращается в начальную таблицу второго этапа и изменяется целевая функция. Пример. Вектор не образует начального допустимого решение (начальное допустимое решение получается приравниванием нулю основных переменных в каноническое системе ограничений). В первое ограничение, дающее отрицательную компоненту, введем искусственную переменную . Преобразуем систему ограничений, умножив первое и второе уравнение на . Т -функция имеет вид: Заполняем первую симплекс-таблицу:
Последняя строка таблицы -это (-М-функция), т.е. . Заполняется она путем выражения искусственных переменных через небазисные переменные (Строки, в которых присутствует искусственная переменная умножаются на и соответствующие их компоненты складываются; в данном случае умножается первая строка. В качестве оценочной строки рассматривается строка , Критерий оптимальности не выполнен. Отрицательный коэффициент соответствует столбцу . Считаем оценочные отношения и находим переменную, выводимую из базиса - .Переходим к новой симплекс-таблице.
Последняя строка показывает, что критерий оптимальности выполнен: . Искусственная переменная тоже равна нулю. Допустимое базисное решение получено . Далее, отбросив последнюю строку и столбец с искусственной переменной переходим ко второму этапу.
Популярное:
|
Последнее изменение этой страницы: 2016-03-17; Просмотров: 988; Нарушение авторского права страницы