Министерство образования Российской Федерации
Пермский Государственный технический университет
Лысьвенский филиал
Кафедра ЕН
Курсовая работа
по дисциплине
«Системный анализ и исследование операций»
Выполнил студент гр. БИВТ-03
Десницкий П.А.
Проверил преподаватель
Мухаметьянов И.Т.
Лысьва, 2006
Содержание
Задание 1…………………………………………………………………………………………...….3
Задание 2……………………………………………………………………………………………..12
Задание 3…………………………………………………………………………………….……….24
ПРИЛОЖЕНИЕ……………………………………………………………….……………..………27
Список литературы………………………………………………………………………………….35
Основная цель: Самостоятельное изучение темы сетевого планирования и оформление лабораторных работ.
Задание 1
Районной администрацией принято решение о газификации одного из сёл района, имеющего 25 жилых домов. Расположение домов указано на рисунке. Числа в кружочках обозначают условный номер дома. Узел 15+R (R - остаток от деления номера варианта на 12) является газораспределительным. Разработать такой план газификации села, чтобы общая длина трубопроводов была наименьшей (расстояния между домами даны в метрах).
Проанализировать решение задачи на единственность. В случае не единственности решения найти все решения и доказать, что других нет.
|
№ варианта |
Значения | |||||||||||||||
|
6 |
а1 |
а2 |
а3 |
а4 |
а5 |
а6 |
а7 |
а8 |
а9 |
а10 |
а11 |
а12 |
а13 |
а14 |
а15 |
а16 |
|
190 |
70 |
240 |
150 |
130 |
360 |
50 |
380 |
180 |
450 |
180 |
70 |
170 |
50 |
80 |
70 | |
|
а17 |
а18 |
а19 |
а20 |
а21 |
а22 |
а23 |
а24 |
а25 |
а26 |
а27 |
а28 |
а29 |
а30 |
а31 |
а32 | |
|
520 |
390 |
160 |
80 |
430 |
350 |
110 |
70 |
210 |
440 |
70 |
50 |
120 |
220 |
580 |
420 | |
|
а33 |
а34 |
а35 |
а36 |
а37 |
а38 |
а39 |
а40 |
а41 |
а42 |
а43 |
а44 |
а45 |
а46 |
а47 |
а48 | |
|
330 |
90 |
450 |
70 |
70 |
90 |
110 |
|
180 |
220 |
90 |
330 |
120 |
600 |
440 |
330 | |
Граф:
Решение:
Данную задачу можно решить «жадным» алгоритмом, который заключается:
В самом начале в остов включаем ребро наименьшего веса, если таких ребер несколько, то включаем любые из них. На следующем шаге включаем в остов из оставшихся ребер ребро наименьшего веса. Цикл при этом не должен получиться. На каждом шаге к образовавшемуся подграфу (вполне возможно не связный на промежуточных этапах) включаем из оставшихся ребер ребро наименьшего веса и не образующего цикл с ребрами уже включенными в остов. Процесс прекращаем при включении n-1 ребра, где n равно количеству вершин в графе.
Граф - это совокупность точек, соединенных линиями.
Вершина графа может представлена вектором (2,3-х и большей мерности), в котором может храниться различная информация - номер точки, местоположение ее, трудозатраты и т.п.).
Последовательность ребер, в которой конец каждого предыдущего ребра совпадает с началом последующего, называют путем.
Остов – это часть графа, которая содержит в себе все вершины исходного графа.
Решая, будем постепенно включать ребра с наименьшим весом, выделяя их пожирнее:
Шаг №1. Выбираем ребро наименьшего веса и включаем его в остов. Ребром наименьшего веса будет являться ребро с весом 50.
Шаг №2. Включаем следующее ребро наименьшего веса 70.
Шаг №3. Включаем следующее ребро наименьшего веса 80.
Шаг №4. Включаем следующее ребро наименьшего веса 90, смотря, чтоб не получился цикл.
Шаг №5. Включаем следующее ребро наименьшего веса 110.
Шаг №6. Включаем следующее ребро наименьшего веса 120.
Шаг №7. Включаем следующее ребро наименьшего веса 130.
Шаг №8. Ребра весом 150, 160, 170 не включаем, чтобы не получился цикл. Включаем следующее ребро наименьшего веса 180, смотря, чтоб не получился цикл.
Шаг №9. Ребро весом 190 не включаем, чтобы не получился цикл. Включаем следующее ребро наименьшего веса 210.
Шаг №10. Включаем следующее ребро наименьшего веса 220.
Шаг №11. Включаем следующее ребро наименьшего веса 330, смотря, чтоб не получился цикл.
или
Шаг №12. Ребра весом 360, 380 не включаем, чтобы не получился цикл. Включаем следующее ребро наименьшего веса 420.
или
В итоге получается два решения данной задачи. Получим 2 дерева с 25-ти ребрами.
50+50+50+70+70+70+70+70+70+70+80+80+90+90+110+110+120+120+130+180+180+210+220++330+420=3110
Существует два решения задачи, которые составляют общую наименьшую длину трубопроводов 3110 м.
Доказательство:
Данная задача имеет два решения, граф был пройден жадным алгоритмом и повторно пройден с анализом на наименьшее значение ребер, примыкающим к вершинам графа, поэтому задача не может иметь других решений.
В результате выполнения этой работы я научился работать с графом, т.е. находить оптимальный план газификации села, с помощью «жадного» алгоритма.