Двойственным симплекс-методом определить оптимальное решение исходной (прямой) задачи линейной оптимизации $$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 Ni55aN |
Начнём с того, что "оптимальное" решение, которое Вы нашли не является оптимальным... Всё дело в том, что у Вас нет условия $%x_1\ge 0,\; x_2\ge 0$%, а при этом задача, в которой Вы добавили новые переменные $%x_3,x_4,x_5$%, ещё не является канонической... следовательно, прямой симплекс-метод ещё применять рано... Во-вторых, я не совсем понимаю как Вы в Вашем решении использовали "двойственный симплекс-метод"... Скорее всего условие звучало как симплекс-метод для двойственной задачи... отвечен 12 Янв '16 11:31 all_exist @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
|