Задача о минимизации пробега автомобилей
Фирма, занимающаяся перевозкой грузов на собственных автомобилях КамАЗ, обслуживает своих клиентов в центральных городах России. Клиенты могут заказать фирме доставку груза из любого населенного пункта в любой город. После доставки КамАЗы ждут распоряжений диспетчера о выполнении следующей заявки в том городе, куда был доставлен груз.
В настоящий момент 4 порожних автомобиля ждут распоряжений диспетчера в Иваново, 3 автомобиля — в Костроме, 6 машин — в Орле и одна — в Калуге. Одновременно диспетчеру поступили заявки на 5 автомобилей во Владимире, на 3 автомобиля в Санкт-Петербурге и на 6 автомобилей в Москве. Расстояния между городами известны и приведены в табл. 7.9.
Табл. 7.9.
| Машины | Клиенты | Наличие машин | ||
| Владимир | С-Петербург | Москва | ||
| Иваново | ||||
| Кострома | ||||
| Орел | ||||
| Калуга | ||||
| Заявки (машин) |
Требуется:
1) составить такой план перегона порожних автомобилей из мест их расположения к клиентам, чтобы суммарный пробег всех автомобилей, а следовательно, и издержки фирмы были минимальными;
2) выяснить, как изменится оптимальный план, если стало известно, что в Калуге освободилась еще одна машина, а в Москве появился дополнительный заказчик.
Решение
Обозначим через хij количество машин, направляемых из i-го города к j-му клиенту. Тогда искомый план перевозок будет содержать 12 неизвестных (табл. 7.10).
Табл. 7.10.
| Машины | Клиенты | Наличие машин | ||
| Владимир | С-Петербург | Москва | ||
| Иваново | х11 | х12 | х13 | |
| Кострома | х21 | х22 | х23 | |
| Орел | х31 | х32 | х33 | |
| Калуга | х41 | х42 | х43 | |
| Заявки (машин) |
Математически задача формулируется следующим образом. Необходимо сформировать такой план (хij), при котором целевая функция Z— суммарный порожний пробег транспортных средств — будет минимальной:
Z = 119 х11 + 971 х12 + 287 х13 + 214 х21 + 1008 х22 + 324 х23 +………+135 х43 (7.16)
На искомые переменные наложены ограничения:
• По свободным машинам, ожидающим распоряжений:
х11 + х12 + х13 = 4,
х21 + х22 + х23 = 3,
х31 + х32 + х33 = 6, (7.17)
х41 + х42 + х43 = 1.
• По заявкам клиентов:
х11 + х21 + х31 + х41 = 5,
х12 + х22 + х32 + х42 = 3, (7.18)
х13 + х23 + х33 + х43 = 6.
Кроме того, переменные неотрицательны:
xij >= 0 (i=l, 2, 3, 4; j =1, 2, 3). (7.19)
Несмотря на то, что данная задача не рассматривает напрямую перевозку грузов, по структуре целевой функции и ограничений, а также способу формализации она относится к классической замкнутой транспортной задаче линейного программирования: необходимо минимизировать целевую функцию (7.16) при условии, что на переменные наложены ограничения (7.17) - (7.19).
Решение задачи в Excel приведено на рис. 7.10 - 7.12.
Рис.7.10. Табличное представление задачи в Excel
Ответы
Оптимальный план перегона автомобилей к заказчикам (рис. 7.10), следующий:
· во Владимир направляются 4 машины из Иваново и одна из Костромы;
· в С.-Петербург – 2 машины из Орла и одна из Калуги;
· в Москву – 2 машины из Костромы и 4 из орла.
При этом будет обеспечен наименьший суммарный пробег всех автомашин, который составит 5281 км.
Рис. 7.11. Окно надстройки «Поиск решения»
Если дополнительно в Калуге освободится еще одна машина, а в Москве появится еще один заказчик, то оптимальный план, полученный в п. 1, изменится (рис. 7.12). В этом случае во Владимир направляются 4 машины из Иваново и одна — из Костромы.
Рис.7.12.