ГЛАВА6

УПРАЖНЕНИЯ 6.1

1. а) 1-3-4-2. Ь) 1-5-4-3-1. с) 1-3-4-5-1. d) См. рис. Г.7. е) См. рис. Г.7.

Остовное дерево

4. Цифры 1 и 8 должны обязательно располагаться в центральных квадратиках. Задача имеет несколько решений (рис. Г.8).

Рис. Г.8

УПРАЖНЕНИЯ 6.2

2. а) 1-2-5-6-4-3 или 3-1-2-5-6-4. Общая длина составит 14 миль.

5. Платформы с высоким давлением газа: 1-2-3-4-6. Платформы с низким давлением газа: 1-5-7 и 5-9-8. Общая длина составит 53 мили.

УПРАЖНЕНИЯ 6.3.1

1. Замена автомобилей должна произойти в 2001 и 2004 годах. Общая стоимость равна 8900 долл. (рис. Г.9).

4100

Рис. Г.9

5. Для каясдой дуги, соединяющей узлы (i, v) и (t + 1, vM), следует определить величины p(q) - необходимость в баллах (число вещей i). Решение: надо взять по одной вещи 1 и 2. Значение необходимости равно 80 баллов (рис. Г.10).

Рис. Г. 10

УПРАЖНЕНИЯ 6.3.2

1. с) 4-5-6-8 или 4-6-8, длина обоих маршрутов равна 8.

УПРАЖНЕНИЯ 6.3.3

1. а) 5-4-2-1, длина маршрута равна 12. 3. Связь между районами 1 и 2: маршрут 1

Связь между районами 1 и 4: маршрут 1

Связь между районами 1 и 5: маршрут 1

УПРАЖНЕНИЯ 6.3.4

1. а) Оптимальное решение: 1-3-4-5, длина маршрута равна 90.

УПРАЖНЕНИЯ 6.4.1

1. Разрез 1: (1, 2), (1, 4), (3, 4), (3, 5), пропускная способность разреза равна 60. УПРАЖНЕНИЯ 6.4.2

1. а) Величина неиспользованных пропускных способностей через дугу (2, 3) равна 40, через дугу (2, 5) - 10, через дугу (4, 3) - 5, через остальные дуги равна нулю.

b) Величины потоков, проходящих через узлы 2, 3 и 4, равны соответственно 20, 30 и 20 единиц.

c) Нет, поскольку в этой сети узким местом являются дуги, исходящие из узла 1.

-3-2, длина маршрута = 500 миль. -3-2-4, длина маршрута = 700 миль. -3-5, длина маршрута = 800 миль.

7. Максимальное количество таких распределений работ равно 4. Одно из распределений работ: Ральф - работа 3, Мэй - работа 1, Бен - работа 2, Ким - работа 5, Кен остается без работы.

УПРАЖНЕНИЯ 6.5.1

1. См. рис. Г.11.

[430] [-100] [-110] [-95] [-125] Рис. Г.11

УПРАЖНЕНИЯ 6.5.2

1. Задача ЛП до исключения нижних границ пропускных способностей дуг: минимизировать г = х12 + 5х13 + Зх24 + 4х32 + 6xS4 при ограничениях

*,2+*13=5°.

~Х\2 X2i ~ Х32 ~ -40,

-*18 + хгг + *34 = 20,

~Х21 - ХМ - -30,

30 < Х13 < 40, Х24 > 10, *32 > 10.

Задача ЛП после исключения нижних границ пропускных способностей дуг: Минимизировать г = х12 + 5х13 + Зх24 + 4х32 + 6х34 при ограничениях

х12 + х13 = 20,

-X -4- X - X = -40

12 24 32

-xl3 + x.i2 + x3i = 4.0, ~х24 - х34 = -20, x <10.

УПРАЖНЕНИЯ 6.5.3

1. Следует произвести 210 единиц продукции на первом этапе и 220 единиц - на третьем. Общая стоимость производства составит 9 895 долл.

5. Школа 1 принимает 450 учащихся из второй общины национальных меньшинств и 1000 из первой обычной общины. Школа 2 принимает 500 учащихся из первой общины национальных меньшинств, 300 человек из третьей общины национальных меньшинств и 1000 из второй обычной общины. Значение целевой функции, определяемой как произведение количества учащихся на расстояние от их местожительства до школы, равно 24 300. Задача имеет альтернативное решение.