Решение транспортной задачи в Excel (стр. 3 из 3)

· Затем задал следующую группу ограничений. Эти ограничения отвечают тому естественному условию, что со склада нельзя увести больше продукции, чем там имеется. Формула, помещенная в ячейку D18, имеет вид:

{=C4 - СУММ(B13:F13)}

Эта формула скопирована уже по столбцу в ячейку D19. Подготовительный этап завершен - можно вызывать Решатель.

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

Рис. 2.21. Окно Решателя при решении транспортной задачи

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

Рис. 2.22. Настройка в окне параметров Решателя при решении транспортной задачи

Осталось щелкнуть кнопку "Solve" и получить оптимальный план перевозок. Вы можете проанализировать, насколько оптимальный план отличается от равномерного распределения, предложенного в качестве первоначального варианта, и как уменьшились транспортные расходы:

Рис. 2.23. Решение транспортной задачи

Параметры, управляющие работой Решателя

Рассмотрим возможности управления работой Решателя, задаваемые в окне Параметры (Options):

· Максимальное время (MaxTime) - ограничивает время, отведенное на процесс поиска решения. По умолчанию задано 100 секунд, что обычно достаточно для задач небольшой размерности, имеющих около 10 ограничений. Для задач большой размерности придется это значение увеличивать.

· Предельное число итераций (Iterations) - еще один способ ограничения времени поиска путем задания максимального числа итераций. По умолчанию задано 100, но это число можно увеличивать до 32767. Чаще всего, если решение не получено за 100 итераций, надежд получить его при увеличении этого значения мало. Лучше попытаться изменить начальное приближение и запустить процесс поиска заново.

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

· Сходимость (Convergence) - задается десятичной дробью, меньшей единицы, позволяя остановить процесс поиска при сходимости решения к неподвижной точке, когда относительные изменения в течение последних 5 итераций не превышают заданную дробь.

· Линейная модель (Assume Linear Model) - этот флажок следует включать, когда целевая функция и ограничения - линейные функции. Эта дополнительная информация позволяет Решателю упростить процесс поиска решения.

· Неотрицательные значения (Assume Non-Negative) - этим флажком можно задать ограничения на переменные, что позволит искать решения в положительной области значений, не задавая специальных ограничений на их нижнюю границу.

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

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

· Относительная погрешность (Tolerance) - задается в процентах. Указанное значение имеет смысл только для задач с целочисленными ограничениями. Решатель в таких задачах вначале находит оптимальное не целочисленное решение, а потом пытается найти ближайшую целочисленную точку, решение в которой отличалось бы от оптимального не более чем на указанное данным параметром количество процентов. Если такая точка найдена, Решатель сообщает об успехе. При большом допуске (по умолчанию 5%) может быть потеряно лучшее целочисленное решение, правда, отличающееся от найденного Решателем в пределах допуска. Для целочисленных задач допуск имеет смысл уменьшить, что я и сделал при решении транспортной задачи. Хочу еще раз обратить внимание на эту особенность решения задач целочисленного программирования. Если значение параметра Tolerance задать большим, то Решатель может остановиться раньше времени, не найдя лучшего целочисленного решения. Если же его взять малым, то наилучшее целочисленное решение будет отличаться от оптимального нецелочисленного решения на величину большую, чем ту, которая задается параметром Tolerance. В этом случае формально решение заканчивается неуспехом, поскольку найденное решение не удовлетворяет всем требованиям. Конечно, параметр Tolerance играет служебную роль, и "умный" Решатель, найдя наилучшее целочисленное решение, должен был бы уведомлять, что решение найдено, но ограничение по Tolerance не выполнено. Этого, однако, не происходит. Мы еще столкнемся с этой ситуацией при рассмотрении следующей задачи.

· Сохранить модель (Save Model) - командная кнопка; позволяет открыть диалоговое окно, где можно указать имя сохраняемой модели. Имеет смысл использовать эту возможность, когда на рабочем листе несколько моделей, так как единственная модель запоминается автоматически.

· Загрузить модель (Load Model) - позволяет загрузить одну из сохраненных моделей.

· Есть еще несколько более специальных параметров, которыми можно управлять, варьируя процедурами, применяемыми в процессе поиска. К ним следует прибегать в тяжелых ситуациях, когда решение найти не удается.