Кстати... о неединственности оптимального решения задачи
, которая выше была приведена к равносильной форме:
Как известно, если оптимальное решение задачи линейного программирования не единственно, то множество оптимальных решений образует выпуклый многогранник. Для задач небольшой размерности этот "многогранник решений" можно найти, перейдя от исходного H-представления многогранника
к V-представлению:
, где
. Тут (в общем случае неограниченный) выпуклый многогранник задается при помощи
вершин и
лучей. Лучи соответствуют неограниченной части многогранника. Минимум целевой функции достигается на ограниченной части многогранника, т.е. коэффициенты при лучах берутся равными нулю. Далее отбираются вершины
, на которых целевая функция достигает своего минимального значения. И далее для этих вершин (посредством
симплекса) задается их выпуклая оболочка! Это и есть искомое множество оптимальных решений (представленное в форме симплекса).
Естественно, есть куча программ (свободного ПО) для перехода между
- и
-представлениями (
http://www.uic.unn.ru/~zny/skeleton/,
http://www.cs.unb.ca/~bremner/docs/recommend/). Однако:
Цитата:
For unbounded polyhedra, the problem is known to be NP-hard
Т.е., как уже было сказано выше, все это можно проделать для задач относительно небольшой размерности. Есть ли более эффективные алгоритмы отыскания "многогранника оптимальных решений", мне неизвестно.
Для примера выше решения задаются симплексом из двух вершин. Для данного примера V-представление состоит из порядка 1600 вершин и (ЕМНИП) 2000 лучей, и только на 2 вершинах из 1600 достигается минимум.