2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Система линейных уравнений и неравенств
Сообщение21.07.2017, 03:22 


21/07/17
2
Добрый день.
Оригинальная задача:
Дан направленный ациклический граф с единственной точкой входа A (нет входящих ребр) и единственной точкой выхода B (нет исходящих ребр). Для каждого ребра указаны его min и max веса (не отрицательные). Также дан некий общий вес W. Необходимо определить веса x всех ребер (с учетом их min и max) так, чтобы вес любого маршрута из A в B был равен W.
Кроме того, заданы несколько желаемых (могут быть невыполнимы из-за ограничений на веса ребр) соотношений весов ребр вида $\frac{x_a}{L_a} = \frac{x_b}{L_b} = \dots \frac{x_c}{L_c}$.
Примечание 1: Если из-за соотношений весов вес ребра выходит за его допустимые границы, то вес этого ребра следует принять равным соответствующей границе (min или max) и исключить это ребро из желаемых соотношений весов (тем не менее, остальные пропорции должны сохраняться как и вес маршрута A->B).
Примечание 2: Если не учитывать направления ребр, то граф может содержать циклы.

Вот к чему свел:
$x_1 \dots x_n$ - искомые неизвестные
Дано:
1) система линейных уравнений
$$\left\{
\begin{array}{rcl}
k_{1,1} \cdot x_1 + \dots + k_{1,n} \cdot x_n &=& w_1 \\
\dots \\
k_{m,1} \cdot x_1 + \dots + k_{m,n} \cdot x_n &=& w_m \\
\end{array}
\right.$$
(k и w известны).
, причем $m<n$
Если это поможет, то можно представить эту систему в виде
$$\left\{
\begin{array}{rcl}
K_{1,1} \cdot x_1 + \dots + K_{1,n} \cdot x_n &=& W \\
\dots \\
K_{m,1} \cdot x_1 + \dots + K_{m,n} \cdot x_n &=& W \\
\end{array}
\right.$$
, причем K = 0 или K = 1, т.е. сумма некоторых равна константе, W \geqslant 0.

2) ограничения на каждую переменную (система неравенств)
$$\left\{
\begin{array}{rcl}
\min_1 \leqslant x_1 \leqslant \max_1 \\
\dots \\
\min_n \leqslant x_n \leqslant \max_n \\
\end{array}
\right.$$
(min и max известны)
, причем в совокупности с системой "1" имеется хотя бы одно решение (а как правило их больше одного), \min \geqslant 0.

3) система линейных уравнений
$$\left\{
\begin{array}{rcl}
l_{1,1} \cdot x_1 + \dots + l_{1,n} \cdot x_n &=& 0 \\
\dots \\
l_{p,1} \cdot x_1 + \dots + l_{p,n} \cdot x_n &=& 0 \\
\end{array}
\right.$$
(l известны)
, причем $m+p > n$ (если говорить более детально, то в каждом из этих уравнений строго 2 ненулевых коэффициента l). На самом деле эти уравнения получены из заданных соотношений вида $\frac{x_a}{L_a} = \frac{x_b}{L_b} = \dots \frac{x_c}{L_c}$

Задача:
найти такие $x_1 \dots x_n$, что:
- все уравнения из "1" строго выполняются
- все ограничения из "2" строго выполняются
- максимальное количество уравнений из "3" выполняются (уравнения в "3" приведены в порядке их "предпочтительности", т.е. в случае необходимости исключать их следует начиная с последнего).

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

Проблемы:
Не ясно что делать с min & max: без них все сводится к системе линейных уравнений, в которой, правда, могут быть противоречия (желаемые соотношения весов могут иметь противоречия друг с другом) с которыми тоже надо что-то делать. Кроме того, количество ребер может исчисляться тысячами и требуется пересчитывать веса до пары сотен раз в секунду (граф меняется редко, обычно только W).
Буду рад подсказкам.

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение21.07.2017, 12:27 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
Первый вариант задача целочисленного ЛП.
Систему $3)$ заменяете, соответственно, на неравенства.
Насколько компьютер "потянет" Вашу задачу, не могу сказать, надо пробовать.
Закиньте в какой-нибудь пакет, типа glpk.
Второй вариант как-то не соображу, как можно формализовать "уравнения из "3" (или часть из них) должны строго выполняться" - только если все. Будет просто задача ЛП, она-то точно должна за разумное время считаться.
Можно еще подумать в сторону как-нибудь свести к задачам ЛП специального вида, типа min-cost-flow, для таких есть существенно более быстрые алгоритмы.

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение21.07.2017, 13:06 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
На ЗЛП не очень похоже, потому что не видать целевой функции (которую нужно минимизировать или максимизировать).

Ну, точнее, можно попробовать увидеть. Если все левые части в 3) возвести в квадрат и просуммировать. Или модули просуммировать. И сумму объявить целевой функцией, подлежащей минимизации. Только, во-первых, она линейной не будет. Если в квадрат возводить, то получается классическая задача квадратичного программирования с ограничениями. Есть методы для её решения, и программные пакеты тоже есть. А во-вторых, ну решим мы эту ЗКП, получим, что 3) выполняется с какими-то погрешностями, но, боюсь, что ни одно уравнение в точности не выполняется, а тут нужно, чтобы хоть какие-то точно выполнились. Ну и в-третьих, дискретность (целочисленность) всё портит, градиентные методы стройными рядами отправляются на север. Не выходит каменный цветок :|

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение21.07.2017, 13:39 


14/01/11
2916
worm2 в сообщении #1235100 писал(а):
На ЗЛП не очень похоже, потому что не видать целевой функции (которую нужно минимизировать или максимизировать).

Эм, что нам мешает взять, например, любое $x$ и оптимизировать его? :-)

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение21.07.2017, 13:43 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
glpk, например, отсутствие minimize/maximize ни разу не смущает.
Типа, равна 0.

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение24.07.2017, 21:18 


21/07/17
2
Спасибо всем за участие, но если честно, я не понял как сюда привязать ЗЛП, ведь в ней нужно находить минимум некой функции.
Зато я сделал следующее наблюдение: если получится решить в нецелых, то получить решение в целых из него будет легко.
Хочу сделать некоторые допущения, может быть тогда станет ясно как решать:
1. Решать можно и в нецелых,
2. Забыть на ограничения переменных сверху (т.е. от 2) остается только $\min_i \leqslant x_i$),
3. Считать что 3) дополняют 1) до n непротиворечивых уравнений (т.е. 1) + 3) имеют однозначное решение).
Текущая проблема:
После решения системы 1) + 3) получаем некое решение. Что делать, если некие $x_i<\min_i$? Взять все $x_i=\min_i$ в общем случае нельзя (легко построить пример, опровергающий такое способ). Что с этим делать? Вероятно, надо нужно взять некоторые (не всегда все) $x_i=\min_i$, заменить ими некоторые (какие пока не ясно) уравнения в 3) и повторить снова решать систему 1) + 3). Есть идеи?

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение25.07.2017, 12:17 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Можно попробовать такую вещь:
I) Отказываемся от последнего уравнения $l_{p,1} \cdot x_1 + \dots + l_{p,n} \cdot x_n = 0$. В результате получаем прямую в $\mathbb{R}^n$, на которой лежат решения системы 1)+3): $\overrightarrow{x}=\overrightarrow{a}+\overrightarrow{b}\cdot t,\,t \in \mathbb{R}$.
II) На этой прямой отмечаем точки, соответствующие $x_i=\min_i$. Выбираем из них точку, в которой выполняется максимальное число ограничений 2). Пусть это точка, в которой $x_j=\min_j$. Фиксируем $x_j=\min_j$. Если какие-то ограничения в 2) ещё не выполнены, повторяем итерацию для меньшего числа неизвестных.
Получается алгоритм сложности $n^4$.
Хотя, можно ещё попробовать подшаманить: не решать на каждом шаге систему полностью заново, а как-то использовать информацию, полученную на предыдущем шаге. Я пока не соображу, как это сделать, нужно препарировать метод Гаусса. Но если получится, то будет $n^3$.

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение25.07.2017, 12:52 


14/01/11
2916
unsa в сообщении #1235724 писал(а):
Спасибо всем за участие, но если честно, я не понял как сюда привязать ЗЛП, ведь в ней нужно находить минимум некой функции.

Собственно, тут от ЗЛП требуется только алгоритм поиска опорного решения, разве нет?

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение25.07.2017, 13:47 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
unsa в сообщении #1235724 писал(а):
Спасибо всем за участие, но если честно, я не понял как сюда привязать ЗЛП, ведь в ней нужно находить минимум некой функции.

А что Вас смущает? Ну, положите эту функцию равной $0$.
glpk, повторюсь, целевая функция не обязательна, он и без нее чудненько все считает.
Думаю, что и другие пакеты так же.
unsa в сообщении #1235724 писал(а):
Зато я сделал следующее наблюдение: если получится решить в нецелых, то получить решение в целых из него будет легко.

Ну, значит, Вам повезло, у Вас "хорошая" задача.
Обычно так не бывает.
unsa в сообщении #1235724 писал(а):
3. Считать что 3) дополняют 1) до n непротиворечивых уравнений (т.е. 1) + 3) имеют однозначное решение).

А если такой вариант: считать целевой функцией сумму модулей левых частей $3)$?
Если Вам целочисленность не обязательна, получаем просто задачу ЛП.

 Профиль  
                  
 
 Re: Система линейных уравнений и неравенств
Сообщение26.07.2017, 07:28 
Заслуженный участник
Аватара пользователя


03/06/08
2147
МО
Если все-таки нужно, чтобы те из уравнений $3)$, которые выполняются, выполнялись точно, то тоже можно, но тогда надо вводить бинарные переменные (грубо говоря, маркеры ноль-не ноль, сумму их устремляем к минимуму), т.е. опять-таки целочисленная задача :(
Вообще, конечно, я бы покрутил разные варианты и посмотрел результат.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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