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