Решение. Для решения сформулированной задачи о назначениях откроем рабочую книгу MS Excel, в которой сохранены результаты расчета маршрутов

Для решения сформулированной задачи о назначениях откроем рабочую книгу MS Excel, в которой сохранены результаты расчета маршрутов, созданных средствами Деловой карты, в процессе выполнения практического занятия №3. Изменим имя третьего листа на Оптимизация.

Сформируем допустимые маршруты. Проанализируем варианты маршрутизации, полученные средствами Деловой карты, в процессе выполнения практического занятия №3 (см. табл. 4 – 7). В соответствии с методикой Шапиро допустимые маршруты, включаемые в модель линейного программирования, должны быть неповторяющимися. Поэтому исключаем маршруты номер 48, 52 и 58 из третьего и четвертого вариантов маршрутизации, которые повторяют маршруты, соответственно 29, 17 и 6 из второго и первого вариантов маршрутизации. Окончательно мы имеем набор из 64 неповторяющихся маршрутов.

Для решения задачи выполним следующие подготовительные действия.

1. Внесем необходимые надписи в ячейки рабочего листа, как это изображено на рис. 20 и рис. 21. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решение рассматриваемой задачи о назначении, а служит для лучшего восприятия информации.

Рис. 20. Экранная форма задачи оптимизации маршрутов по методике Шапиро (начало)

Рис. 21. Экранная форма задачи оптимизации маршрутов по методике Шапиро (окончание)

2. В ячейки B3:BM3 введем порядковые номера маршрутов, созданных средствами Деловой карты.

3. В ячейки B7:BM7 введем номера машин, которые используются для обслуживания заказов в каждом из вариантов маршрутизации.

4. В ячейки B9:BM9 введем марку/тип подвижного состава, который используется для обслуживания заказов в каждом из вариантов маршрутизации.

5. В ячейки B11:BM11 введем значения затраты на аренду автомобиля, руб./ч, на каждом маршруте.

6. В ячейки B12:BM91 введем значения коэффициентов , равные 1, если заказ обслуживается данным маршрутом и равные 0 – в противном случае.

7. В ячейки B94:BM94 введем время работы автомобилей на соответствующих маршрутах. Значения, содержащиеся в ячейках B94:BM94 должны быть заданы в формате времени.

8. В ячейку B95 введем формулу: =B94*24, которая позволяет преобразовать время в десятичный формат, и распространим эту формулу на весь диапазон ячеек B95:BM95, содержащих значение времени.

9. Рассчитаем величину затрат на каждом маршруте, т.е. значения коэффициентов . Для чего в ячейку B96 введем формулу: =ЕСЛИ(B95>4;B11*ОКРУГЛВВЕРХ(B95;0);B11*4) и распространим ее на весь диапазон ячеек B96:BM96, содержащих значения коэффициентов . В этой формуле отражено то, что заказчик (компания ЭКЗ «Лебедянский») должен оплатить перевозчику первые четыре часа работы на маршруте не зависимо от того сколько времени перевозчик отработал. В том случае, если время работы превышает четыре часа, то округленное вверх фактическое время работы умножается на тариф.

10. В ячейку B99 введем целевую функцию (5) в виде формулы: =СУММПРОИЗВ(B96:BM96;B97:BM97).

11. В ячейку BN12 введем формулу: =СУММПРОИЗВ (B71:BM71;$B$97:$BM$97), которая представляет собой первое ограничение в системе (6).

12. Скопируем формулу, введенную в ячейку BN12, в ячейки BN13:BN91.

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

Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис→Поиск решения.

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $B$99.

2. Для группы Равной: выбрать вариант поиска решения - минимальному значению.

3. В поле с именем Изменяя ячейки: ввести абсолютный адрес диапазона ячеек $B$97:$BN$97.

4. Задать первую группу ограничений (6). С этой целью выполнить следующие действия:

- в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

- в появившемся дополнительном окне выбрать диапазон ячеек $BN$12:$BN$91, который должен отобразиться в поле с именем Ссылка на ячейку;

- в качестве знака ограничения из выпадающего списка выбрать равенство;

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

- для добавления первой группы ограничений в дополнительном окне нажать кнопку с надписью Добавить.

5. Задать ограничения на булевы значения переменных задачи. С этой целью выполнить следующие действия:

- в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

- в появившемся дополнительном окне выбрать диапазон ячеек $B$97:$BM$97, который должен отобразиться в поле с именем Ссылка на ячейку;

- в качестве знака ограничения из выпадающего списка выбрать строку «двоичн»;

- в качестве значения правой части ограничения в поле с именем Ограничение: оставить без изменения вставленное программой значение «двоичное»;

- для добавления ограничения в дополнительном окне нажать кнопку с надписью Добавить.

6. В окне дополнительных параметров поиска решения выбрать отметки Линейная модель и Неотрицательные значения.

Общий вид диалогового окна спецификации параметров мастера поиска решения представлен на рис. 22.

Рис. 22. Окно Поиск решения с введенными ограничениями

После задания ограничений и целевой функции можно приступить к поиску численного решения, для чего следует нажать кнопку Выполнить. Результат выполнения расчетов программой MS Excel представлен на рис. 23. На рис. 23 видно, что в строку Выбор маршрута () заносятся значения переменной , которая и является результатом решения данной задачи.

Рис. 23. Результат решения задачи оптимизации маршрутов по методике Шапиро (фрагмент)

Экранная форма представления результатов расчетов не очень удобна ввиду большого размера таблицы. Поэтому в табл. 8 сведены результаты решения данной задачи. Здесь мы видим, что в оптимальный вариант включены 16 маршрутов, причем 13 из них представляют второе возможное решение задачи маршрутизации, к которым добавляется маршрут номер 6 из первого возможного решения задачи маршрутизации и маршруты номер 56 и 63 из четвертого возможного решения задачи маршрутизации.

Таблица 8

Оптимальное решение задачи маршрутизации

№ маршрута	Порядок обслуживания заказов	Автомобиль	Обслужено заказов	Доставлено, кг	Время маршрута, ч	Затраты, руб.
	0-56-13-0	Газель			1,70
	0-21-4-3-65-66-48-0	Газель			4,82
	0-19-2-20-0	Газель			2,00
	0-31-29-28-9-11-7-26-0	Газель			4,57
	0-23-69-64-70-63-22-0	Газель			3,65
	0-73-72-64-62-67-68-61-0	Газель			4,92
	0-30-44-47-37-39-55-54-60-1-0	Газель			6,82
	0-52-33-36-42-34-0	Газель			4,52
	0-8-27-57-14-59-15-58-51-50-38-43-10-0	MB			8,87
	0-24-40-35-12-41-0	ЗИЛ			4,72
	0-46-45-0	ЗИЛ			3,40
	0-5-25-53-0	ЗИЛ			3,75
	0-16-71-0	20-фут.			3,37
	0-49-32-0	40-фут.			4,92
	0-18-17-6-0	Газель			3,17
	0-78-77-79-76-75-74-80-0	ЗИЛ			5,57
Сумма			70,73

Вывод. В оптимальном варианте затраты на транспортировку составят 21610 руб., это на 770 рублей меньше того, что дает четвертое возможное решение задачи маршрутизации (см. табл. 7). Таким образом, по сравнению с лучшим вариантом доставки, рассчитанным средствами Деловой карты, удалось сократить транспортные затраты приблизительно на 3,5%.