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

Графически могут решаться

задачи, заданные в произвольной форме, содержащие не более двух

Графически могут решаться

задачи, заданные в произвольной форме, содержащие не более двух

Графически могут решаться

задачи, заданные в произвольной форме, содержащие не более двух

Этапы графического решения задачи ЛП

Этап 1 – построение области допустимых решений.
Этап

Рассмотрим реализацию метода
на следующем примере:

Построение
области допустимых решений

Заменяя каждое ограничение равенствами, построим прямые .

Построение первой прямой

(1) 3 х1 – 2 х2 = –

Построение первой прямой

(1) 3 х1 – 2 х2 = –

1

3

x1

x2

-2

3

7.5

(1)

Построение второй прямой

(2) 3 х1 + х2 = 3

Построение второй прямой

(2) 3 х1 + х2 = 3

1

3

x1

x2

-2

3

7.5

-6

(1)

(2)

Построение третьей прямой

(3) х1= 3

1

3

x1

x2

-2

3

7.5

-6

(1)

(2)

(3)

(3) х1= 3

Построение первой полуплоскости

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

Построение первой полуплоскости

Выбираем точки А(-2; 3) и В(0;0), принадлежащие разным

1

3

x1

x2

-2

3

7.5

(1)

A(-2;3)

B(0;0)

-12 ≥ -6

0 ≥ -6

Построение второй полуплоскости

(2) 3 х1 + х2 ≥ 3

Выбираем точки А(3;

1

3

x1

x2

-2

3

7.5

(1)

B(0;0)

A(3; 3)

(2)

12 ≥ 3

0 ≥ 3

Построение третьей полуплоскости

(3) х1 ≤ 3

Выбираем точки А(4; 3) и

1

3

x1

x2

-2

3

7.5

(1)

B(0;0)

A(4; 3)

(2)

4 ≤ 3

0 ≤ 3

(3)

3

1

x1

x2

-2

3

7.5

(1)

(2)

(3)

1

3

x1

x2

-2

3

7.5

-6

(2)

(1)

(3)

D

A

B

C

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

Построение
области допустимых решений

Какие варианты ОДР возможны?

1

3

x1

x2

-2

3

7.5

-6

(2)

(1)

(3)

D

A

B

C

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

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

D

3

1

x1

x2

-2

3

7.5

(1)

(2)

(3)

Области допустимых решений – пустое множество.

3

1

x1

x2

-2

F

7.5

(1)

(2)

(3)

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

Построение оптимального решения

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

Построение оптимального решения

Линией уровня называется прямая, на которой функция принимает постоянное

Построение оптимального решения

Нормаль линий уровня указывает направление наискорейшего возрастания целевой функции,

Линии уровня перемещают в задачи на максимум в направлении нормали, а

Построение оптимального решения

Строим прямую и определяем направление возрастания функции , это

2

2

1

С = (2;2)

2

2

1

-2

Линия уровня

Перемещаем прямую параллельно себе в направлении вектора .

Линии уровня перемещают

2

2

1

-2

В – точка выхода

1

3

x1

x2

-2

3

7.5

-6

(2)

(1)

(3)

A

B

C

В = (1) ∩ (3)

В = (3; 7,5)

Оптимальный план X*= (3;

Определение экстремального
значения целевой функции

X* = (3; 7,5) - оптимальный план

Задача 1

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

Задача 2

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

Задача 3

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

Задача 4

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

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

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

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

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

Максимум достигается в двух вершинах, и, следовательно, в

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

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

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

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