Содержание отчета по результатам

В отчете по результатам содержатся оптимальные значения переменных Х₁, Х₂, Х₃, Х₄, которые соответственно равны 0; 10; 30; 0; значение целевой функции - 150, а также левые части ог­раничений.

Содержание остальных отчетов будет рассмотрено ниже.

3. Сформулируем экономико-математическую модель двойственной задачи к задаче о коврах.

Неизвестные. Число неизвестных в двойственной задаче равно числу функциональных ограничений в исходной задаче. Исход­ная задача содержит 3 ограничения: по труду, сырью и оборудо­ванию. Следовательно, в двойственной задаче 3 неизвестных:

Y₁ — двойственная оценка ресурса «труд», или «цена» труда;

Y₂ — двойственная оценка ресурса «сырье», или «цена» сырья;

Y₃ — двойственная оценка ресурса «оборудование», или «цена» оборудования.

Целевая функция двойственной задачи формулируется на ми­нимум. Коэффициентами при неизвестных в целевой функции двой­ственной задачи являются свободные члены в системе ограничений исходной задачи:

g( ) = 80У₁+ 480У₂+130У₃ min.

Необходимо найти такие «цены» на ресурсы (Y_i), чтобы общая стоимость используемых ресурсов была минимальной.

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

7Y₁ + 5Y₂ + 2Y₃ 3,

2Y₁ + 8Y₂ + 4Y₃ 4,

2Y₁ +4Y₂ + Y₃ 3,

6Y₁ +3Y₂ + 8Y₃ 1,

Y₁, Y₂, Y₃ 0.

4. Найдем оптимальный план двойственной задачи, используя
теоремы двойственности.

Воспользуемся первым соотношением второй теоремы двойственности

тогда

Y₁ (7Х₁ + 2Х₂ + 2Х₃ + 6Х₄ - 80) = 0,

Y₂ (5Х₁ + 8Х₂ + 4Х₃ + ЗХ₄ - 480) = 0,

У₃ (2Х₁ + 4Х₂ + Х₃ + 8Х₄ - 130) = 0.

Подставим оптимальные значения вектора в полученные вы­ражения

Y₁ (7х0 + 2х30+ 2х10 + 6х0 - 80) = 0,

Y₂ (5х0 + 8х30+ 4х10 + Зх0 - 480) = 0,

У₃ (2х0 + 4х30 + 1х10 + 8х0- 130) = 0.

и получим

Y₁ (80 - 80) = 0,

У₂ (280 - 480) = 0, так как 280 < 480, то У₂ = 0,

У₃ (130 -130) = 0.

Воспользуемся вторым соотношением второй теоремы двойственности

если х_i>0, то

В нашей задаче Х₂ = 30 > 0 и Х₃ = 10 > 0, поэтому второе и третье ограничения двойственной задачи обращаются в равенства

2 х Y₁ + 8 х Y₂ + 4 х Y₃ = 4,

2 х Y₁+ 4 х Y₂ + 1 х Y₃ = 3,

Y₂ = 0.

Решая полученную систему уравнений, находим Y₁ и У₃.

Теневые цены ресурсов «труд», «сырье» и «оборудование» со­ответственно равны У₁ = 4/3, У₂ = 0, У₃ = 1/3, или в десятичных дробях 1,3333; 0; 0,3333.

Проверим выполнение первой теоремы двойственности

= 80 х Y₁ + 480 х У₂ +130 х У₃ =

= 80x4/3 + 480x0 + 130x1/3 = 150,

= 3 х Х₁ + 4 х Х₂ + 3 х Х₃ + Х₄ =

= 3x0 + 4x30 + 3x10 + 0 = 150.

Это означает, что оптимальный план двойственной задачи определен верно.

Ответ на вопрос о равенстве нулю Х₁ и Х₄ будет дан позже.

Решение двойственной задачи можно найти, выбрав команду Поиск решений => Отчет по устойчивости.

Отчет по устойчивости. Отчет по устойчивости приводится в табл. 1.5. Первая часть таблицы содержит информацию, относя­щуюся к переменным;

• Результат решения задачи.

• Нормированная стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение. Например, в отчете по устойчивости для рассматриваемой задачи (см. табл. 1.5) нормированная стоимость для ковров первого вида равна - 7 тыс. руб./шт. (строка 1). Это означает, что если мы, несмотря на оптимальное решение (0; 30; 10; 0), попробуем включить в план выпуска один ковер первого вида, то новый план выпуска принесет нам доход 143 тыс. руб., что на 7 тыс. руб. меньше, чем прежнее оптимальное решение.

• Коэффициенты целевой функции.

• Предельные значения приращения целевых коэффициентов , при которых сохраняется первоначальное оптимальное реше­ние. Например, допустимое увеличение цены на ковер первого вида равно 7 тыс. руб./шт., а допустимое уменьшение — практически не ограничено (строка 1 из табл. 1.5). Это означает, что если цена ковра первого вида возрастет более чем на 7 тыс. руб./шт., то оптимальное решение изменится: станет целесообразным вы­пускать Х₁. А если их цена будет снижаться вплоть до нуля, то оптимальное решение (0; 30; 10; 0) останется прежним.

Во второй части табл. 1.5 содержится информация, относя­щаяся к ограничениям:

• Величина использованных ресурсов в колонке Результ. значение.

• Предельные значения приращения ресурсов . В графе Допустимое уменьшение показано, на сколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптималь­ное решение. Рассмотрим анализ дефицитных ресурсов. Ана­лизируя отчет по результатам, мы установили, что существуют причины (ограничения), не позволяющие фабрике выпускать больше ковров, чем в оптимальном решении, и получать более высокий доход. В рассматриваемой задаче такими ограниче­ниями являются дефицитные ресурсы «труд» и «оборудование». Поскольку знак ограничений этих запасов имеет вид , то возникает вопрос, на сколько максимально должен возрасти запас этих ресурсов, чтобы обеспечить увеличение выпуска продукции. Ответ на этот вопрос показан в графе Допустимое увеличение. Ресурс «труд» имеет смысл увеличить самое большее на 150 чел./дней, а ресурс «оборудование» - на 30 станко/час.

• Ценность дополнительной единицы ресурса i («теневая цена») рассчитывается только для дефицитных ресурсов.

Таблица 1.5

Содержание отчета по устойчивости

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

• Анализ использования ресурсов в оптимальном плане выпол­няется с помощью второй теоремы двойственности:

если Y_i >0, то i = 1, …, т;

если , то Y_i = 0, i = 1, …, т.

Ресурсы «труд» и «оборудование» имеют отличные от нуля оценки 4/3 и 1/3 - эти ресурсы полностью используются в опти­мальном плане и являются дефицитными, т.е. сдерживающими рост целевой функции. Правые части этих ограничений равны левым частям:

7Х₁ + 2Х₂ + 2Х₃ + 6Х₄ 80,

2Х₁ + 4Х₂ + Х₃ + 8Х₄ 130,

7 х 0 + 2 х 30 + 2 х 10 + 6 х 0 = 80 = 80,

2 х 0 + 4 х 30 + 1 х 10 + 8 х 0 = 130 = 130.

Ресурс «сырье» используется не полностью (280 < 480), поэто­му имеет нулевую двойственную оценку (Y₂ = 0).

5Х₁ + 8Х₂ + 4Х₃ + 3Х₄ 480,

5х0 + 8х30+ 4х10 + 3 х0 = 280 < 480.

Этот ресурс не влияет на план выпуска продукции. Общая стоимость используемых ресурсов при выпуске 30 ков­ров второго вида и 10 ковров третьего вида составит 150 тыс. руб.:

= 80 х Y₁ + 480 х У₂ +130 х У₃ =

= 80x4/3 + 480x0 + 130x1/3 = 150 тыс. руб.

Согласно четвертому ограничению задачи не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его недефицитности. Недефицитность ресурса возникает не из-за его неограниченных запасов (в задаче они ограничены величиной b_i), а из-за невоз­можности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функ­цию .

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

• Анализ эффективности отдельных изделий выполняется на ос­нове соотношений из второй теоремы двойственности:

если X_j > 0, то , j =1, …, n;

если то X_j = 0, j =1, …, n.

Поясним равенство нулю Х₁ и Х₄. Если изделие вошло в опти­мальный план (X_j > 0), то в двойственных оценках оно не убыточ­но, т.е. стоимость ресурсов, затраченных на производство единицы изделия, равна его цене. Такие изделия эффективны, выгодны с точки зрения принятого критерия оптимальности. В нашей зада­че - это ковры второго и третьего видов.

Если стоимость ресурсов, затраченных на производство одного изделия, больше его цены, то это изделие не войдет в оптималь­ный план из-за его убыточности. В нашей задаче в план выпуска не вошли ковры первого и четвертого видов, потому что затраты по ним превышают цену на 7 (10 -3 = 7) тыс. руб. и 9,666 (10,666 - 1 = = 9,666) тыс. руб. соответственно. Этот факт можно подтвердить, подставив в ограничения двойственной задачи оптимальные значения вектора Y:

7x4/3 + 5x0 + 2x1/3 = 30/3 = 10 > 3,

2x4/3 + 8x0 + 4x1/3 = 12/3 = 4 = 4,

2 х 4/3 + 4 х 0 + 1 х 1/3 = 9/3 = 3 = 3,

6 х 4/3 + 3 х 0 + 8 х 1/3 = 32/3 = 10,666 > 1.

Разницу между правыми и левыми частями ограничений двой­ственной задачи можно найти в Отчете по устойчивости в столбце Нормируемая стоимость.

6. Анализ влияния изменения правых частей ограничений на значе­ния целевой функции (чувствительность решения к изменению запасов сырья).

Предположим, что запас сырья ресурса «труд» изменился на 12 ед., т.е. теперь он составляет 80 + 12 = 92 ед.

Из теоремы об оценках известно, что колебание величины b_i приводит к увеличению или уменьшению . Оно определяется величиной y_i в случае, когда при изменении величин b_i значения переменных y_i в оптимальном плане соответствующей двойствен­ной задачи остаются неизменными. В нашей задаче увеличение запасов ресурса «труд» приведет к увеличению значения целевой функции на 16 тыс. руб. ( 12 х 4/3 = 16).

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

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

Таблица 1.6

Отчет по устойчивости

После увеличения запаса ресурса «труд» до 92 чел./час было по­лучено новое решение задачи. Изменение запасов ресурсов в пре­делах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции на 16 тыс. руб., но и к изменению плана выпуска. При этом структура плана не изменилась - изделия, которые были убыточны, не вошли и в новый план выпуска, так как цены на ресурсы не изменились. Новый план выпуска составляет 28 ковров второго вида и 18 ков­ров третьего вида. Изменение общей стоимости продукции на 16 тыс. руб. (24 - 8 = 16) получено за счет уменьшения пла­на выпуска на 2 ед. ковров второго вида по цене 4 тыс. руб. (4 х (28 - 30) = -8 тыс. руб.) и увеличения на 8 ед. плана выпуска ковров третьего вида по цене 3 тыс. руб. (3 х (18 - 10) = 24 тыс. руб.).

Пример1.3. Применяя симплекс-метод к задаче о размещении производственных заказов (см. пример 1.1), был получен оптималь­ный план распределения объемов производства по филиалам пред­приятия:

Требуется: сформулировать экономико-математическую модель прямой и двойственной задачи, используя данные табл. 1.2 и найти оптимальный план двойственной задачи, используя теоремы двой­ственности.

Решение

1. Экономико-математическая модель исходной задачи.

Пусть X_i — объем выпускаемой продукции в филиале i. Целе­вая функция задачи имеет вид

= 83 Х₁ + 89Х₂ + 95Х₃ + 98 Х₄ min.

Ограничения

Х₁ + Х₂ + Х₃ + Х₄ 300 (тыс. шт.),

120Х₁ + 80Х₂ + 50Х₃ + 40Х₄ 18 (млн руб.),

X_1,2,3,4 0.

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

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

Пусть Y₁ — двойственная оценка выпускаемой продукции, ко­торая может быть ценой изделия; Y₂ — двойственная оценка капитальных вложений, которая может быть представлена как коэффициент эффективности капитальных вложений. Тогда

= 300 000Y₁ + 18 000 000Y₂ max,

1 х Y₁ + 120 x Y₂ 83,

1 x Y₁ + 80 x Y₂ 89,

1 x Y₁ + 50 x Y₂ 95,

1 x Y₁ + 40 x Y₂ 98.

3.Для определения оптимального плана двойственной задачи вос­пользуемся соотношениями второй теоремы двойственности.

Если какое-либо ограничение исходной задачи выполняется как строгое неравенство, то соответствующая двойственная оценка равна нулю, т.е.

если то Y_i = 0, i = 1, …, m.

Подставляя значения вектора в ограничения исходной за­дачи, получим:

0 + 100 000 + 200 000 + 0 = 300 000,

120 х 0 + 80 х 100 000 + 50 х 200 000 + 4 х 0 = 18 000 000.

Двойственные оценки Y₁ и Y₂ могут принимать любые значения.

Если какая-либо переменная исходной задачи входит в опти­мальный план, то соответствующее ограничение двойственной задачи выполняется как строгое равенство:

если X_j > 0, то

В нашей задаче Х₂ = 100 000 > 0 и Х₃ = 200 000 > 0, поэтому второе и третье ограничения двойственной задачи обращаются в уравнения, решая которые найдем Y₁ и Y₂:

Тогда

105 = 95 + 50 х 0,2 = 105,

105 = 89 + 80 х 0,2 = 105.

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

= 300 000 Y₁ + 18 000 000 Y₂ =

= 300 000 х 105 + 18 000 000 х (-0,2) = 279 000 000,

= 83 Х₁ + 89 Х₂ + 95 Х₃+ 98 Х₄ = 83 х 0 +

+ 89 х 100 000 + 95 х 200 000 + 98 х 0 = 279 000 000.

Полученные оптимальные планы говорят о том, что в первом и четвертом филиалах размещать заказы по выпуску новых изде­лий невыгодно (Х₁ = 0 и Х₄ = 0), так как затраты на производство единицы изделия в этих филиалах больше цены изделия:

1х Y₁ + 120 х Y₂ = 83; Y₁ = 105; 105 + 120 х (-0,2) < 95;

105 < 95 + 24 = 119;

1Y₁ + 40x Y₂ = 98; Y₂ = -0,2; 105 + 40 х (-0,2) < 89;

105 < 98 + 8 = 106.

Задачи для самостоятельного решения

Задача 1.1. Решите следующую задачу ЛП графическим спо­собом:

= - 2х - х₂ min (max),

2х₁ + 4х₂ 16,

-4x₁ + 2х₂ 8,

х₁ + Зх₂ 9,

6х₁ + 5 х₂ = 30,

х₁, х₂ 0.

Задача 1.2. Решите графическим способом задачу ЛП, связан­ную с распределением ресурсов:

= 2х₁ + 4х₂ max (прибыль),

при ограничениях:

х₁ + 2х₂ 5 (ресурс 1),

х₁ + х₂ 4 (ресурс 2),

х₁ 0,

х₂ 0.

1. Определите статус каждого ресурса (дефицитный, недефицитный).

2. Найдите максимальный интервал изменения запасов ресурса 1, в пределах которого текущее решение остается допустимым.

3. Выполните задание пункта 2 применительно к ресурсу 2.

4. Для пунктов 2 и 3 определите соответствующее изменение оптимальных значений целевой функции.

5. Найдите максимальный интервал изменения удельной прибы­ли для переменной х₁, в пределах которого полученное решение остается оптимальным.

6. Выполните задание пункта 5 применительно к переменяй х₂.

Задача 1.3. Инвестор, располагающий суммой в 300 тыс. руб., может вложить свой капитал в акции автомобильного Концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс руб. Дивиденды по акциям А составляют 8% в год, по акциям В - 10%. Какую максимальную прибыль можно полу­чить в первый год?

Задача 1.4. Фирма производит два популярных безалкоголь­ных напитка — «Лимонад» и «Тоник». Фирма может продать всю произведенную продукцию, однако объем производства ограни­чен количеством основного ингредиента и производственной мощ­ностью оборудования. Для производства 1 л «Лимонада» требуется 0,02 час работы оборудования, а для производства 1 л «Тоника» - 0,04 час. Расход специального ингредиента составляет 0,01 и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно в распоряжении фирмы имеется 24 час времени работы обору­дования и 16 кг специального ингредиента. Доход фирмы состав­ляет 0,10 руб. за 1 л «Лимонада» и 0,30 руб. за 1 л «Тоника». Сколь­ко продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневного дохода?

1.5. СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.5.1. Задачи целочисленного программирования

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

Особый интерес к задачам ЦП вызван тем, что во многих прак­тических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных. К их числу относятся:

• задачи оптимизации раскроя;

• оптимальное проектирование машин и оборудования;

• оптимизация системы сервиса и технического обслуживания машинно-тракторного парка и т.д.

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

Задачи оптимизации, в результате решения которых искомые значения переменных должны быть целыми числами, называются задачами (моделями) целочисленного (дискретного) программи­рования:

max(min) f (x₁,x₂, ...,х_n) =

i = 1, 2,..., m,

x_j 0, j = 1, 2, …, n,

x_j - целые, j = 1, 2, …, p (p n).

Если p = n, то задачу называют полностью целочисленной, если р < п - частично целочисленной.

Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используемым методом является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Excel.

Дискретная оптимизация средствами Excel проводится анало­гично решению соответствующих непрерывных задач. Основное отличие заключается в том, что в диалоговом окне Поиск решения устанавливается требование целочисленности соответствующих переменных (при этом в режиме Параметры устанавливается тип задачи - линейная или нелинейная).

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

Пример 1.4. Задача производства неделимой продукции (опти­мизация производственной программы мебельного предприятия).

Мебельное предприятие выпускает книжные полки, тумбу под телевизоры и три вида наборов мебели. Характеристики каждого вида продукции приведены в табл. 1.7. При условии получения максимальной прибыли объем товарной продукции должен со­ставить не менее 459,31 тыс. руб. Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен, поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели 2 - от 7 до 10 тыс. шт. Спрос на наборы мебели 1 и 3 неограничен, и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, количество которого и нормы затрат времени на изготовление единицы продукции каждого вида приведены в табл. 1.8. Пред­приятие работает в две смены, эффективное время работы каждой машины — 3945 час (коэффициент сменности 1,9). Оптимизиро­вать производственную программу предприятия.

Таблица 1.7

Таблица 1.8

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

Требуется найти план выпуска продукции, максимизирующий прибыль предприятия.

Обозначим через Х₁, Х₂, Х₃, Х₄, Х₅ количество продукции каж­дого типа (шт.). Каждая машина работает в две смены, эффектив­ное время работы - 3945 час. Определим фонд времени работы оборудования каждого типа:

Целевая функция в этом случае имеет вид

= 2,4Х₁ + 4,5Х₂ + 8,9Х₃ + 0,06Х₄ + 0,45Х₅ max.

Ограничение по объему товарной продукции

7,2Х₁ + 14,3Х₂ + 26,9Х₃ + 0,243Х₄ + 1,5Х₅ 459,31 тыс. руб.

Ограничения по фонду времени работы оборудования:

0,068 Х₁ + 0,096 Х₂ + 0,207 Х₃ + 0,018 Х₄ + 0,042 Х₅ 7890,

0,045 Х₁ + 0,080 Х₂ + 0,158 Х₃ + 0,011 Х₄ + 0,035 Х₅ 3945,

0,132 Х₁ + 0,184 Х₂ + 0,428 Х₃ + 0,020 Х₄ + 0,060 Х₅ 7890,

0,057 Х₁ + 0,082 Х₂ + 0,230 Х₃ + 0,010 Х₄ + 0,028 Х₅ 7890,

0,063 Х₁ + 0,090 Х₂ + 0,217 Х₃ + 0,010 Х₄ + 0,033 Х₅ 7890,

0,170 Х₁ + 0,280 Х₂ + 0,620 Х₃ + 0,020 Х₄ + 0,096 Х₅ 157 800.

Ограничение по сбыту продукции:

Х₁ 10 000,

7000 Х₂ 10 000,

Х₃ 10 000,

Х₄ 10 000,

4000 Х₅ 7000,

Х₁, Х₂, Х₃, Х₄, Х₅ 0,

Х₁, Х₂, Х₃, Х₄, Х₅ - целые числа.

Решение задачи целочисленного программирования с помощью средства Excel Поиск решения

На рис. 1.22—1.25 и табл. 1.9 отражена последовательность дей­ствий, необходимая для получения решения задачи.

Таблица 1.9