Глава 1. Графический метод

Наиболее простым и наглядным методом решения ЗЛП является графический. Он применяется для решения ЗЛП с двумя переменными, заданными в неканонической форме, и многими переменными в канонической форме, при условии, что они содержат не более двух свободных переменных.

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

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

1) построить область допустимых решений системы ограничений задачи;

2) построить график линии нулевого уровня для целевой функции, то есть график прямой ;

3) построить вектор , который является вектором нормали для целевой функции ;

4) переместить линию уровня целевой функции по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум;

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

6) найти координаты точки экстремума и значение целевой функции в ней.

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

Пример 2.1. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расход которых на 1 кг мороженого и суточные запасы исходных продуктов даны в таблице.

Исходный продукт	Расход исходных продуктов на 1 кг мороженого	Запас, кг
Сливочное	Шоколадное
Молоко	0,8	0,5
Наполнители	0,4	0,8

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 руб., шоколадного ¾ 14 руб.

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

Решение. Обозначим: ¾ суточные объем выпуска сливочного мороженого, кг, ¾ суточные объем выпуска шоколадного мороженого, кг. Составим математическую модель задачи.

Целевая функция будет иметь вид при ограничениях

Первое неравенство этой системы ¾ это ограничение по молоку, второе ¾ ограничение по наполнителям, третье и четвертое ¾ рыночное ограничение по спросу, последние два ¾ стандартные естественные ограничения для любой задачи.

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

Неравенству соответствует область, лежащая ниже и левее уравнения прямой, а неравенству соответствует область, лежащая выше и правее уравнения прямой. Искомой будет область, которая находится на пересечении всех полученных участков. В нашем случае это область 0ABDEF.

Теперь строим график линии нулевого уровня для целевой функции, то есть график прямой и ее вектор нормали :

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

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

Итак, максимальный доход от реализации составит 9200 руб. в сутки при выпуске 312,5 кг сливочного и 300 кг шоколадного мороженого.