Краткие теоретические сведения. тема: “Решение задачи линейного программирования”

Лабораторная работа №1

тема: “Решение задачи линейного программирования”

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

Краткие теоретические сведения

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

Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру и графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

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

Целевая функция Z (x) при фиксированном значении Z (x) = Z определяет на плоскости прямую линию. Изменяя значения Z, мы получим семейство параллельных прямых, называемых линиями уровня. Для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение Z.

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

Алгоритм решения задач ЛП графическим методом.

1). В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

2). Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0; 0)], и проверить истинность полученного неравенства. Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку, иначе надо заштриховать полуплоскость, не содержащую данную точку.

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

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

3). Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.

4). Если ОДР – не пустое множество, то нужно построить хотя бы одну из линий уровня. Способ построения аналогичен построению прямых ограничений.

5). Построить вектор , который начинается в точке (0; 0) и заканчивается в точке . Если линии уровня и вектор построены верно, то они будут перпендикулярны.

6). При поиске максимума целевой функции необходимо передвигать какую-либо из линий уровня в направлении вектора , при поиске минимума целевой функции – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума целевой функции. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности целевой функции сверху (при поиске максимума) или снизу (при поиске минимум).

7). Определить координаты точки max (min) целевой функции и вычислить значение целевой функции Z (x*). Для вычисления точных координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

Пример.

Найти max Z = 4.5 x₁ + 4 x₂ при следующих ограничениях:

x₂ ≤ 3

4 x₁ + 5 x₂ ≤ 20

6.5 x₁ + 4 x₂ ≤ 26

Решение.

В ограничениях задачи заменим знаки неравенств знаками точных равенств и построим прямые:

x₂ = 3

4 x₁ + 5 x₂ = 20

6.5 x₁ + 4 x₂ = 26

Заштрихуем полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Получим ОДР как пятиугольник ABCOD. ОДР – не пустое множество, поэтому построим целевую прямую. Построим вектор , который начинается в точке (0; 0) и заканчивается в точке (4.5; 4). Будем передвигать целевую прямую в направлении вектора , последняя по ходу движения вершина ОДР – т. А, это и есть точка максимума целевой функции. Определим точные координаты т. А:

x₁ = 3, x₂ = 1.6. т. А (3; 1.6)

Рис.1. Графическое решение задачи

Значение целевой функции в т. А:

max Z = 4.5 x₁ + 4 x₂ = 4.5*3 + 4*1.6 = 13.5 + 6.4 = 19.9