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