Как найти ограничения,кот-е мешает найти оптимум симплексом

[Delphist]

Скажите, пожалуйста, есть ли на сегодняшний день методики (алгоритмы), которые позволяют определить те ограниечение, которые мешают найти оптимум целевой функции через симплекс методом. Теперь попытаюсь объяснить на примере т.е., например,
есть целевая функция:
F = 104*X1 + 85*X2 +49 X3 -> min;

Есть ограничения (требования пользователя):
50 <= 58.05*X1 + 83.16*X2 +34.56*X3 <= 59;
18*X1 + 20.9*X3 >= 12;
16*X1 + 0.023*С2 + 40.1*X3 <= 38;
X1 >= 0.06;
X1 + X2 + X3 = 1;

Поиск X1, X2, X3 осуществляется через симплекс метод (алгоритм его у меня реализован в пакете линейного программирования lpsolve - его часто используют прикладные программисты в своих программах для решения линейных задач симплекс методом). Проблема такая, когда пользователь задает граничные условия, у меня в данном примере это:
1) 50 <=, <= 59;
2) >= 12;
3) <= 38;
4) >= 0.06;
5) = 1;

то может получиться так, что решение задачи (найти X1, X2, X3) не удается выполнить симплекс методом т.к., невозможно выполнить требования ограничений. Так вот хотелось каким-то образом узнавать и выдавать пользователю программы в виде сообщения какой-же показател(ь,и) (ограничени(е,я)) является лимитирующим т.е. из-за какого показателя возникают у симплекс метода проблемы с поиском решения. Как это сделать?

[maxal]

Ну во-первых, симплекс метод в вашему вопросу имеет лишь косвенное отношение. По сути вас интересует разрешимость системы линейных неравенств и как из неразрешимой системы получить разрешимую.

По поводу определения разрешимости - см. ссылки в этой теме.

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

[TOTAL]

Delphist писал(а):

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

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

[Delphist]

maxal писал(а):

Ну во-первых, симплекс метод в вашему вопросу имеет лишь косвенное отношение.

Я бы сказал, что он имеет самое прямое отношение. Дело в том приведенный мной пример из трех ограничений надуманный, а в реальности их может быть до 20, кол-во зависит от пользователя он выбирает на какие показатели накладывать ограничения, выбирет 3 значит в симплексе будет и 3 ограничения, выберет 10 значит в симплексе будет 10 ограничений. Плюс ко всему пользователь сам задает границы ( 50 <=, <= 59 и т.п.) на ограничения. Так вот в большинстве своем случае задача имеет решений и симплекс находит его, но бывают случаи когда найти оптимум не удается вот тут-то пользователю и хотелось бы узнать какой же показатель или показатели мешают нахождению оптимума. lpsolve вроде такого не умеет придется как-то в ручную это делать, вопрос лишь в том как это делать?

Добавлено спустя 45 секунд:

Re: Как найти ограничения,кот-е мешает найти оптимум симплек

TOTAL писал(а):

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

Главное что б понятно было о чем я говорю

[maxal]

Если вопрос про lpsolve - то читайте доку, в частности главу Infeasible models. А если интересует теория и "как сделать самому" - то см. ранееприведенную ссылку.

[Delphist]

maxal писал(а):

Если вопрос про lpsolve - то читайте доку, в частности главу Infeasible models.

А ты хочешь сказать что lpsolve это умеет? И случайно нет ли русского хелпа к lpsolve?

maxal писал(а):

А если интересует теория и "как сделать самому" - то см. ранееприведенную ссылку.

Самому тож было бы не грех разобраться

[нг]

[mod] Delphist
На форуме принято записывать формулы, используя нотацию ($\TeX$; введение, справка).

Пожалуйста, исправьте и сообщите модератору (ЛС).[/mod]