Двойственным симплекс-методом определить оптимальное решение исходной (прямой) задачи линейной оптимизации

$$z=3x_1+9x_2 \rightarrow max$$

$$ \begin{cases} 2x_1+3x_2\ge 6 \\ -3x_1-2x_2 \ge -24 \\-x_1+x_2\ge 5 \end{cases} $$

По опорному плану $%X=(0,0,-6,24,5)$% перешел к оптимальному $$X=(0,12,40,0,7)$$

$$\ \ \ \ | x_1\ | x_2\ | x_3\ | x_4\ | x_5\ | b_i\\ x_3\ |\ 1\ \ | 0\ \ |\ 1\ \ | \frac32\ \ |\ 0\ \ | 30\\ x_2\ |\ \frac32\ \ |\ 1\ |\ 0\ \ |\ \frac12\ \ |\ 0\ \ | 12\\ x_5\ |\ \frac52\ \ |\ 0\ \ |\ 0\ |\ \frac12\ \ |\ 1\ \ | 7\\ z\ |\ 9\ \ |\ 0\ \ |\ 0\ \ |\ 4\ \ |\ 0\ \ | 96$$

Если $%z_{max}=z^*_{min}=96$%, тогда нужно найти такие $%y_1,y_2...$% для оптимального плана двойственной задачи. Как это сделать? Ни по примерам, ни по теории не ясно откуда и как это берется, если взять из последней строки, то есть $%Y=(9,0,0,4,0)$%, тогда не сходится

задан 11 Янв '16 23:01

10|600 символов нужно символов осталось
0

Начнём с того, что "оптимальное" решение, которое Вы нашли не является оптимальным... Всё дело в том, что у Вас нет условия $%x_1\ge 0,\; x_2\ge 0$%, а при этом задача, в которой Вы добавили новые переменные $%x_3,x_4,x_5$%, ещё не является канонической... следовательно, прямой симплекс-метод ещё применять рано...
У Вас задача с двумя переменными, поэтому можете для проверки найти решение графически...

Во-вторых, я не совсем понимаю как Вы в Вашем решении использовали "двойственный симплекс-метод"... Скорее всего условие звучало как симплекс-метод для двойственной задачи...
То есть Вам надо выписать двойственную задачу - она будет канонической... затем использовать симплекс-метод (тут возникнет необходимость задействовать метод искусственного базиса)... ну, и так далее...

ссылка

отвечен 12 Янв '16 11:31

@Ni55aN, выписать забыл. - ну, я не могу угадывать то, что Вы не выписали... (((

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

(12 Янв '16 16:56) all_exist

симплекс методом нашел оптимальный план исходной задачи

(12 Янв '16 17:31) Ni55aN

@Ni55aN, в алгоритме С-М первым пунктом стоит наличие начального плана... Если он допустимый и неоптимальный, то применяют прямой С-М, а если оптимальный и недопустимый - то двойственный... В Вашем примере ни того не другого изначально нет...

Поэтому не видя что и как Вы преобразовывали я большего сказать не могу...

(12 Янв '16 22:18) all_exist

как тогда здесь пропустило недопустимый план? https://goo.gl/vqlR3l

(13 Янв '16 16:56) Ni55aN

@Ni55aN, по второй ссылке как раз и есть описание двойственного С-М (правда, не в очень привычной для меня форме пересчёта... но это уже детали)... то есть, имеется начальное ОПТИМАЛЬНОЕ и НЕДОПУСТИМОЕ решение...

Первая ссыль реализует прямой С-М... но при отсутствии начального плана оно пытается его подобрать... и при чём не известно заранее есть ли оно вообще... (сильно это напоминает полный перебор угловых точек множества).... Здесь оно конечно есть, поэтому всё проходит... А замените во втором условии правую часть с $%(-24)$% на $%(-8)$% и посмотрите, что получится...

(13 Янв '16 19:30) all_exist

@all_exist, чем тогда по онлайн калькулятору с отрицательными свободными членами получается решение?

(17 Янв '16 15:58) Ni55aN
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×76

задан
11 Янв '16 23:01

показан
446 раз

обновлен
17 Янв '16 15:58

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

по почте:

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

по RSS:

Ответы

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

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