Задачи сетевого программирования.

34.По данным таблицы 10 построить сеть.

Таблица 10.

Обозначение работы

Непосредст венно предшествующие работы

–

–

–

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

35. В горной лесопарковой зоне расположено семь площадок для отдыха, соединенных тропами. Расположение площадок и длины троп указаны на рисунке 13. Найти кратчайший путь из в.

36.Комплекс работ представлен сетевым графиком (см. рис.14). Известна продолжительность (в днях) каждой работы и количество единиц ресурса, необходимо для выполнения работы в единицу времени, - интенсивность потребления ресурса (число в скобках). Построить линейный график и найти по нему критический срок, критические работы и резервы времени некритических работ. Построить шкалу потребления ресурса.

37.Предположим, что в условиях задачи 36 требуется установить время начала и окончания каждой работы так, чтобы завершить комплекс в возможно меньшее время, при условии, что в любой момент в период выполнения работ расход ресурса не должен превышать 100 ед.

38.Найти кратчайший путь из в ,из вдля сетей, изображенных соответственно на: а) рис.15; б) рис.16.

39. Для местного аэропорта приобретается автокар. Через три года планируется установка механизированной погрузочной системы, после чего автокары станут ненужными. Тем не менее, может оказаться выгодным заменить автокар через год или два года или даже осуществить две замены (через год и через два года). В следующей таблице 11 приведены полные расходы (с учетом стоимости эксплуатации и выручкой от продажи), связанные с покупкой автокара в конце года i и его продажей в конце года j.

Год покупки (i)	Год продажи (j)

Таблица 11.

Необходимо минимизировать расходы. Сформулировать задачу как задачу выбора кратчайшего пути. Решить полученную задачу.

40. Описать алгоритм построения минимального остовного дерева для данной сети, т.е. дерева с дугами из данной сети, содержащего все ее вершины, и такого, что сумма длин дуг минимальна.

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

42. Построить минимальные связывающие деревья (см. задачу 40) для сетей задачи 38.

43. Сформулировать задачу построения максимального потока как задачу линейного программирования.

44. Найти максимальные потоки из до , из до в сетях, изображенных соответственно на: а) рис. 17; б) рис. 18 (на дугах указаны их пропускные способности в каждом из направлений).

45. На железной дороге между узловыми станциями и расположены промежуточные станции . Движение пассажирских поездов из в происходит в строгом соответствии с заданным расписанием. На запасных путях промежуточной станции может одновременно находиться не более товарных поездов. Пусть между станциями и занимает для товарного поезда мин (все кратны 5). Товарные поезда могут отправляться со станций начиная с 0 часов с интервалом в 5 мин. Ни с какой станции не могут одновременно отправиться более одного товарного поезда. Товарный поезд может отправиться в данный момент со станции лишь при условии, что он не помешает движению пассажирских поездов до момента, пока не достигнет станции, запасные пути которой заполнены не полностью. Необходимо составить расписание товарных поездов так, чтобы общее число товарных поездов, вышедших в течение данных суток из и прибывших в , было максимальным. Сформулировать эту задачу как задачу построения максимального потока в сети.

46. Информация о проекте задана перечнем работ, их продолжительностью выполнения (таблица 12). Построить сетевой график проекта, найти критическое время проекта и критический путь, если известно, что в i-ю работу можно вложить средства , где , при этом время выполнения работы уменьшиться до .

Таблица 12.

Работа	Каким работам предшест вует	Продол житель ность, мес.	Работа	Каким работам предшест вует	Продол житель ность, мес.
	4, 5, 6
	4, 5, 6
	5, 6
				–

47. Начальное условие как в задаче 46, полагая , определить размер вложенных средств в 1-ю, 4-ю и 8-ю работы так, чтобы время завершения всего комплекса работ не превышало 40 мес., а сумма вложений была минимальной.

48. Начальное условие как в задаче 46. В общем случае сформулировать задачу минимизации суммы вложений, необходимых для того, чтобы обеспечить завершение всего комплекса работ к заданному моменту времени T, как задачу линейного программирования.

49. Информация о проекте задана перечнем работ, их продолжительностью и последовательностью выполнения (таблица 13). Построить сеть проекта.

50. Пронумеровать сеть, построенную в задаче 49. Для сети, найти минимальные и максимальные моменты времени , наступления событий , критическое время проекта и критический путь.

Таблица 13.

Работа	Каким работам предшест вует	Продол житель ность в днях	Работа	Каким работам предшест вует	Продол житель ность в днях
	11, 15
	1, 13			–
	9, 14
				1, 13
	–			9, 14
	3, 4
	8, 2			9, 14
	11, 15

Задачи теории игр.

Для следующих платежных матриц определить нижнюю и верхнюю цены игры двух участников, минимаксные стратегии и наличие седловых точек. В последнем случае определить оптимальное решение игры.

60. Для игры, задаваемой матрицей . Определить цену игры и найти оптимальные стратегии.

61. Игра заключается в том, что игрок А записывает числа 1(стратегия ), или 2( ), или 3( ). Игрок В, в свою очередь, может записать числа 1( ) , 2( ), 3( ), или 4( ). Если оба числа окажутся равной четности, то А выигрывает сумму этих чисел, если – разной четности, то В выигрывает сумму этих чисел. Составить платежную матрицу, определить верхнюю и нижнюю цену игры и минимаксные стратегии.

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

63. Система противовоздушной обороны (ПВО) обороняет от воздушного налета участок территории, располагая двумя зенитно–ракетными комплексами (ЗРК), зоны действия которых не перекрываются. Каждый ЗРК с единичной вероятностью поражает самолет противника в зоне своего действия, если его система наведения начинает отслеживать цель и вырабатывать данные для стрельбы еще за пределами зоны. Противник располагает двумя самолетами, каждый из которых может быть направлен в зону действия любого ЗРК.

В момент, когда система ПВО решает задачу целераспределения, т.е. решает, какому ЗРК по какой цели стрелять, самолеты противника могут применить обманный маневр и изменить маршрут. Цель системы ПВО – поразить как можно больше самолетов противника, а цель противника – потерять как можно меньше самолетов. а) Постройте платежную матрицу игры; б) установите имеются ли седловые точки; в) найдите оптимальное решение.

64. Два человека оказались в горящем доме. Они могут покинуть дом и спастись лишь через входную дверь, которую заклинило так сильно, что открыть ее можно только совместными усилиями. Построить платежную матрицу игры. Имеет ли игра седловую точку?

65. Имеются два игрока: игрок А прячется, а игрок В его ищет. Игрок А по своему усмотрению может спрятаться в любом из убежищ с номерами 1 и 2 соответственно. Если игрок В найдет игрока А в том убежище, где тот спрятался, то игрок А платит игроку В штраф в две денежные единицы. Если игрок В будет искать игрока А не в том убежище, где тот спрятался, то игрок В платит игроку А такой же штраф. Для этой игры: а) постройте платежную матрицу игры; б) установите имеются ли седловые точки; в) найдите оптимальное решение.

66. Доказать, что цена игры удовлетворяет соотношениям .

67. Рассчитать величину платежа для игр, заданных матрицами задач 51 и 52 при и .

68. Доказать, что решение игры не измениться, если ко всем элементам платежной матрицы прибавить некоторое постоянное число. Как при этом измениться цена игры?

69. Найти решение игры с матрицей и дать геометрическую интерпретацию этому решению.

70 -72. Найдите седловую точку и чистую цену в игре двух участников, в которой платежная матрица второго игрока имеет вид: