Применение оптимизационных методов к решению задач

Введение 

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

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

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

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

    1.  Теоретические аспекты исследования

                                           1.1 Теория игр

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

       Игра - это совокупность правил, описывающих сущность конфликтной ситуации. Эти правила устанавливают:

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

       Игру  можно определить следующим образом:

• имеются и конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;
• сформулированы правила выбора допустимых стратегий, известные игрокам;
• определен набор возможных конечных состояний игры (например, выигрыш, ничья, проигрыш);
• всем игрокам (участникам игры) заранее известны платежи, соответствующие каждому возможному конечному состоянию. Платежи задаются в виде матрицы А = ||aj.

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

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

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

       Необходимо  подчеркнуть, что методы и рекомендации теории игр разрабатываются применительно  к таким специфическим конфликтным ситуациям, которые обладают свойством многократной повторяемости. Если конфликтная ситуация реализуется однократно или ограниченное число раз, то рекомендации теории игр теряют смысл. Чтобы проанализировать конфликтную ситуацию с помощью математических методов, её необходимо упростить, учитывая лишь важнейшие факторы, существенно влияющие на ход конфликта. Будем рассматривать игры, в которых у каждого из двух игроков А и В конечное число возможных действий - чистых стратегий. Допустим, что игрок А располагает m чистыми стратегиями , а игрок В – n чистыми стратегиями . Чтобы игра была полностью определённой, необходимо указать правило, сопоставляющее каждой паре чистых стратегий и число - выигрыш игрока А за счёт игрока В или проигрыш игрока В. При игрок А платит игроку В сумму .

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

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

       Максиминная стратегия игрока А: 

       Минимаксная стратегия игрока В:

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

       1.2 Элементы теории массового обслуживания 

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

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

       Примерами систем массового обслуживания могут  служить:

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

       Основными компонентами системы массового  обслуживания любого вида являются:

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

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

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

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

       В зависимости от характера формирования очереди СМО различают:

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

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

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

       По  числу каналов обслуживания СМО  делятся на одноканальные и многоканальные.

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

       Рассмотрим  в отдельности элементы СМО.

       Входящий  поток: на практике наиболее распространённым является простейший поток заявок, обладающий свойствами стационарности, ординарности и отсутствия последствия.

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

       Ординарность потока определяется невозможностью одновременного появления двух или более заявок.

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

        ,

       где -интенсивность потока заявок, т.е. среднее число заявок в единицу времени: (чел./мин, р./ч, автом./дн., квт/ч),

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

       Для такого потока заявок время между  двумя соседними заявками распределено экспоненциально с плотностью вероятности

        .

       Случайное время ожидания в очереди начала обслуживания считают распределённым экспоненциально:

        ,

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

        ,

       где - среднее значение времени ожидания в очереди.

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

        ,

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

        (чел./мин, р./дн., кг/ч, докум./дн.),

       где - среднее время обслуживания.

       Важной  характеристикой СМО, объединяющей l и m, является интенсивность нагрузки.

        . 
 
 
 
 
 
 
 
 
 
 
 
 

    1.3 Динамическое программирование 

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

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

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

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

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

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

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

    Итак, при решении оптимизационной  задачи методом динамического программирования необходимо учитывать на каждом шаге последствия, к которым приведёт в будущем решение, принимаемое  в данный момент. Исключением является последний шаг, которым процесс заканчивается. Здесь процесс можно планировать таким образом, чтобы последний шаг сам по себе приносил максимальный эффект. Спланировав оптимальным образом последний шаг, можно к нему “пристраивать” предпоследний так, чтобы результат этих двух шагов был оптимальным, и т.д. Именно так - от конца к началу - и можно развернуть процедуру принятия решений. Но чтобы принять оптимальное решение на последнем шаге, надо знать, чем мог закончиться предпоследний шаг. Значит, надо сделать разные предположения о том, чем мог закончиться предпоследний шаг и для каждого из предположений найти решение, при котором эффект на последнем шаге был бы наибольшим. Такое оптимальное решение, найденное при условии, что предыдущий шаг закончился определённым образом, называют условно-оптимальным.

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

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

    1.4 Сетевое планирование и управление

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

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

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

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

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

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

       Работа  и событие являются основными  элементами сети. Под работой в СПУ понимаются любые действия, трудовые процессы, сопровождающиеся затратами ресурсов или времени и приводящие к определённым результатам (событиям). Иногда выполнение работы требует затрат только времени (естественная сушка материалов, затвердевание бетона и др.). Иногда работы выражают только зависимости: показывают, что одна работа не может быть выполнена ранее какого-либо события. Такие работы называют фиктивными. Фиктивная работа не связана с затратами труда, времени и ресурсов. На сети она изображается отрезком штриховой линии без указания времени. Под событием понимают результат завершения одной или нескольких работ. Событие является предпосылкой для выполнения работ, следующих за ним. Поэтому любая работа на сети может быть определена двумя событиями, между которыми она находится. Событие же может принадлежать нескольким входящим и выходящим из него работам. На    рис 1 приведён пример сети, изображающий комплекс работ по возведению производственного корпуса.

РИС 1.

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

       В первую очередь, перед построением  сетевого графика необходимо составить  список всех работ, входящих в комплекс, представлять их конечные результаты (события). В отношении каждой работы следует выяснить, какие работы ей предшествуют и какие следуют за ней. Только после этого строится эскизный сетевой график, упорядочиваются и нумеруются (шифруются) его события (вершины графа). Если комплекс сложный, то его графическое представление строится по частям, которые затем “сшиваются”. При большом количестве работ и событий упорядочение их и сшивание отдельных сетевых графиков, а также поиск контуров производится на ЭВМ. Если в сети обнаружен контур, необходимо пересмотреть список работ и логические связи между ними. Обычно требуется, чтобы в сети было единственное исходное (начальное) событие и единственное завершающее, что возможно при введении фиктивных работ. В сети не должно быть хвостовых ( кроме исходного I) и тупиковых (кроме завершающего S) событий. Хвостовым называют событие, в которое не входит ни одна работа (рис 2, событие 3); тупиковым – событие, из которого не выходит ни одна работа (рис 2, событие 6).

        РИС 2.

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

       РИС 3.