Кутузов А.Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Excel
Подождите немного. Документ загружается.
программирования следует установить два флажка:
Линейная модель
—
д
ля ускорения поиска решения линейной задачи оптимизации и
получения результатов послеоптимизационного анализа;
Неотрицательные значения
— чтобы переменные были неотрицательны.
Нахождение решения
Вернувшись в окно Поиск решения, вы можете приступать к вычислениям. Для этого
щелкните кнопку Выполнить. Результаты вычислений появятся на рабочем листе, и
одновременно откроется окно Результаты поиска решения с сообщением о том, найдено
решение или нет.
В окне Результаты поиска решения можно выбрать следующие параметры:
Сохранить найденное решение —
д
ля сохранения найденного решения на рабочем
листе.
Восстановить исходные значения
—
д
ля восстановления исходного вида рабочего
листа.
Тип отчета
— для выдачи на отдельных рабочих листах отчетов, содержащих
анализ полученных результатов. В списке можно выделить один или несколько
типов отчета (в случае целочисленного решения доступен лишь один из них —
Результаты). Отчет по результатам содержит ту же информацию, что и основной
рабочий лист, отчет по пределам не представляет особой ценности, поэтому в
дальнейшем подробно анализируется лишь наиболее интересный из отчетов —
по устойчивости.
В нашей задаче выберите параметр
Сохранить найденное решение, выделите в списке
тип отчета — Устойчивость и щелкните кнопку OK. В рабочей книге появится новый лист
с этим отчетом.
Анализ результатов
Результаты вычислений выглядят на рабочем листе следующим образом:
Ст
р
. 51 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
В ячейках B3:E3 выводится оптимальный производственный план, в ячейке F4 —
максимальное значение прибыли.
В строках 8–10, содержащих ограничения на ресурсы, в столбце
Лев.часть
указаны
объемы использованных ресурсов, а в столбце Разница — остаток ресурсов,
оставшихся неиспользованными. Если разница равна нулю, то соответствующий
ресурс дефицитен (используется полностью), если разница положительна — то
недефицитен (не используется полностью).
В строках 9–15, содержащих граничные условия, в столбце Лев.часть указаны
значения переменных в оптимальном решении, а в столбце Разница — разность
между этими значениями и заданными для переменных верхними и нижними
границами. Если разница равна нулю, то соответствующая переменная принимает
свое минимальное или максимальное значение.
Если, задавая параметры поиска решения, вы установили в окне Параметры поиска
решения
флажок
Линейная модель
, то отчет по устойчивости будет содержать сведения о
чувствительности решения к изменениям коэффициентов целевой функции и правых
частей ограничений, как показано на следующем рисунк:.
В первой из таблиц отчета по устойчивости выводится следующая информация:
В первых двух столбцах перечислены ячейки, в которых вычисляются значения
Ст
р
. 52 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
переменных, и их имена.
В столбце
Результ. значение —
найденное оптимальное решение (5; 1,5; 3; 4).
В столбце Нормир. стоимость — двойственные оценки (0; 0; 0; 0). Такая оценка
может быть отлична от нуля только для нулевой переменной и показывает, на
какую величину в целевой функции следует изменить коэффициент этой
переменной, чтобы в оптимальном плане она приняла положительное значение
(например, насколько увеличить цену изделия, чтобы его производить стало
выгодно). Кроме того, эта оценка показывает, на какую величину ухудшится
значение целевой функции, если уйти от оптимального плана, добавив в него
единицу соответствующей продукции.
В столбце Целевой Коэффициент — коэффициенты целевой функции.
В последних двух столбцах —
д
опустимые приращения коэффициентов целевой
функции, при которых сохраняется прежнее оптимальное решение (при этом
1E+30
означает 10
+30
, то есть фактически +
∞
).
При добавлении допустимых приращений к коэффициентам целевой функции
получаются интервалы оптимальности. В нашем примере такими интервалами будут:
для цены 1-го вида продукции — [30, +
∞
),
для цены 2-го вида продукции — [0, 140],
для цены 3-го вида продукции — [30, +
∞
),
для цены 4-го вида продукции — [60, +
∞
).
Во второй таблице отчета по устойчивости выводится следующая информация:
В первых двух столбцах перечислены ячейки, в которых вычисляются левые
части ограничений, и их имена.
В столбце Результ. значение — значения левых частей ограничений (
д
ля
ограничений на ресурсы — их использованное количество, для граничных
условий — значение переменных в оптимальном плане).
В столбце
Теневая Цена
— теневые цены — двойственные оценки, показывающие,
на какую величину изменится целевая функция при увеличении на единицу
правой части ограничения или граничного условия, тогда как остальные данные
неизменны (в частности при добавлении единицы соответствующего ресурса).
ПРИМЕЧАНИЕ
Теневая цена — это максимальная цена, которую стоит платить за дополнительное количество
дефицитного ресурса, чтобы его приобретение было выгодным.
В столбце Ограничение Правая часть — правые части ограничений (запасы ресурсов
или граничные значения переменных).
В последних двух столбцах —
д
опустимые приращения правых частей
ограничений (запасов ресурсов или граничных значений переменных), при
которых неизменны соответствующие теневые цены и в оптимальном решении
сохраняется прежний набор ненулевых переменных (ассортимент продукции).
При добавлении допустимых приращений к правым частям ограничений получаются
интервалы осуществимости (устойчивости). В нашем примере такими интервалами
будут:
для трудовых ресурсов — [18, 20,6],
для сырья — [72, +
∞
),
Ст
р
. 53 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
для финансов — [94,5, +
∞
).
После анализа результатов, можно изменить исходные данные на рабочем листе и
повторить вычисления. При этом не понадобится повторно вводить ограничения или
изменять параметры решения: достаточно лишь выбрать в меню Сервис команду Поиск
решения
и в открывшемся окне нажать кнопку
Выполнить
. Вся информация, заданная в
окне Поиск решения, постоянно хранится вмести с рабочим листом, к которому она
относится. Не пропадет эта информация и при сохранении рабочей книги на диске.
Самостоятельная работа
Как и в предыдущей самостоятельной работе, мы предлагаем вам повторить
решение примера 2.4.1 на своем компьютере, но теперь уже с помощью программы
Excel. Получите отчет по устойчивости и проанализируйте его, сравните с итоговым
отчетом пакета QSB+. «Повторение — мать учения», — гласит народная мудрость.
2.4.4. Целочисленное решение с помощью пакетов QSB+ и QS
В предыдущих разделах мы получили для нашего примера нецелочисленное
решение, а именно (5; 1,5; 3, 4).
Если решение задачи линейного программирования должно выражаться в целых
числах (например, если речь идет о производстве автомобилей, станков, вагонов
и т. п.), то это задача целочисленного линейного программирования.
Давайте получим теперь целочисленное решение для нашего примера. Для чего
воспользуемся программой целочисленного линейного программирования, входящей
в пакеты QSB+ и QS. Для ее запуска выберите в меню программ п. 2 (целочисленное
линейное программирование), если работаете в QSB+ (см. раздел 2.4.2), или
аналогичный по названию п. 3 при работе в QS.
В появившемся меню функций можно выбрать ввод новой задачи (п. 2). Если ранее,
решая задачу линейного программирования в нецелочисленном виде, вы сохранили
ее на диске, то теперь можете загрузить ее для целочисленного решения (выберите
для этого п. 3).
Задание условий целочисленности
Задание параметров поиска решения и ввод числовых данных при целочисленном
решении происходят точно так же, как и для обычной задачи линейного
программирования (см. раздел 2.4.2). Однако теперь при задании граничных условий
можно указать в угловых скобках вид переменной:
c
— непрерывная (continuous);
i
— целая (integer);
b
— двоичная, то есть 0 или 1 (binary).
Продолжая решение нашего примера, внесем изменения только в граничные условия
задачи. Для этого в меню функций выберем п. 7 (изменение задачи), а затем в
открывшемся меню изменения задачи — п. 8 (изменение границ и целочисленности).
Вначале программа предложит задать имя новой, измененной задачи. Введите для
нашего примера прежнее имя
Production
. Откроется уже знакомая вам страница для
ввода граничных условий. Укажите в угловых скобках, что все переменные
целочисленны, как показано на рисунке:
Ст
р
. 54 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Нахождение решения
Вернувшись в меню изменения задачи, выберите п. C, чтобы выйти в меню функций.
В нем выберите п. 5 (решение задачи), что приведет к появлению меню решения,
которое несколько отличается от аналогичного меню, рассмотренного в предыдущем
разделе. Оно выглядит следующим образом:
В этом меню можно выбрать следующие варианты:
1.
Решение без вывода каких-либо итераций.
2.
Решение с выводом всех итераций.
3.
Решение с выводом первой итерации.
4.
Задание допуска на отклонение от оптимального решения (по умолчанию 0,01).
5.
Выбор варианта метода ветвей и границ.
6.
Возврат в меню функций.
Выберем п. 1 (Решение без вывода каких-либо итераций). В нижней строке появится
сообщение, что решение найдено:
The optimal solution has been found.
На следующей странице вы увидите меню результатов, которое можно впоследствии
вызывать и из меню функций, выбрав в нем п. 8 (ввод новой задачи).
В этом меню можно выбрать один из следующих вариантов действий:
1.
Вывод результата.
2.
Печать результата.
Ст
р
. 55 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
3.
Сохранение результата в ASCII-файле.
4.
Возврат в меню функций.
Выбрав п. 1 данного меню, вы увидите следующий результат:
Здесь для каждой переменной приводятся ее целое значение и коэффициент в
целевой функции. В нижней же строке указаны:
значение целевой функции (Miximized OBJ = 1300);
число выполненных итераций;
время работы процессора;
использованный вариант метода ветвей и границ;
допуск на отклонение от оптимального решения;
максимальный номер вершины в методе ветвей и границ.
После просмотра результатов вы вернетесь в меню функций, где можно проделать
следующее:
выбрав п. 7 (изменение задачи), можно изменить условия текущей задачи;
выбрав п. 2 (ввод новой задачи), можно ввести новую задачу;
выбрав п. 9 (выход в меню программ), можно выйти из программы;
выбрав п. 10 (выход из QSB+ (или QS)), можно выйти из пакета.
Самостоятельная работа
Получите целочисленное решение примера 2.4.1 на своем компьютере с помощью
пакета прикладных программ QSB+.
2.4.5. Целочисленное решение с помощью программы Excel
Давайте попробуем получить целочисленное решение для нашего примера (задача
производственного планирования — см
. раздел 2.4.1) теперь уже с помощью
программы Excel. Ранее мы получили нецелочисленное решение — (5; 1,5; 3, 4).
Чтобы получить целочисленное решение задачи линейного программирования с
помощью программы Excel, достаточно добавить к обычным ограничениям задачи
еще одно — требование целочисленности переменных. Это можно сделать в окне
Добавление ограничения, которое для нашего примера будет выглядеть следующим
образом:
Ст
р
. 56 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Остальные ограничения и параметры решения — те же, что и для обычной задачи
линейного программирования.
Выполнив вычисления, вы получим целочисленное решение (5; 1; 3, 4).
Аналогично с помощью окна Добавление ограничения можно потребовать, чтобы
переменные были булевыми, то есть принимали только двоичные значения 0 или 1.
Для этого в раскрывающемся списке следует выбрать пункт двоич.
Самостоятельная работа
Получите целочисленное решение примера 2.4.1 на своем компьютере с помощью
программы Excel.
2.5. Примеры решения задач линейного
программирования на компьютере
Графический метод, описанный в разделе 2.2, основывается на некоторых
фундаментальных свойствах оптимального решения задач линейного
программирования. Однако на практике, где типичная задача линейного
программирования содержит сотни и даже тысячи переменных и ограничений,
графический метод неприменим. Здесь требуется использование компьютерных
программ.
В этом разделе мы рассмотрим сначала, как получить решение на компьютере для
относительно простой модели (производство краски), которая ранее была решена
графически. Только после этого попробуем исследовать несколько реалистических
моделей линейного программирования, в которых определение переменных и
построение целевой функции и ограничений не так однозначно как в моделях с двумя
переменными.
Использование программы Excel или пакетов QSB+ и QS позволяет получить и
интерпретировать результаты решения этих задач.
2.5.1. Производстве краски
Вспомним неоднократно исследованную ранее задачу из раздела 2.1. На ее примере
проиллюстрируем результаты, полученные с помощью программы Excel.
Математическая модель
В этой задаче было необходимо определить ежедневные объемы производства
краски для внутренних и наружных работ, обозначенные как переменные модели:
x
1
— ежедневный объем производства краски для наружных работ;
x
2
— ежедневный объем производства краски для внутренних работ.
Используя эти обозначения, мы построили целевую функцию и ограничения модели.
Окончательно задача была сформулирована следующим образом:
Ст
р
. 57 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Максимизировать z = 5x
1
+ 4x
2
при выполнении ограничений
6x
1
+ 4x
2
≤
24,
1x
1
+ 2x
2
≤
6,
– x
1
+ x
2
≤
1,
x
2
≤
2,
x
1
≥
0, x
2
≥
0.
Решение этой задачи, выполненное программой Excel, будет выглядеть следующим
образом:
Ст
р
. 58 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Выходные результаты программы выводятся на рабочем листе Excel, содержащем
табличное представление нашей модели, и в отчете по устойчивости, создаваемом
программой. На рабочем листе с моделью представлены оптимальные значения
переменных и значение целевой функции.
В рассматриваемом примере оптимальное значение переменной х
1
(количество
выпускаемой краски для наружных работ) равно 3 т, а переменной х
2
(количество
выпускаемой краски для внутренних работ) — 1,5 т. Соответственно, прибыль
составляет $21 000.
На том же листе показаны значения дополнительных переменных в столбце Остаток.
В данной задаче нет ограничений типа «≥», поэтому все дополнительные
переменные являются остаточными. Из таблицы видно, что значения
дополнительных переменных для первых двух неравенств равны нулю. Это означает,
что сырье Ml и М2 потребляется полностью, без остатка. В третьем и четвертом
ограничениях значения дополнительных переменных отличны от нуля, то есть
неравенства этих ограничений выполняются строго.
В отчете по устойчивости в двух таблицах показаны результаты анализа
чувствительности при изменении по отдельности коэффициентов целевой функции
(таблица Изменяемые ячейки) и значений правых частей неравенств ограничений
(таблица
Ограничения
). Например, текущее оптимальное решение сохраняется до тех
пор, пока прибыль на тонну краски для внешних работ составляет от
$2000 (= 5 тыс. – 3 тыс.) до $6000 (= 5 тыс. + 1 тыс.).
Структура решения (номера ненулевых переменных) и теневая цена не изменяются,
если ежедневные поступления сырья Ml будут находиться в пределах от 20 (= 24 – 4)
до 36 (= 24 + 12) тонн. Такой же результат получен графическим способом в разделе
2.3.2.
Вариации коэффициентов целевой функции в определенных пределах (точнее, в тех
пределах, которые не приводят к перемещению точки оптимального решения) не
вызывают изменения оптимальных значений переменных x
1
и x
2
, а изменяют только
значение самой целевой функции. Но изменение правых частей ограничений-
неравенств приводит к изменению как оптимальных значений переменных x
1
и x
2
, та
к
и значения целевой функции (более подробно об этом сказано в разделе 2.3.2).
Теперь рассмотрим информацию, приведенную в столбцах
Норимир. стоимость и Теневая
Цена
отчета по устойчивости.
Начнем с нормированной стоимости. С точки зрения экономиста переменные в
модели линейного программирования можно рассматривать как числовые
характеристики интенсивности определенных видов деятельности (или процессов), в
результате которых потребляются ресурсы («вход» модели) в целях получения
прибыли («выход» модели). Из такой интерпретации вытекает следующее
определение:
Ст
р
. 59 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Если нормированная стоимость какого-либо процесса положительна, то отсюда
следует, что стоимость потребленных ресурсов больше возможной прибыли (все на
единицу интенсивности процесса), поэтому такой процесс экономически неприемлем.
Это обуславливает нулевое значение соответствующей переменной в оптимальном
решении.
Если же экономически привлекательный процесс имеет нулевую нормированную
стоимость, то это означает, что достигнута точка равновесия, когда
«выход» (единичная прибыль) равен «входу» (единичной стоимости ресурсов). В
оптимальном решении обе переменные х
1
и х
2
имеют положительные значения и
нулевые нормированные стоимости.
Теперь рассмотрим определение теневой цены. Теневая цена — это просто еще
одно название стоимости единицы ресурсов. Она равна вкладу, который привносит в
значение целевой функции изменение на одну единицу лимита, определяющего
доступность ресурса. Хотя название «стоимость единицы ресурсов», введенное в
ранее, лучше отображает смысл, вкладываемый в это понятие, мы все же будем
использовать термин «теневая цена», так как он применяется во многих
коммерческих программах решения задач линейного программирования.
На последнем рисунке, представляющем отчет по устойчивости, видно, что теневые
цены для сырья Ml и М2 равны соответственно 0,75 и 0,5 (то есть $750 и $500) за
тонну. Такие же результаты получены графическим способом в разделе 2.3.2 и
справедливы только при условии, что 20 ≤ М
1
≤ 36 и 4 ≤ M
2
≤ 20/3 (здесь через М
1
и
M
2
обозначено количество материалов Ml и М2 соответственно). Отсюда следует, что
если, например, доступное количество сырья Ml возрастет от текущего уровня в 24 т
до 28 т, тогда оптимальное значение целевой функции увеличится на $750
×
(28 –
24) = $3000.
Теневые цены для третьего и четвертого ограничений в данной модели равны нулю
при изменении значений правых частей этих неравенств от –1,5 (= 1 – 2,5) до
∞
и от
1,5 (= 2 – 0,5) до
∞
соответственно. Это означает, что ограничения, накладываемые
рынком на структуру производства (ограничение на производство краски для
внутренних работ до 2 т и т. п.), в данной ситуации не оказывают влияния на
оптимальное решение.
Самостоятельная работа
Решите задачу данного раздела с помощью пакета QSB+. Убедитесь, что решения,
полученные с помощью программы Excel и с помощью пакета QSB+, совпадают.
Сопоставьте приведенную в данном разделе информацию, выдаваемую в отчете по
устойчивости программы Excel, и информацию итогового отчета QSB+.
2.5.2. Предоставление кредитов
Банк, предоставляющий полный набор банковских услуг, находится в процессе
формирования портфеля кредитов объемом 12 миллионов долларов. Возможные
типы банковских кредитов представлены в следующей таблице:
Тип кредита Ставка процента Вероятность
безнадежных долгов
Кредиты физическим
лицам
0,140 0,10
Кредиты на покупку
автомобилей
0,130 0,07
Кредиты на покупку
жилья
0,120 0,03
Сельскохозяйственные 0,125 0,05
Ст
р
. 60 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm