5.19. Описать рекуррентные соотношения для применения метода динамического программирования.
Пусть
означает
расстояние от узла
до
узла
;
-
длина кратчайшего пути от узла
до
конечного узла
.
Тогда
рекуррентные соотношения будут иметь
вид
5.20. Описать рекуррентные соотношения для применения метода к задаче о распределении инвестиций.
Обозначим
через
максимальный
доход, получаемый от распределения
квоты
всем филиалам, то есть
По
принципу оптимальности: каково бы не
было значение
,
оставшаяся квота
должна
будет использоваться так, чтобы получить
максимальный доход в оставшихся
филиалах, то есть величину
.
Таким образом
для
5.21. Описать рекуррентные соотношения для применения метода динамического программирования задаче коммивояжера.
Рассмотрим
множество
.
Для любых
и
обозначим через
минимальную стоимость пути, который
начинается в городе 1, проходит через
все города множества
и заканчивается в городе
Тогда
(а)
Если
,
то
для любого
,
(б)
Если
,
то
.
(5.4.1)
Обозначим
через
длину минимального пути коммивояжера.
Тогда
(5.4.2)
Глава 6
6.1. В чем состоит основное отличие задач массового обслуживания от задач теории расписаний?
Для задач ТР известно, что все заявки уже находятся в системе (или прибудут туда в конкретные моменты времени) и требуется определить оптимальную по некоторому критерию очередность их обслуживания. Задачи МО по своей сущности являются вероятностными моделями, параметры которых меняются случайным образом. В частности, заявки поступают в систему в случайные моменты времени, случайное время могут ожидать в очереди на обслуживание и в течение случайного времени обслуживаться. Трудности исследования большинства задач МО заключаются прежде всего в нахождении законов распределения всех видов случайных величин, описывающих систему.
6.2. Описать составляющие задач массового обслуживания.
Задачи МО возникают в системах, для которых заданы следующие три составляющие:
1. Известны характеристики входного потока заявок на обслуживание.
2. Описана дисциплина очереди.
3. Задан механизм обслуживания.
Каждая СМО состоит из определенного числа обслуживающих единиц, которые будем называть приборами. Чтобы задать механизм обслуживания, необходимо указать количество приборов в системе, а также их взаимное расположение при обслуживании, например, последовательно расположенные приборы, на которых будут обслуживаться все заявки, или идентичные параллельно расположенные приборы, когда каждая заявка обслуживается на одном из них. Обслуживание характеризуется продолжительностью времени обслуживания, причем эти продолжительности являются случайными величинами. Часто, задавая механизм обслуживания, указывают также вероятности выхода приборов из строя.
Каждая СМО предназначена для выполнения потока заявок. Заявки поступают в случайные моменты времени, и принимается, что после обслуживания каждой заявки она уходит из системы и прибор готов для обслуживания следующей заявки. Случайный характер потока заявок может привести к тому, что в какие-то моменты времени на входе системы будет скапливаться некоторое число заявок, которые либо образуют очередь в ожидании обслуживания, либо уходят необслуженными. Может быть, что в отдельные моменты очереди не будет и приборы будут простаивать в ожидании заявок. При описании СМО также часто указывают, могут ли в отдельные моменты времени появиться сразу несколько заявок. Для некоторых систем источник, генерирующий заявки, находится вне системы и считается неисчерпаемым. Изучаются также системы, с ограниченным количеством возможных заявок, которые могут находиться в самой системе.
Дисциплина очереди – описание порядка выполнения заявок, например, при обслуживании могут выполняться требования типа: "первый пришел, первый обслуживается", или могут быть заранее установлены некоторые приоритеты, в соответствии с которыми классифицируются и, в конечном итоге, обслуживаются заявки, стоящие в очереди.