Тема 3 – Методы и модели линейного программирования

Цель: изучение методов линейного программирования при решении задач оптимизации.

 

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

Решение оптимизационной задачи начинается с построения математической модели, при этом предварительно необходимо определить:

- цель и механизмы функционирования исследуемой системы;

- значения каких характеристик исследуемой системы можно варьировать (управляемые переменные);

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

 

Задача линейного программирования в общем виде имеет следующий вид:

F(x) = c₁x₁ + c₂x₂ +... + c_nx_n à opt - целевая функция;

∑a_ijx_j <= b_i, i=1,...m; - функциональные ограничения;

x_j => 0 - прямые ограничения.

 

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

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

Пример

 

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

 

Предприятие выпускает ткань двух видов. Для их производства используется сырье трех видов: хлопок, лен и вискоза. На производство 10 п.м. ткани первого вида требуется 1 катушка хлопка, 2 катушки льна и 1 катушка вискозы. Для производства 10 п.м. ткани второго вида необходимо 1 катушка хлопка, 1 катушка льна и 2 катушки вискозы. На складе предприятия имеется 5 катушек вискозы, 9 катушек льна и 7 катушек хлопка. Известна удельная прибыль от реализации 10 п.м. ткани каждого вида, у.е. (С₁, С₂).

Определить оптимальный план выпуска и провести анализ чувствительности модели.

 

Таблица 11 – Исходные данные

Показатель	Ткань 1	Ткань 2	Запасы
S1 (хлопок), катушки
S2 (лен), катушки
S3 (вискоза), катушки
С (удельная прибыль от реализации), катушки

 

1. В качестве показателя эффективности целесообразно взять прибыль от реализации всех видов произведенной продукции.

 

2. В качестве управляемых переменных задачи следует взять

x₁ – объем производства ткани первого вида;

x₂ – объем производства ткани второго вида.

 

3. Целевая функция

3х₁+4х₂→max,

где 3 – удельная прибыль от реализации 10 п.м. ткани первого вида, у.е.;

4 – удельная прибыль от реализации 10 п.м. ткани второго вида, у.е.;

 

4. Ограничения:

4.1. По использованию хлопка: 1x₁ + 1x₂ £ 5.

4.2. По использованию льна: 2x₁ + 1x₂ £ 9.

4.3. По использованию вискозы: 1x₁ + 2x₂ £ 7.

4.4. Прямые ограничения: x₁ ³ 0, x₂ ³ 0.

Итак, задача в общем виде выглядит следующим образом:

х₁ + х₂ ≤ 5,

2х₁ + х₂ ≤ 9,

х₁ + 2х₂ ≤ 7,

х_1, х₂ ≥ 0.

 

3х₁ + 4х₂→max.

 

Далее следует нанести на график прямые, соответствующие следующим уравнениям:

1) х₁+х₂ = 5,

2) 2х₁+х₂ = 9,

3) х₁+2х₂ = 7,

4) х₁ = 0_,

5) х₂ = 0.

 

Для этого находим точки пересечения с осями:

1) (0; 5); (5; 0);

2) (0; 9); (4,5; 0);

3) (0; 3,5); (7; 0).

 

Затем необходимо заштриховать область, в точках которой выполняются все ограничения одновременно. Каждая точка данной области представляет собой допустимое решение, а множество всех таких точек образует область допустимых решений 0ABCD (рис. 16).

 

 

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

Для того, чтобы решить поставленную задачу, необходимо выбрать одно из решений (точек) в области допустимых решений, которое максимизирует целевую функцию (функцию прибыли), т.е. такие х_1, х₂ при которых 3х₁+4х₂ = мах.

Максимизируем прибыль путем параллельного переноса базовой целевой функции вправо вверх до тех пор, пока не останется хотя бы одной общей точки у целевой функции и области 0АВСD.

Определим базовую целевую функцию произвольно.

Пусть 3х₁+4х₂=12, тогда точки пересечения с осями – (0, 3); (4, 0).

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

 

 

Рис. 17 Максимизация целевой функции

 

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

 

х₁ + х₂ = 5,

х₁ + 2х₂ = 7,

х₁ = 3, х₂ = 2.

 

Итак, оптимальный план выпуска продукции включает в себя выпуск 30 п.м. ткани первого вида и 20 п.м. ткани второго вида. При этом плановая прибыль от реализации составляет Р = 3х₁+4х₂ = 17 у.е.

 

 

Анализ чувствительности

Решение задачи нельзя считать законченным без анализа чувствительности модели. Необходимость такого анализа объясняется тем, что некоторые параметры задачи линейного программирования (финансы, запасы сырья) на практике можно регулировать, что, в свою очередь, может изменить найденное оптимальное решение. Анализ чувствительности позволяет оценить влияние этих параметров на оптимальное решение. Если обнаруживается, что оптимальное решение можно значительно улучшить за счет небольших изменений заданных параметров, то целесообразно реализовать эти изменения.

 

1. Насколько можно увеличить запас некоторого вида сырья для улучшения полученного оптимального значения целевой функции?

 

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

 

 

Рис. 18 Анализ чувствительности модели

 

Рассмотрим ограничение по сырью S_1.

При увеличении запаса данного сырья прямая S₁ будет перемещаться параллельно вверх, стягивая ΔСВК. В (.) К активными становятся ограничения S₂ и S₃ и дальнейшее увеличение запаса S₁ будет нецелесообразным. При этом оптимальное решение переместится в (.) К, координаты которой определяются из решения системы соответствующих уравнений по принципу, указанному выше.

(.) К (11/3; 5/3).

Предельный уровень запаса сырья S₁ составляет х₁+х₂ = 11/3 + 5/3 = 16/3.

Фактический запас сырья S₁ = 5, т.е. прирост запаса будет равен

ΔS₁= 16/3 – 5 = 1/3.

При этом прибыль от увеличения запаса сырья составит

Р(ΔS₁) = 3х₁ + 4х₂ = 3*11/3+4*5/3 = 53/3.

А прирост прибыли будет равен

ΔР(ΔS₁) = 53/3 – 17 = 2/3.

 

Рассмотрим ограничение по сырью S_3.

При увеличении запаса данного сырья прямая S₃ будет перемещаться параллельно вверх. В (.) М оно перестает быть активными и далее увеличивать запас данного сырья не имеет смысла. При этом оптимальное решение переместится в (.) М.

(.) М (0; 5).

Предельный уровень запаса сырья S₃ составляет х₁+2х₂ = 0 + 2*5 = 10.

Фактический запас сырья S₃ = 7, т.е. увеличение запаса будет равно

ΔS₃= 10 – 7 = 3.

При этом прибыль от увеличения запаса сырья составит

Р(ΔS₃) = 3х₁ + 4х₂ = 3*0+4*5 = 20.

А прирост прибыли будет равен

ΔР(ΔS₃) = 20 – 17 = 3.

 

2. На сколько можно понизить запас некоторого вида сырья при сохранении полученного оптимального значения целевой функции?

 

Понижать запас стоит только в том случае, когда речь идет о неактивном ограничении. В данном случае таким ограничением является S_2. При снижении запаса соответствующая прямая будет перемещаться вниз до тех пор, пока не пересечет (.) В (в этот момент ограничение S₂ становится активным и дальнейшее его снижение без изменения оптимального решения невозможно).

Предельный уровень запаса сырья S₂ составляет 2х₁+ х₂ = 2*3 + 2 = 8.

Фактический запас сырья S₃ = 9, т.е. снижение запаса возможно в размере

ΔS₃= 9 – 8 = 1.

 

3. Увеличение какого вида сырья будет наиболее выгодно?

 

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

 

R = ΔР(ΔS_i) / ΔS_i. (22)

 

Чем больше данный коэффициент, тем большую прибыль можно получить от увеличения запаса.

R₁ = ΔР(ΔS₁) / ΔS₁ = (2/3) / (1/3) = 2

R₂ = ΔР(ΔS₂) / ΔS₂ = Ø

R₃ = ΔР(ΔS₃) / ΔS₃ = 3 / 3 = 1

Таким образом, увеличение сырья S₁ является более выгодным.