Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Образовательный студенческий форум _ Разное _ Линейное программирование
Автор: user 11.11.2008, 10:03
Здравствуйте.
Вы не могли бы проверить, правильно ли я решила задачу:
Решить задачу графическим способом. Найти такие значения действительных переменных x1 и x2, для которых целевая функция Q(x1,x2) принимает минимальное значение:
1) 2x1+x2<=4
x2>=0
4x1+x2>=4
Q(x1,x2)=x1+2x2
2)2x1+x2<=4
x1>=0
x1+2x2>=2
Q(x1,x2)=2x1+x2
Составить условие двойственной задачи.
1
У меня получилось: функция достигнет своего минимального значения в точке (1;0)
Двойственная задача
Q=4y1-4y2->min
2y1-4y2>=-1
y1-y2<=-2
2
У меня получилось: функция достигнет своего минимального значения в точке (0;2)
Двойственная задача
Q=4y1-2y2->min
2y1-y2>=-2
y1-2y2<=-1
первый раз решаю такие задачи, поэтому не уверена.
Заранее спасибо
Автор: tig81 11.11.2008, 18:11
Здравствуйте.
Вы не могли бы проверить, правильно ли я решила задачу:
Решить задачу графическим способом. Найти такие значения действительных переменных x1 и x2, для которых целевая функция Q(x1,x2) принимает минимальное значение:
1) 2x1+x2<=4
x2>=0
4x1+x2>=4
У меня получилось: функция достигнет своего минимального значения в точке (1;0)
х1 тоже неотрицательно? Вроде да
Q=4y1-4y2->min
2y1-4y2>=-1
y1-y2<=-2
почему двойственная на минимум, раз исходная на минимум. Т.к. исходная задача на мининмум, то ее надо привести к каноническому виду, т.е. все неравенства должны быть вида "больше равно". Для первого это не выполняется.
x1>=0
x1+2x2>=2
Q(x1,x2)=2x1+x2
У меня получилось: функция достигнет своего минимального значения в точке (0;2)
у меня не так.
Двойственная задача
2y1-y2>=-2
y1-2y2<=-1
первый раз решаю такие задачи, поэтому не уверена.
Заранее спасибо
Аналогично
Автор: user 11.11.2008, 18:42
Я просто смотрела по примеру и так поняла (наверное, неправильно), что прямую задачу сначала нужно привести к максимуму.
Тогда получится так:
1)-2y1+4y2<=1
-y1+y2>=2
Q=-4y1+4y2->max
2) -2y1+y2<=2
y1+2y2>=1
Q=-4y1+2y2->max
Так??
Автор: tig81 11.11.2008, 18:45
Я просто смотрела по примеру и так поняла (наверное, неправильно), что прямую задачу сначала нужно привести к максимуму.
как приводили?
Посмотрите http://www.kgtu.runnet.ru/WD/TUTOR/lp/lp02.html, http://www.ccas.ru/mmes/educat/lab01/7/dwoystv.html, http://www.intuit.ru/department/mathematics/mathprog/5/2.html, http://first.boom.ru/Products/Theory/twiced.htm и наконец http://www.mathelp.spb.ru/book1/lprog5.htm.
Автор: user 11.11.2008, 18:48
Спасибо. Теперь поняла.
Вы не посмотрите, я правильно потом решила?
Автор: user 11.11.2008, 19:03
1)-2y1+4y2=1
-y1+y2>=2
Q=-4y1+4y2->max
2) -2y1+y2<=2
y1+2y2=1
Q=-4y1+2y2->max
Автор: tig81 11.11.2008, 19:18
Тогда получится так:
1)-2y1+4y2<=1
-y1+y2>=2
Q=-4y1+4y2->max
Итак, имеем задачу
http://www.radikal.ru
Приводим систему ограничений к виду: неравенства "больше равно" (т.к. задача на минимум)
http://www.radikal.ru
Матрица
http://www.radikal.ru
Тогда получаем двойственную задачу: (т.к. на переменную х1 не накладывается никакого ограничения, то первое условие в системе огрнаничений будет равенством, x2>=0 - тогда второе ограничение неравенство):
http://www.radikal.ru
П.С. Вроде так.
Автор: user 26.1.2009, 18:38
Здравствуйте еще раз.
Мне преподаватель написал, что все неправильно. Помогите, пожалуйста, исправить.
Решить задачу графическим способом. Найти такие значения действительных переменных x1 и x2, для которых целевая функция Q(x1,x2) принимает минимальное значение:
2)2x1+x2<=4
x1>=0
x1+2x2>=2
Q(x1,x2)=2x1+x2
Я построила прямую 2x1+x2=4 по точкам (0;4) и (2;0) и прямую x1+2x2=2 по точкам (0;1) и (2;0)
у меня получился треугольник ABC (a(0;1), B(0;4), C(2;0)) - область допустимых решений
Взяла произвольную точку (1;1)? подставила ее координаты в функцию Q
получилось Q=3
Прямая уровня имеет вид: 2x1+x2=3
Направление убывания функции будет совпадать с вектором (2;1)=> функция достигнет своего минимального значения в точке A(0;1)
И двойственная задача тоже неправильно найдена. Подскажите, пожалуйста, где я ошиблась.
Заранее спасибо.
Автор: tig81 26.1.2009, 22:00
Я построила прямую 2x1+x2=4 по точкам (0;4) и (2;0) и прямую x1+2x2=2 по точкам (0;1) и (2;0)
у меня получился треугольник ABC (a(0;1), B(0;4), C(2;0)) - область допустимых решений
Область будет не треугольник, т.к. на переменную х2 не накладывается условие неотрицательности.
почему именно эту точку? Для прямой уровня или это оптимальный план?
это как?
Получается, что функция достигает минимум на прямой x1+2x2=2, а значит и в любой точке этой прямой, т.е. и в т.A(0;1), причем Qmin=1.
А какая двойственная задача получилась?
Автор: user 26.1.2009, 22:12
Спасибо.
Область будет не треугольник, т.к. на переменную х2 не накладывается условие неотрицательности.
т.е. будет треугольник, а также нижняя область между двумя прямыми?
почему именно эту точку? Для прямой уровня или это оптимальный план?
Получается, что функция достигает минимум на прямой x1+2x2=2, а значит и в любой точке этой прямой, т.е. и в т.A(0;1), причем Qmin=1.
А какая двойственная задача получилась?
-2y1+y2<=2
-y1+2y2<=1
-4y1+2y2->max
Автор: tig81 26.1.2009, 22:32
т.е. будет треугольник, а также нижняя область между двумя прямыми?
будет "треугольник", но только он не будет ограничен осью Оу. Вроде так.
ясно
ну вы минимум не указали, а точку нашли правильно. Только в этой задаче получается, что она имеет бесконечно много оптимальных планов, т.к. минимум достигается не в одной точке области допустимых решений, а на целой ее границе.
-y1+2y2<=1
-4y1+2y2->max
Т.к. на переменную х2 не накладывается никакого условия, то второе неравенство в системе орграничений двойственной задачи будет равенством. Т.к. ограничения исходной задачи неравенства, то переменные двойственной задачи будут неотрицательные. Поэтому двойственная задача вроде будет такой:
Q*=-4y1+2y2->max
-2y1+y2<=2
-y1+2y2<=1
y1,y2>=0
П.С. Надеюсь, что на ночь глядя ничего не напутала. Если что, то поправьте , пожалуйста.
Скачайте еще книгу http://listlib.narod.ru/vichteh/aAkulich.html и посмотрите там. Вроде доходчиво написана, рассмотрены примеры.
Автор: user 26.1.2009, 22:39
Спасибо
будет "треугольник", но только он не будет ограничен осью Оу. Вроде так.
Не поняла. x1 - только положительные, вроде будет ограничен ox2? а т.к. x2 может принимать отрицательные значения, то я так понимаю, снизу не ограничено. Или нет?
ну вы минимум не указали, а точку нашли правильно. Только в этой задаче получается, что она имеет бесконечно много оптимальных планов, т.к. минимум достигается не в одной точке области допустимых решений, а на целой ее границе.
т.е. функция достигнет своего минимального значения в точке Q(0;1)=1?
Т.к. на переменную х2 не накладывается никакого условия, то второе неравенство в системе орграничений двойственной задачи будет равенством. Т.к. ограничения исходной задачи неравенства, то переменные двойственной задачи будут неотрицательные. Поэтому двойственная задача вроде будет такой:
Q*=-4y1+2y2->max
-2y1+y2<=2
-y1+2y2<=1
y1,y2>=0
П.С. Надеюсь, что на ночь глядя ничего не напутала. Если что, то поправьте , пожалуйста.
Двойственная вроде так, только я тоже боюсь ошибиться=))
И еще я когда брала произвольную точку (1;1) получилось Q=3
Прямая уровня имеет вид: 2x1+x2=3
А у меня это все перечеркнуто почему-то и точка моя зачеркнута была=((
Автор: tig81 27.1.2009, 16:05
Не поняла. x1 - только положительные, вроде будет ограничен ox2? а т.к. x2 может принимать отрицательные значения, то я так понимаю, снизу не ограничено. Или нет?
ну так тяжела вокруг да около, сможете файлик прикрепить с областью, которую описываете?!
тут у вас смешались и кони и люди, т.к. Q(0;1)=1 - это не точка.
Прямая уровня имеет вид: 2x1+x2=3
А у меня это все перечеркнуто почему-то и точка моя зачеркнута была=((
тяжело сказать, что имелось в виду
Автор: user 27.1.2009, 16:32
тут у вас смешались и кони и люди, т.к. Q(0;1)=1 - это не точка.
т.е. в этой точке функция принимает минимальное значение
тяжело сказать, что имелось в виду
А так вроде правильно?
Автор: tig81 27.1.2009, 17:23
т.е. в этой точке функция принимает минимальное значение
т.е. в точке (0;1) функция апринимает мин значение
вроде да, если сама "не напахала"
Автор: user 27.1.2009, 17:26
Спасибо большое за помощь=)))
Автор: tig81 27.1.2009, 17:32
Русская версия Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)