Задача про розвезення вантажу

Змістовна постановка задачі. Нехай деяка центральна база постачає продукцію (її можна вважати однорідною) на т складів. Розвезення продукції на склади здійснюються однією вантажівкою, причому кожний склад одержує своє замовлення в один прийом - вантажопідйомність вантажівки для цього достатня. Вантажівка може одночасно взяти вантаж, що відповідає не більше ніж к замовленням. Вантажівка може об'їжджати склади за визначеними г маршрутами. Один і той самий І склад може знаходитися на різних маршрутах.

Нехай для кожного складу відома функція витрат залежно, наприклад, від розміру замовлення. Потрібно скласти графік перевезень, що забезпечує всіх клієнтів і мінімізує сумарні витрати. Час доставки не враховується. Передбачається, що всі операції з доставки гарантовані й можуть бути здійснені протягом деякого періоду часу, що влаштовує всіх споживачів.

Під способом розвезення будемо розуміти будь-яку припустиму комбінацію виконання замовлень. Вона являє собою m-мірний стовпець», 1-й компонент якого дорівнює одиниці, якщо і-й замовлення в цьому способі задовольняється, і нулю - у противному разі. Для будь-якої реальної задачі при невеликих значеннях т, к і г можна фактично виписати всі такі способи розвезення. Число п цих способів залежатиме не тільки від перерахованих параметрів, але і від числа складів на кожному маршруті, об'єму замовлень і т.д. Кожному j— му способу розвезення І відповідають витрати Cj.

Нехай при даних конкретних умовах задачі сформована матриць A=[a_ij] способів розвезення, що складається з нулів і одиниць. Стовпці цієї матриці являють собою описані вище способи розвезення, тобто , якщо в j-му способі i -є замовлення задовольняється, і - у противному разі. Тепер завдання полягає у виборі найбільш економічної комбінації цих способів.

Математична модель задачі. Введемо змінні: в рівні 1, якщо j спосіб розвезення реалізується, і рівні 0 - у противному разі. Тоді математична модель задачі набуває вигляду:

; (5.29)

(5.30)

(5.31)

(5.32)

Умова (5.30) означає, що всі замовлення повинні бути задоволені тільки один раз.