2016 Геометрический метод

1. Геометрический метод решения задач ЛП

2.

Графически могут решаться
• задачи, заданные в произвольной форме,
содержащие не более двух переменных,
• задачи, заданные в канонической форме, с
числом свободных переменных n − m 2 ,
• задачи, в произвольной форме записи,
которые после приведения к канонической
форме будут содержать не более двух
свободных переменных n − m 2.

3.

Графически могут решаться
• задачи, заданные в произвольной форме,
содержащие не более двух переменных,
• задачи, заданные в канонической форме, с
числом свободных переменных n − m 2 ,
• задачи, в произвольной форме записи,
которые после приведения к канонической
форме будут содержать не более двух
свободных переменных n − m 2.

4.

Графически могут решаться
• задачи, заданные в произвольной форме,
содержащие не более двух переменных,
• задачи, заданные в канонической форме, с
числом свободных переменных n − m 2 ,
• задачи, в произвольной форме записи,
которые после приведения к канонической
форме будут содержать не более двух
свободных переменных n − m 2.

5.

Этапы графического решения задачи ЛП
• Этап 1 – построение области допустимых
решений.
• Этап 2 – построение в допустимой
области оптимального плана

6.

Рассмотрим реализацию метода
на следующем примере:
f ( x) = 2x1 + 2x2 → max
3x1 − 2 x2 −6,
3x1 + x2 3,
x 3
1

7.

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

8.

Построение первой прямой
(1) 3 х1 – 2 х2 = – 6
x1 x2
+ =1
−2 3

9.

Построение первой прямой
(1) 3 х1 – 2 х2 = – 6
x1 x2
+ =1
−2 3

10.

x2
x1 x2
+ =1
−2 3
(1)
7.5
3
-2
1
3
x1

11.

Построение второй прямой
(2) 3 х1 + х2 = 3
x2
x1 + = 1
3

12.

Построение второй прямой
(2) 3 х1 + х2 = 3
x2
x1 + = 1
3

13.

x2
x2
x1 + = 1 (2)
3
(1)
7.5
3
-2
1
-6
3
x1

14.

Построение третьей прямой
(3) х1= 3

15.

x2
(3) х1= 3
(1)
7.5
(3)
(2)
3
-2
1
-6
3
x1

16.

Построение первой полуплоскости
•По знакам неравенств определим
область решений задачи.

17.

Построение первой полуплоскости
(1) 3 х1 – 2 х2 – 6
Выбираем точки А(-2; 3) и В(0;0),
принадлежащие разным полуплоскостям.
А(-2; 3)
B(0; 0)
3·(-2) - 2·3 -6
3·0 - 2·0 -6
-12 -6
0 -6
(неверно)
(верно)

18.

x2
7.5
(1)
A(-2;3)
3
-12 -6
0 -6
-2
B(0;0)
1
3
x1

19.

Построение второй полуплоскости
(2) 3 х1 + х2 3
Выбираем точки А(3; 3) и В(0;0),
принадлежащие разным полуплоскостям.
А(3; 3)
B(0; 0)
3·3 + 3 3
3·0 + 0 3
12 3
0 3
(верно)
(неверно)

20.

x2
7.5
(1)
(2)
A(3; 3)
3
12 3
-2
0 3
B(0;0)
1
3
x1

21.

Построение третьей полуплоскости
(3) х1 3
Выбираем точки А(4; 3) и В(0;0),
принадлежащие разным полуплоскостям.
А(4; 3)
B(0; 0)
4 3
0 3
(неверно)
(верно)

22.

x2
(1)
7.5
(3)
(2)
A(4; 3)
3
4 3
0 3
B(0;0)
-2
1
3
x1

23.

x2
(1)
7.5
(3)
(2)
3
-2
1
3
x1

24.

x2
(1)
7.5
B
(3)
(2)
A
3
D
-2
1
Область допустимых
решений – выпуклый
многоугольник (D).
-6
x1
3
C

25.

Построение
области допустимых решений
Какие варианты ОДР возможны?

26.

x2
(1)
7.5
B
(3)
(2)
A
3
D
-2
1
Область допустимых
решений – выпуклый
многоугольник (D).
-6
x1
3
C

27.

x2
(1)
7.5
(2)
3
D
-2
Область допустимых
решений – выпуклая
многоугольная
неограниченная область.
1
x1

28.

x2
(1)
7.5
(3)
(2)
3
-2
Области допустимых
решений – пустое
множество.
1
3
x1

29.

x2
(1)
7.5
(2)
(3)
F
-2
Области допустимых
решений – единственная
точка (F).
1
3
x1

30. Направление наискорейшего возрастания функции показывает вектор-градиент. Вектор-градиент целевой функции имеет вид .

Построение оптимального решения
Направление наискорейшего
возрастания функции показывает
вектор-градиент.
Вектор-градиент целевой
функции имеет вид с = (с1; с2 ) .

31. Строим вектор целевой функции.

Построение оптимального решения
Строим вектор целевой функции.
L = 2 x1 + 2 x2
с = (2; 2)

32.

x2
(1)
7.5
B
(3)
(2)
A
3
2
С = (2;2)
D
1
-2
1
-6
2
x1
3
C

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

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

34. Линией уровня называется прямая, на которой функция принимает постоянное значение. Уравнение линии уровня имеет вид . Все линии

Построение оптимального решения
Линией уровня называется
прямая, на которой функция
принимает постоянное значение.
Уравнение линии уровня имеет
вид с1x1 + с2 x2 = l , l = const .
Все линии уровня параллельны.
Их нормаль - вектор с = (с1; с2 ) .

35.

x2
7.5
B
Линия уровня
A
3
2
D
1
-2
1
2
x1
3
-2
-6
C

36.

x2
7.5
A
B
3
2
D
1
-2
1
2
x1
3
-2
-6
C

37.

Перемещаем прямую параллельно себе в
направлении вектора C = (2; 2) .
Линии уровня перемещают в задачи на
максимум в направлении нормали, а в
задачи на минимум – в
противоположном направлении.

38.

x2
7.5
В – точка выхода
A
B
3
2
D
1
-2
1
2
x1
3
-2
-6
C

39.

x2
(1)
7.5
В = (1) (3)
(3)
(2)
3x1 − 2 x2 = −6,
x1 = 3
В = (3; 7,5)
B
A
3
-2
1
x1
3
Оптимальный план
X*= (3; 7,5)
-6
C

40.

Определение экстремального
значения целевой функции
f ( x) = 2x1 + 2x2 → max
X* = (3; 7,5) - оптимальный
план
f max = 2 3 + 2 7.5 = 21
f max = 21, при X*= (3; 7,5).

41. Решить графически задачу ЛП

Задача 1
Решить графически задачу ЛП
x1 − x2 + 2 0,
3 x − 2 x − 6 0,
2
1
2 x1 + x2 − 2 0,
x 3,
2
x1 0, x2 0,
L = 3x1 + 2 x2 → max

42.

Задача 1

43. Решить графически задачу ЛП

Задача 2
Решить графически задачу ЛП
4 x1 − x2 0,
2 x + x 6,
1 2
x1 + 2 x2 16,
x 4,
1
x1 − x2 0,
L = 4 x1 + 2 x2 → min

44.

Задача 2

45. Решить графически задачу ЛП

Задача 3
Решить графически задачу ЛП
5 x1 − x2 0,
x + x 5,
1 2
2 x1 − 3 x2 0,
x2 3,
L = 3x1 + 7 x2 → max

46.

Задача 3

47. Решить графически задачу ЛП

Задача 4
Решить графически задачу ЛП
3 x1 − x2 0,
x 6,
2
2 x1 + x2 16,
− x + 2 x 2,
2
1
x1 − x2 3,
L = 4 x1 + 5 x2 → max

48.

Задача 4

49. В зависимости от характера ОДР и взаимного расположения области и вектора-нормали могут встречаться различные случаи

50. Максимум достигается в единственной точке

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

51. Максимум достигается в двух вершинах, и, следовательно, в любой точке отрезка АВ

Ограниченная область допустимых решений
Максимум достигается в двух
вершинах, и, следовательно, в любой
точке отрезка АВ

52. Целевая функция имеет экстремум

Неограниченная область допустимых решений
Целевая функция имеет экстремум

53. Функция неограниченна снизу и сверху

Неограниченная область допустимых решений
Функция неограниченна снизу и сверху

54.

Пример 5
− x1 + x2 + x3 + 2 x4 − 3 x5 = 4,
x + x + 4 x + x − 8 x = 3,
3
4
5
1 2
x
+
x
−
4
x
=
−
4
,
2
3
5
x j 0
L = − x1 − x2 + x3 + 3x4 + 7 x5 → min

55.

Графически могут решаться
• задачи, заданные в произвольной форме,
содержащие не более двух переменных,
• задачи, заданные в канонической форме, с
числом свободных переменных n − m 2 ,
• задачи, в произвольной форме записи,
которые после приведения к канонической
форме будут содержать не более двух
свободных переменных n − m 2.

56.

Решение

57.

Пример 5