«Институт Экономики, управления и права Кафедра управления качеством и механики ЭКОНОМИКА КАЧЕСТВА И МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЗАТРАТ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА ДИСЦИПЛИНЫ (рабочая учебная программа дисциплины) ...»

Сигнал есть сообщение о состоянии элемента.

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

Состояние элемента может меняться самопроизвольно, или в результате сигналов и воздействий, поступающих извне системы.

Сообщение - это совокупность сигналов.

Сигналы, вырабатываемые элементами системы, могут поступать за пределы системы, в этом случае они называются выходными сигналами системы. В свою очередь, на элементы могут поступать сигналы извне системы, они называются входными. Аналогичным образом определяются входные и выходные воздействия.

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

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

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

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

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

1.2. Классификация систем.

Классификацию кибернетических систем мы проведем по двум критериям: степень сложности системы и ее детерминированность.

По степени сложности системы бывают:

1. Простые.

2. Сложные.

3. Сверхсложные.

К простым относятся системы, имеющие простую структуру и легко поддающиеся математическому описанию, они могут быть реализованы без использования ЭВМ.

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

Сверхсложные системы не поддаются математическому описанию.

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

По второму критерию системы делятся на детерминированные и вероятностные.

Все возможные случаи получаются комбинированием указанных классов:

1. Простые детерминированные системы:

- холодильник с регулятором;

- система размещения станков в цехе;

- система автобусных маршрутов;

- расписание занятий факультета;

2. Сложные детерминированные системы:

3. Сверхсложные детерминированные системы:

4. Простые вероятностные системы:

- система статистического контроля продукции на предприятии;

5. Сложные вероятностные системы:

- система материально-технического снабжения на предприятии;

- система диспетчирования движения самолетов вблизи крупного аэропорта;

- система диспетчирования энергетической системы России;

6. Сверхсложные вероятностные системы:

- предприятие в целом, включая все его технические, экономические, административные, социальные характеристики;

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

Состояние системы - это совокупность значений ее показателей.

Все возможные состояния системы образуют ее множество состояний. Если в этом множестве определено понятие близости элементов, то оно называется пространством состояний.

Движение (поведение) системы - это процесс перехода системы из одного состояния в другое, из него в третье и т.д.

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

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

Возможны следующие режимы движения системы:

1) равновесный, когда система находится все время в одном и том же состоянии;

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

Если система находится в равновесном или периодическом режиме, то говорят, что она находится в установившемся или стационарном режиме.

3) переходный режим - движение системы между двумя периодами времени, в каждом из которых система находилась в стационарном режиме;

4) апериодический режим - система проходит некоторое множество состояний, однако закономерность прохождения этих состояний является более сложной, чем периодические, например, переменный период;

5) эргодический режим - система проходит все пространство состояний таким образом, что с течением времени проходит сколько угодно близко к любому заданному состоянию.

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

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

1.5. Кибернетическое моделирование В процессе исследования объекта часто бывает нецелесообразно или даже невозможно иметь дело непосредственно с этим объектом. Удобнее бывает заменить его другим объектом, подобным данному в тех аспектах, которые важны в данном исследовании. Например, модель самолета продувают в аэродинамической трубе, вместо того, чтобы испытывать настоящий самолет - это дешевле. При теоретическом исследовании атомного ядра физики представляют его в виде капли жидкости, имеющей поверхностное натяжение, вязкость и т.п. Управляемые объекты являются, как правило, очень сложными, поэтому процесс управления неотделим от процесса изучения этих объектов.

Модель - это мысленно представляемая или материально реализованная система, которая, отображая или воспроизводя объект исследования, способна замещать его так, что ее изучение дает новую информацию об этом объекте.

При моделировании используется аналогия между объектом оригиналом и его моделью. Аналогии бывают следующими:

1) внешняя аналогия (модель самолета, корабля, микрорайона, выкройка);

2) структурная аналогия (водопроводная сеть и электросеть моделируются с помощью графов, отражающих все связи и пересечения, но не длины отдельных трубопроводов);

3) динамическая аналогия (по поведению системы) - маятник моделирует электрический колебательный контур;

4) кибернетические модели относятся ко второму и третьему типу.

Для них свойственно то, что они реализуются с помощью ЭВМ. Смысл кибернетического моделирования заключается в том, что эксперименты проводятся не с реальной физической моделью объекта, а с его описанием, которое помещается в память ЭВМ вместе с программами, реализующими изменения показателей объекта, предусмотренные этим описанием.

С описанием производят машинные эксперименты: меняют те или иные показатели, т.е. изменяют состояние объекта и регистрируют его поведение в этих условиях. Часто поведение объекта имитируется во много раз быстрее, чем на самом деле, благодаря быстродействию ЭВМ.

Кибернетическую модель часто называют имитационной моделью.

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

Следующим этапом является составление математических моделей эффективного функционирования объекта и его системной модели. Затем производится программирование описания и моделей его функционирования.

2. Задачи линейного программирования Существует множество форм деятельности предприятий, которые связаны с распределением ресурсов. Эти ресурсы включают труд, сырье, оборудование и денежные средства. Иногда процесс распределения ресурсов называют программированием. Поскольку обычно размеры ресурсов ограничены, возникают определенные проблемы. Если компания выпускает продукцию нескольких видов с использованием одного и того же оборудования и трудовых ресурсов, то ее администрация должна решить, какое количество продукции каждого вида производить. Принятое решение будет направлено на удовлетворение определенной цели администрации. Администрация может задаться целью наладить производство таким образом, чтобы максимизировать общий выпуск продукции за месяц, максимизировать время использования оборудования за неделю или минимизировать еженедельные затраты труда.

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

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

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

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

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

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

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

3. Когда оптимальное решение получено, производится его оценка. Она включает в себя анализ задачи на чувствительность.

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

ФОРМУЛИРОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Шаг 2. Определение цели и ограничений на ресурсы.

Шаг 3. Описание цели через переменные задачи.

Шаг 4. Описание ограничений через переменные задачи.

Хотя на применение данной процедуры не влияет число переменных в задаче линейного программирования, рассмотрим сначала задачу с двумя переменными.

Пример 1.1. Небольшая семейная фирма производит два широко популярных безалкогольных напитка — "Pink Fizz" и "Mint Pop". Фирма может продать всю продукцию, которая будет произведена, однако объем производства ограничен количеством основного ингредиента и" производственной мощностью имеющегося оборудования. Для производства 1 л "Pink Fizz" требуется 0,02 ч работы оборудования, а для производства 1 л "Mint Pop" — 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л "Pink Fizz" и "Mint Pop" соответственно. Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Доход фирмы составляет 0,10 ф. ст. за 1 л "Pink Fizz" и 0,30 ф. ст. за 1 л "Mint Pop". Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневного дохода?

Шаг 1. Определение переменных. В рамках заданных ограничений фирма должна принять решение о том, какое количество каждого вида напитков следует выпускать. Пусть р — число литров "Pink Fizz", производимое за день.

Пусть m — число литров "Mint Pop", производимое за день.

Шаг 2. Определение цели и ограничений. Цель состоит в максимизации ежедневного дохода. Пусть Р — ежедневный доход, ф. ст. Он максимизируется в рамках ограничений на количество часов работы оборудования и наличие специального ингредиента.

Шаг 3- Выразим цель через переменные:

Р = 0,10 р + 0.30 m (ф. ст. в день).

Это целевая функция задачи — количественное соотношение, которое подлежит оптимизации.

Шаг 4. Выразим ограничения через переменные. Существуют следующие ограничения на производственный процесс:

а) Время работы оборудования. Для производства р литров "Pink Fizz" и "MintPop" требуется: (0,02 р + 0,04 m) часов работы оборудования ежедневно.

Максимальное время работы оборудования в день составляет 24 ч, следовательно, объем производства должен быть таким, чтобы число затраченных часов работы оборудования было меньше либо равно 24 ч ежедневно. Таким образом, 0,02 р + 0.04 m 24 ч/день.

б) Специальный ингредиент. Производство р литров "Pink Eizz" и m литров "Mint Pop" требует (0,01 р + 0,04 m) кг ингредиента ежедневно.

Максимальный расход ингредиента составляет 16 кг в день, следовательно, объем производства должен быть таким, чтобы требуемое количество специального ингредиента составляло не более 16 кг в день. Таким образом, 0,01 р + 0,04 m 16 кг/день.

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

в) Условие неотрицательности:

Окончательная формулировка задачи линейного программирования имеет следующий вид. Максимизировать:

Р = 0,10 р + 0,30 m (ф. ст. в день) при ограничениях:

время работы оборудования: 0,02 р + 0,04 m 24 ч/день;

специальный ингредиент: 0,01 р + 0,04 m 16 кг/день;

Пример 1.2. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей: Х и Y. Завод располагает фондом рабочего времени в 4000 чел.-ч. в неделю. Для производства одной детали типа X требуется 1 чел.-ч, а для производства одной детали типа Y — 2 чел.-ч.

Производственные мощности завода позволяют выпускать максимум деталей типа Х и 1750 деталей типа Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю.

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

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ф. ст., а от производства одной детали типа Y — 40 ф. ст.?

программирования.

Шаг 1. Идентификация переменных. Необходимо произвести х деталей типа Х и у деталей типа Y в неделю.

Шаг 2. Какова цель задачи? Каковы ограничения на процесс производства?

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

а) фонда рабочего времени — максимально возможный фонд рабочего времени составляет 4000 чел. -ч. в неделю.

б) производственной мощности — для каждого типа деталей существует отдельное ограничение по производственной мощности. Оборудование позволяет выпускать не более 2250 деталей типа Х и 1750 типа Y в в) металлических стержней — максимальный их уровень составляет 10000 кг в неделю.

г) листового металла — максимальный уровень этого ресурса равен кг в неделю.

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

а) постоянные заказы — число произведенных деталей Х должно быть достаточным для удовлетворения размера постоянных заказов.

б) Профсоюзное соглашение —общее число деталей (х + у) не должно быть ниже объема, предусмотренного соглашением.

Шаг 3. Целевая функция. Пусть Р — общий доход за неделю, ф. ст., где Р = 30 х + 40 у (ф. ст. в неделю).

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

Требуемый фонд рабочего времени: х + 2 у S 4000 чел.-ч.

Требуемая производственная мощность: х 2250 деталей Требуемое количество металлических Требуемое количество листового металла: 5 х +2 у 10000 кг Окончательная формулировка задачи линейного программирования имеет виды Производится х деталей типа Х и у деталей типа У в неделю.

Максимизировать:

Р=30х+40у(ф.ст.) при ограничениях:

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

Общая схема формулировки и в этом случае остается неизменной.

Пример 1.3. Завод по производству электронного оборудования выпускает персональные компьютеры и системы подготовки текстов. В настоящее время освоены четыре модели:

а) "Юпитер" — объем памяти 512 Кбайт, одинарный дисковод;

б) "Венера" — объем памяти 512 Кбайт, двойной дисковод;

в) "Марс" — объем памяти 640 Кбайт, двойной дисковод;

г) "Сатурн" — объем памяти 640 Кбайт, жесткий диск.

В производственный процесс вовлечены три цеха завода — цех узловой сборки, сборочный и испытательный. Распределение времени, требуемого для обработки каждой модели в каждом цехе, а также максимальные производственные мощности цехов приведены в табл. 1.1. Отдел исследований рынка производит периодическую оценку потребительского спроса на каждую модель. Максимальные прогнозные значения спроса и доходы от реализации единицы продукции каждой модели также содержатся в табл. 1.1.

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

Решение.

Шаг 1. Выбор переменных. Производится Таблица 1.1.

Время, требуемое на обработку каждой модели в каждом цехе Испытательн Максимально е прогнозное значение месяц Шаг 2. Какова цель задачи? Каковы ограничения на производственный процесс? Цель состоит в максимизации общего дохода за месяц. Объем производства ограничен размером фонда рабочего времени по каждому цеху и возможностью продажи компьютеров каждой модели.

Шаг 3. Целевая функция задачи. Пусть Р (ф. ст.) — общий доход в месяц, тогда:

Р = 15 j + 30 v + 120 m + 130 s (ф. ст. в месяц).

Шаг 4. Ограничения на производственный процесс. Для каждого цеха время, требуемое для производства j, v, m их единиц продукции соответствующих моделей увязывается с максимальной производственной мощностью данного цеха.

Окончательная формулировка задачи линейного программирования такова:

каждый месяц производится j, v, m и s единиц компьютеров типа "Юпитер", "Венера", "Марс" и "Сатурн" соответственно. Максимизировать:

Р = 15 j + 30 v + 120m + 130 s (ф. ст. в месяц) в условиях ограничений, указанных выше.

Пример 1.4.. Менеджер по ценным бумагам намерен разместить 100000 ф.

ст. капитала таким образом, чтобы получать максимальные годовые проценты с дохода. Его выбор ограничен четырьмя возможными объектами инвестиций: А, В, С и D. Объект А позволяет получать 6% годовых, объект В — 8% годовых, объект С — 10%, а объект D — 9% годовых. Для всех четырех объектов степень риска и условия размещения капитала различны. Чтобы не подвергать риску имеющийся капитал, менеджер принял решение, что не менее половины инвестиций необходимо вложить в объекты А и В. Чтобы обеспечить ликвидность, не менее 25% общей суммы капитала нужно поместить в объект предусматривается, что в объект С следует вкладывать не более 20% инвестиций, тогда как особенности налоговой политики требуют, чтобы в объект А было вложено не менее 30% капитала. Сформулируем для изложенной проблемы распределения инвестиций модель линейного программирования.

Решение Вкладывается а ф. ст. в объект А, b ф. ст. — в объект В, с ф. ст. — в объект C u d ф. ст. — в объект D. Целью является максимизация общей суммы годовых процентов с дохода. На распределение инвестиций наложены ограничения, связанные с отсутствием риска, ликвидностью, политикой правительства и системой налогообложения. Обозначим через R общую сумму годового процентного дохода, тогда:

R = 0,06 а + 0,08 b + 0,10 с + 0,09 d (ф. ст. в год).

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

Максимизируется общая сумма годового процентного дохода, т.е.:

R=0,06 а + 0,08 b + 0,10 с + 0,09 d (ф. ст. в год) в условиях следующих ограничений (ф. ст.):

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

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача линейного программирования в данном случае принимает следующий вид: производится х деталей типа Х и у деталей типа Y в неделю. Цель состоит в максимизации общего дохода в неделю. Максимизировать:

Р = 30 х + 40 у (ф. ст. в неделю) при ограничениях:

Такие вспомогательные переменные для ограничений со знаком " " называются остаточными переменными. Они представляют собой количество недоиспользуемого ресурса, т.е. разность между используемым количеством ресурса и его максимальным объемом. Рассмотрим, например, ограничение на фонд рабочего времени, указанное выше. Предположим, что в течение недели выпускается 1000 деталей каждого типа, тогда используемое число человекочасов составит: 1х1000 + 2х1000 = 3000. Поскольку максимальный фонд рабочего времени равен 4000 чел.-ч., резерв времени, или остаток, составит:

4000 - 3000 = 1000 чел.-ч. Следовательно, для данной комбинации х - у и s принимают значение, равное 1000.

Вспомогательные переменные, используемые в ограничениях типа " ", называются избыточными переменными, так как они показывают количество ресурса, используемое сверх минимального его объема. Рассмотрим, к примеру, ограничение на постоянные заказы в случае, когда выпускается 1000 деталей типа X. Минимальное число деталей типа Х составляет в соответствии с данным ограничением 600 штук, следовательно, уровень производства, равный 1000 деталей, порождает излишек в 400 штук сверх минимального количества.

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

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

Графическое решение задачи линейного программирования.

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

Например,неравенство х 7 означает, что х принимает значения, которые либо меньше 7, либо равны 7. Графически эту ситуацию можно проиллюстрировать следующим. образом. Проведем прямую х = 7. Обратимся к графику, изображенному на рис.1.1 слева. Данная прямая разделяет плоскость на три множества точек: точки, для которых х = 7, т.е. точки, лежащие на самой прямой; точки, для которых х < 7, область слева от прямой; и точки, для которых х > 7, т.е. точки, принадлежащие области, лежащей справа от прямой.

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

Предположим, что х + у 10. Какую часть плоскости описывает данное неравенство? Схема поиска ответа на этот вопрос аналогична схеме, используемой в предыдущем примере. Во-первых, проведем прямую х + у = 10.

Обратимся к графику, изображенному на рис. 1.2. слева. Как и в предыдущем примере, проведенная прямая разделяет плоскость на три множества точек:

точки, для которых х + у = 10, принадлежащие прямой; точки, для которых х + у < 10, принадлежащие области, лежащей ниже прямой; и точки, для которых х + у > 10, принадлежащие области, лежащей выше указанной прямой.

Полезным приемом при определении недопустимой области на графике является следующая процедура. Необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением. Если неравенство не выполняется, то точка является недопустимой и принадлежит, следовательно, недопустимой области. Удобной для использования при подстановке в неравенство точкой является начало координат. Подставим х = у = 0 в неравенство х + у 10. Получим 0 + 0 10.

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

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

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

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

Ограничения задачи можно изобразить графически Время работы оборудования: 0,02 р + 0,04 m 24 ч/день, Проведем прямую 0,02 р + 0,04 m = 24. Простейшим способом нанесения прямой на график является нахождение точек пересечения данной прямой с осями координат р и m. Подставив р = 0 в уравнение и рассчитав значение m, получим, что при р = 0 m = 600. Подставив m = 0 в уравнение и рассчитав значение р, получим, что при m = 0 р = 1200. Нанесем эти две точки на график и соединим их прямой. Этим приемом можно пользоваться всегда, за исключением случая, когда прямая проходит через начало координат. В последнем случае применяется иная процедура подстановки в уравнение любого другого значения р и нахождения соответствующего значения m.

Для определения области, которую следует заштриховать, подставим р = 0 и m = 0 в неравенство:

0,02х0+0,04х0 24.

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

Специальный ингредиент: 0,01 р + 0,04 m 16.

Проведем прямую: 0,01 р + 0,04 m = 16.

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

Условие неотрицательности: р > 0 и m > 0.

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

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

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

Р = 0.10 р + 0,30 ш (ф. ст. в день) Если задать Р = 100 ф. ст. в день, целевую функцию можно проиллюстрировать графически. Если затем придать Р другое значение, то новая прямая будет параллельна прямой, соответствующей значению Р = 100 ф.

ст. в день (рис.1.7.).

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

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

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

3. Динамическое программирование Динамическое программирование применяется для решения задач, в которых процесс принятия решений может быть разбит на отдельные шаги этапы, т. е. имеет место динамический процесс принятия решений, а с точки зрения математики имеет место дискретизация, которая может быть естественной,например во времени, тогда t период дискретизации n целочисленные числа(0,1,2,…10) Существует искусственная дискретизация, например разбиение ресурса на части.

При решении задачи динамического программирования существует 2 этапа:

1) прямой ход определяется оптимальное значение критерия эффективности.

2) Обратный ход определяется оптимальная стратегия.

Рассмотрим задачу распределения однородного ресурса:

Компанией планируется распределение ограниченных ресурсов S0=250*106 руб.

между четырьмя предприятиями П1,П2,П3,П4. Известна прибыль каждого предприятия, которую они получают (исходные данные приведены в таблице).

Ресурс 1)Весь ресурс выделяется 1 му предприятию:

Выделенный F1(x) Ресурс 2)Ресурс распределяется между двумя предприятиями:

Ресурс 3) Ресурс распределяется между тремя предприятиями:

Ресурс 4) Ресурс распределяется между четырьмя предприятиями:

Ресурс Оптимальное значение прибыли для предприятия W=117*106 руб.

Ресурс Х*1=(50,100,50,50) Х*2=(50,50,100,50) Х*3=(50,50,50,100) 1) W1=27+40+20+30= 2) W2=27+25+35+30= 3) W3=27+25+20+45= 1. Применение метода динамического программирования предполагает, что прибыль для всех предприятий измеряется в одинаковых единицах.

3. Прибыль одного предприятия не зависит от прибыли других предприятий.

Прямой ход:

1) F1(x)=f1(x) 2) F2(x)= max (f2(x)+F1(x)) 3) F3(x)= 0 max s (f3(x)+F2(x)) 4) F4(x)= 0 max s (f4(x)+F3(x)) …………………………..

n)Fn(x)= max (fn(x)+Fn-1(x)) Обратный ход:

W=Fn(x) 4. Матричные игры Рассмотрим игру, в которой участвуют два игрока, причем каждый их них имеет конечное число стратегий. Обозначим для удобства одного из игроков через А, а другого через В.

Предположим, что игрок А имеет m стратегий:,, …, а игрок В – n стратегий:,, …, Пусть игрок А выбрал стратегию, а игрок В – стратегию Будем считать, что выбор игроками стратегий и однозначно определяет исход игры – выигрыш игрока А и выигрыш игрока В, причем эти выигрыши связаны равенством =.

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

Если нам известны значения выигрыша при каждой паре стратегий, i = 1,2,…,m, j = 1,2,…,n, то их удобно записывать или в виде матрицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В (рис. 2.1.), Рис. 2.1. Общий вид платжной матрицы матричной игры Полученная матрица имеет размер m n и называется матрицей игры или платежной матрицей.

Матричной игрой (при двух участниках) называется игра, в которой выигрыши первого игрока (проигрыши второго игрока) задаются матрицей.

Матричные игры относятся к разряду так называемых антагонистических игр, т. е. игр, в которых интересы игроков прямо противоположны.

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

Величина Vн называется максимином матрицы или нижней ценой игры.

Величина выигрыша игрока A равна, по определению матричной игры, величине проигрыша игрока B. Поэтому для игрока B необходимо определить Или найти максимальные значения по каждому из столбцов платжной матрицы, а затем определить минимальное из этих значений. Величина Vв называется минимаксом матрицы или верхней ценой игры.

В случае, если значения Vн и Vв не совпадают, при сохранении правил игры (коэффициентов ) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве Vн = Vв = V. В этом случае говорят, что игра имеет решение в чистых стратегиях, а стратегии, в которых достигается V - оптимальными чистыми стратегиями. Величина V называется чистой ценой игры.

Цена игры совпадает с элементом матрицы игры A, расположенным на пересечении -й строки (стратегия игрока A) и -го столбца (стратегия игрока B), - минимальным в своей строке и максимальным в своем столбце.

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

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

Седловых точек в матричной игре может быть несколько, но все они имеют одно и то же значение.

Матричные игры с седловой точкой важны и интересны, однако более типичным является случай, когда применение описанного алгоритма приводит к неравенству Vн < Vв.

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

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

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

Приведем простой пример смешивания стратегий.

Арбитр футбольного матча, чтобы определить первую атакующую команду, бросает монету, т.е. вместо того, чтобы принять определенное решение, выбирает пару чисел (1/2, 1/2), где первое число – есть вероятность того, что атакующей будет первая команда, второе - вероятность для второй команды.

Четыре студентки, проживающие в одной комнате, тянут четыре спички, одна из которых короче остальных. Та "неудачница", которой достанется короткая спичка, должна вымыть пол. Поступая так, студентки добавляют к своим четырем стратегиям: "моет пол Галя", "поет пол Вера", "моет пол Наташа", "моет пол Лена" еще одну, а именно, вектор х=(1/4, 1/4, 1/4, 1/4).

Дополнительная стратегия х состоит в смешивании четырех стратегий, каждой с вероятностью 1/4.

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

в которой у игрока A - m, а у игрока B - n чистых стратегий.

Смешанной стратегией игрока называется вероятностное распределение на множестве его чистых стратегий.

(i=1,...,m) - вероятность выбора i-й чистой стратегии. Так как вероятность, то 0 и, поскольку одна из m чистых стратегий обязательно будет выбрана, то представляет собой вероятность Аналогично, смешанная стратегия игрока B есть вероятностный вектор В этих условиях каждая обычная ситуация по определению является случайным событием и ввиду независимости X и Y реализуется с вероятностью. Поскольку в этой ситуации игрок A получает выигрыш, то математическое ожидание выигрыша в условиях ситуации в смешанных Это число принимается за средний выигрыш игрока A в ситуации в смешанных стратегиях.

оптимальными смешанными стратегиями игроков A и B соответственно, если Последнее равносильно тому, что Величина V=, определяемая последней формулой называется ценой игры.

Набор, состоящий из оптимальных смешанных стратегий игроков A и B и цены игры, называется решением матричной игры.

Не всякая матричная игра имеет решение в чистых стратегиях. Благодаря введению смешанных стратегий становится возможным следующее важнейшее в теории игр утверждение.

Теорема 1 (о минимаксе). Любая матричная игра имеет решение в смешанных стратегиях.

Теорема о минимаксе, или основная теорема для матричных игр, впервые была доказана Дж. фон Нейманом.

существуют и равны между собой:

Более того, существует хотя бы одна ситуация в смешанных стратегиях, для которой выполняется соотношение Методы решения матричных игр Сравнительно просто решаются игры, в которых хотя бы один игрок имеет всего две чистых стратегии: игры 2 2, 2 n, m n. Когда m, n>2 теория игр не имеет собственного точного метода. Такие игры сводятся к задачам линейного программирования и решаются методом симплекс-таблиц. Нужно заметить, что применение симплекс метода приводит к громоздким вычислениям уже для игры 3x3. Для игр больших размеров применяются приближенные методы.

Решение 2 2-игры В общем случае игра 2 2 определяется матрицей Прежде всего, необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причм оптимальными стратегиями игроков A и B соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет решения в чистых стратегиях, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями.

Пусть U = (, 1 ) оптимальная стратегия игрока A. Тогда Аналогично, если W = (, 1 – ) – оптимальная стратегия игрока B, то В некоторых случаях игры больших размеров можно упростить и привести к малым размерам. В основе такого преобразования лежит понятие доминирования стратегий.

Пусть дана m n - игра А. Говорят, что i-я стратегия игрока A доминирует его k-ю стратегия, если для всех j = 1,2,…,n. Говорят, что j-я стратегия игрока B доминирует его l-и стратегию, если для всех i = Из определения видно, что доминирующая стратегия дает игроку выигрыш не хуже, чем доминируемая. Отсюда следует, что игрок всегда может обойтись без доминируемых стратегий, в частности, если есть одинаковые стратегии, то он может применять только одну из них. Поэтому в матрице А доминируемые стратегии (строки или столбцы) могут быть отброшены, а это приводит к матрице малых размеров. В результате выполнения доминирования получается игра, эквивалентная первоначальной, в смысле следующего утверждения.

результате исключения доминируемых стратегий. Тогда для всех недоминируемых i, j: =0, для всех доминируемых i:

Пример 1. Рассмотрим игру Стрелками показаны доминируемые стратегии. Получили 2х2-игру, в которой все стратегии недоминируемы. Игра эквивалентна первоначальной игре А, т.е. оптимальные стратегии в игре А имеют вид x=(0, ), В результате вместо игры А мы можем решить более простую 2х2игру.

Теперь мы можем указать общий порядок решения матричной игры:

проверить, существует ли решение в чистых стратегиях; если есть, то игра решена;

если нет решения в чистых стратегиях, то выполнить доминирование;

найти решение в смешанных стратегиях.

5. Теория графов Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. Например, глядя на карту автомобильных дорог, можно интересоваться только тем имеется ли связь между некоторыми населнными пунктами, отвлекаясь от конфигурации и качества дорог, расстояний и других подробностей. При изучении электрических цепей на первый план может выступать характер соединений различных е компонентов -резисторов, конденсаторов, источников и т.п. Органические молекулы образуют структуры, характерными свойствами которых являются связи между атомами.

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

Определение. Множество, вершин V, связи между которыми определены множеством рбер Е, называют графом и обозначают G=(V,E).

Слово граф происходит от латинского слова "графио" - пишу. Типичными графами являются блок-схемы программ для ЭВМ, схемы авиалиний, схемымаршруты движений автобусов.

Первая работа по теории графа была опубликована 20-летием швейцарским математиком Леонардом Эйлером в 1736 г., когда он работал в Российской Академии наук. Она содержала решение задачи о кенигсбергских мостах (рис. 1) и имела следующее содержание: река Прегель делит г. Кенигсберг на части: А, В, С, D, связанные между собой 7 мостами. Требуется определить можно ли выйдя из какой-либо части города пройти по всем мостам по 1 разу и вернуться в исходную часть города. Согласно условию задачи не имеет значения, как проходит путь по части суши А, В, С, D на которых расположен г. Кенигсберг (ныне Калининград), поэтому их можно представить вершинами.

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

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

На рис. 3 а) изображен граф, в котором существуют пары вершин, соединенные более чем одним ребром. Различные ребра, соединяющие две данные вершины, называются кратными. Граф, изображенный на рис. 3 6), содержит ребра, соединяющие вершину саму с собой. Такие ребра называют петлями.

Более точно, графом называют тройку (V, Е, ), где V, Е - конечные множества, V и - отображение из Е в V (2) U V. Если (е) = {u, v}, где и v, то говорят, что ребро е соединяет вершины и, v. В этом случае будем писать е = uv. Если (е) = w, то ребро е называют петлей в вершине n. В этом случае будем также писать е = ии и говорить, что е соединяет вершину w саму с собой.

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

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

Отметим, что обыкновенный граф - это граф без петель и кратных ребер.

Граф G, имеющий п вершин, часто называют п - графом; если, кроме того, G содержит т ребер, то G - (п, т) - граф.

Если е = uv - некоторое ребро данного графа, то вершины и, v называются смежными; говорят также, что и, v - концевые вершины ребра е.

Ребро е и вершина v инцидентны, если v - концевая вершина для е. Ребра е и называются смежными, если они имеют общую концевую вершину.

Пусть G1 = (V1, E1), G2 = (V2, Е2) - два графа. Биективное отображение:

:V1 V2 называется изоморфизмом G1 на G2, если для любых и, v €V число ребер, соединяющих вершины (и) ( v) в G1, равно числу ребер, соединяющих (u) и (v) в G2 (разумеется, при u = v число петель в вершине и равно числу петель в вершине {и)).

Отметим, что в случае обыкновенных графов изоморфизм - это биек-ция, сохраняющая отношение смежности; иными словами, изоморфизм характеризуется свойством: произвольные вершины и, v смежны в графе G тогда и только тогда, когда вершины (u), (v) смежны в графе G2.

Графы G1 и G2 изоморфны (G1= G2), если существует изоморфизм на G2. На рис. 4 приведены диаграммы двух изоморфных графов. Действительно, отображение, определенное правилом (ui) = Vi, (1 i 6), очевидно, является изоморфизмом.

Отношение «быть изоморфными» на множестве всех графов, очевидно, является отношением эквивалентности. Таким образом, множество всех графов разбивается на классы попарно изоморфных графов. Заметим, что диаграмма задает граф с точностью до изоморфизма. Степенью вершины v называется число ребер, инцидентных этой вершине, причем каждая петля учитывается дважды. Степень вершины v обозначается через degGv или просто через degv. Ясно, что в обыкновенном графе степень вершины v равна количеству вершин, смежных с v. Окружением N(v) вершины v называется множество всех вершин, смежных с v.

Если degv=0, то вершина v называется изолированной, а если degv=l, то - висячей. Ребро е, инцидентное висячей вершине, также называют висячим.

Лемма 1 (о рукопожатиях). Пусть G - произвольный граф. Тогда Доказательство. При подсчете суммы степеней произвольное ребро е = uw внесет свой вклад, равный единице, как в deg u, так и в deg w, причем петля будет учитываться дважды.

Следствие. Произвольный граф содержит четное число вершин нечетной степени.

Доказательство. Пусть V 0 и V 1 - соответственно множества вершин четной и нечетной степени.Тогда Ясно, что первое слагаемое четно. Поэтому второе слагаемое также четно. Так как во второй сумме все слагаемые нечетны, их число четно.

Следовательно, множество V 1 содержит четное число вершин.

Будем называть граф одноэлементным, если он имеет единственную вершину. Граф G называется нулевым или вполне несвязным, если множество его ребер EG пусто. Нулевой n-граф будем обозначать через Оп.

Диаграмма графа О4. Ясно, что нулевой граф является обыкновенным графом.

Обыкновенный граф G называется полным графом, если любые его две различные вершины смежны. Для полного n-графа применяется обозначение Кп.. Очевидно, степень каждой вершины в графе Кп равна п - 1. Поэтому из леммы о рукопожатиях следует, что число ребер в Кп равно Граф G называют двудольным, если множество VG можно разбить на два непустых подмножества X и Y так, что любое ребро графа соединяет вершину из X с вершиной из Y. Множества X и Y - это доли двудольного графа G. Если любые вершины х € X и у € Y смежны и двудольный граф является обыкновенным графом, то G называют полным двудольным графом. Если |Х| = р,|Y| = q, то такой полный двудольный граф обозначают через Kp,q.

Граф Н называется подграфом графа G, если VH С VG и ЕН С EG. В число подграфов графа G будем включать и пустой подграф. Если VH - VG, то подграф Н называется стовным подграфом. Редукция графа G - это такой его остовный подграф Н, что Н является обыкновенным графом с наибольшим возможным числом ребер.

Пусть U -подмножество из VG. Обозначим через D множество всех ребер е = uv € EG таких, что и, v € U. Граф G(U) = (U, D) называется подграфом, порожденным множеством вершин U.

Аналогично определяется подграф, порожденный заданным множеством ребер. Пусть D С EG. Обозначим через U множество всех вершин, являющихся концевыми для ребер из D. Тогда граф G(D) = (U, D) называют подграфом, порожденным множеством ребер D.

Пусть G - произвольный граф и H - его подграф. С каждой вершиной v и каждым ребром е можно связать подграфы Н - v, H - е и H + е.

Подграф Н - v получается из подграфа Н удалением вершины v и всех инцидентных этой вершине ребер. Отметим, что если v не лежит в подграфе Н, то Н - v = Н'.

Подграф Н - е получается из Н удалением ребра е. Здесь также Н - е = Н, если е не лежит в Н.

Подграф Н + е получается из Н добавлением ребра е и двух его концевых вершин. Если е лежит в H, то Н + е = Н.

Через Sub(G) будем обозначать множество всех подграфов графа G.

Определим отношение на Sub(G), полагая Н1 Н2 для подграфов H1 и Н графа G тогда и только тогда, когда H1 является подграфом в Н2, т.е. когда VH1 С VH2 и EH1 С ЕН2. Очевидно, отношение есть частичный порядок на Sub(G). Будем говорить, что H1 содержится в Н2, если H1Н2.

Пусть H1 и Н2 — произвольные подграфы графа G.

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

Первый маршрут проходит через последовательность вершин (V1, V2, V3, V2, V3, V5) и соединяет вершины V1 и V5; второй-через последовательность вершин (V3, V5, V5, V2, V5) и соединяет вершины V3, V5.

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

Маршрут, все ребра которого различны, называется цепью.

Пример. В выше приведенном примере (№1) маршрут (l2, l5, l6)- цепь.

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

Пример В выше приведенном примере (№1) маршрут (11, l2, l5)- простая цепь.

Замкнутая цепь называется циклом.

Пример В выше приведенном примере (№1) маршрут (12, l3, l4, l5)-цикл.

Простая цепь называется простым циклом.

Заметим, что цикл полностью определяется множеством своих ребер, поэтому часто под циклом мы будем понимать соответствующее ему множество ребер. Петля дает цикл длины 1, пара кратных ребер образует цикл длины 2. Циклы длины 3 называют обычно треугольниками.

Пример В выше приведенном примере (№1) маршрут (12, 14, l5)-простой цикл.

Цикл, который содержит все ребра графа, называется эйлервеым циклам.

Граф, в котором имеется эйлеров цикл, называется элеровым графам.

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

Две вершины графа называются связанными, если существует маршрут соединяющий эти вершины.

Граф, пара вершин которого связана, называется связанным графом.

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

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

Критерия гамильтонового цикла нет.

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

Маршрут, не содержащий повторяющихся дуг, называется путем.

Маршрут, не содержащий повторяющихся вершин называется простым путем, Замкнутый путь называется контуром Простой замкнутый путь называется простым контуром.

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

Понятие цепи и цикла применимы и к ориентированным графам. При этом направления дуг не учитываются, т.е. по существу вместо орграфа рассматривают неориентированный соотнесенный ему граф.

Теорема 1.1.. Каждый граф является дизъюнктным объединением своих компонент связности.

В дальнейшем граф, имеющий п вершин, т ребер и к компонент связности, будем называть (n, m, к)-графом.

Разрезающим множеством ребер графа называется множество ребер, удаление которого из графа приводит к увеличению числа компонент связности. Минимальное по включению разрезающее множество ребер графа называется его разрезом. Мост графа - это ребро, составляющее одноэлементный разрез. Иными словами, при удалении моста число компонент связности возрастает. На рис. 6, 7показаны примеры разрезов в графах, причем на рис. 6 б) показан мост.

Замечание: при наличие моста в графе имеется, по крайней мере, две точки сочленения.

Граф называется неразделимым, если он связный и не имеет точек сочленения, называется сепарабельным.

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

Блоки В1, В2, В3 графа из П Каждое ребро графа, как и каждая вершина (за исключением точек сочленения), принадлежит только одному из его блоков. Более того, только одному блоку принадлежит и каждый простой цикл.

Лемма 2. При удалении из графа моста число компонент связности увеличивается точно на единицу.

Доказательство. Пусть из графа удаляется мост е = uv. В графе G - е вершины и и v нельзя соединить простой цепью, иначе сохранится отношение связности и, следовательно, сохранится число компонент связности. Таким образом, вершины и и v лежат в разных компонентах связности графа G - е.

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

Лемма 3. При удалении из графа ребер его разреза число компонент связности увеличивается точно на единицу.

Доказательство. Пусть из графа G удаляется разрез {ei, е2,..., et}. Можно считать, что t > 1. После удаления множества ребер {ei, е2,..., et_i} число компонент связности сохраняется и ребро et становится мостом.

Дальнейшее удаление ребра et в силу леммы 2 приводит к увеличению числа компонент связности ровно на единицу.

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

Лемма 4. Ребро графа является мостом тогда и только тогда, когда оно не содержится ни в одном цикле.

Доказательство. Пусть е = uv -мост. Если е содержится в некотором цикле, то существует простая (и, v)-цепь, не содержащая е. Следовательно, после удаления ребра е из графа отношение связности не изменится, что невозможно.

Обратно, пусть е = uv не является мостом. После удаления е из графа G вершины и и v будут лежать в одной компоненте связности графа G - е. В силу леммы 1 в графе G - е имеется простая (и, v;)-цепь. Добавляя к этой цепи ребро е, получим цикл графа G: содержащий ребро е.

Из леммы 4 вытекает, что ациклические ребра - это в точности мосты.

Лемма 5. Пусть множество вершин связного граф G разбито на два непустых непересекающихся подмножества U и W. Тогда существует такое ребро е = uw, что и € U и w € W.

Доказательство. Возьмем две вершины х € U и у € W. В силу связности графа G существует простая (x, у)-цепь:

Пусть vi - последняя вершина цепи, лежащая в U. Тогда vi у и Vi+1 €W. Следовательно, ребро ei+1 =ui ui+1 является искомым.

Теорема 1.2. Пусть G - обыкновенный (n, m, к)-граф. Тогда выполнено двойное неравенство Доказательство. Проверим сначала верхнюю оценку. Обозначим через G обыкновенный граф, имеющий п вершин, к компонент связности и наибольшее возможное число ребер т. Покажем, что Легко понять, что каждая компонента связности графа G является полным графом. Поэтому Можно считать, что n1 п2... nk.

Убедимся, что п2 = 1. Предположим, что п2 > 1. Пусть и -некоторая вершина графа Кn2. Удалим п2 - 1 ребер, инцидентных вершине u, а затем добавим n1 ребер, соединяющих вершину и с каждой вершиной графа Кn1, т.е.

перенесем вершину и из второй компоненты связности в первую. Поскольку п1> п2 - 1, получим граф, имеющий п вершин, к компонент связности и больше чем m ребер. Это противоречит выбору графа G- Следовательно, п2 = 1. Тогда п2 =... = nk = 1, т. е. все ребра графа G содержатся в полном графе Кn1 и n1 = п — k + 1. Поэтому Обратимся теперь к нижней оценке. Для ее проверки применим индукцию по числу ребер. Если m = 0, то п = к: и требуемое неравенство очевидно. Пусть m > 0. Предположим, что для всех графов с числом ребер, меньшим чем m, оценка имеет место. Рассмотрим (п, m, k)-граф G. Пусть G1 - G - е, где е - некоторое ребро графа G. Тогда G1 является (n, m - 1, k1)графом, где к1 к + 1 в силу леммы 2. Следовательно, Следствие 1. Пусть G - обыкновенный (n, т)-граф. Если Доказательство. Пусть к - число компонент связности графа G. Если что невозможно. Следовательно, к = 1, т.е. граф G связен.

Следствие 2. Если G- произвольный (n,m1,k)- граф G1 является редукцией графа G. Тогда m m1 n-k.

Доказательство. Пусть обыкновенный (n, m1, k)-граф G1 является редукцией графа G. Тогда m > m1 > n – к.

Ориентированные графы Пусть V, D - произвольные множества, причем V. Обозначим через V декартов квадрат множества V.

Ориентированным графом или, короче, орграфом G называется тройка (V, D,): где - некоторое отображение множества D в множество V2.

Элементы множеств V и D называются соответственно вершинами и дугами орграфа G. Множества вершин и дуг орграфа G удобно обозначать через VG и DG соответственно. Если f - дуга, то (f) является упорядоченной парой (и, v), где и: v V. Дуга f выходит из вершины и и заходит в вершину v; в свою очередь и и v называются концевыми вершинами дуги f; в дальнейшем будем писать f = (а иногда даже - f = uv, если нет опасности возникновения путаницы).

При записи произвольного орграфа он, как правило, будет представляться в виде G = (V, D).

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

С каждым орграфом G = (V, D) естественно связать граф Go = (V, Е), называемый основанием данного орграфа. Для получения основания необходимо в орграфе G заменить каждую дугу f = ребром е = uv На рис. 8 изображены орграф и его основание Орграф G называется связным, если связным является его основание.

Ориентированым маршрутом или, короче, ормаршрутом в орграфе G называется чередующаяся последовательность вершин и дуг Такой ормаршрут принято называть (V О, vt)-ормаршрутом; вершины V O и vt называются соответственно начальной и конечной вершинами такого ормаршрута. Если V O = vt, то ормаршрут называют замкнутым. Количество дуг, составляющих ормаршрут, - это длина ормаршрута.

Ормаршрут, не содержащий повторяющихся дуг, называют орцепью.

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

Нетрудно проверить, что существование (и,v;)-ормаршрута гарантирует существование простой (и, v)-орцепи.

Говорят, что вершина v достижима из вершины и, если существует (и, v)ормаршрут. Орграф G сильно связен или орсвязен, если любая его вершина достижима из любой другой вершины. Очевидно, сильно связный орграф является связным; обратное утверждение, разумеется, не верно.

Граф G называется ориентируемым, если он является основанием некоторого сильно связного орграфа.

Теорема 1.3. Связный граф G ориентируем тогда и только тогда, когда каждое его ребро не является мостом.

Доказательство. Пусть граф G является основанием орграфа Н и G содержит мост е. Тогда в Н имеется дуга f =, где и, v - концы ребра е.

Очевидно, в Н нет (u, v)-ормаршрутов. Следовательно, граф G не является ориентируемым.

Обратно, пусть граф G не имеет мостов, т. е. каждое ребро графа G содержится в некотором цикле. Поскольку любой цикл является ориентируемым графом, в графе G существует максимальный ориентируемый подграф Н. Убедимся, что Н = G. Допустим, что это равенство не выполнено. В силу связности графа G существует ребро е, инцидентное вершине v из Н и не лежащее в Н. По предположению ребро е лежит в некотором цикле С.

Обозначим через Q множество ребер цикла, не принадлежащих подграфу Н.

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

Пусть G - произвольный орграф. Полустепенью исхода degv вершины v называется число всех дуг, имеющих v в качестве начала. Аналогично, полустепень захода degv - это число всех дуг, для которых вершина v является концом. Орграф, содержащий п вершин и т дуг будем называть (n, т)орграфом.

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

Лемма 1. Пусть G - произвольный (n, т)-орграф. Тогда Это утверждение аналогично лемме 1 из разд. 1.1; его часто называют орлеммой о рукопожатиях.

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

Ремонтные мастерские;

Торговые, транспортные, энергетические системы;

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

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

Требования поступают нерегулярно, в случайные моменты времени.

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

Системы массового обслуживания обладают различной структурой, но обычно в них можно выделить четыре основных элемента:

Входящий поток требований.

Приборы (каналы обслуживания).

Общая схема систем массового обслуживания.

(стрелками показаны моменты поступления требований в систему, прямоугольниками – время обслуживания) На рис.3а представлена модель работы системы с регулярным потоком требований. Поскольку известен промежуток между поступлениями требований, то время обслуживания выбрано так, чтобы полностью загрузить систему. Для системы со стохастическим потоком требований ситуация совершенно иная – требования приходят в различные моменты времени и время обслуживания тоже является случайной величиной, которое может быть описано неким законом распределения (рис.3б).

В зависимости от правил образования очереди различают следующие СМО:

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

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

Рассмотрим характеристики входящего потока требований.

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

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

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

Определение 4. Поток требований называется пуассоновским (или простейшим), если он обладает тремя свойствами: стационарен, ординарен и не имеет последствий. Название связано с тем, что при выполнении указанных условий число событий, попадающих на любой фиксированный интервал времени, будет распределен по закону Пуассона.

Определение 5. Интенсивностью потока заявок называется среднее число заявок, поступающих из потока за единицу времени.

Для стационарного потока интенсивность постоянна. Если – среднее значение интервала времени между двумя соседними заявками, то.В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:

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

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

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

МАРКОВСКИЙ СЛУЧАЙНЫЙ ПРОЦЕСС

Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3,... можно заранее перенумеровать, и переход системы из состояния в состояние происходит практически мгновенно.

Такие процессы бывают двух типов: с дискретным или непрерывным временем.

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

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

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