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. Задача имеет альтернативное решение.
Рис. Г .12
УПРАЖНЕНИЯ 6.6.2
1. Критический путь: 1-3-4-5-6-7, длительность проекта равна 19. 3. Длительность проекта - 38 дней.
УПРАЖНЕНИЯ 6.6.3
3. а) Максимальный сдвиг равен 10.
5. а) Критический путь 1-3-6, длительность проекта - 45 дней.
b) Необходимо пометить "красными флажками" процессы A, D и Е.
c) Начала процессов С, D, G и Н задерживаются на 5 дней. На процесс Е начало процесса А не влияет.
d) Минимально необходимо две единицы этого оборудования.
ГЛАВА 7
УПРАЖНЕНИЯ 7.1.1
2. Точки (1, 0) и (0, 2) принадлежат множеству Q, но точки прямой
Ml, 0) + (1 - к)(0, 2) = (К,2- 2\) не принадлежат множеству Q при 0 < X < 1.
УПРАЖНЕНИЯ 7.1.2
2. Ь) Решение единственно (рис. Г. 13). d) Бесконечное множество решений, f)
Решения не существует.
3. а) Этот набор векторов образует базис, поскольку detB = -4.
d) Этот набор векторов не образует базис, поскольку в данном случае в базисе должно быть ровно три независимых вектора.
УПРАЖНЕНИЯ 6.6.1
1. См. рис. Г.12.