Транспортная задача
В офисной деятельности очень часто приходится анализировать варианты, стараясь найти оптимальное решение. К сожалению, математические методы оптимизации в реальной офисной практике применяются сравнительно редко. Причины этого я обсуждать здесь не буду. Наша цель другая, - показать, как решаются такие задачи. Поэтому я подробно останавливаюсь на возможностях Решателя, полагая, что это средство Excel позволяет легко и просто решать самые разные оптимизационные задачи, возникающие в ходе офисной деятельности.
Рассмотрим более серьезную оптимизационную задачу - транспортную. Вот одна из возможных содержательных постановок этой задачи:
Имеется N складов, на каждом из которых хранится готовая продукция. Пусть:
P1, P2, …PN
- объемы продукции, хранящейся на каждом складе. Пусть теперь есть M магазинов, от которых поступила заявка на завоз этой продукции:
Q1, Q2, …QM
- требуемые объемы продукции для каждого магазина. Транспортные расходы на перевозку единицы продукции из склада I в магазин J задаются матрицей:
|| TI,J || I = 1…N; J = 1…M
Требуется найти оптимальный план перевозок,- матрицу ||XI,J||, минимизирующую суммарные транспортные расходы при естественных ограничениях: все заявки магазинов должны быть удовлетворены, и со склада нельзя увезти продукции сверх того, что там имеется. В формальной постановке эта задача имеет вид:
При ограничениях:
XI,J > = 0; I = 1…N; J = 1…M;
В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов.
- В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах.
- В ячейки E5:I5 - заявки на продукцию, поступившие от магазинов.
- В ячейки B8:F9 - матрицу транспортных расходов, задающую расходы на перевозку из I-го склада в J-й магазин единицы продукции.
- В ячейки B13:F14 - план перевозок - матрицу, задающую количество товара, перевезенного из I-го склада в J-й магазин. Начальное распределение плана задано по принципу "каждой сестре по серьге", равномерно распределив всю имеющуюся на складе продукцию по магазинам. Эти ячейки являются регулируемыми и Решатель должен найти более подходящее решение, изменив значения в этих ячейках.
- В ячейку D15 - записал целевую функцию: {=СУММ(B8:F9*B13:F14)}
- В ячейки D17:H17 записал ограничения, задающие требование о точном выполнении заявки каждого магазина. Как обычно, я записал соответствующую формулу в первую из этих ячеек: {=СУММ(B13:B14) - E5}
Затем скопировал ее. При копировании формула автоматически меняется, задавая нужное ограничение. Правда, нужно следить при этом за правильной ориентацией данных. Например, в данном случае формулу нужно копировать в строку, а не в столбец. - Затем задал следующую группу ограничений. Эти ограничения отвечают тому естественному условию, что со склада нельзя увести больше продукции, чем там имеется. Формула, помещенная в ячейку D18, имеет вид: {= С4 - СУММ(B13:F13)}
Эта формула скопирована уже по столбцу в ячейку D19. Подготовительный этап завершен - можно вызывать Решатель.
При вызове Решателя и задании параметров в его диалоговом окне выполнялась стандартная работа по указанию ячейки с целевой функцией, диапазоном регулируемых ячеек и заданием ограничений. Заметьте, помимо двух групп ограничений я задал и ограничения целочисленности переменных. Предполагается, что продукция может перевозиться только целыми единицами - бочками, мешками, ящиками. Такие ограничения в Решателе создаются совсем просто, - достаточно среди операторов, связывающих левую и правую части ограничения, выбрать оператор int. Взгляните, как выглядят результаты моей работы:
увеличить изображение
Рис. 2.21. Окно Решателя при решении транспортной задачи
Прежде чем дать команду на решение задачи, я провел настройку параметров в окне Options. В частности я включил флажки, указывающие на линейность модели и положительность переменных. Кроме того, я увеличил точность решения целочисленной задачи, задав в окне Tolerance значение в 1% вместо 5%, принятых по умолчанию.
Рис. 2.22. Настройка в окне параметров Решателя при решении транспортной задачи
Осталось щелкнуть кнопку "Solve" и получить оптимальный план перевозок. Вы можете проанализировать, насколько оптимальный план отличается от равномерного распределения, предложенного в качестве первоначального варианта, и как уменьшились транспортные расходы:
увеличить изображение
Рис. 2.23. Решение транспортной задачи