Линейное программирование (графический метод)

[suricat555]

Здравствуйте!

Помогите мне, пожалуйста, дорешать задачку.

F (x) = 2x₁ - x₂ -> min

Система неравенств:
x₁+ x₂ >= 4 (больше или равно)
3x₁ - x₂ <=0 (меньше или равно)



x₁ >= 0; x₂ >=0

Затем я строю график.

Ищем вектор n. Ориентируемся на коэффициенты  функции   n (2;-1)

А дальше я не знаю, что делать.

Помогите, пожалуйста, найти на графике область допустимых значений.

[tig81]

.ods - это что за разрешение?

[suricat555]

У меня график построен в программе OpenOffice. Не открывается?

[tig81]

нет, кидайте скрин

[suricat555]

Сейчас открывается?

[suricat555]

Я пример неправильно написала, извините!

В первом неравенстве x1 + x2 >=4

[tig81]

Сейчас открывается?

Да,Ю но лучше сохраняйте в формате .doc для 3 офиса.
Так а где ваша штриховка?
x1+ x2 >= 4: как определить, какую область заштриховывать. Для это берем произвольную точку, через которую не проходит заданная прямая, например, в данном случае удобнее взять точку (0; 0) и подставить в заданное неравенство. Тогда получаем: 0+0>= 4 или 0>= 4. Получили неверное неравенство, значит точка (0; 0) не лежит в заштрихованной области, т.е. штриховать надо область,оторая лежит выше заданной прямой.
Аналогично попробуйте разобраться со вторым неравенством.

[suricat555]

Если во втором неравенстве взять, к примеру, точку 2, то получится: 3*2 - 2 <=0, 4 <=0 - неверно - штрихуем ту область, которая находится выше.

Итак, область допустимых значений - это треугольник по оси x2 от (4; + бесконечн.), и линия от (1;3) до + бесконечности. Правильно? До бесконечности - потому что у нас есть ещё 2 неравенства x₁>=0 и x₂ >=0?

x₁ + x₂ = 4
3x₁ - x₂ = 0

x₁ = 4 - x₂
3x₁= x2

x₁ = 4 - 3x₁
4x₁ = 4;       x₁ = 1.

x₂ = 3


F (x) = 2 x₁ - x₂ = 2*1 - 3 = -1

Это и есть решение?

[tig81]

Если во втором неравенстве взять, к примеру, точку 2,

(2; 2) т.е.?

то получится: 3*2 - 2 <=0, 4 <=0 - неверно - штрихуем ту область, которая находится выше.

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

Итак, область допустимых значений - это треугольник по оси x2 от (4; + бесконечн.), и линия от (1;3) до + бесконечности. Правильно? До бесконечности - потому что у нас есть ещё 2 неравенства x₁>=0 и x₂ >=0?

x₁ + x₂ = 4
3x₁ - x₂ = 0

x₁ = 4 - x₂
3x₁= x2

x₁ = 4 - 3x₁
4x₁ = 4;      x₁ = 1.

x₂ = 3

Для восприятия сложно, надо рисунок.

[suricat555]

Да, точку (2;2).

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

А дальше из нашего условия берем неравенства и находим x₁ и x₂. Затем подставляем значения в функцию и находим ответ. Правильно?

[tig81]

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

Похоже, что да

А дальше из нашего условия берем неравенства и находим x₁ и x₂.

Это как?
Далее перпендикулярно вектору нормали N вы проводите прямую 2x1 - x2=С, где-то по середине допустимой области и т.к. задача на минимум то противоположно вектору N перемещаете эту прямую до крайней точки области (т.е. чтобы вся область допустимых значений находилась по одну сторону от прямой.)

[suricat555]

Далее перпендикулярно вектору нормали N вы проводите прямую 2x1 - x2=С, где-то по середине допустимой области и т.к. задача на минимум то противоположно вектору N перемещаете эту прямую до крайней точки области (т.е. чтобы вся область допустимых значений находилась по одну сторону от прямой.)

Вектор (2;-1).
Вот в эту прямую, которую Вы написали: 2x₁ - x₂=С, нужно подставлять какие-то значения вместо x₁ и x₂, чтобы её провести, или проводить просто перпендикулярно? Я не совсем понимаю, как это делать.   
Если ее проводить по допустимой области, то ее можно проводить бесконечно, ведь у нас сверху эта область никакой линией не ограничена...

[tig81]

Вектор (2;-1).
Вот в эту прямую, которую Вы написали: 2x₁ - x₂=С, нужно подставлять какие-то значения вместо x₁ и x₂, чтобы её провести, или проводить просто перпендикулярно? Я не совсем понимаю, как это делать.   

Вместо С подставьте любое значение и постройте прямую (как вы делали с прямыми в системе ограничений). Но можно просто ее провести перпендикулярно вектору нормали где-то по средине области

Если ее проводить по допустимой области, то ее можно проводить бесконечно, ведь у нас сверху эта область никакой линией не ограничена...

и т.к. задача на минимум то противоположно вектору N перемещаете эту прямую до крайней точки области (т.е. чтобы вся область допустимых значений находилась по одну сторону от прямой.)

[suricat555]

Получается, что я могу вместо С подставить любое отрицательное значение, и у меня эта перпендикулярная линия всё равно будет касаться допустимой области. С = - бесконечность. Это и есть ответ?


А если бы был точно такой же пример, но
F (x) = 2x1 - x2 ->max, метод решения был был бы такой же, но в последнем действии мы бы взяли наши неравенства

Система неравенств:
x1+ x2 >= 4 (больше или равно)
3x1 - x2 <=0 (меньше или равно)


и находили бы x₁ и x₂, а потом подставили бы в ф-цию и получили бы ответ, и всё?

[tig81]

честно говоря, не поняла