 | Сервис для решения задач по линейному программированиюи другие интересные типовые задачи |
English |
Пример №1. Решение задачи линейного программирования графическим методом.
Функция достигает наибольшего значения в точке
F = x1 - x2
при следующих ограничениях:
 | x1 | + | x2 | ≤ | 7 | |
| x2 | ≤ | 5 | ||||
| x1 | + | x2 | ≥ | 3 | ||
| x2 | ≥ | 2 | ||||
| x1 | ≤ | 4 |
x1 ≥ 0 x2 ≥ 0
Точки, координаты которых удовлетворяют одновременно всем неравенствам системы ограничений, называются областью допустимых решений.
Очевидно, для нахождения области допустимых решений данной задачи, необходимо последовательно рассмотреть каждое неравенство. (см. шаг 1 - шаг 5)
Последние два шага служат непосредственно для получения ответа. (см. шаг 6 - шаг 7)
Это стандартная схема решения. Если область допустимых решений представляет собой точку или пустое множество, то решение будет короче.
Посмотреть план решение этой задачи в картинках
По условию задачи: x1 ≥ 0 x2 ≥ 0.
Если бы это было единственным условием, то область допустимых решений имела бы вид, как на рисунке (вся первая четверть).
Рассмотрим неравенство 1 системы ограничений.
x1 + x2 ≤ 7
Построим прямую: x1 + x2 = 7
Пусть x1 =0 => x2 = 7
Пусть x2 =0 => x1 = 7
Найдены коородинаты двух точек (0, 7) и (7 ,0). Соединяем их и получаем необходимую прямую (1).
Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.
x1 + x2 ≤ 7
Преобразуем неравенство, оставив в левой части только x2
x2 ≤ - x1 + 7
Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (1).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 2 системы ограничений.
x2 ≤ 5
Построим прямую: x2 = 5
Данная прямая параллельна оси OX1 и проходит через точку (0,5) (2)
Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (2).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 3 системы ограничений.
x1 + x2 ≥ 3
Построим прямую: x1 + x2 = 3
Пусть x1 =0 => x2 = 3
Пусть x2 =0 => x1 = 3
Найдены коородинаты двух точек (0, 3) и (3 ,0). Соединяем их и получаем необходимую прямую (3).
Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.
x1 + x2 ≥ 3
Преобразуем неравенство, оставив в левой части только x2
x2 ≥ - x1 + 3
Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 4 системы ограничений.
x2 ≥ 2
Построим прямую: x2 = 2
Данная прямая параллельна оси OX1 и проходит через точку (0,2) (4)
Знак неравенства ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (4).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Рассмотрим неравенство 5 системы ограничений.
x1 ≤ 4
Построим прямую: x1 = 4
Данная прямая параллельна оси OX2 и проходит через точку (4,0) (5)
Знак неравенства ≤ . Следовательно, нас интересуют точки расположенные левее построенной прямой (5).
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
Строим вектор C = (1, -1), координатами которого являются коэффициенты функции F.
Вектор C нарисован не в масштабе, так как он не помещается на рисунке.
Будем перемещать "красную" прямую, перпендикулярно вектору C, от левого верхнего угла к правому нижнему.
"Красная" прямая называется линией уровня. В каждой точке линии уровня значение функции F есть величина постоянная.В точке, в которой "красная" прямая в первый раз пересечет область допустимых решений, функция F достигает своего наименьшего значения.
В точке, в которой "красная" прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения.
Функция F достигает наибольшего значения в точке A. (см. рисунок)
Найдем координаты точки A.
Точка A одновременно принадлежит прямым (4) и (5).
| x2 | = | 2 | => | x1 = 4 | |||
| x1 | = | 4 | x2 = 2 |
Вычислим значение функции F в точке A (4,2).
F (A) = 1 * 4 - 1 * 2 = 2
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
x1 = 4
x2 = 2
F max = 2
Замечание: если возникли сомнения, что функция F достигает своего максимума в точке А , необходимо найти значение функции в интересующей точке и сравнить с F(A).