<<
>>

РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В ЭЛЕКТРОННОЙ ТАБЛИЦЕ EXCEL 5.0

В данной книге решение оптимизационных задач иллюстрируется на примере использования электронной таблицы Excel. Однако, используемая при этом теория и технология применимы и для других электронных таблиц (Quattro Pro, Lotus 1-2-3 и т. д.).

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

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

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

Решение оптимизационных задач в EXCEL 5.0 осуществляется программой ПОИСК РЕШЕНИЯ меню СЕРВИС, которая позволяет решать сложные линейные (нелинейные) задачи со многими переменными и ограничениями. После того, как Вы определите задачу и выберете ВЫПОЛНИТЬ, программа изменит значения переменных и выполнит необходимые вычисления в ЭТ, а затем, основываясь на полученных результатах, будет повторять эту процедуру до тех пор, пока не получит решение, удовлетворяющее условиям задачи. Каждый цикл изменения переменных называется итерацией. Иногда для получения правильного решения может понадобится выполнить несколько сотен итераций.

Пример постановки линейной задачи

Предприятие может выпускать четыре вида продукции П1, П2, ПЗ, П4. Для их изготовления используются три вида ресурсов Р1, Р2, РЗ, объемы которых ограничены. Известна прибыль, получаемая от реализации единицы продукции каждого вида продукции (единичная прибыль). Заданы также граничные значения выпуска каждого вида продукции (верхняя и нижняя граница). Кроме того, известны потребности в ресурсах для выпуска единицы каждого вида продукции (ресурсные коэффициенты, определяющие технологию производства). Требуется определить оптимальное количество выпуска каждого вида продукции, при котором будет получена максимальная прибыль.

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

Целевая функция: ЦФ=60*П1+70ΊΊ2+120*ПЗ+130*П4 -> max.

Ограничения на ресурсы:

Р1=1 *П1+1*П2+1 *ПЗ+1 *П4 ряд параметров (см. Рис. 7.1).

Рис. 7.1. Диалоговое окно “Поиск решения"

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

Значение целевой функции, выражающей критерий оптимизации, может быть задано определенным числом или требованием ее максимизации (минимизации).

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

Рис. 7. 2. Диалоговое окно “Добавить ограничение'

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

В нашем примере необходимо задать таким образом 7 ограничений.

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

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

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

Установленные параметры и ограничения поиска решения можно сохранить в качестве модели. Текущая модель сохраняется вместе с рабочим листом. Для того, чтобы иметь возможность сохранить дополнительные модели, следует нажать на кнопку Сохранить модель в диалоговом окне Параметры поиска решения. В появившемся диалоговом окне нужно указать область модели. Модель сохраняется в вертикальном интервале ячеек, который начинается с выделенной ячейки и расширяется вниз.

Для загрузки модели следует нажать кнопку Загрузить модель в диалоговом окне Параметры поиска решения и в появившемся диалоговом окне задать ссылку на область модели.

Рис. 7. 3. Диалоговое окно “Параметры поиска решения”

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

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

Если установлена опция Восстановить исходные значения и не

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

Рос. 7.4. Диалоговое окно “Результаты поиска решения"

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

Итак, мы получили результат: программа определила значения объемов производства для каждого вида продукции и соответствующее значение целевой функции, выражающее получаемую при этом прибыль (см. Табл. 7.13).

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

Отчет по результатам. На Рис. 7.5 мы видим отчет по результатам решения задачи, включающий в себя три таблицы.

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

жит информацию об ограничениях. В столбце “Значение" помещены оптимальные значения потребных ресурсов и оптимизируемых переменных. Столбец “Формула" содержит ограничения на потребляемые ресурсы и оптимизируемые переменные, записанные в форме ссылок на ячейки, содержащие эти данные. Столбец “Состояние" определяет связанными или несвязанными являются те или другие ограничения. Под "связанными” здесь понимаются ограничения, которые реализуются в оптимальном решении в виде жестких равенств. Заметьте, что Ресурс 2 в оптимальном решении используется до конца (без остатка) и поэтому является связанным, т. е. дефицитным. Последний столбец "Разница” для ресурсных ограничений определяет остаток используемого ресурса, т. е. разность между потребным количеством ресурсов и их наличием. Для ограничений по объему выпуска здесь указывается разность между верхней или нижней границей выпуска данного вида продукции и его полученным оптимальным значением.

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

Отчет по устойчивости. На Рис. 7.6 приведен отчет по устойчивости для линейных задач, состоящий из двух таблиц.

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

Первая часть отчета содержит информацию об изменяемых ячейках, содержащих значения объемов производства продукции. В столбце “Ре зультирующее значение” указываются оптимальные значения оптимизируемых переменных. В столбце “Редуцированная стоимость” (Reduced cost) помещены одноименные показатели для каждого вида продукции. Величина показателя редуцированной стоимости определяется как разность между вносимой в целевую функцию единичной прибылью (от производства единицы продукции данного вида) и оценкой сни-

Microsoft Eicel 5.0 Отчет по устойчивости

Изменяете ячейки

Ячейка Имя Ревупьт.

значение

Редуц.

СТОИМОСТЬ

Целевой Допустимое коэффициент увеличение Допустимое

уменьшение

4В44 OSvpm производства П1 4.00 12.00 $0,00 1.00Е+30 1.20Е.01
4C44 OSvph производства П2 2.00 -2,00 70.00 2.00Е-00 1.00Е+30
4D44 OSvpm производства ПЗ 5.90 0.00 120,00 1.00E+3Q З.ЗЗЕ-00
4Е44 СЮьем производства П4 1.00 •26.00 130,00 2.60Е+01 1.00Е+30
іграничения
Ячейка Имя Ре»|№т.

значение

Теневая

цена

Ограничение Допустимое Правая часть увеличение Допустимое

уменьшение

№48 Pecqpc 1 Требуется: 12.80 0.00 16.00 1.00Е-30 3.10Е+С0
№43 Pecqpc 2 TpeSqeicB: Ю0.00 12.00 100.00 3.10Е+01 3.90Е+01
4F410 Peeqpc 3 Требуется; 60.60 0.00 110.00 1.00Е-30 4.94Е+01

Рис. 7. 6. Отчет по устойчивости для линейных задач

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

Редуцированная стоимость продукции I вида=60-(0*1 + 12*4+ 0*6)=12. Редуцированная стоимость продукции Il вида=70-(0*1+12*6+0*5)=-2. Редуцированная стоимость продукции III вида=120-(0*1+12*10+0*4)=0. Редуцированная стоимость продукции IV вида=130-(0*1+12*13+0*3)=-26.

Столбец “Целевой коэффициент" содержит исходные значения коэффициентов целевой функции. В следующих двух колонках иллюстрируется допустимое увеличение и уменьшение этих коэффициентов без изменения найденного оптимального решения. Так, для нашего случая коэффициент оптимизируемой переменной Ш, равный 60, может быть увеличен на 30 порядков (до значения, равного 60+1029) или уменьшен на 12 единиц (до значения 60-1,2*10) без изменения найденного решения (при сохранении без изменений всех остальных переменных). Вы можете проверить это, повторно решив задачу для значений коэффициента целевой функции при переменной П1, находящихся в диапазоне [48,(60+1029)]. Поскольку второе значение диапазона, как нетрудно заметить, представляет собой практически бесконечно большое число, следует говорить о наличии лишь ограничения снизу на значение рассматриваемого коэффициента целевой функции. Аналогично определяются диапазоны возможного изменения коэффициентов целевой функции при остальных переменных.

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

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

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

Так, например, из отчета по устойчивости (Рис. 7.6) видно, что теневая цена ресурса 2 составляет 12,00. Следовательно, если мы увеличим имеющееся количество данного ресурса на некоторую величину, находящуюся в пределах от 0 и до 31, оптимальное значение целевой функции увеличится на 12,00 за каждую единицу увеличения имеющегося объема ресурса 2. Если же мы уменьшим имеющееся количество ресурса 2 на некоторую величину, находящуюся в пределах от 0 до 39, оптимальное значение целевой функции уменьшится на 12,00 за каждую единицу уменьшения имеющегося объема ресурса 2.

Теперь рассмотрим теневые цены на несвязанные ограничения, по которым ресурсы в оптимальном решении используются не полностью (недефицитные ресурсы). В нашем примере таких ограничений два: ограничения по ресурсу 1 и ресурсу 3 (см. Рис. 7.6). Рассмотрим ограничение по ресурсу 1. Ресурс 1 имеет теневую цену, равную 0, при возможном увеличении объема ресурса до бесконечности или уменьшении, находящемся в пределах от 0 до 3,1. Отсюда следует, что при увеличении имеющегося объема ресурса 1 оптимальное значение целевой функции не изменится. Это и не удивительно, поскольку оптимальное решение оставляет 3,1 единицы ресурса 1 неиспользованными, и дальнейшее увеличение этого излишнего запаса не может улучшить оптимального решения. Однако, с другой стороны, поскольку оптимальное решение оставляет 3,1 единицы ресурса 1 неиспользованными, мы можем сократить имеющийся объем этого ресурса на 3,1 единицы, не оказывая влияния на оптимальное решение. Тоже самое мы можем сказать о ресурсе 3, по которому мы можем сократить имеющийся объем ресурса на 49,4 без изменения оптимального решения.

Вернемся опять к связанным ограничениям. Допустим, что мы решили увеличить имеющийся объем ресурса 2 на 30 единиц. Поскольку это увеличение находится в разрешенных пределах (допустимое увеличение составляет 31 единицу), мы вправе ожидать увеличения оптимального значения целевой функции на 12*30=360. Новое оптимальное значение целевой функции составит 1218+360=1578 (см. Табл. 7.14).

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

Итак, в предыдущем примере, увеличив объем ресурса 2 на 30 единиц, мы увеличили прибыль на 1578-1218=360 единиц. При этом правомерен вопрос: "Сколько мы можем платить за такое увеличение объема ресурса ?" Ответ прост: ”3а каждую дополнительную единицу связанного (дефицитного) вида ресурсов мы может платить надбавку, максимальная величина которой равна теневой цене 360/30=12”. Даже заплатив такую максимальную надбавку (реально она должна быть меньше), мы получим ту же прибыль, что была до увеличения объема ресурсов.

Таблица 7. 14

Решение, полученное после увеличения имеющегося объема ресурса 2

на 30 единиц

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

Рассмотрим еще пример. Допустим, что мы решили выпустить на рынок новый вид продукции. Производство единицы такой продукции требует затрат 1 единицы ресурса 1, 8 единиц ресурса 2, 13 единиц ресурса 3 и приносит 127 единиц прибыли. Будет ли эта продукция прибыльной ?

Ответ на этот вопрос можно дать на основе использования теневых цен. Прежде всего заметим, что производство новой продукции будет базироваться на тех же объемах ресурсов, что существовали до его начала. Таким образом, производство каждой единицы новой продукции отвлекает от прежнего производства 1 единицу ресурса 1, 8 единиц ресурса 2 и 13 единиц ресурса 3. Поскольку ресурсы 1 и 3 являются несвязанными, т. е. оптимальное решение использует их не полностью, отвлечение части этих ресурсов не вызовет изменения прибыли. Однако, отвлечение 8 единиц связанного (дефицитного) ресурса для производства единицы новой продукции вызовет снижение общей прибыли на величину 8*12=96 единиц. Это снижение, однако, будет компенсироваться повышением общей прибыли от производства единицы новой продукции, равным 127. Таким образом чистый эффект от производства единицы новой продукции составит 127-96=31, что говорит об эффективности выпуска новой продукции.

Другой возможностью определить, эффективна ли новая продукция, является решение построенной нами модели. До решения модели следует внести в неё коррективы, связанные с вводом дополнительной оптимизируемой переменной. Решение новой модели и отчет по устойчивости приведены в Табл. 7.15 и на Рис. 7.7.

Таблиц а 7.1 S

Решение модели после ввода в неё нового вида продукции
A l в I 3 L E I F I 8 I И 1
І Задача определения производственной программы
э Виды продукции П1 Π2 пз П4 Π5
4 Объем производства 1,0 2,0 6,0 1,0 S.2 Общая прибыль:
JLj Единичная прибыль 60.0 70,0 120,0 130,0 127,0 L 1702.11
7 Ограничения по ресурсам: Требуется: Имеется:
Ресурс 1 1,0 1,0 1,0 1,0 1,0 15,1 16,0
M Ресурс 2 4,0 6,0 10,0 13,0 8,0 130,0 130,0
IF Ресурс 3 6,0 5,0 4,0 3,0 13,0 110,0 110,0
ж Ограничения по объемам производстве:
13 Нижняя граница 1,0 2,0 2,0 1,0 0,0
14 Верхняя граница 4,0 1,0

Заметим, что оптимизируемые переменные всегда имеют равный нулю показатель редуцированных затрат, если их оптимальные значения находятся внутри интервала, образованного верхней и нижней границами. (В нашей модели верхняя граница для всех переменных кроме П1 и П4 равна плюс бесконечности).

Оптимальные значения объемов производства, полученные для продукции /73 и /75, удовлетворяют этому положению. Переменные, оптимальные значения которых совпадают с нижней границей, имеют

Microsoft Excel 5.0 Отчет по дстончнвости

Изменяемые ячейки

bgcolor=white>0
Ячейка Имя РеЗ|ЛЬТ.

значение

Реддц.

CTOUHOCTb

Целевой Допустимое Допустимое коэффициент івеличенпе умеиьшеїте
*В$4 Объем производства П1 1 -1.918367342 60 1918367342 Є*30
$С$4 Объем производства П2 2 •10.2244888 70 10.2244898 1Е+30
*0*4 Объем производства ПЗ 5.989387755 120 38.75 12,86896552
*Е$4 Объем производства П4 1 -19.04081632 130 19.04081632 1Е*30
$F$4 Объем производства П5 5.163265306 0 127 84.81818181 4.272727262

Ограничения
Резулы. Теневая Ограничение Допустимое Допустимое
Ячейка Имя значение иена Правая часть ІВеЛНЧеНПе IllfHbinfHUf
8G88 Ресурс 1T ребуется: 15.13265306 0 16 1Е*30 0.867346939
*G$9 Ресурс 2 Требуете» 130 10.73469388 130 $444444444 29.92307692
*G*!0 Ресурс 3 Требуется: 110 3.163265306 110 42.5 50.6

Рис. 7. 7. Отчет по устойчивости после ввода в модель нового вида

продукции

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

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

• теневые цены ресурсов определяют прирост (сокращение) общей прибыли при увеличении (уменьшении) на единицу имеющегося объема дефицитных ресурсов;

• недефицитные ресурсы имеют нулевую теневую цену;

• редуцированная стоимость данной продукции равна разности между её единичной прибылью и суммой произведений ресурсных коэффициентов на теневые цены;

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

Рассмотрим теперь, как влияет изменение ресурсных коэффициентов на оптимальное решение модели. Полученное решение и отчет по устойчивости, которые мы видим в Табл. 7.15 и на Рис. 7.7, показывают, что введенный в производство новый вид продукции эффективен, поскольку его редуцированная стоимость не отрицательна (она равна нулю). Определим условие по потреблению ресурса 2, при котором новая продукция будет неэффективной (т. е будет иметь отрицательную редуцированную стоимость).

127- (0*1+ IOJV2+3,2*13) < 0.

Решив неравенство относительно ресурсного коэффициента г2, получим:

Г2> (127-3,2*13) /10,7 =8,0.

Таким образом, если при производстве единицы новой продукции потребление ресурса 2 превысит 8,0 единиц, производить новую продукцию будет неэффективно

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

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

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

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

Для второго случая следует вычислить показатель η по следующим формулам.

где q - первоначальное значение коэффициента целевой функции для переменной Flj;

Aq- планируемое изменение с,;

Ij - допустимое увеличение Cy в соответствии с отчетом по устойчивости;

Dj - допустимое уменьшение Cj в соответствии с отчетом по устойчивости.

Заметим, что η измеряет отношение планируемых изменений величины Сук максимально возможному изменению, при котором сохраняется данное оптимальное решение. Если изменяется только один из коэффициентов целевой функции, найденное оптимальное решение сохранится, при условии выполнения соотношения η< =1. Аналогично, если более чем один коэффициент целевой функции изменяется, найденное оптимальное решение сохранится при условии выполнения

соотношения Ση< =1. (Заметим, что даже в случае невыполнения ука занного соотношения оптимальное решение может сохраниться, хотя это не может гарантироваться).

Отчет по пределам. Отчет по пределам для приведенного в Табл. 7. 3 оптимального решения модели мы видим на Рис. 7.8.

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

Microsoft Excel 5.0 Отчет по пределам
Ячейка Целевое

имя

Значение
$G$5 Единичная прибыль Общая прибыль: 1217,999992

Ячейка ИМЯ Значение
$В$4 Объем производства П1 4
$С$4 Объем производства П2 2
$Ь$4 Объем производства ПЗ 5,899999935
$Е$4 Объем производства П4 1

Рис. 7. 8. Отчет по пределам

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

Целочисленные линейные задачи оптимизации

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

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

целочисленности независимых переменных мы должны добавить соответствующее ограничение в режиме ПОИСК РЕШЕНИЯ (см. Рис. 7.9).

После решения задачи мы получим новые результаты, приведенные в Табл. 7.16, которые значительно отличаются от ранее полученного решения ( Табл. 7.15).

Данное оптимальное решение получено при установленной по умолчанию величине параметра "Допустимое отклонение", равной 5%. Этот параметр, находящийся в окне “Параметры поиска решения”, устанавливает допустимое отклонение найденного решения от оптимального (в этом смысле найденное решение является как бы субоптимальным). Можно попытаться улучшить полученное решение за счет умень

шения параметра "Допустимое отклонение” вплоть до нулевого значения.

Целочисленные задачи с бинарными переменными. Целочисленная переменная, принимающая только два значения 0 и 1, называется бинарной. Использование бинарных переменных часто оказывается очень удобным при моделировании экономических задач, одну из которых мы приводим ниже.

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

Предположим, что компании предложены 6 независимых инвестиционных проектов, каждый из которых рассчитан на 5 лет и направлен на улучшение технологии производства продукции. Все проекты чрезвычайно привлекательны для компании, однако она не располагает достаточными средствами, чтобы поддержать их все. Данные по требуемым финансовым ресурсам и чистой текущей стоимости доходов (NPV) для всех 6 предлагаемых проектов приведены в Табл. 7.17.

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

Xi= 1, если проект / выбран;

Xi= 0, если проект / не выбран;

/= 1,2,...,6.

При этом каждая введенная бинарная переменная работает как переключатель (в режиме да/нет), показывая, выбран данный проект для финансирования или нет.

Таблица 7.17

Исходные данные по инвестиционным проектам

Проект NPV

(в тыс. долл.)

Объем требуемых средств (в тыс. долл.)
Год 1 Год 2 Год 3 Год 4 Год 5
1 141 75 25 20 15 10
2 187 90 35 0 0 30
3 121 60 15 15 15 15
4 83 30 20 10 5 5
5 265 100 25 20 20 20
6 127 50 20 10 30 40
Имеющийся объем средств (в тыс. долл.) 250 75 50 50 50

Теперь запишем данную задачу в виде целевой функции и ограничений следующим образом.

Целевая функция: 141Χι+187Х2+121Хз+83Х4+265Х5+127Хе -» max

Ограничения на объемы требуемых средств:

75Xf+9ОХ2+6ОХ3+ЗОХ4+10OXs+50Хе bgcolor=white>Проект (0-нет, 1-да) NPV Год 1 Год 2 Год 3 Год А Год 5 6 1 0 141 75 25 20 15 10 7 2 0 187 90 35 0 0 30 S 3 0 121 60 15 15 15 15 9 4 0 83 30 20. 10 5 5 10 5 0 265 100 25 20 20 20 11 S 0 127 50 20 10 30 40 13 Требуемые средства: 0 0 0 0 0 14 Имеющиеся средства: 250 75 50 50 50 15 15 Суммарная чистая текущая стоимость: 0

Правые части ограничений на объемы средств записаны в ячейки D14:H14. И, наконец, целевая функция записана соответствующей формулой (или функцией =СУММПРОИЗ(С6:С11, В6.В11)) в ячейку D16.

Чтобы решить модель в электронной таблице, мы должны сообщить программе ПОИСК РЕШЕНИЯ, где (в каких ячейках) находятся целевая функция, управляемые переменные и ограничения. На Рис 7.10 мы видим диалоговое окно, которое появляется на экране после запуска указанной программы в меню СЕРВИС. В нем мы указываем, что целевая функция находится в ячейке D16, для управляемых переменных резервированы ячейки В6:В11 и добавляем соответствующие ограничения.

Рис. 7.10. Диалоговое окно “Поискрешения" при решении задачи планирования капитальных вложений

Первые три ограничения определяют бинарный характер управляемых переменных, находящихся в ячейках В6:В11. Последнее четвертое ограничение в диалоговом окне определяет требование, в соответствие с которым значения в ячейках D13:Н13 должны быть меньше, чем соответствующие значения в ячейках D14:H14. Как нетрудно заметить, это требование есть не что иное как условие сбалансированности имеющихся и требуемых средств по годам реализации рассматриваемых инвестиционных проектов.

Поскольку данная модель содержит 6 управляемых бинарных переменных, в принципе может существовать 26=64 её возможных решения. Однако, если предположить, что ряд решений не попадут в область допустимых значений управляемых переменных, количество возможных вариантов еще уменьшится. Таким образом, есть все основания ожидать, что при решении данной задачи у компьютера трудностей не возникнет.

Поэтому мы можем установить самый высокий показатель точности решения (параметр "Допустимое отклонение’’=0) в диалоговом окне "Па-

раметры поиска решения” (см. Рис. 7.11). Окончательный вид полученного решения модели приведен на Табл. 7.19.

Бинарные переменные дают возможность использовать в модели различные логические условия. Так, если некоторые из рассматриваемых проектов (например, 1, 3 и 6) являются альтернативными, модель может быть дополнена следующим условием:

Это условие говорит о том, что из трех бинарных переменных Xu Хз и Хбтолько одна может иметь значение 1.

В случае, если проект 4 опирается на результаты проекта 5, и не может быть выполнен, если пятый проект не выполняется, то модель дополняется выражением:

X4-Xs bgcolor=white>2 400

Производство каждого вида продукции требует значительной переналадки поточной линии, что обходится для первого вида продукции в 1000 долл., для второго вида продукции - в 800 долл, и для третьего вида продукции - в 900 долл. Отдел маркетинга компании полагал, что вся произведенная продукция будет продана. Руководство же компании хочет определить наилучший набор выпуска продукции, который обеспечит ей максимальную прибыль.

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

1. Xi- количество продукции вида /, которое должно быть произведено, /=1, 2, 3.

2. Yi= 1, если Х,-> 0, /=1,2,3;

У,= 0, если Xi= 0, /=1,2,3.

Таким образом, мы имеем три обычные целочисленные управляемые переменные Xf, Хг и Хз, выражающие объем производимой продукции по ее видам. При этом каждая X,- имеет соответствующую бинарную переменную Y;, которая будет равняться 1, если соответствующая Xi будет иметь положительное значение и будет равна 0, если соответствующая X/, будет равна нулю. Дальше мы поясним это более подробно.

Используя введенные переменные построим целевую функцию задачи в следующем виде:

48Х)+55Х2+5ОХ3-1000Yj-800Уг-900Уз -илах. (7.1)

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

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

2Хі+ЗХ2+6Хз ограничение по токарным операциям

6Хі+ЗХ2+4Х3 решения линейных и нелинейных задач в ЭТ имеет много общего.

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

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

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

Hi=Cnpoc на продукцию I вида=300-0,106*Ш,

/72=Спрос на продукцию Il вида=325-0,150*Ц2,

/73=Спрос на продукцию III вида=310-0,133*ЦЗ, (7.5)

/"M=Cnpoc на продукцию IV вида=280-0,12УЦ4,

где П1, П2, ПЗи П4- спрос на продукцию каждого вида;

Ц1, Ц2, ЦЗ и Ц4 - цены на единицу продукции каждого вида.

Себестоимость (затраты) производства единицы продукции каждого вида C при этом составила:

Ci=1520,

С2= 1400,

С3=1800,

С4=1680.

Условия производства, характеризующиеся значениями ресурсных коэффициентов, не изменились, а имеющиеся запасы ресурсов увеличились, составив соответственно 160, 1300 и 1100.

Как нетрудно заметить, переменные П1, П2, /73 и /74 в данной постановке задачи уже не являются управляемыми переменными, поскольку их значения определяются не решениями менеджера, а установленными значениями цен Ц1, Ц2, ЦЗ и Ц4 по формулам (7.5).

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

(ЦМ 520)/71 +(Ц2-'\400)П2+(ЦЗ-Ш0)ПЗ+(Ц4-\680)/74 -> max

Подставив в полученное выражение значения переменных, выражающих спрос (П1, П2, ПЗ и П4), определяемые в соответствие с формулами (7.5), получим

(ЦМ 520) (300-0,106*Ц1)+(Ц2-'\400) (325-0,150*Ц2)+

+(ЦЗ-1800) (310-0,1 ЪЗ,ЦЗ)+(Ц4-‘\ 680) (280-0,123*Ц4)=

=-0,106(Ш)2+461,12*Ш-0,15(Ц2)2+535*Ц2-0,133 (ЦЗ)2+ +549,4*ЦЗ-0,123(Ц4)2+486,64*Ц4-1939400.

Нетрудно заметить, что полученная целевая функция не является линейной относительно независимых (оптимизируемых) переменных Ц1, Ц2, ЦЗ и Ц4, поскольку они встречаются в ней во второй степени.

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

Pi=I */71+1 */72+1 */73+1 */74 bgcolor=white>Объем производства П1 4 11,99999964 $С$4 Объем производства П2 2 -1,999997391 $D$4 Объем производства ПЗ 6,9 0 $Е$4 Объем производства П4 1 0 Ограничения Ячейка Имя Результ.

значение Множитель

Лагранжа $F$8 Ресурс 1 Требуется: 13,9 0 $F$9 Ресурс 2 Требуется: 110 11,99999999 $F$10 Ресурс 3 Требуется: 64,6 0

Рис. 7.17. Отчет об устойчивости для нелинейных задач

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

Нетрудно также заметить, сравнивая данные отчеты, что значения, указанные в колонках “Редуцированная стоимость” и “Теневая цена” на Рис. 7.16 частично совпадают с величинами, содержащимися в столбцах “Нормир. Градиент” и “Множитель Лагранжа" на Рис. 7.17. При рассмотрении отчетов задач, решаемых симплекс методом, мы определили, что теневые цены ограничений вычисляют предельную стоимость дополнительной единицы ресурса, выражаемого данным ограничением, или величину улучшения целевой функции, при уменьшении имеющегося объема ресурсов данного вида на единицу. Подобная интерпретация может быть отнесена также и к множителям Лагранжа. Главное отличие теневых цен от множителей Лагранжа связано с наличием у первых из них диапазона изменения объемов имеющихся ресурсов, в пределах которого этот показатель сохраняют своё значение. Таким образом, используя симплекс метод, мы могли определить допустимое увеличение или уменьшение объема имеющихся ресурсов, в пределах которых теневая цена ограничения сохраняет своё значение. Мы смогли делать это, поскольку целевая функция и ограничения задачи были линейны, что облегчало расчет изменения целевой функции при при изменении объемов имеющихся ресурсов. При использовании нелинейных методов возможности определения допустимых изменений объемов имеющихся ресурсов отсутствуют. Поэтому в таких случаях мы не можем указать диапазон изменения объемов имеющихся ресурсов, в пределах которого множители Лагранжа для каждого ограничения сохраняют своё значение. Множители Лагранжа, таким образом, могут использоваться только для приблизительной оценки влияния на целевую функцию единичных изменений объема имеющихся ресурсов по каждому из ограничений.

Как уже было замечено при решении линейных задач, редуцированная стоимость переменной, показывающая расположение решения относительно верхней и нижней границ, определяет прирост (сокращение) целевой функции при допустимом увеличении этой переменной на единицу. Подобная интерпретация, но в несколько более приближенном смысле, может быть дана показателю “Нормир. градиент” (Reduced gradient). Действительно, ненулевое значение нормированного градиента выражает влияние на целевую функцию малых изменений данной переменной. Так, например, увеличение объема производства продукции второго вида П2 на единицу уменьшает значение целевой функции на две единицы, о чем говорит соответствующее значение редуцированных затрат (Рис. 7.12) и нормированного градиента (Рис. 7.13).

На Рис. 7.18 и 7.19 приведены отчеты по пределам и устойчивости для полученного оптимального решения нелинейной задачи определения цен на производимую продукцию (см. Табл. 7.24).

Microsoft Excel 5.0 Отчет по пределен

Ячейка

$G$9

Целевое

имя

Общая прибыль:

Значение

84 336 р.

Ячейка Изменяемое

имя

Значение Низший

предел

Целевой

результат

Верхний

предел

Целевой

результат

$В$3 Цены П1 2 223 р. 2 223 р. 84 336 р. 2 500 р. 73 392 р.
$с$з Цены П2 1 849 р. 1 849 р. 84 336 р. 2167 р. 62 943 р
$D$3 Цены ПЗ 2195 р. 2195 р. 84 336 р. 2 331 р. 77 215 р.
$Е*3 Цены П4 2 032 р. 2 032 р. 84 336 р. 2 276 р. 73 758 р.
Рис. 7.18. Отчет по пределам для решения нелинейной задачи определения цен

Ячейка Имя Рездльт.

значение

Норммр.

градиент

$Б$3 Цеі-«=.і П1 2 223 р. 0 р.
$с$з Цены П2 1 849 р. 0 р.
*D$3 Uehft=I ПЗ 2 135 D. о р.
ІЕ$3 Uehft=I П4 2 032 р. _
граничения
Ячейка Имя ResgnbT.

значение

Множитель

Лагранжа

$G$11 РеСЧРС 1 Требуется: 1Є0,0000001 131.5323215
Ресурс 2 Требуется; 984.8635098 0
$В$7 Ресурс 3 Требуется: Спрос П1 636.2122386

64.33

0

0.00

$С$7 Спрос П2 47.Є4 0,00
$D$7 Спрос ПЗ 18.01 0,00
*Е$7 Спрос П4 30.02 0,00
Microsoft Excel 5.0 Отчет по дстомчнвосты

Исменяемые ячейки______________________________________

Рис. 7.19. Отчет по устойчивости для решения нелинейной задачи определения цен

class="lazyload" data-src="/files/uch_group42/uch_pgroup33/uch_uch6536/image/134.jpg">

Команда ПОИСК РЕШЕНИЯ меню СЕРВИС предлагает пользователю ряд опций для контроля за решением нелинейных моделей, которые находятся в нижней части диалогового окна Параметры поиска решения (см. Рис. 7.20). Таких опций три: Оценка, Производные и Метод. Выбранные по умолчанию значения этих опций обеспечивают устойчивую работу ЭТ во многих случаях. Однако, если при решении не линейных моделей у Вас возникают проблемы, Вы можете изменить стратегию поиска оптимального решения.

Опция Оценка определяет способ оценки управляемых переменных в процессе улучшения решения. Используемое по умолчанию значение этой опции Линейная оценивает переменные с использованием техники линейной экстраполяции. Второе значение опции - Квадратичная - использует технику нелинейной экстраполяции.

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

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

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

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

ЗАМЕЧАНИЕ. Команда РЕШИТЬ УРАВНЕНИЕ меню СЕРВИС дает также возможность решать задачу “Как сделать, чтобы ?” для наибЬ- лее общего ее случая. Задав величину целевой функции в диалоговом окне ПОИСК РЕШЕНИЯ, Вы можете найти значения независимых переменных, обеспечивающих её получение при соблюдении введенных Вами ограничений.

НОВЫЕ ПОНЯТИЯ И ТЕРМИНЫ

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ

1. Перечислите основные задачи моделирования, решаемые в среде электронной таблицы

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

3. Какие возможности предоставляет пользователю электронная таблица Excel 5.0 для решения задачи анализа чувствительности ?

4. Какие возможности предоставляет пользователю электронная таблица Excel 5.0 для решения задачи “Как сделать, чтобы ?”

5. Какие задачи называют оптимизационными ?

6. Какие возможности предоставляются пользователю для решения оптимизационных задач в среде электронной таблицы Excel 5.0?

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

8. В чем отличие линейных и нелинейных оптимизационных задач ?

9. Какую информацию содержат отчеты, выдаваемые по решению нелинейной задачи.

10. В чем особенности решения линейных целочисленных задач ?

<< | >>
Источник: Матвеев Л. А.. Компьютерная поддержка решений: Учебник — СПб:1998.—472 с.. 1998

Еще по теме РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В ЭЛЕКТРОННОЙ ТАБЛИЦЕ EXCEL 5.0:

  1. 2.6.2.7 ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ АКТИВАМИ
  2. 4.3 Технология решения оптимизационных задач
  3. УСЛУГИ БАНКА КАК ИНСТРУМЕНТАРИЙ РЕШЕНИЯ БИЗНЕС-ЗАДАЧ КЛИЕНТОВ
  4. Примеры решения бизнес-задач страхования валютных сделок для клиентов банка
  5. 2.1. Место функций поддержки принятия решений в задаче управления банком
  6. Глава 4. Примеры решения прикладных задач финансового планирования
  7. Приложение 1 Краткий практикум кредитной арифметики с применением Excel
  8. Федеральный бюджет и его роль в решении общегосударственных задач
  9. 7.6. Практическая часть 7.6.1. Задачи для самостоятельного решения
  10. РАЗДЕЛ 3. ПОДДЕРЖКА ПРИНЯТИЯ РЕШЕНИЙ СРЕДСТВАМИ ЭЛЕКТРОННОЙ ТАБЛИЦЫ