Доброго времени суток!

Условие задачи звучит следующим образом:

Есть некоторое количество "заводов" которые  из  одного ресурса получают другой. 
Каждый завод может произвести   какое-то ограниченное количество ресурса. 
У каждого завода есть  свое фиксированное соотношение  получаемого ресурса  вида Б из  А.


На вход подается какое-то количество ресурса одного вида.  На выходе нужно получить максимально возможное количество ресурса другого вида, путем  преобразования ресурсов на заводах.


Потери при преобразовании неважны. Т.е. если получаем избыточное число промежуточного ресурса который нельзя задействовать в дальнейшем преобразовании  то плевать на него.
Главное получить максимальное количество  заданного другого ресурса.
Число промежуточных заводов неограничено (или для простоты алгоритма можно ограничивать каким-то уровнем 2,3,4 ....). 
Также может быть множество заводов  производящих ресурс А из Б, но при этом иметь  разный  объем производства и  разное соотношение производимого ресурса.


вот небольшое схематическое изображение процесса
http://s1.ipicture.ru/uploads/20110214/UV6JX3rC.png



помогите пожалуйста написать алгоритм для решения данной задачи, или подскажите на основании каких алгоритмов ее можно решить.



Это сообщение отредактировал(а) FF0000 - 14.2.2011, 22:17

Попытался вникнуть и плоховато понял. Не могли бы Вы переформулировать задачу. Пока что у меня складывается такая картинка:
Имеем сырье (ресурс-0). Имеем продукт (ресурс-N).
Имеем конечное число заводов, каждый из которых способен переработать определенное количесвто ресурса-K в ресурс-L.
Но тогда в чем же проблема? На одном конце все заводы, потребляющие ресурс-0, на другом - все производящие ресурс-N. Между ними - несколько цепочек промежуточных стадий. Промежуточные цепочки могут ветвиться или соединяться.
Но что-то уж очень просто получается. Чего я не понял?

Если бы мощности заводов были неограничены - да, было бы просто. 

FF0000, приблизительно такие задачи решаются в химкинетике. Очень похоже на многоходовую необратимую реакцию... там есть матаппарат - но он рассчитан всё больше на обратимые реакции и на расчёт скоростей - т.е. не очень применим... но можешь посмотреть - вдруг на какую мыслю наведёт.

Akina, в химкинетике условие 

малоприменимо, если конечно, нет способа вывода избытка из системы.

Но я все равно плохо въезжаю в чем заключается сложность. Согласно схеме имеется несколько линейных путей производства конечного продукта. Допускаю, что пути могут ветвиться или объединяться. Ну и что? На каждом пути будет своя лимитирующая стадия. Остальные заводы будут работать не на полную мощность или производить излишки.

Видимо, есть еще какие-то условия, которые я не смог осознать?

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

Добавлено через 2 минуты и 14 секунд
FF0000, я бы пошёл про итерационному алгоритму. Он получится сложным (не в реализации - вычислительно), но должен дать результат. Ведь фактически твоя задача - это поиск глобального максимума функции многих переменных.

Все равно не въезжаю. Ну и будет один путь работать не на полную мощность. Что такого? Условие "задействовать минимальное количество заводов" ведь не ставится.

Получается, что рисуем все пути. Сортируем их по эффективности переработки сырья в конечный продукт. Загружаем работой самые эффективные. Самые неэффективные отключаем. Один путь, оказавшийся граничным, загружаем неполностью.

Но кажется мне, что есть еще условия, которых я не углядел.  

Пути могут пересекаться. И дать приходящего промежуточного продукта больше, чем может быть переработано.

FF0000, попробуй составление системы материальных балансов. По каждому заводу (выход = вход * коэфф.) и по каждому продукту (остаток = исх. + сумма произведённого - сумма портеблённого), плюс ограничивающие условия, и выполнить максимизацию полученной системы линейных уравнений и неравенств.

Akina, что-то мне кажется, что с материальным балансом здесь намучаешься. ИМХО работать надо с графом и путями в нем. 

Позвольте мне перформулировать задачу так. Имеем направленный граф. На входе ограниченное количество исходного сырья. На выходе нужно получить максимум конечного продукта. Каждый завод потребляет один продукт и производит другой. Соотношение сырье/продукт для каждого завода свое и задается априори. В результате конечный продукт может быть получен разными путями. Отходы не учитываются.

Есть еще условия, которых я не учел? Например, может какому-то заводу надо несколько типов сырья и/или он производит несколько продуктов, используемых другими заводами (т.е. не отходов)?

Если так, то я распишу довольно простой жадный алгоритм.

Akina, _Y_ спасибо большое за ваше внимание  и предложения.


Вот походу более качественное изображение 






Пояснение:
 - Большие точки -  ресурс.
 - связи между ними  - заводы производящие переработку 1 ресурса на 2 
 - стрелка указывает направление обмена
 - текст на стрелке указывает соотношение обмена  и количество конечного ресурса которого может произвести данный завод

к примеру: 1/2 (100) [AC1]

• AC1 - условно имя завода
• 1/2 - соотношение обмена ресурса,  
• (100)  - максимальное возможное число единиц производимого ресурса.
• Т.е.  завод AC1  делает переработку ресурса А  на ресурс С. Из одной единицы ресурса А он может произвести 2 единицы ресурса С. Всего он может произвести 100 единиц ресурса С.

Пояснение к "большому" изображению


На вход подаем 100 единиц ресурса А.
На выход хотим получить  наибольшее количество ресурса B

Есть маршрут 
ab1  Из него можно сразу получить 100 B. Но при наличии других маршрутов он не есть оптимальный.

Второй возможный маршрут Ac1
Ac1:   50A => 100C
                                 =>CB2:  25C -> 50B
                                 =>CB1:  75C -> 75B
                                 -----------------------------
                                   ∑ 125B     получили

 25C «остаток»  его можно либо задействовать  на 2 линиях, либо даже вернуть  в первоначальное состояние  Т.е. снова преобразовать в А.  Ну или на крайний случай ничего не делать с ним.


Таким образом на втором маршруте используем 50 единиц ресурса А,  а на первый (и в данном случае единственный ) пускаем остальные 50 единиц.

AB1 => 50A => 50B
-----------------------------------------------
 ∑ 125B + 50B = 175B - получили из 100 единиц ресурса А

•  Несколько путей могут пересекаться.
  
•  Некоторые пути могут зависеть от предыдущих путей, к примеру  из А получаем B (через C ). Для чего используем  2 маршрута.
      I)  А -> C -> B 
      II) А -> C -> B 
     После их выполнения   на "С" появится некий "излишек" ресурса. Его можно будет задействовать на "новом" появившимся лишь после прохождения этих первых двух маршрутов, к примеру   С->  D -> B
  Т.е. если  "промежуточный" ресурс  можно задействовать в других/ паралельных маршрутах - его нужно задействовать.
  
  Но если его уже нельзя никак задействовать - то плевать на него. Т.е. задача "безотходного"  производства или "производства без потерь" не ставится. 
  
  
• не исключается "откат", т.е.  возвращение  к первоначальному ресурсу  из каких-то промежуточных ресурсов, а то и  с конечного.
  
  Т.е.  если   хотим получить из  10 А  B,  
  и есть маршруты    1 А - > 2 B  (150 )
  и   1B -> 2 A ( 20 ) 
  
  то следующие шаги вполне допустимые:
  1)  по маршруту 1 А - > 2 B  (150 )  получить  20 Б
  2) по маршруту  1B -> 2 A ( 40 )  получить  40 А
  3) по маршруту  1 А - > 2 B  (130 )  [это первый маршрут но у него уже на 20 единиц конечной продукции меньше ]    из 40 А  получить  80 B

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


Количество заводов  и количество видов ресурсов не ограничивается.
Количество заводов производящих  один вид ресурса из другого также не ограничивается.
Сложность алгоритма ( с точки зрения вычислений  ) также неособо важна.


При наличии 5 заводов и  по  две связи между каждым ресурсом ( а связей может быть в разы больше)  будет какая-то такая паутина http://imglink.ru/pictures/17-02-11/877256...461dcf0f402.jpg


Но для простоты  реализации или вычислений количество одного и другого можно искусственно ограничить.


Это сообщение отредактировал(а) FF0000 - 17.2.2011, 18:26

Аааа. Т.е. граф с замкнутыми путями. И поэтому приходится делать развертку по времени, точнее пошажную. Первое, что приходит в голову - решать генетическим алгоритмом. Расписать? Или подумать может что попроще в голову придет?  


На картинке вроде не 5 заводов, а 5 продуктов. Ошибаюсь?

Это сообщение отредактировал(а) _Y_ - 17.2.2011, 23:43

Ошибаешься. 4 продукта и 10 заводов.

Akina, мы на разные картинки смотрим? Вроде имеются продукты A B C D E - я пальцем посчитал  

А на той - 5 продуктов и 20 заводов.

Ого! Я там заводы считать не решился. Носки снимать лень было, а на руках пальцев не хватило  

Это сообщение отредактировал(а) _Y_ - 17.2.2011, 23:25

_Y_   разве для подобных задач  генетический алгоритм можно применять?  Как в нем мутацию произвести?  А выбор потомства как сделать?  вить можно выбросить какой-то завод который  на каком-то N-том шаге может понадобится.  Чет мне кажется что с генетическим алгоритмом здесь ничего не сделаешь ... разве что  если только не использовать его как-то несовсем стандартно 


а на той картинке 20 заводов ... считать их ненужно ...   есть  5  ресурсов   и каждый ресурс можно  преобразовать на любой другой  ресурс.   Т.е. он используется как входящий  на 4 других заводах.  Ну и 5*4 = 20