Методы оптимальных решений

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РФ БАРНАУЛЬСКИЙ ФИЛИАЛ Ильина М.А., Копылов Ю.Н., Копылова Н.Т. Методы оптимальных решений конспект лекций Учебно-методическое пособие Барнаул – 2012 ББК 65.23я73 М.А.Ильина, Ю.Н.Копылов, Н.Т.Копылова. Методы оптимальных решений. Конспект лекций. Учебно-методическое пособие.- Барнаул: Изд-во АлтГТУ, 2012.- 139 с. Учебное пособие подготовлено для студентов II курса, обучающихся по направлению «Экономика». В пособии представлен конспект лекций по дисциплине «Методы оптимальных решений», разобраны типовые задачи. Пособие может быть использовано при подготовке к собеседованиям по контрольной работе и экзамену по дисциплине. Рецензент: Половникова Е.С., к.ф.-м.н., доцент Алтайской академии экономики и права. Печатается по решению кафедры математики и информатики (протокол № 4 от 11.12.12) Тема 1. Введение в дисциплину. Общее представление о задаче оптимизации (0,5/-/4) 1.1. Математические модели в экономике Современная экономика и управление - это мир моделей. Соответственно, основным методом исследования управленческих и экономических процессов в настоящее время является метод моделирования, т.е. способ теоретического и практического действия, направленного на разработку и использование моделей. Метод моделирования обеспечивает принятие решений в условиях определённости, риска и неопределённости. Он основывается на принципе аналогии, т.е. возможности изучения реального объекта не непосредственно, а через рассмотрение подобного ему и более доступного объекта, его модели. Под моделью вообще понимают некоторый объект, способный заменить исследуемый с целью получения нового знания, т.е. модель – это некоторый образ исследуемого явления, процесса, объекта. Математические модели в экономике и управлении чаще всего строятся для следующих целей: • определение по модели оптимальных значений параметров процесса; • имитация процесса при различных значениях параметров для получения представления об изменениях тех или иных характеристиках в связи с изменением параметров; • финансово-экономический анализ деятельности и прогнозирование значений тех или иных параметров процесса. Математические модели в экономике, или ЭММ – это математический образ, математическое представление существа исследуемого экономического процесса. В наиболее общем виде подразделяют следующим образом: • макро- и микроэкономические; • прескриптивные и дескриптивные; • статистические и динамические; • детерминированные и стохастические. Современные ЭММ представляют собой, как правило, комплексы, где сочетаются различные виды моделей. Экономико-математические методы – это методы разработки, исследования и принятия решений по экономико-математическим моделям. В составе методов можно выделить следующие группы методов (научных дисциплин): • математико-статистические методы (выборочный метод, методы дисперсионного анализа, корреляционно-регрессионного анализа, факторного анализа и др.); • методы эконометрики (методы разработки моделей парной и множественной регрессии, системы одновременных уравнений и др.); • методы исследования операций (оптимальное программирование, теория массового обслуживания, теория игр и др.); • методы финансовой математики(процентные вычисления и потоки платежей, анализ инвестиционных проектов и лизинговых операций, портфельные инвестиции и др.); • методы экспериментального изучения экономических явлений (имитационное моделирование, деловые игры, методы экспертных оценок). 1.2. Основные этапы решения экономических задач с применением математических методов В процессе решения экономических задач с применением математических методов можно выделить (условно) четыре основных этапа. 1. Постановка экономической проблемы, задачи (описание экономико-организационной сути). 2. Моделирование (разработка ЭММ проблемы, задачи и оценка адекватности этой модели). 3. Получение решения по модели (реализация ЭММ). 4. Внедрение полученного решения (разработка рекомендаций, предложений в доступном и наглядном для практики виде). Основные принципы разработки ЭММ: • адекватность модели – означает требование максимального приближения теоретической модели к устойчивым, существенным характеристикам и закономерностям исследуемого (реального) процесса; • системность – предполагает интерпретацию производственного объекта как большой системы и, соответственно, применение системного подхода (взаимосвязанное рассмотрение всех элементов системы) к его исследованию. Системный подход означает, что экономический объект рассматривается, с одной стороны, как единое целое, а с другой – как совокупность относительно самостоятельных элементов. Практическая реализация этого принципа предполагает построение моделей, которые соответствовали бы содержанию каждой отдельной части системы и одновременно позволяли бы создать целостную картину возможного развития объекта (системы) в будущем. В простейшем случае на практике системный подход при моделировании сводится к тому, что каждую подсистему (элемент), работа которой исследуется, полезно рассмотреть как часть другой, более обширной системы и выяснить, как влияет работа данной подсистемы (элемента) на работу последней. 1.3.Принцип оптимальности в планировании и управлении Оптимизационные (экстремальные) модели в экономике возникают при практической реализации принципа оптимальности в управлении и планировании. Необходимым условием использования принципа оптимальности (оптимального подхода к планированию и управлению) являются гибкость, альтернативность производственно-хозяйственных ситуаций, в условиях которых приходится принимать те или иные управленческие решения. Именно такими, как правило, и являются ситуации, составляющие повседневную практику хозяйствующего субъекта (выбор производственной программы, прикрепление к поставщикам, маршрутизация, раскрой материалов, приготовление смесей, загрузка контейнеров и т.д.). Суть принципа оптимальности состоит в стремлении выбрать такое управленческое решение X = (x1, x2, … , xn), где xj, j = 1, … , n - его компоненты, которое наилучшим образом учитывало бы внутренние возможности и внешние условия производственной деятельности предприятия. “Наилучшим образом” здесь означает выбор некоторого критерия оптимальности, то есть некоторого экономического показателя, позволяющего сравнивать эффективность тех или иных управленческих решений. Традиционные критерии оптимальности в экстремальных моделях – “максимум прибыли”, “минимум затрат”, “максимум объёма работ (услуг)” и др. “Учитывало бы внутренние и внешние условия производственной деятельности” означает, что на выбор управленческого решения накладывается ряд условий, то есть выбор X осуществляется из некоторой области возможных (допустимых) решений D. Задачу условной оптимизации обычно записывают в виде: найти максимум или минимум функции f(X) = f(x1, x2, … , xn) (1.1) при ограничениях (1.2) xj ≥ 0, j = 1, 2, … n (1.3) f(X) - запись критерия оптимальности – целевая функция (ЦФ). Условие (1.3) –теоретически не всегда имеет место, однако чаще всего оно выполняется, поскольку экономические показателя, как правило, могут принимать только положительные значения. Обозначение {≤, =, ≥} говорит о том, что в конкретном ограничении возможен один из этих трёх знаков. Условия (1.2) принято называть функциональными ограничениями, поскольку левая часть ограничения является функцией от вектора переменных X, а (1.3) прямые ограничения называют условиями неотрицательности переменных. Вектор X называется допустимым решением или планом задачи оптимального (математического) программирования, если он удовлетворяет системе ограничений (1.2) – (1.3), или, другими словами, ограничения (1.2)-(1.3) задают область допустимых решений D. А тот план X (допустимое решение), который доставляет максимум или минимум целевой функции f(x1, x2, … , xn) называется оптимальным планом (оптимальным поведением или просто решением) задачи оптимального (математического) программирования. Существует два варианта, когда невозможно получить решение по оптимизационной модели: 1) область допустимых решений может оказаться пустым множеством (задача противоречива) 2) целевая функция является неограниченной на области допустимых решений. Первый случай связан с некорректностями в постановке экономической задачи и (или) разработанной математической модели. Например, имеющимся объёмом ресурсов заведомо невозможно выполнить даже те минимальные объёмы работ, которые закладываются в ограничения как минимально необходимые задания. Если в данной ситуации всё же возможно найти решение задачи, то следует построить непустое множество допустимых решений, исключив одно или несколько ограничений, то есть фактически соблюсти принцип альтернативности. Второй случай обычно означает, что математическая модель разработана некорректно и некоторые существенные ограничения в ней отсутствуют. Задачи оптимального программирования в наиболее общем виде классифицируют по следующим признакам. 1. По характеру взаимосвязи между переменными – a) линейные, б) нелинейные. В случае а) все функциональные связи в системе ограничений и функция цели – линейные функции; наличие нелинейности хотя бы в одном из упомянутых элементов приводит к случаю б). 2. По характеру изменения переменных - а) непрерывные, б) дискретные. В случае а) значения каждой из управляющих переменных могут заполнять сплошь некоторую область действительных чисел; в случае б) все или хотя бы одна переменная могут принимать только целочисленные решения. 3. По учёту фактора времени – а) статические, б) динамические. В задачах a) моделирование и принятие решений осуществляется в предположении о независимости от времени элементов модели в течение периода времени, на который принимается планово-управленческое решение. В случае б) такое предположение принято не может быть и необходимо учитывать фактор времени. 4. По наличию информации о переменных – а) задачи в условиях полной определённости (детерминированные), б) задачи в условиях неполной информации, в) задачи в условиях неопределённости. В задачах б) отдельные элементы являются вероятными величинами, однако известны или дополнительными статистическими исследованиями могут быть установлены их законы распределения. В случае в) можно сделать предположение о возможных исходах случайных элементов, но нет возможности сделать вывод о вероятностях исходов. 5. По числу критериев оценки альтернатив – а) простые, однокритериальные задачи, б) сложные, многокритериальные задачи. В задачах а) экономически приемлемо использование одного критерия оптимальности или удаётся специальными процедурами (например, “взвешиванием приоритетов”) свести многокритериальный поиск к однокритериальному (например, “взвешиванием параметров”). Сочетания признаков 1-5 позволяет группировать (классифицировать) в самом общем виде задачи и методы оптимального программирования, например: 1а)2а)3а)4а)5а) – задачи и методы линейного программирования, 1б)2а)3а)4а)5а) – задачи и методы нелинейного программирования, 1а)2б)3а)4а)5а) – задачи и методы целочисленного (дискретного) линейного программирования и т.д. Если в признаках 2-5 выполняется условие а), то их перечисление опускается при описании типа задачи. Выбору того или иного метода нахождения решения конкретной задачи оптимального программирования предшествует её классификация, то есть отнесение к одному из классов оптимизационных задач, начиная с приведённых самых общих признаков. Развитие и совершенствование методов решения задач оптимального программирования идёт от случаев типа а) к случаям типа б), в). Тема 2. Линейное программирование (1/4/35) 2.1. Задачи линейного программирования, различные формы записи Общей задачей линейного программирования (ЗЛП) называется задача отыскания оптимального решения X = (x1, x2, … , xn) такого, что , (2.1) при ограничениях (2.2) (2.3) Рассмотренная модель ЗЛП является линейной, так как основу её составляют выражения линейного типа. Термин «программирования» означает поиск оптимального программы (решения). ЗЛП - наиболее изученные задачи, для которых разработан универсальный метод решения – метод последовательного улучшения плана (симплекс-метод), то есть любая ЗЛП решается (реализуется этим методом). Замечание При решении ЗЛП возможны особые случаи: • область допустимых решений является пустым множеством (ограничения противоречивы); • целевая функция является неограниченной на области допустимых решений (математическая модель разработана некорректно и некоторые существенные ограничения в ней отсутствуют); • задача имеет множество решений, равноценных между собой, но оптимальных по сравнению с другими допустимыми решениями. Рассмотрим математические модели некоторых важных экономических задач. Задача об использовании ресурсов (задача планирования производства). Для производства 2-х видов продукции Р1 и Р2 используют 4 вида ресурсов r1, r2, r3 и r4. Запасы ресурсов и их расход для изготовления единицы продукции каждого вида приведены в таблице: Вид ресурса Количество ед. ресурса для изготовления ед. продукции Запас ресурса Р1 Р2 r1 1 3 18 r2 2 1 16 r3 - 1 5 r4 3 - 21 Прибыль, получаемая от реализации единицы продукции Р1 и Р2, равна соответственно 2 и 3 ден. ед. Требуется составить математическую модель задачи с целью найти такой план производства продукции, при котором прибыль от ее реализации будет наибольшей. Решение. Для построения математической модели: 1. Введем управляющие переменные. Обозначим x1 – количество единиц продукции Р1, x2 – количество единиц продукции Р2. По смыслу задачи переменные неотрицательны: x1 ≥0, x2 ≥0, 2. Построим функцию цели. Прибыль от реализации продукции Р1 составит 2x1 ден. ед., прибыль от реализации продукции Р2 составит 3x2 ден. ед. Функция цели - суммарная прибыль - должна быть максимальной и описывается выражением: F=2x1 +3x2 → max 3. Построим систему функциональных ограничений. Расход каждого ресурса для изготовления продукции Р1 и Р2 в количестве x1 и x2 соответственно описывается выражением: ресурса r1 - 1x1 +3x2 ресурса r2 - 2x1 +1x2 ресурса r3 - 0x1 +1x2 ресурса r4 - 3x1 +0x2 Потребление ресурсов не должно превышать их запасов, поэтому связь между потреблением и запасами ресурсов выразится системой неравенств: Таким образом, математическая модель задачи построена: Найти такой план выпуска продукции , при котором прибыль максимальна и выполнены ограничения Задача о составлении рациона (о диете, о смесях) Имеется два вида корма К1 и К2. Данные о содержании витаминов в 1кг каждого вида корма, необходимый минимум этих витаминов и стоимость 1кг каждого вида корма приведены в таблице: Витамины Количество витаминов (ед.) в 1кг корма Необходимый минимум К1 К2 А 3 2 8 В 2 1 12 С 1 4 16 Стоимость 1кг корма 3 5 Требуется составить экономико-математическую модель задачи с целью найти дневной рацион, имеющий минимальную стоимость и содержащий не менее установленного предела каждого вида питательных веществ. Решение. 1. Введем управляющие переменные: Обозначим - количество кормов К1 и К2, входящих в дневной рацион. По смыслу переменные неотрицательны: 2. Функция цели - общая стоимость дневного рациона питания – описывается выражением и должна быть минимальной: 3. Построим систему ограничений. Рацион будет включать следующие количества витаминов: единиц витамина А, единиц витамина В, единиц витамина С. Учитывая установленные пределы содержания питательных веществ, получим систему неравенств: Таким образом, математическая модель задачи получена: Составить дневной рацион ,стоимость которого минимальна и выполнены заданные ограничения 2.2. Графическое решение задачи линейного программирования Рассмотрим случай n=2, то есть задачу на плоскости: найти , (2.4) при ограничениях (2.5) (2.6) Каждое ограничение в этом случае задаёт полуплоскость (при наличии знака неравенства), либо прямую (при наличии в ограничении знака равенства). Пересечение этих полуплоскостей и прямых может дать пустое множество, точку, луч, многоугольник, неограниченную многоугольную область. Непустая область пересечения называется многоугольником решений или областью допустимых решений ОДР. Если целевая функция ЗЛП ограничена на многограннике решений, то существует такая угловая точка многогранника решений, в которой ЦФ достигает своего оптимума. Графический способ решения состоит из следующих этапов: 1. Строится многоугольная область допустимых решений ЗЛП – ОДР. 2. Строится вектор-градиент целевой функции c1, c2, где с1, с2 – коэффициенты ЦФ. 3. Строится целевая функция – линия уровня. 4. Выбирается оптимальное решение При нахождении максимума целевой функции F(x1 , x2 ) линию уровня La надо передвигать параллельно самой себе в направлении вектора-градиента до тех пор, пока она не покинет пределов области допустимых решений D. Предельная точка области при таком движении и является точкой максимума целевой функции. При нахождении минимума целевой функции линию уровня La надо передвигать в направлении противоположном вектору градиенту до достижения предельной точки многоугольника. Рассмотрим пример графического решения ЗЛП по заданной математической модели Найти при ограничениях Решение. 1. Построим область допустимых решений Ограничения x1 ≥0, x2 ≥0, задают первую координатную четверть плоскости x1 O x2. Определим полуплоскость, соответствующую каждому неравенству. Неравенство определяет полуплоскость, ограниченную прямой Она проходит через точки (0; 5) и (10; 0). В качестве контрольной точки возьмем О (0;0), т.е. x1 = 0, x2 = 0 и подставим ее координаты в правую часть неравенства: 0 ≤ 10 - истина, значит искомая полуплоскость находится с той же стороны, что и точка. Аналогично построим другие полуплоскости Возьмем КТ О(0;0): - ложь, значит, искомая полуплоскость лежит с противоположной стороны от прямой. =11. Возьмем КТ О(0;0): - истина, значит, искомая полуплоскость находится с той же стороны, что и КТ. Возьмем КТ О(0;0): - истина, значит, искомая полуплоскость находится с той же стороны, что и КТ. Пересечение всех найденных полуплоскостей определяет область допустимых решений D задачи. 2. Построим линию уровня Линия уровня определяется уравнением La: F(x1, x2=a. Возьмем a = 7 , чтобы линия уровня La: 3x1+1x2 =7 пересекала ОДР. Она проходит через точки с координатами (1;4) и (0;7). 3. Построим вектор градиент Координаты вектора определяются коэффициентами целевой функции F=3x1+1x2 Начало вектора находится в точке (0;0), а точка с координатами (3;1) является концом вектора. 4. Найдем оптимальное решение При нахождении максимума целевой функции линия уровня La передвигается параллельно самой себе в направлении вектора до тех пор, пока не покинет пределов области допустимых решений D. Точка М является точкой максимума целевой функции. Найдём координаты точки М: Значение целевой функции в точке М(5,5;0) . Ответ: максимальное значение функции равно и достигается при и . Симплексный метод решения ЗЛП Симплексный метод – это аналитический метод решения ЗЛП, реализующий алгоритм графического метода аналитичесски, без построения чертежа. Таким образом, суть симплексного метода состоит в направленном переборе допустимых решений, при котором значение целевой функции на каждом шаге лучше, чем на предыдущем. Процесс повторяется до тех пор, пока не будет получено оптимальное по значению целевой функции решение. Симплекс метод может использоваться для решения ЗЛП с любым количеством неизвестных. Техническая реализация симплексного метода связана с решением систем линейных уравнений, для чего используют метод Гаусса, разработаны табличные формы и правила преобразования симплексных таблиц. 2.3. Двойственность в линейном программировании Рассмотрим задачу планирования производства: сырье Продукция П1 П2 … Запас сырья 1-е 2-е … а11 а12 … а21 а22 … … … … b1 b2 … Прибыль от реализации С1 С2 … Имея целью получение максимальной прибыли, запишем задачу линейного программирования: Решение этой задачи определяет оптимальный с точки зрения полученной прибыли план выпуска продукции. С каждой задачей линейного программирования по определённым правилам связана другая ЗЛП, называемая двойственной к исходной задаче. Смысл двойственной задачи: предприятие может продать сырье, установив на него цены y1, y2,…, ym. Эти цены должны быть установлены с учетом требований, отражающих несовпадающие интересы продающего предприятия и покупающей организации: • покупающая организация стремится минимизировать общую стоимость покупки; • предприятие согласно продать сырье только по таким ценам, при которых полученная выручка будет не меньше, чем доход при организации производства. Такие требования позволяют сформулировать новую задачу линейного программирования: Полученная задача называется двойственной по отношению к исходной. Переменные y1, y2,… называются двойственными оценками (теневыми ценами, оценками ресурсов). Правила составления двойственных задач 1. Если прямая задача – на максимум, то двойственная к ней – на минимум. 2. Число переменных в двойственной задаче равно числу ограничений исходной задачи; число ограничений в двойственной задаче – числу переменных в исходной. 3. Все переменные неотрицательны. 4. В задаче на максимум все неравенства-ограничения имеют вид « ≤ », в задаче на минимум – вид « ≥ ». 5. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены системы ограничений исходной задачи; правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной. 6. Матрицы ограничений исходной и двойственной задач являются транспонированными друг к другу. Исходная задача Двойственная задача Пример (к задаче об использовании ресурсов). Построить двойственную задачу к исходной, заданной моделью: Решение. Согласно правилам составления двойственной задачи: 1. 2. В двойственной задаче число переменных – 4; число ограничений – 2. 3. Все переменные y1, y2, y3, y4 неотрицательны. 4. В исходной задаче знак ≤ в двойственной задаче – знак ≥ 5. Коэффициенты при неизвестных в целевой функции двойственной задачи: (18;16;5;21) Правые частями в ограничениях двойственной задачи: 6. Матрицы ограничений исходной и двойственной задач являются транспонированными друг к другу: Вывод: математическая модель двойственной задачи имеет вид: Теоремы двойственности Терема 1 (основная). Если одна из двойственных задач имеет оптимальное решение, то другая тоже имеет оптимальное решение, причём экстремальные значения целевых функций равны. Если целевая функция одной задачи неограниченна на множестве допустимых решений, то система ограничений двойственной задачи противоречива. Теорема 2 (о дополняющей нежесткости). Для оптимальных планов Х* и У* двойственных задач выполняются соотношения Теорема 3 (об оценках). Значения переменных оптимальном решении двойственной задачи представляют собой оценки влияния запасов ресурсов bi на величину максимальной прибыли, т.е. Экономический смысл двойственных оценок 1. Оценка рентабельности производства и характеристик непроизводительных затрат. Рассмотрим оптимальное решение Х* основной задачи. • xj* > 0 - j-ый вид продукции является рентабельным и его следует производить в указанном количестве. По теореме 2 выполняется равенство - непроизводительные затраты отсутствуют. • xj*= 0 - j-ый вид продукции нерентабелен. Выполняется неравенство . Величина непроизводительных затрат показывает, насколько будет снижен достигнутый оптимальный уровень прибыли при изготовлении одной единицы нерентабельной продукции. 2. Оценка степени дефицитности ресурсов и влияние изменения их запасов на размер прибыли. Рассмотрим оптимальное решение Y* двойственной задачи. • yi* > 0 – означает, что соответствующий ресурс ri является дефицитным. По теореме 2 выполняется равенство (ресурс ri используется полностью); • yi* = 0 – показывает, что ресурс ri недефицитный. По теореме 2 выполняется неравенство . Излишки этого ресурса составляют величину: ; • cогласно теореме 3: величина yi* двойственной оценки ресурса ri показывает, насколько возрастёт максимальное значение целевой функции при увеличении данного ресурса на одну единицу; • двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Чем выше величина оценки, тем острее дефицитность ресурса; • отношение yi /yj определяет «норму заменяемости» ресурсов rj и ri относительно конечной прибыли. 3. Оценка эффективности изменения ассортимента продукции. Экономический смысл двойственных оценок yi* позволяет использовать их для анализа целесообразности изменений в структуре выпуска продукции. С их помощью можно рассчитать выгодным или нет будет производство новых видов продукции. Пусть ai*- нормы затрат ресурсов на производство новой продукции Р*. с* - ожидаемая прибыль от реализации единицы этой продукции. Тогда - затраты на производство Р*. Следовательно, если чистый доход – производство продукции Р* выгодно, если , то включение в план продукции Р* невыгодно. Экономико-математический анализ позволяет выявить узкие места в обеспечении ресурсами и регулировать запасы ресурсов с наибольшим экономическим эффектом. Рассмотрим связь между решениями исходной и двойственной задач. Исходная задача Двойственная задача Известно: при . Найти . Решение. Проанализируем соотношения теоремы 2. Значит Решая эту систему уравнений, найдём Таким образом, решение двойственной задачи: Вычислим значение целевой функции двойственной задачи Условие теоремы 1 выполнено: =24. Использование программы «Поиск решения» для экономического анализа Получить всю необходимую для экономического анализа информацию можно с помощью программы «Поиск решения». Для этого нужно указать тип отчёта – «устойчивость». Рассмотрим отчёт по устойчивости для задачи об использовании ресурсов: Верхняя часть таблицы содержит информацию, относящуюся к переменным. • «результ. значение» - найденные оптимальные значения . • «нормир. стоимость» - непроизводительные затраты. Для рентабельных видов продукции они равны нулю. Для нерентабельных величина нормированной стоимости показывает, на сколько изменится целевая функция в случае принудительного включения такой продукции в план производства. • «целевой коэффициент» - коэффициенты целевой функции. • «допустимое увеличение» и «допустимое уменьшение» - предельные значения приращений целевых коэффициентов и , при которых сохраняется оптимальный план прямой задачи. В рассматриваемой задаче продукт П1 включен в оптимальный план и для него и . Это означает, что если цена понизится более чем на 1 у.е., или повысится более чем на 4 у.е., то может измениться структура оптимального решения и продукт П1 может стать нерентабельным. Если цена П1 будет изменяться в интервале устойчивости продукта П1 , то этот продукт останется рентабельным. Во второй части таблицы содержится информация, относящаяся к ограничениям. • «результ. значение» - величина затрат соответствующего ресурса при реализации оптимального плана. • «теневая цена» - оптимальные значения двойственных переменных . • «ограничения правая часть» - запасы ресурсов. • «допустимое увеличение» и «допустимое уменьшение» - предельные значения приращений ресурсов и , при которых сохраняется оптимальный план двойственной задачи. В рассматриваемой задаче ресурс является дефицитным и для него и . Это значит, что если ресурс увеличится более чем на 2,5 ед. или уменьшится более чем на 5 ед., то может измениться структура оптимального плана и ресурс может стать недефицитным. Ресурс останется дефицитным, если его запасы будут изменяться в пределах . Ресурс останется недефицитным, если его запас будет не менее единиц (увеличение этого ресурса не влияет на оптимальное решение, что соответствует . 2.4. Специальные задачи линейной оптимизации Двухиндексные ЗЛП – это задачи оптимизации, в которых искомые переменные представляют собой матрицу . Примером может служить транспортная задача по критерию стоимости, которая формулируется следующим образом. В m пунктах отправления П1, П2, ... Пm, которые в дальнейшем будем называть поставщиками, сосредоточено определённое количество единиц некоторого однородного продукта, которое обозначим ai, i=1, 2, … , m. Данный продукт потребляется в n пунктах P1, P2, ... Pп, которые будем называть потребителями; объём потребления обозначим bj, j = 1, 2, … ,п. Известны расходы на перевозку единицы продукта из пункта Пi в пункт Pj, которые равны cij и приведены в матрице транспортных расходовC =(cij ). Требуется составить такой план перевозок, при котором весь продукт вывозится из пунктов Пi в пункты Pj в соответствии с потребностью и общая величина транспортных расходов будет минимальной. Обозначим количество продукта, перевозимого из пункта Пi в пункт Pj через xij. Тогда целевая функция задачи будет иметь вид: найти (2.7) при ограничениях (2.8) Первое из условий (2.8) означает полное удовлетворение спроса во всех пунктах потребления; второе условие из (2.8) определяют полный вывоз продукции от всех поставщиков. Необходимым и достаточным условием разрешимости задачи (2.7)-(2.8) является условие (2.9) Условие (2.9) означает, что суммарные запасы продукта у поставщиков равны суммарному спросу потребителей. В этом случае транспортная задача называется закрытой. Если баланс (2.9) не выполняется, задача является открытой, и одно из ограничений (2.8) принимает вид неравенства. Если в (2.9) стоит знак ≥, это значит, что суммарные мощности поставщиков превышают суммарные мощности потребителей, тогда поставщики не смогут поставить весь имеющийся запас, то есть во втором из неравенств (2.8) нужно поставить знак ≤. Наоборот, если в (2.9) стоит знак ≤, это значит, что суммарные мощности поставщиков меньше суммарных мощностей потребителей, тогда потребители не смогут получить продукции в количестве равном своим потребностям, то есть в первом из неравенств (2.8) нужно поставить знак ≤. Рассмотрим пример решения транспортной задачи в MS Excel. В четырёх районах А1, А2 ,А3 ,А4 (поставщики) имеется зерно, которое требуется доставить на три элеватора В1, В2, В3 (потребители) согласно их мощностям. Запасы зерна в районах (мощность поставщика аi), мощности элеваторов (мощность потребителя bj) и затраты на перевозку 1т зерна из каждого района на каждый элеватор (cij) приведены в таблице (матрице затрат). Составить план перевозок грузов так, чтобы затраты на эти перевозки были минимальны. Решение. 1. Введём управляющие переменные: xij – количество зерна, перевозимого из района Аi на элеватор Вj. Следовательно, искомая матрица перевозок . 2. Построим функцию цели. Стоимость перевозки зерна из пункта Аi в пункт Вj составит cij xij. Тогда целевая функция – наименьшие суммарные затраты на все перевозки – запишется выражением или в общем виде: 3. Для составления ограничений проверим баланс задачи. Всего зерна в районах (мощности поставщиков) Элеваторы могут принять (мощности потребителей) Следовательно, , задача является сбалансированной (закрытой), т.е. зерно из районов можно вывезти полностью и полностью загрузить все элеваторы. 4. Запишем систему ограничений. По поставщику: весь имеющийся на станции отправления груз будет вывезен. или По потребителю: условие полной загрузки элеваторов: или . По смыслу все Замечание. Необходимое и достаточное условие разрешимости ТЗ Условие сбалансированности задачи является необходимым и достаточным условием разрешимости ТЗ. Ответ. Величина затрат на перевозку будет минимальной и составит ден.ед., если 800 т зерна из района А1 (весь запас) отгрузить на элеватор В1; 600 т из района А2 перевезти на элеватор В2, а 100 т - на элеватор В3; 200 т из района А3 - на элеватор В1 и 800 т - на элеватор В3; 500 т (весь запас) из района А4 следует отправить на элеватор В2. В соответствии с предложенным планом зерно из всех районов будет вывезено полностью, а также полностью будут загружены все элеваторы. Дополнительные ограничения: • Запрет перевозки в направлении от Аi к Вj: . • Ограничения перевозок в направлении от Аi к Вj: или . 2.5.Модели целочисленного (дискретного) программирования Эти модели возникают, когда на искомые переменные накладываются условия целочисленности, а область допустимых решений конечна. Это связано с физической неделимостью многих элементов расчёта: например, нельзя построить полтора завода, купить полтора автомобиля, произвести полторы детали и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объёма (например, товарных запасов). В противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач, среди которых можно выделить два направления: методы отсечения (построение дополнительных ограничений и применение двойственного симплексного метода) и комбинаторного метода (например, метода ветвей и границ). В надстройке MS Excel имеются специальные возможности для решения задач целочисленного программирования. Отличие от приведённых выше алгоритмов решения задач заключается в задании дополнительного условия целочисленности переменных (Рис. 2.10). В левом поле окна Добавление ограничения указываются адреса ячеек, отведенных под искомые переменные, а в поле, отведённом для знака ограничения, выбирается значение “цел”. Подпись “целое” в правом поле окна появляется автоматически. Рисунок 2.10. Задание условий целочисленности (или двоичности) переменных. Аналогично в Поиске решения можно задать условие двоичности переменных (Рис. 2.10). Эта возможность оказывается полезной в таких типах задач как задача о назначениях, задача о выборе проектов для финансирования. Задача о назначениях Задача о назначениях – это распределительная задача, в которой для выполнения каждой работы требуется только один ресурс (человек, автомашина и т.д.) и каждый ресурс может быть использован только на одной работе. Задача о назначениях является частным случаем транспортной задачи. В качестве поставщиков выступают ресурсы с мощностями ai=1, i = 1, 2, ... , n, а в качестве потребителей – работы с мощностями bj=1, j = 1, ... , m. Известны также характеристики выполнения j-й работы с помощью i-го ресурса: cij. Требуется составить план распределения ресурсов между работами, так, чтобы общая характеристика выполнения всех работ была наилучшей. В разных задачах такая характеристика может быть разной – минимум времени, максимум продукции и т.д. Математическая постановка имеет следующий вид: xij – факт назначения или неназначения i-го ресурса на j-ю работу, то есть Найти максимум или минимум функции при ограничениях: по поставщикам (ресурсам) - по потребителям (работам) - Целевая функция выражает общую характеристику выполнения работ. Условия по поставщикам означают, что каждый ресурс может быть назначен только на одну работу. Аналогично, условия по потребителям означают, что на каждую работу может быть назначен ровно один ресурс. Задача имеет решение, если сумма мощностей поставщиков равна сумму мощностей потребителей, то есть количество ресурсов равно количеству работ: n = m. Если количество ресурсов меньше количества работ (n < m), то не все работы будут обеспечены ресурсами и в условиях по потребителям нужно ставить знак <= (меньше или равно), при этом в условии по поставщикам остаётся равенство. Если количество ресурсов больше количества работ (n > m), то не все ресурсы будут использованы при выполнении работ и в условиях по поставщикам нужно ставить знак <= (меньше или равно), при этом в условии по потребителям остаётся равенство. Рассмотрим пример задачи о назначениях. Задача. С целью получения наибольшего дохода необходимо распределить 4-х продавцов на 4-е торговые точки, причём каждый из продавцов П1, П2, П3 и П4 (п = 4) может работать на любой торговой точке Т1, Т2, Т3 и Т4 (п = 4). Эффективность (доход) cij от работы i-го продавца на j- ой торговой точке - матрица эффективности – известна заранее. Замечание: • каждый продавец может работать только на одной точке; • на каждую точку может быть назначен только один продавец. Решение. 1. Введём управляющие переменные: xij – решение о назначении i-го продавца на j- ую торговую точку. (xij = 1 – назначен; xij = 0 – не назначен). Следовательно, искомая матрица назначений . 2. Построим функцию цели. Эффективность работы продавца Пi на точке Тj составит cij xij. Тогда целевая функция – наибольший доход – запишется выражением: или в общем виде: 3. Задача является сбалансированной, т.к. число продавцов п = 4 равно числу торговых точек k = 4 . Это означает, что на каждую торговую точку обязательно будет назначен продавец, причём только один, и каждый продавец получит назначение, причём только на одну торговую точку. 4. Запишем систему ограничений. По продавцам: каждый продавец должен получить рабочее место, причём только одно. или . По торговым точкам: каждая торговая точка должна получить только одного продавца. или . По смыслу , т.е. переменные - двоичные (бинарные). Ответ. Эффективность будет максимальной , если продавца П1 назаначить на 1-ую торговую точку; П2 – на 3-ю; П3 – на 2-ую; П4 – на 4-ую. Дополнительные ограничеения: • Запрет назначения продавца Пi на точку Тj: • Принудительное назначение продавца Пi на точку Тj: . • Пусть решается несбалансированная задача, в котрой не хватает рабочих мест. Чтобы гарантировать продавцу Пs назначение, надо в системе ограничений по продавцам поставить равенство . Модели оптимизации в инвестиционном анализе Рассмотрим постановку задачи об инвестировании финансов. Предлагается п инвестиционных проектов , тщательная экономическая проработка которых позволяет получить для каждого из проектов достаточно убедительные экономические оценки ожидаемого эффекта о его реализации и необходимой величины капиталовложений . Общий объём возможных инвестиций ограничен величиной G . Необходимо так распорядиться имеющимися финансовыми ресурсами, чтобы максимизировать суммарный эффект от инвестиций. Математическая модель. Введём в рассмотрение управляющие переменные, пусть: C учётом этих обозначений задача по критерию «максимум экономического эффекта» математически запишется следующим образом: max, , . Приведённая задача является задачей дискретного линейного программирования с булевыми переменными (переменные, которые могут принимать только два значения: 1 и 0, т.е. «да» или «нет»). Тема 3. Нелинейное программирование (1/4/31) 3.1. Общая задача нелинейного программирования Задача оптимизации является нелинейной, если нелинейной является хотя бы одна функция, входящая в постановку задачи, а именно: целевая функция или левая часть функционального ограничения. У произвольной задачи нелинейного программирования некоторые или все свойства ЗЛП отсутствуют. Вследствие этого задачи нелинейного программирования несравненно сложнее задач ЛП и для них не существует общего универсального метода решения (аналогичного симплексному методу). Особое место занимают задачи типа: найти max(min)Z = f(x1, x2, … , xn) при ограничениях gi(x1, x2, … , xn) = 0, i = 1, … , m, для решения которых можно воспользоваться классическим методом оптимизации Лагранжа, или методом разрешающих множителей. При этом предполагается, что функции f и gi непрерывны вместе со своими первыми частными производными. Для решения задачи составляют функцию Лагранжа Определяют частные производные этой функции по переменным xj и множителям Лагранжа λi, приравнивают их нулю и получают систему уравнений: Решая систему, получаем множество стационарных точек, в которых функция Z может иметь экстремальные значения. При этом, как правило, неизвестен способ определения точек глобального максимума или минимума. Однако, если решения системы найдены, то для определения глобального максимума или минимума достаточно найти значения целевой функции в соответствующих точках области определения. Рассмотрим применение метода Лагранжа на примере: Найти экстремум функции Z = x1* x2 + x2* x3 при ограничениях x1 + x2 =2, x2 + x3 =2. Решение. Составляем функцию Лагранжа дифференцируем её по всем 5-и переменным и полученные выражения приравниваем 0: Из первого и третьего уравнений следует, что λ1 = λ2 = - x2, поэтому Решением системы является точка x1 = x2 = x3 = 1. Значение целевой функции в этой точке равно 2. Сравним это значение со значением целевой функции в любой точке области допустимых решений. Например, точка (0; 2; 0) является допустимым решением и в ней Z = 0. Поскольку полученное экстремальное значение Z = 2 больше, то точка (1; 1; 1) – точка глобального максимума. Рассмотрим ещё один пример задачи нелинейного программирования. Задача о портфельных инвестициях Инвестирование означает приобретение активов в целях получения будущих выгод. Инвестиции в ценные бумаги называют портфельными , а инвестиции в воспроизводство основных средств (фондов) – капитальными вложениями . Совокупность всех ценных бумаг, принадлежащих инвестору, называют портфелем ценных бумаг. Рассмотрим моделирование портфельных инвестиций или задачу оптимального формирования портфеля ценных бумаг. Приняты следующие обозначения: – средняя ожидаемая доходность j – й ценной бумаги, ( называют эффективностью j – й ценной бумаги); - дисперсия случайной доходности j – й ценной бумаги, ( называют риском j – й ценной бумаги); – ковариация дохода от ценных бумаг i и j (, ); - верхняя граница доли, которую ценные бумаги j –го вида могут составлять в структуре портфеля, . Необходимо сформировать оптимальный портфель ценных бумаг минимального риска при условии, что обеспечивается заданное значение эффективности портфеля (портфель Марковица минимального риска). Математическая модель. Пусть () – доля капитала, потраченная на покупку ценных бумаг j –го вида (весь выделенный капитал принимается за единицу). С учётом этих обозначений ЭММ задачи формирования портфеля ценных бумаг с минимальной дисперсией (вариацией портфеля) имеет следующий вид: найти (), минимизирующие дисперсию доходности портфеля ценных бумаг; при условиях: а) обеспечивается заданное значение эффективности портфеля , т.е. ; б) верхняя граница доли, которую ценные бумаги j –го вида могут составлять в структуре портфеля, составляет не более , т.е. , ; в) весь выделенный для инвестиций капитал в целях моделирования принимается за единицу, т.е. . 3.2.Метод динамического программирования (ДП) Весьма полезным вычислительным методом для решения некоторых типов задач нелинейного программирования является метод динамического программирования. При решении задачи этим методом процесс решения расчленяется на этапы, решаемые последовательно во времени и приводящие, в конечном счёте, к искомому решению. Типичные особенности многоэтапных (многошаговых) задач, решаемых методом динамического программирования, состоят в следующем. • Процесс перехода производственно-экономической системы из одного состояния в другой должен быть марковским (процесс с отсутствием последействия). Это означает, что если система находится в некотором состоянии, то дальнейшее развитие зависит только от данного состояния и не зависит от того, каким путём система приведена в это состояние. • Процесс длится определённое число шагов. На каждом шаге осуществляется выбор одного управления un, под воздействием которого переходит из одного состояния Sn в в другое Sn+1: Поскольку процесс марковский, то un = un(Sn) зависит только от текущего состояния. • Каждый шаг (выбор очередного решения) связан с определенным эффектом, который зависит от текущего состояния и принятого решения: φn(Sn, un). • Общий эффект (доход) слагается из доходов на отдельных шагах, то есть критерий оптимальности должен быть аддитивным. Требуется найти такое решение un для каждого шага (n = 1, 2, … , N), то есть последовательность решений (u1 , u2, ... , uN), чтобы получить максимальный общий эффект (доход). Любая возможная последовательность решений (u1 , u2, ... , uN) называется стратегией управления. Стратегия управления, доставляющая максимум критерию оптимальности, называется оптимальной. В основе концепции метода ДП лежит принцип оптимальности Беллмана - оптимальная стратегия обладает следующим свойством: независимо от того, каким образом система оказалась в рассматриваемом конкретном состоянии, последующие решения должны составлять оптимальную стратегию, привязывающуюся к этому состоянию. Математически этот принцип записывается в виде рекуррентного соотношения ДП: , , где - все допустимые управления при условии, что система находится в состоянии ; – эффект от принятия решения ; – эффект за оставшиеся п шагов. Благодаря принципу оптимальности удаётся при последующих переходах испытывать не все возможные варианты, а лишь оптимальные выходы. Рекуррентное отношение ДП позволяет заменить трудоёмкое вычисление оптимума по N переменным в исходной задаче решением N задач, в каждой из которых оптимум находят лишь по одной переменной. Тема 4. Оптимальные решения для отдельных классов задач оптимизации в экономике (1/2/30) 4.1.Методы управления запасами Управление запасами – это более сложная ступень их нормирования, предусматривающая активное изменение всех факторов, влияющих на образование запасов. Управление запасами заключается в установлении той или иной периодичности поставок, их объёмов, регулярности и наилучших сроков выполнения. Совокупность правил, по которым принимаются эти решения, называют системой (стратегией, политикой) управления запасами. Основные системы регулирования запасов: • система с фиксированным размером заказа; • система с фиксированной периодичностью заказа; • система с двумя фиксированными уровнями (s, S) – система; • саморегулирующиеся системы; • системы оптимального управления запасами. Примеры детерминированных моделей 1. Модель Уилсона (классическая система управления запасами, модель наиболее экономичного размера партии) Рассмотрим работу склада, на котором хранятся товарные запасы, расходуемые на снабжение потребителей. Работа склада сопровождается множеством отклонений от идеального режима. Учесть все отклонения практически невозможно, поэтому при моделировании работы склада обычно делаются следующие предположения: • скорость расходования запасов со склада - постоянная величина, которую обозначим М (единиц товарных запасов в единицу времени); в соответствии с этим график изменения величины запасов в части расходования является отрезком прямой; • объём партии пополнения Q есть постоянная величина, так что система управления запасами – это система с фиксированным размером заказа; • время разгрузки прибывшей партии пополнения запасов мало, будем считать его равным нулю; • время от принятия решения о пополнении до прихода заказанной партии есть постоянная величина так, что можно считать, что заказанная партия приходит как бы мгновенно: если нужно, чтобы она пришла точно в определённый момент, то её следует заказать в момент времени на ранее; • на складе не происходит систематического накопления или перерасхода запасов. Если через Т обозначить время между двумя последовательными поставками, то обязательно выполнение равенства: . Из сказанного выше следует, что работа склада происходит одинаковыми циклами длительностью Т, и за время цикла величина запаса изменяется от максимального уровня S до минимального уровня s; • наконец, будем считать обязательным выполнение требования, чтобы отсутствие запасов на складе было недопустимым, т.е. выполняется неравенство. С точки зрения уменьшения издержек склада на хранение отсюда вытекает, что и, следовательно, . Расходы склада, не зависящие от объёма партии, называют накладными. Сюда входят почтово-телеграфные расходы, командировочные, некоторая часть транспортных расходов и др. Накладные расходы будем обозначать через К. Издержки хранения запасов будем считать пропорциональными величине хранящихся запасов и времени их хранения. Издержки на хранение одной единицы запасов в течение одной единицы времени называют величиной удельных издержек хранения; мы будем обозначать через h . Таким образом, затраты склада за время Т при размере партии пополнения Q в случае идеального режима работы склада равны . После деления этой функции на постоянную величину Т с учётом равенства получим выражение для величины затрат на пополнение и хранение запасов, приходящихся на единицу времени: . Это и будет целевой функцией, минимизация которой позволит указать оптимальный режим работы склада. Найдём объём заказываемой партии Q , при котором минимизируется функция средних затрат склада за единицу времени, т.е. функция . Задачу на минимум можно решить методами дифференциального исчисления: , откуда находим точку минимума . Рисунок 4.1. Графики затрат Эта формула называется формулой Уилсона. Оптимальный размер партии, рассчитываемый по формуле Уилсона, обладает характеристическим свойством: размер партии Q оптимален тогда и только тогда, когда издержки хранения за время цикла Т равны накладным расходам К. Используя формулу Уилсона, в сделанных ранее предположениях об идеальной работе склада можно получить ряд расчётных характеристик работы склада в оптимальном режиме: оптимальный средний уровень запаса ; оптимальная периодичность пополнения запасов ; оптимальные средние издержки хранения запасов в единицу времени . величина x = t M/T определяет точку заказа: каждый раз, когда на складе остаётся х единиц подаётся новый заказ на Qопт единиц товара (t -период его поставки). Пример. На склад доставляют цемент на барже по 1500 т. В сутки со склада потребители забирают 50 т цемента. Накладные расходы по доставке партии цемента равны 2 тыс. руб. Издержки хранения 1 т цемента в течение суток равны 0,1 руб. Требуется определить: 1) длительность цикла, среднесуточные накладные расходы и среднесуточные издержки хранения; 2) эти же величины для размеров партии в 500 т и в 3000 т; 3) каковы оптимальный размер заказываемой партии и расчётные характеристики работы склада в оптимальном режиме. Решение. Параметры работы склада: М = 50 т/сут.; К =2 тыс. руб.; h = 0,1 руб/т·сут.; Q =1500 n/ 1. Длительность цикла: среднесуточные накладные расходы: среднесуточные издержки хранения: 2. Аналогичные расчёты проведём для : среднесуточные накладные расходы: среднесуточные издержки хранения: и для : среднесуточные накладные расходы: среднесуточные издержки хранения: 3. Найдём оптимальный размер заказываемой партии по формуле Уилсона: ; оптимальный средний уровень запаса ; оптимальная периодичность пополнения запасов ; оптимальные средние издержки хранения запасов в единицу времени . 2. Классическая модель с допущением дефицита В некоторых случаях издержки хранения продукции являются гораздо более высокими, чем издержки, связанные с отсутствием запаса в течение небольшого промежутка времени. Для этого разработаны модели управления запасами, моделирующие два вида ситуаций, когда: 1. при наличии дефицита заказы покупателей не выполняются и никак не учитываются на будущее; 2. заказы покупателей выполняются с задержкой, т.е. после получения очередного заказа. Изменение уровня запасов в обеих ситуациях представлено на рисунках 4.2 и 4.3. Рисунок 4.2. Изменение уровня запасов с учётом планирования дефицита для ситуации 1 Рисунок 4.3. Изменение уровня запасов с учётом планирования дефицита для ситуации 2 Случай невыполнения заявок Введём дополнительные обозначения: S – максимальный размер дефицита (максимально возможное число единиц товара, которое могло бы быть реализовано за время его отсутствия в каждом цикле); Cd – годовая стоимость отсутствия единицы продукции в запасе (потеря доверия клиентов, непроданная продукция и т.д.). Издержки торгового склада в этом случае определяются по формуле: Издержки ТС = Стоимость подачи заказа+ Стоимость хранения + Штраф за дефицит, Где под Q следует понимать Qопт , то есть оптимальный размер заказа. Решениями этой задачи будут величины: . Случай выполнения заявок В случае выполнения заявок максимальный уровень запасов будет равен не Qопт, а Издержки ТС = Стоимость подачи заказа+ Стоимость хранения + Штраф за дефицит, Решениями этой задачи будут величины: . 4.2. Методы массового обслуживания Система массового обслуживания (СМО) – это система, в которой, с одной стороны, возникают массовые запросы (требования) на выполнение каких-либо услуг, а с другой происходит удовлетворение этих запросов. Всякая система массового обслуживания (СМО) содержит следующие элементы: • источник требований; • входящий поток; • очередь; • обслуживающее устройство; • выходящий поток. СМО классифицируют по разным признакам • По месту нахождения источника требования разомкнутые – источник требования находится вне системы, число требований неограниченно (магазины, вокзалы и т.п.); замкнутые - источник находится в системе, число требований ограничено (работа водопроводчика или сантехника в ЖЭУ). • По условиям ожидания клиентом начала обслуживания СМО с отказами (телефонная станция: требование на соединение получает отказ, если вызываемый абонент занят). Для системы с отказами основными характеристиками являются вероятность отказа и средняя доля заявок, оставшихся неудовлетворёнными. СМО с ожиданием – работа кассиров с покупателями в магазине самообслуживания. В СМО с ожиданием требование, поступившее в момент, когда все каналы обслуживания заняты, не покидает систему, а становится в очередь. При освобождении очередного канала одна из заявок из очереди немедленно принимается на обслуживание. Для СМО с ожиданием основными характеристиками являются средняя длина очереди и среднее время ожидания. Рис.4.4. Структура СМО Встречаются смешанные СМО. Для них характерно наличие промежуточных условий: ограничение длины очереди, времени ожидания и т.п. • По числу одновременно обслуживаемых объектов (каналов): одноканальные и многоканальные. • По дисциплине обслуживания: системы с приоритетом в обслуживании и без приоритета. • СМО однофазные и многофазные. В однофазных СМО требования обслуживаются каналами одного типа без передачи их от одного канала к другому (кассиры), в многофазных такое возможно (салон красоты). Методы теории массового обслуживания позволяют проводить анализ эффективности работы СМО. Наиболее разработаны методы решения задач для простейших (пуассоновских) потоков требований. Простейший поток обладает тремя основными свойствами: • ординарностью (означает практическую невозможность одновременного поступления двух или более требований); • стационарностью (среднее число поступивших в систему требований зависит только от продолжительности временного интервала); • отсутствием последействия (число требования поступивших в систему до времени t , не влияет на количество требований поступивших в следующий момент) Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно k требований задаётся формулой: , где λ – параметр, интенсивность входящего потока заявок. Теория массового обслуживания ставит своей задачей организовать обслуживание таким образом, чтобы длина очереди была минимальной, а время прохождения заявки - оптимальным. При этом должно обеспечиваться минимальное время простоя системы и её максимально возможная загрузка. Наиболее распространёнными являются СМО с ожиданиями. Система состоит из п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование. В систему поступает простейший (пуассоновский) поток требований. Если в момент поступления очередного требования в системе уже обслуживается п требований, то новое требование становится в очередь. Время обслуживания каждого требования – случайная величина, распределённая по экспоненциальному закону. Обозначим т – число обслуживаемых объектов (для разомкнутой СМО); n – число обслуживающих аппаратов; λ – интенсивность поступления требований (для замкнутой СМО – частота требований от отдельного источника; для разомкнутой СМО - частота требований от всех источников); – среднее время обслуживания одного требования; В замкнутой системе поток поступающих требований ограничен (в СМО может находиться не более т требований). В разомкнутой системе количество требований не ограничено. Для нормального функционирования такой системы необходимо, чтобы очередь не росла бесконечно, т.е. количество обслуживающих аппаратов п должно быть не меньше, чем среднее число занятых аппаратов : . Для описания работы системы составляют ряд распределений случайной величины k – количества требований, поступающих в систему: k 1 … n … m(x) Pk P0 P1 … Pn … … Pk – вероятности, что в системе находится k требований. Их вычисляют по формуле . Предварительно нужно определить коэффициенты . Их расчёт выполняется по-разному для замкнутых и разомкнутых СМО и, кроме того, зависит от величины k. (отсутствие очереди) (очередь) Замкнутая СМО Разомкнутая СМО Вероятность того, что все обслуживающие аппараты свободны : для замкнутой СМО:. для разомкнутой СМО:. Вероятность отказа в немедленном обслуживании (все аппараты заняты, возникает очередь): для замкнутой СМО: . для разомкнутой СМО: . Для оценки качества функционирования рассматриваемой системы используют следующие основные критерии: Коэффициенты простоя 1. Коэффициент простоя требования в ожидании обслуживания – только для замкнутой СМО . 2. Коэффициент полного простоя требования (на обслуживании и в ожидании обслуживания) – только для замкнутой СМО . Коэффициент простоя обслуживающих аппаратов . Рассмотрим пример расчёта характеристик замкнутой СМО. Пример. Бригада обслуживает 4 объекта, получая в среднем от каждого 3 заявки в час и затрачивая в среднем 20 минут. Поток заявок можно считать пуассоновским. Сколько мастеров должно быть в бригаде, чтобы средняя длина очереди не превышала 1 заявки? Решение. По условию CМО замкнутая, Предположим, что в бригаде 1 мастер. Определим среднюю длину очереди. Для чего проведём вспомогательные расчёты. Количество заявок в системе Коэффициенты и вычислим по формуле , а по формуле . Суммируем Вероятность, что отсутствуют заявки (мастер свободен): Заполним столбец вероятностей Кол-во заявок обслуж. n= 1 1 4 0,015 0,062 очередь m= 2 3 4 12 24 24 0,185 0,369 0,369 0,184615 0,738462 1,107692 Сумма 65 1 2,030769 Cредняя длина очереди составит , что не удовлетворяет требованиям задачи. Один мастер не обеспечивает своевременного выполнения заявок. Положим и выполним аналогичные расчёты: Кол-во заявок обслуж. n= 1 2 1 4 6 0,05 0,2 0,3 очередь m= 3 4 6 3 0,3 0,15 0,3 0,3 Сумма 20 1 0,6 Средняя длина очереди составит . Таким образом, при наличии 2-х мастеров средняя длина очереди не превышает 1 заявки. Рассмотрим n- канальную СМО с отказами, т.е. в системе имеется п приборов, на которые поступает простейший поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ=. Заявка, заставшая систему занятой, сразу же покидает её. Следует определить: вероятность того, что заявка, пришедшая в момент времени t , получит отказ; абсолютную и относительную пропускную способность СМО; среднее число заявок, обслуживаемых одновременно (другими словами, среднее число занятых каналов). Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале XX века датским математиком Эрлангом. 1. Вероятность отказа в обслуживании (формулы Эрланга) , где ; - нагрузка на систему. 2. Относительная пропускная способность В, т.е. вероятность того, что заявка будет обслужена, . 3. Абсолютную пропускную способность А получим, умножая интенсивность потока заявок λ на В: . 4. Cреднее число занятых каналов . Пример. На строительном участке в инструментальной мастерской работают два мастера. Если рабочий заходит в мастерскую, когда оба мастера заняты обслуживанием ранее обратившихся работников, то он покидает мастерскую, не ожидая обслуживания. Статистика показал, что среднее число рабочих, обращающихся в мастерскую в течение часа, равно 18; среднее время, которое затрачивает мастер на заточку или ремонтравно10 мин. Оценить основные характеристики работы данной мастерской как СМО с отказами. Сколько мастеров должно работать в мастерской, чтобы вероятность обслуживания рабочих была выше 85%? Рис.4.5. Расчёт характеристик СМО в Excel Расчёты проведём в Excel. Видно, что СМО перегружена: из двух мастеров занято в среднем М=1,4, а из обращающихся в мастерскую рабочих около Ротк =53% остаются необслуженными. Из графика на рисунке 4.6 видно, что минимальное число каналов обслуживания (мастеров), при котором вероятность обслуживания работников будет выше 85% (вероятность отказа ниже 15%), равно . Рис.4.6. График вероятности отказа в обслуживании 4.3. Методы сетевого планирования и управления Сетевой моделью (сетевым графиком, сетью) называется экономико-математическая модель, отражающая комплекс работ (операций) и событий, связанных с реализацией некоторого проекта (научно-исследовательского, производственного и др.), в их логической и технологической последовательности и связи. Анализ сетевой модели, представленный в графической или табличной (матричной) форме, позволяет, во-первых, более четко выявить взаимосвязи этапов реализации проекта и, во-первых, определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращение сроков выполнения всего комплекса работ. Математический аппарат сетевых моделей базируется на теории графов. Графом называется совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами. Если рассматриваемые пары вершин являются упорядоченными, то есть на каждом ребре задаётся направление, то граф называется ориентированным; в противном случае – неориентированным. Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь. Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным. Граф, в котором два ребра не имеют общих точек, кроме инцидентной им обоим вершины, называют плоским. Если граф имеет цикл, содержащий все ребра по одному разу, то такой граф называют эйлеровым. Если этот цикл является к тому же простым (вершины не повторяются) то граф называют гамильтоновым. В экономике чаще всего используются два вида графов: дерево и сеть. Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. Сеть – это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф виды «сеть». Основные понятия СМ: событие, работа и путь. Работа характеризует материальное действие, требующее использование ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом представлении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i, j), где i – номер событие, из которого работа выходит, а j – номер события, в которое она входит. Каждая работа имеет определённую продолжительность t(i, j). К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и на графике изображаются пунктирными стрелками. Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени. События свершаются в тот момент, когда оканчивается последняя из работ, входящая в него. События обозначаются одним числом и при графическом представлении СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2, ... N). В СМ имеется начальное событие (с номером 1), из которого только выходят, и конечное событие (с номером N), в которое работы только входят. Путь – это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают Lкр, а его продолжительность tкр. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведёт к срыву срока всего комплекса работ. Кратчайший путь – это путь, имеющий наименьшую продолжительность от исходного события до завершающего. Рис.4.7. Сетевой график Рис.4.8. Элементы сетевого графика Основные характеристики СМ и методы их расчёта СМ имеют ряд характеристик, которые позволяют определить степень напряжённости выполнения отдельных работ, а также всего их комплекса и принять решение о перераспределении ресурсов. Однако перед расчётом СМ следует убедиться, что она удовлетворяет следующим основным требованиям: 1. События правильно пронумерованы, то есть для каждой работы (i, j) i < j. При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем: • нумерация событий начинается с исходного события, которому присваивается №1; • из исходного события вычеркивают все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают №2; • затем вычёркивают работы, выходящие из события №2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают №3, и так продолжается до завершающего события, номер кото- рого должен быть равен количеству событий в сетевом графике; • если при очередном вычеркивании работ одновременно несколько событий не имеют входящих работ, то их нумеруют очередными номерами в произвольном порядке. 2. Отсутствуют тупиковые события (кроме завершающего), то есть такие, за которыми не следует хотя бы одна работа. 3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа. 4. Отсутствуют циклы, то есть замкнутые пути, соединяющие события с ним же самим. При невыполнении указанных требований бессмысленно приступать к вычислениям характеристик событий, работ и критического пути. Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв. Ранний срок свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причём tp(1)=0, а tp(N) = tкр(L): Поздний срок свершения события характеризует самый поздний допустимый срок, к которому должно совершаться событие, не вызывая при этом срыва свершения конечного события: Этот показатель определяется «обратным ходом», начиная с завершающего события, с учётом соотношения tП(N) = tР(N). Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i): R(i) = tП(i) - tР(i). Резерв показывает, на какой предельно допустимый срок можно задержать наступление этого события, не вызывая при этом увеличении срока выполнения всего комплекса работ. Полный резерв времени показывает, насколько можно увеличить время выполнения конкретной работы при условии, что срок выполнения всего комплекса работ не изменится. Независимый резерв времени соответствует случаю, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие – начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ. Путь характеризуется двумя показателями – продолжительностью и резервом. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Резерв определяется как разность между длинами критического и рассматриваемого путей. Из этого определения следует, что работы, лежащие на критическом пути, и сам критический путь имеют нулевой резерв времени. Резерв времени пути показывает, насколько может увеличиться продолжительность работ, составляющий данный путь, без изменения продолжительности общего срока выполнения всех работ. Продолжительность выполнения работ часто трудно задать точно и поэтому в практической работе вместо одного числа (детерминированная оценка) задаются две оценки – минимальная и максимальная. Минимальная (оптимистическая) оценка характеризует продолжительность выполнения работы при наиболее благоприятных обстоятельствах, а максимальная (пессимистическая) – при наиболее неблагоприятных. Продолжительность работы в этом случае рассматривается как случайная величина, которая в результате реализации может принять любое значение в заданном интервале. Такие оценки называются вероятностными (случайными), и их ожидаемое значение оценивается по формуле (при бета-распределении плотности вероятности): Для характеристики степени разброса возможных значений вокруг ожидаемого уровня используется показатель дисперсии: На основе этих оценок можно рассчитать все характеристики СМ, однако они будут иметь иную природу, будут выступать как средние характеристики. При достаточно большом количестве работ можно утверждать (а при малом – лишь предполагать), что общая продолжительность любого, в том числе и критического, пути имеет нормальный закон распределения со средним значением, равным сумме средних значений продолжительности составляющих его работ, и дисперсией, равной сумме дисперсий этих же работ. Кроме обычных характеристик СМ, при вероятностном задании продолжительности работ можно решить две дополнительные задачи: 1. определить вероятность того, что продолжительность критического пути не превысит заданного директивного уровня Т ; 2. определить максимальный срок выполнения всего комплекса работ Т при заданном уровне вероятности р. Первая задача решается на основе интеграла вероятностей Лапласа использованием формулы: Где z – нормированное отклонение случайной величины: – среднее квадратическое отклонение, вычисляемое как корень квадратный из дисперсии продолжительность критического пути. Значения функции Лапласа находятся в таблице в статистической литературе. При достаточно большой полученной величине вероятности (более 0,8) можно с высокой степенью уверенности предполагать своевременность выполнения всего комплекса работ. Для решения второй задачи используется формула: Методы оптимизации сетевых моделей реализованы в существующих автоматизированных системах планирования и управления. Таких систем существуют достаточно много. Например, система MS Project 2007. Программа MS Project 2007 даёт возможность формировать сетевые графики, определять время проведения работ, назначать необходимые ресурсы, проводить анализ результатов, управлять ресурсами и финансами. Пробную версию можно найти на официальном сайте Microsoft Office по адресу: http://www.microsoft.com (после регистрации пользователь получает ссылку на ключ по электронной почте). 4.4.Метод статистического моделирования Для того чтобы определить законы распределений, которыми определяются входящий поток требований СМО и длительность обслуживания, необходимо выполнить следующие этапы: • построение статистического ряда; • расчёт моментов статистического распределения; • выбор типа кривой распределения; • оценка параметров выбранной кривой распределения; • проверка согласованности статистического распределения с теоретическим. После группировки данных строится гистограмма частот. По её внешнему виду выбирают распределение одного из видов. Оценку параметров выбранной функции распределения осуществляют одним из следующих методов: • метод наибольшего правдоподобия Фишера • метод минимума χ2 • метод наименьших квадратов • метод моментов. Рассмотрим последний. Согласно методу моментов параметры функции распределения определяются из условия равенства статистических и теоретических моментов. Число рассматриваемых моментов при этом равняется числу неизвестных параметров. Вопрос о согласованности статистического распределения с теоретическим решается с помощью критериев согласия. Наиболее часто используют критерий Пирсона (χ2) в предположении, что объём выборки достаточно большой. , где k – количество разрядов (интервалов) при группировке; i - порядковый номер разряда; – наблюдаемые (эмпирические) частоты; – расчётные (теоретические) частоты. Для оценки соответствия экспериментального распределения теоретическому можно воспользоваться имеющимися таблицами, а можно правилом Романовского: , где ν – число степеней свободы (, s – число параметров функции распределения). Если неравенство выполняется, то расхождения между эмпирическим и теоретическим распределениями с.в. несущественны. В противном случае расхождения следует считать существенными, а эмпирическое распределение – не согласующимся с выбранным теоретическим законом распределения. Табличное представление моделирующего алгоритма Критерий χ2 при исследовании длительности обслуживания вычисляется по данным таблицы, имеющей следующую форму: Интервал времени Кумулятивное значение наблюдаемой частоты Кумулятивное значение теоретической частоты Кумулятивное значение теоретической частоты определяем по формуле , где N – объём выборки; – дополнительная функция распределения. Например: • для показательного (экспоненциального) закона распределения длительности обслуживания ; • для закона распределения Эрланга =; • для гиперэкспоненциального распределения , . Эти законы наиболее часто встречаются на практике. Вычисление в таблице (выше) начинаются (первая строка) с интервала времени, равного нулю. Соответственно, в графе «Кумулятивное значение наблюдаемой частоты» по определению дополнительной функции распределения фиксируется N , а в графе «Кумулятивное значение теоретической частоты» также получаем N (). Пример. На автомобильном заводе решается задача определения оптимального числа служащих, выдающих рабочим инструменты из инструментальной кладовой. Предварительно проводится статистическое исследование входящего потока требований (рабочих) и длительности их обслуживания служащими этой кладовой. Решение. Исследование начинается с определения статистических характеристик прибытия рабочих (клиентов) и времени, затрачиваемого служащими на их обслуживание. Изучение входящего потока проводим следующим образом. Каждые 10 мин (в течение 100 последовательных 10-минутных интервалов) отмечается число рабочих, пришедших за инструментами. Подсчитывается частота, соответствующая этим числам. Результат заносится в соответствующую графу таблицы. Среднее значение данной совокупности равно 15,6. В четвёртую графу этой же таблицы занесены частоты, соответствующие теоретическому распределению – распределению Пуассона. Затем с помощью критерия χ2 поверяется приемлемость гипотезы о пуассоновском распределении исследуемой совокупности. Расчётные частоты определяются в соответствии с пуассоновским распределением по формуле . В этой формуле означает вероятность попадания в 10-минутный интервал количества требований, соответствующих i – му интервалу. Например, , (первому интервалу соответствует 5 требований). Величина содержится в ячейке D44 как результат вычисления по формуле =100*(EXP(-15,6))*(15,6^B44)/ФАКТР (В44). Аналогично в Excel рассчитываются все остальные частоты. Рис. 4.9.Статистическое исследование входящего потока Используем правило Романовского. Здесь . Итак, можно допустить, что рассматриваемое распределение следует закону Пуассона с параметром λ=15,6/10=1,56 требования/мин. Чтобы измерить длительность обслуживания, используется таймер, который включают в начале обслуживания и выключают в конце. Таким образом регистрируется продолжительность 1000 обслуживаний. Затем подсчитывают кумулятивные (накопленные) частоты, соответствующие 0; 15; 30; 45; 60; 75;…;300 c. Эти данные приведены в первых трёх графах таблицы (ниже). После проведения замеров было вычислено среднее значение μ. Оно оказалось равным 0,9. В четвёртую графу таблицы для сравнения занесены значения кумулятивных частот, соответствующие показательному закону . Например, кумулятивная частота по показательному закону содержится в ячейке D5 как результат вычисления по формуле =1000*EXP(-0,9*B5/60). Меру расхождения определяем как сумму последнего столбца, где - кумулятивное значение наблюдаемой частоты; - кумулятивная частота по показательному закону. В нашем случае при числе степеней свободы, равном 19. Тогда . Итак, можно допустить, что в рассматриваемом случае имеет место показательное распределение с интенсивностью обслуживания μ=0,9 интервала обслуживания в минуту. Рис.4.10. Статистическое исследование длительности Имитационное моделирование Имитационное моделирование – это численный процесс проведения на компьютерах экспериментов с математическими моделями, описывающими состояние сложных систем в течение длительных периодов времени. Преимущества имитационного моделирования: 1. имитация на компьютере позволяет исследовать особенности функционирования системы и выработки рекомендаций по улучшению в широком спектре возможных условий 2. применение вычислительной техники сокращает продолжительность испытаний системы. Использование имитационного моделирования целесообразно, если: • неприемлемы или отсутствуют аналитические методы решения задач; • есть полная уверенность в успешном создании имитационной модели, адекватно описывающей исследуемую систему или процесс. • имеется возможность использовать процесс построения имитационной модели для предварительного исследования моделируемой системы и выработки рекомендаций по улучшению её работы. Важный момент при исследовании на имитационных моделях - установить адекватность модели реальным объектам. Оценка адекватность модели включает оценку адекватности её принципиальной структуры, т.е. замысла, и оценку достоверности реализации. Например, если известно решение, полученное аналитическим методом. Этапы реализации метода имитационного моделирования 1. Составление моделирующего алгоритма (логической структуры или таблицы). 2. Разработка методики моделирования, включая планирование экспериментов, и методики статистической обработки результатов экспериментов. 3. Разработка программного обеспечения, которое может быть выполнено с помощью общепринятых электронных таблиц, языков программирования или специальных методов и систем моделирования. 4. Проведение имитационного моделирования на компьютере, анализ и обобщение полученных результатов. Пример моделирующего алгоритма Рассмотрим блок-схему, приведённую на рисунок 4.10. В блоке 2 с помощью генератора случайных чисел формируются N реализаций τi случайной величины (с.в.) длительности интервала τ между очередными поступлениями N требований. Соответственно, кумулятивным образом на временной оси [0,T] фиксируется время (i=1,2,…,N) поступления каждого из N требований. Далее к обслуживанию принимается первое требование (i=1) , а в последующем – некоторое i- е требование по принципу (блок 3). Число k фиксируется в блоке 6 (исходное значение k=0). Для получения реализации (для фиксированного i) с.в. длительности обслуживания t в блоке 5 используется соответствующий датчик. Затем в этом блоке определяется момент окончания обслуживания рассматриваемого требования: Далее последовательно сравниваются время окончания обслуживания каналом данного требования и время поступления требований данного требования и время поступления требований (после i –го требования); в счётчике отказов фиксируется 0 (требование принято к обслуживанию) или 1 (требованию отказано в обслуживании). Первое требование, для которого выполняется условие (после зафиксированного i –го требования), и определит число k, по которому и осуществится переход к новому циклу расчётов (переход из блока 6 к блоку 3). При обработке результатов имитационного эксперимента (блок 7), в частности, проводится статистическая оценка вероятности отказа в обслуживании (если в соответствии со счётчиком отказов зафиксировано отказов, то ). Рис. 4.11. Моделирующий алгоритм Имитация с применением метода Монте-Карло, использование средств Excel Метод Монте-Карло – это метод статистического моделирования, позволяющий воспроизводить на компьютере случайные величины с заданными законами распределения. Отдельные реализации этих с.в. называют псевдослучайными числами. Процедуры получения таких чисел называют датчиками псевдослучайных чисел. Непрерывное равномерное распределение (р.р.) моделирует функция Excel =СЛЧИС(), которая возвращает случайное число из интервала от 0 до 1. Для моделирования в Excel дискретного р.р. целых чисел, принимающих значения от x до y, используется формула: =ЦЕЛОЕ (Х+(Y-X+1)*СЛЧИС()) В общем случае генерирование случайных чисел основывается на использовании фундаментального соотношения теории вероятности: где xi - случайные числа с законом распределения, соответствующим плотности распределения (нижний предел интеграла равен 0, если необходимы только положительные числа); Pi – случайные числа с р.р. в интервале от 0 до 1. Например, используя это соотношение для получения случайных чисел с показательным законом распределения , будем иметь . Примеры применения имитационного моделирования в задаче СМО Пример 1. С помощью табличной модели проведём имитацию функционирования инструментальной мастерской, в которой работают два мастера. Если рабочий заходит в мастерскую, когда оба мастера заняты обслуживанием ранее обратившихся работников, то он покидает мастерскую, не ожидая обслуживания. Статистика показал, что среднее число рабочих, обращающихся в мастерскую в течение часа, равно 18; среднее время, которое затрачивает мастер на заточку или ремонт равно10 мин(1/6 часа). Дать оценку вероятности отказа в обслуживании в этой двухканальной СМО с отказами в предположении, что входящий поток рабочих – это простейший поток (λ = 18), а время обслуживания следует экспоненциальному закону (μ = 6). Решение. Имитационный эксперимент проведём с использованием MS Excel. На рисунке 4.12 представлен моделирующий алгоритм (табличная имитационная модель) при числе испытаний N = 15. Рис.4.12. Табличное представление имитации Для получения случайных чисел с показательным законом распределения использовано соотношение . Случайные числа Pi с равномерным их распределением в интервале от 0 до 1 получены с помощью функции =СЛЧИС() Мастер функций (Математические). Эти числа содержатся в ячейках $C$4:$Q$4 (рис.5.2). Пятнадцать реализаций с.в. длительности интервала τ (в часах) между очередными поступлениями требований (рабочих) содержатся в ячейках $C$5:$Q$5. Для получения, например, содержимого ячейки С5 использована функция =(-1/18)*LN(C4). Соответственно, кумулятивным образом (строка 7) на временной оси [0, T] зафиксировано время Тi ( i=1,2,…,15) поступления требований (в минутах, с округлением). Для получения реализаций с.в. длительности обслуживания t (в минутах, с округлением) в соответствующую ячейку электронной таблицы (строки 8 и 10) записывается формула =60*(-1/6)*LN(СЛЧИС()). Рис.4.12. Табличное представление имитации Далее последовательно сравниваются время окончания обслуживания каналами (строки 9 и 11) и время поступления требований (строка 7); соответственно, в счётчике отказов (строка 12) фиксируется 0 (требование принято к обслуживанию) или 1 (требованию отказано в обслуживании). В соответствии со счётчиком отказов (в ячейках $C$12:$Q$12) зафиксировано 8 отказов, т.е. статистическая оценка вероятности отказа в данной СМО при N =15 равна (8/15) =0,53. В общем случае для более точной оценки необходимо увеличить число испытаний N. Следует отметить, что во многих реальных задачах для получения результатов имитации приемлемой точности достаточно провести N = 100 испытаний. При проведении имитационных экспериментов в среде MS Excel используются два подхода к организации датчиков случайных чисел. Первый подход. В практических расчётах с применением встроенных функций Excel можно использовать следующую процедуру получения случайных чисел. Например, для нормально распределённой случайной величины. 1. С помощью датчика равномерно распределённых случайных чисел Мастер функций Excel/ СЛЧИС получаем число Pi. 2. С помощью соответствующей встроенной функции Excel, например, Мастер функций Excel/ НОРМОБР, находим соответствующее Pi число xi с требуемым законом распределения вероятностей. Так, чтобы получить значение нормально распределённой случайной величины сроков поставки товара со средним значением т = 3 дня и стандартным отклонением σ = 1 день, надо применить формулу Excel =НОРМОБР(СЛЧИС();3;1). Второй подход. Применение инструмента Генерация случайных чисел требует установки надстройки Excel Пакет анализа. При вызове этой надстройки (Данные/ Анализ данных) появляется диалоговое окно Анализ данных, содержащее список инструментов анализа (рисунок 4.13). Рис.4.13. Диалоговое окно Анализ данных Из списка Инструменты анализа выбирается пункт Генерация случайных чисел (кнопка ОК). На экране появляется диалоговое окно Генерация случайных чисел (рисунок 4.14). Рис.4.14. Диалоговое окно Генерация случайных чисел Рассматриваемая надстройка позволяет использовать семь типов распределений: равномерное, нормальное, Бернулли, биномиальное, Пуассона, модельное и дискретное. Для заполнения полей диалогового окна Генерация случайных чисел следует использовать режим справки (клавиша Справка). Для моделирования некоторой дискретной с.в. с конечным числом исходов можно предложить следующий алгоритм (датчик): сначала из опытных данных определяются частоты появления возможных значений этой величины. По частотам вычисляются вероятности, по вероятностям – кумулятивные вероятности. Затем с использованием кумулятивных вероятностей устанавливается соответствие между случайными числами и значениями случайной величины. Далее генерируются несколько случайных чисел, по ним восстанавливаются значения с.в., и определяются нужные характеристики. Пример . Известны данные по количеству холодильников, выпускаемых в час сборочной линией компании: Количество холодильников 3 4 5 6 Процентная частота 15 45 30 10 Смоделируйте объём выпуска холодильников для целей построения имитационной модели (предложите описание датчика случайных чисел, получите 10 случайных чисел в Excel). Решение. Заполним следующую таблицу: V Вероятность Кумулятивная вероятность Случайные числа 3 0,15 0,15 0-14 4 0,45 0,60 15-59 5 0,30 0,90 60-89 6 0,10 1,00 90-99 Сумма 1,00 Полученная таблица используется следующим образом. С помощью функции =ЦЕЛОЕ(100*СЛЧИС()) Мастер функций Excel получаем случайные числа (с.ч.). определяем, в какой интервал нашей таблицы они попадают, и находим соответствующие значения V: Час 1 2 3 4 5 6 7 8 9 10 с.ч. 58 9 32 74 8 51 64 88 94 41 V 4 3 4 5 3 4 5 5 6 4 Подобным образом для целей построения имитационной модели может быть получено любое количество псевдослучайных чисел (V). Система моделирования GPSS World Эта система ориентирована на имитационное моделирование систем массового обслуживания. Система представляет собой среду программирования, состоящую из языка GPSS и транслятора, разработана компанией Minuteman Software (США) и в варианте студенческой версии распространяется бесплатно с сайта компании http://www.minutemansoftware.com. Модели в GPSS World записываются в виде блоков, каждый из которых предназначен для выполнения своей функции и имеет различные свойства (СЧА – системные числовые атрибуты), которые могут быть использованы в дальнейшем для формирования результатов моделирования. Блоки в TERMINATE уничтожает заявки и т.д. Тема 5. Методы оптимальных решений в условиях неопределенности (0,5/2/28) 5.1.Основные понятия и определения теории игр. Теория игр - это математическая теория конфликтных ситуаций, разрабатывающая рекомендации по наиболее рациональному образу действий каждого из участников в ходе конфликтных ситуаций, т.е. таких действий, которые обеспечивали бы ему наилучший результат. Игра – это упрощённая математическая модель конфликтной ситуации, отличающаяся от реального конфликта тем, что ведётся по определённым правилам. Исход игры – это значение некоторой функции, называемой функцией выигрышы, котрая может задаваться аналитически либо таблично (матрицей, её называют матрицей игры или платёжной матрицей). Игра, в котрой выигрыши и проигрыши игроков задаются матрицей, называется матричной. Игра, в которой один из игроков выигрывает ровно столько, сколько проигрывает другой, называется игрой с нулевой суммой. Под стратегией в игре понимают совокупность правил, опреляющих выбор игроком одного из возможных вариантов действий. Задачи теории игр 1. Выбор оптимальной стратегии 2. Определение размера выигрыша 3. Определение наилучшей стратегии на предприятии с учётом представлений о других участниках игры (конкурентах), их ресурсах и возможных поступках Постановка задачи: • имеется множество конфликтующих сторон, принимающих решения, интересы которых не совпадают; • сформулированы правила выбора допустимых стратегий, известные игрокам; • определен набор возможных конечных состояний игры (например, выигрыш, ничья, проигрыш); • всем игрокам заранее известны функции выигрыша (платежи), соответствующие каждому возможному конечному состоянию. Пример. В игре участвуют два игрока, каждый из них может записать независимо от другого 1,2 и 3. Если разность между цифрами, записанными игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами; и наоборот: если разность отрицательна, то выигрывает второй игрок. Если разность равна нулю, игра заканчивается в ничью. У первого игрока три стратегии: A1 (записать 1), А2 (записать 2) и А3 (записать 3); у второго игрока также три стратегии: В1, В2, В3. Задача первого игрока - максимизировать свой выигрыш, задача второго игрока - минимизировать свой проигрыш. Матрица игры, или платёжная матрица, имеет вид . Найдём наилучшую стратегию первого игрока. Если игрок выбрал стратегию A1, то в худшем случае он получит выигрыш При выборе стратегии А2 выигрыш составит , а при выборе стратегии А3 - соответственно . Предвидя такую возможность, первый игрок должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш: . Аналогично определяется наилучшую стратегию второго игрока. Второй игрок при выборе стратегии В1 в худшем случае получит проигрыш При выборе стратегии или проигрыш составит соответственно ; Второй игрок выбирает стратегию, при которой его проигрыш будет минимальным: Величина α – гарантированный выигрыш игрока – называется, нижней ценой игры. Стратегия, обеспечивающая получение выигрыша α, называется максиминной. Величина β – гарантированный проигрыш игрока – называется, верхней ценой игры. Стратегия, обеспечивающая получение проигрыша β, называется минимаксной. Для матричных игр справедливо неравенство Если , то такая игра называется игрой с седловой точкой. Элемент матрицы, соответствующий паре оптимальных стратегий, называется седловой точкой. Этот элемент является ценой игры. Таким образом, решением игры, рассмотренной выше, будут оптимальные стратегии: A3* (i = 3 – третья строка), В3* (j = 3 – третий столбец); цена игры ν. Игры с природой Игры с природой – это игры, в которых неопределённость вызвана не сознательным противодействием противника, а недостаточной осведомлённостью об условиях, в которых действуют стороны. Например, заранее неизвестна погода в некотором регионе или покупательский спрос на некоторую продукцию. Условия такой игры обычно представляются таблицей решений, в которой строки а1, а2,…, аm соответствует стратегиям ЛПР (лица, принимающего решения), а столбцы b1, b2,…, bn - стратегиям природы; aij – выигрыш ЛПР, соответствующий каждой паре стратегий аi, bj . Возможные стратегии b1 b2 … bn a1 a11 a12 … a1n … … … … … am am1 am2 … amn В рассматриваемой ситуации при выборе из множества { а1, а2,…, аm} наилучшего решения обычно используют следующие критерии. 1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она выбирается из условия и совпадает с нижней ценой игры. Критерий Вальда является пессимистическим: считается, что природа будет действовать наихудшем для человеком способом. 2. Критерий максимума. Он выбирается из условия . 3. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле , где – степень оптимизма (показатель пессимизма – оптимизма) изменяется в диапазоне [0, 1]. Критерий Гурвица придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При критерий превращается в критерий Вальда, а при – в критерий максимума. На оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем больше последствия ошибочных решений, больше желания застраховаться, тем ближе к единице. 4. Критерий Сэвиджа. Суть критерия состоит в выборе такой стратегии, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесёт человек(фирма), если для каждого состояния природы он не выберет наилучшей стратегии: . Элементы матрицы рисков находятся по формуле , где – максимальный элемент в столбце исходной матрицы. Оптимальная стратегия определяется выражением . При принятии решений в условиях неопределённости следует оценивать различные варианты с точки зрения нескольких критериев. Если рекомендации совпадают, можно с большей уверенностью выбрать наилучшее решение; если рекомендации противоречат друг другу, окончательное решение надо принимать с учётом результатов дополнительных исследований. Пример. В приближении посевного сезона фермер имеет четыре альтернативы: A1 - выращивать кукурузу, А2 – пшеницу, А3 – овощи или А4 – использовать землю под пастбища. Платежи, связанные с этими возможностями, зависят от количества осадков, которые условно можно разделить на четыре категории: : В1- сильные осадки , В2 - умеренные, В3 – незначительные, В4 – засушливый сезон. Платёжная матрица оценивается следующим образом: . Какое управленческое решение должен принять фермер? Решение. 1. Согласно критерию Вальда рекомендуется применять максиминную стратегию: . Следует использовать землю под пастбища. 2. Воспользуемся критерием Сэвиджа. Составим матрицу рисков, элементы которой находим по формуле : . Оптимальная стратегия определяется выражением . В соответствии с этим критерием следует сеять пшеницу. 3. Воспользуемся критерием Гурвица. Оптимальная стратегия определяется по формуле Предположим, что степень оптимизма . Тогда Т.е. следует принять решение о выращивании овощей. 4. Если допустить, что известно распределение вероятностей для различных состояний природы, например эти состояния равновероятны (), то для принятия решения следует найти математические ожидания выигрыша: Так как максимальное значение имеет , то следует сеять пшеницу. Таблица Решения, принятые в зависимости от используемого критерия Решение Критерий Число решений, принятых по разным критериям Вальда Гурвица Сэвиджа МО выигрыша A1 - A2 х х 2 A3 х 1 A4 х 1 Из таблицы видно, что оптимальное поведение во многом зависит от принятого критерия выбора наилучшего решения, поэтому выбор критерия является наименее простым и наиболее ответственным вопросом в исследовании операций. 5.2. Экспертные методы принятия решений Неполная формализация управленческих процессов, недостаточная полнота и достоверность их информационного обеспечения часто не позволяют применять для принятия решения строгие математические методы. В этих условиях при выработке решений в зависимости от конкретной управленческой ситуации прибегают к методам экспертных оценок. Для широкого круга не формализуемых задач экспертные процедуры являются эффективным, а в ряде случаев и единственным средством их решения. Можно привести многочисленные примеры применения экспертных оценок для решения задач прогнозирования, планирования, оперативного управления контроля. Сущность метода экспертных оценок заключается в проведении квалифицированными специалистами-экспертами интуитивно-логического анализа проблемы с количественной оценкой суждений и формальной обработкой результатов. Получаемое в результате обработки обобщённое мнение принимается как решение проблемы. Задача экспертного оценивания состоит, как правило, в получении группового объективного мнения на основе некоторой совокупности индивидуальных субъективных мнений экспертов. В общем виде блок-схема процедуры формирования групповых экспертных оценок имеет вид, представленный на рисунке 5.1. Рисунок 5.1. Блок-схема процедуры формирования групповых экспертных оценок Одним из наиболее эффективных методов экспертных оценок является метод Дельфи (рисунок 5.2). Метод Дельфи Рисунок 5.2. Блок-схема метода Дельфи Особенности метода Дельфи • полный отказ от личных контактов экспертов и от коллективных обсуждений, • многотуровая процедура опроса экспертов, • обеспечение экспертов информацией, включая и обмен информацией между ними, после каждого тура опроса при сохранении анонимности оценок, аргументации и критики, • обоснование ответов экспертов по запросу координатора. Метод Дельфи имеет ряд недостатков • уровень компетентности участников может оказаться недостаточным; • сохранение анонимности снижает надёжность информации и ответственность участников опроса; • возможно ложное согласие участников опроса из-за неоднозначности толкования вопросов. Несмотря на это, метод Дельфи – одна из наиболее перспективных форм проведения экспертного оценивания. Пример. Десять экспертов оценили прогнозные значения экономического показателя: Эксперт 1 2 3 4 5 6 7 8 9 10 Прогноз 16,9 13,8 11,9 12,3 16,3 12,0 16,1 20,6 16,8 13,1 Требуется методом Дельфи найти точечный и интервальный прогнозы. Решение. Расположив результаты оценок в порядке возрастания, получим следующий ряд: 11,9 12,0 12,3 13,1 13,8 16,1 16,3 16,8 16,9 20,6 В качестве точечного прогноза принимают медиану полученного ряда. Медиана – это среднее, полученное путём выявления «центрального» значения в перечне данных, расположенных в ранжированном порядке (иначе говоря, медиана – это значение признака у средней единицы ранжированного ряда). В общем виде при наличии п значений медиана отвечает [(n+1)/2] – порядковому номеру. В последовательности из 10 данных значений медиана будет отвечать [(10+1)/2]=[5,5] – му порядковому номеру (т.е. номеру, который находится посередине между 5-м и 6-м значениями). Таким образом, медиана равна 13,8+ (16,1 – 13,8)/2 =14,95. При интервальном прогнозе в качестве нижней и верхней границ доверительного интервала принимают значения первого и третьего квартиля соответственно (при межквартильном размахе доверительная вероятность прогноза 50%). Определим значения первого и третьего квартиля: • нижний (первый) квартиль значение признака у единицы ранжированного ряда, делящей совокупность в соотношении ([(n+1)/4]- е порядковое значение): • верхний (или третий) квартиль - значение признака у единицы ранжированного ряда, делящей совокупность в соотношении ([3(n+1)/4]- е порядковое значение): Межквартильный размах включает 50% центральных значений. Второй квартиль есть не что иное, как медиана. При этом и межквартильный размах . Метод статистической обработки результатов экспертных оценок При статистической обработке результатов экспертных оценок (значение прогнозируемой величины, данное i-м экспертом, i=1,2,…,п) в качестве точечной оценки принимают среднее значение прогнозируемой величины: Далее определяется дисперсия D и оценка ∆ для доверительного интервала: , , где t- коэффициент Стьюдента для заданного уровня доверительной вероятности р и числа степеней свободы п-2. Доверительные границы для значения прогнозируемой величины (верхняя и нижняя границы) вычисляются по формуле . Пример. Десять экспертов оценили прогнозные значения экономического показателя. Методом статистической обработки результатов экспертизы найти точечный и интервальный прогнозы (). Результаты экспертного опроса Эксперт 1 2 3 4 1 21,3 1,31 1,72 2 19,2 -0,79 0,62 3 17,9 -2,09 4,37 4 18,2 -1,79 3,20 5 20,9 0,91 0,83 6 18,0 -1,99 3,96 7 20,7 0,71 0,50 8 23,7 3,71 13,76 9 21,2 1,21 1,46 10 18,8 -1,19 1,42 Сумма 199,9 - 31,85 Решение. В качестве точечной оценки принимают средне значение прогнозируемой величины: . Для нахождения дисперсии D и оценки ∆ для доверительного интервала используются графы 3 и 4 таблицы (t = СТЬЮДРАСПРОБР(0,4; 8)=0,88): , Верхняя граница доверительного интервала нижняя граница . При коллективном способе экспертной оценки результаты экспертизы можно считать достоверными лишь в том случае. Если будет достигнута достаточная степень согласия между участвующими в экспертизе экспертами. Поэтому необходимо выбрать меру, с помощью которой мы имели бы возможность измерять степень согласия между экспертами, а также оценивать приемлемость степени согласия. Мерой близости ранжировок двух экспертов может служить коэффициент ранговой корреляции. При практических расчётах корреляционной зависимости ранжировок предпочтительнее использовать удобную для расчётов формулу коэффициентов ранговой корреляции Спирмена : , , где т – количество ранжируемых элементов; - ранг, полученный j –м элементов соответственно от первого и второго эксперта. Значение коэффициента ρ может изменяться в пределах от -1 до +1: • если , мнения экспертов относительно важности элементов полностью совпадают; • если , мнения экспертов полностью противоположны. Пример. Два эксперта провели ранжирование шести экономических признаков. Результаты ранжирования Эксперт Ранг элемента Х1 Х2 Х3 Х4 Х5 Х6 Первый 1 2 3 4 5 6 Второй 2 3 1 4 6 5 d -1 -1 2 -1 1 d2 1 1 4 1 1 R(d2) 8 Оценить степень согласованности двух экспертов. Решение. Рассчитаем коэффициент ранговой корреляции Спирмена: Таким образом, существует достаточно сильная положительная корреляция между ранжировками двух экспертов. Для оценки степени согласованности мнений N экспертов используются специальные показатели, называемые коэффициентами конкордации (согласованности). Предположим, что каждый эксперт ранжирует (упорядочивает) т элементов по убыванию их важности. Первый член ранжировки получает 1-й ранг; последний – ранг, равный т (прямое ранжирование). Наиболее известным является коэффициент конкордации Кендалла: , где . Коэффициент конкордации Кендалла меняется в пределах от 0 (в случае наименьшей согласованности мнений нескольких экспертов) до 1 (в случае абсолютной согласованности). Величина N (m -1)W имеет распределение χ2 с ν = т – 1 степенями свободы. Для признания значимости коэффициента конкордации необходимо и достаточно, чтобы найденное N (m -1)W было больше табличного χ2 , определяемого числом степеней свободы и уровнем значимости α (вероятностью ошибки). Таким образом, задавшись уровнем значимости и числом степеней свободы, можно получит в Excel с помощью функции =ХИ2ОБР табличное значение χ2 и оценить значимость вычисленного по формуле коэффициента конкордации W . Чаще всего в подобных расчётах уровень значимости задаётся равным 0,05 или 0,01. Пример. Десять экспертов ранжировали по значимости следующие четыре показателя, характеризующие эффективность инвестиционных проектов: Х1- объём инвестиций; Х2 – срок окупаемости; Х3 – чистый дисконтированный доход; Х4 – рентабельность инвестиций. Эксперт Ранг показателя Э1 4 2 1 3 Э2 3 1 2 4 Э3 1 2 3 4 Э4 3 1 2 4 Э5 3 2 4 1 Э6 3 4 1 2 Э7 3 1 2 4 Э8 2 1 3 4 Э9 2 4 1 3 Э10 3 2 1 4 27 20 20 33 2 -5 -5 8 4 25 25 64 118 Оценить степень согласованности этих экспертов Решение. Определим коэффициент конкордации W при . Для вычисления рассчитаем предварительно суммы рангов показателей с помощью функции СУММ, затем используем функцию СУММКВРАЗН, где в качестве первого массива выступают вычисленные суммы, а второй массив состоит из одинаковых чисел . Получим . Окончательно: Получим расчётное значение по формуле χ2 = 10·3·0,24 = 7,2. При уровне значимости α = 0,05 для ν = т – 1 = 3 степеней свободы находим табличное значение χ2 с помощью функции =ХИ2ОБР (Мастер функций Excel/категория Статистические): χ2набл = ХИ2ОБР(0,05; 3) = 7,8 Так как χ2< χ2табл , то степень согласованности экспертов W = 0,24 не только мала, но и незначима. К обобщению мнений экспертов можно приступить лишь при достаточно высокой статистически значимой согласованности мнений членов экспертной группы. При обобщении мнений экспертов чаще всего на практике используется метод «сумм рангов». Данный метод заключается в суммировании рангов по элементам, выставленных каждым экспертом, и определении групповой (обобщенной) ранжировки на основе суммарных рангов. В приведённом выше примере обобщенная группировка может быть представлена (прямое ранжирование): . Знак «>» надо понимать, как «предпочтительнее, важнее», а знак «=» - «одинаково, равносильно». Определение групповых ранжировок при использовании других способов выражения предпочтений экспертов также основано на осреднении соответствующих оценок (балльных, непосредственно числовых) и построении на основе средних результатов обобщенной ранжировки. В результате обобщения объективных данных и информации, получаемой от экспертов, а также собственных предпочтений ЛПР выбирает наилучшую альтернативу. Литература 1. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие. – М.: Вузовский учебник, 2011. 2. Федосеев В.В., Гармаш А.Н., Орлова И.В., Половников В.А. Экономико-математические методы и прикладные модели: учебное пособие для вузов, -3-е издание, М.: Юрайт-издат: Высшее образование, 2011. 3. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: учебное пособие.- М.: ВЗФЭИ: Вузовский учебник, 20011. Оглавление Тема 1. Введение в дисциплину. Общее представление о задаче оптимизации……………………………………………………………..3 Тема 2. Линейное программирование………………………………...11 Тема 3. Нелинейное программирование………………………44 Тема 4. Оптимальные решения для отдельных классов задач оптимизации в экономике……………………………………..............50 Тема 5. Методы оптимальных решений в условиях неопределенности……………………………………………………...92 Литература…………………………………………………………….111