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-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:

   

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

главная