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

1000л:, + 1200*2 + 1400*3 + 800*4 > 100 ООО.

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

400*, + 600*2 + 840л:3 + 450х* 200 000

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

хО, х2>0, xt>0, xt>0.

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

*, + 1,2х2 + 1,4*3 + °>8х4 100, 0,4*, + 0,6*2 + 0,84*з + °.45*4 < 200.

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

На рис. 2.20 представлено оптимальное решение для построенной модели. Отметим, что обычная задача линейного программирования не предполагает целочисленного решения. Поэтому мы получили значения *, = 339,15, *4 = 1,70 и *2 = *3 = 0. Мы можем округлить полученные значения, тогда *, = 339 и *4 = 2 (эти значения в данном случае совпадут с оптимальным решением задачи целочисленного линейного программирования).

Оптимальное решение не рекомендует строить домики на две и три семьи, несмотря на то что доходность этих домиков (12 000 и 15 000 долл.) выше, чем домиков, рассчитанных на одну семью. Этот результат показывает, что только по коэффициентам целевой функции нельзя судить о рентабельности отдельных видов экономической деятельности, которым соответствуют данные коэффициенты. Следует учитывать также стоимость ресурсов, необходимых для осуществления такой деятельности. Это тот фактор, который выражается приведенной стоимостью. Приведенные стоимости для домиков на две и три семьи составляют 3012,47 и 5024,94 долл. соответственно. Это означает, что для того, чтобы такие домики были рентабельными, необходимо либо на величины приведенных стоимостей уменьшить стоимость ресурсов, необходимых для их строительства и эксплуатации, либо на такую же величину увеличить их доходность.

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

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

LINEAR PROGRAMMING OUTPUT SUMMARY

Title: Land Use Model, Example 2.5-2 Final Iteration No.: 8 Objective Value = 3391521.2

Рис. 2.20. Выходной отчет программы TORA для модели использования земли

В третьем ограничении двойственная цена равна -24,94 долл. (если точно, то -4,9377 долл.), поэтому любое увеличение этого ресурса приведет к снижению общего дохода. Но почему так происходит? Чтобы ответить на этот вопрос, нужно знать, сколько единиц этого ресурса содержится в данном ограничении. Рассмотрим это ограничение подробнее.

200xt-xx - 2х2- Зл-3 >0.

Неравенство показывает, что минимальная площадь рекреационной зоны зависит от количества домиков. В такой записи единицы измерения левой части неравенства не видны. Поэтому мы разделим все неравенство на 200, в результате получим

х4 - (0,005л-, + 0,01л-2 + 0,015л-3) > 0.

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

неравенства (т.е. возрастание от 0 до 1) можно интерпретировать как увеличение на один акр площади рекреационной зоны. На основании такого представления ограничения можно сказать, что двойственная цена соответствует стоимости увеличения на акр рекреационной зоны. Но новая запись ограничения показывает, что двойственная цена должна быть равной 200 х (-24,9377) = -4987,54 долл. (Повторив расчеты программы TORA при такой записи третьего ограничения, вы должны получить именно такую величину двойственной цены - проверьте это!)

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

Пример 2.5.3. Расписание движения автобусов

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

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

Нетрудно заметить, что такое определение переменных неоднозначно. Мы знаем, что каждый автобус должен отработать 8-часовую смену, но мы не знаем, когда эта смена должна начинаться. Если следовать схеме обычной 3-сменной работы (1-я смена с8:01 до 16:00, 2-я - с 16:01 до 24:00 и 3-я - с 00:01 до 8:00) и обозначить через х2 и.т3 количество автобусов, работающих на линии в эти смены, тогда, исходя из транспортных потребностей (рис. 2.21), получаем х, > 10, х2 > 12 и х3 > 8, а общее количество ежедневно используемых автобусов составляетхх + х2 + х3 = 10 + 12 + 8 = 30. Это решение приемлемо, если смены должны начинаться так, как при обычной организации 3-сменной работы. Однако можно оптимизировать расписание движения автобусов, если поискать другое, лучшее время начала рабочих смен. Предположим, что между началом соседних смен может быть 4 часа, а не 8, как в обычной схеме 3-сменной работы. В нижней части рис. 2.21 показана такая схема организации перекрывающихся рабочих смен, согласно которой они должны начинаться в 00:01, 4:01, 8:01, 12:01, 16:01 и 20:01, при этом каждая смена продолжается 8 часов. Теперь мы готовы определить переменные: