2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 ЗЛП - минимизировать функцию
Сообщение16.06.2013, 18:48 
Аватара пользователя


27/12/11
17
Минимизировать функцию графическим методом.
Пробовал через онлайн-решалку, но она решает её как с 7ю переменными и непонятно зачем заполняет их (не выявил никакой закономерности), так что этот вариант не прошёл...
Знаю, что сначала нужно уменьшить количество переменных до двух, но вот как...

Заранее благодарен за любую помощь, я постоянно проверяю тему в надежде на любой ответ.

$z = x_1+3x_2+3x_3 \to \min$

\begin{aligned}
x_2+x_3\leqslant 3 \\
x_1-x_2\geqslant 0 \\
x_2\geqslant 1 \\
3x_1+x_2\leqslant 15
\end{aligned}

 Профиль  
                  
 
 Re: ЗЛП - минимизировать функцию
Сообщение16.06.2013, 19:33 
Супермодератор
Аватара пользователя


20/11/12
5728
artyomdevyatov в сообщении #737368 писал(а):
Минимизировать функцию графическим методом.
...
Знаю, что сначала нужно уменьшить количество переменных до двух, но вот как...
В принципе, графическим методом можно решить и 3-хмерную задачу :-)
Кстати, вводя новую переменную, можно избавиться от одного ограничения (от самого простого).

artyomdevyatov в сообщении #737368 писал(а):
Пробовал через онлайн-решалку, но она решает её как с 7ю переменными и непонятно зачем заполняет их (не выявил никакой закономерности), так что этот вариант не прошёл...
Похоже на приведение ЗЛП к форме М-задачи.

 Профиль  
                  
 
 Re: ЗЛП - минимизировать функцию
Сообщение16.06.2013, 19:42 
Аватара пользователя


27/12/11
17
Цитата:
вводя новую переменную, можно избавиться от одного ограничения

А зачем нам от него избавляться? Количество переменных нужно уменьшить, а не увеличить :-)
Можно конечно решать и 3-х мерную задачу, но имея под рукой двухмерную бумагу хотелось бы решать 2-х мерную задачу. Да и преподаватель требует свести задачу к двум неизвестным.

 Профиль  
                  
 
 Re: ЗЛП - минимизировать функцию
Сообщение16.06.2013, 20:36 
Супермодератор
Аватара пользователя


20/11/12
5728
artyomdevyatov в сообщении #737386 писал(а):
Можно конечно решать и 3-х мерную задачу, но имея под рукой двухмерную бумагу хотелось бы решать 2-х мерную задачу. Да и преподаватель требует свести задачу к двум неизвестным.
Может быть я чего-то не вижу, но я думаю, что не всякую 3-хмерную задачу ЗЛП можно свести к 2-мерной. И в данном случае думаю, что этого сделать нельзя.

Хотя можно попытаться обосновать, что $x_3=0$. Если это сделать, то задача сведется к 2-мерной, хотя прием, конечно, будет необщим.
Вообще, нам надо найти минимум линейной функции. В данном случае ответ довольно очевиден.

 Профиль  
                  
 
 Re: ЗЛП - минимизировать функцию
Сообщение16.06.2013, 21:27 
Заслуженный участник


12/09/10
1547
Deggial в сообщении #737399 писал(а):
Хотя можно попытаться обосновать, что $x_3=0$

Это если предположить, что переменные неотрицательны. Что не факт...
Хотя, с другой стороны, иначе и минимума не будет.

-- Вс июн 16, 2013 22:30:50 --

Ну да, неотрицательность обычно по умолчанию подразумевается...

 Профиль  
                  
 
 Re: ЗЛП - минимизировать функцию
Сообщение16.06.2013, 23:04 
Аватара пользователя


27/12/11
17
Да в том-то и дело, что задание, скорее всего, было задано неверно.
Преподаватель сказал, что если не будет получаться, то можно заменить неравенства на равенства (при этом не указав какие).
Так что я заменил, получил $x_1 = x_2$ и задача стала детской. Надеюсь, прокатит :o

 Профиль  
                  
 
 Re: ЗЛП - минимизировать функцию
Сообщение17.06.2013, 17:33 
Супермодератор
Аватара пользователя


20/11/12
5728
artyomdevyatov в сообщении #737421 писал(а):
Да в том-то и дело, что задание, скорее всего, было задано неверно.
Нормальное задание.

artyomdevyatov в сообщении #737421 писал(а):
Преподаватель сказал, что если не будет получаться, то можно заменить неравенства на равенства (при этом не указав какие).
Так что я заменил, получил $x_1 = x_2$ и задача стала детской. Надеюсь, прокатит :o
Фокусы какие-то безосновательные. Лучше так: пусть система неравенств задает многогранник $D$, ЦФ $f(x_j)$ возрастает по всем переменным, $f(x_j)\to\min$. Докажите, что если существует параллельный перенос $T$ многогранника $D$ такой, что $O\in T(D)$ и $T(D)$ остается лежать в области $x_j\geqslant 0$, то $T^{-1}(O)$ - минимум ЦФ.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group