Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.02.2011, 19:37
Новичок

Отправить личное сообщение для FF0000 Посмотреть профиль Найти все сообщения от FF0000
 
Регистрация: 17.02.2011
Сообщений: 2

получить максимальное количество ресурса
Доброго времени суток!

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

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


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


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







Пояснение:
- Большие точки - ресурс.
- связи между ними - заводы производящие переработку 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


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


Помогите пожалуйста кто чем может
алгоритмом решения или подсказками на что эта задача смахивает и с помощью чего было бы оптимально ее решить, любые идеи и подсказки
Буду благодарен любой Вашей помощи.
  #2  
Старый 19.02.2011, 15:32
Пользователь

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

Задача выглядит довольно просто.
1. Для каждого ресурса нужно завести неотрицательную переменную, обозначающую количество вырабатываемого ресурса.
2. Для каждого завода нужно завести неотрицательную переменную, ограниченную сверху его мощностью, обозначающую объем выработки.
3. Количество ресурса есть сумма входящего потока ресурсов плюс выработка его заводами
4. Заводы не могут потребить ресурса больше, чем его есть (см. пункты 1,3)
5. Критерий оптимальности: количество вырабатываемого ресурса B минус объем этого потребляемого ресурса другими заводами.

Математическое описание пунктов 1-5 – это задача линейного программирования. Решается соответствующими пакетами (линейное программирование есть в Excel)
  #3  
Старый 21.02.2011, 13:01
гость1

 
Сообщений: n/a

mserg
Нет, так не получится. Допустим, есть у тебя ресурсы A и B и 2 завода, переводящих эти ресурсы друг в друга с коэффициентом 2 и максимальным объёмом выработки 100. Пусть первоначально мы имеем 1 единицу A. Сколько B мы можем получить?
  #4  
Старый 21.02.2011, 19:58
Пользователь

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

Неужто бесконечность?
  #5  
Старый 22.02.2011, 10:08
гость1

 
Сообщений: n/a

На бесконечность производственных мощностей не хватит, но 75,5 можно запросто получить.
  #6  
Старый 22.02.2011, 11:00
гость1

 
Сообщений: n/a

Хотя нет, линейное программирование подходит, если всё корректно сформулировать:
1. Для каждого ресурса нужно завести неотрицательную переменную, обозначающую итоговое количество ресурса.
2. Для каждого завода нужно завести неотрицательную переменную, ограниченную сверху его мощностью, обозначающую объем выработки.
3. Количество ресурса есть сумма входящего потока ресурсов плюс выработка его заводами минус потребление его заводами.
4. Критерий оптимальности: максимизация количества целевого ресурса.
  #7  
Старый 25.02.2011, 19:36
Новичок

Отправить личное сообщение для FF0000 Посмотреть профиль Найти все сообщения от FF0000
 
Регистрация: 17.02.2011
Сообщений: 2

Спасибо большое всем отписавшимся.

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

Также возникли небольшие сомнения в выбранном варианте решения.
Насколько я понимаю, то для решения данной задачи с помощтю ЛП необходимо задать начальные уровнения. Но как задать эти уровнения если фактически частью условия задачи является поиск этих уровнений ( поиск путей/ цепочек преобразования продукта ). Ну и, грубо говоря поиск в найденных ту, которая дает максимальный выхлоп заданного ресурса.

как-то оно не укладывается у меня в голове =(...

--------------------
И еще одно
Насколько оправданно пытаться получить решения данной задачи геннетическим алгоритмом или же нейронными сетями ... - есть ли в этом смысл? Насколько я понимаю то эти два алгоритма позволили бы найти необходимые цепочки с той или инной оптимальностью, но отпугивает тот факт что результат их решения может быть не всегда 100% максимальный.
  #8  
Старый 25.02.2011, 19:56
гocть

 
Сообщений: n/a

Цитата:
А не подскажите более конкретно к какому разделу линейного программирования относиться данная задача
линейное программирование не такая большая наука чтобы в ней были какие-то "разделы"

Цитата:
чтоб почитать/посмотреть на аналогичные решения
ну, если все коэффициенты равны единице, то это в точности задача о максимальном потоке или транспортная задача.

Цитата:
Насколько я понимаю, то для решения данной задачи с помощтю ЛП необходимо задать начальные уровнения.
Вы про поиск начального допустимого решения для симплекс метода что-ли? Это не ваша забота, а симплекс метода.

Цитата:
поиск этих уровнений ( поиск путей/ цепочек преобразования продукта ).
не, у вас система уравнений не про пути будет, а про ребра и вершины: 1) у каждого ребра есть ограничение на максимальное число товаров толкаемых по нему, 2) в каждой вершине, кроме стока/истока, должен быть баланс - сколько прибыло, столько и убыло, с учетом коэффициентов.

Цитата:
Насколько оправданно пытаться получить решения данной задачи геннетическим алгоритмом или же нейронными сетями
неоправданно. ЛП быстрее, точнее.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Максимальное количество золот гость Задачи 6 07.09.2009 13:01
Топкодер. Как получить выигрыш? rustam85 Оффтопик 10 05.07.2008 16:38
Максимальное размещение фигур на площаде. energyy Вычислительная геометрия 0 19.05.2008 14:03
разместить максимальное количество кругов в прямоугольнике ibobak Задачи 2 01.03.2007 00:28
разместить максимальное количество кругов в прямоугольнике ibobak Вычислительная геометрия 1 25.02.2007 18:05