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