Оптимизационная задача

[Zo]

Привет, нужны соображения по поводу решения такой задачи:
$\sum\limits_{i=1}^n X_i\cdot U_i \to min$
Ограничение: $\sum\limits_{i=1}^n A_i\cdot U_i \geqslant V$,
где все $U_i\in \left\{0,1\right\}$, а $A_i\in R$,$X_i\in R$,
$A_i>0$,$X_i>0$,$V>0$
И естественно $\sum\limits_{i=1}^n A_i\geqslant V$
Оптимизация идет по $U_i$
Сказали, что нужно применить динамическое программирование, но у меня в результате его применения все свелось к банальному перебору (а он слишком большой $2^n$ - "проклятие размерности" ), затем принцип оптимальности Беллмана меня привел после видимо левых рассуждений к тому, что для решения достаточно занулять последовательно те $U_i$, для которых самые большие $X_i$, а ограничения задачи сохраняются - по этому алгоритму получалось, что как только окажется, что никакое $U_i$ больше занулить нельзя, то решение получено. Но это неверный метод. Вопрос что делать, как быть, как избежать прямого перебора (про метод Гомори знаю, но надо без него). Пожалуйста, подскажите. Интересны любые соображения.

[PAV]

По-моему, правильное решение действительно будет таким: одни значения $U_i$ будут нулями, другие - единицами, и некоторое одно будет между 0 и 1, чтобы ограничение имело вид равенства.

Только нужно смотреть не только на величину коэффициента $X_i$, но на соотношение между $X_i$ и $A_i$. Рассуждайте так: пусть имеется некоторое решение, при котором ограничение имеет вид равенства. Возьмите некоторую пару переменных $U_i$ и $U_j$ и уменьшите первую на $\varepsilon>0$, а вторую увеличьте на такое число, чтобы равенство сохранилось. Теперь посмотрите, что при этом произойдет с целевой функцией, увеличится ли она или уменьшится. Это покажет, по какому критерию нужно упорядочить переменные, чтобы затем последовательно их занулять.

[Zo]

PAV писал(а):

По-моему, правильное решение действительно будет таким: одни значения $U_i$ будут нулями, другие - единицами, и некоторое одно будет между 0 и 1, чтобы ограничение имело вид равенства.

Только нужно смотреть не только на величину коэффициента $X_i$, но на соотношение между $X_i$ и $A_i$. Рассуждайте так: пусть имеется некоторое решение, при котором ограничение имеет вид равенства. Возьмите некоторую пару переменных $U_i$ и $U_j$ и уменьшите первую на $\varepsilon>0$, а вторую увеличьте на такое число, чтобы равенство сохранилось. Теперь посмотрите, что при этом произойдет с целевой функцией, увеличится ли она или уменьшится. Это покажет, по какому критерию нужно упорядочить переменные, чтобы затем последовательно их занулять.

Видимо я не точно сформулировал задачу: это $U_i\in \left\{0,1\right\}$ означет, что $U_i$ либо ноль, либо единица (т.е. задача целочисленная по $U_i$). Еще пояснение: $A_i$ таковы, что ограничение даже при оптимальном решении все равно может не быть активным (т.е. равенства может и не быть, а будет просто знак $>$).

[Zo]

Zo писал(а):

Привет, нужны соображения по поводу решения такой задачи:
$\sum\limits_{i=1}^n X_i\cdot U_i \to min$
Ограничение: $\sum\limits_{i=1}^n A_i\cdot U_i \geqslant V$,
где все $U_i\in \left\{0,1\right\}$, а $A_i\in R$,$X_i\in R$,
$A_i>0$,$X_i>0$,$V>0$
И естественно $\sum\limits_{i=1}^n A_i\geqslant V$
Оптимизация идет по $U_i$

Окзалось, что все сводится в итоге к такой задаче:
Остается k пар ($k<n$) вида:
($X_i$,$A_i$), для которых при j>i выполнено: $X_i< X_j$ и $A_i<A_j$
И надо выбрать $U_i$ так чтобы:
$\sum\limits_{i=1}^k X_i \cdot U_i \to min$
и было выполнено ограничени: $\sum\limits_{i=1}^k A_i \cdot U_i \ge \tilde{V}$
По-прежнему $U_i\in \left\{0,1\right\}$ (то есть либо ноль, либо единица), а $A_i\in R$,$X_i\in R$,
$A_i>0$,$X_i>0$,$V>0$
И естественно $\sum\limits_{i=1}^k A_i\geqslant \tilde{V}$
Какие будут идеи ?

[Zo]

Вобщем дальше так ничего и не смог придумать "своего". Но вроде с динамическим программированием получше разобрался -с помощью него решается без полного перебора.
А PAV спасибо за проявленное внимание

[PAV]

Если не сложно, напишите, пожалуйста, в двух словах, как применяется динамическое программирование к данной задаче. Что-то сходу не соображу.

[Zo]

PAV писал(а):

Если не сложно, напишите, пожалуйста, в двух словах, как применяется динамическое программирование к данной задаче. Что-то сходу не соображу.

Получилось так: от этой задачи
$\sum\limits_{i=1}^n X_i\cdot U_i \to min$
Ограничение: $\sum\limits_{i=1}^n A_i\cdot U_i \geqslant V$,
переходим к эквивалентной через замену $\tilde {U_i}=1-U_i$ (просто если исходную решать, то у меня не вышло ничего и с динамическим программированием)
Получается: $\sum\limits_{i=1}^n X_i\cdot \tilde{U_i} \to max$
Ограничение: $\sum\limits_{i=1}^n A_i\cdot \tilde{U_i} \leqslant \sum\limits_{i=1}^n A_i - V$,
Обозначим $M=\sum\limits_{i=1}^n A_i - V$
Дальше из книжки Ковалева "Дискретная оптимизация" взято:
(перед этим ограничение задачи приводится к виду, чтобы все $A_i$ и $M$ были целыми):
Вводим $F_k(y)=max \left\{ \sum\limits_{i=1}^k X_i \cdot \tilde{U_i} \left| \sum\limits_{i=1}^k A_i \cdot \tilde{U_i} \le y \right\}$
и итоговое рекуррентное соотношение ($k=1 \dots n , y=0 \dots M$):
$F_k(y)=max \left\{ X_k \cdot \tilde{U_k}+F_{k-1}(y-A_k \cdot \tilde{U_k})\right\}$
где максимум берется по $\tilde{U_k} \in \left\{ 0,1 \right\}$
Т.е. численно только получается. Аналитически не решилось.

[V.V.]

А Вы не исследовали, сколько операций получается при динамическом программировании?

[Zo]

V.V. писал(а):

А Вы не исследовали, сколько операций получается при динамическом программировании?

n*M операций (где М- целое число, получающееся после приведения ограничения задачи к виду, когда все $A_i$ и $M$ - целые).
Проблема в том, что преподавателю, который дал мне такое задание, не нравится вышеуказанный подход - он говорит, что надо использовать попятную процедуру, а мне кажется, что так, как я написал выше - проще.