На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Задача о распределении ресурсов , класс задачи
    Всем привет :)

    Классическая модельная задача, которую обычно решают ДП:
    Между конечным числом получателей распределяется целое положительное количество какого-то ресурса.
    Прибыль от вложений ресурса задана табличкой.
    Требуется эту прибыль максимизировать.

    К какому классу относится эта задача?
      Первый-на :lool: Самое оптимальное решение - дает полный перебор...
      Но тут нет никакого инструмента выявления экстремумов. Иными словами - "или все, или ничего".
        Ну вот про рюкзак или про набор суммы заданными слагаемыми(задача тысячелетия!) скоро на заборе будет написано, что они NP-полные, но решаются за псевдополиномиальное время.
        А про эту ничего не нашла.
          Цитата swf @
          К какому классу относится эта задача?

          Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе).
          Решается за полиномиальное время.
            Не вижу НИКАКОГО различия между этой задачей и рюкзаком.

            Цитата swf @
            Между конечным числом получателей рюкзаков распределяется целое положительное количество какого-то ресурса.
            Прибыль от вложений ресурса Вес задана табличкой.
            Требуется эту прибыль стоимость максимизировать.
              Цитата amk @
              Цитата swf @
              К какому классу относится эта задача?

              Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе).
              Решается за полиномиальное время.

              В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять.

              Добавлено
              Цитата Akina @
              Не вижу НИКАКОГО различия между этой задачей и рюкзаком.

              Цитата swf @
              Между конечным числом получателей рюкзаков распределяется целое положительное количество какого-то ресурса.
              Прибыль от вложений ресурса Вес задана табличкой.
              Требуется эту прибыль стоимость максимизировать.

              Да! конечно. Много рюкзаков.
              Спасибо, Акина!
              И решается с помощью ДП рюкзак двойным циклом, а распределение ресурсов - тройным.
              Скрытый текст

              Это я щас пишу главку для уч. пособия "Решение NP-полных задач точными методами", нельзя ДП обойти. Задачи решаю по всем правилам науки, прямой и обратной прогонкой :D
                Нет, это не рюкзак и не много рюкзаков, думаем дальше :D

                Добавлено
                частный случай задачи распределения из теории расписаний
                  Цитата swf @
                  В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять.
                  Кроме поиска максимума линейной функции при линейных ограничениях, задачи, решаемой собственно линейным программированием, есть ещё и несколько дискретных задач вроде транспортной задачи.

                  По мне, так описание соответствует именно транспортной задаче.
                    amk,
                    в транспортной задаче сколько единиц потока вышло из источника, ровно столько пришло в сток.
                    Есть, правда, потоки с усилением, когда поток, проходя через вершину умножается на коэффициент, что опять линейная функция.
                    А тут от от одной единицы прибыль 10, от двух - 15, от трёх - 16, а от четырёх теоретически может быть меньше 16, никто ведь не обещал, что функция монотонно возрастает.

                    Видимо, надо идти от программы, от того тройного цикла, который я написала. Если каждое число a на входе (величина ресурса, величина прибыли) закодировать как логарифм (log a), то длина входа будет равна
                    (n+M)*log (max a), где n - число заводов, M - количество вариантов объёма ресурса, max a - максимальное входное число.
                    Соответственно, у полиномиального алгоритма выч.сложность ограничена полиномом от длины входа, у псевдополиномиального - неограничена.
                    Ну вот решаем набор суммы ДП, набираем сумму B n слагаемыми, табличка n*B, выч. сложность псевдополиномиальная O(n*B), что не ограничено никаким полиномом от nlog B.

                    А тут что-то не соображу, от чего у меня табличка (количество состояний) зависит: от количества вариантов ресурса или от (максимальной) величины выделяемого ресурса.
                    Сообщение отредактировано: swf -
                      Цитата swf @
                      Всем привет :)

                      Классическая модельная задача, которую обычно решают ДП:
                      Между конечным числом получателей распределяется целое положительное количество какого-то ресурса.
                      Прибыль от вложений ресурса задана табличкой.
                      Требуется эту прибыль максимизировать.

                      К какому классу относится эта задача?

                      Спасибо. Пошел по ссылке нашел классный курс ДП на ютуб. Уже посмотрел 34 лекции
                        Рассмотрела свои реализации прямой и обратной схемы.
                        Если решать обратной схемой, то Z[i,j] - прибыль от первых i предприятий, j - остаток средств.
                        Состояние системы описывается имеющимися средствами.
                        Начинаем от всей суммы, заканчиваем 0.

                        Если решать прямой схемой, то Z[i,j] - прибыль от первых i предприятий, j - потраченные средства.
                        Состояние системы описывается потраченными средствами.
                        Начинаем от 0 (ничего не потратили), заканчиваем полной суммой - всё потратили.

                        Пусть i = 1..n, где n -количество предприятий и число строк в табличке;
                        j= 0..M, где M - число различных вариантов выделения средств.
                        Если количество выделяемых средств кратно номеру варианта (например, M = 3: {0, 40, 80, 120}),
                        то столбцы в табличке нумеруем 0..M.
                        Уравнение состояния
                        для обратной схемы: Si = Si-1-Xi, где Xi - управление, Xi*40 - средства, выделенные заводу;
                        для прямой схемы Si = Si-1+Xi.
                        Как только выделенные средства перестают быть линейной функцией номера варианта - всё,
                        в табличке, как для рюкзака или как для набора суммы заданными слагаемыми, нужно столбцы вести не по номерам вариантов а по распределяемой сумме денег.

                        Как верно заметил Акина, получаем рюкзак.
                        Но полиномиальную сводимость рюкзака (или набора суммы) к этой задаче, конечно, нужно доказывать.
                        Поэтому тема остаётся открыта :)
                        Сообщение отредактировано: swf -
                          swf,
                          А пример исходных данных можно посмотреть, как задана прибыль от вложений ресурса?
                          Допустимо ее аппроксимировать линейной функцией либо найти другое математическое упрощение?
                            Это учебные задачи на динамическое программирование.
                            Там обычно или без затей 0 ... M, или 0, 40, 80, 120, или как-то линейно от номера варианта прибыли.
                            Для таких входных данных, конечно, класс P.
                            А вот если прибыль - любая точка RM+1, то нигде не сказано, к какому классу относится задача.
                            Сообщение отредактировано: swf -
                              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                              0 пользователей:


                              Рейтинг@Mail.ru
                              [ Script execution time: 0,0353 ]   [ 15 queries used ]   [ Generated: 29.03.24, 05:12 GMT ]