Народы!!! Заранее благодарствую : )
А теперь к делу...

Задачу описывать не буду -- я знаю, как её решать, единственная загвоздка -- это проверить множество, заданное линейными неравенствами (неравенств больше переменных) на непустоту. Т.е. неравенства -- на непротиворечивость. Можно ли это сделать, если да -- то опишите, пожалуйста, вкратце суть (меня клинит -- вообще никаких мыслей нет... вернее есть, но мне каэтся, что это бред. Опишу ниже : ).
Программирую в Дельфи, но это неважно ("обязательно" указала ; ) -- главное суть, а запрограммирую сама.

Теперь обещанный бред... Пожалуй, приведу пример:
пусть переменных две, а неравенств три.

х1 + х2 <= 7,
x1 >= 5,
x2 >= 5,
все переменные положительны (здесь это и так ясно, а в общем сл. это требование должно выполняться дополнительно к заданным неравенствам).

Множество, задаваемое этими неравенствами пусто (нерав-ва противоречивы).
Но если неравенств больше сотни (переменных 10), то противоречия не видны невооружённым глазом. Внутренний голос мне подсказывает (и я почему-то уверена, что он нагло врёт), что надо добавить одну переменную (здесь. Чтобы уравнять число (не)равенств и переменных) и превратить т.о. одно из неравенств в равенство, например, первое:

х1 + х2 + x3 = 7,
x1 >= 5,
x2 >= 5,
(все переменные остаются положительными).

И затем решить одним из известных методов систему уравнений, заменив в остальных неравенствах знак >= (или <=) на просто =. (Вот здесь-то вся загвоздка -- насколько правомерна такая замена???). Если решение есть и все компоненты его положительны, значит, неравенства непротиворечивы и множество непусто. И наоборот.

Ещё была мысля попробовать найти (или хотя бы оценить) объём множества, задаваемого неравенствами, т.е. если объём этого мн-ва заведомо больше положительного числа, то мн-во непусто. Но как это сделать (если вообще можно) -- кто его знает...

Вот...

P.S. Не горит, но в течение недели-двух (максимум) хотелось бы в этом разобраться.

P.P.S. Да, кста! Если это важно: обработка неравенств -- это решение задачи линейного программирования на заданном этими неравенствами мн-ве симплекс-методом. Может быть, я чего-то недопонимаю и в процессе обработки выяснится, что мн-во пусто??? Во всех книжках, которые я видела, симплекс-метод описан для "непустого мн-ва". А у меня могут быть противоречия. Как их опознать в процессе работы алгоритма??

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

второй способ: (используя описанный здесь же подход)
превращаем каждое неравенство в равенство вводя кучу переменных (все они неотрицательны)
получим что-то вроде прямой в 3-мерном пространстве, только размерности будут другие
тоже может что-то получиться...

вот...больше в голову ничего не приходит...пока...

Это сообщение отредактировал(а) maxim1000 - 13.4.2005, 01:22

а...это ж просто
если система разрешима, симплекс-метод даст ответ
если нет, то есть два варианта:
1. при выполнении возникнет ошибка - отловить, я думаю, трудности не представит
2. выдаст бредовый результат - его можно просто подставить в систему и проверить
Добавлено @ 01:28

Цитата

Как их опознать в процессе работы алгоритма??

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

maxim1000

Цитата

1. при выполнении возникнет ошибка - отловить

В том то и беда, что я не знаю, как противоречивые неравенства отразятся на ходе алгоритма! Ежели бы я знала, какую ошибку ждать, то при её возникновении выдала бы пользователю что-нть типа "Данные противоречивы, задача неразрешима, проверьте... и т.д. и т.п." и всё...

Цитата

выдаст бредовый результат - его можно просто подставить в систему

Боюсь, что симплекс-метод (СМ) результата не выдаст в сл. противоречий, а либо зациклится (вообще число итераций неизвестно), либо выдаст ошибку типа "прогр. выполнила недопустимую операцию..."
Здесь важно проверить на непротиворечивость до запуска СМ...
Либо в процессе (кто-нибудь знает, как это происходит в СМ?), но этого я пока не умею.

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

Но предложения и пожелания принимаются всё равно!!! : )
Ишшо раз всем спасибо! : )