Симплексный метод решения задачи линейного программирования. Однокритериальные и многокритериальные задачи, методы решения многокритериальных задач (выделение множества Парето)

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

Основное содержание симплексного метода заключается в следующем:

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

В зависимости от числа критериальных функций (учитывающих различные качества альтернативы) различают два типа задач:

1. Однокритериальные задачи:
Пусть имеется критерий q(x). Будем считать, что выбор любой альтернативы приводит к однозначно известным последствиям (случаи наличия неопределенностей рассматриваются специальными теориями - математической статистикой, теорией игр, теорией размытых множеств). В данном случае наилучшей альтернативой х считается та, которая обладает наибольшим значением критерия. В принципе простая, эта задача может оказаться сложной в смысле техники получения решения, если характер множества X или способ задания критерия приведут к сложным математическим структурам.
2. Многокритеритериальные задачи:
Однокритериальные задачи в практике редки. Часто приходится учитывать несколько качеств одной альтернативы, вводя несколько разных критериев: q1(х). q2(х)....qp (х). При этом почти никогда нет такой альтернативы, которая по всем критериям была бы лучше остальных. Выбор перестает быть таким простым и однозначным, как в однокритериальной задаче, и требуется разработать процедуры принятия решений специально для многокритериальных задач. Таких процедур несколько.
• Построение глобального критерия

• Лексикографическое выделение наилучшей альтернативы.
• Метод задания уровней
• Условная оптимизация
• Метод уступок
Характерным для всех перечисленных методов является нацеленность на отыскание единственной "наилучшей" альтернативы.
Метод выделения паретовского множества явно и открыто признает эту особенность, и выявляет все наилучшие в смысле данного набора критериев альтернатив.

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

15. Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: . (6.11) Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.

Из первой части утверждения теоремы следует, что равенство (6.10) является не только достаточным признаком оптимальности решений, но и необходимым признаком оптимальности решений взаимно двойственных задач.

Экономический смысл первой (основной) теоремы двойственности. План производства и набор цен (оценок) ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при "внешних" (известных заранее) ценах с ₁, с ₂, ..., с_n равна затратам на ресурсы по "внутренним" (определяемым только из решения задачи) ценам у ₁, у ₂ ,..., у_т. Для всех же других планов X и Y обеих задач в соответствии с основным неравенством теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.