Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие

Подождите немного. Документ загружается.

2.2. СЕТИ

попасть из пункта А в пункт В будет просто невозможно). Ясно,

что пропускная способность разделяющего сечения складывается из

пропускных способностей всех мостов.

Рис. 22

Подобных сечений, разделяющих пункты А

В,

может быть не-

сколько (рис. 22), и каждое из них обладает своей пропускной спо-

собностью. Из того, что поток из пункта А в пункт В должен прохо-

дить через каждое разделяющее сечение, вытекает, что максимально

возможный поток не может превосходить пропускной способности ни

одного из этих сечений.

Таким образом, отыскание макси-потока (максимально возмож-

ного потока) сводится к отысканию мини-сечения (разделяющего се-

чения с наименьшей пропускной способностью).

Пример 6. Рассмотрим сеть, заданную на рис. 23. Требуется

найти максимально возможный поток из узла 1 в узел 7.

Рис.

Вычислим пропускную способность ключевых сечений. Имеем:

пропускная способность сечения {(1,2), (1,3)} равна 4,

пропускная способность сечения {(2,4), (3,5)} равна 4,

пропускная способность сечения {(1,3), (2,3), (6,7)} равна 5,

пропускная способность сечения {(5,7), (6,7)} равна 2.

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

Сравнивая пропускные способности сечений, получаем, что мак-

симальный поток от вершины 1 к вершине 7 равен 2.

2.2.4. Кратчайший маршрут

Дана сеть, каждое ребро которой помечено числом, равным его дли-

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

узла к каждому из узлов сети.

Алгоритм решения этой задачи состоит из двух частей.

Покажем, как он работает, на следующем примере.

Пример 7. Рассмотрим сеть, заданную на рис. 24, с выделенным

узлом 1.

Рис.

Прямой ход алгоритма

1-й шаг. Все узлы, которые соединены с выделенным узлом 1

одним ребром, метятся так, как это показано на рис. 25 — первое

число в метке равно расстоянию от помеченного узла до узла 1.

Ребро, связывающее узлы 1 и 3, является кратчайшим маршру-

том от узла 1 к узлу 3 (любой другой маршрут от узла 1 к узлу 3

длиннее), и поэтому узлу 3 приписывается постоянная метка (15,1).

Таким образом, по окончании 1-го шага узлы 1 и 3 имеют посто-

янные метки, узлы 2 и 4 — временные метки, а узлы 5, 6 и 7 никаких

меток не имеют (рис. 26).

Замечание. При получении постоянной метки узел 3 выделяется так

же, как и узел 1.

2-й шаг. Отбираются все узлы, которые соединены с узлом 3 од-

ним ребром и не имеют постоянных меток. Это узлы 2, 4 и б.

2.2. СЕТИ

(20,1)

Сравнивая длины маршрутов 1-2 и 1-3-2, замечаем, что длина

первого (20) меньше длины второго (15 + 10 = 25). Поэтому метка

(20,1) узла 2 остается неизменной.

Сравнивая длины маршрутов 1-4 и 1-3-4, замечаем, что длина

первого (25) больше длины второго (15 + 8 = 23). Поэтому временная

метка (25,1) узла 4 меняется на метку (23,3).

Узел 6 получает метку (45,3).

Замечание. Первое число в метке указывает длину маршрута от уз-

ла 1, а второе — номер предшествующего узла.

Ребро, связывающее узлы 1 и 2, является кратчайшим маршру-

том от узла 1 к узлу 2 (любой другой маршрут от узла 1 к узлу 2

длиннее), и поэтому узлу 2 приписывается постоянная метка (20,1).

Таким образом, по окончании 2-го шага узлы 1, 2 и 3 имеют посто-

янные метки, узлы 4 и 6 — временные метки, а узлы 5 и 7 никаких

меток не имеют (рис. 27).

3-й шаг. Отбираются все узлы, которые соединены с узлом 2 од-

ним ребром и не имеют постоянных меток. Это узлы 5 и 7.

Узел 5 получает метку (40,2).

Узел 7 получает метку (60,2).

Маршрут 1-3-4, связывающий узлы 1 и 4, является кратчайшим

маршрутом от узла 1 к узлу 4 (любой другой маршрут от узла 1 к

узлу 4 длиннее); поэтому узлу 4 приписывается постоянная метка

(23,3).

Таким образом, по окончании 3-го шага узлы 1, 2, 3 и 4 имеют

постоянные метки, а узлы 5, 6 и 7 — временные метки (рис. 28).

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

(20,1)

(60,2)

(45,3)

Рис. 28

4-й шаг. Отбираются все узлы, которые соединены с узлом 4 од-

ним ребром и не имеют постоянных меток. Это узел 6.

Сравнивая длины маршрутов 1-3-6 и 1—3-4—6, замечаем, что дли-

ны первого (45) и третьего (45) больше длины второго (43). Поэтому

временная метка (45,3) узла 6 меняется на метку (43,4).

Маршрут 1-2-5, связывающий узлы 1 и 5, является кратчайшим

маршрутом от узла 1 к узлу 5 (любой другой маршрут от узла 1 к

узлу 5 длиннее), и поэтому узлу 5 приписывается постоянная метка

(40,2).

Таким образом, по окончании 4-го шага узлы 1, 2, 3, 4 и 5 имеют

постоянные метки, а узлы 6 и 7 — временные метки (рис. 29).

Д20,1)

(60,2)

(23,3)

(43,4)

(49,5)

(23,3)

(43,4)

Рис. 29 Рис. 30

Следующие два шага позволяют дать постоянные метки узлам 6

и 7 — (43,4) и (49,5) соответственно (рис. 30).

2.2. СЕТИ

Замечание. На каждом шаге временная метка одного из узлов ме-

няется на постоянную по следующему правилу: рассматриваются

все узлы с временными метками и выбирается тот из них, длина

маршрута до которого от узла 1 является наименьшей.

Обратный ход алгоритма

Используя вторую компоненту метки, определяем последователь-

ность вершин в каждом кратчайшем маршруте. Например:

метка (49,5) узла 7 указывает на предшествующий узел 5,

метка (40,2) узла 5 указывает на предшествующий узел 2,

метка (20,1) узла 2 указывает на предшествующий узел 1.

В результате обратная последовательность узлов кратчайшего

маршрута от узла 1 к узлу 7 имеет вид

->•

-»•

->•

Ответ:

2.2.5. Критический путь

Предположим, что требуется проанализировать проект с точки зре-

ния минимальных временных затрат на его выполнение. Для этого

проект разбивают на отдельные работы, или действия, оценивают

время, необходимое на проведение каждой из них, и записывают по-

следовательность операций, показывающую, какие работы должны

быть закончены, прежде чем начнутся другие. Затем вычерчивает-

ся диаграмма работ, на которой каждая работа изображается на-

правленным ребром, и определяется критический путь, имеющий

наибольшую общую продолжительность. Он и определяет минимум

временных затрат на выполнение проекта.

Покажем, как делается временная оценка проекта, на примере

строительства небольшого загородного дома.

В табл. 1 и 2 указаны работы, их продолжительность и последо-

вательность выполнения.

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

Таблица 1

Работа

Продолжительность

1-7

{

Работа

Продолжительность

Здесь А — заливка фундамента, В — изготовление оконных рам и две-

рей, С — изготовление встроенных шкафов и мебели, D — монтаж во-

допроводной системы, Е — возведение стен, F — оштукатуривание стен,

G — возведение крыши, Н — благоустройство территории, I — установ-

ка встроенных шкафов и мебели, J — покраска.

Продолжительность работ указана в днях.

Таблица 2

Таблица 3

Перенумеруем последовательно все работы, не имеющие предше-

ствующих.

В данном случае это работы А —

(ai),

В —

(а

)

и С —

(а

Затем последовательно нумеруем остальные работы таким обра-

зом, чтобы все предшествующие им были уже занумерованы:

Е —

(04)

(следует за

(а\)

(а

)),

D —

(а

)

(следует за

(а

)),

G —

(а

)

(следует за

(а

)),

F —

(а

)

(следует за

(о

)

(а

)),

Н —

(о

)

(следует за

(а

)),

—

(а

)

(следует за

(а

)

(а

)),

(следует за

(а

)).

—

В результате получаем табл. 3.

Составим диаграмму работ.

2.2. СЕТИ

В верхней части рис. 31 каждая работа представлена на временной

шкале (точка отсчета совпадает с началом работ) горизонтальным

отрезком. Длины этих отрезков пропорциональны продолжительно-

сти соответствующих работ, а положения их левых концов опреде-

ляются возможностью их выполнения (см. табл. 3).

Рис.

В нижней части рис. 31 изображена направленная сеть, постро-

енная по данным табл. 3 и в более наглядной форме показываю-

щая, как именно связаны между собой работы по проекту и в ка-

кой очередности их следует выполнять. Ребра, обозначенные пунк-

тиром, необходимы для соблюдения правильной последовательности

операций.

ГЛАВА 2. ГРАФЫ

СЕТИ

Жирным выделен критический путь (направленный путь из на-

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

жительность).

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

+10

+ 6 + 8 + 2 + 3 = 36.

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

ван за 36 дней и ни днем раньше.

Замечание. Всякая работа на критическом пути называется крити-

ческой (малейшая задержка с началом ее выполнения увеличивает

общую продолжительность работ). В данном случае критическими

являются работы

02,

, а

аю,

или, возвращаясь к исходным обозначениям,

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

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

ния проекта.

В отличие от критической работы момент начала работы, не вхо-

дящей в критический путь, может быть несколько сдвинут (вперед)

без увеличения общей продолжительности. Важно, чтобы сдвинутая

некритическая работа была завершена до начала критических работ,

которым она предшествует.

2.3. Задания

1. Телефонная компания планирует соединить подземным кабелем

шесть городов, расстояния между которыми заданы при помощи та-

блицы:

2.3. ЗАДАНИЯ

Рис. 32

Найдите минимальную длину кабеля, позволяющего жителям лю-

бых двух городов связаться друг с другом по телефону.

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

гие узлы сети, представленной на рис. 32.

.25

Рис. 33

3. Найдите максимальный поток в сети, представленной на рис. 33

(исходный узел — 1, конечный узел — 7).

4. Найдите критический путь для цикла работ

А(3),

В(6),

С(12),

£>(9),

£(11),

F(3),

G(5),

tf(7) и /(3) (в скобках указана продолжи-

тельность соответствующего вида работы в днях) и минимальное

время, необходимое для выполнения всего цикла, если последова-

тельность операций подчинена следующим требованиям: работа D

должна следовать за работой Е, Е — за

Ли

В,

— за D

G —

за Е, Н — за G, I — за С и

Зак.

7492

Глава 3

ЛИНЕЙНЫЕ ЗАДАЧИ

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

мых классов математических моделей.

Издавна тройное правило (позднее — линейная функция) было

важным математическим инструментом в физике, химии, астроно-

мии, экономике и вообще везде, где человек хотел объяснить и упо-

рядочить наблюдаемые явления. И это естественно — для всякого

наблюдения линейная функция является самой удобной математи-

ческой моделью, и ею охотно пользуются.

Конечно, сейчас поле математических приложений значительно

расширилось. Но по-прежнему линейные модели привлекают огром-

ное внимание. Они сравнительно просты, хорошо разработаны, до-

пускают полное исследование и достаточно эффективны в целом ря-

де стандартных ситуаций.

Линейность — это свойство математических выражений и функ-

ций. Выражение вида

ах

+ by,

где х

и.

у — переменные величины, а о, и Ъ — постоянные числа,

называется линейным относительно переменных х и у.

В случае если переменных больше двух —

х\,

Хъ,

...,

линейное

выражение относительно этих переменных имеет вид

где

Ох,

а,2,

•..,

— постоянные числа.

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

вой степени и никакие переменные не перемножаются.

Линейное программирование является, по-видимому, наиболее

известным и одним из наиболее широко используемых инструмен-

тов management science. Это математический метод решения задачи

5(3