ФЭА / АИТ / Лабораторная работа №4 по дисциплине «Моделирование систем» на тему «Математические расчеты на базе MATLAB. Максимальный поток в сети»
(автор - student, добавлено - 7-04-2014, 13:17)
СКАЧАТЬ:
Максимальный поток в сети Задача о максимальном потоке как задача линейного программирования Сетью называется орграф со взвешенными дугами и с выделенными в нем двумя вершинами, одна из которых называются источником сети, а другая -стоком. Обычно вершину-источник обозначают буквой s, а сток t. Как правило, из s только выходят дуги, а в t только входят, но это не обязательно. Из s в t ведут разные пути по дугам разного веса. Неотрицательные веса дуг будем обозначать ск. В задаче о максимальном потоке вес каждой дуги рассматривается как ограничение на ее пропускную способность. Для каждой дуги eк введем в рассмотрение ассоциированную с ней переменную, которую также обозначим eк. Ее смысл: это реальная величина потока в данной дуге. Поток в дуге eк неотрицательный и не превышает пропускную способность ск в этой дуге: (1) В задаче о максимальном потоке, как следует из ее названия, требуется максимизировать суммарный поток, выходящий из источника s при условии, что во всех промежуточных вершинах (кроме s и t) сумма входящих и выходящих потоков должна быть равна нулю. Из общего баланса потоков следует, что поток в t будет отличаться от потока в s только знаком: ведь ни в дугах, ни в промежуточных вершинах ничего не задерживается! Примером такой задачи является построение схемы развозки товара со склада s в магазин t по улицам с ограничением транспортного потока. По каким маршрутам и сколько машин направить, чтобы максимизировать количество доставленного за данное время товара? В этой задаче считается, что нигде на маршруте товар не задерживается: ни на улицах (дугах), ни на перекрестках (промежуточных вершинах).
Задача о максимальном потоке в сети с ограниченными пропускными способностями допускает формулировку в терминах линейного программирования. Мы уже ввели переменные eк и ограничения на них(1). Введем также в рассмотрение матрицу инцидентности орграфа А. Она похожа на матрицу инцидентности графа, но в ней есть не только единицы, но и -1. А именно: будем полагать аik= 1,если из вершины vi выходит дуга eк, и аek = -1, если в вершину vi входит дуга eк. Например, матрица инцидентности орграфа с рис. 1, имеет вид: (2) В каждом столбце этой матрицы по одной единице и по одной -1, поэтому сумма всех строк — нулевая строка. Это соответствует общему балансу потоков. Для матрицы инцидентности орграфа А обозначим:
Тогда максимизируемая целевая функция — общий поток из источника. Она может быть записана так: (3) где е — век тор-столбец переменных eк. А условие баланса потоков во всех промежуточных вершинах записывается в виде ограничения-равенства: Аste=0 (4) Вместе с ограничениями (1) выражения (3-4) определяют задачу линейного программирования, причем даже не целочисленную, а обычную, т. к. потоки в дугах могут быть дробными.
2. Описание процедуры MaxFlows В инструментарии MATLAB есть процедура linprog для решения задачи линейного программирования. Поэтому процедура MaxFlows, которую мы сейчас опишем, фактически является интерфейсом между формулировкой задачи и вызовом процедуры linprog. Для работы MaxFlows нужно задать входной параметр— список дуг орграфа и их веса. Как обычно, будем использовать массив размером тx2 или тx3, которому в процедуре соответствует идентификатор Е. В третьем его столбце — веса дуг. Если пользователь их не задал, будем считать их единичными. Нужно также задать номера вершин источника и стока. На выходе мы должны получить вектор длины т потоков в дугах и суммарный максимальный поток из источника (вершины s). Пишем заголовок и справочную информацию. Function [v,mf]=MaxFlows(E,s,t) % Функция [v,mf]=MaxFlows(E,s,t) решает задачу о максимальном потоке % в сети с ограниченными пропускными способностями. % Входные параметры: % Е (m,2) или (m,3) — дуги орграфа и их веса; % 1-й и 2-й элементы каждой строки — это номера вершин; % 3-й элемент каждой строки — это вес дуги; % m — количество дуг % Если задан массив Е (m,2), то все веса равны 1. % s — источник сети (номер вершины) ; % t — сток сети (номер вершины) . % Выходные параметры: % v(m,1) — вектор-столбец потоков в дугах; % mf- общий максимальный поток в сети. % Используется сведение к задаче линейного программирования . Проверяем исходные данные. Вначале проверяем наличие данных, размерность и количество столбцов входного массива, положительность и целочисленность первых двух столбцов. if nargin<3, error('Нет исходных данных') end sz=size(E); if length(sz)~=2, error('Массив Е должен быть двумерным') end if (sz(2)<2), error('В массиве Е должно быть 2 или 3 столбца'), end if ~all(all(E(:,1:2)>0)), error('1-й и 2-й столбцы массива Е должны быть положительными') end if ~all(all((E(:,1:2)==round(E(:,1:2))))), error('1-й и 2-й столбцы массива Е должны быть целыми') end Из вершины с номером s обязательно должны выходить дуги, а в вершину с номером t — входить. Проверяем это. if ~ismember(s,E(:,1)), error(['Из вершины номер s=' num2str(s) ' не выходит ни одной дуги']) end if ~ismember(t,E(:,2)), error(['В вершину номер t=' num2str(t) ' не выходит ни одной дуги']) end Находим размер и мощность орграфа. Если пользователь не задал веса дуг, задаем их единичным. m=size(E,1); n=max(max(E(:,1:2))); if sz(2)==2, E(:,3)=1; end Строим матрицу инцидентности орграфа вида (2). Вначале она состоит из одних нулей. Затем записываем 1 и -1 на нужные места. A=zeros(n,m);% для матрицы инциденции for k=1:m, % просматриваем все дуги A(E(k,1),k)=1; % если из вершины выходит дуга A(E(k,2),k)=-1; % если в вершину входит дуга end
Для системы ограничений-равенств (4) удаляем из матрицы инцидентности строки с номерами s и t. Aeq=A(setdiff([1:n],[s t]),:); % баланс потоков в промежуточных вершинах Вектор коэффициентов в целевой функции (3)— это s-я строка матрицы А. Мы берем ее со знаком "минус", т. к. процедура linprog решает задачу минимизации. f=-A(s,:)'; % коэффициенты в целевой функции Настраиваем опции для процедуры linprog. Нам не нужно выдавать на экран сообщения, поэтому подавляем вывод. options=optimset('linprog');% опции по умолчанию options.Display='off'; % подавляем вывод И наконец, решаем задачу линейного программирования и находим общий поток из источника v=linprog(f,[],[],Aeq,zeros(size(Aeq,1),1),... zeros (m,1),E(:,3),[],options); mf=-f'*v; return
3. Пример обращения к процедуре MaxFlows Продемонстрируем порядок обращения к процедуре MaxFlows. Используем граф с взвешенными дугами и невзвешенными вершинами (рис. 1).
рис.1. Исходный граф с взвешенными дугами clear all V=[[0 0];[1 1];[1 0];[1 -1];… [2 1];[2 0];[2 -1];[3 1];... [3 0];[3 -1];[4 0]]; %координаты вершин E=[[1 2 5];[1 3 5];[1 4 5];[2 3 2];[3 4 2];[2 5 3];… [2 6 2];[3 6 5];[3 7 2];[4 7 3];[6 5 1];[6 7 1];… [5 8 5];[6 8 2];[6 9 3];[7 9 2];[7 10 3];[8 9 2];… [9 10 2];[8 11 5];[9 11 4];[10 11 4]]; % ребра и их веса PlotGraph(V,E,'0'); %рисуем граф set(get(gcf,'CurrentAxes'),'FontName','Times New Roman Cyr','FontSize',10) title('\bfИсходный орграф'). Пусть источник s – это вершина, а сток t-v11. Зададим их. Решим задачу о максимальном потоке и напечатаем решение: потоки в дугах и общий максимальный поток из источника. На рисунке (рис. 2) изобразим наш орграф, у которого вместо весов дуг покажем потоки в них.
s=1; % источники сети t=11; % сток сети fprintf('Источник сети s=%d\nСток сети t=%d\n',s,t) [v,mf]=MaxFlows(E,s,t); % решаем задачу disp('Решение задачи о максимальном потоке в сети') disp(' N дуги поток') fprintf(' %2.0f %12.8f\n',[[1:length(v)];v']) fprintf('Максимальный поток =%12.8f\n',mf) PlotGraph(V(:,1:2),[E(:,1:2),v],'0'); % рисуем, пишем потоки в дугах set(get(gcf,'CurrentAxes'),'FontName','Times New Roman Cyr','FontSize',10) title('\bfПотоки в дугах').
Решение задачи о максимальном потоке в сети N дуги поток 1 5.00000000 2 5.00000000 3 3.00000000 4 0.63432629 5 0.00000000 6 2.79872259 7 1.56695111 8 4.12415344 9 1.51017285 10 3.00000000 11 0.93404510 12 0.17003857 13 3.73276770 14 1.85198251 15 2.73503838 16 1.86897174 17 2.81123968 18 0.58475020 19 1.18876032 20 5.00000000 21 4.00000000 22 4.00000000 Максимальный поток = 13.00000000
рис.2. Потоки в дугах, найденные с помощью MATLAB.
Похожие статьи:
|
|