2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Оптимизационная задача
Сообщение28.04.2006, 21:40 
Привет, нужны соображения по поводу решения такой задачи:
$\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$ больше занулить нельзя, то решение получено. Но это неверный метод. Вопрос что делать, как быть, как избежать прямого перебора (про метод Гомори знаю, но надо без него). Пожалуйста, подскажите. Интересны любые соображения.

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

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

 
 
 
 
Сообщение29.04.2006, 13:02 
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$ таковы, что ограничение даже при оптимальном решении все равно может не быть активным (т.е. равенства может и не быть, а будет просто знак $>$).

 
 
 
 Re: Оптимизационная задача
Сообщение30.04.2006, 13:49 
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}$
Какие будут идеи ;-) ?

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

 
 
 
 
Сообщение02.05.2006, 17:52 
Аватара пользователя
Если не сложно, напишите, пожалуйста, в двух словах, как применяется динамическое программирование к данной задаче. Что-то сходу не соображу.

 
 
 
 
Сообщение03.05.2006, 14:00 
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\}$
Т.е. численно только получается. Аналитически не решилось.

 
 
 
 
Сообщение06.05.2006, 11:18 
А Вы не исследовали, сколько операций получается при динамическом программировании?

 
 
 
 
Сообщение06.05.2006, 21:59 
V.V. писал(а):
А Вы не исследовали, сколько операций получается при динамическом программировании?

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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group