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:

2016-03-28 в 02:27 

Я немного подравил. Теперь верно. Решая систему я получил: `{(lambda_1=2+delta), (lambda_2=2+delta), (lambda_3=1-delta), (lambda_4=1):}`
Надо чтобы все лямбды были `>=0`, так как иначе точка - больше не оптимум (а нам нужно, чтобы остался оптимум), поэтому `delta in [-2;1]`

2016-03-28 в 02:47 

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

2016-03-28 в 02:52 

да, но мое рассуждение про смену оптимума было для исходной задачи. Когда я перешел к двойственной ей я уже говорю, что теперь у меня есть новая задача. У неё было решение `(5,0,3,0)`. И поскольку в моей новой задаче теневые цены это продукты (то есть была теневая цена, стал как бы продукт `y_1`), и теперь вопрос такой: а при каком дельта оптимум (были теневые цены в исходной задаче, в новой - это оптимум) не изменяется. Ну и дальше я просто записал условие первого порядка: градиент целевой функции раскладывается по градиентам активных ограничений. Так что пока не вижу ничего неверного в моем решении. Предлагаю взять какую-нибудь дельту, которая лежит в моем отрезке, но не лежит в вашем и проверить, сохраниться ли цена? Например, `delta=-1`

2016-03-28 в 02:54 

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

2016-03-28 в 03:05 

в этот раз получилось `delta>=-1`... Давайте попробуем взять `delta=4` и посмотреть у кого верно?

2016-03-28 в 03:12 

При `delta=4` получим вот такую систему для теневых цен:
`{(2y_1+7y_2+y_4->min), (y_1+y_2+y_4>=1), (y_1-y_3>=2), (y_2+y_3>=3),(y_i>=0):}`
И я утверждаю, что точка `(5,0,3,0)` по-прежнему будет оптимумом. Я это проверил. Значит `delta=4` подходит

2016-03-28 в 03:23 

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

В задании второго неравенства...а я для первого решал
Дык, про первое и написано в задании ... :nea:
Про второе - это Вы в задание (d) посмотрели...

2016-03-28 в 03:39 

Ну да, точно, спасибо, не туда посмотрел. Что же, тогда наши методы работают, это радует!
Не могли бы Вы помочь еще с одной задачей, или Вы уже уходите?

Тут я подумал вот как: `S=(abc)/4R` ну и еще три неравенства треугольника. Только вот как решать такую задачу нелинейную не знаю вообще... Есть еще идейка избавиться от третьей переменной с помощью теоремы синусов: `a=2Rsin(alpha), b=2Rsin(beta), c=2Rsin(pi-alpha-beta)`, так у нас получится функция двух переменных, которые ограничены `pi/2` и нулем. Но я всё равно не смог решить систему

2016-03-28 в 03:57 

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

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

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

Судя по методам Ваших решений, для пунктов (b) и (c) подразумевается использования обобщения метода множителей Лагранжа - теоремы Куна - Таккера...

2016-03-28 в 03:59 

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

   

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

главная