Рассмотрены два типа моделей: распределения векторных ресурсов по сетевым графикам и транспортным сетям при наличии неопределенных факторов или противника и детерминированные модели.
Задачи распределения ресурсов на сетевых графиках и транспортных сетях в детерминированном случае весьма просто сводятся к задачам нелинейного программирования. Если же имеются неопределенные факторы, то поиск гарантированного распределения ресурсов в прямой постановке приводит к задаче тройной оптимизации игрового характера со связанными ограничениями, и требуется определенное искусство, чтобы свести эти задачи к задачам нелинейного программирования.
В данной главе не приводятся алгоритмы решения задач, поскольку эти задачи являются задачами нелинейного программирования, где имеется очень много известных алгоритмов решения. Выбор каждого алгоритма обусловливается особенностями задачи и имеющимся математическим обеспечением. Впрочем, в список литературы включено довольно много руководств, содержащих описание и даже программы на различных алгоритмических языках алгоритмов локальной, глобальной и выпуклой оптимизации.
На первый взгляд может показаться, что рассмотрение случая конечного числа значений неопределенных факторов сужает область применимости рассматриваемых задач. Но это ограничение, во-первых, позволяет значительно упростить структуру задач, а во-вторых, не является слишком ограничительным, поскольку любую непрерывную игру на компактных множествах стратегий игроков можно аппроксимировать конечной игрой, выбрав достаточно плотные сетки на множествах стратегий игроков.
8.5.1. Основы сетевого планирования.
Время выполнения комплекса работ равно Возьмем ориентированный граф {MJSl) обла-
величине критического дающий следующими свойствами: 1) сущест-"У"1[ вует единственная вершина графа Z], из ко-
торой дуги только выходят, т.е. не существует дуг вида (zy,zi); 2) существует единственная вершина графа , в которую дуги только входят, т.е. не существует дуг вида {zj,Zj)\ 3) в графе отсутствуют замкнутые пути и, следовательно, все пути в нем простые; 4) пусть zi,...,Z; - все вершины фафа,1, w, - все дуги графа, тогда для любой вер-
шины2/ существует путь из Z] в z, проходящий через эту вершину, а для любой дуги lj,j= \, ,..,т существует путь из zj в z, содержащий эту дугу.
Вершины нашего графа будем называть событиями, а его дуги - работами. Пусть каждой работе Ij поставлено в соответствие
число гу >0,7 = 1,которое назовем продолжительностью рабо-
Граф, удовлетворяющий всем перечисленным ограничениям и имеющий все перечисленные характеристики, называется сетевым графиком.
Содержательное истолкование сетевого графика состоит в следующем. Имеется проект, состоящий из работ /у,7 = 1,Для каждой
работы задана ее продолжительность. Событие zj- начало всех работ. С началом работ начинаются все работы, выходящие из события Z]. Каждое промежуточное событие z состоит в том, что окончились все работы, входящие в z-, и начались все работы, выходящие из z. Наступление события означает окончание всех работ. Если бы в сетевом
графике существовал замкнутый путь, то существовала бы последовательность событий z/,z-2,...,z/ ,zy, соединенных работами. Пусть г, s
= 1,к - 1,- время наступления события z-, тогда
ti <t2 <...</jt i </i. Но это противоречие. Следовательно, для содержательной непротиворечивости необходимо отсутствие замкнутых путей в сетевом графике.
Пусть дан путь zi,...,zy и пусть /., / = 1, - дуги этого пути. Ве-
личиной пути назовем число dj = 2 »- продолжительность
работы / .
В дальнейшем будем считать, что событие Z] наступает в нулевой момент времени.
Теорема. Время наступления события Zj равно d. = max d\, где
1<S<1
с/у"", 5 = 1,...,/, - величины всех путей из Z] в zj.
Максимальный по величине путь из Z] в будет определять время
окончания всего комплекса работ, т.е. время совершения события z.
Такой путь называется критическим.
Рассмотрим работу . Пусть начало этой работы есть событие z- и
ведет работа в событие Zj, тогда, если продолжительность работы есть
, должно выполняться условие
hsh-s = l,...,/w.(8.5)
Числа t,,.,,t, удовлетворяющие условию (8.5), будем называть календарным планом.
Если задан календарный план, то продолжительность всего комплекса работ будет (t -/j). Естественно стремиться к назначению такого календарного плана, при котором продолжительность всего комплекса работ бьша бы минимальной. Тогда надо решить задачу.
in(/;7-/l),(8.6)
Задача (8.6) есть задача линейного программирования.
8.5.2, Оптимальное распределение ресурсов на сетевых графиках в детерминированном случае. Рассмотрим сетевой график с событиями zi,...,z и работами Ij ,j = 1,..., т, причем будем считать, что zj - начало всех работ, Zj - их окончание. Предположим также, что времена
выполнения всех работ есть функции от распределений ресурсов. При этом будем предполагать, что задано множество X распределений ресурсов, и как только выбрано распределение ресурсов хе X, так сразу же определяются функцииу(х), т.е. времена выполнения работ Ij,j = 1,...,
т. Будем считать, что функции (pj{x)J = 1,..., т, - непрерьгоные функции, а множество X - компактное множество евклидова пространства
Е. Поставим задачу нахождения такого распределения ресурсов, чтобы время выполнения всех работ было минимальным. Если распределение ресурсов л: € X выбрано, то время выполнения всех работ согласно (8.6) будет определяться из решения задачи 234