Математические фантазии - Слойер С.
ISBN 5-03-002367-4
Скачать (прямая ссылка):
(n -f- N) S.
Задача 1. Предположим, что два обслуживающих устройства обслуживают одну
очередь и каждому из этих устройств требуется время 5 для обслуживания
клиента. Используя обозначения, введенные в нашем
110
Фантазия 28
обобщенном случае, определите первого клиента, который не застанет
очереди перед обслуживающим устройством, а также полное время,
требующееся для ликвидации очереди.
Задача 2. В обобщенном случае мы предполагали, что 0 f ^ Т. А что
произойдет, если f ^ 7?
Задача 3. В обобщенном случае определите, сколько времени произвольный
заданный клиент будет ждать окончания своего обслуживания.
Фантазия 28
"КРОВАВОЕ" ДЕЛО
Математика: алгебра (см. фантазии 8 и 9)
В фантазиях 8 и 9 мы ввели понятие линейного программирования. В этом
разделе мы покажем, как можно переформулировать довольно сложную задачу
таким образом, чтобы получилась задача линейного программирования. Мы не
будем решать эту задачу, а просто предположим, что ее можно решить на
компьютере с помощью соответствующей программы.
Допустим, клиника располагает следующими запасами крови:
Группа Запас Стоимость переливания
крови (в пинтах) пинты (в долл.)
А 8 25
В 5 25
АВ 2 40
О 6 20
аКровавое" дело
Пусть имеются шесть пациентов, которые нуж даются в переливании крови:
" _ Требуемое количество
Пациент Группа крови крови (в пинтах)
1 А 4
2 В 2
3 В 1
4 АВ 3
5 О 1
6 0 3
Задача состоит в том, чтобы провести все необходимые переливания крови с
минимальными затратами.
Донор с группой крови А может дать свою кровь реципиентам с группой крови
А или АВ. Донор с группой крови В может дать кровь реципиентам с группой
крови В или А В. Донор с группой крови Л В может дать свою кровь только
реципиентам с группой крови АВ. Донор с группой крови О является
универсальным донором: его кровь подходит реципиентам с группами крови А,
В, АВ и О.
Предположим, что мы составили следующую схему:
Реципиент
Донор 1 2 3 4 5 6 Меньше или равно
А а ё 8
В с е h 5
АВ i 2
0 Ъ d f k / m 6
Больше 4 2 1 3 1 3
или
равно
где а, Ь, с, d, е, ..., т - число пинт крови, которое донор дает
реципиенту. Таким образом, граничные
m
Фантазия 28
неравенства для этой задачи имеют вид a + g<8. с + е + Л^5,
/'< 2,
b-\-d-\-f-\-k-\-tn ^ 6, a + ft|> 4, c + d>2, e + f> 1, г + л + у + *>з,
/>1, т>3,
о^О, ft ^ 0 m ^ О,
и мы замечаем, что они описывают геометрическую фигуру в 12-мерном
пространстве.
Общая стоимость переливания крови описывается формулой
С= 25 (с + g) + 25 (с + е + h) + 40 (/) +
+ 20 {b + d + f + k + 1 + т).
Таким образом, для каждого упорядоченного набора из 12 чисел (a, ft, ...,
m), который удовлетворяет приведенным выше неравенствам, мы вычисляем
значение С и из всех вариантов выбираем тот, для которого значение С
оказывается минимальным. Это и есть оптимальное решение. Задачи такого
типа (в том числе и задачи разделов 8 и 9) известны как задачи "линейного
программирования".
Наши неравенства задают в 12-мерном пространстве конечную фигуру,
аналогичную тем фигурам в двумерном пространстве, которые можно заключить
в квадрат, и тем фигурам в трехмерном пространстве, которые можно
заключить в куб. Функции, подобные С, достигают на таких фигурах
минимального значения, причем это значение они принимают "в углу".
Поэтому достаточно просто найти все угловые значения. В нашей задаче
таких углав приблизи-
Вспомним о спутнике
113
тельио 60. Процесс нахождения всех этих углов, не говоря уже о вычислении
значений С в них, очень трудоемкий. Математик Георг Данциг нашел алгоритм
поиска такого решения, а также разработал метод, сокращающий число шагов.
Этот метод предусматривает, что мы начинаем поиск из любого угла и
перемещаемся из данного угла в смежный с ним угол, в котором значение С
становится меньше. Таким образом мы находим минимальное значение С.
Задача. Сформулируйте задачу линейного программирования для минимизации
затрат на переливание крови исходя из следующих данных:
Стоимость переливания
ГРУппа крови (в п^ах) одной пинты крови (в долл.)
А 9 20
В 6 20
АВ 2 35
0 7 15
Пациент Группа крови Требуемое количество крови (в пинтах)
1 А 3
2 В 3
3 АВ 2
4 О 1
Фантазия 29
ВСПОМНИМ О СПУТНИКЕ
Математика: тригонометрия
Предположим, что спутник выводится на экваториальную орбиту,
расположенную в 300 милях над поверхностью земли. Мы хотим расположить
станции слежения вдоль экватора. Каждая станция
8-1748
114
Фантазия 29
слежения располагает сканирующим экраном с диапазоном сканирования 180°,
как показано на рнс. 1.
Рис. I
Нужно расположить станции слежения таким образом, чтобы не оставалось
"мертвой зоны", в которой за спутником не будет наблюдать ни одна станция
(рис. 2).
Рис. 2
Наибольшее расстояние, на которое станции А и В могут быть удалены друг
от друга, показано на рис. 3.
Приняв радиус земли равным 4000 миль и заметив, что рис. 3 симметричен,
мы увидим, что нам нужно найти расстояние d на рис. 4.
Поскольку угол CES прямой,