Кутузов А.Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Excel

Подождите немного. Документ загружается.

Безнадежные долги считаются невозвратимыми, поэтому они должны вычитаться из

возможной прибыли.

Конкурентная борьба с другими финансовыми институтами вынуждает банк не менее

40% капитала помещать в сельскохозяйственные и коммерческие кредиты.

ля

содействия строительной индустрии своего региона банк планирует вложить кредиты

на покупку жилья не менее 50% от общей суммы кредитов физически лиц, на покупку

автомобилей и жилья. Банк также поддерживает государственную политику,

указывающую, что отношение безнадежных долгов ко всей сумме кредитов не

должно превышать 0,04.

Математическая модель

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

образом:

— кредиты физическим лицам,

— кредиты на покупку автомобилей,

— кредиты на покупку жилья,

— сельскохозяйственные кредиты,

— коммерческие кредиты.

Банк, естественно, желает максимизировать чистую прибыль, то есть разность между

прибылью от инвестируемых сумм и суммой невозвращенных кредитов. Поскольку

безнадежные долги считаются невозвратимыми, они вычитаются как из

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

функцию можно записать следующим образом.

Максимизировать z = 0,14

(0,9x

) + 0,13

(0,93x

) + 0,12

(0,97x

) +

+ 0,125

(0,95x

) + 0,1

(0,98x

) – 0,lx

– 0,07x

– 0,03x

– 0,05x

– 0,02x

После приведения подобных членов получаем следующий вид целевой функции:

Максимизировать z = 0,026x

+ 0,0509x

+ 0,0864x

+ 0,06875x

+ 0.078x

Рассматриваемая задача имеет пять ограничений.

Ограничение общей суммы кредитов:

+ x

≤ 12.

Ограничение на сельскохозяйственные и коммерческие кредиты:

+ x

≥ 0,14

или

+ x

≥ 4,8.

Ограничения кредитов на покупку жилья:

≥

0,5(x

+ x

Ограничения на невозвращенные кредиты:

Коммерческие 0,100 0,02

Ст

. 61 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

или

0,06x

+ 0,03x

– 0,01x

+ 0,01x

– 0,02x

≤

Условия неотрицательности:

≥

0, x

≥

0, x

≥

0, x

≥

0, x

≥

Необходимо иметь в виду еще, что все кредиты выделяются примерно в одно и то же

время. Это позволит игнорировать временной фактор в процессе размещения

капитала в различные кредиты.

Оптимальное решение сформулированной задачи линейного программирования

представлено здесь:

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

коммерческие кредиты. Среди неиспользованных типов кредитов наименее

привлекательны кредиты физическим лицам и не только из-за того, что коэффициент

при переменной x

в целевой функции наименьший (= 0,026), но и потому, что

приведенная стоимость таких кредитов наибольшая (= 0,0604) среди всех остальных.

Нормированная стоимость показывает, что «рентабельность» этой переменной

должна возрасти не менее чем на 0,0604, чтобы кредиты для физических лиц стали

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

что увеличение суммы всех кредитов на единицу (миллион долларов) приводит

увеличению чистой прибыли на 0,0864 (миллиона долларов). Это эквивалентно

8,64% годовых от суммы инвестиций.

Ст

. 62 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

Поскольку соответствующий интервал для значения правой части этого ограничения

простирается от 4,8 (= 12 – 7,2) до бесконечности, указанный процент годовых

гарантирован для любой общей суммы кредитов, превышающих 12 миллионов

долларов.

В формуле целевой функции наибольший коэффициент (0,0864) стоит перед

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

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

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

покупку жилья.

Второе ограничение данной задачи указывает нижнюю границу суммы

сельскохозяйственных и коммерческих кредитов. Отрицательная теневая цена (–

0,0084) показывает, что увеличение этой границы приведет к уменьшению чистой

прибыли банка.

Другими словами, экономически не выгодно устанавливать нижнюю границу для

суммы сельскохозяйственных и коммерческих кредитов. Это еще раз подтверждает,

как было видно при рассмотрении первого ограничения, что любые дополнительные

вложения следует помещать в кредиты на покупку жилья, а не в

сельскохозяйственные и коммерческие кредиты. Если мы вообще удалим это

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

Самостоятельная работа

Проверьте последнее утверждение раздела, удалив второе ограничение и решив

новую задачу с помощью программы Excel.

Решите задачу данного раздела с помощью пакета QSB+. Убедитесь, что

решения, полученные с помощью программы Excel и с помощью пакета QSB+,

совпадают. Сопоставьте приведенную в данном разделе информацию,

выдаваемую в отчете по устойчивости программы Excel, и информацию итогового

отчета QSB+.

2.5.3. Освоение земли

Компания владеет 800 акрами необработанной земли с живописным озером в

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

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

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

озере.

Чтобы предотвратить это, разработаны строгие ограничительные требования для

возможного дальнейшего освоения

этой территории.

Разрешается возводить домики только на одну, две или три семьи, причем доля

домиков на одну семью должна составлять не менее 50% от всех построенных.

Ограничивается количество емкостей для хранения сточных вод: минимальная

территория, отведенная для размещения одной емкости, обслуживающей один

домик на одну, две или три семьи, составляет соответственно 2, 3 и 4 акра.

Зона отдыха рассчитывается исходя из нормы — не менее одного акра на 200

семей.

Для предотвращения загрязнения озера запрещается использовать

поверхностные воды для полива и бытовых нужд.

Правление компании решило изучить возможности дальнейшего освоения тех 800

акров земли, которые ей принадлежат.

альнейшее освоение этих земель

предусматривает строительство домиков для отдыха на одну, две и три семьи.

Ст

. 63 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

Подсчитано, что необходимо отвести не менее 15% всей территории на прокладку

дорог и строительство вспомогательных сооружений. Компания планирует сдавать

домики отдыхающим и рассчитывает получить от одного домика следующую

прибыль:

Стоимость планируемой водопроводной сети пропорциональна количеству домиков,

подключенных к водопроводу. Однако власти округа настаивают на том, что

необходимо собрать не менее $100 000, чтобы этот проект был экономически

осуществимым. Кроме того, известно, что даже в пиковый период водопроводная

сеть не сможет поставить больше 200 000 галлонов воды в день. В следующей

таблице приведена стоимость подключения к водопроводной сети одного домик и

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

Математическая модель

Компания должна определить, сколько строить домиков различного типа и какова

должна быть зона отдыха, чтобы удовлетворить требованиям, сформулированным

выше. Положим:

— количество домиков на одну семью,

— количество домиков на две семьи,

— количество домиков на три семьи,

— количество акров земли, отводимых под зону отдыха.

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

функцию можно записать так:

Максимизировать z = 1000x

+ 12000x

+ 15000x

Задача имеет следующие ограничения:

Ограничение на общую площадь используемой земли.

Ограничение, связанное со строительством домиков преимущественно на одну

семью.

Ограничение, учитывающее требования к зоне отдыха.

Ограничение, связанное со строительством водопроводной сети.

Ограничение на потребление воды в пиковый период.

Эти ограничения математически будут записаны следующим образом.

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

Тип домика На одн

семью На две семьи На т

и семьи

Чистая прибыль

($)

10 000 12 000 15 000

Тип домика На одн

семью На две семьи На т

и семьи Зона отдыха

Стоимость

подключения

водопроводу

($)

1000 1200 1400 800

Потребность

в воде

(галлон/день)

400 600 840 450

Ст

. 64 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

+ 3x

+ 4x

+ 1x

≤ 680 (=0,85

800).

Ограничение, связанное со строительством домиков преимущественно на одну

семью:

0,5x

– 0,5x

≥

Ограничение, учитывающее требования к зоне отдыха:

Ограничение, связанное со строительством водопроводной сети

1000x

+ 1200x

+ 1400x

+ 800x

≥

100 000.

10.

Ограничение на потребление воды в пиковый период:

400x

+ 600x

+ 840x

+ 450x

≤ 200 000.

11.

Условия неотрицательности:

≥

0, x

≥

0, x

≥

0, x

≥

ВНИМАНИЕ

Еще на этапе формулирования математической модели следует обращать внимание на возможные

проблемы, которые могут возникнуть из-за ошибок машинного округления.

В нашей модели коэффициенты в четвертом и пятом ограничениях значительно

больше по величине, чем все остальные. Эта несоразмерность (относительная)

величин коэффициентов может привести к непредвиденным ошибкам машинного

округления и, следовательно, к неверному результату.

В нашем случае мы можем предотвратить эту потенциальную опасность путем

масштабирования коэффициентов,

ля чего все коэффициенты в четвертом и пятом

неравенствах надо разделить на 1000. После этого неравенства будут записаны

следующим образом.

+ 1,2x

+ 1,4x

+ 0,8x

≥

100,

0,4x

+ 0,6x

+ 0,84x

+ 0,45x

≤ 200.

К подобным вычислительным проблемам может привести и наличие в неравенствах

слишком малых по величине коэффициентов. В этом случае также применяется

масштабирование коэффициентов, но уже в сторону их увеличения.

ПРИМЕЧАНИЕ

Большинство программ, предназначенных для решения задач линейного программирования, пытается

согласовать величины коэффициентов еще до начала расчетов. Например, чтобы программа Excel

выполняла такое согласование, следует в окне

Параметры поиска решения

установить флажо

Автоматическое масштабирование

(см. раздел 2.4.3). Однако это не гарантирует успешного

устранения всех возникающих проблем. Поэтому все же желательно выполнять масштабирование

вручную, еще на этапе формализации модели.

Итак, оптимальное решение для построенной модели будет таким:

Ст

. 65 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

Отметим, что обычная задача линейного программирования не предполагает

целочисленного решения. Поэтому мы получили значения:

= 339,152, x

= 1,696 и x

= x

= 0.

Мы можем округлить полученные значения, тогда

= 339 и x

= 2.

Эти значения в данном случае совпадут с оптимальным решением задачи

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

Оптимальное решение не рекомендует строить домики на две и три семьи, несмотря

на то, что прибыльность этих домиков ($12 000 и $15 000) выше, чем домиков,

рассчитанных на одну семью.

ВНИМАНИЕ

Этот результат показывает, что только по коэффициентам целевой функции нельзя судить о

«рентабельности» отдельных видов экономической деятельности, которым соответствуют данные

коэффициенты. Следует учитывать также стоимость ресурсов, необходимых для осуществления такой

деятельности. Это как раз тот фактор, который учитывается нормированной стоимостью.

Нормированные стоимости для домиков на две и три семьи составляют $3012,47 и

Ст

. 66 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

$5024,94, соответственно. Это означает, что для того чтобы такие домики были

рентабельными, необходимо одно из двух:

либо на величины нормированных стоимостей уменьшить стоимость ресурсов,

необходимых для их строительства и эксплуатации;

либо на такую же величину увеличить их цену.

В ограничениях 2, 4 и 5 величины в столбце Разница имеют положительные значения,

а это указывает, что соответствующие «ресурсы» использованы не полностью. В

результате теневые цены, соответствующие этим ограничениям, равны нулю.

Теневая цена первого ограничения (на общую площадь используемой земли) равна

$4987,53. Это значит, что увеличение общей площади на один акр должно принести

$4987,53 чистой прибыли. Эту информацию можно использовать для определения

цены при покупке дополнительного земельного участка.

В третьем ограничении теневая цена равна –$25, поэтому любое увеличение этого

«ресурса» приведет к снижению общей прибыли. Но почему так происходит? Чтобы

ответить на этот вопрос, нужно знать, сколько единиц этого «ресурса» содержится в

данном ограничении.

Рассмотрим подробнее данное ограничение:

200x

– x

– 2x

– 3x

≥ 0.

Это неравенство показывает, что минимальная площадь зоны отдыха зависит от

количества домиков. В такой записи единицы измерения левой части неравенства не

видны. Поэтому мы разделим все неравенство на 200, в результате получим

– (0,005x

+ 0,01x

+ 0,015x

) ≥ 0.

Поскольку площадь зоны отдыха измеряется в акрах, то выражение в скобках также

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

неравенства (то есть возрастание от 0 до 1) можно интерпретировать как увеличение

на один акр площади зоны отдыха. На основании такого представления ограничения

можно сказать, что теневая цена соответствует стоимости увеличения на акр зоны

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

равной 200

(–25) = –$5 000. (Если повторить расчеты программы Excel при такой

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

цены — проверьте это! Это — задание для самостоятельной работы.)

Новая теневая цена свидетельствует о том, что увеличение площади зоны отдыха на

один акр приведет к уменьшению общей прибыли на $5 000. Интересно, что это

число приблизительно равно теневой цене первого ограничения, но с

противоположным знаком. Такой результат имеет экономический смысл, поскольку

перевод акра земли в зону отдыха означает исключение этого акра земли из той

площади, на которой можно построить домики, приносящие прибыль. Поэтому не

стоит удивляться, что эти величины почти одинаковы.

Самостоятельная работа

Проверьте с помощью программы Excel утверждение, сформулированное в тексте

данного раздела относительно новой записи третьего ограничения.

Решите задачу данного раздела с помощью пакета QSB+. Убедитесь, что

решения, полученные с помощью программы Excel и с помощью пакета QSB+,

совпадают. Сопоставьте приведенную в данном разделе информацию,

выдаваемую в отчете по устойчивости программы Excel, и информацию итогового

отчета QSB+.

2.5.4. Движение автобусов

Ст

. 67 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

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

автобусов, которая снизила бы загазованность в городе путем уменьшения

количества используемых автобусов.

Прежде всего, определили минимальное количество автобусов, необходимое для

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

суток требуется разное количество автобусов.

альнейшее изучение этого вопроса

позволило аппроксимировать суточную потребность в автобусах кусочно-постоянной

функцией с 4-часовыми интервалами постоянных значений, которая выглядит

следующим образом:

При решении задачи (т. е. составлении расписания движения автобуса) следует

учитывать, что каждый автобус должен находиться на линии непрерывно в течение 8

часов (одна рабочая смена).

Математическая модель

Итак, требуется определить число автобусов, выходящих на линию в определенную

смену, (переменные) так, чтобы

довлетворить минимальные потребности в

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

количество автобусов, выходящих на линию в течение суток (целевая функция).

Такое определение переменных неоднозначно. Известно, что каждый автобус должен

отработать 8-часовую смену, но мы не знаем, когда эта смена должна начинаться.

Если следовать схеме обычной 3-сменной работы (1-я смена с 8:01 до 16:00, 2-я— с

16:01 до 24:00 и 3-я— с 00:01 до 8:00) и обозначить через x

, x

и x

количество

автобусов, работающих на линии в эти смены, тогда, исходя из транспортных

потребностей получаем

≥

10, x

≥

12 и x

≥

Ст

. 68 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

а общее количество ежедневно используемых автобусов составляет

+ x

= 10 + 12 + 8 = 30.

Это решение приемлемо, если смены должны начинаться так, как при обычной

организации 3-сменной работы. Однако можно оптимизировать расписание движения

автобусов, если поискать другое, «лучшее» время начала рабочих смен.

Предположим, что между началом «соседних» смен может быть 4 часа, а не 8, как в

обычной схеме 3-сменной работы. В нижней части нашего рисунка схематично

показана такая схема организации перекрывающихся рабочих смен, когда они

должны начинаться в 00:01, 4:01, 8:01, 12:01, 16:01 и 20:01, при этом каждая смена

продолжается 8 часов. Теперь мы готовы определить переменные:

— количество автобусов, начинающих работу в 00:01,

— количество автобусов, начинающих работу в 4:01,

— количество автобусов, начинающих работу в 8:01,

— количество автобусов, начинающих работу в 12:01,

— количество автобусов, начинающих работу в 16:01,

— количество автобусов, начинающих работу в 20:01.

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

Минимизировать z = x

+ x

при выполнении условий

+ x

≥

4 (время от 00:01 до 4:00),

+ x

≥

8 (время от 4:01 до 8:00),

+ x

≥

10 (время от 8:01 до 12:00),

+ x

≥

7 (время от 12:01 до 16:00),

+ x

≥

12 (время от 16:01 до 20:00),

+ x

≥

4 (время от 20:01 до 24:00),

≥

0 j = 1,2,...,6.

Результаты решения этой задачи линейного программирования будут таковы:

Ст

. 69 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm

Отметим, что в оптимальном решении общее количество автобусов равно 26, при

этом x

= 4, x

= 10, x

= 0, x

= 8, x

= 4 и x

= 0. Нормированные стоимости всех

переменных равны нулю. Это указывает на возможность альтернативных

оптимальных решений. Действительно, нормированные стоимости, соответствующие

переменным x

и x

, равны нулю, хотя сами переменные имеют нулевые значения.

Таким образом, в оптимальном решении эти переменные могут быть увеличены на 1

без изменения целевой функции.

ПРИМЕЧАНИЕ

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

соответствующие нулевым переменным, отличны от нуля.

Интерес представляет информация о рассчитанных теневых ценах. Теневая цена,

равная 1, показывает, что увеличение правой части соответствующего неравенства

на единицу приводит к возрастанию общего количества автобусов также на единицу.

Если теневая цена равна нулю, то увеличение значения правой части

соответствующего неравенства не приводит к возрастанию общего числа

используемых автобусов.

Однако эти утверждения справедливы только тогда, когда значения правых частей

неравенств не выходят за пределы соответствующих интервалов (возможные

изменения правых частей указаны в столбцах Допустимое Увеличение и Допустимое

Уменьшение

таблицы

Ограничения

Например, правая часть второго неравенства может возрасти от 8 до 14 (= 8 + 6), без

увеличения общего количества используемых автобусов. А увеличение на какую-

либо величину правой части третьего неравенства (начиная со значения 10 и выше)

приводит к такому же увеличению общего количества автобусов. Эта информация

Ст

. 70 из 101Шаблон для книг

(

Word 97

)

15.09.2004mk:

MSITStore:\\e

b4\New%20files\К

зов.chm::/Manual.htm