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

[suricat555]

1) По поводу примера, который мы решаем:
Вместо С можно подставить любое отрицательное число, из этого следует, что F(C) = - бесконечность; f min -> - бесконечность. Это верный ответ?

2) Предположим, если бы у нас был такой же пример, но стремился бы он не к min, а к  max,  
F (x) = 2x1 - x2 -> maх

То мы решали бы так же, чертили бы график, и перпендикуляры  тоже чертили к вектору?  Я имею в виду, что метод решения у нас одинаков, к чему бы не стремилась ф-ция: к max или к min ?  
Я не могу понять, для чего мы рисуем этот перпендикуляр. Вы не могли бы мне это объяснить, пожалуйста? В учебнике у меня сказано, что его нужно чертить, но что он нам дает - я не поняла.

[tig81]

1) По поводу примера, который мы решаем:
Вместо С можно подставить любое отрицательное число, из этого следует, что F(C) = - бесконечность; f min -> - бесконечность. Это верный ответ?

Вместо С можно подствить и любое положительное число. При С=-00, данная прямая будет касаться области допустимых значений?

2) Предположим, если бы у нас был такой же пример, но стремился бы он не к min, а к  max,  
F (x) = 2x1 - x2 -> maх
То мы решали бы так же, чертили бы график, и перпендикуляры  тоже чертили к вектору?  Я имею в виду, что метод решения у нас одинаков, к чему бы не стремилась ф-ция: к max или к min ?  

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

Я не могу понять, для чего мы рисуем этот перпендикуляр. Вы не могли бы мне это объяснить, пожалуйста? В учебнике у меня сказано, что его нужно чертить, но что он нам дает - я не поняла.

Это опорное как бы решение. Из всех таких прямых мы выбираем ту, в которой целевая функция достигает свое экстремальное значение (max или min).

[suricat555]

1) Я подставляла и положительные числа, но в этом случае перпендикуляр не пересекал область допустимых значений.

2) Вы не могли бы помочь мне решить ещё один пример?

f(x) = -2x₁ + 4x₂ -> max

Система уравнений:
3x₁ - x₂ <=6 (меньше или равно)
-x₁ + 2x₂ <=5
x₁ + x₂ >= 1


x₁ >=0
x₂ >=0


Чертим график и находим область допустимых значений (т.е.для каждой прямой вместо x1 и x2 подставляем точку (0,0), везде получаем верное рав-во, следовательно, штрихуем область, "внутри" полученного пятиугольника).

Вектор (-2; 4).
Рисуем перпендикуляры, двигаясь по направлению вектора.

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

[tig81]

1) Я подставляла и положительные числа, но в этом случае перпендикуляр не пересекал область допустимых значений.

Возможно, надо рисовать. НО похоже, что так. Т.е. задача решения не имеет.

2) Вы не могли бы помочь мне решить ещё один пример?
-x₁ + 2x₂ <=5

Должна проходить через точку (-5; 0), у вас на рисунке не похоже.

везде получаем верное рав-во,

Везде?

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

Вроде как да.

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

Теперь двигайте перпендикуляр так, чтобы он касался области в одной точке или по какой-то границе. Только перерисуйте прямую (2).

Ответ: \( f_{max}=f(0; 5/2)=10 \)

[suricat555]

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

f(x) = 3x₁ + x₂ -> max

Система ограничений:

x₂ - x₁ <=3 (меньше или равно)
x₁ <= 5
x₁ + x₂ <= 7


x₁ >=0
x₂ >=0

1) Вводим доп.неотрицат.переменные:

-x₁ + x₂ + x₃ = 3
x₁ + x₄ = 5
x₁ + x₂ + x₅ = 7

2) Выражаем свободные переменные (x1 x2) через основные

x₃ = 3 + x₁ - x₂
x₄ = 5 -   x₁
x₅ = 7 - x₁ + x₂


3) Выражаем целевую ф-цию через свободные переменные:

f(x) = 3x1 + x2

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

Ищем базисное решение:

x1      0            ?               ?
x2      0             ?             ?
x3  =  3  + x1 *   1  + x2 *   -1
x4      5            -1              0
x5      7            -1              1

То, что обозначено синим цветом:

Вместо x₁ x₂ подставляем 0, следовательно, получаем значения 3,5,7.


То, что обозначено зеленым:

Эти значения я брала из второго действия, где я выражала свободные переменные через основные, и эти значения - это коэффициенты возле x₁ x₂.


А как мне найти значения, где стоят знаки вопросов?

[tig81]

А каким методом надо решить?

[suricat555]

Симплексный метод решения.

[tig81]

А тогда, где симплекс таблицы?

[suricat555]

А что это такое? Я решаю по образцу, и у нас такого не было...

[suricat555]

У меня в методичке написан такой ход решения:
1. Составление канонической задачи л.п.
2. Поиск первоначального допустимого базисного решения.
3. Выражение целевой ф-ции через свободн.переменные (вот это у меня и не получается)
4. Проверка решения на оптимальность (если решение на maх, то решение оптимальное, если в выражении все коэф. при свободных переменных отрицательные)
5. Определение новой основной и свободной переменной.

[tig81]

Хм... Ну обычно все вычисления делаются в симплекс-таблицах... А так я не делала, поэтому немного затрудняюсь что-то вам посоветовать.
И тут не поняла:

2) Выражаем свободные переменные (x1 x2) через основные

x₃ = 3 + x₁ - x₂
x₄ = 5 -   x₁
x₅ = 7 - x₁ + x₂

А тут наоборот, все через х1, х2 выражено?!

[suricat555]

Ну просто я запуталась, что из этих переменных является свободными, что основными... Значит, выражаем основные через свободные.

[tig81]

Я конечно не совсем так делаю, но мне кажется, что надо наоборот.\

П.С. А так почитайте про симплекс таблицы

[suricat555]

Добрый вечер!

Вы не могли бы помочь мне с задачей (двойственная задача л.п.)?

F (x) = 2x1 + 18 x2 + 36 x3 + 10x4 -> min

Система ограничений:

-5 x1 - 3x2 + 3x3 + 2x4 + x5 >=8
2x1 + 4x2 + 2x3 - x4 - 3x5 >=1
x1,......,x5 >=0


Ф-ция цели двойственной задачи:

z = 8 y1 + 1y2

Система ограничений для двойственной задачи:

-5y1 + 2y2 >=2
-3y1 + 4y2 >=18
3y1 + 2y2 >=36
2y1 - y2 >=10
y1 - 3y2 >=0


Добавляем балансовые переменные (со знаком "+", если ф-ция стремится к min):

-5y1 + 2y2 + y3 >=2
-3y1 + 4y2 + y4 >=18
3y1 + 2y2 + y5 >=36
2y1 - y2+ y6 >=10
y1 - 3y2 + y7 >=0

-----

-5x1 - 3x2 + 3x3 + 2x4 + x5 + x6 >=8
2x1 + 4x2 + 2x3 - x4 - 3x5 + x7 >=1



А теперь нужно составить табличку соответствия переменных:


x1   x2   x3   x4   x5   x6   x7     (x1, x2,x3,x4,x5 - основные переменные, x6,x7 - дополнит.переменные)

y3   y4   y5   y6   y7  ?     ?      (y1,y2 - основные, y3,y4,y5,y6,y7 - дополнительные)

Я не могу определить соответствие между x6 x7 и y1 y2 , помогите, пожалуйста!

Но, как я понимаю, это не ответ?

[tig81]

А как конкретно задание звучит?