Здравствуйте.
Вы не могли бы проверить, правильно ли я решила задачу:
Решить задачу графическим способом. Найти такие значения действительных переменных 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
первый раз решаю такие задачи, поэтому не уверена.
Заранее спасибо

х1 тоже неотрицательно? Вроде да

почему двойственная на минимум, раз исходная на минимум. Т.к. исходная задача на мининмум, то ее надо привести к каноническому виду, т.е. все неравенства должны быть вида "больше равно". Для первого это не выполняется.

у меня не так.
Двойственная задача

Аналогично

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

Тогда получится так:
1)-2y1+4y2<=1
-y1+y2>=2
Q=-4y1+4y2->max

2) -2y1+y2<=2
y1+2y2>=1
Q=-4y1+2y2->max
Так??

как приводили?

Посмотрите здесь, здесь, здесь, здесь и наконец здесь.

Спасибо. Теперь поняла.
Вы не посмотрите, я правильно потом решила?

1)-2y1+4y2=1
-y1+y2>=2
Q=-4y1+4y2->max

2) -2y1+y2<=2
y1+2y2=1
Q=-4y1+2y2->max

Итак, имеем задачу
(IMG:http://s49.radikal.ru/i126/0811/ae/599586905b93.png)
Приводим систему ограничений к виду: неравенства "больше равно" (т.к. задача на минимум)
(IMG:http://s46.radikal.ru/i113/0811/89/a85f4d29dd09.png)
Матрица
(IMG:http://i002.radikal.ru/0811/6e/054642bffb9f.png)
Тогда получаем двойственную задачу: (т.к. на переменную х1 не накладывается никакого ограничения, то первое условие в системе огрнаничений будет равенством, x2>=0 - тогда второе ограничение неравенство):
(IMG:http://s55.radikal.ru/i150/0811/ff/0da9cb28ddeb.png)

П.С. Вроде так.

Здравствуйте еще раз.
Мне преподаватель написал, что все неправильно. Помогите, пожалуйста, исправить.
Решить задачу графическим способом. Найти такие значения действительных переменных 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)
И двойственная задача тоже неправильно найдена. Подскажите, пожалуйста, где я ошиблась.
Заранее спасибо.

Область будет не треугольник, т.к. на переменную х2 не накладывается условие неотрицательности.

почему именно эту точку? Для прямой уровня или это оптимальный план?

это как?

Получается, что функция достигает минимум на прямой x1+2x2=2, а значит и в любой точке этой прямой, т.е. и в т.A(0;1), причем Qmin=1.

А какая двойственная задача получилась?

Спасибо.

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

Я вот этого немного не поняла. Так я правильно нашла минимум?



-2y1+y2<=2
-y1+2y2<=1

-4y1+2y2->max

будет "треугольник", но только он не будет ограничен осью Оу. Вроде так.

ясно

ну вы минимум не указали, а точку нашли правильно. Только в этой задаче получается, что она имеет бесконечно много оптимальных планов, т.к. минимум достигается не в одной точке области допустимых решений, а на целой ее границе.

Т.к. на переменную х2 не накладывается никакого условия, то второе неравенство в системе орграничений двойственной задачи будет равенством. Т.к. ограничения исходной задачи неравенства, то переменные двойственной задачи будут неотрицательные. Поэтому двойственная задача вроде будет такой:
Q*=-4y1+2y2->max
-2y1+y2<=2
-y1+2y2<=1
y1,y2>=0
П.С. Надеюсь, что на ночь глядя ничего не напутала. Если что, то поправьте , пожалуйста.

Скачайте еще книгу Акулич И.Л. Математическое программирование в примерах и задачах и посмотрите там. Вроде доходчиво написана, рассмотрены примеры.

Спасибо

Не поняла. x1 - только положительные, вроде будет ограничен ox2? а т.к. x2 может принимать отрицательные значения, то я так понимаю, снизу не ограничено. Или нет?

т.е. функция достигнет своего минимального значения в точке Q(0;1)=1?

Двойственная вроде так, только я тоже боюсь ошибиться=))
И еще я когда брала произвольную точку (1;1) получилось Q=3
Прямая уровня имеет вид: 2x1+x2=3
А у меня это все перечеркнуто почему-то и точка моя зачеркнута была=((

ну так тяжела вокруг да около, сможете файлик прикрепить с областью, которую описываете?!

тут у вас смешались и кони и люди, т.к. Q(0;1)=1 - это не точка.

(IMG:style_emoticons/default/smile.gif)

тяжело сказать, что имелось в виду

т.е. в этой точке функция принимает минимальное значение

А так вроде правильно?

т.е. в точке (0;1) функция апринимает мин значение

вроде да, если сама "не напахала" (IMG:style_emoticons/default/smile.gif)

Спасибо большое за помощь=)))

(IMG:style_emoticons/default/smile.gif)