Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Контрольная работа - файл 4 Динамическое программирование и сетевое планирование.doc


Загрузка...
Контрольная работа
скачать (1273 kb.)

Доступные файлы (5):

1 Графический метод решения задач линейного программирования.doc488kb.27.09.2008 16:04скачать
2 Линейное программирование.doc1049kb.28.09.2008 18:29скачать
3 Транспортная задача.doc770kb.28.09.2008 18:31скачать
4 Динамическое программирование и сетевое планирование.doc299kb.28.09.2008 18:31скачать
Прочитай.txt1kb.28.11.2008 14:06скачать

4 Динамическое программирование и сетевое планирование.doc

Реклама MarketGid:
Загрузка...
4. Динамическое программирование и сетевое планирование.
Задание:

r(0.1)=8

r(2.4)=8

r(3.7)=3

r(7.8)=10

r(0.2)=5

r(2.5)=7

r(4.8)=7

r(7.9)=15

r(0.3)=7

r(2.6)=6

r(4.9)=5

r(8.10)=7

r(1.4)=7

r(2.7)=5

r(5.8)=6

r(9.10)=4

r(1.5)=6

r(3.4)=4

r(5.9)=4




r(1.6)=5

r(3.5)=2

r(6.8)=8




r(1.7)=4

r(3.6)=2

r(6.9)=3




  1. Построить сетевой график.

  2. Найти кратчайшее расстояние между городами (прямым и обратным ходом)

  3. Построить линейную диаграмму и по ней определить rmin и Lmin.


Решение:


  1. Постоим сетевой график.

Для этого занесем наши данные в таблицу.

R(i,j)=x, где i – предшествующий пункт, j – последующий пункт, х – расстояние между пунктами.




i

j

l




i

j

l



0

1

8



3

6

2



0

2

5



3

7

3



0

3

7



4

8

7



1

4

7



4

9

5



1

5

6



5

8

6



1

6

5



5

9

4



1

7

4



6

8

8



2

4

8



6

9

3



2

5

7



7

8

10



2

6

6



7

9

15



2

7

5



8

10

7



3

4

4



9

10

4



3

5

2













Изображаем сетевой график (Рис.1), удовлетворяющий следующим условиям:

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

  • сеть не должна иметь "хвостовых" событий (кроме исходного), которым не предшествует хотя бы одна работа;

  • в сети не должно быть замкнутых контуров (циклов);

  • в сетевой модели не допускаются работы, имеющие одинаковые шифры;

  • любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой;

  • в сети рекомендуется иметь одно исходное и одно завершающее события.


frame1
Где 0 – начальный пункт, 10 – конечный пункт, 1-9 – промежуточные города.

Графом называется пара , состоящая из непустого множества Х  и отображения Г множества х на множество х (Х,Г). Отображением множества Х на множество У называется закон сопоставления каждому элементу х из Х некоторого элемента у из У, т.е. х-->у.

Если одному элементу х сопоставляется несколько элементов у, то отображение называется неоднозначным. В качестве У выступает Х. Элементы множества х обозначаются в виде точек на плоскости, а отображения представляют собой дуги, соединяющие точки. Элементы множества Х преобразуются в виде точек. Поэтому элементы множества Х называют вершинами графа, а пары элементов (х,у) - дугами. Множество дуг можно обозначить U. Тогда граф можно задать так G=(X,U)

 

Г(х0)-> { х123}

Г(х1)->{x4,x567}

Г(x4)->{x8,x9}

Г(x8)->{x10}

Г(x10)->{0}




Г(х2)->{x4,x567}

Г(x5)->{ x8,x9}

Г(x9)->{x10}







Г(х3)->{x4,x567}

Г(x6)->{ x8,x9}













Г(x7)->{ x8,x9}







Вершины называются соседними (смежными), если они связаны дугами.

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

Путь называется простым, если ни одна из вершин не встречается дважды. Путь называется элементарным, если ни одна из вершин не встречается дважды. Контуром называется путь, начало и конец которого совпадают.

Если вершинам (или дугам) сопоставлены некоторые числовые характеристики, то граф называется сетью. Пусть длина дуги обозначена l, тогда  длина пути L=S li



  1. Найти кратчайшее расстояние между городами (прямым и обратным ходом)


Построим матрицу весов:




х0

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х0




8

5

7






















х1













7

6

5

4










х2













8

7

6

5










х3













4

2

2

3










х4

























7

5




х5

























6

4




х6

























8

3




х7

























10

15




х8































7

х9































4

Введем обозначение: С(Т) - длина кратчайшего пути из вершины 0 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(10) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.1 и в табл.1, в вершины 1,2,3 входят по одной стрелке из вершины 0 длиной 8,5 и 7 соответственно Кроме того, очевидно, что С(0) = 0.

В вершину 10 можно попасть либо из вершины 8, пройдя путь, равный 7, либо из вершины 9, пройдя путь, равный 4. Поэтому справедливо соотношение

С(10) = min {С(8) + 7 ; С(9) + 4}. (1)

Таким образом, проведена реструктуризация задачи - нахождение С(10) сведено к нахождению С(8) и С(9). 

В вершину 8 можно попасть либо из вершины 4, пройдя путь, равный 7, либо из вершины 5, пройдя путь, равный 6, либо из вершины 6, пройдя путь, равный 8, либо из вершины 7, пройдя путь, равный 10. Поэтому справедливо соотношение

С(8) = min {С(4) + 7 ; С(5) + 6; С(6) + 8; С(7) + 10}. (2)

В вершину 9 можно попасть либо из вершины 4, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 4, либо из вершины 6, пройдя путь, равный 3, либо из вершины 7, пройдя путь, равный 15. Поэтому справедливо соотношение

С(9) = min { С(4) + 5 ; С(5) + 4; С(6) + 3; С(7) + 15}. (3)

В вершину 4 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 2, пройдя путь, равный 8, либо из вершины 3, пройдя путь, равный 4. Поэтому справедливо соотношение

С(4) = min {С(1) + 7 ; С(2) + 8; С(3) + 4}. (4)

Мы знаем, что С(1) = 8, С(2) = 5, С(3) = 7. Поэтому

С(4) = min {8+7 ; 5+8; 7 +47} или С(4) = min {15 ; 13; 11}*

В вершину 5 можно попасть либо из вершины 1, пройдя путь, равный 6, либо из вершины 2, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 2. Поэтому справедливо соотношение

С(5) = min {С(1) + 6 ; С(2) + 7; С(3) + 2}. (5)

Мы знаем, что С(1) = 8, С(2) = 5, С(3) = 7. Поэтому

С(5) = min {8+6 ; 5+7; 7 + 2} или С(5) = min {14 ; 12; 9}

В вершину 6 можно попасть либо из вершины 1, пройдя путь, равный 5, либо из вершины 2, пройдя путь, равный 6, либо из вершины 3, пройдя путь, равный 2. Поэтому справедливо соотношение

С(6) = min {С(1) + 5 ; С(2) + 6; С(3) + 2}. (6)

Мы знаем, что С(1) = 8, С(2) = 5, С(3) = 7. Поэтому

С(6) = min {8+5 ; 5+6; 7 + 2} или С(6) = min {13 ; 11; 9}

В вершину 7 можно попасть либо из вершины 1, пройдя путь, равный 4, либо из вершины 2, пройдя путь, равный 5, либо из вершины 3, пройдя путь, равный 3. Поэтому справедливо соотношение

С(7) = min {С(1) + 4 ; С(2) + 5; С(3) + 3}. (7)

Мы знаем, что С(1) = 8, С(2) = 5, С(3) = 7. Поэтому

С(7) = min {8+4 ; 5+5; 7 + 3} или С(4) = min {12 ; 10; 10}

Теперь мы можем найти С(8) и С(9) :

С(8) = min {С(4) + 7 ; С(5) + 6; С(6) + 8; С(7) + 10}

С(8) = min {11 + 7 ; 9 + 6; 9 + 8; 10 + 10}

С(8) = min {18 ; 15; 17; 20}

С(9) = min { С(4) + 5 ; С(5) + 4; С(6) + 3; С(7) + 15}

С(9) = min { 11+ 5 ; 9 + 4; 9 + 3; 10 + 15}

С(9) = min { 16 ; 13; 12; 25}

Теперь мы можем найти С(10):

С(10) = min {С(8) + 7 ; С(9) + 4}.

С(10) = min {15 + 7 ; 12 + 4}.

С(10) = min {22 ; 16}

Таким образом, длина кратчайшего пути равна 16. Из последнего соотношения ясно, что в вершину 10 надо идти через вершину 9. Возвращаясь к вычислению С(9), видим, что в вершину 9 надо идти через вершину 6. В вершину 6 надо идти из вершины 3, а в вершину 3 можно попасть только из вершины 0. Итак, кратчайший путь таков (рис.2):

0 → 3 → 6 → 9 → 10.



Рисунок 2. Кратчайший путь.



  1. Построить линейную диаграмму и по ней определить rкрит и Lкрит.





* Значение, соответствующее кратчайшему пути выделено знаком _.






Скачать файл (1273 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru