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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ» __________________________________________________________________ Тульский филиал Кафедра математики и информатики Конспект лекций по дисциплине «Методы оптимальных решений» для студентов, обучающимся по направлению 080100.62 «Экономика» Квалификация (степень) бакалавр Составил: к.ф.-м.н., доцент кафедры математики и информатики Луценко Алексей Георгиевич Рассмотрено и одобрено на заседании кафедры кафедры математики и информатики протокол № ___ от «___»____________ 2013 г. Тема 1:  Введение в дисциплину. Общее представление о задаче оптимизации 1. Математические методы и модели в экономике. Основные понятия и общая классификация. Иллюстрация на конкретных примерах Определение 1. Математическая модель в экономике или экономико-математическая модель (ЭММ) – математическое описание исследуемого экономического процесса. Эта модель выражает закономерности экономического процесса с помощью математических соотношений. Единой классификации ЭММ к настоящему времени не выработано. В общем виде ЭММ разделяют следующим образом: • макроэкономические и микроэкономические модели; • прескриптивные (нормативные) и дескриптивные (аналитические) модели; • статические (в один период времени) и динамические (в развитии) модели; • детерминированные (заданные величины) и стохастические (случайные величины и процессы) модели. По предназначению ЭММ различают следующим образом: • оптимизационные модели; • балансовые модели; • трендовые модели; • имитационные модели и т.д. По математическому аппарату ЭММ различают следующим образом: • модели массового обслуживания; • модели теории игр; • регрессионные модели и т.д. Определение 2. Математические методы в экономике или экономико-математические методы – это методы разработки, исследования и принятий решений по экономико-математическим моделям. Общепринятой классификации этих методов также не существует. Можно выделить следующие группы методов: • методы математической статистики (выборочный метод, методы корреляционно-регрессионного анализа, методы дисперсионного анализа, методы факторного анализа и др.); • методы эконометрики (методы анализа временных рядов, методы разработки моделей парной и множественной регрессии, системы одновременных уравнений); • методы исследования операций (оптимальное программирование, теория массового обслуживания, теория игр и др.); • методы финансовой математики (процентные вычисления, потоки платежей, анализ инвестиционных проектов и лизинговых операций, портфельные инвестиции и др.); • методы экспериментального изучения экономических явлений (имитационное моделирование, деловые игры, экспертные оценки и др.) и т.д. В процессе решения экономических задач с применением математических методов можно выделить следующие основные этапы: 1) постановка экономической проблемы (задачи); 2) моделирование (разработка ЭММ и оценка адекватности этой модели); 3) получение решения (реализация ЭММ); 4) внедрение полученного решения (разработка рекомендаций, предложений в наглядном и доступном виде). 2. Принцип оптимальности в планировании и управлении, математическая запись. Примеры применения для принятия оптимальных решений Определение 1. Принцип оптимальности – выбор такого управленческого решения , где – его компоненты, которое наилучшим образом учитывает внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта. Математическая запись принципа оптимальности в общем случае имеет вид: , где: D – область возможных (допустимых) решений; f(X) – целевая функция. Критерий оптимальности должен быть выражен количественно и соответствовать общей цели деятельности рассматриваемой системы. Традиционные критерии оптимальности – «максимум прибыли», «минимум затрат» и т.д. 3. Задача оптимального программирования, основные понятия и определения, общая классификация. Примеры практических приложений Определение 1. Задача оптимального программирования имеет вид: Найти максимум или минимум функции (3.1) при ограничениях (3.2) (3.3) f(X) – целевая функция (ЦФ), зависящая от вектора X; Обозначение говорит о том, что в каждом конкретном ограничении возможен один из этих знаков. Ограничения (3.1) называются функциональными ограничениями, а (3.2) – прямыми ограничениями. Более компактно: (3.4) (3.5) (3.6) Вектор X называется допустимым решением (допустимым планом задачи оптимального программирования), если его компоненты удовлетворяют системе ограничений (3.4) и (3.5). План называется оптимальным планом задачи оптимального программирования, если . Определение 2. Решить задачу оптимального программирования – это значит: 1) найти оптимальный план ; 2) найти оптимальное значение . Задачи оптимального программирования классифицируют по следующим признакам: • линейные и нелинейные задачи (по характеру связей между переменными); • непрерывные и дискретные задачи (по характеру изменения переменных); • статические и динамические задачи (по учету фактора времени); • однокритериальные и многокритериальные задачи (по числу критериев оценки альтернатив); • задачи в условиях полной определенности, в условиях неполной информации (случай риска) и в условиях неопределенности (по наличию информации о переменных). 4. Классическая задача оптимизации, решение методом множителей Лагранжа Если в задаче оптимизации отсутствует условие неотрицательности переменных, а функциональные ограничения имеют вид равенств, то такую задачу называют классической задачей оптимизации: (4.1) . (4.2) Если все функции , непрерывны вместе с частными производными первого порядка, то для решения задачи оптимизации можно применить классический метод множителей Лагранжа. Алгоритм: 1. Сначала составляют функцию Лагранжа: . (4.3) 2. Далее вычисляют для функции (4.3) частные производные первого порядка по всем переменным и , приравнивают их нулю и получают систему уравнений: (4.4) 3. Если удается найти все решения системы (4.4), то для определения глобального максимума или минимума достаточно найти значения функции в соответствующих точках области определения задачи и выбрать наибольшее или наименьшее значение функции. Замечание. Теоретической основой метода является следующее утверждение: если функция f(X) в точке имеет экстремум, то существует вектор такой, что точка является решением системы уравнений (4.4). 5. Типовые задачи оптимизации и их экономико-математические модели Задача об использовании ограниченных ресурсов.  Задача о размещении производственных заказов.  Задача о раскрое строительных материалов [1, с.30-31, 33-35].  Задача о смесях [1, с.37-38].  Задача об инвестициях [1, с.41-42, 45].  Задача о «ранце».  Задача о «рационе».  Задача о распределении рекламного бюджета.  Тема 2:  Линейное программирование 6. Задача линейного программирования (ЗЛП). Основные свойства, понятия и определения, примеры практического использования Наиболее изученными задачами оптимизации являются задачи линейного программирования (ЗЛП), для которых разработан универсальный метод решения – симплекс-метод (метод последовательного улучшения плана). Определение 1. Задача линейного программирования имеет вид: Найти максимум или минимум линейной функции (6.1) при линейных ограничениях (6.2) (6.3) где , – заданные постоянные величины. Вектор называется допустимым решением (допустимым планом) ЗЛП, если его компоненты удовлетворяют системе ограничений (6.2) и (6.3). План называется оптимальным планом (оптимальным решением) ЗЛП, если , т.е. допустимый план, который дает максимум или минимум целевой функции. Определение 2. Канонической формой записи ЗЛП называется задача вида: (6.4) , (6.5) , (6.6) . (6.7) где , , – заданные постоянные величины. Любую ЗЛП можно привести к каноническому виду (КЗЛП). Чтобы неравенства обратились в равенства достаточно: • в левую часть каждого неравенства со знаком ≤ ввести добавочную переменную со знаком –; • в левую часть каждого неравенства со знаком  ввести добавочную переменную со знаком +. 7. Графический метод решения ЗЛП, особые случаи решения ЗЛП графическим методом Для выработки наглядных представлений о ЗЛП рассмотрим графический метод, который может быть применен в случае решения ЗЛП с двумя переменными: (7.1) , (7.2) (7.3) где , – заданные постоянные величины. Геометрически ЗЛП представляет собой отыскание в многоугольнике решений такой угловой точки, координаты которой дают максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений. Алгоритм решения ЗЛП с двумя переменными графическим методом 1. Построить область допустимых решений (ОДР) ЗЛП. 2. Построить вектор-градиент целевой функции , перпендикулярно ему провести прямую (линию уровня). 3. Перемещать линию уровня в направлении вектора-градиента при решении задачи на max, в обратном направлении – при решении задачи на min. 4. Последняя точка области при этом движении и является точкой оптимального решения. Особые случаи решения ЗЛП графическим методом Возможны следующие особые случаи: 1. Линия уровня параллельна некоторой стороне многоугольника (ОДР). В этом случае каждая угловая точка этой стороны многоугольника и любая точка между ними является оптимальным решением ЗЛП (бесконечное множество решений). 2. ОДР является неограниченной, целевая функция на ОДР не ограничена сверху (задача на max не имеет решения). 3. Система ограничений несовместима, ОДР есть пустое множество (ЗЛП не имеет решения). 8. Основы симплексного метода решения ЗЛП: идеология и общая схема метода. Получение оптимальных решений средствами MS Excel Сначала кратко напомним некоторые математические понятия и факты. Теорема 1. Если функция непрерывна на замкнутом ограниченном множестве конечномерного евклидова пространства, то она ограничена на нем и достигает наименьшего и наибольшего значений. Определение 1. Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные n-m переменных называются неосновными (свободными). Определение 2. Базисным решением системы m линейных уравнений с n переменными (m < n) называется всякое её решение, в котором неосновные переменные имеют нулевое значение. Определение 3. Решение системы m линейных уравнений с n переменными (m < n) называется допустимым, если в нём все основные переменные неотрицательны. Теорема. Существует взаимнооднозначное соответствие между угловыми точками множества допустимых решений системы m линейных уравнений с n переменными (m < n) и её допустимыми базисными решениями. Сначала необходимо ЗЛП привести к каноническому виду (КЗЛП). Доказано, что оптимальное решение ЗЛП (если оно существует и притом единственное) совпадает с одним из допустимых базисных решений системы ограничений, следовательно, с угловой точкой многогранника решений. Однако для реальных задач число допустимых базисных решений может быть очень велико и провести перебор всех угловых точек многогранника затруднительно. Этот перебор можно сократить, используя идею симплексного метода (метод предложен в 1949 г. американским ученым Дж. Данцигом). Для реализации симплекс-метода – метода последовательного улучшения плана – необходимо знать три основные операции: 1) способ определения какого-либо первоначального допустимого базисного решения; 2) алгоритм перехода от одного допустимого базисного решения к другому; 3) критерий проверки оптимальности решения. Замечание. Если первоначальное базисное решение недопустимо, то удобно использовать симплекс-метод с искусственным базисом. 9. Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана Рассмотрим основные понятия и выводы специального раздела линейного программирования — теории двойственности. С каждой задачей линейного программирования определенным образом тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой. Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП. Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой задачи. Однако при определении симплексным методом оптимального плана одной из задач находится решение и другой задачи. Правило построения двойственной задачи по отношению к исходной задаче определяется системой соотношений: Исходная задача Двойственная задача Двойственная задача составляется согласно следующим правилам: 1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи — на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид «», а в задаче на минимум — «». 2) матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием; 3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи; число ограничений двойственной задачи равно числу переменных в исходной задаче; 4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи; 5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства «», соответствует переменная, связанная условием неотрицательности. Основные утверждения о двойственных задачах содержатся в двух следующих теоремах Теорема 1 (основная теорема двойственности). Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значения целевых функций задач равны: . Если одна из двойственных задач неразрешима, то неразрешима и другая. Теорема 2 (о дополняющей нежесткости). Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю. Если i-я компонента оптимального плана двойственной задачи положительна, то i-е ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство. То есть для оптимальных планов двойственных задач имеют место соотношения: , которые позволяют, зная оптимальное решение одной из двойственных задач, найти оптимальное решение другой задачи. Экономический смысл задачи, двойственной к задаче оптимального использования ресурсов Составим экономико-математическую модель задачи оптимального использования ресурсов на максимум прибыли. Теперь сформулируем двойственную задачу. Пусть некая организация решила закупить все ресурсы рассматриваемого предприятия. При этом необходимо установить оптимальную цену на приобретаемые ресурсы у1, у2, y3, … сходя из следующих объективных условий: — покупающая организация старается минимизировать общую стоимость ресурсов; — за каждый вид ресурсов надо уплатить не менее той суммы, которую хозяйство может выручить при переработке сырья в готовую продукцию. Оптимальные значения переменных двойственной задачи называют двойственными оценками (теневыми ценами, объективно обусловленными оценками). Экономический смысл первой теоремы двойственности можно интерпретировать так: предприятию безразлично, производить ли продукцию по оптимальному плану X и получить максимальную прибыль либо продать ресурсы по оптимальным ценам Y и возместить от продажи равные ей минимальные затраты на ресурсы. Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок. В пределах устойчивости двойственных оценок (для определения этих границ существуют математические соотношения, которые реализованы в «Отчете по устойчивости» Excel) имеют место следующие свойства. 1. Величина двойственной оценки того или иного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу (двойственные оценки измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи). Сказанное позволяет выявить направления «расшивки» узких мест, обеспечивающие получение наибольшего экономического эффекта, а также целесообразность изменения в структуре выпуска продукции с позиций общего оптимума. 2. Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны). 3. Двойственные оценки позволяют определять своеобразные «нормы заменяемости ресурсов»: имеется в виду не абсолютная заменяемость ресурсов, а относительная; т.е. заменяемость с точки зрения конечного эффекта и лишь в конкретных условиях данной задачи. 4. Двойственные оценки служат инструментом определения эффективности отдельных хозяйственных решений (технологических способов), с их помощью можно определять выгодность производства новых изделий, эффективность новых технологических способов: если — выгодно, если — невыгодно. Двойственные оценки как мера влияния ограничений на целевую функцию Теорема об оценках. Значения переменных yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений (неравенств прямой задачи) на величину : . Решая ЗЛП симплексным методом, мы одновременно решаем двойственную задачу. Значения переменных двойственной задачи yi в оптимальном плане называют, как выше уже отмечено, объективно обусловленными, или двойственными оценками. Из теоремы об оценках известно, что колебание величины bi приводит к увеличению или уменьшению . Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных yi в оптимальном плане соответствующей двойственной задачи остаются неизменными. Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, в которых оптимальный план двойственной задачи не менялся бы. Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивность этих векторов (значения неизвестных) в плане могут меняться. 10. Специальные задачи линейного программирования: транспортная задача, решение средствами MS Excel Транспортная задача является одной из наиболее распространенных задач линейного программирования и находит широкое практическое приложение. Постановка задачи (об оптимальном закреплении потребителей к поставщикам). Некоторый однородный продукт, сосредоточенный у m производителей (поставщиков) Ai в количестве ai единиц, необходимо доставить n потребителям Bj в количестве bj единиц. Известна стоимость cij перевозки единицы груза от поставщика i к потребителю j. Необходимо составить план перевозок, позволяющий с минимальными затратами перевезти все грузы и полностью удовлетворить потребителей. Часто исходные данные транспортной задачи записывают в виде таблицы (матрицы) планирования: Потребитель Производитель B1 B2  Bn Предложение (запасы) A1 c11 c12  c1n a1 A2 c21 c22  c2n a2       Am cm1 cm2  cmn am Потребность (спрос) b1 b2  bn Составим экономико-математическую модель (транспортная задача относится к двухиндексным задачам линейного программирования): 1) вводим переменные: , где xij – количество единиц груза, перевозимых от поставщика i к потребителю j ; стоимость этой перевозки составит ; 2) задаем целевую функцию , которая выражает стоимость перевозок всех грузов; 3) из условий задачи составляем ограничения: a) все грузы должны быть перевезены, т.е. ; b) все потребности должны быть удовлетворены, т.е. . Таким образом, модель транспортной задачи имеет следующий вид: Найти минимальное значение целевой функции (10.1) при ограничениях , (10.2) , (10.3) , , . (10.4) В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е. . (10.5) Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой транспортной задачей, в противном случае получаем открытую транспортную задачу. Замечание. Решение открытой ТЗ проводится сведением к закрытой ТЗ (введением фиктивного поставщика или фиктивного потребителя): a) если суммарные запасы превышают суммарные потребности, то вводится фиктивный потребитель Bn+1, потребность которого равна ; b) если суммарные потребности превышают суммарные запасы, то вводится фиктивный поставщик Am+1, запасы которого равны . Стоимость перевозки единицы груза до фиктивного потребителя или от фиктивного поставщика приравнивается нулю, так как груз в обоих случаях фактически не перевозится. 11. Специальные задачи линейного программирования: задача о назначениях, решение средствами MS Excel Задача о назначениях является частным случаем транспортной задачи, в котором все значения ai и bj равны 1. Такая задача возникает при распределении людей на должности или работы, водителей на машины, рабочих на станки, автомашин на маршруты, групп по аудиториям и т.п. Постановка задачи (об оптимальном закреплении исполнителей на работы). Имеется n видов работ и n исполнителей этих работ. Известна эффективность cij выполнения исполнителем i работы j. Требуется так назначить исполнителей по видам работ, чтобы суммарный эффект от назначений был максимальным. Часто исходные данные задачи о назначениях записывают в виде таблицы (матрицы) планирования: Работы Исполнители B1 B2  Bn Число исполнителей A1 c11 c12  c1n 1 A2 c21 c22  c2n 1       An cn1 cn2  cnn 1 Количество работ 1 1  1 Составим экономико-математическую модель (задача о назначениях относится к двухиндексным задачам линейного программирования): 1) вводим переменные: , где 2) задаем целевую функцию , которая выражает суммарный эффект от назначений; 3) из условий задачи составляем ограничения: a) каждый исполнитель должен быть назначен на работу, т.е. ; b) на каждую работу должен быть назначен исполнитель, т.е. . Таким образом, модель задачи о назначениях имеет следующий вид: Найти минимальное значение целевой функции (11.1) при ограничениях , (11.2) , (11.3) , , . (11.4) Замечание. Если число исполнителей m не равно числу работ n (т.е. задача является открытой), то возможно применение двух способов: 1) решение открытой задачи о назначениях сводим к решению закрытой задачи о назначениях; для этого вводим фиктивных исполнителей или фиктивные виды работ; 2) изменяем ограничения 11.2 и 11.3: a) если число исполнителей m больше числа работ n, то ; ; b) если число исполнителей m меньше числа работ n, то ; . Решение средствами MS Excel При решении задачи о назначениях необходимо учитывать, что переменные принимают значения «0» или «1». Поэтому при заполнении диалоговова окна Поиск решения в поле Ограничения необходимо ввести требование двоичности (бинарности в MS Office 2010) изменяемых переменных: 12. Задачи дискретной оптимизации, решение средствами MS Excel Задачи оптимизации, в которых переменные должны быть целыми числами, называются задачами целочисленного (дискретного) программирования: Найти максимальное (минимальное) значение целевой функции (12.1) при ограничениях (10.2) целые неотрицательные числа,. (10.3) Для получения целочисленных решений применяются специальные методы: • методы отсечения; • методы дерева решений; • эвристические (приближенные) методы. Решение средствами MS Excel Дискретная оптимизация проводится аналогично решению непрерывной задачи. Отличие состоит в том, что при заполнении диалоговова окна Поиск решения в поле Ограничения необходимо ввести требование целочисленности изменяемых переменных: Тема 3:  Нелинейное программирование 13. Задачи нелинейного программирования, решение средствами Excel Задача оптимального программирования, в которой целевая функция и (или) хотя бы одна из функций является нелинейной функцией, называется задачей нелинейного программирования (ЗНЛП): Найти максимальное (минимальное) значение целевой функции (13.1) при ограничениях (13.2) , . (13.3) Не существует универсального метода решения НЗЛП. Наиболее простыми ЗНЛП являются задачи с линейными ограничениями и нелинейной целевой функцией: Найти максимальное (минимальное) значение целевой функции (13.4) при ограничениях (13.5) , . (13.6) Чтобы гарантировать возможность нахождения оптимального решения и в этом случае на функцию должны быть наложены дополнительные условия (например, вогнутость или выпуклость функции). Решение средствами MS Excel При решении ЗНЛП в диалоговом окне Поиск решения во вкладке Параметры должна быть отключена опция Линейная модель. 14. Метод динамического программирования Для решения некоторых типов задач оптимального программирования используется метод динамического программирования (ДП). В основе общей концепции метода ДП лежит принцип оптимальности Беллмана: Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения. Благодаря принципу оптимальности удается при последующих переходах испытывать не все возможные варианты, а лишь оптимальные выходы. Для решения задач методом динамического программирования не предлагается подходящих программных средств – разобраться в сути принцип оптимальности Беллмана следует с карандашом в руке [1, с.96-102]. Тема 4:  Оптимальные решения для отдельных классов задач оптимизации в экономике 15. Методы теории массового обслуживания: основные понятия и определения, примеры СМО При решении многих задач оптимальной организации торговли, бытового обслуживания, складского хозяйства и т.п. часто используется интерпретация производственной структуры как системы массового обслуживания (СМО), т.е.системы в которой с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой стороны происходит постоянное удовлетворение этих запросов. Всякая СМО включает 4 элемента: 1) источник требований (ИТ); 2) входящий поток требований; 3) система обслуживания, которая включает в себя: ◦ очередь, ◦ обслуживающее устройство (каналы обслуживания); 4) выходящий поток требований. Требованием называется каждый отдельный запрос на выполнение какой-либо работы. Поступив в обслуживающую систему, требование (заявка) на обслуживание присоединяется к очереди других ранее поступивших требований и ждет обслуживания. Блок обслуживания выбирает очередное требование и начинает его обслуживать. После завершения обслуживания обслуживающая система приступает к обслуживанию следующего требования. Этот цикл работы СМО многократно повторяется. К основным характеристикам СМО относятся: • среднее число заявок находящихся в системе; • среднее число заявок в очереди (ее длина); • средняя продолжительность пребывания клиента в системе; • средняя продолжительность пребывания клиента в очереди; • среднее количество занятых средств обслуживания; • среднее время обслуживания; • вероятность отказа в обслуживании и др. Для классификации СМО используется ряд признаков: 1. В зависимости от условий ожидания начала обслуживания различают: ▪ СМО с отказами (потерями) – требования получившие отказ (каналы заняты) теряются; ▪ СМО с ожиданием - требования становятся в очередь и ожидают обслуживания, такие СМО делятся на: • СМО с ограниченной длиной очереди; • СМО с неограниченной длиной очереди; • СМО с ограниченным временем ожидания. 2. По числу каналов обслуживания различают два вида СМО: ▪ одноканальные; ▪ многоканальные. 3. По месту нахождения источника требования (ИТ) СМО делятся на два вида: ▪ разомкнутые – ИТ вне системы; ▪ замкнутые – ИТ в составе системы. 4. По дисциплине обслуживания (в зависимости от порядка выбора заявок на обслуживание) выделяют: ▪ СМО с приоритетом – вначале обслуживаются заявки с более высоким приоритетом; ▪ СМО без приоритета – приоритет в обслуживании заявок отсутствует. Методы и модели исследования СМО можно разделить на ▪ аналитические; ▪ статистические. Аналитические методы позволяют получить характеристики СМО как функции её параметров, но применимы эти методы к ограниченному кругу задач теории массового обслуживания (ТМО). Простейший поток требований В настоящее время достаточно хорошо разработана ТМО применительно к простейшему (Пуассоновскому) потоку заявок на обслуживание. Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается формулой , где λ – параметр потока (число требований, поступающих в единицу времени). Основные свойства простейшего потока: Ординарность – практическая невозможность одновременного поступления двух и более требований. Стационарность – означает, что среднее число требований (математическое ожидание) поступающих в систему в ед. времени (λ=const) не меняется во времени. Отсутствие последействия – число требований, поступивших в систему до момента времени t не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Δt. Время обслуживания требований в системе Важной характеристикой СМО является время обслуживания одного требования в системе. Оно является случайной величиной и может быть описано законом распределения. Наиболее часто рассматривается как случайная величина (СВ), которая подчиняется экспоненциальному закону распределения. Для этого закона функция распределения вероятности имеет вид: , т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, определяется формулой , где μ – параметр экспоненциального закона распределения времени обслуживания требований в системе – т.е. величина, обратная среднему времени обслуживания одного требования , т.е. . 16. Система массового обслуживания с отказами, основные характеристики функционирования Рассмотрим многоканальную СМО с отказами, т.е. в системе имеется n каналов, в которые поступает простейший поток заявок с интенсивностью . Требование, поступившее в момент, когда все каналы заняты, получает отказ на обслуживание. Это одна из первых задач ТМО, она возникла при изучении работы телефонной станции и была решена в начале XX века датским математиком Эрлангом [1, с.107-108]. 1. Вероятность отказа в обслуживании (средняя доля требований, получивших отказ) , где: • n – число каналов обслуживания; • – величина, обратная среднему времени обслуживания одного требования ; • – нагрузка на систему; • – вероятность того, что все каналы свободны. 2. Относительная пропускная способность B, т.е. вероятность того, что заявка будет обслужена . 3. Абсолютная пропускная способность A . 4. Среднее число занятых каналов M . 17. Система массового обслуживания с ожиданием, основные характеристики функционирования Рассмотрим аналитические модели СМО с ожиданием, т.е. требование, поступившее в момент, когда все обслуживающие каналы заняты, становится в очередь и ожидает, когда освободится один из каналов. Предположим также, что в систему поступает простейший поток заявок с интенсивностью ., а время обслуживания одного требования в системе является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром . Математический аппарат, используемый для расчета основных характеристик СМО (формулы Эрланга) зависит от того, является ли СМО замкнутой или разомкнутой. Расчет характеристик замкнутой СМО с ожиданием (в системе может быть не более m требований) [1, с.110-112]. 1. Вероятность того, что в системе находится k требований при условии, что их число не превышает числа обслуживающих аппаратов (каналов) n: где: • n – число каналов обслуживания; • m – наибольшее возможное число требований, находящихся в обслуживаемой системе одновременно; • λ – частота (интенсивность) поступления требований в систему от одного источника; •  – средняя продолжительность обслуживания одного требования; • ; •  – вероятность того, что все обслуживающие аппараты свободны. 2. Вероятность того, что в системе находится k требований при условии, что их число больше числа обслуживающих аппаратов: где . 3. Вероятность того, что все обслуживающие аппараты свободны, определяется из условия . Следовательно, . 4. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди): . 5. Коэффициент простоя требования в ожидании обслуживания: . 6. Вероятность того, что все обслуживающие аппараты заняты: . 7. Среднее число требований, находящихся в обслуживающей системе (обслуживаемых и ожидающих обслуживания): . 8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания: . 9. Среднее время простоя требования в очереди на обслуживание: . 10. Среднее число свободных обслуживающих аппаратов: . 11. Коэффициент простоя обслуживающих аппаратов: . 12. Вероятность того, что число требований, ожидающих обслуживания, больше некоторого числа B (вероятность того, что в очереди на обслуживание находится более B требований): . Расчет характеристик разомкнутой СМО с ожиданием (источник обладает бесконечным числом требований) [1, с.113-114]. 1. Для нормального функционирования системы необходимо соблюдение требования (в противном случае очередь неограниченно растет), где: • n – число каналов обслуживания; • λ – частота (интенсивность) поступления требований в систему; •  – средняя продолжительность обслуживания одного требования одним аппаратом. 2. Вероятность того, что в системе находится k требований при условии, что их число не превышает числа обслуживающих аппаратов: где: • ; •  – вероятность того, что все обслуживающие аппараты свободны. 3. Вероятность того, что в системе находится k требований при условии, что их число превышает число обслуживающих аппаратов: где: • ; 4. Вероятность того, что все обслуживающие аппараты свободны: . 5. Вероятность того, что обслуживающие аппараты заняты (вероятность отказа в немедленном обслуживании): . 6. Средняя длина очереди: . 7. Средняя продолжительность ожидания обслуживания (продолжительность простоя в очереди): . 8. Среднее число свободных аппаратов: . 9. Коэффициент простоя обслуживающего аппарата: . 18. Классическая модель управления запасами без дефицита Управление запасами (УЗ) – установление периодичности поставок, их объемов, регулярности и наилучших сроков выполнения. Рассматривают несколько основных систем регулирования запасов: • система с фиксированным размером заказа [1, с.123]; • система с фиксированной периодичностью заказа [1, с.124]; • система с двумя фиксированными уровнями или (s-S)-система [1, с.124]; • системы оптимального управления запасами [1, с.125] и т.д. Разработаны различные модели управления запасами: • детерминированные модели; • стохастические модели; • статические модели; • динамические модели. Простейшей моделью УЗ является классическая модель системы управления запасами наиболее экономичного размера партии (модель Уилсона). Это детерминированная модель, имеющая аналитическое решение. Она основана на выборе фиксированного размера заказываемой партии, которая минимизирует общие расходы на оформление заказа, доставку и хранение товара. Предполагается также, что выполнены следующие условия: • уровень запаса убывает равномерно от q до 0; • время поставки заказа является известной и постоянной величиной; • каждый заказ поставляется в виде одной партии; затраты s на оформление заказа и доставку товара не зависят от объема партии; • ежедневная стоимость h хранения единицы товара постоянна; • отсутствие запаса (дефицит) является недопустимым. Циклы изменения уровня запаса в модели Уилсона графически представлены на рис.18.1. Максимальное количество продукции, которая находится в запасе, совпадает с размером заказа q. Рис.18.1. График циклов изменения запасов в модели Уилсона (без дефицита) Входные параметры модели Уилсона 1) s – затраты на осуществление заказа, включающие оформление и доставку заказа и доставку товара (руб.); 2)  – время доставки заказа (ед.вр.); 3) h – ежедневная стоимость хранения единицы товара (руб./ ед.тов.*ед.вр.); 4)  – спрос на товар за временной промежуток T (ед.тов.). Выходные параметры модели Уилсона 1) q – размер заказа (ед.тов.); 2)  – период поставки, т.е. время между подачами заказа или между поставками (ед.вр.); 3)  – точка заказа, т.е. размер запаса на складе, при котором надо подавать заказ на доставку очередной партии (ед.тов.); 4)  – общие затраты на управление запасами (руб.). Несложно вывести следующие формулы [1, с.128-129]: 1. Оптимальный размер заказываемой партии . 2. Длительность цикла повторения заказа . 3. Общее число партий, заказанных за временной промежуток T . 4. Общая величина расходов . Замечание. Минимум расходов имеет место в том и только в том случае, когда стоимость заказа равна расходам на хранение товара. 19. Классическая модель управления запасами с допущением дефицита В некоторых случаях целесообразно ввести систему с плановым дефицитом, поскольку это приводит к уменьшению совокупных расходов на управление запасами. Цикл изменения уровня запаса в модели Уилсона с допущением дефицита графически представлен на рис.19.1. Рис.19.1. График цикла изменения запасов в модели Уилсона (с дефицитом) Входные параметры модели Уилсона 1) s – затраты на осуществление заказа, включающие оформление и доставку заказа и доставку товара (руб.); 2) d – потери из-за дефицита, т.е. потери от нехватки единицы товара в единицу времени (руб./ ед.тов.*ед.вр.); 3) h – ежедневная стоимость хранения единицы товара (руб./ ед.тов.*ед.вр.); 4)  – спрос на товар за временной промежуток T (ед.тов.); 5)  – интенсивность спроса (ед.тов./ед.вр.). Выходные параметры модели Уилсона 1) Q – уровень запаса в начале цикла движения запасов (ед.тов.); 2)  – период поставки, т.е. время между подачами заказа или между поставками (ед.вр.); 3)  – затраты на управление запасами в единицу времени (руб. /ед.вр.). Расчет параметров модели [1, с.129-130]: 1. Оптимальный размер заказываемой партии . 2. Длительность цикла повторения заказа . 3. Общая величина расходов . 20. Методы сетевого планирования и управления Методы сетевого планирования и управления (СПУ) разработаны для обеспечения процесса планирования и выполнения работы как математические методы построения моделей исследования операций. Методы СПУ основаны на моделировании процессов с помощью сетевых графиков и представляют собой совокупность расчётных методов, организационных и контрольных мероприятий по планированию и управлению комплекса работ. К ним относятся методы, предназначенные для работы с сетевой моделью по временным, ресурсным, стоимостным и другим параметрам работ. Система СПУ позволяет: • формировать календарный план реализации некоторого комплекса работ; • выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы; • осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ; • повышать эффективность управления в целом при четком распределении ответственности между руководителями разных уровней и исполнителями работ. Рассмотрим метод критического пути (или СРМ – Critical Path Method), который был разработан в конце 50-х годов в США, в 1956 г., М. Уолкером из фирмы "Дюпон" и Д. Келли из группы планирования капитального строительства фирмы "Ремингтон Рэнд". Они попытались использовать ЭВМ для составления планов-графиков крупных комплексов работ по модернизации заводов фирмы "Дюпон". Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графиком. При этом используются некоторые понятия, теоремы и обозначения теории графов (рис.20.1). Основные понятия сетевой модели: событие, работа, путь. Событие на графе отмечается кругом (с порядковым номером), является узловым пунктом сети. Работа на графе отмечается стрелкой, соединяющая два события. Первое событие – конец предыдущей работы и начало предстоящей (рассматриваемой), второе событие – это окончание рассматриваемой работы. Действительная работа со своим объёмом затраченного времени, затратами ресурсов или ожидание обозначается сплошной стрелкой. Фиктивная работа (зависимость) – это пунктирная стрелка. Стрелки указывают последовательность выполнения операций. Взаимосвязь кружков и стрелок является графическими символами сетевой модели, которые должны строиться по определенным правилам. Рис.20.1. Схема сетевого графика Начало стрелки показывает, с какого события данная работа начинается, а конец стрелки показывает, в каком событии она заканчивается. Работы имеют временные оценки, которые проставляются на стрелках. Событие считается свершившимся тогда, когда будет закончена самая длительная из всех входящих в него работ. Требуемые для выполнения работы размеры ресурсов указываются на стрелках в скобках. Путем в графе называется такая упорядоченная последовательность дуг (стрелок), что конец любой дуги (стрелки), кроме последней, совпадает с началом следующей дуги. Максимальный по продолжительности полный путь в сети называется критическим; работы, лежащие на этом пути, также называются критическими (на графике они отражаются двойными стрелками). Выявление критического пути позволяет установить работы (операции), определяющие ход выполнения проекта. Критические работы в ходе проектирования должны выполняться строго по графику. Именно длительность критического пути определяет наименьшую общую продолжительность работ по проекту в целом. При анализе сетевого графика ставятся следующие задачи: 1. Отыскание минимального времени выполнения всего проекта (критического времени). 2. Отыскание тех операций, которые существенно влияют на критическое время; их совокупность образует так называемый критический путь. 21. Методы статистического моделирования (метод Монте-Карло), получение псевдослучайных чисел Производственные процессы в экономических системах настолько сложны и многообразны, что аналитические методы и модели исследования часто не могут успешно применяться при принятии решений. В этих случаях нередко используется имитационное моделирование, которое состоит в компьютерном моделировании реальной производственной ситуации. С другой стороны проведение расчетов на имитационных моделях требует значительных затрат времени исследователей, программистов и средств вычислительной техники. В основе имитационного моделирования, применяемого в условиях риска, лежит метод статистического моделирования (метод Монте-Карло), позволяющий воспроизводить на компьютере случайные величины с заданными законами распределения. В связи с тем, что реализации этих случайных величин получены искусственно, их называют псевдослучайными числами. Важную роль при применении метода Монте-Карло играет равномерный закон распределения, с помощью которого можно получить любое другое распределение. В MS Excel используется функция СЛЧИС(), которая возвращает случайное число от 0 до 1, равномерно распределенное на [0, 1]. Напомним, что случайная величина X имеет равномерный закон распределения на отрезке [a, b], если её плотность вероятности (x) постоянна на этом отрезке и равна нулю вне этого отрезка, т.е. Для получения случайных чисел xi с показательным законом распределения с параметром  можно использовать известное соотношение , где Pi есть равномерно распределенная величина [1, с.158-159]. Для получения случайных чисел с другими законами распределения можно использовать следующие соотношения и процедуры [1, с.162-163]. Тема 5:  Методы оптимальных решений в условиях неопределенности 22. Матричные игры и их решение В экономической деятельности часто возникают ситуации, в которых интересы сторон либо противоположны, либо не совпадают. При этом каждая сторона стремится получить наилучший результат за счет другой стороны. Это приводит к возникновению конфликтной ситуации. Теория игр занимается выработкой рекомендаций по оптимальному поведению сторон в конфликтной ситуации. Исход игры – это значение некоторой функции, называемой функцией выигрыша (может задаваться аналитически или таблицей). Рассмотрим таблицу решений, в которой строки соответствуют стратегиям 1-го игрока, а столбцы – стратегии 2-го игрока. – выигрыш (проигрыш), соответствующий каждой паре стратегий , . Стратегии 2-го игрока Стратегии 1-го игрока … … …  … … … … … Игра, в которой выигрыши и проигрыши игроков задаются матрицей , называется матричной игрой. Стратегией в игре называется совокупность правил, определяющих выбор игроком одного из возможных вариантов действий. Нижней ценой игры называется гарантированный выигрыш первого игрока (соответствующая стратегия называется максиминной) . Верхней ценой игры называется гарантированный проигрыш второго игрока (соответствующая стратегия называется минимаксной) . Для матричных игр всегда справедливо неравенство . Если , то игра называется игрой с седловой точкой. Элемент матрицы, соответствующий паре оптимальных стратегий, называется седловой точкой. Этот элемент называется ценой игры. Если платежная матрица не имеет седловой точки, т.е. , то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами. 23. Игры с природой. Методы их решения Игры с природой – это игры, в которых неопределенность вызвана не сознательным противодействием противника, а недостаточной осведомленностью об условиях, в которых действуют стороны. Условия такой игры обычно представляются таблицей решений, в которой строки соответствуют стратегиям ЛПР (лица, принимающего решение), а столбцы – стратегиям природы. – выигрыш ЛПР, соответствующий каждой паре стратегий , . Возможные стратегии … … … … … … … … … Для нахождения оптимального решения (стратегии) используют следующие критерии [1, с.147-149]. Критерий Вальда рекомендует применять максиминную стратегию и совпадает с нижней ценой игры. Это пессимистический критерий: предполагается, что природа будет действовать наихудшим способом. Критерий Сэвиджа рекомендует применять стратегию, не допускающую чрезмерно высоких потерь , где: •  – элементы матрицы рисков; •  – максимальный элемент в столбце исходной матрицы. Замечание. При принятии решений в условиях неопределенности следует оценивать различные варианты с позиции нескольких критериев. 24. Экспертные методы принятия решений: проверка согласованности и достоверности экспертных оценок Метод экспертных оценок представляет собой процедуру, позволяющую группе экспертов приходить к согласию. Для многих неформализуемых управленческих задач экспертные процедуры являются эффективным, а в ряде случаев и единственным средством их решения. Сущность метода экспертных оценок заключается в проведении квалифицированными специалистами-экспертами интуитивно-логического анализа проблемы с количественной оценкой суждений и формальной обработкой результатов. Можно выделить два класса методов экспертных оценок: 1) индивидуальные экспертные оценки; 2) групповые экспертные оценки. Методы коллективной экспертной оценки разделяют на два класса: одни используют открытую дискуссию, другие – опрос с помощью анкет. Актуальной проблемой в области коллективной экспертизы при анкетной форме является повышение достоверности групповой оценки. Результаты экспертизы можно считать достоверными лишь в том случае, если достигнута достаточная степень согласия между участвующими в экспертизе экспертами. Для оценки согласования мнений двух экспертов используют коэффициент ранговой корреляции Спирмена: , где: • m – количество ранжируемых элементов; • ; •  – ранг, полученный j–ым элементом соответственно от первого и второго эксперта. Известно, что  меняется от -1 до 1. Чем больше , тем выше степень согласованности мнений экспертов. Для оценки согласования мнений N экспертов используют специальные показатели, называемые коэффициентами конкордации (согласованности). Наиболее известным является коэффициент конкордации Кендалла: , где: • N – число экспертов; • m – количество элементов, подлежащих упорядочению по степени их важности; • ; •  – ранг (от 1 до m), полученный j–ым элементом от –го эксперта. Известно, что W меняется от 0 до 1. Чем больше W, тем выше степень согласованности мнений экспертов. Доказано, что величина N(m-1)W имеет распределение с  = m-1 степенями свободы. Для признания значимости коэффициента конкордации необходимо и достаточно, чтобы найденное значение N(m-1)W было больше табличного значения , где  – число степеней свободы,  – уровень значимости критерия (вероятность ошибки). 25. Методы экспертных оценок: метод Дельфи, его достоинства и недостатки; примеры использования Одним из наиболее эффективных методов групповой экспертной оценки с помощью анкетирования является метод Дельфи. В этом методе участвует координатор и группа экспертов. Ни один из экспертов не знает, кто ещё находится в этой группе, все контакты проходят через координатора [1, с.170-171]. 1. Координатор запрашивает прогнозы. 2. Координатор получает индивидуальные прогнозы от каждого эксперта. 3. Координатор определяет: • средний прогноз; • 50%-й интервал для среднего прогноза. 4. Координатор запрашивает объяснения экспертов, чей прогноз не попал в 50%-й интервал. 5. Координатор отправляет всем экспертам: • средний прогноз; • 50%-й интервал для среднего прогноза; • объяснения. 6. Возврат к пункту 1 (обычно до трех проходов). 7. Окончательная оценка точечного и интервального прогнозов. Опишем процедуру получения точечного и интервального прогнозов. Среднее значение прогнозируемой величины: , где: • n – число экспертов; • Bi – значение прогнозируемой величины, данной i–ым экспертом. Дисперсия прогнозируемой величины: . Оценка доверительного интервала: , где: • t – коэффициент Стьюдента для заданного уровня значимости и числа степеней свободы n-2. Доверительные границы прогнозируемой величины: .