Основы математического программирования (стр. 26 )

Траектория, выделенная желтым цветом

G = 11 + 10 + 10 + 7 + 13 + 12 + 7 + 10 +10 + 11 +13 + 14 + 16 + 17 = 161

Можно перебрать все траектории, но их слишком много. Гораздо проще решить эту задачу методом динамического программирования.

Процесс состоит из 14 шагов.

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

Конечное состояние самолета нам задано. 14-ый шаг непременно приведет в эту точку3.

Находясь первоначально в этой точке (S14), перемещаемся в левый нижний угол таблицы, выбирая шаг с минимальным расходом топлива.

Чтобы найти в каждой узловой точке оптимальное управление, нужно посмотреть два возможных пути из этой точки – по вертикали и по горизонтали.

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

Например, находясь в точке S14 можно осуществить переход по горизонтали (расход 17 у. е.) или по вертикали (расход 14). Осуществляем переход по минимальному пути.

Находясь в точке S13, можно пойти по вертикали (расход 13), можно по горизонтали (расход 14) и т. д.

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

Если подсчитать расход, то он составит 138 у. е.

Оптимальное управление процессом будет состоять в следующем:

1. На первом шаге увеличить только скорость, сохраняя неизменной высоту Ho, и довести скорость до Vo + DV

2. На втором шаге увеличить высоту до Ho + DH, сохраняя скорость неизменной.

3. На третьем шаге увеличить скорость до Vo + 2DV.

4. На четвертом шаге увеличить высоту до Ho + 2DH.

5. На пятом и шестом шагах снова набирать скорость, пока она не станет равной Vo + 4DV.

6. На седьмом и восьмом шагах набирать высоту и довести ее до Ho + 4DH.

7. На девятом, десятом, и двенадцатом шагах снова набирать скорость и довести ее до заданного конечного значения Vf.

8. На последних двух шагах набирать высоту до заданного значения Hf.

Это простейший пример, на котором можно продемонстрировать основную идею динамического программирования

В действительности, это упрощенный вариант.

Такая упрощенная постановка задачи не вполне соответствует действительности. Фактически самолет набирает скорость и высоту одновременно. (кусочно-линейная аппроксимация).

По осям могут откладываться не только скорость и время, ,а, например, количества средств, вкладываемых в разные отрасли производства, а показателем эффективности может быть доход, приносимый группой предприятий.

Выбор системы координат, способ деления операций на шаги могут быть самыми разнообразными. Это диктуется соображениями удобства, наглядностью и т. п.

Теория массового обслуживания

Теория систем массового обслуживания началась с исследования причин неэффективности телефонных сетей.

Примерами СМО могут быть телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро и т. п.

Каждая СМО состоит из какого-то числа обслуживающих единиц, которые называются каналами обслуживания.

В качестве каналов можно рассматривать линии связи, рабочие точки, железнодорожные пути и т. п.

СМО могут быть одноканальными и многоканальными.

Каждая СМО предназначена для обслуживания какого-то потока заявок, поступающих на СМО в какие-то случайные моменты времени.

Обслуживание поступившей заявки продолжается некоторое (случайное) время, после чего канал освобождается и готов к принятию следующей заявки.

Случайный характер потока заявок приводит к тому, что в какие-то промежутки времени на входе СМО скапливается большое число заявок (они либо покидают СМО необслуженными, либо образуют очередь). В другие периоды СМО будет работать с недогрузкой или простаивать.

СМО в зависимости от числа каналов и их производительности, а также от характера потока заявок обладает какой-то пропускной способностью, позволяющей ей более или менее успешно справляться с потоком заявок.

Предмет теории массового обслуживания – установление зависимости между характером потока заявок, числом каналов, их производительностью, правилами работы СМО и эффективностью обслуживания.

Характеристиками эффективности могут быть:

· среднее количество заявок, которое может обслужить СМО в единицу времени;

· средний процент заявок, получающих отказ и покидающих СМО необслуженными;

· вероятность того, что поступившая заявка будет немедленно принята к обслуживанию;

· среднее время ожидания в очереди;

· среднее количество заявок, находящихся в очереди; средний доход, приносимый СМО в единицу времени и т. д.

Случайный характер, как потока заявок, так и длительности обслуживания приводит к тому, что в СМО будет происходить какой-то случайный процесс.

Чтобы дать рекомендации по рациональной организации этого процесса, надо его изучить и описать математически. Этим и занимается теория массового обслуживания.

Область применения теории массового обслуживания непрерывно расширяется. В качестве систем массового обслуживания могут рассматриваться информационно-вычислительные сети, операционные системы ЭВМ, системы сбора и обработки информации, поточные линии, транспортные системы, системы противоздушной обороны и т. п.

Математическое исследование СМО очень облегчается, если случайный процесс, протекающий в системе, является марковским.

Тогда можно легко описать работу СМО с помощью аппарата обыкновенных дифференциальных уравнений.

Рассмотрим кратко понятие марковского случайного процесса.

Случайный процесс, протекающий в системе S, называется марковским, если обладает следующим свойством: для каждого момента времени tй.o, вероятность любого состояния системы в будущем (при t > to) зависит только от ее состояния в настоящем (при t = to) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. от того, как развивался процесс в прошлом).

На практике очень часто встречаются случайные процессы, которые с той или и ной степенью приближения, являются марковскими. Теория марковских случайных величин является разделом теории вероятностей.

При рассмотрении случайных процессов, протекающих в СМО, основным понятием является потоки событий.

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

Примеры:

· поток вызовов на телефонную станцию

· поток включений приборов в бытовую электросеть

· поток неисправностей (сбоев) ЭВМ и т. п.

Как уже отмечалось, если случайный процесс в СМО не является марковским, то его математическое описание становится очень сложным и требует сложного математического аппарата, доведение которого до аналитических формул возможно только в самых простейших случаях.

Для того, чтобы процесс, протекающий в системе, был марковским, нужно, чтобы потоки событий были потоками без последействия.

Поток событий называется потоком без последействий, если для любых отрезков времени число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой

Примеры.

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

2. Поток грузовых поездов, идущих по железнодорожной ветке. Если по условиям безопасности они не могут следовать один за другим чаще, чем через интервал времени to, то между событиями в потоке имеется зависимость, и условие последействия нарушается. Однако, если интервал to мал по сравнению со средним интервалом между поездами, то такое нарушение несущественно.

В тех случаях, когда в СМО случайный процесс не является марковским, то с помощью аппарата «марковский» теории массового обслуживания, характеристики эффективности СМО оцениваются приближенно.

Следует отметить, что чем сложнее СМО, чем больше в ней каналов обслуживания, тем точнее оказываются приближенные формулы.

В ряде случаев для принятия обоснованного решения по управлению работой СМО вовсе и не требуется точного знания всех ее характеристик – зачастую достаточно приближенного.

Основные классы СМО:

1. Системы с отказами. В таких системах заявка, поступившая в момент, когда все каналы заняты, получает «отказ», покидает СМО и в дальнейшем процессе обслуживания не участвует.

2. Системы с ожиданием (с очередью). В таких системах заявка, поступившая в момент, когда все каналы заняты, становится в очередь и ожидает, пока не освободится один из каналов. Когда канал освобождается, одна из заявок, стоящих в очереди, принимается на обслуживание.

Системы с ожиданием бывают:

· упорядоченными – заявки обслуживаются в порядке поступления;

· неупорядоченными – заявки обслуживаются в случайном порядке;

· стековыми – первой из очереди выбирается последняя заявка;

· с приоритетом – некоторые заявки обслуживаются в первую очередь. С статическим приоритетом (приоритет постоянный). С динамическим приоритетом (приоритет увеличивается в зависимости от времени ожидания;

· с неограниченным ожиданием – любая заявка, поступившая в СМО, рано или поздно будет обслужена;

· с ограниченным ожиданием. Ограничения по длине очереди – система с ограниченной длиной очереди. Ограничения по времени пребывания заявок в очереди – система с ограничением времени ожидания.

В зависимости от типа МО применяются различные показатели эффективности.

СМО с отказами – важнейшие характеристики:

· абсолютная пропускная способность – среднее число заявок, обслуживаемых в единицу времени;

· относительная пропускная способность – отношение среднего числа заявок, обслуживаемых в единицу времени к среднему числу поступивших за это время заявок;

· среднее число занятых каналов;

· среднее относительное время простоя системы в целом и отдельного канала.

СМО с неограниченным ожиданием – важнейшие характеристики:

· среднее число заявок в очереди;

· среднее число заявок в системе (на обслуживании и в очереди);

· среднее время ожидания в очереди;

среднее время пребывания заявки в системе (на обслуживании и в очереди).

СМО с ограниченным ожиданием – важнейшие характеристики:

Возможны обе группы характеристик.

Для анализа процесса, протекающего в СМО надо знать основные параметры системы:

· число каналов n;

· интенсивность потока заявок l;

· производительность каждого канала (среднее число заявок m, обслуживаемых каналом в единицу времени);

· условия образования очереди (ограничения, если они есть).

В зависимости от значений этих параметров выражаются характеристики эффективности работы СМО.