графическое решение задачей линейного программирования на пл

[arhangelnn]

z (x)=3x1-x2+2x3=>max
Функция:
-3x1+2x2+x3=<3
x1+3x2+2x3=<14
2x+3x2+x3=<16
Xi>=0(i=1,3)
Народ помогите пожалуйста решить, очень надо:(

[Brukvalub]

А что не получается?

[arhangelnn]

базисный неизвестный понять не могу как найти...запутался:(

[Brukvalub]

arhangelnn в сообщении #203689 писал(а):

базисный неизвестный понять не могу как найти...запутался

Что такое базисный неизвестный в графическом способе решения?

[мат-ламер]

Может просто перебрать все вершины многогранника?

[Brukvalub]

мат-ламер в сообщении #203788 писал(а):

Может просто перебрать все вершины многогранника?

Там же в заголовке написано, что решать нужно графически на пл(оскости), а какие на плоскости могут быть многогранники?

[Yu_K]

Для Вашей постановки подойдет графический метод в пространственном случае - у Вас же три переменных в ограничениях и в целевой функции. Если хотя бы одно из неравенств в ограничениях было строгим равенством (скорее всего Вы потеряли такое ограничение) то можно было бы использовать графический метод на плоскости. А если все же пространственная задача - семейство "линий" уровня целевой функции будут параллельные плоскости. Ограничения дадут многогранник допустимых значений. Ищите точку где одна из "плоскостей уровня" коснется многогранника допустимых значений. Из названия темы нужно тогда убрать "пл".
Хорошая показательная задачка особенно совместно с симплекс методом - можно посмотреть как симплекс-метод последовательно перебирает вершины многогранника, улучшая каждый раз значение целевой функции.

[Spectator]

Для начала следует задачу линейного программирования записать в стандартной форме:

\[f({x_i}) = \sum\limits_{i = 1}^n {{c_i}{x_i}} \to \max \]

\[{a_{11}}{x_1} + {a_{12}}{x_2} + \ldots + {a_{1n}}{x_n} = {b_1},\]

\[{a_{21}}{x_1} + {a_{22}}{x_2} + \ldots + {a_{2n}}{x_n} = {b_2},\]

\[ \cdots \]

\[{a_{p1}}{x_1} + {a_{p2}}{x_2} + \ldots + {a_{pn}}{x_n} = {b_p},\]

\[{x_i} \ge 0,\,\,i = 1, \ldots ,n,\,\,p < n.\]

Задача с минимизацией критерия оптимальности сводится к стандартной заменой

\[f(x)\]

на

\[ - f(x).\]

Ограничения-неравенства превращают в равенства, вводя дополнительные неотрицательные переменные

\[{S_q} > 0.\]

Теперь, что касается непосредственно геометрического метода (для задачи, записанной в стандартной форме).

Поскольку каждая переменная

\[{x_i} \ge 0,\,\,i = 1, \ldots ,n\]

Положим переменные

\[{x_1}\]

и

\[{x_2}\]

свободными и разрешим систему

\[p = n - 2\]

линейных алгебраических уравнений (приведенную выше) относительно базисных переменных.

\[{x_3} = {a_{31}}{x_1} + {a_{32}}{x_2} + {\beta _3},\]

\[{x_4} = {a_{41}}{x_1} + {a_{42}}{x_2} + {\beta _4},\]

\[ \cdots \]

\[{x_n} = {a_{n1}}{x_1} + {a_{n2}}{x_2} + {\beta _n},\]

где каждая базисная переменная

\[{x_i} \ge 0,\,\,i = 3, \ldots ,n\]

неотрицательна, то допустимые решения должны лежать в неотрицательном квадранте плоскости

\[\left( {{x_1},{x_2}} \right).\]

Полагая в предыдущих уравнениях

\[{x_i} = 0,\,\,i = 3, \ldots ,n,\,\]

построим

\[n - 2\]

прямые линии

\[{a_{i1}}{x_1} + {a_{i2}}{x_2} + {\beta _i} = 0,\]

каждая из которых определяет допустимую полуплоскость

\[{x_i} \ge 0,\]

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

\[y = f(x)\]

через свободные переменные:

\[y = {\lambda _1}{x_1} + {\lambda _2}{x_2} + {\lambda _0} \to \max. \]

Постоянное слагаемое

\[{\lambda _0}\]

можно отбросить.

Строим на плоскости опорную прямую

\[{y_0} = {\lambda _1}{x_1} + {\lambda _2}{x_2} = 0.\]

При параллельном перемещении опорной прямой велечина

\[{y_0}\]

будет изменяться в зависимости от коэффициентов

\[{\lambda _1}\]

и

\[{\lambda _2}.\]

Перемещаем опорную прямую в сторону увеличения

\[{y_0}.\]

В опорной точке

\[{P^ * }\]

(т.е. последней точке многоугольника, которую пересечет опорная прямая) функция

\[{y_0}\]

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

[ASA]

Spectator писал(а):

Положим переменные

\[{x_1}\]

и

\[{x_2}\]

свободными и разрешим систему

\[p = n - 2\]

линейных алгебраических уравнений ... относительно базисных переменных.

Увы, при приведении исходной системы к стандартной форме мы получим 3x6-матрицу ранга 3. И, стало быть, свободных переменных тоже 3.

[Spectator]

ASA писал(а):

Spectator писал(а):

Положим переменные

\[{x_1}\]

и

\[{x_2}\]

свободными и разрешим систему

\[p = n - 2\]

линейных алгебраических уравнений ... относительно базисных переменных.

Увы, при приведении исходной системы к стандартной форме мы получим 3x6-матрицу ранга 3. И, стало быть, свободных переменных тоже 3.

Да, согласен. Надо брать 3 свободных переменных.

Получается, что для решения задачи геометрическим методом на плоскости, необходимо, чтобы

\[n - r = 2,\]

где

\[n\]

- число переменных, а

\[r\]

- число ограничений.

[ASA]

Можно так. Заменив первое неравенство на равенство, исключаем одну из переменных. Далее решаем задачу ЛП с двумя переменными графически на плоскости. Затем тоже самое делаем со вторым неравенством и с третьим. Из полученных решений задач ЛП выбираем то, которое дает большее значение целевой функции.
Да, забыл. Еще надо рассмотрить случай $x_1=0$. Далее, соответственно, $x_2=0$ и $x_3=0$.