Задача о минимизации пробега автомобилей

 

Фирма, занимающаяся перевозкой грузов на собственных автомобилях КамАЗ, обслуживает своих клиентов в центральных городах России. Клиенты могут заказать фирме доставку груза из любого населенного пункта в любой город. После доставки КамАЗы ждут распоряжений диспетчера о выполнении следующей заявки в том городе, куда был доставлен груз.

В настоящий момент 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 х₁₁ + 971 х₁₂ + 287 х₁₃ + 214 х₂₁ + 1008 х₂₂ + 324 х₂₃ +………+135 х₄₃ (7.16)

 

На искомые переменные наложены ограничения:

• По свободным машинам, ожидающим распоряжений:

х₁₁ + х₁₂ + х₁₃ = 4,

х₂₁ + х₂₂ + х₂₃ = 3,

х₃₁ + х₃₂ + х₃₃ = 6, (7.17)

х₄₁ + х₄₂ + х₄₃ = 1.

• По заявкам клиентов:

х₁₁ + х₂₁ + х₃₁ + х₄₁ = 5,

х₁₂ + х₂₂ + х₃₂ + х₄₂ = 3, (7.18)

х₁₃ + х₂₃ + х₃₃ + х₄₃ = 6.

Кроме того, переменные неотрицательны:

x_ij >= 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.