Линейные модели оптимизации

Тема 10. Линейные модели оптимизации в управлении экономикой

Общая постановка задачи линейного программирования (ЗЛП)

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

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

Найти вектор =(Х₁, Х₂, ..., Х_n)  максимизирующий линейную форму

      j=1, ..., n         (7.1)

и удовлетворяющий условиям: 

                                                                       (7.2)

Рекомендуемые материалы

                                                          (7.3)

Линейная функция называется целевой функцией задачи,   условия (7.2) - функциональными, а условия (7.3) – прямыми ограничениями задачи.

 Вектор =(Х₁, Х₂, ..., Х_n), компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, будем называть планом, или допустимым решением ЗЛП.

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

 где – оптимальное решение ЗЛП.

Будем считать, что ЗЛП записано в канонической форме, если ее целевая функция максимизируется, ограничения имеют вид равенств с правой неотрицательной частью и все переменные неотрицательны.

Задачи оптимизации производственной

программы предприятия

В качестве критериев оптимальности будем использовать: прибыль, себестоимость, затраты станочного времени, номенклатуру произведенной продукции.

Неизвестным в задаче являются объемы выпуска продукции каждого вида. Введем следующие обозначения:

Х_{j, s}    –  объем производства j-го продукта по s-му технологическому способу (j = 1,…, n); (s = 1,…, Qj);

n        –  количество видов выпускаемой продукции;

Q_j       –  число технологических способов, используемых при производстве j-го продукта;

b_i       –  наличие i-го ресурса (i = 1,…, m);

m       – количество типов используемых ресурсов;

a _{i, j, s}   –  норма затрат i-го ресурса на производство единицы j-го продукта по

s-му технологическому способу;

p _{j, s}    –  прибыль от производства j-го продукта по s-му технологическому способу;

T_j       –  задание (госзаказ) по выпуску j-ого вида продукции;

C _{i, j}    –  себестоимость производства j-го продукта по s-му технологическому способу;

Pi,j          --  заданный уровень прибыли.

Задача на максимум прибыли

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

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

При составлении плана производства приходится учитывать не только ограниченность ресурсов, но и директивные задания (госзаказы) по выпуску продукции. При этом модель дополняется ограничением вида X_j>T_j, а свобода выбора значительно снижается.

Задача на минимум себестоимости производства

Экономико-математическая модель задачи имеет вид:

При построении модели на минимум затрат наличие ограничений типа «больше» или «равно» обязательно. Отсутствие ограничений снизу ведет к оптимальному плану с нулевыми значениями переменных, которые дадут наименьшее значение критерия оптимальности. Такое решение абсурдно с экономической точки зрения.

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

Следует подчеркнуть, что при различной величине результатов вариант с меньшими затратами может быть и не лучшим: просто с наименьшими затратами мы  достигаем и меньшего результата.

Задача на максимум выпуска продукции в заданном

ассортиментном соотношении (на максимум комплексов)

Введем новые обозначения:

          K_j – количество изделий вида j, которые входят в некоторый комплект (например, комплект запасных частей для автомобиля).

Функция максимума комплектной продукции будет следующая:

,

то есть общее количество комплектов К определяется количеством изделий, из которых можно сформировать меньше всего «порций», объемом K_j . Эти изделия определяют, как бы «узкое место» в формировании комплектов, к максимальной «расшивке» которого следует стремиться.

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

Задача на минимум затрат станочного времени

 при заданной производственной программе

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

В результате система ограничений примет следующий вид:

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

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

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

      Прямая задача                          Двойственная задача

  (7.1) (7.4)

                         (7.2)          (7.5)

                            (7.3)                          (7.6)

Согласно теории линейного программирования каждой ЗЛП вида (7.1) - (7.3) соответствует двойственная ей ЗЛП (7.4) - (7.6). Основные утверждения о взаимно двойственных задачах содержится в двух следующих теоремах:

Первая теорема двойственности

Для взаимодвойственных задач  вида (7.1-7.3) и (7.4-7.6) возможен один из взаимоисключающих случаев:

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

2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пусто допустимое множество.

3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4. Обе рассматриваемые задачи имеют пустые допустимые множества.

Вторая теорема двойственности.
(теорема о дополняющей не жесткости)

Пусть вектор =(х₁, х₂, ..., х_n) допустимое решение прямой задачи (7.1-7.3), а Y=(y₁, y₂, ..., y_m) – допустимое решение двойственной задачи (7.4-7.6). Для того, чтобы они были оптимальными решениями, необходимо и достаточно, чтобы выполнялись следующие соотношения:

                  (7.7)

              (7.8)

Условия (7.7) и (7.8) позволяют, если известно решение одной из взаимно двойственных задач найти оптимальное решение для другой задачи.

Теорема об оценках

Значения переменных Y_i в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов b_i системы ограничений - неравенств прямой задачи на величину ∆f(x):

∆ f (x) = ∆ b_i ^.Y_i                                              (7.9)

Решая ЗЛП (7.1-7.3), симплексным методом, мы одновременно решаем и двойственную задачу ЗЛП (7.4-7.6). Переменные двойственной задачи Y_i называется объектно-обусловленными оценками.

Экономическая интерпретация двойственной задачи

    

  Рассмотрим экономическую интерпретацию двойственной задачи на следующих примерах.

Пример №1. Задача оптимального использования  ресурсов

Для составления плана выпуска четырех видов продукции Р1-Р4 на предприятии используют три вида сырья S1-S3. Объемы выделенного сырья, нормы расхода сырья и прибыль, полученная в результате выпуска каждого вида продукции, приведем в следующей таблице 7.1.

Составим экономико-математическую модель задачи оптимального использования на максимум прибыли. В качестве неизвестных примем Xj - объем выпуска продукции j-го вида, где j=1,...,4.

                                                                                           Таблица 7.1.

Модель задачи:

функциональные условия

   

x_j ≥ 0,             j=1,…,4   -     прямые ограничения.

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

1. покупающая организация старается минимизировать общую стоимость ресурсов;

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

     Согласно первому условию общая стоимость сырья выражается величиной:

g(Y) = 35Y₁ + 30Y₂ + 40Y₃ → min

Согласно второму требованию вводятся ограничения: на единицу первого вида продукции Р1 расходуются четыре единицы первого ресурса S1 ценой Y1, одна единица второго ресурса ценой Y2 и три единицы третьего ресурса ценой Y3. Стоимость всех ресурсов, расходуемых на производство единицы первого вида продукции, равна 4Y₁ + Y₂ + 3Y₃ и должна составлять не менее 14, то есть 4Y₁ + Y₂ + 3Y₃ ≥ 14.

В результате аналогичных рассуждений относительно производства остальных (2,3) видов продукции система неравенств примет следующий вид:

4Y₁ + Y₂ + 3Y₃ ≥ 14

2Y₁ + Y₂ + Y₃ ≥ 10

2Y₁ + 2Y₂ + 2Y₃ ≥ 14

3Y₁ + 3Y₂ + Y₃ ≥ 11

Цены ресурсов, естественно, должны быть неотрицательные: Y1≥0;Y2≥0;Y3≥0.

Получили симметричную пару взаимно двойственных задач. Для производственной программы (х₁,х₂,…,х_n) и при любом векторе оценок =(Y₁,Y₂,…,Y_m) выполняется неравенство, то есть ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Значит, величина  характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов.

Из первой теоремы двойственности следует, что при оптимальных производственной программе и векторе оценок ресурсов, производственные потери равны нулю.

Согласно второй теоремы, предъявляются следующие требования:

                

   (7.10)                          

                                     

   (7.11)        

                                           

Условия (7.10) можно интерпретировать так: если оценка Yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью. Если же ресурс используется не полностью, то его оценка равна нулю. Из условия (7.11) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет выпуска.

Пример №2. Планирование выпуска продукции пошивочным предприятием

Намечается выпуск двух  видов костюмов – мужских и женских.

 На женский костюм потребуется 1 метр шерсти, 2 метра лавсана и 1 человеко-день трудозатрат.

 На мужской костюм – 3,5 метра шерсти, 0,5 метра лавсана и 1 человеко-день трудозатрат.

Всего имеется 300 метров шерсти, 240 метров лавсана и 150 человеко-дней трудозатрат.

Требуется определить оптимальное число костюмов каждого вида, обеспечивающее максимальную прибыль предприятию, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского 20 денежных единиц. При этом следует иметь ввиду, что необходимо сшить не менее 60 мужских костюмов и обеспечить прибыль не менее 1400 денежных единиц.

Модель задачи:

Введем обозначения:

Х₁ и Х₂ – число соответственно женских и мужских костюмов. Прибыль от реализации женских костюмов составляет 10Х₁, а от реализации мужских костюмов 20Х₂, то есть необходимо максимизировать целевую функцию f(x)=10Х₁+20Х₂šmax.

Ограничения задачи имеют вид:

Х₁ +3.5Х₂ ≤350

2Х₁ +0.5Х₂ ≤240

Х₁ +Х₂ ≤ 150

10Х₁ +20Х₂ ≥1400

Х₂ ≥ 60,    Х₁,Х₂ ≥0

1. Необходимо привести все неравенства системы ограничений исходной задачи к одному виду: если в исходной задаче требуется найти максимум линейной формы, то все неравенства системы ограничений необходимо привести к виду «≤».

Поэтому неравенства, в которых данное требование не выполняется, следует умножить на  (-1), в результате получим:

         Х ₂  ≥60                                  - Х ₂ ≤60

     10Х₁+20Х₂  ≥1400                  -10Х₁-20Х ₂ ≤-1400

2. Выписываем матрицу А коэффициентов при переменных исходной задачи и транспонируем ее:

                        

                  

3. Составить систему ограничений двойственной задачи, для чего коэффициенты при переменных взять компоненты транспортированной матрицы Ат:

                   Y₁ +2 Y₂ + Y₃ - 10Y₅ ≥10

                   3.5Y₁+0.5 Y₂ + Y₃ – Y₄ -20Y₅ ≥ 20

                   Y_{1, 2, 3, 4, 5} ≥0.

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

      g(Y) =350Y₁+240Y₂ + 150Y₃ – 60Y₄ +1400Y₅.

Y₁   –  двойственная оценка ресурса «шерсть», которая может быть «ценой» шерсти;

Y₂   –  двойственная оценка ресурса «лавсан», которая может быть «ценой» лавсана;

Y₃ – двойственная оценка ресурса «трудозатраты», которая может быть «ценой» трудозатрат;

Y₄   –  двойственная оценка заказа  по выпуску женских и мужских костюмов;

Y₅   –  двойственная оценка задания по прибыли.

В результате решения симплексным методом получим:

               Х= (70, 80, 0, 60, 0, 40, 900)

               У= (4,0, 6, 0, 0, 0, 0)

               f(x) = g(y )=2300.

Таким образом, максимальная прибыль составила 2300 денежных единиц, при производстве 70 женских и 80 мужских костюмов.

Дополнительные переменные х₅=0, х₆=40, х₇=900 показывают, что шерсть и трудовые ресурсы использованы полностью (х₃ и х₅ =0), лавсана осталось 60 м =х₄, плановые задания перевыполнены по числу костюмов х₆=40 и по прибыли х₇=900. Решение двойственной задачи указывает на дефицитность ресурсов «шерсть» (У₁=4) и «трудозатраты» (У₃=6).

Пример №3. Размещение производственных заказов

В планируемом периоде необходимо обеспечить производство 300000 однородных новых изделий, которые могут выпускаться на четырех филиалах предприятия. Для освоения этого нового вида изделий нужны определенные капитальные вложения. Разработанные для каждого филиала предприятия проекты освоения нового вида изделия характеризуются величинами единицы продукции удельных капиталовложений и себестоимостью единицы продукции (Табл. 7.2.).

Предположим, что на все филиалы предприятия для освоения 300 тысяч новых изделий может выделить 18 миллионов тенге.

                                                                                                        Таблица 7.2.

Необходимо найти такой вариант распределения объемов производства продукции и капитальных вложений по филиалам, при котором суммарная стоимость изделий будет минимальной.

Введем обозначения:

 i - номер филиала (i=1,…,4);

X_i  – объем выпускаемой продукции в i-ом филиале предприятия;

T – суммарная потребность в изделиях (Т=300000 штук);

K – выделяемые капиталовложения (К=18 млн. тенге);

C_i – себестоимость производства продукции в  i-ом филиале;

K_i  - удельные капиталовложения на 1 продукции в i-ом филиале.

Экономико-математическая модель задачи имеет следующий вид:

x_i ≥ 0 ;  i=1,…,n , с учетом имеющихся данных.

f(x)=83Х₁ + 89Х₂ +95Х₃ +98Х₄→ min

Х₁ + Х₂+ Х₃+ Х₄ ≥300000 штук

12Х₁ +80Х₂+50Х₃+40Х₄ ≤ 18 млн. тенге

x₁ , x₂ , x₃ , x₄ ≥ 0.

Сформулируем экономико-математическую модель двойственной задачи. Введем обозначения переменных двойственной задачи Y₁ и Y₂ .

Y₁ - двойственная оценка выпускаемой продукции, которая может быть ценой изделия;

Y₂ - двойственная оценка капитальных вложений, которая может быть представлена как коэффициент эффективности капитальных вложений.

Экономико-математическая модель двойственной задачи имеет вид:

g(Y)=T^.Y₁- K^.Y₂ → max

Y₁- K^. Y₂ ≤ C_i   i=1,…,4

Y₁ ≥ 0;   Y₂ ≥ 0.

Целевая функция g(Y) означает, что необходимо максимизировать разность между стоимостью произведенной продукции (T_*Y₁) и величиной капитальных вложений, соизмеренной во времени с выпуском заданного объема продукции (K_*Y₂). Разность между ними соответствует суммарному «выигрышу» от вложенных капиталовложений на изготовление 300000 изделий.

Цена продукции Y₁ и коэффициент эффективности Y₂ взаимосвязаны. Цена одного изделия, выпускаемого в каждом из филиалов, не может быть больше, чем все производственные затраты, включающие в себя в данном случае себестоимость С_i и приведенные к текущим издержкам через коэффициент эффективности капиталовложения K_i*Y_1.

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

g(Y)=300000_*Y₁ –18000000_*Y₂ → max

                       Y₁ –120_* Y₂ ≤ 83

                       Y₁ –  80_* Y₂ ≤  89

                       Y₁ –  50_* Y₂ ≤95

                       Y ₁ – 40_* Y₂ ≤ 98

Вам также может быть полезна лекция "35. Прогнозирование и дизайн белковых структур".

                       Y₁ ≥0;  Y₂ ≥ 0.

В результате решения получены оптимальные планы:

= (0; 100000; 200000; 0);

= (105; 0; 2);

= 279 млн.

Которые говорят о том, что в первом и четвертом филиалах размещать заказы по выпуску новых изделий невыгодно (x₁=0 и  x₄ =0). Выпуск следует наладить во втором и третьем филиалах. При этом суммарная себестоимость выпускаемых изделий составит 279 миллионов.