Описание отчетов о решении задачи

Отчет по результатам: таблица Целевая ячейка выводит сведения о целевой функции; таблица Изменяемые ячейки показывает значение искомых переменных, полученных в результате решения задачи; таблица Ограничения отображает результаты оптимального решения для ограничений и для граничных условий. В поле Формула приведены зависимости, которые были введены в окно Поиск решения, в поле Разница – величины использованного материала. Если материал используется полностью, то в поле Статус указывается связанное, при неполном использовании материала в этом поле указывается не связан. Для граничных условий приводятся аналогичные величины с той лишь разницей, что вместо величины неиспользованного продукта показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

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

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

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

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

В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной, или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

Переменные двойственной задачи y_i называются объективно обусловленными оценками (или двойственными оценками, «ценами» ресурсов, теневыми ценами).

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

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

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид (≤ ), в задаче на минимум вид (≥ );

2) матрица А , составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица А^Т в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной;

5) каждому ограничению одной задачи соответствует переменная другой задачи, номер переменной совпадает с номером ограничения. При этом ограничению, записанному в виде неравенства ≤, соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:

, (10)

(11)

а модель двойственной задачи –

(12)

(13)

 

Решая ЗЛП симплекс-методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи y_ί называют объективно обусловленными оценками.

Рассмотрим анализ оптимального решения на основе примера 1. Решение произведено с использованием MS Excel ( Поиск решения ) и представлено на рисунке 13.

 

Создание отчёта по результатам поиска решения

Excel позволяет представить результаты поиска решения в форме отчёта (рис. 25, 26).

Существует три типа таких отчётов:

· отчет по устойчивости «Sensitiviti», содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений;

· отчет по пределам «Limits». Помимо исходных и конечных значений изменяемых и целевой ячеек, в отчёт включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений;

· отчет по результатам «Answer». В отчёт включаются исходные и конечные значения целевой и изменяемых ячеек, дополнительные сведения об ограничениях.

В отчёте по результатам содержатся оптимальные значения переменных Х1, Х2, Х3, Х4, которые, соответственно, равны 0; 30; 10; 0; значение целевой функции – 150, а также левые части ограничений (рис. 25).

Рис. 25. Отчёт по результатам

 

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

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

· результат решения задачи;

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

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

 

· коэффициенты целевой функции;

· предельные значения приращения целевых коэффициентов ∆ с_i, при которых сохраняется первоначальное оптимальное решение. Например, Допустимое увеличение цены на изделие вида А – 7 тыс. руб/шт., Допустимое уменьшение – практически не ограничено. Если цена изделия А возрастет более чем на 7 тыс. руб/шт., то оптимальное решение изменится: станет целесообразным выпускать продукцию Х₁. А если их цена будет снижаться вплоть до нуля, то оптимальное решение (0, 30, 10, 0) останется прежним.

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

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

· предельные значения приращения ресурсов ∆ b_i. В графе Допустимое уменьшение показано, насколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптимальное решение.

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

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

если Y_i> 0, то (14)

если (15)

 

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

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), поэтому имеет нулевую двойственную оценку Υ ₂= 0).

5Х₁ + 8Х₂ + 4Х_з + 3Х₄ ≤ 480,

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

Этот ресурс не влияет на план выпуска продукции.

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

= 80× Υ ₁ + 480× Υ ₂+ 130× Υ ₃ =

= 80× 4/3 + 480× 0 + 130× 1/3 = 150 тыс. руб.

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

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

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

если то (16)

если то (17)

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

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

7× 4/3 + 5× 0+ 2× 1/3 = 30/3 = 10 > 3,

2× 4/3 + 8× 0 + 4× 1/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.

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

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

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

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

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

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

Рис. 27. Отчет по устойчивости

 

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

4. Нелинейное программирование

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

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: