Задача о соединении городов 39

Вид материала

Задача

Содержание Глава 2. графы и сети Глава 2. графы и сети Dдолжна следовать за работой Е, Е Линейные задачи

Подобный материал:

• Тема форума, 187.38kb.
• 1 Вопросы методологии исследования, 416.32kb.
• Проект Сводного доклада Форума "Стратегии крупных городов. Инвестиционные строительные, 508.25kb.
• Проблемы развития городов в последние годы уверенно занимает ключевую позицию в приоритетах, 81.82kb.
• Городов Всемирного Наследия, Международной Ассоциации Породненных Городов, Европейской, 145.2kb.
• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
• Малые города России: в будущее – через инновации, 56.32kb.
• При физическом соединении двух или более компьютеров образуется компьютер¬ная сеть, 1009.79kb.
• Деловую программу откроет конференция, на которой будут обсуждаться вопросы формирования, 201.02kb.

^ ГЛАВА 2. ГРАФЫ И СЕТИ

Таблица 1

Работа	Продолжительность	Работа	Продолжительность
А	2	F	2
В	7	G	6
С	15	Н	8
D	8	I	2
Е	10	J	3

Здесь А — заливка фундамента, В — изготовление оконных рам и две­рей, С — изготовление встроенных шкафов и мебели, D — монтаж во­допроводной системы, Е — возведение стен, F — оштукатуривание стен, G — возведение крыши, Н — благоустройство территории, I — установ­ка встроенных шкафов и мебели, J — покраска. Продолжительность работ указана в днях.

Таблица 2

Таблица 3

Бдолжна	следовать	за	Е
Едолжна	следовать	за	А	и	В
F должна	следовать	за	D	и	G
Сдолжна	следовать	за	Е
Ндолжна	следовать	за	G
I должна	следовать	за	с,	F	иН
J должна	следовать	за	I

dl	—	2
a2	—	7
аз	—	15
а4	а\, а%	10
а5	а4	8
а6	а4	6
а7	а5, а6	2
а8	а6	8
а9	а3, а7, а8	2
«10	а9	3

2.2. СЕТИ

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

l fli l		Я4		я5		а7		я9	яю
						я8
а	1 > ^^ яз
		—-	V		ч яю

Рис. 31

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

47

^ ГЛАВА 2. ГРАФЫ И СЕТИ

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

Подсчитаем временные затраты на критическом пути. Имеем:

7 + 10 + 6 + 8 + 2 + 3 = 36.

Отсюда следует, что анализируемый проект может быть реализо­ван за 36 дней и ни днем раньше.

Замечание. Всякая работа на критическом пути называется крити­ческой (малейшая задержка с началом ее выполнения увеличивает общую продолжительность работ). В данном случае критическими являются работы

а₂, а₄, а₆, а₈, а₉, а₁₀, или, возвращаясь к исходным обозначениям,

В, Е, G, H, I, J.

Определение всех таких работ важно для эффективного составле­ния проекта.

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

2.3. Задания

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

	А	В	С	D	Е	F
А	—	10	9	30	27	20
В	10	—	15	18	17	20
С	9	15	—	25	21	16
V	30	18	25	—	8	17
Е	27	17	21	8	—	13
Е	20	20	16	17	13	—

48


2.3. ЗАДАНИЯ



Рис. 32

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

2. Найдите кратчайшие маршруты, ведущие из узла А во все дру­гие узлы сети, представленной на рис. 32.



Рис. 33

3. Найдите максимальный поток в сети, представленной на рис. 33
   (исходный узел — 1, конечный узел — 7).
   
4. Найдите критический путь для цикла работ А(3), В(6), С(12),
   D(9), £"(11), F(3), G(5), H(7) и /(3) (в скобках указана продолжи­
   тельность соответствующего вида работы в днях) и минимальное
   время, необходимое для выполнения всего цикла, если последова­
   тельность операций подчинена следующим требованиям: работа ^ D
   должна следовать за работой Е, Е — за А ж В, F — за Д и G, G —
   за Е, Н — за С, / — за С и F.
   

Глава 3 ^ ЛИНЕЙНЫЕ ЗАДАЧИ

Линейные модели являются одним из наиболее активно используе­мых классов математических моделей.

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

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

Линейность — это свойство математических выражений и функ­ций. Выражение вида

ах + by,

где ж и у — переменные величины, а а и Ъ — постоянные числа, называется линейным относительно переменных х и у.

В случае если переменных больше двух — х\, ж₂, . . ., х_п, линейное выражение относительно этих переменных имеет вид

aiXi + а₂х₂ + • • • + а_пх_П}

где а\, а₂, . . . , а_п — постоянные числа.

Заметим, что в линейное выражение все переменные входят в пер­вой степени и никакие переменные не перемножаются.

Линейное программирование является, по-видимому, наиболее известным и одним из наиболее широко используемых инструмен­тов management science. Это математический метод решения задачи

50