Графический метод решения задач линейного программирования с двумя переменными

Графический метод решения задач линейного программирования

Рассмотрим стандартную задачу линейного программирования с двумя переменными:

, .

Допустимым решением задачи линейного программирования называется - мерный вектор , удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений образуют область допустимых решений задачи линейного программирования.

Оптимальным решением задачи линейного программирования называется допустимое решение, при котором целевая функция задачи принимает экстремальное значение ( или )

Для графического метода решения задач линейного программирования используются линии уровня целевой функции.

Линиями уровня функции называются прямые вида , которые параллельны между собой и перпендикулярны общему вектору нормали .

Алгоритм решения задачи линейного программирования с двумя переменными графическим методом:

1. По системе ограничений строится область допустимых значений. Если область допустимых решений пустое множество, то задача решения не имеет.

2. Строится вектор с точкой приложения в начале координат. Это вектор указывает направление возрастания целевой функции.

3. Перпендикулярно вектору проводится одна из линий уровня, например линия уровня функции , имеющая общие точки с областью допустимых решений.

4. Линия уровня перемещается по направлению вектора для задач на максимум и в противоположном направлении относительно вектора для задач на минимум до крайнего положения на области допустимых значений.

5. После нахождения оптимальных решений вычисляется значение целевой функции на этом решении.

В зависимости от вида области допустимых решений и линейной функции задача может иметь единственное решение, бесконечное множество решений или не иметь ни одного оптимального решения.

а) мин. знач. в точке А б) минимальное значение принимает на в) не ограничена в

макс. знач. в точке С опорной прямой, совпадающей с сторону увеличения

одной из сторон многоугольника значения мин. функции

Пример 5. Решить задачу линейного программирования графическим методом.

, .

Решение. Строим область допустимых решений.

1) Рассмотрим первое неравенство системы ограничений. Заменим знак неравенства знаком равенства и выразим из полученного уравнения одну из переменных, например : , . Для построения прямой достаточно двух точек: . Отмечаем эти две точки, проводим прямую и нумеруем ее цифрой один. Эта прямая разбивает всю плоскость на две части. Возьмем любую точку, не лежащую на этой прямой, и подставим ее координаты в первое неравенство. Например, возьмем точку (0;0). При подстановке координат этой точки в первое неравенство системы ограничений неравенство выполняется. Таким образом, стрелки на концах прямой направляются в сторону полуплоскости, содержащей выбранную точку.

Аналогично все остальные неравенства заменяем на равенства, строим соответствующие прямые и определяем полуплоскость решений.

2) , , .

3) , .

4) , - прямая параллельная оси абсцисс.

5) Находим общую часть полуплоскостей решений, учитывая условия неотрицательности.

6) Строим вектор нормали (координаты - коэффициенты целевой функции).

7) Через начало координат проводим линию уровня и, так как задача на отыскание максимума, двигаем ее по направлению вектора нормали до окончания области допустимых решений.

8) Крайней точкой области допустимых решений является точка пересечения прямых (2) и (4). Находим координаты этой точки, приравнивая уравнения прямых: .

9) Находим оптимальное значение целевой функции .

Пример 5. Решить задачу линейного программирования графическим методом.

, .

Решение. Строим область допустимых решений.

1) 4 , .

2) , .

3) , , .

4) - прямая параллельная оси ординат.

5) , .

6) Находим общую часть полуплоскостей решений, учитывая условия неотрицательности.

7) Строим вектор нормали (координаты - коэффициенты целевой функции).

8) Так как задача на отыскание минимума, то линию уровня двигаем против направления вектора нормали до окончания области допустимых решений.

9) Крайним положением линии уровня является прямая (2). Она проходит через точки (пересечение прямых (1) и (2)) и (пересечение прямых (5) и (2)). В таком случае задача имеет бесконечное множество решений, расположенных на отрезке .

10) Решаем системы и и находим точки и .

10) Находим оптимальное значение целевой функции .

Задания для решения в аудитории

1. Решить задачу линейного программирования графическим методом.

, .

2. Решить задачу линейного программирования графическим методом.

, .

Дата добавления: 2015-06-27