| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Определение оптимального расположения. |
| Автор: Sliderian 10.1.2012, 14:09 |
| Доброго времени суток. Опишу сначала вкраце суть процесса: Есть N городов. В каждом городе находится M пунктов сбыта. Есть несколько городов в которых расположены хранилища, по одному в городе. До каждого города известно расстояние. Есть несколько типов машин для перевозки (по объему). Также известна цена перевозки за 1 км. На пунктах сбыта с некоторой частотой уменьшается количество товара. Когда достигается порог минимума, происходит заказ с хранилища. Поставка осуществляется с хранилища в пункт напрямую. Машина выбирается так чтоб влез весь необходимый объем. Задача состоит в том, чтобы определить города, в которых нужно создать дополнительные перегрузочные склады, в которые товар будет идти из хранилища одной большой машиной, а из склада распределяться по пунктам маленькими для уменьшения затрат. Известно количество складов, которые можно создать. По этому количеству необходимо определить оптимальное расположение складов для максимального снижения затрат. Перебором всех вариантов делать не хочется. Должен быть какой-нибудь способ определения варианта близкого к лучшему, только вот не могу понять даже в какой области искать. |
| Автор: Akina 10.1.2012, 14:18 |
| Гм... а максимум количества товара в каждом пункте сбыта задан? или нет, не так - разность между этими минимумом и максимумом больше или меньше грузоподъёмности машины с наиболее дешёвым тарифом на доставку единицы груза? |
| Автор: Sliderian 10.1.2012, 14:22 |
| Задан целевой уровень до которого пополняется запас. Про разницу между целевым и минимальным ничего не говорится, но судя по данным он точно меньше макс машины которой возится товар в склады. Насчет остальных неоднозначно и для каждого пункта уровни разные. |
| Автор: Mirkes 13.2.2012, 13:30 |
| Напрашивается что-то вроде транспортной задачи или задачи комивояжера. В качестве целевой функции видимо что-то вроде стоимости перевозки при заданом расположении складов. Плюс штрафная функция за число складов, превышающее заданный максимум. Например добавляем переменную типа терминал (перегрузочный склад) в каждый город, но добавляем условие, что сумма этих переменных не должна быть больше заданного числа складов. Однако от классических задач Вашу отличает вероятная нерегулярность поставок. Классическая задача комивояжера говорит о необходимости посетить каждый город 1 раз а транспортная - о перевозке заданного количества товаров. Дополнительно нужно определиться, может ли товар храниться в терминалах или нет. По хорошему имея заданные частоты "уменьшения запасов в магазинах" вычисляется объем месячной (недельной и т.п.) поставки в каждый магазин. После этого задачу можно сводить к одной из стандартных. |