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

Пример

Цех изготавливает изделия А и Б. Расход сырья, его запас и прибыль от реализации изделия указаны в таблице.

Вид сырья	Расход на изделие		Запас
	А	Б
	48	12	600
	24	21	840
	15	27	1350
Прибыль	12	18

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

Решение

Построение экономико-математическая модели задачи линейного программирования

Через и обозначим количество выпускаемой продукции вида и соответственно.

Тогда ограничения на ресурсы будут выглядеть следующим образом:

- ресурс

- ресурс

- ресурс

Кроме того, по смыслу задачи ,

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

Получаем следующую экономико-математическую модель:

,

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

Построение области допустимых решений

Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям -неравенствам граничные прямые:

Найдем точки, через которые проходят прямые:

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

Областью допустимых решений является область .

Строим вектор координаты которого являются коэффициентами целевой функции.

Перпендикулярно к построенному вектору проводим линию уровня .

Нахождение оптимального плана задачи линейного программирования

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

Решением на максимум является точка , координаты которой находим как точку пересечения прямой (2) и оси .

Ответ: Таким образом, необходимо выпускать 40 ед. изделия Б. Изделие A выпускать невыгодно. При этом прибыль будет максимальной и составит 720 д.е.