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

Задача линейного программирования с двумя неизвестными может быть решена графически
Замечание:
К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2

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

1. Построить область допустимых решений (ОДР) в системе координат, заданную системой ограничений
Алгоритм графического решения ЗЛП

2. Построить градиент целевой функции
F = с1х1+с2х2
(вектор нормали к прямой с1х1+с2х2 = F)
Алгоритм графического решения ЗЛП

3. Построить опорную прямую, перпендикулярную вектору нормали – линию уровня целевой функции
Алгоритм графического решения ЗЛП

4. Перемещая опорную прямую в направлении вектора нормали, определить «точку входа» и «точку выхода» (первая встретившаяся опорной прямой точка из ОДР и последняя встретившаяся опорной прямой точка из ОДР соответственно)
В точке входа: F → min
В точке выхода: F → max
Алгоритм графического решения ЗЛП

5. Определить координаты оптимальной точки (точки входа или точки выхода) и найти значение целевой функции в ней
Алгоритм графического решения ЗЛП
Замечание:
Оптимальная точка является угловой точкой выпуклой области допустимых решений

Минимальное значение целевая функция достигает в точке В: Fmin = F(B)
Максимальное значение: Fmax = ∞
Частные случаи

Минимальное значение целевая функция достигает в точке E: Fmin = F(E)
Максимальное значение целевая функция достигает во всех точках отрезка ВС :
Fmin = F(B)= F(C)
Частные случаи

Решить графически ЗЛП

Решить графически ЗЛП
1. Построим область допустимых решений, заданную системой неравенств
(см. презентацию Геометрический смысл линейного неравенства)

Решить графически ЗЛП
2. Построим вектор нормали N(3;4) и перпендикулярную ему опорную прямую

Решить графически ЗЛП
3. Перемещаем опорную прямую в направлении вектора нормали и определяем «точку выхода»
Файл 04_model_01.ggb
В – точка выхода

Решить графически ЗЛП
4. Найдем координаты точки В, как точки пересечения прямых (1) и (3)

Решить графически ЗЛП
4. Найдем координаты точки В, как точки пересечения прямых (1) и (3):

Решить графически ЗЛП
5. Найдем значение целевой функции в точке В

Решить графически ЗЛП
Ответ: