Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832848 Fri, 19 Jun 2020 19:00:44 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832848 Там обычно или без затей 0 ... M, или 0, 40, 80, 120, или как-то линейно от номера варианта прибыли.
Для таких входных данных, конечно, класс P.
А вот если прибыль - любая точка RM+1, то нигде не сказано, к какому классу относится задача.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832818 Fri, 19 Jun 2020 12:30:09 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832818 swf,
А пример исходных данных можно посмотреть, как задана прибыль от вложений ресурса?
Допустимо ее аппроксимировать линейной функцией либо найти другое математическое упрощение?]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832437 Thu, 11 Jun 2020 15:35:02 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832437 Если решать обратной схемой, то 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832431 Thu, 11 Jun 2020 14:12:01 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832431 Цитата swf @
Всем привет :)

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

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

Спасибо. Пошел по ссылке нашел классный курс ДП на ютуб. Уже посмотрел 34 лекции]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832358 Thu, 11 Jun 2020 09:29:15 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832358 в транспортной задаче сколько единиц потока вышло из источника, ровно столько пришло в сток.
Есть, правда, потоки с усилением, когда поток, проходя через вершину умножается на коэффициент, что опять линейная функция.
А тут от от одной единицы прибыль 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832337 Wed, 10 Jun 2020 21:43:56 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832337 Цитата swf @
В теории написано, что функции дискретные (заданы табличками), поэтому методы ЛП нельзя применять.
Кроме поиска максимума линейной функции при линейных ограничениях, задачи, решаемой собственно линейным программированием, есть ещё и несколько дискретных задач вроде транспортной задачи.

По мне, так описание соответствует именно транспортной задаче.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832221 Tue, 09 Jun 2020 10:39:35 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832221
Добавлено
частный случай задачи распределения из теории расписаний]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832213 Tue, 09 Jun 2020 09:03:41 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832213 Цитата amk @
Цитата swf @
К какому классу относится эта задача?

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

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

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

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

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

Это я щас пишу главку для уч. пособия "Решение NP-полных задач точными методами", нельзя ДП обойти. Задачи решаю по всем правилам науки, прямой и обратной прогонкой :D
]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832187 Tue, 09 Jun 2020 04:20:32 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832187
Цитата swf @
Между конечным числом получателей рюкзаков распределяется целое положительное количество какого-то ресурса.
Прибыль от вложений ресурса Вес задана табличкой.
Требуется эту прибыль стоимость максимизировать.
]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832185 Tue, 09 Jun 2020 02:15:19 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832185 Цитата swf @
К какому классу относится эта задача?

Это классическая задача линейного программирования. Целочисленная (транспортная задача, задача о назначениях, максимальное паросочетание в двудольном графе).
Решается за полиномиальное время.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832180 Mon, 08 Jun 2020 20:25:35 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832180 А про эту ничего не нашла.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832178 Mon, 08 Jun 2020 20:01:43 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832178 Но тут нет никакого инструмента выявления экстремумов. Иными словами - "или все, или ничего".]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832177 Mon, 08 Jun 2020 19:53:59 +0000 Задача о распределении ресурсов https://forum.sources.ru/index.php?showtopic=418870&view=findpost&p=3832177
Классическая модельная задача, которую обычно решают ДП:
Между конечным числом получателей распределяется целое положительное количество какого-то ресурса.
Прибыль от вложений ресурса задана табличкой.
Требуется эту прибыль максимизировать.

К какому классу относится эта задача?]]> swf Алгоритмы