Что вы всегда хотели узнать, но боялись спросить

[Swetlana]

Source of the post

Source of the post
не ставится у меня "Сумма размеров" как оптимизационная задача ЦЛП

Минимизируйте абсолютную разность полученной суммы и целевой суммы.

спасибо за интерес к теме! и, раз уж разговор этого коснулся,
целый коллектив денег лишился, из-за меня этого критерия - минимизации абсолютной разности набранной суммы и целевой суммы

хоздоговор был заключен на размещение готовой листопрокатной продукции на складе, а следующий планировался на отгрузку готовой продукции со склада, но я сразу сделала в комплексе, и размещение, и отгрузку
провела эксперименты на реальных данных - алгоритм отгрузки чудо как хорош и сбалансирован! кому-то немного недогрузим, кому-то перегрузим, и к концу месяца по всем видам сортамента уходим в нули - и себе не в убыток, и, главное, склад не забивается неучтёнными остатками, которые по документам ушли
ответственный исполнитель поехал к заказчику (меня заказчикам не показывали, как неадекватушку ), приезжает, грит, что размещение приняли, и спрашивает:
- А можно вес набирать только с недостатком?
тут я сразу сообразила, что верхняя оценка погрешности моего приближённого алгоритма от этого станет в 2 раза больше, что мне главный показатель хотят испортить, и грю:
- Нет. Нельзя.


в инете есть статья в pdf, когда доберусь до сверхбольшой размерности, поясню
Девятов Д.Х., Файнштейн С.И., Тутарова В.Д., Калитаев А.Н. Оперативное планирование отгрузки готовой продукции со складов металлургических предприятий // Мехатроника, автоматизация, управление. – 2008. – №4. – С. 36 - 40.

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

Определение. Комбинаторная оптимизационная задача $$Ï$$ есть либо задача минимизации, либо задача максимизации и состоит из трёх частей:
(1) множества $$D_Ï$$ индивидуальных задач;
(2) для каждой $$I \in D_Ï$$ имеется конечное множество $$S_Ï(I)$$ допустимых решений задачи ;
(3) функции $$m_Ï$$, сопоставляющей каждой задаче $$I \in D_Ï$$ и каждому допустимому решению
$$\sigma \in S_Ï(I)$$ некоторое положительное целое число $$m_Ï(I, \sigma )$$, называемое величиной решения.
Для обозначения величины оптимального решения будем использовать обозначение .

чтобы ответить, нельзя разговаривать на уровне задач и алгоритмов, нужно переходить на уровень языков, схем кодирования и формальных моделей вычислителя... тоска
имхо, Гэри-Джонсон сознательно уклоняются от обсуждения. Т.к., предлагая модель переборной задачи, для которой и задача распознавания, и задача оптимизации суть частные случаи, говорят, что "можно избежать дискуссии, принадлежит ли пустое слово языку"

[Swetlana]

Итак, задача распознавания из решалась $$ÍÄÌÒ$$, у которой были состояния $$q_y \ è \ q_n.$$
Задача оптимизации решалась на обычной ДМТ, причём на ленте записывалось закодированное входное слово перед началом работы, а после останова на ленте должно было быть записано закодированное выходное слово-ответ.
Теперь эти два типа задач объединяются в так называемую переборную задачу и для переборных задач затем строится целая теория - трудных задач, на основе сводимости по Тьюрингу.
Интересно, что с задачами, дополнительными к - трудным, всё в порядке - они тоже - трудные.
Я сама всего этого не знаю, кто любит более меня, пусть пишет далее меня
Но определение переборной задачи нужно дать.

Определение. Переборная задача $$Ï$$ это множество её индивидуальных задач $$D_Ï.$$
Для каждой индивидуальной задачи $$I \in D_Ï$$ известно множество $$S_Ï(I)$$ конечных объектов, называемых решениями задачи . Будем говорить, что алгоритм решает переборную задачу $$Ï$$ , если, получив в качестве входа произвольную задачу $$I \in D_Ï$$, этот алгоритм выдаёт ответ "нет", если $$S_Ï(I)$$ пусто, и вырабатывает некоторое решение $$s \in S_Ï(I)$$ в противном случае.

Например, для задачи ГЦ пишем "нет", если гамильтонова цикла в графе не существует. Если таких циклов не один, то записываем в качестве ответа любой.

...а теперь переходим к практическим аспектам

[Swetlana]

то ли сумму набирать, то ли вначале несколько слов про ДП (дин. прогр.) сказать
все слова забыла
щас в одном месте подсмотрю
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления // М.: Наука, 1969, 118 стр.

Многошаговые процессы принятия решения. Принцип оптимальности Беллмана. Основное функциональное уравнение Беллмана.

В качестве примера общей модели управляемого процесса, т.е. процесса, для которого имеется возможность выбирать какие-то параметры, влияющие на его ход, рассмотрим многошаговый процесс принятия решений, предложенный американским математиком Ричардом Беллманом, основоположником теории динамического программирования (динамической оптимизации).

Пусть – пространство состояний системы (у физиков - фазовое пространство), функция – преобразование, переводящее систему из состояния в состояние где

Определение 1. Бесконечная последовательность состояний системы $$\[p_0, \ p_1, \dots, \ p_n, \dots \] \ ãäå \ p_0 = p \ è \ p_{n+1} = T(p_n), \ n = 0, \ 1, \ 2, \dots $$ есть история системы, наблюдаемая в дискретные моменты времени, или многошаговый процесс.

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

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

Определение 2. Назовем последовательность пошаговых управлений стратегией. Стратегия, максимизирующая функцию дохода, называется оптимальной стратегией или оптимальным управлением.

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

Принцип оптимальности Беллмана.
Оптимальная стратегия обладает тем свойством, что, каковы бы ни были первоначальное состояние и первоначальное решение (управление), последующее решение должно определять оптимальную стратегию относительно состояния, полученного в результате первоначального решения.
разъясняем
начальное состояние и начальное управление - любые, они перевели систему в новое состояние . Забываем историю процесса, раз наше текущее состояние , значит, выстраиваем оптимальную стратегию относительно начального состояния
надеюсь, теперь понятно

Если в качестве функции дохода использовать аддитивную функцию, где общий выигрыш складывается из суммы выигрышей по всем шагам, то принцип выбора оптимальных пошаговых управлений формулируется так:
«Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».
Используя это соображение, можно записать основное рекуррентное соотношение динамического программирования (функциональное уравнение Беллмана), позволяющее получить как аналитически, так и численно оптимальную стратегию и максимальный доход.

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

[Swetlana]

Основное функциональное уравнение Беллмана

Рассмотрим задачу о максимизации функции дохода. Как уже было сказано, функция дохода должна иметь такую структуру, чтобы выбор оптимального решения (управления) зависел только от текущего состояния системы и не зависел от всей истории процесса.
Заметим, что под "состоянием системы" понимается описание математической модели системы.

Например, требуемым свойством "сепарабельности", т.е. отделимости прошлого от будущего, обладают следующие критерии (функции дохода):
1. .
2. .
3. (терминальное управление).
4. (для бесконечношаговых процессов).

Выведем функциональное уравнение для первой функции дохода, где общий доход равен суммарному доходу по всем шагам: .

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

Из принципа оптимальности получаем, что при любом начальном управлении для верно:


что мы тут сделали
начальное состояние системы и начальное решение (управление) были произвольные, они перевели систему в состояние
все последующие решения-управления составили оптимальную стратегию относительно начального состояния , поэтому сумму в квадратных скобках заменили максимальным доходом, полученным за шаг
Далее, чтобы получить максимальный доход за все шагов, нужно найти максимум функции дохода по всем возможным управлениям на первом шаге.
Для этого либо этих возможных управлений должно быть конечное число, либо функции $$g(p, \ q) \ è \ T(p, \ q)$$ должны быть достаточно гладкими.
Так или иначе, но получаем

основное функциональное уравнение для аддитивной функции дохода:

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

Литература
Беллман Р., Калаба Р. Динамическое программирование и современная теория управления // М.: Наука, 1969.
тоненькая книжечка,

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

[Swetlana]

Лекции Котова по динамическому программированию

Псевдополиномиальные алгоритмы это динамическое программирование, другие псевдополиномиальные алгоритмы науке пока неизвестны
я училась решать задачи по ДП с помощью лекций Котова для школьников, учащихся старших классов

вот они


[img]/modules/file/icons/application-octet-stream.png[/img] ___________________.rar

[Swetlana]

Решаем задачу "Сумма размеров" с помощью ДП

Открываем лекции Котова на стр. 17
Пример 1.
Имеется 5 неделимых предметов. Для каждого предмета известна его масса (в кг). Величины массы являются натуральными числами. Ваша цель состоит в том, чтобы определить, существует ли среди 4кг, 5кг, 3кг, 7кг, 6кг несколько предметов, суммарная масса которых равна 16 кг. Если такой набор существует, то требуется определить список предметов в наборе.
Решение.
Пусть массы всех предметов хранятся в массиве , где - масса -го предмета.

Стоп.
Задача о наборе веса 16кг - задача распознавания.
Динамическое программирование (динамическая оптимизация) решает задачи оптимизации.
Основное реккурентное соотношение Беллмана, которое мы вывели, максимизирует функцию дохода.
Как же так???
Спокойствие, ув. коллеги. Читаем учебник для старших школьников дальше

Через $$Ò$$ обозначим функцию, значение которой равно , если искомый набор имеется, и равно , если такого набора нет. Аргументами у этой функции будут количество предметов и требуемая суммарная масса набора .
То есть нам надо определить значение функции $$Ò(5,16)$$. Если оно равно , то вес можно набрать, если - нельзя. Поскольку , будем максимизировать значение функции согласно функциональному уравнению Беллмана.

Определим значения функции дохода при всех возможных значениях аргументов.
$$T(0,j) = 0 \ ïðè \ j \geq 1$$ //нельзя без предметов набрать массу .
$$T(i,0) = 1 \ ïðè \ i \geq 0$$ //всегда можно набрать нулевую массу.

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

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

Теперь нам необходимо выбрать лучшую из этих двух возможностей. Поэтому рекуррентное соотношение при $$i \geq 1 \ è \ j \geq 1$$ имеет вид:
$$T(i,j) = T(i-1,j) \ ïðè \ j < M[i];$$" title="$$ //$$" align="middle" style="border: 0; vertical-align: middle">i$$-й предмет не берётся, т.к. не проходит по весу
$$T(i,j) = max (T(i-1,j),T(i-1,j-M[i])) \ ïðè \ j \geq M[i].$$

Реккурентные соотношения составлены.
Вычислять значения функции удобно с помощью таблицы,
где строки - количество разрешённых к использованию предметов, ;
столбцы - набранный вес,
Далее смотрим у Котова, на табличку и на алгоритм определения предметов, которые вошли в набор.
Реально хороший учебник.
Вот моя первая прожка по ДП, списанная с котовой
Набираем сумму 90, но её набрать невозможно, и ДП даёт ближайшую сумму по недостатку - 89.

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

Код: Выбрать все

const N=5;
 Ves=90;
 var
 M: array[1..N]of integer;
 T:array[0..N,0..Ves]of byte;
 sum,i,j:integer;
 begin
 M[1]:= 35; M[2]:= 30; M[3]:= 17; M[4]:= 13;
 M[5]:= 11;
 T[0,0] := 1;
 for j := 1 to Ves do T[0, j] := 0;
 for i := 1 to N do T[i, 0] := 1;

 for i := 1 to N do begin
 for j := 1 to Ves do begin
 if j >= M[i] then begin
 if T[i - 1, j]> T[i - 1, j - M[i]] then
 T[i,j]:= T[i - 1, j]
 else T[i, j]:= T[i - 1, j - M[i]];end
 else T[i, j]:= T[i - 1, j];
 end;
 end;

 for j:=Ves downto 1 do
 begin
 sum:=j;
 if T[N, j] = 1 then
 begin
 for i := N downto 1 do
 begin
 if T[i, sum] = T[i - 1, sum] then
 writeln (i, '---No')
 else begin writeln (i, '---Yes');
 sum := sum - M[i];
 end;
 end;
 break;
 end;
 end;

 readln;
 end.

...а когда я немного освоилась с ДП, то решила написать прожку для набора заданной суммы минимальным числом слагаемых, на сорцах из всех профи душу вынула
[url=http://forum.sources.ru/index.php?showtopic=339382#]http://forum.sources.ru/index.php?showtopic=339382#[/url]

[Andrew58]

Светлана,
Во-первых, огромное спасибо за ликбез. Я еще несколько раз перечитаю все с огромным удовольствием, ладно?
Дурацких же вопросов по дороге возникло много. Самый дурацкий - а есть в этой теории место понятиям количеству информации, неопределенности и прочему? Казалось бы, в экспоненте тут бы самое место, чтобы воткнуть...

[Swetlana]

на доброе здоровьичко, только я ещё не закончила

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

То есть классическое ДП - это дискретные детерминированные процессы, принятие решений в условиях определённости. Это преподают, и это все знают. Но.
В уже упомянутой книжке Беллмана-Калабы ДП обощается на случай непрерывных и стохастических процессов. Я в этом не разбиралась, потому что моя фишка - выбор в условиях многокритериальности, когда исчезает граница между оптимизацией и распознаванием, потому что из-за многокритериальных ограничений нет допустимых решений. Об этом как-нибудь потом

[Swetlana]

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

Приближённые методы решения

Приближённые методы решения имеют смысл только для оптимизационных задач.
Определение 1. Комбинаторная оптимизационная задача $$Ï$$ есть либо задача минимизации, либо задача максимизации и состоит из трёх частей:
(1) множества $$D_Ï$$ индивидуальных задач;
(2) для каждой $$I \in D_Ï$$ имеется конечное множество $$S_Ï(I)$$ допустимых решений задачи ;
(3) функции $$m_Ï$$, сопоставляющей каждой задаче $$I \in D_Ï$$ и каждому допустимому решению
$$\sigma \in S_Ï(I)$$ некоторое положительное целое число $$m_Ï(I, \sigma )$$, называемое величиной решения.
Для обозначения величины оптимального решения будем использовать обозначение .

Определение 2. Алгоритм называется приближённым алгоритмом решения задачи $$Ï$$, если для любой индивидуальной задачи $$I \in D_Ï$$ алгоритм отыскивает некоторое допустимое решение $$\sigma \in S_Ï(I)$$.
Для обозначения величины приближённого решения будем использовать обозначение .

Случай, когда множество допустимых решений пусто, у Гэри-Джонсона не обсуждается. К слову, в многокритериальных задачах оптимизации, которые пришли из жизни, оно всегда пусто.
В такой ситуации я снимаю все ограничения, заменяю их штрафными функциями, где штрафы за нарушения ограничений суть настроечные константы, позволяющие адаптировать алгоритм к реальным данным, и решаю задачу на области недопустимых решений, т.е. получаю решение с небольшими нарушениями технологических ограничений, что на производстве происходит каждый день. Это жизнь.
Но сейчас мы решаем задачи, как положено, на множестве допустимых решений, и оно не пусто. Такие задачи тоже есть

Определение 3. Если для всех $$I \in D_Ï$$, то называется точным алгоритмом задачи $$Ï$$.

[Swetlana]

теперь нужно определиться , как мы будем мерять погрешность приближённых алгоритмов
возможно, терминология Гэри-Джонсона устарела, лучше смотреть в Кормене
но Кормена под рукой нет

Пусть $$Ï$$ - задача минимизации (максимизации), $$I \in D_Ï$$ - произвольная индивидуальная задача.
Тогда величину ( и для задачи максимизации)
назовём относительной погрешностью алгоритма решения индивидуальной задачи $$I \in D_Ï$$.

Теперь введём другую безразмерную величину, отношение
(и для задачи максимизации соответственно)

Определение 4. Погрешностью приближённого алгоритма решения задачи $$Ï$$ назовём величину :
$$R_A = inf \left\{ r \geq 1: \ R_A(I) \leq r \ äëÿ \ âñåõ \ I \in D_Ï \right \}$$.

Определение 5. Асимптотической погрешностью приближённого алгоритма назовём величину :
$$R_A^{\infty} = inf \{ r \geq 1:íàéä¸òñÿ \ N \in Z^+,òàêîå, \ ÷òî \ R_A(I) \leq r \ äëÿ \ âñåõ $$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">\ I \in D_Ï, \ äëÿ \ êîòîðûõ \ âûïîëíåíî \ ñîîòíîøåíèå \ Opt(I) \geq N \}$$.

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