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

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

Алгоритм графического метода рассмотрим применительно к задаче:

при

Шаг 1. Строим область допустимых решений - область Р, т.е. геометриче­ское место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каж­дое из неравенств (а)-(д) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми:

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

откуда или .

Подставляя значения и в функцию , найдем

.

4. Задача о раскрое материала.

Продукция ткацкой фабрики выпускается в виде рулонов ткани шириной 2,20 м. и 1,50 м. Длина ткани в рулоне соответственно 84 м. и 120 м. Из ткани шьют спальные комплекты: односпальные и двуспальные. Цена односпального комплекта 800 руб., а двуспального 1000 руб. Выяснить какое количество комплектов каждого вида нужно изготовить, что бы получить максимальную прибыль от продажи?

Доход ткани

Ширина (м)	Односпальный комплект (м)	Двуспальный комплект (м)	Количество ткани в рулоне (м)
1,50	8,3	12,4	120
2,20	7	8	84

Постановка задачи

1. Построение математической модели начинаем с идентификации переменных (искомых величин). После этого целевая функция и ограничения выражаются через соответствующие переменные.

Переменные По условию имеем переменные т. к. нужно выяснить количество комплектов первого и второго видов, переменными являются: X₁ – количество односпальных комплектов, X₂ - количество двуспальных комплектов.

Целевая функция Т. к. цена односпального комплекта 800 руб., то прибыль от реализации 800 руб. Цена двуспального комплекта 1000 руб., доход от продажи 1000 руб.

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

, .

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

Расход исходного продукта для производства обоих видов изделия

Максимально возможный запас данного исходного продукта

Решим задачу графическим методом

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

Шаг 2. Строим вектор – градиент , указывающий направление возрастание функции.

Шаг 3. Строим прямую линию уровня функции перпендикулярную вектору – градиенту .

Шаг 4 . Передвигая линию уровня в направлении вектора, убеждаемся в неограниченном возрастании функции.

Оптимальное решение: