FAQ Поиск Пользователи Группы ФотоАльбом  Регистрация Войти и проверить личные сообщения Вход
[алгоритм ?] фиксированный поток минимальной стоимости

 
Начать новую тему   Ответить на тему       Список форумов Forum.profintel.ru -> Программерский раздел
Предыдущая тема :: Следующая тема  
Автор Сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Вт Фев 09, 2010 1:30 pm    Заголовок сообщения: [алгоритм ?] фиксированный поток минимальной стоимости Ответить с цитатой

Уже несколько месяцев думаю над задачей: "найти сопротивление произвольной цепи резисторов". Цепь уже приведена к виду, где нет последовательных и параллельных соединений, а следовательно свести её просто к сочетанию последовательных и паралллельно соединённых резисторов нельзя. Пример простейшей такой схемы на рисунке (я проставил конкретные номиналы для примера, они могут быть совершенно произвольными). Пусть точка А будет исток, а точка D - сток. Ток течёт из A в D так, чтобы минимизировать сопротивление, но при этом протечь всему.

Суть задачи сводится к следующему раставить вдоль каждой участка цепи долю тока (от общего пропущенного тока), так чтобы цена прохода вдоль любого пути от источника до стока была одинаковой. Цена прохода вдоль какого либо участка - это произвдение тока на сопротивление (iR). Произведение iR называется также падением напряжения или потенциалом.

Вообще данную схему легко решить на бумаге используя нехитрые принципы:
1. Сумма втекающего тока равна сумме истекающего в каждом узле:
iAB * I + iAC * I = I (ток вытекающий из источника равен току втекающему в источник - т.е. общему току, здесь I - общий ток, iAB, iAC - доли тока пущеных по АВ и АС, далее будет считать I = 1 и опускать её)
iCB + iCD = iAC
iBD = iAB + iCB
iBD + iCD = 1 (весь вытекающий ток равен общему току)
2. Величина потенциала в каждом узле не зависит от пути по которому мы в неё пришли
Для вершины D:
iAB * RAB + iBD * RBD = U[D]
iAC * RAC + iCB * RCB + iBD * RBD = U[D]
iAC * RAC + iCD * RCD = U[D]
U[D] нам неизвестно (её и надо найти), но комбинируя эти уравнения можно исключить U[D]
Для вершины B
iAB * RAB = U
iAC * RAC + iCB * RCB = U[B]

Как видно уравнений более чем достаточно, чтобы решить систему, правильный ответ:
iAB = 38/55
iAC = 17/55
iCB = 4/55
iBD = 42/55
iCD = 13/55

Но если возникает потребность "решить" схему где тысячи резисторов и каждый соединён с 5 - 8 другими, то решать на бумаге как-то не хочется.

[b]Замечание.
В приведённой задаче изначально указаны правильные направления движений токов. Понятно что все токи вытекают из истока, и все втекают в сток, так направления AB, AC, BD, CD известны. Но вот про BC мы такое заранее сказать не можем. Решая систему уравнений можно допустить любое направление, тогда отрицательная величина будет указывать на то, что нужно сменить направление. Для разрабатываемого алгоритма допустим, что все направления нам известны.

Некоторые соображения:

1. Первое что приходит в голову - составить систему уравнений вида
с11 * i1 + c12 * i2 + c13 * i3 + .... = A1,
c21 * i1 + c22 * i2 + c23 * i3 + .... = A2,
...
и решить её [url=http://ru.wikipedia.org/wiki/Метод_Крамера]методом Крамера[/url], но как видно из текста выше получаются в основном уравнения где Ai = 0 (кроме тех, что с единицей - их всего два) и вообще в каждом уравнении очень часто будут встречаться нулевые коэффициенты (в настоящем примере можно составить только одно уравнение, где только один из 5 коэффициентов будет ненулевым). А чтобы решить уравнения методом Крамера, нужно чтобы определители матриц составленных из коэффициентов с и А были ненулеввые), для наших систем это маловероятно.

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

В данных алгоритмах для каждого ребра вводится пропускная способность - максимальная величина потока который может пройти через это ребро. Попробуем приспособить их решения к нашему. Введём пропускные способности равные 1 (т. к. мы измеряем поток в долях от общего тока), а стоимость единичного потока через ребро зададим равной сопротивлению), то алгоритмы максимального потока быстро нам дадут ответ iAB = iBC = iAC = iCD = 1, что неверно, даже если мы нормируем потом на суммарный исток.


3. Попробовать устроить что-то типа последовательных приближений:

1. Сначала пустим весь ток вдоль пути наименьшего сопротивления (ABD) (эти пути легко искать элементарными алгоритмами типа Дейкстры),

2. затем попробуем пустить часть потока через AC - тогда ближайшая точка по сопротивлениям вдоль уже известного пути - это B. Попробуем перенормировать потоки так, чтобы U[A] + (iAB - x) * RAB = U[A] + (iAC + x) * (RAC + RCB) - для начала допустим что весь ток потечёт из С в B.
Уравнение легко решается и мы получаем потоки текущие через AB и AC.

3. Переходим в следующую точку ветвления - C. Теперь решаем уравнение аналогичное предыдущему:
UB + (iBD - x) * RBD = U[C] + (iCD + x) * RCD
находим токи текущие через BD и CD.

4. Но своим решением мы исказили UB - возвращаемся в начало и коректируем потоки AC и AB по аналогичному уравнению, но учитывая уже то, что ток из С не весь потечёт в В, а толко какая-то часть (допустим из соотношения iCB/(iCB + iCD) полученного входе пред. итерации)

5. Снова идём в точку C и решаем уравнение из 3 шага.

Повторяем шаги 4, 5 пока не выполнится какой-нибудь критерий приближённого решения.

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

Буду очень признателен какой-либо помощи

_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
ant_man
Майор


Репутация: 28    

Зарегистрирован: 08.03.2003
Сообщения: 1187
Откуда: с ВИЗа

СообщениеДобавлено: Вт Фев 09, 2010 7:35 pm    Заголовок сообщения: Ответить с цитатой

http://ru.wikipedia.org/wiki/Метод_Гаусса
?

_________________
Надо же... живу...
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Вт Фев 09, 2010 10:40 pm    Заголовок сообщения: Ответить с цитатой

ant_man, спасибо. Решил методом Гаусса данную систему в экселе. Правда там зависит от того какие уравнения взять. Первый раз взял на бумаге и там два уравнения свелись к одному, второй раз взял другие - но где-то видимо ошибся, поэтому набил табличку в экселе и давай решать там.

Вообщем сейчас буду думать алгоритм составления уравнений, так чтобы система решалась. + надо ещё подумать вообще всегда ли систему можно решить методом Гаусса.

_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
AlexSYS
Ст. Сержант


Репутация: 14    

Зарегистрирован: 18.03.2008
Сообщения: 143
Откуда: ВИЗ, Екатеринбург

СообщениеДобавлено: Ср Фев 10, 2010 10:17 pm    Заголовок сообщения: Ответить с цитатой

Wizard RAA,
это чисто научный интерес или для практического применения?

В институте решал подобные задачи - расчёт электрического режима (нахождение напряжения в каждом узле и величина перетоков по каждому участку цепи).

p.s. велосипед давно изобретён и на нём уже давно катаются.

_________________
С уважением AlexSYS
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Чт Фев 11, 2010 11:34 pm    Заголовок сообщения: Ответить с цитатой

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

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


ant_man,
спасибо Метод Гаусса подошёл, сегодня несколько часов боя с "Се два плюс" и получил прогу, выдающее решение.
Готов выразить благодарность материально: ну там пиво или ещё что))))

_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
AlexSYS
Ст. Сержант


Репутация: 14    

Зарегистрирован: 18.03.2008
Сообщения: 143
Откуда: ВИЗ, Екатеринбург

СообщениеДобавлено: Пт Фев 12, 2010 8:13 pm    Заголовок сообщения: Ответить с цитатой

Wizard RAA,
а если в цепи будут произвольные элементы (резисторы, ёмкости, индуктивности), то тогда как? Wink

_________________
С уважением AlexSYS
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Пт Фев 12, 2010 10:32 pm    Заголовок сообщения: Ответить с цитатой

AlexSYS, ну я думаю если ток переменный, то ёмкости и индуктивности можно заменить на резисторы, например Rc = 1/2/pi/w/C

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

гораздо интереснее когда в цепи есть ещё источники, вот это пожалуй посложнее фича....

AlexSYS, Однако если Вам не жалко можете изложить свои мысли по поводу алгоритмов.

_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
ant_man
Майор


Репутация: 28    

Зарегистрирован: 08.03.2003
Сообщения: 1187
Откуда: с ВИЗа

СообщениеДобавлено: Пт Фев 12, 2010 11:59 pm    Заголовок сообщения: Ответить с цитатой

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

http://ru.wikipedia.org/wiki/Законы_Кирхгофа

_________________
Надо же... живу...
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
AlexSYS
Ст. Сержант


Репутация: 14    

Зарегистрирован: 18.03.2008
Сообщения: 143
Откуда: ВИЗ, Екатеринбург

СообщениеДобавлено: Сб Фев 13, 2010 12:29 am    Заголовок сообщения: Ответить с цитатой

Wizard RAA,
Цитата:
Суть задачи сводится к следующему раставить вдоль каждой участка цепи долю тока (от общего пропущенного тока), так чтобы цена прохода вдоль любого пути от источника до стока была одинаковой. Цена прохода вдоль какого либо участка - это произвдение тока на сопротивление (iR). Произведение iR называется также падением напряжения или потенциалом.

не совсем понятна цель.

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

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

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

_________________
С уважением AlexSYS
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Сб Фев 13, 2010 2:00 pm    Заголовок сообщения: Ответить с цитатой

ant_man, у меня как раз и решается по законам Кирхгофа с помощью метода Гаусса. Smile


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

_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Табуреткин Петя
Подполковник


Репутация: 105    

Зарегистрирован: 10.11.2007
Сообщения: 1797
Откуда: :адуктО

СообщениеДобавлено: Сб Фев 13, 2010 3:37 pm    Заголовок сообщения: Ответить с цитатой

Surprised Вроде университет не так давно закончил, но все позабыл совсем. Шарите, молодцы!
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
AlexSYS
Ст. Сержант


Репутация: 14    

Зарегистрирован: 18.03.2008
Сообщения: 143
Откуда: ВИЗ, Екатеринбург

СообщениеДобавлено: Сб Фев 13, 2010 8:58 pm    Заголовок сообщения: Ответить с цитатой

Wizard RAA,
для расчёта эквивалентного сопротивления необязательно рассчитывать электрический режим.

Если в данной схеме из пяти элементов преобразовать "треугольник" в "звезду" - получится последовательно-параллельное соединение элементов.

Попробуй Метод узловых потенциалов.

_________________
С уважением AlexSYS
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Вт Фев 16, 2010 12:10 pm    Заголовок сообщения: Ответить с цитатой

Да, действительно, эту схему можно упроситить, правда в википедии написано что для этого Rab/Rbd <> Rac/Rcd, что в общем случае не так. И я не знаю, если будет несколько сопряжённых треугольников можно ли использовать такой трюк.
_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
AlexSYS
Ст. Сержант


Репутация: 14    

Зарегистрирован: 18.03.2008
Сообщения: 143
Откуда: ВИЗ, Екатеринбург

СообщениеДобавлено: Ср Фев 17, 2010 10:07 pm    Заголовок сообщения: Ответить с цитатой

Wizard RAA,
забудь на время википедию, обратись к обычной литературе.
Например: Касаткин А.С. Электротехника.Учебник для вузов.

p.s. я не считаю википедию источником информации, слишком много ошибок встречается.

_________________
С уважением AlexSYS
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Wizard RAA
Генерал


Репутация: 41    

Зарегистрирован: 17.03.2005
Сообщения: 3010
Откуда: из Ордена Полуночи, 248 сегмент

СообщениеДобавлено: Вт Апр 06, 2010 2:37 pm    Заголовок сообщения: Ответить с цитатой

AlexSYS, согласен Smile
_________________
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Показать сообщения:   
Начать новую тему   Ответить на тему       Список форумов Forum.profintel.ru -> Программерский раздел Часовой пояс: GMT + 6
Страница 1 из 1

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете вкладывать файлы
Вы не можете скачивать файлы