Графический метод решения ЗЛП

Краткая теория

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

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

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

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

Пример решения задачи

Задача

Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить кг сырья первого типа, кг сырья второго типа, кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить кг первого типа, сырья второго типа, сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве кг, кг, кг соответственно. Рыночная цена единицы Изделия 1 составляет тыс руб., а единицы Изделия 2 - тыс. руб.

Требуется:

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

Решение

На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение). Для этого вам нужно только связаться со мной:

Телеграм (+7 968 849-45-98)
ВКонтакте
WhatsApp (+7 968 849-45-98)

Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту. Опыт работы более 25 лет.

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Построение модели

Через и обозначим количество выпускаемых изделий 1-го и 2-го типа.

Тогда ограничения на ресурсы:

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

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

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

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

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

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

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

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

Для определения полуплоскости возьмём любую точку, например , не принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:

Области решений соответствующего 1-го неравенства соответствует левая полуплоскость

Возьмём любую точку, например , не принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:

Области решений соответствующего 2-го неравенства соответствует левая полуплоскость

Возьмём любую точку, например , не принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:

Области решений соответствующего 2-го неравенства соответствует левая полуплоскость

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

Нахождение решения задачи ЛП

Строим вектор , координаты которого пропорциональны коэффициентам целевой функции. Здесь - коэффициент пропорциональности.

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

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

Ответ: Таким образом необходимо выпускать 56 изделий 1-го вида и 64 изделия 2-го вида. При этом выручка от реализации изделий будет максимальна и составит 5104 ден.ед.