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