Ознакомьтесь с нашей политикой обработки персональных данных
21:22 

Линейное программирвоание

Добрый вечер! Не могли бы Вы помочь с линейным программирвоанием?
Дана задача:
`{(x_1+2x_2+3x_3 -> max), (x_1+x_2<=2), (x_1+x_3<=3), (x_2>=x_3), (x_1<=1), (x_i>=0):}`
Нужно записать двойственную задачу и решить её. Предварительно нам дано решение исходной задачи: `(0,2,2)`
Прежде чем приступать к решению двойственной задачи я хотел спросить: а как вообще решать линейные задачи? Предположим, нам не было бы дано решение исходной системы, как её решать?

@темы: Линейное программирование

Комментарии
2016-03-27 в 21:31 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
MestnyBomzh? а как вообще решать линейные задачи?
"Хороший вопрос... я ждал его..."(с)
Нууу... есть графический метод решения... а если переменных много (как в Вашем случае), то симплекс-метод...

Предварительно нам дано решение исходной задачи:
Оно вроде не является допустимым... не выполнено ограничение `x_1 >= 1`...

2016-03-27 в 21:42 

All_ex, я тоже исправил:)
Теперь у меня такой вопрос. Я проверил, что этот набор - решение, с помощью нахождения теневых цен (они же - коэффициенты Лагранжа). Теперь у меня появилась идея, что двойственную задачу можно не решать, а эти лямбды и будут ответом. Это верно?

2016-03-27 в 21:55 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
MestnyBomzh, наличие решения наводит на мысль, что задание звучит не совсем так как у Вас записано...
Гипотеза такая: "Используя двойственную задачу проверить является ли данное решение оптимальным"

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

2016-03-27 в 22:01 

Нет, сначала задача: проверить, является ли этот набор оптимальным.

Я это сделал следующим образом. Сначала выяснил какое из ограничений является активным, после чего нашел разложение градиента функции `(1,2,3)` по градиентам активных ограничений.

2016-03-27 в 22:18 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Я это сделал следующим образом. Сначала выяснил какое из ограничений является активным, после чего нашел разложение градиента функции `(1,2,3)` по градиентам активных ограничений.
ну, это некий усечённый аналог теоремы о дополняющей нежёсткости...

Теперь у меня появилась идея, что двойственную задачу можно не решать
Нет... решать её надо, поскольку у Вас есть ещё и неравенства в двойственной задаче, которым найденные множители Лагранжа могут не удовлетворять... да и оптимальность такого решения пока неоткуда не следует...

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

2016-03-27 в 22:26 

Вот, что дальше спрашивают.

Ну вот, что у меня получилось: активные ограничения - первое, третие и пятое. Тогда надо решить систему: `lambda_1((1),(1),(0))+lambda_3((0),(-1),(1))+lambda_5((-1),(0),(0))=((1),(2),(3))`
Отсюда `lambda_1=5, lambda_3=3, lambda_5=4`. Так вот, отсюда нельзя сразу сделать вывод о том, чему равны игреки?
На всякий случай привожу сразу двойственную задачу, чтобы не путаться:
`{(2y_1+3y_2+y_4->min), (y_1+y_2+y_4>=1), (y_1-y_3>=2), (y_2+y_3>=3),(y_i>=0):}`

2016-03-27 в 22:43 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Так вот, отсюда нельзя сразу сделать вывод о том, чему равны игреки?
для какого-то допустимого решения - можно... но в данном случае оно не будет оптимальным (если я не ошибся в вычислениях) ...

2016-03-27 в 22:44 

А почему нет? В учебниках пишут, что `lambda_i` - это теневые цены. Но при этом они же пишут, что `y_i` - тоже теневые цены. Это разве не одно и то же?

2016-03-27 в 23:00 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Это разве не одно и то же?
Я не говорил, что это разные понятия...
Просто такой метод нахождения, который Вы применили справедлив только для пары оптимальных решений...
А в вычислениях я таки ошибся, не на тот коэффициент посмотрел... :bricks: ... данное решение действительно оптимально...

2016-03-27 в 23:15 

Ага, отлично, решение оптимально. Тогда, как вы сказали справедлив только для пары оптимальных решений...
Тогда `y_i=lambda_i`?

2016-03-27 в 23:31 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
MestnyBomzh, Ага, отлично, решение оптимально. - Ну, это Вам ещё надо проверить...
Ведь для любого допустимого решения исходной задачи Вы можете выявить активные ограничения и найти множители Лагранжа... :nope:
И тут надо либо применять некоторые утверждения теории двойственности... либо решать двойственную задачу целиком...

2016-03-27 в 23:34 

га, отлично, решение оптимально. - Ну, это Вам ещё надо проверить... - так Вы же уже согласились, что данное решение оптимально, нет? Да и моя проверка вполне легальна.

2016-03-27 в 23:46 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
так Вы же уже согласились, что данное решение оптимально, нет?
А как Вы это будете преподносить преподавателю?... :upset: ... типа "на одном сайте согласились, что решение оптимально"... :alles:

Да и моя проверка вполне легальна.
Про это Вы не обмолвились не словом... :nope:

2016-03-27 в 23:48 

Нет, это не домашнее задание, это я к экзамену готовлюсь, так что оформлением (если понадобится) займусь уже на экзамене.
Так вот, решение оптимально, на этом согласились. Дальше можно же утверждать или нет, что `lambda_i = y_i`

2016-03-27 в 23:57 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Нет, это не домашнее задание, это я к экзамену готовлюсь
В марте месяце?... :upset: ... настолько заранее или у Вас сессии два раза в семестр?...

так что оформлением
Тут вопрос не про оформление, а про знание теоретических положений... уж, коль скоро речь зашла об экзамене...

Дальше можно же утверждать или нет, что `lambda_i = y_i`
Ну, если Вы сами указываете на то, что В учебниках пишут, что `lambda_i` - это теневые цены. Но при этом они же пишут, что `y_i` - тоже теневые цены....

2016-03-28 в 00:04 

В марте месяце?... ... настолько заранее или у Вас сессии два раза в семестр?... 4 раза в год сессия.
Да, но вот тут и вопрос. В исходной задаче было 4+3 = 7 ограничений. то есть итого 7 лямбд. В двойственной же теперь у нас четыре игрека. Вот тут то я и не понимаю как такое может быть?

2016-03-28 в 00:08 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
. В исходной задаче было 4+3 = 7 ограничений. то есть итого 7 лямбд. В двойственной же теперь у нас четыре игрека.
Остальные лямбды - это дополнительные переменные, которые добавляют при приведении задачи к каноническому виду...

2016-03-28 в 00:09 

Остальные это какие? Которые соответствуют условиям `x_1>=0, x_2>=0, x_3>=0`?

2016-03-28 в 00:12 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Остальные это какие? - с пятой по седьмую... :)

2016-03-28 в 00:18 

я понял. Тогда получаем, что `y_1=5, y_2=0,y_3=3,y_4=0` (это оптимальной решение двойственной)?

2016-03-28 в 00:22 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Тогда получаем, что `y_1=5, y_2=0,y_3=3,y_4=0` (это оптимальной решение двойственной)?
Да... оно станет таковым, как только Вы проверите оптимальность... :alles: ...

2016-03-28 в 00:27 

Ну давайте пока что отталкиваться от предпосылки, что `(0,2,2)` было оптимальным.
Так вот, я тут прочитал, что `max` в исходнике должен быть равен `min` в двойственной. Здесь совпадет. Это всегда должно быть выполнено, верно?

2016-03-28 в 00:31 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Так вот, я тут прочитал, что `max` в исходнике должен быть равен `min` в двойственной. Здесь совпадет. Это всегда должно быть выполнено, верно?
Такое равенство выполняется только на оптимальных решениях... это называется критерием Канторовича...

2016-03-28 в 01:01 

Ну да, на оптимальных. Отлично.
А не могли бы Вы помочь с пунктом e)?
Там добавляется константа в правую часть первого неравенства и спрашивается, когда цена первого ресурса останется неизменной.
Так вот, проблема в том, что оптимум то может меняться, а цена оставаться той же. Единственное, что я понял, это то, что должно быть вот такое условие:
`((1),(2),(3)) = 5*((1),(1),(0))+?` вот под вопросом может же быть всё, что угодно

2016-03-28 в 01:13 

Ну, не всё, что угодно. Там сумма лямбд на активные ограничения

2016-03-28 в 01:36 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Вам не поможет простая попытка найти допустимое решение с первой координатой равной пяти... если говорится про оптимальность, то нужен критерий оптимальности...
Вот здесь Вам и нужно решение двойственной задачи... (если не обсчитался, то в правой части первого ограничения может стоять любое число из интервала `[0; 3]`) ...

2016-03-28 в 01:44 

Понял, решение двойственной у нас уже есть: `y_1=5, y_2=0, y_3=3, y_4=4`. Как его использовать и какой критерий?

2016-03-28 в 01:52 

Судя по моим записям с семинаров мы делали из неравенств равенства, добавляя к каждому из нервенств по `z_i`, а дальше решали систему относительно `x_1...x_n`

2016-03-28 в 02:12 

А, про двойственную понял. Нам нужно перейти к двойственной. Там было решение `(5,0,3,0)`. А теперь появляется коэффициент при `y_1`
Раньше в двойственной задаче активными были активные ограничения (2), (3), (5), (7) то есть получаем: `((2+delta),(3),(0),(1))=lambda_1*((1),(0),(-1),(0))+lambda_2*((0),(1),(1),(0))+lambda_3*((0),(1),(0),(0))+lambda_4*((0),(0),(0),(1))`

2016-03-28 в 02:17 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Там было решение `(5,0,3,4)`. - нет... было решение `(5,0,3,0)`...

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

   

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная