Сжатие множества допустимых решений в математическом программировании

Сжатие множества допустимых решений

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

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

Однако пользователь сам определяет, какие критерии нужно перевести в ограничения и с какими значениями правых частей Например, неверный выбор Сжатие множества допустимых решений может привести к несовместной задаче линейного программирования. Решение принимается на основе анализа серии подобным образом построенных задач ЛП, т.е. процедура решения задачи МКЛП носит интерактивный характер.

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

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

Трудности здесь могут возникнуть при нахождении всех альтернативных оптимумов для вычисления всех крайних точек.

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

В любом случае надо найти исходную эффективную крайнюю точку. Для этого можно использовать методы: 1) взвешенных сумм; 2) взвешенных сумм с использованием подзадачи-теста; 3) лексикографической максимизации; 4) лексикографической максимизации с использованием подзадачи-теста; 5) Эккера-Куоды; 6) Бенсона.

В методе взвешенных сумм выбирается некоторое

и решается задача

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

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

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

Сжатие множества допустимых решений — область сжатия допустимой области после максимизаций,

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

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

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

В методе Эккера-Куоды решается вспомогательная задача:

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