Розглянемо табличний алгоритм Форда знаходження максимального потоку в мережі, який складається з послідовності кроків.

Початковий етап. Записуємо пропускну здатність дуг мережі в таблицю розмірності , де - кількість вершин мережі G(E,e).

Основний етап. Основний етап, який повторюється, складається з трьох дій.

1. Знаходимо по таблиці шлях з в з пропускною здатністю більшою за нуль. Для цього стовпчик, який відповідає джерелу Е0 помічаємо символом * . Шукаємо в -му рядку елементи , і стовпці в яких вони знаходяться, помічаємо зверху номером рядка, який розглядаємо (тобто цифрою 0). В результаті будуть виділені всі дуги () з додатною пропускною здатністю. Ці дуги можуть бути першими дугами шляху з в .

Далі розглянемо ті рядки, номери яких співпадають з номерами помічених стовпців. В кожному такому рядку, наприклад -овому, шукаємо елементи > 0, які знаходяться в непомічених стовпцях, і помічаємо ці стовпці номером розглядуваного рядка. Таким чином, ми виділяємо ті дуги, які можуть бути другими дугами шляху з Е0 в Е. Продовжуємо аналогічний перегляд рядків, номера яких співпадають з номером помічених стовпців, до тих пір, поки:

а) або не буде позначений стовпець (мережі). Це означає, що вдалось виділити шлях з пропускною здатністю більше нуля з в ;

б) або переконаємося в тому, що неможливо помітити нові стовпці (в розглядуваних рядках не виявиться додатних елементів, що містяться в непомічених стовпцях). В цьому випадку відсутній шлях з в , що проходить по дугах з пропускною здатністю більше нуля.

У випадку а) шуканий шлях ц з в знаходимо, використовуючи мітки. Нехай остання вершина шляху , позначена номером k. По цій помітці знаходимо попередню вершину (переглядаємо рядок , тут були помічені стовпець , і дуга () - остання в шуканому шляху) . Елемент , який знаходиться на перетині -го рядка і -го стовпця, відмічаємо знаком мінус, а симетричний йому елемент - знаком плюс. Ми розглядали -ий рядок, -й стовпець помічений, номером . Тому, рухаємося від елемента по -му стовпцю до r-го рядка. Продовжуємо цей процес до тих пір, поки не дійдемо до -го рядка і не позначимо знаком мінус елемент цього рядка і знаком плюс симетричний йому елемент. Переходимо до дії 2.

У випадку б) стовпчик , який відповідає стоку, помітити неможливо. З цього випливає, що не існує більше шляху з пропускною здатністю більше нуля з в , і основний етап, що повтроюється, завершено. Вершини, що знаходяться в постачених стовпцях, утворюють підмножину R (ці вершини досяжні по деякому шляху із джерела ). Інші вершини входять в підмножину ). Дуги, які виходять з вершин і входять в вершини і утворюють розріз з мінімальною пропускною здатністю.

2. Знаходимо пропускну здатність в знайденого шляху. Під пропускною здатністю розуміємо максимальну кількість речовини, яка може переміститися з в по шляху за одиницю часу. Пропускна здатність шляху рівна найменшій із пропускних здатностей дуг, які належать до цього шляху.

3. Визначаємо залишкову пропускну здатність дуг знайденого шляху і симетричних до них. Для цього від елементів таблиці віднімаємо , а до елементів додаємо . В результаті виконання цієї операції отримаємо нову таблицю, аналогічну початковій, але з іншими пропускними здатностями.

Після отримання нової таблиці повертаємося до дії 1 основного етапу, який виконується до тих пір, поки не отримаємо кінцеву таблицю, яка не містить жодного шляху з в з пропускною здатністю більше нуля.

Заключний етап. Від елементів початкової таблиці віднімаємо відповідні елементи таблиці, яку ми отримали на останньому кроці. В результаті отримаємо таблицю, додатні елементи якої рівні величинам потоків по відповідних дугах (). А максимальний потік в мережі - сумі елементів -го рядка або-го стовпця.

4. Задача максимізації кількості призначень у задачах розподілу як задача про максимальний потік

Приклад 1. На підприємстві є 5 вакансій і 4 працівники. Можливість прийняття працівників на вакансії подано таблицею

На основі цих даних побудуємо граф

Размещено на http://www.allbest.ru/

На основі даного графу приходимо задачі про максимальний потік. Знайдемо результат з використанням програмної реалізації модифікованого алгоритму Форда. Приведемо покроковий процес розв'язання

Приклад 2. На підприємстві є 8 вакансій і 6 працівників. Можливість прийняття працівників на вакансії подано таблицею

Знайдемо розв'язок з використанням програмної реалізації модифікованого алгоритму Форда

теорія граф числовий максимізація

Приклад 3. На підприємстві є 6 вакансій і 6 працівників. Можливість прийняття працівників на вакансії подано таблицею

Знайдемо розв'язок з використанням програмної реалізації модифікованого алгоритму Форда

Висновки

У роботі розглянуто задачу максимізації кількості призначень в задачі розподілу. Для розв'язання цієї задачі застосовано підхід, що полягає у зведенні цієї задачі до задачі про максимальний потік.

Перевагою такого підходу є те, що він дозволяє застосувати відомі методи розв'язання задачі про максимальний потік. Цей факт значно спрощує процес розв'язання поставленої задачі.

Недоліком такого підходу є те, що при побудові графа і його представленні за допомогою матриці суміжності ми одержуємо матрицю великої розмірності, яка є дуже розрідженою. Цього недоліку можна позбутися зберігаючи тільки важливі сектори даної матриці.

Список використаної літератури

1. Глебена МЛ. Кузка O.I. Задача про максимальний потік (методичні вказівки).- Ужгород 2007.

2. Навчальний посібник для студентів факультету кібернетики «Теорія графів» - 1998.

3. Уилсон Р. Введение в теорию графов.- М., 1977.

4. Оре О. Теория графов.- М., 1980.

5. Головина Л.И. Графы и их применения . Математика в школе, 1965, №3.

6. Нагибин Ф.Ф. Применение графов для решения логических задач. Математика в школе , 1964, № 3.

7. Шедивы Я. Решение логических задач при помощи графов.- Математика в школе, 1967, № 6.

8. Скляр І.В. Теорія графів у школі: задачі: посібник /Ірина Скляр. - К.:Шкільний світ, 2010. - 128с.

9. Збірник науково-популярних статей « У світі математики» Випуск 11.- 1980.

Додатки

Текст програми

program Project1;

end.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls, Spin, Menus;

type

TForm1 = class(TForm)

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

Label1: TLabel;

robSpinEdit: TSpinEdit;

daniStringGrid: TStringGrid;

Label2: TLabel;

misSpinEdit: TSpinEdit;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

rezEdit: TEdit;

Label3: TLabel;

priznMemo: TMemo;

Label4: TLabel;

tempStringGrid: TStringGrid;

CheckBox1: TCheckBox;

procedure FormCreate(Sender: TObject);

procedure robSpinEditChange(Sender: TObject);

procedure misSpinEditChange(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N6Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

TMatr=array[-1..100,-1..100] of integer;

Pvet=^Vet;

vet=record

inf:integer;

next:PVet;

end;

var

Form1: TForm1;

Dani,FMatr,Matr:TMatr;

n,m,nr,nm:integer;

QFirst,QLast:Pvet;

implementation

uses DateUtils;

{$R *.dfm}

procedure showNums;

var i:integer;

begin

with Form1 do

begin

for i:=1 to Form1.misSpinEdit.Value do

begin

daniStringGrid.Cells[0,i]:='Місце'+inttostr(i);

end;

for i:=1 to Form1.robSpinEdit.Value do

begin

daniStringGrid.Cells[i,0]:='Роб.'+inttostr(i);

end;

end;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

showNums;

end;

procedure TForm1.robSpinEditChange(Sender: TObject);

begin

daniStringGrid.ColCount:=robSpinEdit.Value+1;

showNums;

end;

procedure TForm1.misSpinEditChange(Sender: TObject);

begin

daniStringGrid.RowCount:=misSpinEdit.Value+1;

showNums;

end;

procedure TForm1.N3Click(Sender: TObject);

var f:TextFile;

i,j:integer;

begin

if SaveDialog1.Execute then

begin

AssignFile(f,SaveDialog1.FileName);

Rewrite(f);

writeln(f,misSpinEdit.Value,' ',robSpinEdit.Value);

for i:=1 to misSpinEdit.Value do

begin

for j:=1 to robSpinEdit.Value do

begin

writeln(f,daniStringGrid.Cells[j,i]);

end;

end;

CloseFile(f);

end;

end;

procedure TForm1.N2Click(Sender: TObject);

var f:TextFile;

nr,nm,i,j:integer;

s:string;

begin

if OpenDialog1.Execute then

begin

AssignFile(f,OpenDialog1.FileName);

Reset(f);

readln(f,nm,nr);

robSpinEdit.Value:=nr;

misSpinEdit.Value:=nm;

for i:=1 to nm do

begin

for j:=1 to nr do

begin

readln(f,s);

daniStringGrid.Cells[j,i]:=s;

end;

end;

CloseFile(f);

end;

end;

procedure getData;

var i,j,l:integer;

d:real;

begin

with Form1 do

begin

nr:=robSpinEdit.Value;

nm:=misSpinEdit.Value;

for i:=1 to nm do

begin

for j:=1 to nr do

begin

val(daniStringGrid.Cells[j,i],dani[i,j],l);

if l<>0 then

dani[i,j]:=0;

end;

end;

end;

end;

procedure createFirstMatr;

var i,j:integer;

begin

n:=nr+nm+1;

for i:=0 to n do

begin

for j:=0 to n do

begin

FMatr[i,j]:=0;

end;

end;

//0-row

for j:=1 to nm do FMatr[0,j]:=1;

//n-col

for i:=nm+1 to nm+nr do FMatr[i,n]:=1;

//dani

for i:=1 to nm do

begin

for j:=nm+1 to nm+nr do

begin

FMatr[i,j]:=Dani[i,j-nm];

end;

end;

end;

//--------------------------------------------------

{----------------- Quee ---------------------}

procedure QPush(inf:integer);

var cur:PVet;

begin

new(cur);

cur^.inf:=inf;

cur^.next:=nil;

if QFirst=nil then

begin

QFirst:=cur; QLast:=cur;

end

else

begin

QLast^.next:=cur;

QLast:=cur;

end;

end;

function QPop(var inf:integer):boolean;

var cur:PVet;

begin

if QFirst=nil then

Result:=false

else

begin

inf:=QFirst^.inf;

cur:=QFirst;

QFirst:=QFirst^.next;

Dispose(cur);

if QFirst=nil then QLast:=nil;

Result:=true;

end;

end;

procedure QErase;

var cur:Pvet;

begin

while QFirst<> nil do

begin

cur:=QFirst;

QFirst:=QFirst^.next;

Dispose(cur);

end;

QLast:=nil;

end;

{----------------- /Quee ---------------------}

procedure ShowMaatr(M:TMatr; n:integer; s:string);

var i,j:integer;

begin

if Form1.CheckBox1.Checked then

begin

With Form1 do

begin

tempStringGrid.ColCount:=n+1;

tempStringGrid.RowCount:=n+2;

for i:=-1 to n do

begin

for j:=0 to n do

begin

tempStringGrid.Cells[j,i+1]:=inttostr(M[i,j]);

end;

end;

end;

ShowMessage(s);

end;

end;

{------------------------ Max potik ---------}

function baseEtap:boolean;

//-------------------------

function setMark:integer;

var k,j:integer;

begin

QFirst:=nil; QLast:=nil;

for j:=0 to n do Matr[-1,j]:=-1;

QPush(0);

while QPop(k) do

begin

for j:=1 to n do

begin

if (Matr[-1,j]=-1)and(Matr[k,j]>0) then

begin

Matr[-1,j]:=k;

QPush(j);

if j=n then

begin

Result:=j;

QErase;

Exit;

end;

end;

end;

end;

Result:=-1;

end;

//-------------------------

procedure Etap3(k:integer);

var kn:integer;

begin

kn:=n;

repeat

Matr[k,kn]:=0;

Matr[kn,k]:=1;

kn:=k;

k:=Matr[-1,k];

until kn=0;

end;

var k:integer;

begin

repeat

k:=setMark;

ShowMaatr(Matr,n,'setMark');

if k<>-1 then

begin

Etap3(k);

ShowMaatr(Matr,n, 'etap3');

end;

until k=-1

end;

Function MaxPriznach:integer;

var i,j,kPrizn:integer;

function getRob(i:integer):integer;

var j:integer;

begin

for j:=nm+1 to nm+nr do

begin

if FMatr[i,j]>0 then

begin

Result:=j-nm;

Exit;

end;

end;

Result:=-1;

end;

begin

Matr:=FMatr;

baseEtap;

for i:=0 to n do

begin

for j:=0 to n do

begin

FMatr[i,j]:=FMatr[i,j]-Matr[i,j]

end;

end;

//------------

kPrizn:=0;

for j:=0 to n do kPrizn:=kPrizn+FMatr[0,j];

for i:=1 to nm do FMatr[i,-1]:=getRob(i);

Result:=kPrizn;

ShowMaatr(FMatr,n,'Rez');

end;

{------------------------ /Max potik ---------}

procedure TForm1.N6Click(Sender: TObject);

var i:integer;

begin

getData;

createFirstMatr;

ShowMaatr(FMatr,n,'First');

rezEdit.Text:=inttostr(MaxPriznach);

priznMemo.Clear;

for i:=1 to nm do

begin

if FMatr[i,-1]>0 then

priznMemo.Lines.Add('(Місце - '+inttostr(i)+') -> (Робочий -'+inttostr(FMatr[i,-1])+')');

end;

end;

procedure TForm1.N7Click(Sender: TObject);

begin

close

end;

end.

Інструкція користувача

Головна форма програми має зручний і зрозумілий інтерфейс

Всі операції з даними (зберігання даних, завантаження) виконуються з використанням пункту головного меню «Файл».

Знаходження оптимального розподілу здійснюється з використанням пункту головного меню «Знайти макс. призначення».

З використанням елемента «Виводити проміжкові результати» користувач має можливість проглядати покроково весь процес розв'язання.

Размещено на Allbest.ru