| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Задача о распределении ресурсов |
| Автор: swf 08.06.20, 19:53 |
Всем привет  Классическая модельная задача, которую обычно решают ДП: Между конечным числом получателей распределяется целое положительное количество какого-то ресурса. Прибыль от вложений ресурса задана табличкой. Требуется эту прибыль максимизировать. К какому классу относится эта задача? |
| Автор: JoeUser 08.06.20, 20:01 |
Первый-на  Самое оптимальное решение - дает полный перебор...Но тут нет никакого инструмента выявления экстремумов. Иными словами - "или все, или ничего". |
| Автор: swf 08.06.20, 20:25 |
| Ну вот про рюкзак или про набор суммы заданными слагаемыми(задача тысячелетия!) скоро на заборе будет написано, что они NP-полные, но решаются за псевдополиномиальное время. А про эту ничего не нашла. |
| Автор: amk 09.06.20, 02:15 |
| Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе). Решается за полиномиальное время. |
| Автор: Akina 09.06.20, 04:20 |
| Не вижу НИКАКОГО различия между этой задачей и рюкзаком. Цитата swf @ Между конечным числом Требуется |
| Автор: swf 09.06.20, 09:03 |
| Цитата amk @ Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе). Решается за полиномиальное время. В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять. Добавлено Цитата Akina @ Не вижу НИКАКОГО различия между этой задачей и рюкзаком. Цитата swf @ Между конечным числом Требуется Да! конечно. Много рюкзаков. Спасибо, Акина! И решается с помощью ДП рюкзак двойным циклом, а распределение ресурсов - тройным. Скрытый текст Это я щас пишу главку для уч. пособия "Решение NP-полных задач точными методами", нельзя ДП обойти. Задачи решаю по всем правилам науки, прямой и обратной прогонкой  |
| Автор: swf 09.06.20, 10:39 |
| Нет, это не рюкзак и не много рюкзаков, думаем дальше Добавлено частный случай задачи распределения из теории расписаний |
| Автор: amk 10.06.20, 21:43 |
| Цитата swf @ Кроме поиска максимума линейной функции при линейных ограничениях, задачи, решаемой собственно линейным программированием, есть ещё и несколько дискретных задач вроде транспортной задачи.В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять. По мне, так описание соответствует именно транспортной задаче. |
| Автор: swf 11.06.20, 09:29 |
| 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. А тут что-то не соображу, от чего у меня табличка (количество состояний) зависит: от количества вариантов ресурса или от (максимальной) величины выделяемого ресурса. |
| Автор: esperanto 11.06.20, 14:12 |
| Цитата swf @ Всем привет Классическая модельная задача, которую обычно решают ДП: Между конечным числом получателей распределяется целое положительное количество какого-то ресурса. Прибыль от вложений ресурса задана табличкой. Требуется эту прибыль максимизировать. К какому классу относится эта задача? Спасибо. Пошел по ссылке нашел классный курс ДП на ютуб. Уже посмотрел 34 лекции |
| Автор: swf 11.06.20, 15:35 |
| Рассмотрела свои реализации прямой и обратной схемы. Если решать обратной схемой, то 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. Как только выделенные средства перестают быть линейной функцией номера варианта - всё, в табличке, как для рюкзака или как для набора суммы заданными слагаемыми, нужно столбцы вести не по номерам вариантов а по распределяемой сумме денег. Как верно заметил Акина, получаем рюкзак. Но полиномиальную сводимость рюкзака (или набора суммы) к этой задаче, конечно, нужно доказывать. Поэтому тема остаётся открыта |
| Автор: m-ch 19.06.20, 12:30 |
| swf, А пример исходных данных можно посмотреть, как задана прибыль от вложений ресурса? Допустимо ее аппроксимировать линейной функцией либо найти другое математическое упрощение? |
| Автор: swf 19.06.20, 19:00 |
| Это учебные задачи на динамическое программирование. Там обычно или без затей 0 ... M, или 0, 40, 80, 120, или как-то линейно от номера варианта прибыли. Для таких входных данных, конечно, класс P. А вот если прибыль - любая точка RM+1, то нигде не сказано, к какому классу относится задача. |