3. Дискретно – стохастические модели p – схемы

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

Рассмотрим множество G, элементами которого являются всевозможные пары (xi,zs), где xi и zs – элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции Фи и Кси, то с их помощью осуществляется отображения G->Z и G->Y, то говорят, что F=(Z, X, Y, Фи, Кси) определяет автомат детерминированного типа.

Пусть Ф – множество всевозможных пар вида (zk, yj), где yj – элемент выходного подмножества Y. Пусть любой элемент множества G способствует появлению на множестве Ф некоторого закона распределения.

При этом , где bkj – вероятности перехода автомата в состояние zk и поялвение на выходе сигнала yj, если он был в состоянии zs, и на его вход в этот момент времени поступил сигнал xi.

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

Обозначим множество этих таблиц через B. Тогда четверка элементов P=(Z, X, Y, B) называется вероятностным автоматом (P – автоматом).

Если для всех k и j имеет место соотношение , то такой P – автомат называется вероятностным автоматом Мили.

Если для всех k и I имеет место соотношение , то такой P – автомат называется вероятностным автоматом Мура.

Если выходной сигнал P – автомата определяется детерминировано, то такой автомат называется Y – детерминированным вероятностным автоматом. Аналогично, Z – детерминированным вероятностным автоматом называется автомат, у которого выбор нового состояния является детерминированным.

Итог: P – автоматы могут использоваться как генераторы Марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды E.

4. Непрерывно-стохастические модели q-схемы

Система массового обслуживания – Q-схема.

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

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявки и обслуживание заявки.

Пусть имеется некоторый i-ый прибор обслуживания Пi, состоящий из накопителя заявок Нi, в котором может одновременно находиться заявок, где - емкость i-го накопителя, и канала обслуживания заявок (или просто канала) Ki. На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi – поток заявок wi, на канал Ki – поток обслуживания ui.

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

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

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

Выходной поток – заявки, обслуженные каналом Ki, и заявки, покинувшие прибор Пi, по различным причинам не обслуженными.

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

Если приборы соединены параллельно, то имеет место многофазное обслуживание.

Разомкнутая Q-схема: выходной поток обслуженных заявок не может снова поступить на какой-либо элемент, т.е. обратная связь отсутствует.

Замкнутая Q-схема: имеются обратные связи, по которым заявки двигаются в направлении, обратном движению вход-выход.

В теории СМО применяют терминологию:

• системы с потерями;

• системы с ожиданиями;

• системы смешанного типа.

В зависимости от динамики приоритетов:

• статические – назначаются заранее и не зависят от состояния схемы;

• динамически – возникают при моделировании в зависимости от возникающих ситуаций.

На обслуживание канала можно выделить следующие приоритеты;

• относительный – заявка с более высоким приоритетом ожидает предшествующую заявку, после этого занимает канал;

• абсолютный – заявка с более высоким приоритетом прерывает обслуживание заявки с более низким приоритетом и занимает канал.

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

Таким образом, Q-схему можно описать , где W – множество входящих потоков, H – подмножество собственных параметров (обслуживание с бесконечной емкостью накопителя), Z – множество состояний, R – оператора сопряжения элементов структуры (однофазовое обслуживание в разомкнутой системе), А – оператор алгоритмов обслуживания заявок (без приоритетное обслуживание, без прерываний и блокировок).

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

Вопросы с 25 по 35

25

Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

• математические модели очень большого числа экономических задач линейны относительно искомых переменных;

• эти типы задач в настоящее время наиболее изучены;

• для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

• многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;

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

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

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

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

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

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

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что  а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);

• систему ограничений в форме линейных уравнений и неравенств;

• требование неотрицательности переменных.

26 Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.^[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP.

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.

ПРИМЕР. Матрица тарифов (здесь количество поставщиков равно 4, количество магазинов равно 6):

	1	2	3	4	5	6	Запасы
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	10	1	100	60
Потребности	10	30	40	50	70	30

Решение. Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.  ∑a = 80 + 60 + 30 + 60 = 230  ∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230  Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.  На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).  Для демонстрации алгоритма приведем лишь несколько итераций.  Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60, потребности 30. Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).

3	20	8	13	4	x	80
4	4	18	14	3	0	60 - 30 = 30
10	4	18	8	6	x	30
7	19	17	0	1	x	60
10	30	40	50	70	30 - 30 = 0	0

Итерация №2. Снова ищем минимум (0). Из пары (60;50) выбираем минимальное число 50. Вычеркиваем пятый столбец.

3	20	8	x	4	x	80
4	4	18	x	3	0	30
10	4	18	x	6	x	30
7	19	17	0	1	x	60 - 50 = 10
10	30	40	50 - 50 = 0	70	0	0

Итерация №3. Процесс продолжаем до тех пор, пока не выберем все потребности и запасы.  Итерация №N. Искомый элемент равен 8. Для этого элемента запасы равны потребностям (40).

3	x	8	x	4	x	40 - 40 = 0
x	x	x	x	3	0	0
x	4	x	x	x	x	0
x	x	x	0	1	x	0
0	0	40 - 40 = 0	0	0	0	0

	1	2	3	4	5	6	Запасы
1	3[10]	20	8[40]	13	4[30]	100	80
2	4	4	18	14	3[30]	0[30]	60
3	10	4[30]	18	8	6	0	30
4	7	19	17	0[50]	1[10]	100	60
Потребности	10	30	40	50	70	30

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 9. Следовательно, опорный план является вырожденным. Строим новый план. Иногда приходится строить несколько опорных планов, прежде чем найти не вырожденный.

	1	2	3	4	5	6	Запасы
1	3[10]	20	8[40]	13[30]	4	100	80
2	4	4[20]	18	14	3[10]	0[30]	60
3	10	4[10]	18	8[20]	6	0	30
4	7	19	17	0	1[60]	100	60
Потребности	10	30	40	50	70	30

В результате получен первый опорный план, который является допустимым, так как число занятых клеток таблицы равно 9 и соответствует формуле m + n - 1 = 6 + 4 - 1 = 9, т.е. опорный план является невырожденным.  Третий этап заключается в улучшении найденного опорного плана. Здесь используют метод потенциалов илираспределительный метод. На этом этапе правильность решения можно контролировать через функцию стоимости F(x). Если она уменьшается (при условии минимазации затрат), то ход решения верный.