Задач линейного программирования

     Цель  работы: изучить теорию и методы решения задач линейного программирования; пробрести навыки построения моделей линейного программирования и решения задач линейного программирования на ЭВМ.

      

     Краткие теоретические сведения

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

     Пример 1. Фирма производит две модели (А и В) сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м² досок, а для изделия модели В - 4 м². Фирма может получить от своих поставщиков до 1 700 м² досок в неделю. Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели 5-30 мин. В неделю можно использовать 160 ч машинного времени.

     Сколько изделий каждой модели следует фирме  выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В-А дол. прибыли?

     Чтобы сформулировать эту задачу математически, обозначим через х_{ количество выпущенных за неделю полок модели Л, а через х₂ -количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения х\ и х₂. Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль. Еженедельная прибыль составляет

     Р = 2x₁, + 4x₂.

     Поскольку х₁ и х₂ выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т.е.

     х_{ > 0,     х₂>0                                             (1)

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

     Зх₁ + 4х₂ < 1700          (2)

     для машинного времени -

     2X₁ + 5 х₂ < 1600.           (3)

     Следовательно, задача состоит в том, чтобы найти  значения х₁ и х₂, удовлетворяющие условиям неотрицательности  (1) и ограничениям типа неравенства (2) - (3) и максимизирующие функцию Р.

     Это типичная двумерная задача линейного  программирования. Целевая функция, которая должна быть максимизирована, является линейной функцией своих переменных. Ограничения на эти переменные тоже линейны (1). 

             

Рис. 1 Линия  уровня целевой функции и допустимое множество задачи ЛП 

     Условия неотрицательности позволяют ограничиться рассмотрением положительного квадранта. Границы определяются прямыми

                   3x₁ + 4х₂ = 1700,

                   2х₁ + 5х₂ = 1 600.

     Стрелка на каждой границе указывает, с какой  стороны прямой * выполняется ограничение. Заштрихованная область ОАВС, содержащая точки, для которых соблюдены условия (2) и (3), является допустимой. Точки внутри и на границе этой области изображают допустимые решения. Допустимых решений много. Задача состоит в том, чтобы найти точку максимума функции Р.

     Штриховыми  линиями изображены прямые

       2x₁ + 4x₂ =0,

     2x₁ + 4x₂ = 800,

обозначенные  а и b соответственно. Эти прямые параллельны и представляют собой две линии уровня функции Р со значениями 0 и 800. Ясно, что значение функции Р возрастает по мере того, как линии уровня удаляются   от начала координат в положительном квадранте.

ми (2, 4), указывающий направление возрастания  функции Р перпендикулярен штриховым линиям и направлен в сторону, противоположную началу координат.

     Линией  уровня с наибольшим значением функции  Р имеющей хотя бы одну точку с допустимой областью, является прямая с, проходящая через вершину В; на ней Р принимает значение 1 400. Точка В, в которой х₁ = 300, х₂ = 200, соответствует оптимальному решению задачи. Эти значения могут быть получены как решения уравнений.

     2х₁ +4х₂ =1700,

     2х₁ +5х₂ =1 600.

Следовательно, максимальная прибыль составляет 2*300 + 4*200 = 1400.

     В точке максимума оба ограничения  превращаются в равенства, что означает полное использование сырья и  машинного времени.

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

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

Порядок выполнения работы

      Вариант № 2

-2х₁ + 3х₂ → max 

Графический метод: 

 

 

  

1) х₁ + 2х₂ 12     2) 3х₁ + 2х₂

х₁ > 0   x₂ > 0    х₁ > 0   x₂ > 0 

x₁ = 0   x₂ = 6             x₁ = 0   x₂ = 4 

x₁ = 12  x₂ = 0    x₁ = 8/3   x₂ = 0 

3) -2х₁ + х₂ -8

х₁ > 0   x₂ > 0  

x₁ = 0   x₂ =-8

x₁ = 4            x₂ = 0 
 

 
 
 
 
 
 
 
 
 
 
 

Таблица 1 – Начальное  базисное решение

 

Опорная точка: х₁ = 0, х₂ = 0, х₃ = 12, х₄ = 8, х₅ = -8, G = 0. 

Таблица 2 – Правило  минимальных отношений 

 
 

Таблица 3 – Сложное  базисное решение