Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Математическая модель задачи имеет вид
(9) H = ∑ f(i,j)*h(i,j) à min
| ∑ f(s,j) - ∑ f(l,s) = 1, s - источник, | (10) | ∑ f(i,j) - ∑ f(k,i) = 0,, ∀ i∈X, i≠s, i≠t, | | ∑ f(t,j) - ∑ f(k,t) =-1, t - сток,
(11) f(i,j) >= 0 ∀ (i, j) ∈ U.
Здесь условия (10) - условия сохранения 1ед. потока пропущенного через сеть,а, значит,выделение ориентированных цепей из s в t с дугами веса 1. Согласно (9) из всех таких цепей выбирается цепь наименьшего веса.
Во втором случае строится дерево кратчайших путей.
(12) H = ∑ f(i,j)*h(i,j) à min
| ∑ f(s,j) = st(s), s - источник, (13) | ∑ f(l,i) = 1,, ∀ i∈X, i≠s,
(14) f(i,j) - двоичные ∀ (i, j) ∈ U. (15) ∑ f(i,j) = n -1, n-число вершин графа.
Здесь n – число вершин графа, l – номер вершины, предшествующей вер- шине i, h(i, j) – стоимость передачи потока по дуге (i, j), f(l,i) – поток, входя- щий в вершину i по дуге (l, i).
В двойственной задаче о кратчайшем пути определяются потенциалы вершин pi, представляющие собой расстояния от вершины источника до вер- шины i. Необходимо найти минимальные значения pi. При этом не имеет смысла разделять задачи нахождения кратчайщего пути и построения дерева кратчайших путей, так как длина кратчайшего пути из источника в сток совпа- дает со значением потенциала стока, а чтобы найти последний требуется определить потенциалы все предшествующих вершин. В двойственной задаче целевая функция максимизируется. Математическая модель задачи, составленная по правилам перехода к двойственной задаче линейного программирования выглядит следующим образом:
(16) P = ∑ pi à max
(17) pj - pi <= hk, k = 1,..m;
(18) pj – не ограничены, ps = 0.
Здесь n - число вершин, m - число дуг.
ПОСТАНОВКА ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ
Мы уже дали ранее определение потока на ориентированном графе со взвешенными дугами (то есть в сети). Поток наибольшей величины называет ся максимальным потоком.Определение потока и дает ограничения задачи ли- нейного программирования, которая соответствует задаче отыскания макси- мального потока в сети. С учетом целевой функции математическая модель выглядит так:
P = ∑ f(s, k) à max (s –источник) (s,k) ∈ U
∑ f(k, i) = ∑f(i,l), I ∈ X, (k,i) ∈U (I,l) ∈U
f(i, j) >= 0 ∀ (i, j) ∈ U.
|