Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Задача КОММИВОЯЖЕРА

Читайте также:
  1. XV. СВЕРХЗАДАЧА. СКВОЗНОЕ ДЕЙСТВИЕ
  2. Боевая задача выполнена
  3. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  4. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  5. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  6. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  7. Ваша особая задача

Задача о КРАТЧАЙШЕМ (MIN) ПУТИ

Задан граф с 20 вершинами/пунктами (рёбра не ориентированы; начало –
в левом верхнем углу, конец – в правом нижем), расположенными в виде прямоугольника (в виде прямоугольной сетки). Каждая вершина соединена с соседними с ней вершинами справа, слева, снизу и сверху неориентированными ребрами. “Длины” ребер указаны между вершинами.

(при выполнения алгоритма, отсутствие нумерованного порядка проставления постоянных пометок,
т.е. “*”-ек, снижает баллы ВДВОЕ)

 

                Вариант 21   ┌5┬7┬4┬7┐ 6 7 4 2 7 ├7┼5┼7┼4┤ 6 2 4 5 2 ├7┼2┼5┼3┤ 5 6 4 6 6 └5┴6┴7┴5┘   Вариант 22   ┌5┬5┬4┬7┐ 3 2 4 6 4 ├3┼3┼2┼7┤ 5 3 5 2 4 ├7┼6┼3┼4┤ 6 6 2 3 7 └7┴7┴7┴3┘   Вариант 23   ┌7┬2┬3┬7┐ 4 4 3 6 6 ├3┼7┼4┼4┤ 5 7 4 4 6 ├6┼6┼2┼2┤ 7 5 5 2 2 └5┴5┴4┴7┘   Вариант 24   ┌3┬6┬3┬6┐ 3 4 2 2 5 ├6┼5┼2┼5┤ 5 6 7 2 6 ├4┼4┼2┼5┤ 7 3 7 6 6 └3┴7┴6┴7┘
Вариант 25   ┌4┬2┬7┬3┐ 4 6 6 2 5 ├3┼6┼4┼6┤ 5 7 6 3 4 ├2┼7┼5┼2┤ 6 6 5 2 2 └4┴3┴4┴4┘   Вариант 26   ┌4┬5┬5┬4┐ 6 5 3 2 6 ├6┼4┼2┼6┤ 3 3 3 2 2 ├5┼7┼4┼4┤ 5 5 3 7 3 └5┴4┴5┴7┘   Вариант 27   ┌5┬7┬2┬7┐ 4 5 6 2 5 ├5┼5┼7┼3┤ 6 3 6 6 7 ├6┼3┼4┼7┤ 3 7 5 4 3 └5┴5┴6┴6┘   Вариант 28   ┌5┬4┬3┬4┐ 6 3 5 5 7 ├7┼5┼2┼7┤ 5 6 6 6 3 ├7┼7┼3┼6┤ 4 5 2 5 4 └4┴3┴7┴7┘   Вариант 29   ┌7┬6┬3┬6┐ 6 5 5 2 6 ├2┼4┼2┼4┤ 4 2 6 6 3 ├6┼4┼7┼7┤ 2 4 3 5 7 └4┴4┴6┴6┘   Вариант 30   ┌5┬4┬7┬2┐ 4 2 5 4 5 ├3┼7┼5┼7┤ 3 6 2 2 5 ├7┼4┼4┼6┤ 5 5 2 2 3 └3┴5┴5┴5┘   Вариант 31   ┌7┬2┬6┬3┐ 4 7 5 5 7 ├7┼4┼4┼2┤ 4 2 5 3 5 ├5┼4┼5┼4┤ 5 2 7 4 7 └5┴3┴6┴3┘   Вариант 32   ┌7┬3┬3┬6┐ 3 4 4 6 2 ├2┼7┼7┼2┤ 6 5 6 2 3 ├6┼3┼4┼2┤ 4 7 2 7 4 └6┴5┴6┴3┘
Вариант 33   ┌5┬6┬6┬6┐ 3 5 4 4 3 ├4┼7┼5┼6┤ 5 6 7 6 4 ├4┼7┼3┼7┤ 6 2 7 2 3 └2┴2┴7┴6┘   Вариант 34   ┌6┬7┬7┬4┐ 7 4 4 2 4 ├6┼2┼2┼4┤ 4 4 2 6 7 ├3┼3┼2┼3┤ 3 2 3 7 3 └3┴7┴6┴4┘   Вариант 35   ┌3┬5┬6┬4┐ 7 3 7 5 3 ├2┼6┼4┼7┤ 7 4 2 5 6 ├5┼2┼2┼4┤ 6 5 2 6 3 └7┴2┴6┴6┘   Вариант 36   ┌5┬4┬3┬5┐ 4 7 7 2 5 ├3┼2┼7┼6┤ 3 3 3 2 4 ├7┼7┼7┼5┤ 2 3 7 7 7 └6┴5┴3┴5┘   Вариант 37   ┌4┬2┬5┬7┐ 6 4 3 5 6 ├7┼6┼3┼7┤ 6 3 5 7 7 ├4┼7┼4┼7┤ 7 3 3 4 3 └7┴2┴7┴7┘   Вариант 38   ┌2┬3┬6┬7┐ 7 5 7 6 7 ├4┼2┼7┼7┤ 6 7 7 5 7 ├5┼3┼3┼2┤ 6 5 5 3 4 └2┴4┴2┴7┘   Вариант 39   ┌6┬6┬4┬2┐ 6 4 7 6 4 ├3┼2┼4┼2┤ 6 5 7 5 2 ├6┼5┼7┼2┤ 2 6 6 5 3 └4┴3┴4┴4┘   Вариант 40   ┌6┬7┬7┬3┐ 7 6 3 7 2 ├4┼3┼6┼7┤ 5 3 6 7 6 ├2┼4┼6┼3┤ 4 4 2 4 2 └2┴7┴4┴2┘

 

Найти “длину” кратчайшего пути и сам кратчайший путь из левой верхней вершины в правую нижнюю вершину (решение без обоснования в виде нумерации порядка проставления постоянных пометок – не принимается!).

 

 

Задача о СЕТЕВОМ ГРАФИКЕ.

Задан комплекс из 20 работ, схематично расположенных в виде прямоугольника 4´5 длительностей их выполнения. Каждую работу можно начинать выполнять только после окончания выполнения соседних с ней работ слева и сверху.

 

                Вариант 21   3─3─3─6─5 │ │ │ │ │ 7─3─6─5─4 │ │ │ │ │ 7─5─2─6─4 │ │ │ │ │ 4─2─2─3─5   Вариант 22   4─2─4─3─5 │ │ │ │ │ 5─3─5─5─4 │ │ │ │ │ 4─2─2─3─2 │ │ │ │ │ 7─6─5─5─3   Вариант 23   4─3─2─5─6 │ │ │ │ │ 3─6─3─7─4 │ │ │ │ │ 3─5─2─2─6 │ │ │ │ │ 7─6─3─5─5   Вариант 24   2─2─5─3─7 │ │ │ │ │ 3─2─7─6─3 │ │ │ │ │ 5─4─7─3─4 │ │ │ │ │ 7─7─4─5─2
Вариант 25   4─4─3─2─6 │ │ │ │ │ 6─3─7─3─7 │ │ │ │ │ 3─5─5─6─7 │ │ │ │ │ 7─6─4─5─3   Вариант 26   7─4─5─4─3 │ │ │ │ │ 7─7─6─3─2 │ │ │ │ │ 2─7─5─3─2 │ │ │ │ │ 5─2─5─3─3   Вариант 27   4─6─4─5─2 │ │ │ │ │ 2─3─4─2─3 │ │ │ │ │ 6─2─3─3─5 │ │ │ │ │ 5─7─4─7─4   Вариант 28   3─2─4─4─6 │ │ │ │ │ 3─4─2─6─6 │ │ │ │ │ 2─5─4─2─4 │ │ │ │ │ 2─2─7─4─2   Вариант 29   7─6─7─6─3 │ │ │ │ │ 7─7─2─2─7 │ │ │ │ │ 6─2─6─2─2 │ │ │ │ │ 4─3─5─3─2   Вариант 30   6─4─7─6─4 │ │ │ │ │ 3─6─3─7─4 │ │ │ │ │ 4─7─6─4─4 │ │ │ │ │ 3─7─7─7─3   Вариант 31   6─6─5─2─7 │ │ │ │ │ 5─2─4─3─5 │ │ │ │ │ 2─4─2─7─7 │ │ │ │ │ 3─6─3─7─4   Вариант 32   3─3─3─4─6 │ │ │ │ │ 3─3─7─5─3 │ │ │ │ │ 6─4─5─3─6 │ │ │ │ │ 5─2─7─7─6
Вариант 33   7─5─7─6─2 │ │ │ │ │ 5─4─2─6─4 │ │ │ │ │ 7─5─7─4─5 │ │ │ │ │ 6─2─5─7─3   Вариант 34   6─3─6─5─5 │ │ │ │ │ 5─3─7─2─3 │ │ │ │ │ 5─4─6─6─2 │ │ │ │ │ 3─7─4─6─7   Вариант 35   4─3─7─3─3 │ │ │ │ │ 2─4─2─2─6 │ │ │ │ │ 4─3─3─3─2 │ │ │ │ │ 2─7─7─6─3   Вариант 36   5─6─4─6─6 │ │ │ │ │ 3─6─2─2─6 │ │ │ │ │ 2─5─3─5─5 │ │ │ │ │ 5─6─6─2─6   Вариант 37   7─7─3─2─6 │ │ │ │ │ 4─3─4─2─6 │ │ │ │ │ 3─7─6─6─6 │ │ │ │ │ 2─3─3─4─4   Вариант 38   5─7─5─5─4 │ │ │ │ │ 7─6─6─3─5 │ │ │ │ │ 7─7─7─3─4 │ │ │ │ │ 3─3─2─2─4   Вариант 39   2─2─7─2─6 │ │ │ │ │ 5─6─5─5─4 │ │ │ │ │ 2─6─6─3─5 │ │ │ │ │ 2─3─5─7─3   Вариант 40   4─5─7─2─4 │ │ │ │ │ 3─4─7─7─3 │ │ │ │ │ 2─6─4─3─3 │ │ │ │ │ 7─6─3─5─5

 

Найти:

1) минимальное время выполнения комплекса работ

(включить в “Ответ”, как: |T| =...);

2) самые ранние и самые поздние сроки выполнения каждой работы;

3) полный и свободный резервы каждой работы;

4) критический путь;

5) число критических работ

(включить в “Ответ”, как: |Критич.раб.| =...);

6) количество работ, у которых свободный резерв равен 0

(включить в “Ответ”, как: |Раб. с нул. Св.рез.| =...);

7) количество работ, у которых свободный резерв равен полному

(включить в “Ответ”, как: |Раб. с равн. Св. и Полн. рез.| =...).

Решить ВЕНГЕРСКИМ АЛГОРИТМОМ задачу о назначениях лишь НА МАКСИМУМ

(в ходе выполнения попытки перераспределения назначений, отсутствие индексированной нумерации снижает баллы на 1/3 максимально возможных баллов [или на 5 – при Зачёте], на 3 – при Экзамене)

 

    21. 7 8 7 4 12 15 10 5 9 11 10 8 7 6 8 3 6 4 7 4 6 5 5 10 1 4 2 10 3 3 1 10 4 13 6 4
22. 15 11 6 10 8 2 1 7 8 7 13 1 8 9 12 2 1 8 13 4 9 15 4 12 6 2 4 8 2 2 7 9 2 6 13 15 23. 6 2 5 15 4 11 14 5 15 8 1 12 5 4 8 9 15 8 15 5 10 8 9 2 6 3 2 2 14 10 10 5 1 15 9 4 24. 4 5 6 15 2 3 13 10 8 14 1 3 1 2 10 12 2 2 13 14 14 15 15 15 11 7 5 2 10 6 8 5 12 10 5 15
25. 10 9 2 14 5 13 1 10 15 10 13 11 4 12 14 9 8 12 2 9 14 10 11 10 10 13 10 6 13 10 15 8 9 11 4 11 26. 3 9 3 3 6 6 7 3 6 13 10 3 1 9 14 9 3 3 5 2 5 3 9 8 4 7 13 2 1 1 1 15 11 12 6 6 27. 2 12 5 2 11 10 2 2 3 10 9 6 4 4 3 6 12 8 8 8 9 12 11 4 14 5 14 15 14 2 11 12 11 15 3 9
28. 2 9 1 8 13 3 9 7 6 12 9 15 3 7 7 2 13 14 1 8 1 7 12 15 4 7 13 11 13 6 1 2 3 8 12 10 29. 13 6 7 7 4 8 10 2 11 14 13 15 3 8 8 7 14 2 12 10 13 2 6 7 14 3 15 8 9 9 10 14 13 11 7 15 30. 3 15 2 6 8 8 6 12 2 4 8 2 6 15 2 7 7 3 11 2 6 3 13 13 9 15 13 3 8 8 11 10 10 7 2 1
31. 13 2 8 14 2 14 14 9 11 14 2 5 10 5 12 14 12 10 11 7 15 14 12 1 10 6 15 8 3 14 4 6 10 4 13 14 32. 8 9 10 7 10 8 12 6 12 4 6 3 3 1 6 1 4 5 5 9 11 6 2 8 15 2 13 6 11 10 5 3 15 1 3 6 33. 12 8 12 6 6 2 15 11 10 14 2 2 14 7 5 8 11 10 11 14 6 14 12 3 15 6 10 14 2 5 11 9 11 1 10 8
34. 5 14 10 6 10 7 6 11 10 11 7 10 5 1 12 4 5 5 12 10 5 1 3 11 6 1 13 6 4 5 9 7 15 7 6 10 35. 5 11 13 1 4 15 8 11 1 4 15 3 9 5 4 1 14 5 12 6 8 14 9 14 7 13 3 6 1 6 6 15 5 7 2 13 36. 5 3 11 1 8 3 8 2 9 15 1 14 10 7 1 11 13 3 2 7 9 8 5 11 10 9 6 2 9 6 7 5 12 7 3 14
37. 15 5 10 2 12 15 2 12 4 11 7 7 8 4 3 4 2 13 15 9 12 9 15 6 9 5 13 15 12 15 6 2 3 10 11 11 38. 9 15 2 3 2 10 7 5 6 6 2 6 3 15 1 10 5 10 13 15 14 6 12 3 11 9 15 15 13 2 4 10 15 8 2 9 39. 11 15 1 11 11 9 4 14 13 6 6 1 12 14 9 12 9 1 10 15 12 7 3 11 14 13 14 4 3 14 6 7 12 14 1 4
40. 9 6 2 13 8 9 11 11 11 7 10 8 3 6 1 11 5 6 13 14 1 6 10 13 7 7 7 5 13 8 12 10 14 15 6 1    

 

(в ходе выполнения попытки перераспределения назначений, отсутствие индексированной нумерации снижает баллы на 1/3 максимально возможных баллов [или на 5 – при Зачёте], на 3 – при Экзамене)

 

21. 9 11 7 7 15 │120 10 7 6 11 14 │180 7 3 15 15 9 │280 ─------------- 60 180 60 90 190 22. 4 13 12 1 5 │ 10 9 5 7 1 13 │ 60 13 9 10 1 2 │440 ─------------------- 40 70 170 140 90 23. 15 6 1 10 7 │ 30 11 2 1 10 3 │200 7 14 3 15 15 │370 ─------------------ 110 160 120 70 140 24. 2 3 11 11 8 │ 20 5 11 5 9 1 │170 6 12 4 12 3 │310 ─----------------- 110 60 90 150 90 25. 4 6 7 7 2 │ 60 4 1 1 1 8 │190 12 7 1 5 4 │160 --------------------- 10 170 70 70 90 26. 4 11 15 7 5 │ 40 3 5 9 13 14 │160 9 13 10 7 11 │340 ─------------------- 170 90 130 100 50 27. 10 3 2 7 15 │ 60 6 4 11 12 4 │ 60 14 5 1 4 9 │430 ─------------------- 140 90 120 120 80 28. 7 5 9 10 9 │160 11 10 4 2 11 │150 1 4 8 1 7 │230 --------------------- 10 180 40 130 180 29. 1 2 1 9 9 │170 13 4 7 8 9 │200 3 7 13 1 14 │160 --------------------- 130 70 120 20 190 30. 6 14 7 6 5 │ 80 6 3 12 15 1 │ 50 7 13 15 2 1 │330 ─------------------- 160 10 160 100 30 31.13 3 1 7 6 │ 60 4 15 4 15 4 │130 6 12 10 15 7 │150 ------─------------- 60 50 20 80 130 32. 1 4 6 14 4 │180 4 12 13 13 9 │130 4 4 9 8 2 │420 ------─------------- 150 160 120 190 110 33. 9 3 15 15 8 │120 4 11 15 11 9 │160 12 2 3 13 4 │200 ─-----─------------- 70 190 180 20 20 34. 2 3 2 1 5 │180 5 8 1 9 15 │120 4 4 3 8 12 │200 -------------------- 30 130 30 200 110 35. 2 8 6 11 4 │150 13 3 6 1 13 │110 8 15 6 5 1 │410 ------─------------- 120 160 180 20 190 36. 12 1 4 8 14 │ 80 10 6 6 5 6 │200 1 4 9 11 13 │290 --------------------- 200 50 50 140 130 37. 5 11 9 11 12 │ 40 3 7 4 6 5 │120 13 12 6 1 12 │340 -–------------------ 110 30 50 130 180 38. 2 3 5 3 1 │180 3 9 15 5 10 │ 70 1 2 3 5 13 │270 ------─------------- 50 130 200 30 110 39. 1 10 3 15 13 │160 6 4 5 7 2 │120 1 11 9 9 8 │250 -------─------------- 70 160 150 80 70 40. 6 5 15 1 2 │ 20 7 9 10 9 15 │150 6 5 6 12 9 │500 ─------------------ 200 180 140 30 120

 

 

Задача КОММИВОЯЖЕРА

 

 

            21. ¥ 5 20 5 18 1
              20 ¥ 2 1 10 20
              13 2 ¥ 13 13 3
              2 16 9 ¥ 14 18
              2 11 3 8 ¥ 5
              17 4 11 4 5 ¥
               
22. ¥ 9 19 18 13 8   23. ¥ 7 16 5 13 18   24. ¥ 15 7 1 5 15
  12 ¥ 4 2 20 16     15 ¥ 20 7 17 12     16 ¥ 8 14 1 11
  18 19 ¥ 19 2 8     1 19 ¥ 10 13 16     8 15 ¥ 9 5 11
  14 20 5 ¥ 6 15     1 7 9 ¥ 13 15     18 3 3 ¥ 10 19
  19 6 5 16 ¥ 1     6 7 12 11 ¥ 2     16 2 1 3 ¥ 14
  14 16 13 2 8 ¥     5 15 20 3 19 ¥     3 5 19 8 13 ¥
               
25. ¥ 8 17 15 9 19   26. ¥ 16 2 1 1 8   27. ¥ 20 2 20 2 7
  12 ¥ 1 9 10 10     1 ¥ 13 14 9 11     17 ¥ 4 12 2 13
  9 15 ¥ 4 1 9     10 7 ¥ 10 4 7     10 15 ¥ 1 5 12
  15 17 18 ¥ 13 15     19 8 4 ¥ 7 1     9 11 10 ¥ 10 1
  5 18 16 15 ¥ 10     8 2 8 15 ¥ 18     19 16 11 19 ¥ 18
  9 7 9 5 12 ¥     13 3 8 13 11 ¥     10 17 12 2 7 ¥
               
28. ¥ 9 16 9 1 17   29. ¥ 6 1 10 4 13   30. ¥ 20 13 16 3 20
  9 ¥ 13 5 3 20     11 ¥ 20 9 1 1     10 ¥ 6 18 13 6
  3 15 ¥ 19 10 7     3 2 ¥ 19 17 13     17 3 ¥ 12 4 11
  13 19 10 ¥ 20 14     1 19 9 ¥ 7 12     2 8 7 ¥ 12 19
  13 9 12 8 ¥ 14     16 14 2 16 ¥ 11     4 12 1 7 ¥ 18
  1 12 9 20 3 ¥     4 20 3 7 20 ¥     9 10 9 15 10 ¥
               
31. ¥ 20 13 19 1 5   32. ¥ 13 8 6 16 3   33. ¥ 14 9 1 2 7
  13 ¥ 6 7 14 15     6 ¥ 11 12 15 13     3 ¥ 7 3 2 13
  13 10 ¥ 13 15 18     11 19 ¥ 10 6 11     13 5 ¥ 8 16 9
  7 4 8 ¥ 4 4     15 14 6 ¥ 15 10     8 19 5 ¥ 20 6
  16 9 3 7 ¥ 12     5 9 10 12 ¥ 16     7 16 6 1 ¥ 16
  9 7 6 10 17 ¥     5 8 15 16 12 ¥     14 3 14 7 19 ¥
               
34. ¥ 18 20 9 10 13   35. ¥ 11 17 14 1 19   36. ¥ 8 3 6 1 14
  13 ¥ 9 6 15 20     16 ¥ 2 17 2 18     4 ¥ 12 14 3 13
  14 18 ¥ 11 16 13     17 20 ¥ 2 14 2     20 1 ¥ 19 20 3
  4 5 3 ¥ 15 7     1 1 10 ¥ 2 20     9 4 5 ¥ 13 2
  13 10 5 2 ¥ 2     1 14 15 15 ¥ 13     17 15 6 15 ¥ 13
  8 11 4 16 5 ¥     20 1 19 3 20 ¥     20 19 19 8 14 ¥
               
37. ¥ 10 12 4 2 11   38. ¥ 11 15 17 19 13   39. ¥ 19 10 12 2 20
  3 ¥ 18 12 14 11     8 ¥ 3 8 6 20     8 ¥ 17 16 1 10
  6 1 ¥ 3 10 15     17 17 ¥ 20 20 7     9 12 ¥ 16 1 14
  1 2 14 ¥ 10 3     5 6 17 ¥ 1 9     6 20 6 ¥ 2 2
  9 15 20 11 ¥ 3     5 6 7 17 ¥ 13     16 13 11 1 ¥ 13
  6 4 7 8 20 ¥     14 12 19 16 17 ¥     9 10 10 10 11 ¥
               
40. ¥ 14 8 14 20 4            
  8 ¥ 5 12 13 17            
  4 16 ¥ 19 16 6            
  14 17 8 ¥ 10 15            
  5 13 19 8 ¥ 19            
  17 13 13 7 19 ¥            

 

Дата добавления: 2015-08-21; просмотров: 74 | Нарушение авторских прав

<== предыдущая страница | следующая страница ==>
Линейная алгебра| Задача об ОПТИМАЛЬНЫХ ИНВЕСТИЦИЯХ
mybiblioteka.su - 2015-2024 год. (0.01 сек.)