Версия для печати темы

Автор: Бандерлог 21.4.2009, 14:00

Задача состоит в том, чтобы минимизировать симплекс-методом функцию:
f(x1,x2)=x1^2+x2^2-20x1-30x2
с ограничениями
5x1+13x2<=51
15x1+7x2<=107
x1,x2>=0


По теореме кунна-такера составляю ограничения для симплекс-матрицы:
2x1-20+5L1+15L2-M1=0
2x2-30+13L1+5L2-M2=0
5x1+13x2+x3=51
15x1+7x2+x4=107

Но для окончательного построения симплекс-матрицы мне нужно составить на основе этих ограничений дополнительную минимизируемую функцию. И вот с этим у меня возник затык. Я так и не смог понять по какому принципу она строится.
Дальше симплекс-матрицу я решу своими силами, а вот с построением ее у меня никак не получается.
Заранее спасибо.

Автор: tig81 21.4.2009, 16:31

Если я правильно помню, то в случае задачи на минимум, ограничеия должны быть виды ">=".

Автор: Бандерлог 22.4.2009, 5:43

Ну ограничения не я составлял, так что приходится решать с такими, которые есть. Тем более что ограничения не влияют на то, что нам надо искать, минимум или максимум. Я могу взять функцию U(x)=-f(x) и искать ее максимум. При этом ограничения на х1 и х2 останутся прежними и ответ будет тем же самым. Так что тут не в ограничениях дело.

Автор: Бандерлог 22.4.2009, 8:27

Пытался делать вот по этому описанию:
http://iasa.org.ua/iso.php?lang=eng&ch=5&sub=5

Так как тут описывается максимизация функции, то для однообразия также решил ввести дополнительную функцию U(x)=-x1^2-x2^2+20x1+30x2 и максимизировать ее. При этом ограничения на x1 и х2 остаются неизменными

5x1+13x2<=51
15x1+7x2<=107
x1,x2>=0

Составил функцию Лагранджа
U(x1,x2,L1,L2)=-x1^2-x2^2+20x1+30x2+L1(51-5x1-13x2)+L2(107-15x1-7x2)
Применяю теорему Куна-Таккера
dU/dx1=-2x1+20-5L1-15L2<=0
dU/dx2=-2x2+30-13L1-7L2<=0
dU/dL1=51-5x1-13x2>=0
dU/dL2=107-15x1-7x2>=0

И условия дополняющей нежескости:
dU/dx1 *х1=0 dU/dx2 *х2=0 dU/dL1 *L1=0

Вводим свободные переменные х3,х4,х5,х6
-2x1+20-5L1-15L2+х3=0
-2x2+30-13L1-7L2+х4=0
51-5x1-13x2-х5=0
107-15x1-7x2-х6=0

И условие дополняющей нежескости:
х1*х3=0 х2*х4=0 х5*L1=0

Получаем:
2x1+5L1+15L2-x3=20
2x2+13L1+7L2-x4=30
5x1+13x2+x5=51
15x1+7x2+x6=107

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

Автор: crazymaster 22.4.2009, 12:25

Цитата(Бандерлог @ 22.4.2009, 14:27)

Автор: Бандерлог 22.4.2009, 12:35

Крейзи, спасибо огромное. До меня таки дошло как это все строится.
Ведь для нахождения минимума и максимума надо производные приравнять к нулю. Соответственно минимизируемая функция - сумма дополнительных переменных, введенных для приравнивания производных к нулю.

Автор: crazymaster 22.4.2009, 13:06

Цитата(Бандерлог @ 22.4.2009, 18:35)

Автор: Бандерлог 22.4.2009, 13:10

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

Автор: Пользователь 27.5.2009, 19:54

Помогите пожалуйста!!!!у меня точно такая же задача.в принципе все понимаю, как решать!НО, решение не получается никак!!!говорят что это м б из-за холостова шага в симплекс-методе поделитесь решием,пожаааалуйста,оч оч надо!!!!