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