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

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


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

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

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

Смежные темы решебника:

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


Пример 1

Скачать пример 1 в формате pdf

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

Требуется:

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

Решение

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

Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98

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

Подробное решение получите точно в срок или раньше.

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Пример 2

Скачать пример 2 в формате pdf

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

Решение

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

Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98

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

Подробное решение получите точно в срок или раньше.

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

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

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

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

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


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

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

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

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

Ответ: .