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

Пример.

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

Решение. Найдем вначале область допустимых решений (ОДР). Решим графически первое неравенство:

(1)

Для этого построим вначале прямую линию, соответствующую уравнению:

. (11)

Поскольку, если то то прямая (11) проходит через точку М1(0;8). Аналогично, если то и прямая (11) проходит также через точку М2 (8;0). Проведем через эти две точки прямую линию и отметим ее с помощью 1 (см. рис. 1). Эта линия делит плоскость на две полуплоскости, которые мы условно назовем верхней и нижней полуплоскостями. Так как координаты точки (0;0) удовлетворяют неравенству (1), то этому неравенству соответствует нижняя полуплоскость, которая содержит эту точку. Этот факт мы изобразим на рис. 1 штрихами, направленными вниз от линии 1 .

Теперь решим графически второе неравенство:

(2)

Ему соответствует прямая, заданная уравнением:

(21)

Ее мы построим несколько иначе. Перепишем уравнение (21) в виде:

Тогда при оказывается , что дает точку М3 (0;3) искомой прямой. Угловой коэффициент этой прямой Но угловой коэффициент любой прямой равен где - угол наклона прямой к оси 0х: . Если теперь мы отложим три единицы вправо от точки М3 (0;3) и затем две единицы вверх, то получим другую точку М4 (3;5) которая также лежит на прямой (21). Через точки М3 и М4 мы проводим прямую 2 (рис.1). Начало координат (0;0) удовлетворяет (2) и лежит ниже графика линии 2 , поэтому соответствующая полуплоскость является «нижней», что мы и отмечаем штрихами, направленными вниз от прямой 2 (рис.1). Аналогично строим прямую 3.

Уравнение

(31)

Заменяем на уравнение .

Ясно, что прямая проходит через т. М5 (5;0), и имеет угловой коэффициент к = 2. При этом самому неравенству

Соответствует верхняя полуплоскость, отмеченная штрихами вверх от прямой 3.

Тривиальному неравенству соответствует правая полуплоскость координатной плоскости, то есть полуплоскость, лежащая справа от вертикальной оси Ее отмечаем штрихами, направленными вправо от оси 0 Наконец неравенству соответствует верхняя полуплоскость координатной плоскости, отмеченная штрихами, направленными вверх от оси 0. Пересечение всех указанных полуплоскостей определяет ОДР данной задачи. На рисунке 1 это область, ограниченная выпуклым пятиугольником ОАВСD.

Изобразим на рисунке 1 вектор роста целевой функции . Это вектор началом в т. (0;0) и концом в точке М (4;3), поскольку .

Построим теперь линию уровня . Она определяется уравнением:

(4)

Мы взяли здесь константу С =11, для того чтобы точки пересечения прямой (4) с осями имели целые координаты. Действительно, если то и, если То Что дает две точки М1 (0;4) и М2 (3;0) линии уровня (4). Через них проводим пунктиром соответствующую линию уровня (рис. 1). Она оказывается перпендикулярна вектору роста . Отрезок пересекается с ОДР и в каждой его точке х значение целевой функции равно 11:

.

Мы знаем, что значение функции F увеличивается в направлении вектора роста . Чтобы найти максимальное значение на ОДР будем параллельно перемещать линию уровня в направлении вектора роста До тех пор, пока, она будет иметь хотя бы одну точку пересечения с ОДР задачи. Из рисунка 1 ясно, что последнее пересечение смещенной линии уровня (4) будет точка

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

На этой линии очевидно и будет достигаться максимальное значение целевой функции F в ОДР, поскольку при дальнейшем движении линии уровня в направлении вектора роста, она перестает пересекаться с ОДР. Итак, максимальное значение функция F(х) имеет в точке . Так как точка является пересечением прямых 1 и 3, то ее координаты находятся из системы:

(5)

Чтобы решить эту систему, сложим оба уравнения. Тогда получим, что или .

Из первого уравнения находим, что

Итак, координаты точки С найдены : С (6;2). Найдем максимальное значение функции:

.

Задача решена.

Ответ: максимальное значение целевой функции F достигается в точке С (6;2) и равно 29:

.

© 2011-2024 Контрольные работы по математике и другим предметам!