Разработка системы планирования размещения точек водоснабжения в населенных пунктах

d_4,2⁵=min{d_4,5⁴+d_5,2⁴d_4,2⁴}=min{2+?; ?}=?

d_4,3⁵=min{d_4,5⁴+d_5,3⁴d_4,3⁴}=min{2+?; ?}=?

d_4,4⁵=min{d_4,5⁴+d_5,4⁴d_4,4⁴}=min{2+?; 0}=0

d_4,5⁵=min{d_4,5⁴+d_5,5⁴d_4,5⁴}=min{2+0; 2}=2

d_4,6⁵=min{d_4,5⁴+d_5,6⁴d_4,6⁴}=min{2+3; ?}=5

d_5,1⁵=min{d_5,5⁴+d_5,1⁴d_5,1⁴}=min{0+?; ?}=?

d_5,2⁵=min{d_5,5⁴+d_5,2⁴d_5,2⁴}=min{0+?; ?}=?

d_5,3⁵=min{d_5,5⁴+d_5,3⁴d_5,3⁴}=min{0+?; ?}=?

d_5,4⁵=min{d_5,5⁴+d_5,4⁴d_5,4⁴}=min{0+?; ?}=?

d_5,5⁵=min{d_5,5⁴+d_5,5⁴d_5,5⁴}=min{0+0; 0}=0

d_5,6⁵=min{d_5,5⁴+d_5,6⁴d_5,6⁴}=min{0+3; 3}=3

d_6,1⁵=min{d_6,5⁴+d_5,1⁴d_6,1⁴}=min{9+?; 2}=2

d_6,2⁵=min{d_6,5⁴+d_5,2⁴d_6,2⁴}=min{9+?; 3}=3

d_6,3⁵=min{d_6,5⁴+d_5,3⁴d_6,3⁴}=min{9+?; 5}=5

d_6,4⁵=min{d_6,5⁴+d_5,4⁴d_6,4⁴}=min{9+?; 7}=7

d_6,5⁵=min{d_6,5⁴+d_5,5⁴d_6,5⁴}=min{9+0; 9}=9

d_6,6⁵=min{d_6,5⁴+d_5,6⁴d_6,6⁴}=min{9+3; 0}=0

d_i,j⁶=min{ d_i,6⁵+ d_6,j⁵; d_i,j⁵}.

d_1,1⁶=min{d_1,6⁵+d_6,1⁵d_1,1⁵}=min{10+2; 0}=0

d_1,2⁶=min{d_1,6⁵+d_6,2⁵d_1,2⁵}=min{10+3; 1}=1

d_1,3⁶=min{d_1,6⁵+d_6,3⁵d_1,3⁵}=min{10+5; 3}=3

d_1,4⁶=min{d_1,6⁵+d_6,4⁵d_1,4⁵}=min{10+7; 5}=5

d_1,5⁶=min{d_1,6⁵+d_6,5⁵d_1,5⁵}=min{10+9; 7}=7

d_1,6⁶=min{d_1,6⁵+d_6,6⁵d_1,6⁵}=min{10+0; 10}=10

d_2,1⁶=min{d_2,6⁵+d_6,1⁵d_2,1⁵}=min{9+2; ?}=11

d_2,2⁶=min{d_2,6⁵+d_6,2⁵d_2,2⁵}=min{9+3; 0}=0

d_2,3⁶=min{d_2,6⁵+d_6,3⁵d_2,3⁵}=min{9+5; 2}=2

d_2,4⁶=min{d_2,6⁵+d_6,4⁵d_2,4⁵}=min{9+7; 4}=4

d_2,5⁶=min{d_2,6⁵+d_6,5⁵d_2,5⁵}=min{9+9; 6}=6

d_2,6⁶=min{d_2,6⁵+d_6,6⁵d_2,6⁵}=min{9+0; 9}=9

d_3,1⁶=min{d_3,6⁵+d_6,1⁵d_3,1⁵}=min{7+2; ?}=9

d_3,2⁶=min{d_3,6⁵+d_6,2⁵d_3,2⁵}=min{7+3; ?}=10

d_3,3⁶=min{d_3,6⁵+d_6,3⁵d_3,3⁵}=min{7+5; 0}=0

d_3,4⁶=min{d_3,6⁵+d_6,4⁵d_3,4⁵}=min{7+7; 2}=2

d_3,5⁶=min{d_3,6⁵+d_6,5⁵d_3,5⁵}=min{7+9; 4}=4

d_3,6⁶=min{d_3,6⁵+d_6,6⁵d_3,6⁵}=min{7+0; 7}=7

d_4,1⁶=min{d_4,6⁵+d_6,1⁵d_4,1⁵}=min{5+2; ?}=7

d_4,2⁶=min{d_4,6⁵+d_6,2⁵d_4,2⁵}=min{5+3; ?}=8

d_4,3⁶=min{d_4,6⁵+d_6,3⁵d_4,3⁵}=min{5+5; ?}=10

d_4,4⁶=min{d_4,6⁵+d_6,4⁵d_4,4⁵}=min{5+7; 0}=0

d_4,5⁶=min{d_4,6⁵+d_6,5⁵d_4,5⁵}=min{5+9; 2}=2

d_4,6⁶=min{d_4,6⁵+d_6,6⁵d_4,6⁵}=min{5+0; 5}=5

d_5,1⁶=min{d_5,6⁵+d_6,1⁵d_5,1⁵}=min{3+2; ?}=5

d_5,2⁶=min{d_5,6⁵+d_6,2⁵d_5,2⁵}=min{3+3; ?}=6

d_5,3⁶=min{d_5,6⁵+d_6,3⁵d_5,3⁵}=min{3+5; ?}=8

d_5,4⁶=min{d_5,6⁵+d_6,4⁵d_5,4⁵}=min{3+7; ?}=10

d_5,5⁶=min{d_5,6⁵+d_6,5⁵d_5,5⁵}=min{3+9; 0}=0

d_5,6⁶=min{d_5,6⁵+d_6,6⁵d_5,6⁵}=min{3+0; 3}=3

d_6,1⁶=min{d_6,6⁵+d_6,1⁵d_6,1⁵}=min{0+2; 2}=2

d_6,2⁶=min{d_6,6⁵+d_6,2⁵d_6,2⁵}=min{0+3; 3}=3

d_6,3⁶=min{d_6,6⁵+d_6,3⁵d_6,3⁵}=min{0+5; 5}=5

d_6,4⁶=min{d_6,6⁵+d_6,4⁵d_6,4⁵}=min{0+7; 7}=7

d_6,5⁶=min{d_6,6⁵+d_6,5⁵d_6,5⁵}=min{0+9; 9}=9

d_6,6⁶=min{d_6,6⁵+d_6,6⁵d_6,6⁵}=min{0+0; 0}=0

В результате, нами получена матрица длин кратчайших путей между каждой парой вершин графа. Ниже представлена таблица путей. Каждый элемент Cij таблицы, это путь из вершины i в вершину j

Таблица путей

	1	2	3	4	5	6
1	-	d1-2=1-2	d1-3=1-2-3	d1-4=1-2-3-4	d1-5=1-2-3-4-5	d1-6=1-2-3-4-5-6
2	d2-1=2-3-4-5-6-1	-	d2-3=2-3	d2-4=2-3-4	d2-5=2-3-4-5	d2-6=2-3-4-5-6
3	d3-1=3-4-5-6-1	d3-2=3-4-5-6-1-2	-	d3-4=3-4	d3-5=3-4-5	d3-6=3-4-5-6
4	d4-1=4-5-6-1	d4-2=4-5-6-1-2	d4-3=4-5-6-1-2-3	-	d4-5=4-5	d4-6=4-5-6
5	d5-1=5-6-1	d5-2=5-6-1-2	d5-3=5-6-1-2-3	d5-4=5-6-1-2-3-4	-	d5-6=5-6
6	d6-1=6-1	d6-2=6-1-2	d6-3=6-1-2-3	d6-4=6-1-2-3-4	d6-5=6-1-2-3-4-5	-

2. Поиск медианы

Основываясь на полученной нами матрице длин кратчайших путей, найдем CВВ(i) для каждой вершины графа

CВВ(i)=Уd(i, j).

CВВ(1)==У_jd(1, j)=26

CВВ(2)==У_jd(2, j)=32

CВВ(3)==У_jd(3, j)=32

CВВ(4)==У_jd(4, j)=32

CВВ(5)==У_jd(5, j)=32

CВВ(6)==У_jd(6, j)=26

Медианами графа является такая вершина x, для которой

СВВ(x)=min{СВВ(i)}

Минимальное значение имеет СВВ(1) и СВВ(6)=26, а это значит, что вершина 1 и вершина 6 являются медианами графа.

Выводы к разделу 2

Теория графов находит широкое применение в различных областях науки и техники. Многие математические факты удобно формулировать на языке графов. В последнее время теория графов находит всё больше применений в прикладных вопросах. Графы стали широко использовать в теории массового обслуживания, поскольку там возникают задачи оптимального размещения точек обслуживания. Основной проблемой является минимизация расстояния от любой точки населенного пункта до ближайшего пункта обслуживания.

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

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

Поэтому использование графов в разработках систем планирования размещения объектов в населенных пунктах не только актуально на сегодняшний день, но и практично и удобно в использовании.

оптимальный алгоритм граф флойд

Раздел 3. Программная реализация системы планирования размещения точек водоснабжения в населенных пунктах

3.1 Описание функциональных возможностей разрабатываемого приложения. Информационная структура приложения

Нахождение медиан графа реализовано в методе Флойда в среде программирования Delfi.

Чтобы найти медианы графа необходимо построить граф.

Для задания матрицы весов и количества вершин предусмотрена возможность их введения как вручную, так и из текстового файла. Для этого нужно нажать на вкладку «ввод» и выбрать соответствующее действие (рисунок 7).

Рисунок 7. «Форма программы»

Если вы выбрали «считать из файла», то у вас появится окно (рисунок 8), в котором нужно выбрать: 1.txt (нахождение 1 медианы графа) или 2.txt (нахождение 2 медиан графа) или 3.txt (нет медиан, т.к. задан несвязный граф), которые показаны на рисунках 9,10 и 11 соответственно.

Также предусмотрено изменение элементов матрице вручную на форме программы.

Рисунок 8. «Окно для выбора текстового файла»

Рисунок 9. «Текстовый файл для нахождения 1 медианы»



Рисунок 10. «Текстовый файл для нахождения 2 медиан»

Рисунок 11. «Текстовый файл для несвязного графа»

Предусмотрены следующие проверки:

1) на главной диагонали стоят только нули;

2) матрица должна содержать все элементы;

3) матрица симметрична относительно главной диагонали;

4) значения должны быть целочисленными.

После того как мы загрузили 1.txt (рисунок 12), необходимо нажать на кнопку «построить граф» (рисунок 13).



Рисунок 12. «Форма программы»

Рисунок 12. «Форма программы»

После этого нажав на кнопку «Медиана» мы можем найти 1 или более медиан графа, если он является связным (рисунок 13).



Рисунок 13. «Форма программы»

Также предусмотрено:

1) очистка рисунка и значений матрицы;

2) сохранение матрицы, содержимое которой будет хранится в текстовом файле;

3) сохранение рисунка в файл, имеющий расширение: «.bmp», «.ico», «.emf», «.wmf»;

4) закрытие формы программы.

3.2 Информационная структура приложения. Программная реализация основных модулей

Рассмотрим основные имена функций, процедуры и переменных в программе:

1) procedure TForm1.Button1Click(Sender: TObject)// кнопка «построить граф»;

2) procedure StringGrid1Click(Sender: TObject);//матрица весов и вершин;

3) procedure Button3Click(Sender: TObject);//кнопка нахождения медиан;

4) Matr_S//массив, в котором храниятся значения матрицы;

5) Ves_Tree//переменная - весовой коэффициент;

6) procedure redraw(var im: Timage);//процедура рисования графа;

7) function kolvos// функция, использующая для подсчета и занесения значений в StrinGrid.

Выводы к разделу 3

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

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

Заключение

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

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

Список использованной литературы

1. Берж К., Теория графов и ее применения, 1972.

2. Кристофидес Н., Теория графов. Алгоритмический подход, 1975.

3. Кормен Т., Лейзер Ч., Алгоритмы. Построение и анализ.

4. Оре О., Графы и их применения, 1975.

5. www.uchimatchact.ru

6. www.matematik.com.ua

7. Джигерей В.С., Экология и охрана окружающей среды, 2006.

8. Белявский Г.О., Экологические показатели и их сравнение, 2008.

Приложение

// нахождение медиан с помощью алгоритма Флойда

const

INF: Double = 1000000;

var

D: array of array of Double;

dist: array of Double;

sum, min_d: Double;

i, j, k, n: Integer;

begin

n := Length(Matr_S);

SetLength(dist, n);

SetLength(D, n, n);

for i := 0 to n - 1 do

for j := 0 to n - 1 do

if Matr_S[i][j] = 0 then D[i][j] := INF else

D[i][j] := Matr_S[i][j];

for k := 0 to n - 1 do

for i := 0 to n - 1 do

for j := 0 to n - 1 do

D[i][j] := Min( D[i][j], D[i][k] + D[k][j]);

min_d := 1000000;

for i := 0 to n - 1 do begin

sum := 0;

for j := 0 to n - 1 do

sum := sum + D[i][j];

dist[i] := sum;

if dist[i] < min_d then min_d := dist[i];

end;

Edit1.Text := '{ ';

for i := 0 to n - 1 do

if dist[i] = min_d then Edit1.Text := Edit1.Text + IntToStr(i + 1) + '; ';

Edit1.Text := Edit1.Text + '}';

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