ЗЛП - минимизировать функцию

[artyomdevyatov]

Минимизировать функцию графическим методом.
Пробовал через онлайн-решалку, но она решает её как с 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}

[Deggial]

artyomdevyatov в сообщении #737368 писал(а):

Минимизировать функцию графическим методом.
...
Знаю, что сначала нужно уменьшить количество переменных до двух, но вот как...

В принципе, графическим методом можно решить и 3-хмерную задачу
Кстати, вводя новую переменную, можно избавиться от одного ограничения (от самого простого).

artyomdevyatov в сообщении #737368 писал(а):

Пробовал через онлайн-решалку, но она решает её как с 7ю переменными и непонятно зачем заполняет их (не выявил никакой закономерности), так что этот вариант не прошёл...

Похоже на приведение ЗЛП к форме М-задачи.

[artyomdevyatov]

Цитата:

вводя новую переменную, можно избавиться от одного ограничения

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

[Deggial]

artyomdevyatov в сообщении #737386 писал(а):

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

Может быть я чего-то не вижу, но я думаю, что не всякую 3-хмерную задачу ЗЛП можно свести к 2-мерной. И в данном случае думаю, что этого сделать нельзя.

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

[Cash]

Deggial в сообщении #737399 писал(а):

Хотя можно попытаться обосновать, что $x_3=0$

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

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

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

[artyomdevyatov]

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

[Deggial]

artyomdevyatov в сообщении #737421 писал(а):

Да в том-то и дело, что задание, скорее всего, было задано неверно.

Нормальное задание.

artyomdevyatov в сообщении #737421 писал(а):

Преподаватель сказал, что если не будет получаться, то можно заменить неравенства на равенства (при этом не указав какие).
Так что я заменил, получил $x_1 = x_2$ и задача стала детской. Надеюсь, прокатит

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