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

задан 30 Сен '16 0:46

Известен способ проверки совместности системы линейных неравенств методом исключения переменных. - Вы уверены, что для неравенств, а не для уравнений?...

(30 Сен '16 8:26) all_exist

Способ не известен. Но если предположить его известность, то все остальное становится известным по-средством двойственной задачи.

(30 Сен '16 9:42) abc

@abc, так у ТС речь не про двойственность... а про исключения в неравенствах ... (((

(30 Сен '16 10:38) all_exist

@all_exist, Да, уверен. Пусть есть система неравенств скажем с тремя неизвестными. Преобразуем их так, чтобы в левой части стояла только эта неизвестная, а справа что-то еще. Тогда можем исключить эту переменную следующим образом: правые части полученных неравенств со знаком >= должны быть не больше соответствующих правых частей полученных неравенств со знаком <=. Получая новые неравенства на правые части, переменная исключается.

(30 Сен '16 19:39) alois

@alois: я думаю, такая процедура должна работать, но получится очень долго. Если есть ограничение сверху и снизу на переменную x, то мы знаем, что для оптимума подходит крайнее, но не знаем, какое именно. Тогда получится перебор, грубо говоря, 2^n вариантов. Обычный симплекс-метод этого избегает, и работает существенно быстрее.

(30 Сен '16 19:51) falcao

@alois, предположим у Вас есть система из неравенств, все коэффициенты которой положительны и все знаки в одну сторону... ну, получите Вы неравенства вида $%x_1\le g_k(b_k;x_2;\ldots;x_n)$%, где $%k=1;\ldots;m$% - номер неравенства... и как Вы будете избавляться от переменной?... а ещё остаётся вопрос про исключение переменной из целевой функции...

В общем вопросов больше, чем ответов... (((

(30 Сен '16 19:56) all_exist

Между прочим обычный симплекс метод, чуть модифицированный, является полиномиальным.

(1 Окт '16 2:46) abc
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×43

задан
30 Сен '16 0:46

показан
462 раза

обновлен
1 Окт '16 2:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru