LINUX.ORG.RU

задача на распределение ресурсов

 ,


0

1

Такая задача. Есть некая фабрика и есть время, за которое надо потребить сколько-то (Х) ресурсов. В каждый определенный промежуток этого времени фабрика может потребить только ровно Х_i ресурсов.

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

Собственно, цель - минимизировать цену закупки ресурсов за указанное время с учетом выполнения фабрикой плана потребления ресурсов.

Это задача решается методами исследования операций (симплекс метод) или я не в том направлении смотрю?



Последнее исправление: jcdr (всего исправлений: 3)

или я не в том направлении смотрю?

В том.

anonymous
()

Ключевые слова: дискретно-событийное моделирование, GPSS, AnyLogic

dave ★★★★★
()

Глянь ещё в сторону теории оптимального управления, со всякими там принципами Понтрягина.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

У меня не получается выразить связность между загрузкой/выгрузкой из/в склад. Т.е. тут надо выдерживать емкость склада. А она должна быть в каждый момент времени в интервале от 0 до некоего M. А каждая загрузка/выгрузка из склада меняет сумму. Можно такую временную зависимость выразить тем же симплекс-методом?

Я правильно говорю, что это невыпуклая задача?

Про теорию оптимального управления ничего не знаю, буду читать

jcdr
() автор топика
Ответ на: комментарий от Miguel

Принцип Понтрягина - это непрерывный случай. Там, для летательных аппаратов, чтобы правильно приземлились. А тут явно дискретный случай

dave ★★★★★
()
Ответ на: комментарий от jcdr

Вот и я не представляю где там симплекс. По-моему это вообще задача на поиск кратчайшего пути в нагруженном графе. Вершина в графе - день и запас на складе. Достижимые вершины из неё - день + 1, запас - x_i + разное количество поставок по минимальной на этот день цене, ну, естественно, с учётом неотрицателтности запаса и непривышения склада. Вес ребра, естественно, цена поставки в этот день. Нужно найти кратчайший путь из день0 запас 0 в деньН запас 0. Главная проблема - размер склада, если он дискретный, но большое, то жопа. Можно в принципе метод ветвей и границ подцепить.

khrundel ★★★★
()
Ответ на: комментарий от khrundel

Да, спасибо. Я пока тоже к методу ветвей и границ пришел

jcdr
() автор топика
Ответ на: комментарий от Miguel

Ну, тут похоже на целочисленное программирование вкупе с дискретно-событийным моделированием. Метод ветвей и границ и/или A* вроде норм.

dave ★★★★★
()

как эвристика - можно начать решать задачу без склада(ибо очевидно появление склада это возможность взять из прошлого самое дешёвое из ещё не выкупленного - но тут и вылезет(нелинейность) ценности места на складе ибо возможны случае пересечений по времени разных…

qulinxao3 ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.