2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Оптимизационная задача
Сообщение28.04.2006, 21:40 


19/07/05
243
Привет, нужны соображения по поводу решения такой задачи:
$\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 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение29.04.2006, 13:02 


19/07/05
243
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 


19/07/05
243
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 


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

 Профиль  
                  
 
 
Сообщение02.05.2006, 17:52 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение03.05.2006, 14:00 


19/07/05
243
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 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение06.05.2006, 21:59 


19/07/05
243
V.V. писал(а):
А Вы не исследовали, сколько операций получается при динамическом программировании?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group