Экономико-математические методы

Раздел 4. Экономико-математические методы Тема 4.1. Моделирование задач принятия решений 4.1.1. Этапы математического моделирования. В настоящее время в различных областях знаний завоевал большое признание метод математического моделирования. В его основе лежит приближенное описание какого-либо класса про­цессов и явлений символами математики и логики. Процесс ма­тематического моделирования можно разделить на четыре этапа. Первый этап – определение класса изучаемых объектов и за­конов, связывающих рассматриваемые объекты. Этот этап требует знания множества фактов, относящихся к изучаемым явлениям, и глубокого проникновения в их взаимосвязи. Результатом этого этапа является запись в математических терминах сформулиро­ванных качественных представлений о связях между объектами моделирования, т.е. построение математической модели. Второй этап – это получение результатов с помощью матема­тической модели для дальнейшего их сопоставления с результата­ми наблюдений изучаемых явлений. Здесь важную роль играет ма­тематический аппарат, необходимый для анализа математической модели, и вычислительная техника, позволяющая количественно решить сложные математические задачи. Третий этап – выяснение того, удовлетворяет ли принятая гипотетическая модель критерию практики, т.е. согласуются ли результаты наблюдений с теоретическими следствиями модели и если да, то с какой точностью. Применение критерия практики к оценке математической модели позволяет делать вывод о правиль­ности положений, лежащих в основе изучаемой модели. Метод моделирования является единственным методом изучения непо­средственно недоступных явлений макро- и микромира. Четвертый этап состоит в анализе модели в соответствии с накопленными данными об изучаемых явлениях и процессах и в усовершенствовании модели. Экономическое прогнозирование, которое наиболее сис­темно реализуется с помощью математических моделей, является ключевым мо­ментом в процессе принятия управленческих решений. Прогнозирование позволяет не только получить значения экономических показателей в буду­щем, оценить эффективность управленческой деятельности, но и выявить возможные ее направления в зависимости от изменения того или иного фактора, вли­яющего на принятие управленческих решений. Несомненным преимуществом математических моделей явля­ется то, что оценка вариантов управленческих решений может осуществляться, с одной стороны, с учетом прогнозных значений экономических показателей, а не только фактических данных, с другой стороны, с учетом ресурсных затрат, необходимых для реализации конкретных меро­приятий и программ. Еще одним несомненным достоинством математического мо­делирования, облегчающим процесс анализа информации и при­нятия решения, является возможность использования при изуче­нии исследуемых моделей ЭВМ. 4.1.2. Основные понятия математического моделирования. Существует известное изречение, что правильно поставить задачу – значит наполовину решить ее. Следует признать, что правильная постановка задачи является сама по себе сложной задачей. Однако методология процесса постановки задач (как первого этапа операционного исследования) выходит за рамки проблематики данного раздела, посвященного математическим аспектам решения задач организационного управления. Для этого очень важно суть задачи словесно описать таким образом, чтобы были возможны дальнейшая формализация и разработка математической модели, то есть описание задачи на математическом языке. Формальная структура постановки задач базируется на определенной совокупности элементов. Соотнесение всех условий задачи этим элементам позволяет «обнажить» суть задачи и, в конечном итоге, получить ее четкую, однозначно понимаемую формулировку. Принято выделять следующие элементы общей структуры задач принятия решений: а) цели, ради достижения которых принимается решение; б) множество управляемых (разрешающих) переменных, значения которых могут определяться лицом, принимающим решение (ЛПР); в) множество внешних (экзогенных) переменных, значения которых не контролируются ЛПР и имеют вероятностный или неопределенный характер; г) множество параметров, которые также не контролируются, но считаются в условиях данной задачи вполне определенными; д) ограничения – предельные значения тех параметров и неконтролируемых переменных, которые не могут быть превзойдены или не достигнуты при реализации решения; е) решение (или стратегия) – некоторая допустимая совокупность значений управляемых переменных; ж) критерий эффективности (показатель качества) решения, на основе которого производится оценка и сравнение вариантов решений, и выбор лучшего. Предполагается, что приведенные выше элементы должны быть измеримыми, то есть иметь характер «количества» или, по меньшей мере, «величины». Тогда дальнейший процесс разработки математической модели задачи будет сводиться к изучению взаимосвязей между целями, переменными и параметрами и отражению этих взаимосвязей в виде математических выражений (уравнений, неравенств и т.п.). Среди этих выражений можно выделить две группы: К первой отнесем условия достижения целей, т.е. выражения, отображающие зависимости между управляемыми переменными и поставленными целями. Ко второй группе относятся выражения, отображающие условия-ограничения, описывающие связи между управляемыми переменными и теми из параметров и «внешних» переменных, которые или не могут быть превзойдены, или не достигнуты при реализации решения. (В отечественной литературе математические выражения, как правило, на упомянутые группы не подразделяются и обозначаются единым термином – «ограничения»). Совокупность значений управляемых переменных, удовлетворяющих системе указанных выше выражений (условиям достижения целей и ограничениям), принято называть допустимым решением (стратегией, планом). Множество допустимых решений называется областью допустимых решений. Поскольку проблема принятия решения заключается не только в нахождении допустимого решения, но и в выборе наилучшего из них по принятому критерию, – возникает необходимость определения значения критерия в зависимости от значений контролируемых переменных. Функция, определяющая эту зависимость, называется целевой функцией. Таким образом, совокупность (система) математических выражений, отражающих условия достижения целей и условия выполнения ограничений, вместе с целевой функцией и представляют собой математическую модель задачи. Допустимое решение, при котором значение целевой функции достигает экстремума (минимального или максимального значения в зависимости от условий задачи), называется оптимальным решением. Приведенные понятия (элементы структуры задач принятия решений) являются наиболее общими. Далее, при рассмотрении отдельных типов задач, понятийный аппарат будет расширен. Так, например, при изучении задач массового обслуживания будут введены такие понятия, как дисциплина очереди, канал обслуживания, интенсивность обслуживания и др.; в задачах упорядочения и координации (управление проектами) – такие понятия, как критические работы, резервы времени и т.п.; в состязательных задачах (теория игр) – понятия ход, платежная матрица, чистые и смешанные стратегии и т.д… При постановке задачи и ее моделировании необходимо прежде всего оценить, какой из формулировок принципа экономичности соответствует данная ситуация принятия решения. Принцип экономичности может формулироваться двояко: • заданных целей (результатов) достигнуть при минимальных затратах; • при заданных пределах затрат достигнуть цели в максимальной степени (достичь максимума результата). Принцип экономичности в первой формулировке иногда называют «принципом экономии средств», во второй – «принципом максимального эффекта». Если задача формулируется по «принципу максимального эффекта», то целевая функция являет собой условие достижения цели (цель – максимум результата), остальные математические выражения, входящие в модель, – суть условия-ограничения. Часто принцип экономичности формулируют так: «достигнуть максимальной степени реализации цели (максимального результата) при минимальных затратах». Такое определение неверно, внутренне противоречиво с содержательной точки зрения и ведет к постановке математически неразрешимой задачи. Кроме того, у руководителей возникает искушение оптимизировать решение задачи по нескольким критериям. Например, следующим образом: «найти такое решение, которое обеспечило бы максимум прибыли при минимуме годовых издержек на содержание производства и минимуме капитальных вложений». При всей внешней привлекательности и кажущейся естественности – такая постановка ведет к неразрешимой задаче. Желательно, как правило, стремиться так формулировать задачи, чтобы при множественности целей и ограничений, критерий оптимизации решения (а, стало быть, и целевая функция) был один. Это еще раз подтверждает важность правильного обоснования цели и критерия эффективности при постановке задачи, так как при этом определяется и выбор соответствующего варианта формулировки принципа экономичности. Рассмотренные в данном разделе модели и методы оптимизации ориентированы преимущественно на решение однокритериальных задач. Следует отметить, что в ряде сложных организационных задач возникает проблема многокритериальности. Некоторые подходы к постановке и решению такого рода задач будут рассмотрены в Теме 4.11. 4.1.3. Пример построения математической модели Рассмотрим проблему математического моделирования на примере задачи оптимизации параметров реорганизационной политики. Для большинства неплатежеспособных предприятий неудовлетворительная структура баланса отождествляется с отставанием фактического уровня текущей ликвидности от его норматива (Ктл < 2) даже при достаточном уровне обеспеченности собственными средствами (Косс  0,1). Реорганизационные политики – процедуры реструктуризации балансов – позволяют перевести их в удовлетворительную структуру за счет реализации специально подобранного комплекса организационно-технических мероприятий. Но однозначно выбрать для практической реализации из возможных вариантов реорганизационных политик один, наиболее рациональный затруднительно, так как, если по прогнозируемым показателям платежеспособности, структуры баланса они равнозначны, то по прогнозным финансовым результатам могут быть противоречивыми. Оценить предпочтительность каждого из этих вариантов оказывается возможным, если сформулировать задачу оптимизации реорганизационных политик с помощью математической модели, которая будет определяться текущим уровнем финансовой состоятельности, прежде всего, сложившимся уровнем платежеспособности. Задача оптимизации основных параметров текущей деятельности может быть представлена следующей общей постановкой: где F(x) – целевая функция задачи; хi – независимые искомые переменные по направлениям реорганизационной политики (вектор управления структурой имущества: искомая величина продаж одного вида средств, приобретения другого, погашения долгов); i – экспертная оценка приоритетности i-го направления реорганизации; w – константа обеспечения текущей ликвидности (w=2КЗ – ОА; КЗ – краткосрочная задолженность, ОА – оборотные активы); аi – коэффициенты при неизвестных переменных в ограничении на обеспеченность собственными оборотными средствами; q – минимально-допустимый уровень обеспеченности собственными оборотными средствами (q = ВА + 0,1ОА – КР; ВА – внеоборотные активы, КР – капитал и резервы); а – верхний предел допустимых продаж и приобретений активов; – соответственно нижняя и верхняя границы возможного изменения i-го вида активов; i – удельный вес i-го вида активов предприятия в общей стоимости его имущества. В частности, применительно к типичной неудовлетворительной структуре баланса Ктл < 2, Косс  0,1, характерной для большинства неплатежеспособных предприятий, ищем такие х1 – объем продаж части активов, х2 – размер погашения кредиторской задолженности, чтобы выполнилось условие Ктл = 2 при сохранении Косс  0,1. Тогда модель приобретает вид: Ктл = (ОА + х1 – х2)/(КЗ – х2) = 2, откуда х1 + х2 = 2КЗ – ОА; Косс = (КР – ВА + х1)/(ОА + х1 – х2)  0,1, откуда 0,9х1 + 0,1х2  ВА +0,1ОА – КР; х2 – х1  ОА; х1  ВА; х2  КЗ, где    – предельно допустимые для сохранения статуса деятельности предприятия размеры уменьшения соответственно оборотных активов (например, до 20%), внеоборотных активов (10%), краткосрочной задолженности (50%). Целевая функция min(1х1 + 2х2), где 1, 2 – экспертные оценки значимости продажи имущества и погашения наиболее срочных обязательств. Приведенная выше задача может быть решена методами линейного программирования, которые будут рассмотрены в теме 4.2. Однако встречаются математические модели, которые решить аналитически невозмож­но. Для их решения существуют специальные методы чис­ленного решения. Особенностью таких методов является нали­чие погрешности в результатах. Погрешность в результатах оп­ределяется неточностью модели, т.е. ошибочностью или недоста­точностью положений, лежащих в основе построенной модели, и погрешностью математических методов, с помощью которых про­водился анализ изучаемой модели. Представленные ниже в темах 4.2 – 4.11 модели и методы в основном ориентированны на те задачи, которые попадают в сферу исследования операций в управленческой и экономической деятельности и могут быть полностью или частично использованы при их математическом моделировании. Тема 4.2. Линейное программирование 4.2.1. Моделирование задачи оптимизации производства методами линейного программирования. Линейное программирование является одним из методов решения общих задач оптимизации, в которых учитывается большое число переменных, подчиненных определенным ограничениям. При решении этих задач необходимо получить оптимальное значение определенного критерия эффективности (функции цели), например прибылей, затрат, количества произведенных продуктов или других показателей, при условии, что удовлетворяются поставленные ограничения. Эти ограничения в свою очередь носят различный характер и объясняются условиями производства, управления, сбыта, хранения, наличием сырья или законодательными положениями. Линейное программирование можно использовать для решения задач оптимизации, в которых выполняются следующие условия: 1. Необходимо наличие линейной функции цели, оптимальное значение которой необходимо отыскать. Требование линейности существенно для применения методов, изложенных в этой и следующей теме. Линейность означает, например, что для изготовления 10 изделий потребуется в10 раз больше средств, чем для получения одного изделия, или для получения 5 изделий уйдет в 5 раз больше времени, чем на изготовление одного изделия, и т.д. Если же такое допущение пропорциональной зависимости неверно или нельзя получить линейную функцию за счет преобразования переменных, то методы линейного программирования неприменимы. 2. Ограничения также должны быть заданы в виде системы линейных равенств или неравенств. Если задача поставлена правильно, то можно использовать методы линейного программирования для ее решения. Рассмотрим следующую производственную задачу: Необходимо произвести два вида продукции в объемах х1 и х2, используя три ресурса, которые имеются в количестве b1, b2, b3, соответственно. Известны нормативы потребления ресурсов на производство единицы первого и второго вида продукции: а11 – количество первого ресурса, необходимого для производства единицы первого вида продукции; а12 – количество первого ресурса, необходимого для производства единицы второго вида продукции; а21 – количество второго ресурса, необходимого для производства единицы первого вида продукции; а22 – количество второго ресурса, необходимого для производства единицы второго вида продукции; а31 – количество третьего ресурса, необходимого для производства единицы первого вида продукции; а32 – количество третьего ресурса, необходимого для производства единицы второго вида продукции. Пусть с1 и с2 – прибыль от реализации единицы первого и второго вида продукции. Это постоянные факторы данной задачи. Пример 4.2.1. Придадим постоянным факторам конкретные числовые значения и сведем их в табл.4.2.1. Таблица 4.2.1. Изделие 1(х1) Изделие 2(х2) Наличие Ресурс 1 а11 = 2 а12 = 1 b1 = 12 Ресурс 2 а21 = 2 а22 = 3 b2 = 18 Ресурс 3 а32 = 1 а32 = 3 b3 = 15 Прибыль с1 = 5 с2 = 6 Производственная задача формулируется следующим образом: Найти такие объемы производства продукции х1 и х2, при которых потребление ресурсов в соответствии с нормативами не превышало бы их наличия, и при этом прибыль от реализации продукции была бы максимальна. Предполагая, что количество потребляемых ресурсов, а также прибыль пропорциональны объемам производства, получаем следующую математическую модель задачи: (I) 2х1 + 1х2  12 (II) 2х1 + 3х2  18 (III) 1х1 + 3х2  15 (4.2.1.) х1  0, х2  0 F=5х1 + 6х2  max. Система неравенств (4.2.1) отражает ограничения на потребляемые ресурсы, а целевая функция F определяет прибыль, которую необходимо максимизировать. Пару чисел х1 и х2, удовлетворяющих системе ограничений (4.2.1), будем называть допустимым планом, а допустимый план, дающий максимальное значение целевой функции F – оптимальным планом (решением). 4.2.2. Геометрическая интерпретация задачи линейного программирования. Рассмотрим геометрическую интерпретацию данной задачи. Каждой паре чисел х1 и х2 поставим в соответствие точку плоскости (2-мерного пространства) с координатами х1 и х2, тогда каждое ограничение (4.2.1) задает полупространство, а вся система (4.2.1) определяет многоугольник (в n-мерном пространстве – многогранник), полученный в результате их пересечения. В общем случае многогранник может быть неограниченным или пустым (система неравенств противоречива). В примере 4.2.1 множество допустимых планов соответствует на плоскости множеству точек многоугольника OABCD(рис 4.2.1.). Целевая функция F=5х1 + 6х2 определяет на плоскости семейство прямых линий (в n-мерном пространстве – плоскостей), параллельных друг другу, причем, чем дальше прямая от точки О, тем большее значение принимает целевая функция. Таким образом, оптимальное решение будет в точке многоугольника OABCD, где целевая функция касается этого многоугольника при удалении от точки О. х2 11 (I) 10 9 8 7F 6 n 5A B 4 3 n2 C (III) 2 (II) 1 n1 2 3 4 5 D 6 7 8 9 10 11 12 14 15 O Рис.4.2.1. Графическое представление задачи примера 4.2.1 х1 В нашем примере это будет вершина многоугольника С с координатами (примерно) х1=4.5; х2=3. Для точного определения координат точки С рассмотрим уравнения прямых, пересечение которых ее образовало. Получаем систему из двух уравнений: 2х1 + 1х2 = 12, 2х1 + 3х2 = 18, решив которую получим точные значения х1 , х2. Метод решения системы линейных уравнений может быть использован любой, однако, в целях сокращения объема вычислений при дальнейшем изложении предлагается метод Крамера (см.2.2). Напомним кратко его суть: Для решения системы а11 х1 + а12 х2 = b1, а21 х1 + а22 х2 = b2, вычисляем  = а11 а22  а12 а21, 1 = b1 а22  а12 b2, 2 = а11 b2  b1 а21, и затем х1 = 1 /  ; х2 = 2 / . В нашем примере: =23 – 12 = 4, 1 = 123 – 118 = 18, 2 = 2 18 – 12 2 = 12 , откуда х1 = 18 / 4 = 4.5, х2 = 12 / 4 = 3 (совпало с первоначальным приближением). Вычислим значение целевой функции в точке С: F = 5  4.5 + 6 3 = 40.5. Таким образом мы решили поставленную задачу, нашли объемы производства х1 первого и х2 второго вида продукции, удовлетворяющие ограничениям (4.2.1) и доставляющие максимальное значение целевой функции F = 40.5 усл.ед. Пример 4.2.2. Рассмотрим еще одну задачу (ее часто называют задачей о диете, хотя аналогичной математической моделью можно описывать задачи, ничего общего с диетой не имеющие). Таблица 4.2.2 Виды кормов Содержание в 1 кг Себестоимость 1 кг (усл. ед). Кормовых единиц Белок гр. Кальций гр. Сено (х1) 0.5 50 10 1.5 Концентраты(х2) 1 200 2 2.5 Норматив 20 2000 100 Под нормативом понимается необходимый минимум питательных веществ суточного рациона. В этой задаче необходимо найти такие объемы кормов х1, х2 , чтобы обеспечить содержание в них кормовых единиц, белка и кальция не менее нормативного при минимальной стоимости. Опять же предполагая, что количество полезных веществ, а также стоимость пропорциональны объемам кормов, получаем следующую математическую модель задачи: (I) 0.5х1 + 1х2  20 (II) 50х1 + 200х2  2000 (III) 10х1 + 2х2  100 (4.2.2) х1  0, х2  0 F=1.5х1 + 2.5х2 min. Геометрическую интерпретацию данной задачи приведем на рис.4.2.2. х2 50 A (II) 40 35 30 F n 20 B (III) 10 (I) 5 C 5 10 15 20 25 30 35 40 х1 Рис.4.2.2. Графическое представление задачи 4.2.2 В данном случае множество допустимых планов представляет собой неограниченный многоугольник, заштрихованный на рис.4.2.2. Целевая функция принимает наименьшее значение в точке В. Визуально на графике координаты этой точки х1  7, х2  17. Сделаем аналитическую проверку: =0.52 – 110 = –9, 1 = 202 – 1100 = –60, 2 = 0.5 100 – 20 10 = –150. Откуда х1 = –60 / –9 = 6.67, х2 = –150 / –9 = 16.67. 4.2.3. Общая задача линейного программирования. Мы рассмотрели сейчас предельно упрощенные примеры, преследуя исключительно иллюстративные цели, однако их анализ позволит осмыслить общие идеи и математические методы, лежащие в основе решения подобных задач. В обоих примерах множество допустимых планов определяется точками выпуклого многогранника, полученного в результате пересечения полупространств, заданных линейными неравенствами (4.2.1) и (4.2.2). Линейная целевая функция при двух переменных задает на плоскости семейство параллельных прямых, при трех переменных – семейство параллельных плоскостей в трехмерном пространстве, а в случае n переменных – семейство параллельных (n-1)–мерных пространств (гиперплоскостей) в n-мерном пространстве. Линейные ограничения и линейная целевая функция появились в наших примерах благодаря предположению о пропорциональной зависимости переменных и постоянных факторов. В силу этого подобный класс задач называют задачами линейного программирования. Геометрически решение задачи линейного программирования сводится к следующим этапам: а) определение области допустимых планов, т.е. построение соответствующего ограничениям многогранника; б) перемещение гиперплоскости целевой функции в пространстве параллельно самой себе до тех пор, пока она не будет максимально (минимально) удалена от начала координат и при этом будет иметь хотя бы одну общую точку с многогранником допустимых планов. Этой точкой, как мы видели, будет вершина многогранника, хотя может быть грань или ребро в случае параллельности гиперплоскости целевой функции какой-либо грани или ребру многогранника. Координаты этой вершины и будут определять оптимальное решение. Если целевая гиперплоскость касается грани или ребра, то в этом случае получается множество оптимальных планов, имеющих одно и тоже максимальное (либо минимальное) значение целевой функции. Из анализа решения примеров делаем важный вывод: оптимальному плану соответствует точка в области допустимых планов (возможно неединственная), являющаяся вершиной многогранника допустимых планов. На этом основана идея метода решения задачи линейного программирования, заключающаяся в том, что для нахождения оптимального плана достаточно просматривать лишь вершины многогранника допустимых планов. Решение (план), которому соответствует вершина многогранника, называется базисным. Для нахождения базисного плана необходимо решить систему из n линейных уравнений с n неизвестными. Разработанный в 1949г. Дж. Данцигом симплекс-метод основан на последовательном переходе от одной вершины многогранника допустимых планов к соседней, в которой линейная целевая функция принимает лучшее (не худшее) значение до тех пор, пока не будет найдено оптимальное решение. Рассмотренные выше примеры позволяют сформулировать общую задачу линейного программирования. Дана система m линейных неравенств с n переменными а11 х1 + а12 х2 + …+ а1nхn  b1 а21 х1 + а22 х2 + …+ a2nxn  b2 ……………………………….. (4.2.3) аm1 x1 + am2x2 + …+ amnxn  bm и линейная функция F = c1x1 + c2x2 + … + cnxn (4.2.4) Необходимо найти такое решение системы Х = (x1, x2,… , xn ), где xj  0 (j=1,2,…n), (4.2.5) при котором линейная функция F (4.2.4) принимает оптимальное (максимальное или минимальное) значение. Система (4.2.3) называется системой ограничений, а функция F – целевой функцией, критерием или функцией цели. Более кратко общую задачу линейного программирования можно представить в виде: F =  max( min) при ограничениях:  bi (i=1,2,…,m), xj  0 (j=1,2,…n). Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение системы ограничений (4.2.3), удовлетворяющее условию (4.2.5), при котором линейная функция (4.2.4) принимает оптимальное (максимальное или минимальное) значение. В рассматриваемой задаче все неравенства вида “  “, хотя могут быть и вида ““, каждое такое неравенство, как мы видели на примерах, определяет полупространство в n-мерном пространстве. Постоянные коэффициенты aij являются, как правило, нормами расхода i-го ресурса на производство единицы j-го изделия (продукта). Коэффициенты bi задают предельные объемы использования i-го ресурса. Коэффициенты cj определяют удельную прибыль (или затраты) от производства единицы j-го изделия (продукта). Если мы какую либо производственную задачу смоделировали в виде задачи линейного программирования, то в ходе ее решения можно получить следующие результаты: 1. Ограничения могут оказаться несовместными, и задача не имеет решения. 2. Целевая функция не ограничена в области допустимых планов, ее максимум ( или минимум)  +  (- ). 3. Оптимальное решение единственное (целевая функция касается области допустимых планов в единственной вершине, ее координаты и определяют оптимальный план). 4. Существует некоторое множество оптимальных решений (планов). Если задача экономически поставлена правильно, то 1-й и 2-ой случаи исключаются. 4.2.4. Устойчивость оптимального решения. Рассмотрим теперь понятие устойчивости оптимального решения. В первом примере (см. рис 4.2.1.) оптимальное решение находится в точке С, которая является пересечением двух прямых, заданных уравнениями 2х1 + 1х2 = 12, (I) 2х1 + 3х2 = 18. (II) Целевая функция F=5х1 + 6х2 (здесь c1=5, c2=6) максимальное значение приняла в точке С. После составления плана и его реализации в конкретной производственной программе c1 и c2 (удельная прибыль или затраты) могут изменяться. Зададимся следующим вопросом: при каком соотношении коэффициентов целевой функции c1 и c2 оптимальное решение сохранится (устоит) в точке С? Из аналитической геометрии (см.2.1) нам известно, что коэффициенты, стоящие перед переменными х1 и х2 в уравнении прямой суть координаты вектора, перпендикулярного данной прямой (т.н. нормаль). На рис.4.2.1 нормаль к целевой функции обозначена n, нормаль к ограничению (I) n1 и нормаль к ограничению (II) n2. Чтобы оптимальное решение сохранялось в точке С при изменяющихся коэффициентах c1 и c2 необходимо, чтобы вектор нормали n лежал между векторами n1 и n2. Для этого необходимо, чтобы тангенс угла между вектором n и осью х1(обозначим через tg(n, х1)) был больше tg(n1, х1), но меньше tg(n2, х1). Таким образом, для обеспечения устойчивости оптимального решения в точке С необходимо выполнение условия: tg(n1, х1)  tg(n, х1)  tg(n2, х1). Так как tg(n, х1) = c2/ c1, tg(n1, х1) = а12 /а11 =1/2, tg(n2, х1) = а22 /а21 =3/2, окончательно получаем для примера 4.2.1 соотношение устойчивости оптимального решения в виде: 1/2  c2 /c1  3/2. В случае n переменных получаем много соотношений аналогичного вида между всеми сk и cj (kj) показывающих, при каких условиях изменение коэффициентов целевой функции не повлечет изменение оптимального решения. Подставляя вместо c1 и c2 их значения получим проверочные соотношения 1/2  6 /5  3/2. Для второй задачи соотношение устойчивости оптимального решения будет иметь вид: 2/10  c2 /c1  1/0.5, а проверочное соотношение 2/10  2.5 /1.5  1/0.5. 4.2.5. Обьективно-обусловленные оценки. Рассмотрим опять пример 4.2.1. Оптимальное решение было найдено в точке С с координатами х1=4.5; х2=3. Существенными оказались ограничения (I) и (II), они в точке оптимального плана обращаются в равенство: 24.5 + 13 = 12, 24.5 + 33 = 18, т.е. эти ресурсы используются полностью, тогда как третий ресурс (несущественное ограничение (III)) оказывается в избытке: 14.5 + 33 < 15 (избыток составляет 15 – (14.5 + 33) = 1.5). Попробуем теперь ответить на следующий вопрос: На сколько изменится значение целевой функции (в данном примере увеличится прибыль), если ограничение увеличить на одну единицу? Или, другими словами, какова ценность для нашей задачи каждого ресурса? Для третьего ресурса (который и так в избытке) ответ очевиден – значение целевой функции не изменится (F = 40.5). Посчитаем эти изменения целевой функции для ограничений (I) и (II), для чего решим две системы (используя также метод Крамера). Увеличим сначала на одну единицу количество первого ресурса: 2х1 + 1х2 = 12 + 1, 2х1 + 3х2 = 18.  не изменилось ( =23 – 12 = 4), тогда как 1 = (12 +1) 3 – 118 = 18 + 3 = 21, 2 = 2 18 – (12 + 1) 2 = 12 –2 =10, откуда координаты новой точки будут х1 = 21 / 4 = 5.25, х2 = 10 / 4 = 2.5. Вычислим значение целевой функции в этой новой точке: F1 = 5  5.25 + 6 2.5 = 41.25, откуда y1 = F1 - F = 41.25 – 40.5 = 0.75. Аналогично, увеличивая на одну единицу количество второго ресурса, решаем систему: 2х1 + 1х2 = 12, 2х1 + 3х2 = 18 + 1. 1 = 123 – 1 (18 + 1) = 18 – 1 = 17, 2 = 2  (18 + 1) – 12 2 = 12 + 2 =14, откуда х1 = 17 / 4 = 4.25, х2 = 14 / 4 = 3.5 Вычислим значение целевой функции в этой новой точке : F2 = 5  4.25 + 6 3.5 = 42.25, откуда y2 = F2 – F = 42.25 – 40.5 = 1.75. Таким образом, мы нашли объективно обусловленные оценки всех ресурсов (ограничений): у существенных ограничений y1=0.75, y2 = 1.75, у третьего несущественного ограничения y3= 0. 4.2.6. Двойственная задача линейного программирования. В 4.2.2 мы рассматривали общую задачу линейного программирования. Рассмотрим теперь другую экономическую задачу на том же предприятии с теми же исходными данными. Необходимо определить такие цены ( y1  0, y2  0,…, ym  0 ) (4.2.6) всех ресурсов, чтобы сумма потраченных средств на их приобретение была бы минимальна, т.е. Z = b1 y1 + b2 y2 +…+ bm ym  min. (4.2.7) С другой стороны, предприятию будет выгодно продать ресурсы в случае, если выручка от их продажи будет не менее той суммы, которую предприятие может получить при изготовлении продукции из этих ресурсов. Т.к., на производство единицы продукции j расходуется a1j единиц ресурса 1, a2j единиц ресурса 2,…, amj единиц ресурса m, то для обеспечения выгодности продажи ресурсов необходимо выполнение следующих неравенств: a11 y1 + a21 y2 +…+ am1 ym  c1, a12 y1 + a22 y2 +…+ am2 ym  c2, …………………………………. (4.2.8) a1n y1 + a2n y2 +…+ amn ym  cn, Полученная экономико-математическая модель называется двойственной или сопряженной по отношению к исходной. Цены ресурсов y1, y2,…, ym получили различные названия: учетные, неявные, теневые. В отличие от «внешних» цен c1, c2 ,…,cn на продукцию, известных, как правило, до начала производства, цены ресурсов y1, y2,…, ym являются внутренними, ибо они определяются непосредственно в результате решения задачи, поэтому их чаще называют объективно обусловленными оценками ресурсов (Л.В.Канторович). Построим двойственную задачу для примера 4.2.1: Z = 12 y1 + 18 y2 +15y3  min. (4.2.9) 2y1 + 2y2 + y3  5, y1 + 3y2 + 3y3  6, (4.2.10) y1  0, y2  0, y3  0. Из алгебраических соображений легко показать, что F  Z, откуда maxF= minZ, если они существуют ( основная теорема двойственности). В нашем примере 4.2.1 maxF = minZ = 40.5, и объективно обусловленные оценки y1= 0.75, y2 = 1.75, y3 = 0, вычисленные простым счетом в 4.2.5, являются решением двойственной задачи (4.2.9)-(4.2.10). Действительно, 120.75 + 181.75 + 150 = 40.5. Из выражения (4.2.9) видно, что если увеличить в условии задачи какое-либо ресурсное ограничение bi на единицу, то Z (и следовательно F) также увеличится ровно на yi . Однако прямая и двойственная ей задача линейного программирования имеют и экономическое истолкование. Так, в задачах на распределение ограниченных ресурсов в производстве оптимальный план можно получить, либо минимизируя издержки для заданной программы, либо максимизируя выпуск при заданной общей сумме издержек. Двойственными аспектами одной и той же задачи являются распределение ресурсов и оценка их. Если для ресурсов не существует рыночных цен, то необходимо их создать, ввести систему условных или расчетных цен. Рассмотрим теперь пример 4.2.2 и построим для него двойственную задачу. Напомним, что в этом примере из сена и концентратов необходимо составить суточный рацион питания, калорийность которого 20 кормовых единиц, содержание белка 2000 гр., а кальция 100 грамм. Цена сена 1.5, а концентратов 2.5 усл.единиц за 1 кг. Пусть y1 , y2 , y3 - наша оценка (за единицу) полезности каждого из этих показателей. Тогда общая (условная) оценка рациона питания: Z = 20 y1 + 2000 y2 +100y3. Мы будем стремиться максимизировать Z. Если 1 кг. сена содержит 0.5 кормовых единиц, 50г белка и 10 г кальция, то оценка его питательного содержания, т.е. 0.5y1 + 50y2 + 10y3 , не может превышать его рыночной цены (1.5). Аналогично этому для концентратов оценка питательных веществ, равная y1 + 200y2 + 2y3, не может превышать 2.5. Следовательно, двойственную задачу можно сформулировать таким образом: Найти такие оценки питательных веществ, чтобы Z = 20 y1 + 2000 y2 +100y3  mах (4.2.11) при условии 0.5y1 + 50y2 + 10y3  1.5, y1 + 200y2 + 2y3  2.5, (4.2.12) y1  0, y2  0, y3  0. Мы получили двойственную задачу к примеру 4.2.2, в котором требовалось найти минимальную стоимость входящих в рацион продуктов питания при заданных рыночных ценах на эти продукты и при соблюдении ограничений в отношении потребности в питательных веществах. После введения условных оценок показателей питательности возникает двойственная задача (4.2.11) – (4.2.12), где требуется максимизировать условную оценку рациона питания при соблюдении ограничений, согласно которым расходы в расчете за единицу продукта не могут превышать его заданной рыночной цены. Цель первой, прямой задачи заключается в том, чтобы закупаемые продукты были возможно более дешевыми, удовлетворяя вместе с тем требованиям в отношении питательной ценности, а цель сопряженной двойственной задачи – в том, чтобы при заданных рыночных ценах на продукты получить рацион наиболее высокопитательный. Имея краткую запись общей задачи линейного программирования в виде: F =  max( min) при ограничениях:  bi (i=1,2,…,m), xj  0 (j=1,2,…n), можно так же кратко записать двойственную к ней задачу: Z =  min ( max) при ограничениях:  cj (j=1,2,…,n), yi  0 (i=1,2,…,m). Тема 4.3. Задачи транспортного типа 4.3.1. Экономико-математическая модель транспортной задачи. Важным частным случаем задачи линейного программирования является так называемая транспортная задача. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта (или взаимозаменяемых продуктов) из пунктов производства в пункты потребления. Экономико-математическая модель транспортной задачи в общем виде может быть сформулирована следующим образом: Имеется m пунктов производства однородного продукта и n пунктов потребления. Для каждого пункта производства i задан объем производства Аi, для каждого пункта потребления j известна потребность (спрос) Вj (в тех же единицах измерения). Известны издержки сij, связанные с перевозкой единицы продукта из пункта i в пункт j. Требуется составить план перевозок, обеспечивающий наиболее экономным путем (при наименьших транспортных издержках) удовлетворение всех пунктов потребления за счет реализации всего продукта, произведенного пунктами производства. Предположим, что суммарный спрос (В = jВj ) равен суммарному объему производства (А =iАi ). Такие задачи называются закрытыми транспортными задачами. Что такое план перевозок? План перевозок определяет: Сколько единиц продукта перевозится от каждого пункта производства к каждому пункту потребления, т.е. план представляется набором чисел хij (всего таких чисел mn), где хij показывает, сколько единиц продукта должно быть перевезено от i-го производителя j-му потребителю. В термин «транспортные издержки» (сij) не всегда вкладывается строгий экономический смысл. Это могут быть расстояния, тарифы, время, расход топлива и т.п. В каждой конкретной задаче оговаривается конкретный смысл сij. Система ограничений примет вид = Аi (i=1,2,…,m), (4.3.1) = Вj (j=1,2,…n). (4.3.2) Система (4.3.1) включает в себя уравнения баланса по поставщикам, а система (4.3.2) – по потребителям. Суммарные транспортные издержки выражаются в виде следующей линейной функции, которую необходимо минимизировать F =  min (4.3.3) Математическая модель транспортной задачи в общей постановке будет следующей: на множестве неотрицательных решений системы ограничений (4.3.1), (4.3.2) (мы будем называть такие решения допустимые) найти такое решение Х=(х11, х12,…,хij ,…,хmn ), при котором значение целевой функции (4.3.3) минимально. Условия транспортной задачи весьма удобно представлять в табличной форме Таблица 4.3.1 Пункт произ- водства i Объем произ- водства Аi Пункты потребления j и их спрос Вj 1 2 … n В1 В2 … Вn 1 А1 с11 х11 с12 х12 … с1n х1n 2 А2 с21 х21 с22 х22 … с2n х2n … … … … … … m Аm сm1 хm1 сm2 хm2 … сmn хmn В левом верхнем углу произвольной клетки (i,j) (i – номер строки, j–номер столбца) стоит показатель транспортных затрат сij, в правом нижнем – значения переменных хij (план перевозок). Любое решение Х=(х11, х12,…, хij ,…, хmn) системы ограничений (4.3.1) – (4.3.2) назовем распределением поставок. Рассмотрим простейший числовой пример (таб. 4.3.2). Здесь параметры задачи принимают следующие значения: с11 =2, с12 =1, с13 =5, с21 =3, с22 =4, с23 =3, с31 =4, с32 =6, с33=6; А1 =50, А2 =60, А3 =70, В1 =40, В2 =85, В3=55. Таблица 4.3.2 40 85 55 50 2 х11 1 х12 5 х13 60 3 х21 4 х22 3 х23 70 4 х31 6 х32 6 х33 Составим систему уравнений для этого примера: Чтобы объем производства каждого поставщика был реализован, необходимо выполнение баланса по каждой строке таблицы, т.е. х11 + х12 + х13 = 50 х21 + х22 + х23 = 60 (4.3.4) х31 + х32 + х33 = 70 Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса выписываем для каждого столбца таблицы: х11 + х21 + х31 = 40 х12 + х22 + х32 = 85 (4.3.5) х13 + х23 + х33 = 55 Суммарные транспортные затраты F (целевая функция) выражаются через издержки и поставки следующим образом: F = 2х11 + х12 +5х13 +3х21 +4х22 +3х23 +4х31 +6х32 +6х33. В этом примере шесть уравнений и девять переменных, система (4.3.4)–(4.3.5) имеет бесчисленное множество решений (допустимых поставок). Вот одно из них: Таблица 4.3.3 40 85 55 50 2 40 1 10 5 60 3 4 60 3 70 4 6 15 6 55 Суммарные транспортные затраты для данного распределения: F = 240 +110 +50 +30 +460 +30 +40 +615 +655=750. Всего в этом примере около 3600 только целочисленных решений, а если допустить дробность – то бесконечное множество. Все допустимые решения удовлетворяют системе ограничений, но отличаются друг от друга величиной суммарных транспортных издержек. Вот еще одна допустимая поставка: Таблица 4.3.4 40 85 55 50 2 1 50 5 60 3 40 4 3 20 70 4 6 35 6 35 Суммарные транспортные затраты для данного распределения: F = 150 +340 +320 +635 +635=650. Наша задача научиться находить оптимальное решение, т.е. такое, для которого целевая функция имеет наименьшее значение. 4.3.2. Исходный опорный план. Первым шагом при решении транспортной задачи является получение допустимого решения, которое называют исходный опорный план. Исходный план можно легко получить, используя алгоритм, разработанный Данцигом и названный Чарнсом и Купером “правилом северо-западного угла”. Это наиболее простой метод, хотя исходный план, полученный этим способом ,как правило, весьма далек от оптимального. “Правило северо-западного угла” формулируется следующим образом: 1. Начать с северо-западного угла исходной таблицы – клетки (1,1), куда дать максимально возможную поставку: х11 =minА1,В1. 2. Следующую максимально возможную поставку дать либо в клетку (1,2), либо в клетку (2,1), в зависимости от результата первого шага. 3. Продолжить этот процесс шаг за шагом от северо-западного до юго-восточного угла таблицы. Таким образом, в нашем примере (см. табл. 4.3.3) процесс определения исходного плана происходит следующим образом: В клетку (1,1) даем максимально возможную поставку: х11 =min50,40=40. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы выпадает из последующего рассмотрения. Переходим к клетке (1,2) и даем в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 40 единиц своей продукции и у него осталось только 50 – 40 = 10 единиц, получим х12=min10,85=10. После этого объемы 1-го производителя полностью реализованы и из рассмотрения выпадает первая строка таблицы. В оставшейся таблице снова находим «северо-западный угол» и т.д. В результате получаем исходное распределение поставок (см. табл. 4.3.3). Число заполненных клеток в полученном распределении оказалось равным m+n–1 = 3+3–1 = 5. Это не случайно. Действительно, на каждом шаге (кроме последнего) из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец и строка. Поэтому число заполненных клеток на единицу меньше, чем сумма числа строк и столбцов, т.е. равно m+n–1. Справедлива теорема (которую мы примем без доказательств) утверждающая, что в оптимальном решении число заполненных клеток (т.е. основных, так называемых базисных переменных) должно быть равно m+n–1. Существенный недостаток метода “северо-западного угла” состоит в том, что он построен без учета значений транспортных издержек. Можно модифицировать данный метод, избавившись от этого недостатка: на каждом шаге максимально возможную поставку следует давать не в “северо-западную” клетку оставшейся таблицы, а в клетку с наименьшим значением транспортных издержек. При этом распределение поставок оказывается, вообще говоря, ближе к оптимуму, чем распределение, полученное методом “северо-западного угла”. Такой метод получения исходного плана называется методом наименьших затрат. Исходный план, полученный данным методом, приведен в табл. 4.3.4. Студентам предоставляется право самостоятельно убедиться в справедливости последнего утверждения. 4.3.3. Распределительный метод решения транспортной задачи. Рассмотрим сейчас так называемый распределительный метод решения транспортной задачи. Этот метод довольно сложен и неудобен для решения практических задач, однако мы его подробно рассмотрим, т.к. этот метод позволяет понять основные идеи, лежащие в основе решения задач линейного программирования и, в частности, транспортных задач. Вернемся к нашему примеру и возьмем базисный план, построенный методом северо-западного угла (табл. 4.3.3). Соответствующие данному плану суммарные транспортные затраты (значение целевой функции) F=750. Чтобы определить, является ли полученный план оптимальным, необходимо «оценить» различные варианты, связанные с неиспользованием клеток, в которых нет поставок (выделенных чисел). Таких клеток в нашем примере четыре. Посмотрим, что произойдет с таблицей, если дать единичную поставку в одну из пустых клеток, например в (2,1). Чтобы не нарушался баланс по строкам и столбцам необходимо уменьшить на единицу поставку в клетки (2,2) и (1,1). Уменьшив поставку в (1,1) мы должны увеличить на единицу поставку в клетку (1,2). Заметим, что последнее изменение восстановило баланс по столбцу 2, нарушенный уменьшением поставки в клетку (2,2). Мы получили новый допустимый план поставок (см. табл. 4.5). Таблица 4.3.5 40 85 55 50 2 39 1 11 5 60 3 1 4 59 3 70 4 6 15 6 55 Заметим, что число ненулевых поставок (выделенных чисел) здесь превышает m+n–1, т.е. этот допустимый план не является базисным. Перераспределяя поставки мы прошли по четырем клеткам. Путь нашего движения образовал так называемый цикл (цепь, контур). Представим этот цикл на рис. 4.3.1. На нем изображены клетки, в которых будем менять поставки (слева от каждой клетки написан в скобках ее номер). (1,1) 2 – (1,2) 1 + 40 10 (2,1) 3 + (2,2) 4 – 60 Рис. 4.3.1 При этом знаком “+” помечены те клетки, поставка в которых увеличится (положительные вершины). Знаком “–“ отмечены клетки, в которых поставка уменьшится (отрицательные вершины). Для циклов в транспортной задаче характерны следующие особенности: а) цикл является замкнутым многоугольником; б) вершинами цикла являются клетки таблицы, причем одна из вершин – пустая клетка, а все остальные – клетки с поставками базисного плана (с выделенными числами); в) все углы цикла прямые и каждый отрезок цикла, ограниченный двумя вершинами, целиком принадлежит к одному столбцу или к одной строке таблицы; г) в цикле четное число вершин; д) отрезки цикла могут проходить заполненные поставками клетки, не являющиеся вершинами данного цикла; е) в цикле одинаковое количество положительных и отрицательных вершин. Цикл, сохраняя все перечисленные свойства, может иметь самую различную форму, но всегда для любой пустой клетки цикл пересчета существует, причем единственный (доказательство этого утверждения опускаем). Введем теперь понятие оценки пустой клетки. Так же как и в общей задаче линейного программирования поставим вопрос следующим образом: на сколько изменится значение целевой функции, после совершения единичной поставки в рассматриваемую пустую клетку? Рассмотрим табл. 4.3.5. Записав единичную поставку в клетку (2.1), мы увеличили целевую функцию на 3 (с21 =3). Уменьшив поставку в клетку (1,1) на единицу, мы уменьшили значение целевой функции на 2 (с11 =2). Увеличив поставку в клетку (1.2), мы увеличили целевую функцию на 1 (с12 =1). И, наконец, уменьшив поставку в клетку (2,2) на единицу, мы уменьшили значение целевой функции на 4 (с22=4). В итоге целевая функция изменилась на 3–2+1–4= –2 (т.е. уменьшилась на 2). Эту величину и будем называть оценкой пустой клетки (i,j) и обозначать еij. Отметим, что оценка может быть как отрицательная, так и положительная. Только что мы вычислили е21 = –2. Значит каждая единичная поставка в клетку (2,1) будет уменьшать значение целевой функции на 2. Чем больше будет величина поставки в клетку (2,1), тем лучше будет план поставок. Очевидно, наибольшее значение поставки в клетке (2,1) будет равно величине меньшей из поставок в отрицательных вершинах цикла. В противном случае в одной из этих вершин появится отрицательная поставка, что противоречит условиям задачи. Наибольшее значение х21 в данном случае равно 40 (перепоставка из отрицательной вершины (1,1)). Принимая х21 = 40, для сохранения баланса по строкам и столбцам корректируем на эту величину поставки в остальных вершинах цикла: х11 = 0, х12 = 50, х22 = 20. Получим новый базисный план (клетка (1,1) освободилась от поставки). Транспортные издержки этого плана (см. табл. 4.3.6) изменились на е21х21= –240 = –80, т.е. уменьшились на 80. Суммарные транспортные затраты для данного распределения можно посчитать и по общей формуле: F = 150 +340 +420 +615 +655=670. Мы видим, что и по общей формуле расчета суммарные транспортные затраты уменьшились на 750 – 670 = 80 единиц. Таблица 4.3.6 40 85 55 50 2 1 50 5 60 3 40 4 20 3 70 4 6 15 6 55 Итак, базисный план находить мы умеем (метод северо-западного угла или метод наименьших затрат). Научились определять оценки пустых клеток с помощью циклов и перераспределять по цепи поставки. Этого достаточно, чтобы решить транспортную задачу. Общий ход решения таков: 1. Находим исходный базисный план. 2. Для пустых клеток определяем оценки еij, пока не найдем клетку с отрицательной оценкой. 3. В эту клетку записываем максимально возможную поставку, производя необходимую корректировку поставок в вершинах соответствующего цикла. В результате получаем новый базисный план, лучший чем предыдущий. 4. Для нового базисного плана выполняем опять процедуру 2. Если все оценки еij  0, то план поставок улучшить невозможно (суммарные транспортные издержки не уменьшаются), значит, полученный на последнем шаге план поставок оптимальный. Если существует хотя бы одна клетка с отрицательной оценкой – переходим к процедуре 3. Будем придерживаться этого общего алгоритма решения для улучшения нашего нового базисного плана(табл. 4.3.6). Определим оценку клетки (1,3) с помощью цикла (рис. 4.3.2). (1,2) 1 – (1,3) 5 + 50 е13 =5 –1 + 6 – 6 = +4 (3,2) 6 + (3,3) 6 – 15 55 Рис. 4.3.2 Значит давать поставку в клетку (1,3) невыгодно – приращение целевой функции положительное, т.е. это приведет к удорожанию плана перевозок. Определим оценку следующей пустой клетки (2,3) с помощью цикла (рис. 4.3.3). (2,2) 4 – (2,3) 3 + 20 е23 =3 – 4 + 6 – 6 = –1 (3,2) 6 + (3,3) 6 – 15 55 Рис. 4.3.3 Следовательно рассматриваемый план не оптимален и может быть улучшен, если дать поставку (максимально возможную) в клетку (2,3). Очевидно, максимально возможная величина поставки х23 = 20, что изменит значение целевой функции на –120 = –20. Скорректировав соответственно поставки х22=0, х32 =35, х33 =35, получаем новый базисный план (табл. 4.3.7). Таблица 4.3.7 40 85 55 50 2 1 50 5 60 3 40 4 3 20 70 4 6 35 6 35 Суммарные транспортные затраты для данного распределения: F = 150 +340 +320 +635 +635=650. Проверим этот план на оптимальность. Для этого нужно узнать, нет ли отрицательных оценок пустых клеток. Рассмотрим клетку (3,1). Цикл для нее изображен на рис. 4.3.4. (2,1) 3 – (2,3) 3 + 40 20 е31 =4 –3 +3 – 6 = –2 (3,1) 4 + (3,3) 6 – 35 Рис. 4.3.4 Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать максимально возможную поставку в эту клетку х31= 35. Целевая функция должна уменьшиться на 235 = 70. Скорректировав соответственно в вершинах цикла поставки х21=5, х23 =55, х33 =0, получаем новый базисный план (табл. 4.3.8). Таблица 4.3.8 40 85 55 50 2 1 50 5 60 3 5 4 3 55 70 4 35 6 35 6 Суммарные транспортные затраты для данного распределения: F = 150 +35 +355 +435 +635=580, т.е., как мы и предполагали, уменьшились на 650 – 580 = 70. Проверим теперь этот план на оптимальность. Для этого опять вычисляем оценки пустых клеток. Рассмотрим клетку (1,1). Цикл для нее изображен на рис. 4.3.5. (1,1) 2 + (1,2) 1 – 50 е11 = +2 –1 +6 –4=+3 (3,1) 4 – (3,2) 6 + 35 35 Рис. 4.3.5 Рассмотрим клетку (2,2). Цикл для нее изображен на рис. 4.3.6. (2,1) 3 – (2,2) 4 + 5 е22= +4 –6 +4 –3= –1 (3,1) 4 + (3,2) 6 – 35 35 Рис. 4.3.6 Значит, и этот план не оптимальный. Его можно улучшить, если дать максимально возможную поставку в эту клетку: х22 = 5. Целевая функция уменьшается на 15 = 5. Скорректировав соответственно в вершинах цикла поставки х21 =0, х31 =40, х32 =30, получаем новый базисный план (табл. 4.3.9). Суммарные транспортные затраты составят: F = 150 + 45 +355 +440 +630=575, что как раз на 5 единиц меньше предыдущего значения целевой функции. Этот план оптимальный, оценки всех пустых клеток (е11, е13 , е21, е32) неотрицательны! Таблица 4.3.9 40 85 55 50 2 1 50 5 60 3 4 5 3 55 70 4 40 6 30 6 Студентам предоставляется возможность самим убедиться, что этот план оптимальный. Основным недостатком распределительного метода является необходимость построения циклов с целью определения оценок клеток. Так, при таблице 25 строк на 25 столбцов на каждом шаге для проверки оптимальности плана надо строить mn – (m+n–1) = 2525 – (25+25–1) = 576 циклов. В некоторых случаях циклы имеют множество вершин и довольно сложную конфигурацию. 4.3.4. Метод потенциалов. Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов. Этот способ имеет свои разновидности. Мы рассмотрим одну из них, предложенную Дж.Данцигом в 1951 году и названную им методом МОДИ. Следует отметить, что Л.В.Канторовичем еще в 1940 году был разработан метод, отличающийся от метода МОДИ лишь весьма несущественными деталями. Свой метод Л.В.Канторович назвал методом потенциалов. Мы так и будем его называть. Идея метода заключается в том, что для определения оценок предварительно находятся некоторые числа (они и называются потенциалами), с помощью которых легко вычисляются оценки любой пустой клетки. Потенциалы ставятся в соответствие каждой строке и каждому столбцу. Потенциал i-й строки обозначим ui, а потенциал j-го столбца vj. Потенциалы определяются исходя из единственного требования: для каждой занятой клетки (i,j) алгебраическая сумма потенциалов i-й строки и j-го столбца должна быть равна транспортным издержкам сij , т.е. справедливо: сij = ui+ vj, ui = сij – vj , vj = сij – ui (4.3.6) Когда через транспортные издержки занятых клеток определены потенциалы всех строк и столбцов, то оценки каждой пустой клетки определяются по формуле: еij = сij – (ui+ vj). (4.3.7) Как же определяются потенциалы? Можно начать с любого столбца или строки и назначить в качестве их потенциала произвольное число. Произвольно назначается только этот первый потенциал, все остальные рассчитываются по формулам (4.3.6). Проиллюстрируем это на новом примере решения транспортной задачи. В табл. 4.3.10 приведены условия нового примера с базисным планом, полученным методом северо-западного угла. Примем произвольно, например, для 2-й строки потенциал u2=10. Тогда по формулам (4.3.6) можно вычислить потенциалы 2-го и 3-го столбца, а именно: v2 = с22 – u2 = 5 – 10 = –5, v3 = с23 – u2 = 7 – 10 = –3. Таблица 4.3.10 АiВj 55 90 40 30 20 ui 80 5 55 4 25 3 2 1 9 75 3 5 65 7 10 5 3 10 45 5 4 3 30 4 15 5 6 35 2 3 4 5 15 6 20 7 vj –4 –5 –3 –2 –1 Теперь, используя уже вычисленные потенциалы v2 и v3, находим потенциалы 1-й и 3-й строки: u1 = с12 – v2 = 4 – (–5) = 9, u3 = с33 – v3 = 3 – (–3) = 6. А теперь, используя уже вычисленные потенциалы u1 и u3, находим потенциалы 1-го и 4-го столбца: v1 = с11 – u1 = 5 – 9 = –4, v4 = с34 – u3 = 4 – 6 = –2. Нам осталось вычислить потенциалы 4-й строки и 5-го столбца: u4 = с44 – v4 = 5 – (–2) = 7, v5 = с45 – u4 = 6 – 7 = –1. Зная потенциалы всех столбцов и строк по формуле (4.3.7) вычисляем оценки любой пустой клетки. В данном примере е13 = с13 – (u1+ v3) =3 – (9 –3) = –3, е14 = с14 – (u1+ v4) =2 – (9 –2) = –5, е15 = с15 – (u1+ v5) =1 – (9 –1) = –7, е21 = с21 – (u2+ v1) =3 – (10–4) = –3, е24 = с24 – (u2+ v4) = 5 – (10–2) = –3, е25 = с25 – (u2+ v5) = 3 – (10–1) = –6, е31 = с31 – (u3+ v1) = 5 – (6–4) =3, е32 = с32 – (u3+ v2) = 4 – (6–5) =3, е35 = с35 – (u3+ v5) = 5 – (6–1) =0, е41 = с41 – (u4+ v1) = 2 – (7–4) = –1, е42 = с42 – (u4+ v2) = 3 – (7–5) =1, е43 = с43 – (u4+ v3) = 4 – (7–3) =0. Найдя отрицательную оценку перемещаем в соответствующую клетку поставку по циклу, как и в распределительном методе. Можно найти сначала все отрицательные оценки, а затем выбрать клетку, перемещение поставки в которую даст наибольший эффект, т.е. наибольшую величину уменьшения целевой функции. Заметим, что эта величина зависит как от значения оценки, так и от максимально допустимой поставки, которую можно дать в данную клетку. Студентам предоставляется право самостоятельно довести решение до конца. Оптимальное решение приведено в табл. 4.3.11. Таблица 4.3.11 АiВj 55 90 40 30 20 80 5 4 50 3 2 30 1 75 3 55 5 7 5 3 20 45 5 4 5 3 40 4 5 35 2 3 35 4 5 6 4.3.5. Вырожденные случаи. Открытая транспортная задача. Некоторые замечания по частным случаям, которые могут встретиться при решении. 1. Если на некотором шаге построения базисного плана из рассмотрения выпадают одновременно и строка и столбец (случай вырождения), можно использовать следующий прием: дать нулевую (фиктивную) поставку в произвольную еще не занятую клетку данной строки или столбца. (Тем самым сохраняется число занятых клеток m+n–1 для базисного распределения поставок). 2. Если в отрицательных вершинах цикла, по которому перераспределяется поставка, две или более минимальных поставок, то все они при перераспределении обратятся в нуль. Так как на каждом шаге число занятых клеток сохраняется в количестве m+n–1, то из этих “нулевых” клеток образуется только одна пустая клетка, а остальные считаются заполненными поставкой равной 0. 3. Если мы нашли клетку с отрицательной оценкой и построили соответствующий цикл перераспределения, в одной из отрицательных вершин которого находится нулевая поставка, то следует переместить эту нулевую поставку (значение целевой функции при этом не изменится), а затем вновь определять оценки пустых клеток в полученном базисном плане. Рассмотрим некоторые моменты, имеющие практическое значение, но усложняющие постановку транспортной задачи: 1. Обязательные поставки. Независимо от оптимальных расчетов некоторому поставщику вменяется определенный объем поставки некоторому потребителю (например, определенная марка бетона производится только на таком-то заводе, а некоторому потребителю необходимо определенное количество данной марки). В этом случае на величину обязательных поставок корректируются мощности и потребности, и после этого решается задача. 2. Ограничения пропускной способности. Ранее мы исходили из того, что от любого поставщика любому потребителю можно перевозить любое количество продукта (в пределах мощности и спроса). В реальных задачах часто приходится учитывать пропускную способность коммуникаций (особенно железных дорог). Самый простой способ учитывать пропускную способность состоит в следующем: Пусть поставка в клетку (i,j) ограничена числом, строго меньшим Вj. Столбец j, соответствующий потребителю с ограниченной пропускной способностью, разбивается на два столбца, в одном спрос принимается равным ограничению, а в другом – остатку. Показатели транспортных затрат одинаковы для этих двух столбцов за исключением клетки (i,j) в столбце, где спрос равен разности (остатку). Здесь сij принимается очень большим, блокирующим какую-либо поставку в эту клетку. До сих пор мы рассматривали закрытую транспортную задачу, т.е. при условии баланса спроса и объемов производства (мощностей). В практических задачах это условие далеко не всегда выполняется. При нарушении баланса возникает открытая транспортная задача, которая решается сведением ее к закрытой транспортной задаче. При превышении суммарной мощности над суммарным спросом на величину  вводится дополнительный столбец так называемого фиктивного потребителя со спросом равным . Показатели сin+1 (i=1,2,…,m) в этом столбце выбираются произвольно, но с одним условием, что все они равны между собой. Удобнее всего принимать их равными 0. Далее задача решается как закрытая. Аналогично, при превышении суммарного спроса над суммарной мощностью на величину  вводится дополнительная строка так называемого фиктивного поставщика с мощностью равной  и с нулевыми транспортными издержками. Тема 4.4. Математические основы сетевого моделирования 4.4.1. Построение сетевых графиков. Методы сетевого моделирования применяются при планировании и управлении разработкой крупных народнохозяйственных комплексов, научными исследованиями, конструкторской и технологической подготовкой производства, освоения новых видов изделий, строительством и реконструкцией, капитальным ремонтом основных фондов. Сетевое моделирование основано на применении так называемой сетевой модели комплекса взаимосвязанных работ, направленных на достижение определенной цели. Первые системы, использующие сетевые модели, были применены в США в конце 50-х годов и получили названия СРМ (английская аббревиатура метода критического пути) и РЕRT(метод оценки и обзора программы). Система СРМ была впервые применена при управлении строительными работами, метод РЕRT – при разработке ракетных систем “Поларис”. В России работы по сетевому планированию начались в 60-х годах. Тогда эти методы нашли применение в строительстве и научных разработках. В дальнейшем сетевые методы стали широко применяться и в других областях народного хозяйства. Система сетевого планирования и управления позволяет: а) формировать календарный план реализации некоторого комплекса работ; б) выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы; в) осуществлять управление комплексом работ с прогнозированием и предупреждением возможных срывов в ходе работ; г) повышать эффективность управления в целом при четком распределении ответственности между руководителями разных уровней и исполнителями работ. Диапазон применения методов сетевого планирования и управления весьма широк: от задач, касающихся деятельности отдельных лиц, до проектов, в которых участвуют сотни организаций и десятки тысяч людей. Для того чтобы составить план работ по осуществлению больших и сложных проектов, состоящих из тысяч отдельных исследований и операций, необходимо описать его с помощью математической модели. Таким средством описания проектов (комплексов работ) и является сетевая модель. Сетевая модель содержит информацию о параметрах работ и их логической взаимосвязи. Основу логической взаимосвязи работ составляют: а) технологическая зависимость работ, в) ресурсные зависимости. Графическое изображение сетевой модели будем называть сетевым графиком. Сетевой график состоит из двух основных элементов: дуг (стрелок) и вершин Вершины Дуги (события) (работы) Рис. 4.4.1 Дуги графика обычно задают работы; вершины, которые какие-либо дуги соединяют, называют событиями. Дуга (стрелка) используется для отображения: а) действительной работы, б) работы – ожидания, в) фиктивной работы. Под действительной работой будем понимать процесс, требующий для своего осуществления затрат времени и ресурсов (например, возведение фундаментов, монтаж каркаса и т.п.). Под работой – ожиданием будем понимать процесс, требующий для своего осуществления затрат времени, но не требующий затрат ресурсов (например, твердение бетона, охлаждение цементной печи т.п.). Фиктивная работа используется для отображения взаимосвязи между событиями. Событие отображает результат одной или совокупный результат нескольких работ, представляющий возможность начать одну или несколько непосредственно следующих (из данного события) работ. Если работа отображается дугой, примыкающей к некоторому событию своим концом, то такая работа называется входящей в данное событие. Рис. 4.4.2. Входящие работы Если работа отображается дугой, примыкающей к некоторому событию своим началом, то такая работа называется выходящей из данного события. Рис. 4.4.3. Выходящие работы Событие считается свершившимся, если окончены все входящие в него работы. Работы, выходящие из события, могут быть начаты только после свершения данного события. Таким образом, работы, входящие в событие, должны быть выполнены ранее работ, выходящих из этого события. Событие, за которым непосредственно следует работа (из которого работа выходит) называется начальным событием данной работы. Событие, которому работа непосредственно предшествует, называется конечным событием данной работы. Топологией сетевого графика называется его структура, определяющая взаимозависимость событий и работ. События кодируются числами. При правильной кодировке код начального события должен быть меньше кода конечного события. Работы обозначаются с помощью кодов начального и конечного событий. Если начальное событие имеет код i, а конечное событие код j, то работу, их связывающую, будем обозначать (i,j). Правила построения сетевого графика Условимся знаком  обозначать предшествование работ друг другу, т.е. запись А  В означает, что работа А должна быть завершена до начала работы В. 1. Если работы А и В предшествуют работе С (А, В  С), то это изображается следующим образом: А С В 2. Если А, В  С и В  Д, то изображение А С А С Е В Д В Д неправильно правильно В правильном фрагменте используется фиктивная работа Е. Поскольку на работу Е не затрачиваются ни время, ни ресурсы, заданные отношения упорядочения выполняются. 3. Если для начала работ А и В необходимо свершение события i, а окончание работ А и В необходимо для свершения события j, то такая ситуация изображается так: А А Е В В неправильно правильно Любые два события должны быть непосредственно связаны не более чем одной работой (стрелкой).Такой способ изображения вводится для того, чтобы работы А и В различались при обозначении с помощью кодов начального и конечного события. Работу А обозначим тогда (i,l), а работу В – (i,j). Работа Е-( l,j) – фиктивная. 4. Если для начала работы В достаточно выполнить только часть работы А, то эта ситуация изображается А В А1 А2 В неправильно правильно т.е. работа А разбивается на две части (работы) А1 и А2, где А1та часть работы А, после которой можно начинать работу В. 5. Если результат работы В нужен не к началу работы А, а к некоторому моменту в процессе ее выполнения, то это изображается так: В А А1 А2 В неправильно правильно 6. В сетевом графике не должно быть замкнутых контуров (циклов, петель), т.е. путей, соединяющих некоторые события посредством стрелок с ними же самими. 7. В сетевом графике может быть только одно событие, которому не предшествует ни одна работа. Это событие назовем исходным. Исходное событие отражает необходимые условия для начала выполнения всего комплекса работ. 8. В сетевом графике может быть только одно событие, из которого не выходит ни одна работа. Это событие назовем завершающим. Завершающее событие отражает конечную цель выполнения всего комплекса работ. В последующем будут рассмотрены случаи, когда требование единственности исходного и завершающего событий необязательно. Кроме выше приведенных примеров фиктивные работы (или события) могут вводиться и в ряде других случаев, например, для отражения зависимости событий, не связанных с реальными работами. На сетевом графике такие фиктивные работы (связи) показываются пунктирными стрелками. Кроме того, фиктивные работы могут вводиться для отражения реальных отсрочек и ожидания. 4.4.2. Временные параметры сетевого графика Каждой дуге сетевого графика поставим в соответствие некоторое число, соответствующее продолжительности работы, отображаемой данной дугой. Число, приписанное дуге (i,j), будем называть длиной дуги и обозначать tij. Множество дуг, упорядоченное таким образом, что конечное событие одной из них является начальным событием другой, называется путем. Рассмотрим небольшой пример. Рис. 4.4.4 Будем различать четыре вида пути: а). Полный путь – путь, начало которого совпадает с исходным событием сети, конец – с завершающим, например, (0,1)–(1,4)–(4,5)–(5,6) или (0,2)–(2,4)–(4,6). б). Путь, предшествующий событию – это путь от исходного события до данного события, например, для события 4 предшествующими путями будут (0,2)–(2,4) и (0,1)–(1,4). в). Путь, следующий за событием – это путь от данного события до завершающего, например, для события 2 это пути (2,4)–(4,5)–(5,6) и (2,4)–(4,6). г). Путь между двумя событиями – путь, начало и конец которого совпадают с соответствующими событиями, например, между событиями 2 и 5 лежит путь (2,4)–(4,5). Под длиной пути будем понимать продолжительность выполнения всей последовательности работ, составляющих данный путь. Таким образом, длина пути равна сумме длин всех дуг данного пути. Наиболее продолжительный полный путь в сетевом графике называется критическим. Критическими называются также работы и события, расположенные на этом пути. Рассмотрим еще один пример сетевого графика. Цифры на каждой дуге означают продолжительности работ. 4 3 3 2 3 6 4 5 5 1 8 2 10 Рис. 4.4.5 Здесь полными путями будут: путь (0,1)-(1,3)-(3,6)-(6,8) продолжительностью 2+4+3+3=12, путь (0,3)-(3,6)-(6,8) продолжительностью 3+3+3=9, путь (0,2)-(2,3)-(3,6)-(6,8) продолжительностью 5+6+3+3=17, путь (0,2)-(2,5)-(5,7)-(7,8) продолжительностью 5+1+8+5=19, путь (0,2)-(2,5)-(5,8) продолжительностью 5+1+4=10 и путь (0,2)-(2,4)-(4,7)-(7,8) продолжительностью 5+2+10+5=22. Перебрав все полные пути, мы видим, что последний путь имеет наибольшую продолжительность, поэтому он и является критическим (далее мы приведем способ определения критического пути без перебора всех полных путей). Продолжительность критического пути составляет 22 (например, дня), т.е. для проведения всего комплекса работ понадобится 22 дня. Быстрее комплекс выполнить нельзя, так как для достижения цели (завершающего события) работы критического пути надо выполнить обязательно. Определив критический путь, мы тем самым установили критические события сети 0, 2, 4, 7, 8 и критические работы (0,2), (2,4), (4,7), (7,8). Критический путь имеет особое значение в системах сетевого планирования и управления. Действительно, срыв сроков выполнения какой-либо работы критического пути влечет срыв срока выполнения всего комплекса в целом, и, с другой стороны, для сокращения продолжительности проекта необходимо в первую очередь сокращать продолжительность работ, лежащих на критическом пути. Временные параметры сети состоят из временных параметров событий и временных параметров работ. Рассмотрим содержание и алгоритм расчета параметров событий. Временем Тj наступления (или свершения) события j считается момент окончания всех работ, входящих в это событие. Минимальное (самое раннее) время Тjо наступления события j равно длине максимальному из путей, предшествующих данному событию. Очевидно, что это время является и самым ранним временем начала работ, выходящих из этого события. Например, в последнем примере событие 3 может свершиться не ранее, чем через 11 дней от исходного события, т.к. наибольшая длина пути, предшествующего данному событию (пути (0,2)-(2,3)) равна 11. Критическим временем выполнения комплекса работ будем называть раннее время наступления завершающего события. Критическое время – это минимальное количество времени, необходимое для выполнения всего комплекса работ, очевидно, совпадает с длиной критического пути. Для вычисления Тjо необходимо сначала рассмотреть все события i, соединенные дугой (i,j) с данным событием j, вычислить для них ранние времена и при этом на каждом шаге использовать формулу Тjо =max Тiо + tij (4.4.1) i Вычисления начинаются с исходного события и продолжаются до тех пор, пока не будет достигнуто завершающее событие всей сети. Проиллюстрируем алгоритм вычисления ранних времен на последнем примере. Принимаем Т0о =0. Поскольку в событие 1 входит только одна работа (0,1) продолжительностью t01=2, то Т1о = Т0о + t01 =0+2=2. Рассмотрим далее событие 2 (Заметим, что событие 3 пока рассматривать нельзя, так как срок Т2о еще неизвестен). Таким образом, Т2о =Т0о + t02 =0+5=5. Перейдем теперь к событию 3. Поскольку в него входят три дуги (0,3),(2,3) и (1,3), то Т3о =max Тiо + ti3= max 0 + 3; 2+4; 5+6=11. i=0,1,2 Вычисления продолжаем аналогичным образом, пока не будут определены значения Тjо для всех событий j. Имеем Т4о = Т2о + t24 = 5 + 2 = 7, Т5о = Т2о + t25 = 5 + 1 = 6, Т6о = Т3о + t36 = 11 + 3 = 14, Т7о =max Тiо + ti7= max7+10; 6+8=17, i=4,5 Т8о =max Тiо + ti8= max6+4; 14+3; 17+5=22. i=5,6,7 На этом вычисления Тiо заканчиваются. Теперь от завершающего события к исходному (справа налево) определяем Тi1 - максимально допустимый (поздний) срок завершения всех работ, входящих в данное событие, при котором критическое время выполнения всего комплекса работ останется неизменным. Если обозначить n – завершающее событие сети, то Тn1 = Тn0 является отправной точкой алгоритма вычисления поздних сроков. В общем виде для любого события i, Тi1 =min  Тj1 – tij для всех дуг (i,j). (4.4.2) j Вычислим значения Тi1 на последнем примере (рис.4.4.5). Т81 = Т80=22, Т71 = Т81 – t78 = 22 – 5 = 17, Т61 = Т8о – t68 = 22 – 3 = 19, Т51 =min  Тj1 – t5j= min17–8; 22 – 4=9, j=7,8 Т41 = Т71 – t47 = 17 – 10 = 7, Т31 = Т61 – t36 = 19 – 3 = 16, Т21 =min Тjо – t2j= min16–6; 7 – 2; 9 – 1=5, j=3,4,5 Т11 = Т31 – t13 = 16 – 4 = 12, Т01 =min Тj1 – t0j= min12–2; 5 – 5; 16 – 3=0. j=1,2,3 Определим резерв времени Ri i-го события как разность между поздним и ранним сроками его свершения: Ri = Тi1 – Тi0 (4.4.3) Резерв времени события показывает, на какой допустимый период времени можно задержать наступление данного события, не вызывая при этом увеличения срока выполнения комплекса работ. Сведем результаты вычислений значений Тi1 , Тiо и Ri в таблицу: Таблица 4.4.1 Номер события Сроки свершения события Резерв времени Ri Ранний Тiо Поздний Тi1 1 2 12 10 2 5 5 3 11 16 5 4 7 7 5 6 9 3 6 14 19 5 7 17 17 8 22 22 Теперь, используя данные табл. 4.4.1, можно определить работы критического пути (без полного перебора полных путей). Работа (i,j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям: Тi0=Тi1 Тjо = Тj1 (4.4.4) Тjо – Тiо =Тj1 – Тi1 = tij По существу, эти условия означают, что между ранним сроком начала (окончания) и поздним сроком начала (окончания) критической работы запас времени отсутствует. Условиям (4.4.4) удовлетворяют работы (0,2), (2,4), (4,7) и (7,8), т.е. они образуют критический путь, в чем мы и ранее убедились перебором всех полных путей. Временные параметры работ. Различают несколько разновидностей резервов времени работ, мы рассмотрим два основных вида: полный резерв и свободный резерв. Полный резерв работы (i,j) определяется по формуле: Rпij=Тj1 – Тi0 – tij (4.4.5) Rпij показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения всего комплекса работ не изменится. Кроме того, полный резерв времени есть разность между критическим временем и длиной максимального полного пути, проходящего через эту работу. Полный резерв критических работ равен 0. У некритических работ Rпij0. При использовании полного резерва времени только для одной работы резервы времени остальных работ, лежащих на максимальном пути, проходящем через нее, будут полностью исчерпаны, т.е. увеличение продолжительности некритической работы за счет использования всего ее полного резерва обязательно влечет появление нового критического пути, в состав которого войдет эта работа. Опоздание начала некритической работы (i,j) по сравнению с Тi0 на всю величину ее полного резерва влечет за собой необходимость начинать все работы, выходящие из события j в наиболее позднее допустимое время Тj1 наступления этого события. Свободный резерв времени Rсij работы (i,j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершаются в свои самые ранние сроки. Rсij=Тj0 – Тi0 – tij (4.4.6) Таким образом, свободный резерв времени может быть использован на увеличение продолжительности данной и предшествующих работ без нарушения резерва времени последующих работ. Для рис. 4.4.5 проведем вычисления по формулам (4.4.5), (4.4.6): Таблица 4.4.2 (i,j) tij Тi0 Тj1 Rпij Rсij (0,1) 2 12 10 (0,2) 5 5 (0,3) 3 16 13 8 (1,3) 4 2 16 10 5 (2,3) 6 5 16 5 (2,4) 2 5 7 (2,5) 1 5 9 3 (3,6) 3 11 19 5 (4,7) 10 7 17 (5,7) 8 6 17 3 3 (5,8) 4 6 22 12 12 (6,8) 3 14 22 5 5 (7,8) 5 17 22 В табл. 4.4.2 приведены результаты расчетов временных параметров работ. Она содержит всю необходимую для построения календарного плана (графика) информацию. Когда полный резерв равен 0, свободный резерв также должен быть равен 0. Однако обратное неверно, поскольку свободный резерв некритической работы также может быть нулевым (например, работы (0,1), (2,3)). Конечным результатом выполняемых на сетевой модели расчетов является календарный график (план). При построении календарного графика необходимо учитывать наличие ресурсов, так как одновременное выполнение некоторых работ из-за ограничений, связанных с рабочей силой, оборудованием, материальными и другими видами ресурсов, может оказаться невозможным. Проблемам оптимизации потребления ограниченных ресурсов на основе сетевых моделей посвящена тема 4.5. Далее на нашем примере (рис. 4.4.5, расчетные данные в табл.4.4.2) иллюстрируется процедура построения календарного плана при отсутствии ограничений на ресурсы. Работы (7,8) (6,8) (4,7) (5,8) (5,7) (3,6) (2,3) (2,5) (2,4) (1,3) (0,3) (0,2) (0,1) 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 22 Рис. 4.4.6 Пояснения к рис. 4.4.6. Стрелками на графике обозначены: критические работы, некритические работы, полные резервы, свободные резервы (как часть полных). Все работы выставлены на графике в ранние сроки начала. 4.4.3. Приведение сетевого графика к заданному сроку. Процедура приведения сетевого графика к заданному сроку не относится к классу оптимизационных задач. На основе анализа сетевого графика нам необходимо принять некоторое целенаправленное решение, а именно, обеспечить окончание комплекса работ к заданному (директивному) сроку. Обозначим его Тдир. Речь не идет о поиске наилучшего (по какому-нибудь критерию) решения, а лишь о целенаправленном решении. Мы рассмотрим процедуру приведения сетевого графика к заданному сроку, которая осуществляется, как правило, при использовании метода РЕRТ или СРМ. Эта процедура не формализована, т.е. не является строгим алгоритмом, как, например, при расчете параметров сетевого графика. Приведение сетевого графика к заданному сроку осуществляется при творческом анализе информации, которую дает сетевой график, и конкретных производственных условий, не отраженных в сетевой модели, так называемых внемодельных факторов. Вначале сравниваем критическое время комплекса работ (Тn0) с директивным. Если Тn0  Тдир, то сокращать ничего не нужно. Если Тn0  Тдир, то критическое время необходимо сократить на величину = Тn0 – Тдир, причем прежде всего сокращению подлежат работы критического пути. Кроме того, необходимо проанализировать пути, содержащие работы, у которых Rпij  . Если эти пути содержат работы критического пути, уже сокращенные на общее количество дней, меньшее , или не содержат таких работ вообще, то и некоторые работы подобных (так называемых, подкритических) путей также необходимо сократить. В противном случае, после сокращения работ критического пути подкритический путь становится новым критическим путем. Какие именно работы и на сколько сокращать – в этом и заключается творчество, базирующееся на доскональном знании производственной ситуации. Сокращение продолжительности работ можно достичь добавлением ресурсов (рабочей силы, механизмов и т.п.). Сокращение отдельных путей можно произвести за счет совмещения (параллельного выполнения) некоторых работ пути, при этом частично изменяется топология сетевого графика. Рассмотрим опять наш пример (рис 4.4.5). Пусть Тдир =18, тогда  = 22 – 18 = 4. Значит, необходимо на 4 дня сократить длину критического пути. Также следует рассмотреть путь, содержащий работы (2,5) и (5,7), так как Rп25 = Rп57 =3  4. Этот путь имеет общие работы с критическим путем – (0,2) и (7,8). Если производственная ситуация позволяет сократить их продолжительность на 2 дня каждую, то критический путь и подкритический (0,2)-(2,5)-(5,7)-(7,8) сокращаются на 4 дня, что нам и требовалось. Рассмотренные нами традиционные сетевые модели обладают рядом недостатков: в таких сетевых моделях адекватно можно отобразить только независимо или последовательно выполняемые работы. Другие схемы выполнения работ (например, параллельное или частично совмещенное их выполнение) не подаются точному описанию. Чтобы отобразить подобные ситуации в традиционных сетевых моделях, прибегают к раздроблению работ. Например, работу «монтаж коробки здания» разбивают на работы «монтаж 1-го этажа», «монтаж 2-го этажа» и т.д., работу «отделка здания» на «отделку 1-го этажа», «отделку 2-го этажа» и т.д. Фрагмент сетевой модели представляется тогда в следующем виде: Монтаж 1 эт. Монтаж 2 эт. Монтаж 3 эт. Отделка 1 эт. Отделка 2 эт. Отделка 3 эт. Такой прием усложняет построение модели, увеличивает число работ сети, делает модель менее гибкой по отношению, например, к последовательности раздробленных работ или к изменению их продолжительностей. Кроме того, не исключено появление календарного плана, при котором работа «монтаж коробки здания» ведется с перерывами, что может быть неприемлемым в связи с требованием использования какого-либо ресурса (бригады, механизма) без простоя. Традиционные сетевые модели, отражая одновариантную технологию и организацию работ, обладают низкой «устойчивостью» по отношению к изменениям, происходящим в объекте моделирования в процессе его функционирования, т.к. даже незначительные изменения в технологии выполнения работ требуют внесения существенных изменений в топологию сети. 4.4.4. Обобщенные сетевые модели. Обобщенные сетевые модели, разработанные В.И.Воропаевым[18] в конце 60-х годов, лишены перечисленных выше недостатков. Основные отличия обобщенных сетевых моделей от традиционных заключаются в следующем: – вводятся дуги отрицательной длины; • разрешается наличие циклов (правда, для обеспечения непротиворечивости модели, только отрицательной длины); • можно задавать «абсолютные» ограничения на сроки свершения любых событий. Обобщенная сетевая модель представляет собой ориентированный граф, который описывается системой неравенств: Тj  Ti+ij (4.4.7) для любой дуги графа и li  Ti  Li, (4.4.8) где Ti – искомые сроки свершения событий, ij – произвольные действительные числа, li и Li – “абсолютные ограничения” (на тех событиях, где они не заданы, принимается li = –, Li =+). Если событие i определяет момент начала работы (i,j), а событие j момент ее окончания, то неравенство (4.4.7) при положительном значении ij совпадает по смыслу с аналогичным неравенством в традиционных сетях, причем ij равно минимальной продолжительности этой работы tijmin. Максимальную продолжительность работы (i,j) задают с помощью отрицательного параметра ji, равного (–tijmax). Требование непрерывности выполнения работы (i,j) реализуется заданием параметров ij = – ji. Если события i и j принадлежат разным работам и связаны дугой (i,j), то она интерпретируется как технологическая зависимость: – при положительном значении ij событие j может свершиться не ранее чем через ij единиц времени после свершения события i; • при отрицательном ij событие i должно наступить не позднее чем через ij единиц времени после свершения события j. 10 -15 8 -12 20 5 -7 11 -11 На приведенном фрагменте обобщенной сетевой модели заданы две работы (1,2) и (3,4), причем продолжительности работ удовлетворяют требованиям: 10  t12  15 и t34=11 (работа (3,4) должна выполняться без перерыва). Начинать работу (3,4) можно не ранее чем через 8 дней, но и не позднее чем через 12 после начала работы (1,2). Закончена работа (3,4) должна быть не ранее чем через 5 дней и не позднее чем через 7 после окончания работы (1,2), кроме того, окончание работы (3,4) технологически связано с началом работы (1,2) – между этими событиями должно пройти не менее 20 дней. Как мы видим даже на этом маленьком примере, обобщенные сетевые модели способны обеспечивать более адекватное моделирование технологических процессов при управлении проектами, чем традиционные сетевые модели. Особенно большое значение такие модели приобретают при решении задач оптимизации планов по различным критериям, связанным с использованием ресурсов и соблюдением специальных технологических и организационных требований. К таким требованиям относится, например, условие непрерывности выполнения работ исполнителями на одном или разных проектах, непрерывность или ограничение перерывов между работами, ограничение сроков выполнения некоторых комплексов работ и т.п. Обобщенные сетевые модели позволяют без существенных изменений использовать основные понятия традиционного сетевого планирования, такие как ранние и поздние сроки, резервы времени, критический путь и др. Вычисление этих параметров производится с помощью некоторым образом модифицированных алгоритмов, рассмотренных нами выше для традиционных сетей. Высокая степень гибкости и устойчивости обобщенных сетевых моделей при практически том же порядке трудоемкости подготовки исходных данных по сравнению с традиционными моделями позволяет использовать их в качестве основы для развития и широкого внедрения методов моделирования и оптимизации в системах управления различного назначения. 4.4.5. Вероятностные сетевые модели. Выше рассматривались постановки задач календарного планирования, не учитывающие вероятностный характер процесса проектирования. Однако во многих случаях при планировании и управлении созданием нового проекта продолжительность работ сетевого графика является случайной величиной, подчиненной некоторому закону распределения. Что касается параметров распределения, то последние задаются для каждой работы их ответственными исполнителями на основе либо нормативных данных, либо априорных соображений, либо своего производственного опыта. В первых сетевых моделях (РЕRT) для каждой работы задавались три оценки продолжительности выполнения: - наиболее вероятное время выполнение m; - оптимистическая оценка времени a; - пессимистическая оценка времени b. Наиболее вероятное время определяется как время выполнения работы при нормальных условиях. Оптимистическая и пессимистическая оценки задают размах колебаний продолжительности работы под влиянием неопределенности. Вероятностная сетевая модель типа РЕRT предполагает, что продолжительность любой работы t есть случайная величина, распределенная по закону бета-распределения на отрезке [а,b] с плотностью (t)= C(t – a)p-1(b – t)q-1. Ожидаемая продолжительность работы приближенно определяется как =(а+4m+b)/6. Среднеквадратическое отклонение от среднего значения =(b – a)/6. Вероятностные методы, применяемые в системе PERT. В системе РЕRT с помощью заданных пользователем трех оценок продолжительности всех работ по вышеприведенным формулам вычисляется средняя продолжительность  и ее дисперсия 2. Рассматривая среднее значение как фактическую (детерминированную) продолжительность работы, определяют все временные характеристики сети (и критический путь). При этом продолжительность всего проекта определяется как случайная величина, математическое ожидание которой есть сумма средних продолжительностей работ, находящихся на критическом пути, а дисперсия, аналогично, равна сумме всех дисперсий, при допущении, что продолжительности всех работ независимы. В более общем случае ожидаемое время Mt(i)=M(i) свершения любого i–го события определяется как сумма математических ожиданий времени выполнения работ, лежащих на максимальном пути L между исходным (0) и i–м событиями: M(i)=n=1Mt(i-1,i), если L=0i1i2…in= i и Mt(L)  Mt(L), где L любой другой путь между 0 и i–м событиями. Аналогично определяется и дисперсия времени свершения i–м события: D(i)= 2(i) =Dt(L)=n=1Dt(i-1,i). Предполагая выполненными условия центральной предельной теоремы (см.3.4), закон распределения времени окончания проекта (в общем случае, любого события i), считают близким к нормальному, вследствие чего используют интегральную формулу Муавра-Лапласа. Таким образом, оценка pi вероятности свершения i–го события в запланированный срок tпл(i) вычисляется по формуле: P{t(i)  tпл(i)}=(1/2){Ф[(tпл(i) – M(i)) / (i)]+1}, где Ф – функция Лапласа (таблица ее значений – приложение 2). Вероятность отсутствия резерва времени для момента окончания работы (i,j) оценивают по формуле: P1(j)=1 – Ф[(Т1(j) – Т0(j))/ (j)]. Двухоценочная методика. После анализа большого количества сетевых проектов был построен закон распределения продолжительности выполнения работ с плотностью, зависящей лишь от двух параметров [17]: p(x)=[12/(b – a)4](x – a)(b – x)2. Это распределение относится к классу бета-распределений и имеет следующие параметры: - математическое ожидание М(х)=(3а+2b)/5; - моду m=(2a+b)/3; - дисперсию D(х)= 2(х)=0.04(b – а)2. Методика оценки параметров распределения на основании двух задаваемых временных оценок отличается рядом преимуществ по сравнению с трехоценочной методикой системы PERT, прежде всего, за счет уменьшения объема информации, который требуется от исполнителя работы. Эту методику можно с одинаковым успехом применять как при расчете детерминированных (или близких к ним) сетей, так и при моделировании стохастических сетевых проектов. Рассмотренные нами вероятностные модели и методы определения их временных характеристик использовались большей частью для временного анализа сети и иногда для решения оптимизационных задач типа «время-стоимость». Основные результаты, получаемые в процессе моделирования вероятностных сетей, следующие:  получение с определенным уровнем доверительности минимального и максимального времени выполнения проекта;  получение также с некоторым уровнем уверенности минимального и максимального времени свершения наиболее важных событий;  оценка вероятности попадания некоторого события на критический путь;  оценка вероятности попадания работы на критический путь;  выделение с некоторым уровнем доверительности критического и резервного подграфов. 4.4.6. Стохастические сетевые модели. До сих пор мы рассматривали модели с детерминированной топологией сети. При моделировании сложного проекта нередко наиболее гибкими и полезными оказываются сетевые модели со стохастической структурой. Стохастическую сеть определяют как сеть, содержащую альтернативные узлы (состояния), при этом дуги (работы) характеризуются не только вероятностным распределением продолжительности, но и вероятностью их выполнения. Стохастическая сетевая модель с множеством возможных исходов, являясь дальнейшим развитием традиционных сетей, дает возможность полнее отобразить процесс разработки и создания сложного проекта. Применяемый для анализа стохастических сетевых моделей математический аппарат позволяет вычислять вероятности различных альтернативных исходов, оценивать время их возможной реализации. Стохастическая сетевая модель есть конечный граф G=(,А), где – есть множество детерминированных и альтернативных вершин, отождествляемых с событиями, а технологическая матрица А={pij} задает множество ориентированных дуг, отождествляемых с работами (или связями). Для стохастических сетей 0 pij  1, причем pij =1 определяет работу (i,j) аналогично принятым в традиционных сетях определениям, а 0 < pij < 1 соответствует альтернативному событию i, из которого с вероятностью pij «выходит» работа (i,j). Другими словами pij – вероятность того, что работа (i,j) будет выполнена при условии, что узел i выполнен. Пусть (tij) – плотность распределения времени выполнения работы (i,j). М[х] – математическое ожидание случайной величины х. Вводится условная производящая функция моментов случайной величины tij как Мij(s)=М[еstij], т.е. Мij(s)=  еstij(tij)dtij (для непрерывной случайной величины),  еstij(tij) (для дискретной случайной величины). В частности, Мij(s)=М[еsа] = еsа при tij=а=const, Мij(0)=1. Для каждой дуги (i,j) определяется –функция как ij(s) = pijМij(s). Исходная сеть преобразуется в эквивалентную, используя три базисных преобразования:  последовательные дуги,  параллельные дуги,  петли. Для последовательных дуг (рис.4.4.7) ij jk Рис. 4.4.7 ik(s) = ij(s)jk(s). Для параллельных дуг (рис.4.4.8) a b Рис. 4.4.8 ij(s) = a(s) +b(s). Для петель вида (рис. 4.4.9) a b Рис. 4.4.9 ij(s) = b(s)/[1 - a(s)]. Комбинируя базисные преобразования, любую сеть можно преобразовать в эквивалентную сеть, состоящую из одной дуги (Е-дуги). Цель временного анализа стохастической сети состоит в вычислении математического ожидания и дисперсии времени выполнения сети (или любого ее фрагмента) и вероятности выполнения заключительного (или любого другого события) сети. Здесь используется теория замкнутых потоковых графов, где введенная выше –функция трактуется как соответствующий коэффициент пропускания дуги. Для применения результатов этой теории к открытой сети с искомым параметром Е(s) вводится дополнительная дуга с параметром А(s), соединяющая конечное событие (сток) с начальным (источником). Затем используется топологическое уравнение для замкнутых графов, известное как правило Мейсона [17], следующего вида: 1 – Т(L1) + Т(L2) – Т(L3) +…+ (–1)mT(Lm) + … =0, (4.4.9) где T(Lm) – сумма эквивалентных коэффициентов пропускания для всех возможных петель m-го порядка. Эквивалентный коэффициент пропускания для петли m-го порядка равен произведению коэффициентов пропускания m не связанных между собой петель первого порядка, т.е. T(Lm)=m k=1Tk. Непосредственно из правила Мейсона следует, что 1–А(s)Е(s)=0 или А(s)=1/Е(s). Используя данный результат, в топологическом уравнении (4.4.9) А(s) заменяется на 1/Е(s) и затем оно решается относительно Е(s), тем самым получается эквивалентная –функция для исходной стохастической сети. Поскольку Е(s) = pЕМЕ(s), а МЕ(0)=1, то pЕ=Е(0), откуда следует, что МЕ(s)= Е(s)/pЕ =Е(s) /Е(0). (4.4.10) После получения аналитического выражения для МЕ(s), вычисляют первую и вторую частную производную по s функции МЕ(s) в точке s=0, т.е. 1E=/sМЕ(s)s=0 (4.4.11) 2E=2/s2МЕ(s)s=0 (4.4.12) Первый момент 1E относительно начала координат есть математическое ожидание времени выполнения сети (преобразованной в эквивалентную ей Е-дугу), а дисперсия времени выполнения сети равна разности между вторым моментом 2E и квадратом первого, т.е. 2= 2E – (1E) 2. (4.4.13) Таким образом, описанный выше аппарат позволяет вычислять временные параметры любых интересующих пользователя событий стохастической сети, а также определять вероятность их наступления. Используя полученную информацию, можно с помощью неравенства Чебышева оценивать вероятность любых доверительных интервалов времени окончания проекта при произвольных законах распределения времени выполнения отдельных операций. Если время выполнения каждой операции имеет нормальное распределение, то результирующее время также нормально распределено. В этом случае можно получить вероятностные оценки времени выполнения проекта, используя интегральную теорему Муавра-Лапласа. Кроме того, при достаточно большом числе работ в сети и выполнении некоторых условий (в частности, независимость работ) можно использовать предельную теорему Ляпунова и считать результирующее время выполнения проекта нормально распределенной случайной величиной с характеристиками, вычисленными по выше описанной методике. Таким образом, стохастическая сетевая модель включает все случайные отклонения и неопределенность, возникающие непосредственно во время выполнения каждой отдельной работы. В качестве параметра дуги мы рассматривали время выполнения операции (работы). Можно рассматривать также любой характерный параметр, который обладает аддитивностью по дугам любого пути. Это может быть стоимость работы, количество потребного накапливаемого ресурса и т.п. Следует отметить, что до настоящего времени широкое практическое применение нашли только методы детерминированного сетевого моделирования, некоторые эвристические методы оптимального распределения ресурсов и параметрические методы оценки затрат (преимущественно в сфере воздушных и космических полетов). Хотя точное решение стоимостных задач календарного планирования на основе классических сетевых моделей теоретически найдено (описано в Теме 4.5), но его практическое использование сопряжено с трудностью получения фактических данных о зависимостях «время-стоимость». Каждая из рассмотренных выше моделей имеет свою предметную область, по-своему (более или менее полно) реализует базовые функции управления проектом, и только синтез анализируемых моделей и методов позволяет построить модель, адекватно отражающую процесс реализации сложного проекта в условиях неопределенности, и при этом получить приемлемое в практическом отношении решение сформулированной задачи. 4.4.7. Организационные аспекты применения сетевых моделей. Сетевое планирование и управление комплексами работ (программами, проектами) включает три основных этапа: структурное планирование, календарное планирование и оперативное управление. Этап структурного планирования начинается с разбиения проекта на четко определенные работы (операции). Затем определяются оценки продолжительности работ, и строится сетевая модель. Кстати, при поразительном сходстве независимо разработанных методов РЕRТ и СРМ (упомянутых в самом начале), существенным различием первоначально было то, что в методе СРМ оценки продолжительности работ предполагались детерминированными величинами, а в методе РЕRТ – случайными. Построение сетевой модели на этапе структурного планирования позволяет детально проанализировать все работы и внести улучшения в структуру проекта еще до начала его реализации. Конечной целью этапа календарного планирования является построение календарного графика работ. Выявленным работам критического пути необходимо уделять особое внимание, чтобы закончить проект в директивный срок. Что касается некритических работ, то их резервы времени можно выгодно использовать при задержке выполнения таких работ или с позиций эффективного использования ресурсов. Заключительным этапом является оперативное управление процессом реализации проекта. Этот этап включает использование сетевой модели и календарного графика для составления периодических отчетов о ходе выполнения проекта. Случаи, когда на этапе планирования удается разработать календарный план, в точности соблюдаемый на этапе реализации проекта, встречаются крайне редко. Как правило, некоторые работы выполняются быстрее или медленнее, добавляются новые и упраздняются старые, что, естественно, зависит от конкретных условий. При возникновении таких отклонений от исходного календарного плана возникает необходимость разработки нового плана для остальной части проекта. В этом случае уже законченным работам приписываются нулевые значения продолжительности. Частично выполненным работам приписываются оценки продолжительности, соответствующие их незавершенному объему. В сеть вносятся также структурные изменения, т.е. исключаются работы, которые по каким-либо причинам стали излишними, и вводятся работы, не предусмотренные ранее, но необходимые в будущем. После этого рассчитывается новый календарный план и оценивается возможное изменение продолжительности проекта. В реальных условиях частые корректировки календарного плана, как правило, требуются на начальном этапе реализации проекта. Затем процесс выполнения переходит в установившийся режим и число требуемых корректировок календарного плана существенно сокращается. Тема 4.5. Оптимизация потребления ресурсов на основе сетевых моделей 4.5.1. Основные понятия. Коэффициент напряженности. В теме 4.4 были рассмотрены сетевые модели без учета ограниченности ресурсов, т.е. задача наилучшего распределения ресурсов как таковая не ставилась. В рассмотренных нами методах использования сетевых моделей основное внимание уделялось срокам выполнения отдельных работ и выявлению наиболее важных (критических и подкритических) цепочек работ, от которых зависит своевременное окончание проекта (ввод объекта в эксплуатацию). Таким образом, характерной особенностью этих методов является классификация информации по степени ее важности с точки зрения завершения всего комплекса работ в установленный срок. Количественной мерой важности информации являются резервы времени работ или коэффициенты напряженности Кij=1 – Rпij/(Tn0–Ткр(i,j)), (4.5.1) где Rпij – полный резерв работы (i,j), Tn0 – критическое время выполнения проекта, Ткр(i,j) – продолжительность совпадающего с критическим путем отрезка максимального пути, содержащего работу (i,j). 0  Кij  1, причем, чем ближе Кij к 1, тем относительно меньше резерва в запасе у работы (i,j), следовательно, выше риск ее невыполнения в заданные сроки. Например, у работы (2,5) (рис.4.4.5 темы 4.4) Ткр(2,5)=5, Rп25 =3, откуда К25=1 –3/(22 – 5)=0.82, а у работы (5,8) Ткр(5,8)=0, Rп58=12, откуда К58=1 –12/(22 – 0)=0.45. Работы могут обладать одинаковыми полными резервами, но степень напряженности сроков их выполнения может быть различна. И наоборот, различным полным резервам могут соответствовать одинаковые коэффициенты напряженности. Имея информацию, классифицированную подобным образом, руководитель проекта в каждый момент времени может определить, на каком участке следует сосредоточить внимание (и ресурсы) для ликвидации намечающихся отклонений от заданного срока завершения всех работ. Прежде чем наметить дальнейшие пути совершенствования методов сетевого планирования и управления, остановимся подробнее на некоторых основных недостатках, присущих методам, рассмотренным в теме 4.4. Давая временную оценку продолжительности какой-либо работы, мы предполагали использование для выполнения этой работы определенных ресурсов с определенной интенсивностью (интенсивность потребления ресурса – это количество ресурса, потребляемое в единицу времени). В момент назначения временной оценки неизвестно, когда эта работа должна будет выполняться, какие другие работы проекта, потребляющие тот же вид ресурса, будут вестись одновременно. Более того, как правило, одни и те же ресурсы могут потребоваться одновременно на разных проектах. Поэтому не исключено, что суммарная потребность в том или ином ресурсе в отдельные моменты времени может превосходить их наличный уровень. В этих случаях придется или уменьшать интенсивность потребления ресурсов на отдельных работах, либо отложить выполнение ряда работ на более поздние сроки, зачастую за пределы полных резервов этих работ. Это приводит в процессе выполнения проекта к частым корректировкам исходного плана, иными словами, к неустойчивости плана. Очевидно, если заранее при планировании процесса выполнения проекта учесть ограниченность ресурсов, то можно получить гораздо более надежный план. Наличный уровень ресурсов и возможные сроки завершения проекта взаимосвязаны. Время завершения всего проекта будет зависеть от того, когда и какое количество ресурсов будет выделено на каждую работу, а это в значительной мере определяется их предполагаемым наличием в каждый момент времени. Таким образом, возникает задача о распределении ресурсов в сетевой постановке. Вообще говоря, любой процесс производственного планирования есть ни что иное, как решение задачи об эффективном использовании ресурсов. Критерии эффективности могут быть различны, на этом важном моменте планирования (выборе и обосновании критерия) мы остановимся несколько ниже при рассмотрении конкретных задач. Введем некоторые понятия и определения. 1. Программой работ назовем определенное множество операций (работ), которое нужно выполнить для достижения одной или нескольких целей, причем выполнение работ программы подчинено единому руководящему центру. Можно говорить о программе работ по пусковому комплексу, программе работ участка, строительной организации, проектного института и т.п. 2. Однотемной программой работ будем называть программу, состоящую из одного комплекса технологически взаимосвязанных работ, направленных на достижение одной (одноцелевая тема) или нескольких целей (многоцелевая тема). 3. Многотемной программой работ будем называть программу, состоящую из нескольких комплексов работ, технологически взаимосвязанных внутри каждого комплекса. Каждый комплекс работ может иметь одну или несколько конечных целей. Работы, принадлежащие разным комплексам, технологически между собой не связаны. Принадлежность тем одной многотемной программе обуславливается единством управляющего центра и общностью резервуара ресурсов. 4.5.2. Постановки задач распределения ресурсов. Рассмотрим сначала различные постановки задач распределения ресурсов для однотемной одноцелевой программы. Исходя из двух возможных целевых установок при управлении проектом, описанным сетевой моделью, возможны два основных типа постановки задач. Первый тип ориентирован на жесткое соблюдение ограничений по ресурсам, тогда как второй тип предполагает строгое выполнение сроков завершения проекта. Формулировка первого типа постановки задачи («калибровка»). При заданных ограничениях в потреблении ресурсов найти такое их распределение с учетом технологической последовательности ведения работ, определенной топологией сетевого графика, которое обеспечивает завершение всей программы за минимальное время. Формулировка второго типа постановки задачи («сглаживание»). При соблюдении заданной продолжительности выполнения программы требуется так распределить ресурсы по отдельным работам, чтобы их потребление было оптимальным. Вопрос о выборе критерия оптимальности для этой постановки будет нами рассмотрен специально. В силу разного механизма удовлетворения потребности в ресурсах их принято разделять на две группы: накапливаемые (складируемые) и ненакапливаемые (нескладируемые). Вторую группу ресурсов часто называют «ресурсы типа мощности». К первой группе относятся ресурсы, которые по своему характеру допускают накопление с возможностью их последующего использования, например, денежные средства, различные материалы и конструкции и т.п. Ресурсные ограничения в этом случае могут быть заданы интегральной неубывающей функцией, показывающей в каждый момент времени суммарную величину поставок ресурса за весь предшествующий период. Ко второй группе относятся ресурсы, накопление которых для последующего использования невозможно. Например, ресурсы рабочего и машинного времени. Простой рабочих и механизмов является безвозвратной потерей. Ресурсные ограничения для этой группы задаются функцией наличия ресурса в каждый момент времени. Пусть rkij– интенсивность потребления k-го ресурса на работе (i,j). Тогда величину wkij = rkijtij – назовем объемом работы. Обозначим εk – множество работ, потребляющих ресурс k, а εkt – множество работ, потребляющих ресурс k в момент времени t (εk=tεkt), тогда общая потребность на всю программу в k-м ресурсе равна Wк =(i,j)εkwkij = =(i,j)εkrkijtij, причем для ресурсов второго типа этот показатель измеряется в машиносменах, человекоднях и т.п. Пусть наличие ресурсов в каждый момент времени задано функцией Ак(t). Если наличие ресурсов во времени неизменно, т.е. Ак(t)=Ак, то величина maxkWк/Aк – определяет минимальное время выполнения программы с точки зрения обеспеченности ресурсами. Учитывая, что время выполнения однотемной программы не может быть меньше критического(Tn0), вычисленного без учета ограниченности ресурсов, то получаем оценку нижней границы времени, искомого в задачах «калибровки»: Т ≥ max Tn0, maxkWк/Aк . Обозначая Fк(t)=(i,j)εktrkij – потребность в ресурсе k в момент времени t, получаем математическую модель задачи «калибровка» в виде: Найти такие сроки начала и окончания работ (i, j) Тi* и Тj*, что 1. Тj* – Тi* – tij ≥ 0, для всех работ (i, j); 2. Ак(t) ≥ Fк(t), для всех t и k; 3. Tn* min. Первое ограничение отображает требование соблюдения технологической последовательности работ. Второе ограничение учитывает ограниченность ресурсов, т.е. в каждый момент времени потребность в ресурсе не должна превышать его наличия. Tn* – срок свершения завершающего события. Алгоритм решения сформулированной выше задачи носит эвристический характер, и основная его идея заключается в следующем: (для упрощения примем k =1 и Ак(t)=А, т.е. ресурс один и его наличие постоянно во времени). Процедура 1. Производится расчет временных параметров сетевого графика и составляется линейная диаграмма, при этом начала работ (i,j) ставятся в ранние сроки свершения событий i (см.тему 4.4). Процедура 2. Последовательно (начиная с t=0) проверяем соотношение 2 модели. Если оно выполняется (ресурса хватает на все работы, попавшие в данный интервал), то переходим к следующему интервалу времени и так до конца, в противном случае – к процедуре 3. Процедура 3. Все работы, на которые в интервале  не хватило ресурса, упорядочиваем в соответствии с Кij (корректируя при этом полный резерв в (4.4.1) ранее начатых работ на число дней от их начала до ). Сдвигаем работы по календарной шкале вправо в порядке возрастания Кij (устанавливаем начало на +1 или прерываем работу в интервале , если разрыв возможен), пока суммарная потребность в ресурсе оставшихся в данном интервале работ не придет в соответствие с его наличием. После этого производим пересчет временных параметров работ, расположенных в правой от  части линейной диаграммы, возвращаемся к процедуре 2, и процесс решения продолжается с интервала +1. Проиллюстрируем применение алгоритма на примере. Пример 4.5.1. Имеется сетевой график 7 3 6 4 5 5 2 5 4 6 3 2 5 4 3 4 4 7 Цифра под стрелкой означает временную оценку (tij), цифра над стрелкой задает объем необходимого ресурса (rij). Рассмотрим людской ресурс, и пусть имеется всего 12 исполнителей (т.е. Ак(t)=А=12). Найдем суммарную трудоемкость всех работ W=wij=rijtij= =62+55+34+74+44+56+52+34+47=173, откуда получаем оценку для Т: Т ≥ max Tn0, W/A = max 14, 173/12=15. Процедура 1. В табл. 4.5.1 приведены результаты расчетов временных параметров работ. Таблица 4.5.1 (i,j) tij Тi0 Тj1 Rпij Rсij (0,1) 2 2 (0,2) 4 7 3 (0,3) 5 6 1 1 (1,3) 4 2 6 (2,5) 7 4 14 3 3 (1,4) 3 2 12 7 7 (3,4) 6 6 12 (4,5) 2 12 14 (3,5) 4 6 14 4 4 На рис.4.5.1 приведен календарный план при отсутствии ограничений на ресурсы. В этой линейной диаграмме начала всех работ приурочены к ранним срокам их свершения. Над каждой работой проставлена необходимая для ее выполнения потребность в ресурсе. Для наглядности под линейной диаграммой поместим эпюру потребности в ресурсах (график функции F(t)). Работы (4,5) 5 (3,5) 3 (3,4) 5 (2,5) 4 (1,4) 7 (1,3) 4 (0,3) 5 (0,2) 3 (0,1) 6 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T 20 20 19 18 16 14 А=12 12 12 10 8 9 8 6 5 4 2 Рис 4.5.1. Процедура 2. Рассматриваем начальный интервал (от 0 до 2). Здесь потребность в ресурсе превышает его наличие на 2. Значит, переходим к процедуре 3. Процедура 3. Вычисляем коэффициенты напряженности для работ, выполняемых в этом интервале: К01 = 1 – 0 = 1, К02 = 1 – 3/(14 – 0) = 0.79, К03=1 – 1/(14 – 8)=0.83. Сдвигаем работу (0,2) с меньшим коэффициентом на два дня; т.к. она не имеет свободного резерва, то соответственно сдвигается на два дня и работа (2,5) в пределах свободного резерва. Результаты этого шага отобразим на рис.4.5.2. Процедура 2. Рассматриваем теперь интервал от 2 до 5. Здесь 4 работы имеют общую потребность 19, значит, опять переходим к процедуре 3. Процедура 3. Вычисляем К03=1 –1/(14 – 8)=0.83, К02=1 –1/(14 –0)= =0.93, К13=1 –0=1, К14=1 –7/(14 – 2)=0.42. Сдвигаем работу (1,4) на три дня в пределах ее свободного резерва. Результаты на рис.4.5.3. Работы (4,5) 5 (3,5) 3 (3,4) 5 (2,5) 4 (1,4) 7 (1,3) 4 (0,3) 5 (0,2) 3 (0,1) 6 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T 20 19 18 16 14 А=12 12 11 12 10 9 8 7 6 5 4 2 Рис 4.5.2. Работы (4,5) 5 (3,5) 3 (3,4) 5 (2,5) 4 (1,4) 7 (1,3) 4 (0,3) 5 (0,2) 3 (0,1) 6 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T 20 19 18 16 14 14 А=12 12 11 12 12 10 9 8 6 5 4 2 Рис 4.5.3. Процедура 2. Рассматриваем интервал от 5 до 6. Имеем превышение потребности ресурса над его наличием на 2. Процедура 3. Самый меньший коэффициент напряженности у работы (1,4), К14=1 – 4/(14 – 2)=0.67, поэтому ее сдвигаем на 1. Остаются в расписании на этот интервал работы (0,2) и (1,3) с общей потребностью 7 человек. Процедура 2. Рассматриваем интервал от 6 до 9. Суммарная потребность составляет 19. Процедура 3. Самый меньший коэффициент напряженности опять у работы (1,4), К14=1 –3/(14 – 2)=0.75, поэтому ее сдвигаем на 3. Остаются в расписании на этот интервал работы (2,5), (3,4) и (3,5) с общей потребностью 12 человек. Процедура 2. Рассматриваем интервал от 9 до 10. Суммарная потребность составляет 19. Процедура 3. Сейчас меньший коэффициент напряженности у работы (3,5), но ее сдвиг не уменьшит потребность в ресурсе на необходимое число (7), поэтому вынуждены двигать опять работу (1,4) на 1. Остаются в расписании на этот интервал те же работы (2,5), (3,4) и (3,5) с общей потребностью 12 человек. Т.к. у работы (1,4) резерва уже не было, то соответственно подвинулась работа (4,5) также на 1. Процедура 2. Рассматриваем интервал от 10 до 12. Суммарная потребность составляет 16. Процедура 3. Сейчас резервы времени исчерпаны, коэффициенты напряженности у всех работ равны 1, поэтому вынуждены двигать опять еще не начатую работу (1,4) на 2. Остаются в расписании на этот интервал работы (2,5) и (3,4) с общей потребностью 9 человек. Т.к. у работы (1,4) резерва уже не было, то соответственно подвинулась работа (4,5) еще на 2. Процедура 2. Рассматриваем интервал от 12 до 13. Суммарная потребность составляет 11. На интервале от 13 до 15 потребность составляет 7 и от 15 до 17 потребность 5 человек. Алгоритм закончен, время выполнения проекта Т=17. Окончательный результат представлен на рис.4.5.4. Как мы видим, совсем без резервов остались работы (1,4) и (4,5), у остальных работ, даже работ бывшего критического пути, появились резервы времени. Работы (4,5) 5 (3,5) 3 (3,4) 5 (2,5) 4 (1,4) 7 (1,3) 4 (0,3) 5 (0,2) 3 (0,1) 6 0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 T 20 18 16 14 А=12 12 11 12 12 11 10 9 8 7 7 6 5 4 2 Т=17 Рис 4.5.4. Аналогичная постановка задачи для накапливаемых ресурсов отличается от предыдущей только видом ограничения 2, которое принимает вид: 2.  t=1Ак(t) ≥  t=1Fк (t), для всех  и k; т.е. суммарная потребность в накапливаемом ресурсе от начала планового периода к любому моменту  не должна превышать суммарного объема поставок этого же вида ресурса за соответствующий период. Алгоритм решения данной задачи в принципе проще предыдущего и здесь не приводится. Оптимальное распределение ресурсов при заданном времени – “сглаживание”, является задачей, в некотором смысле обратной к рассмотренной выше. Прежде всего, необходимо определить критерий оптимальности. В большинстве случаев целесообразно в качестве критерия оптимальности принимать меру неравномерности потребления ресурсов. Если Т – заданное время выполнения программы, то Rkср=Wк/Т – среднее потребное количество ресурса k в единицу времени. В качестве меры неравномерности потребления ресурса могут быть выбраны различные функции, например: 1=tFк(t) – Rkср, 2=t(Fк(t) – Rkср)2, 3=maxtFк(t) – Rkср, 4=maxtFк(t), 5=t(Fк(t) – Ak(t))2, 6=t(Fк(t) – Ak(t)), где = 1 – если (Fк(t) – Ak(t)) > 0, -2 – если (Fк(t) – Ak(t)) < 0, т.е. 1 – удельные затраты, связанные с превышением потребности над наличием (для ресурсов типа “мощности” – стоимость сверхурочного времени), 2 – удельные затраты, связанные с избыточным наличием ресурса (для ресурсов типа “мощности” – стоимость простоя исполнителей или оборудования). Могут быть и другие критерии. Выбор критерия связан со спецификой конкретной системы управления проектом, например, выбирая 1, мы предполагаем «равнозначность» как положительных, так и отрицательных отклонений потребности в ресурсе от его средней потребности, а также два отклонения по 1 эквивалентны одному отклонению на 2. Критерий 2 применим в случае, когда такие отклонения не эквивалентны (одно на 2 равно 4 по 1), 5 подобен 2, только отклонения анализируются не от средней потребности, а от наличия ресурса. Критерий 6 целесообразен при различной оценке превышения (положительной или отрицательной). Критерий 4 (наибольшее ежедневное потребление) часто используется при составлении проекта организации строительства отдельного объекта или комплекса работ. Таким образом, математическая модель задачи «сглаживания» имеет вид: Найти такие сроки начала и окончания работ (i, j) Тi* и Тj*, что 1. Тj* – Тi* – tij ≥ 0, для всех работ (i, j); 2. Tn*  Т; 3. i min. Рассмотрим идею алгоритма минимизации максимального потребления ресурса (критерий 4). Процедура 1. Расчет временных параметров сетевой модели и составление линейной диаграммы по ранним срокам. Построение эпюры потребности в ресурсе. Вычисление уровня = maxtFк(t). Процедура 2. Понижаем уровень на 1. В интервалах времени, где наблюдается превышение потребности над уровнем, пытаемся сдвинуть работы в пределах их резервов. Работы для сдвига выбираем в порядке возрастания коэффициентов напряженности. Если подобным образом удалось ликвидировать все превышения над уровнем, повторяем процедуру 2 сначала, иначе – стоп, получен оптимальный план. Представленные выше модели предполагали постоянную продолжительность работ. Практически почти каждую работу можно выполнить за различное время в зависимости от количества ресурсов, привлекаемых для выполнения данной работы. 4.5.3. Оптимизация сетевого графика методом “время – стоимость”. Обозначим аij – минимально возможное время выполнения работы (i,j), которому соответствуют затраты саij; bij – максимально возможное время выполнения работы (i,j), которому соответствуют затраты сbij. Предполагается, что ускорение работы связано с дополнительными затратами (на привлечение дополнительной рабочей силы и оборудования, сверхурочные доплаты и т.п.). Имеем аij  tij  bij , сbij  сij  саij; (4.5.2) сij – затраты, соответствующие времени выполнения tij. Пусть зависимость затрат от времени выполнения линейная, т.е. сij =zij – yijtij , откуда, используя (4.5.2), получаем выражение для коэффициента пропорциональности yij = (саij – сbij)/(bij – аij)=с/t. (4.5.3) Таким образом, yij характеризует затраты, связанные с сокращением продолжительности работы на единицу времени. Будем называть yij – “ценой” сокращения работы на единицу времени. Если на всех работах принять tij = аij, то будет получено наименьшее критическое время Ткрmin. Этому времени соответствуют наибольшие затраты, равные Са = (i,j) саij; Если на всех работах принять tij = bij, то мы получим сетевой график, которому соответствуют наименьшие затраты, равные Сb = =(i,j) сbij, и наибольшее критическое время Ткpmax. При наименьшем критическом времени Ткрmin можно уменьшить затраты, если «удлинить» некритические работы за счет их резервов времени. Ведь увеличение tij на единицу снижает ее стоимость на yij. Обозначим эти затраты через Сd, тогда можем утверждать, что для Т= Ткрmin минимальная стоимость равна Сd, и, в общем случае, для любого ТТкрmin ,Ткрmах существует план с минимальными затратами С(Т). График функции С(Т) приведен на рис 4.5.5. С Са Сd С(Т) Сb Рис 4.5.5. Ткрmin Ткрmах Имея график оптимальной зависимости стоимости проекта от продолжительности его выполнения можно, с одной стороны, определять минимальную стоимость проекта при любом возможном сроке его выполнения, а с другой стороны, находить минимальную продолжительность выполнения проекта при заданной его стоимости. С помощью функции С(Т) можно также оценить дополнительные затраты, связанные с сокращением сроков завершения проекта. Если затраты линейно зависят от продолжительности работ, как мы выше предположили, то нахождение С(Т) можно свести к решению задачи линейного программирования вида: Найти такие продолжительности работ – tij, что 1. Тj – Тi – tij ≥ 0, для всех работ (i, j); 2. аij  tij  bij , 3. Tn0  Т, 4. С(Т)=(i,j) сij =(i,j) (zij – yijtij )  min, что эквивалентно (i,j) yijtij  mах. Однако решать такие задачи методами линейного программирования, как правило, неэффективно, в связи с чем используются специально разработанные эвристические алгоритмы. Разберем один из них на небольшом примере. Сеть приведена на рис.4.5.6. 10 13 Цифры над работами 16 6 8 10 означают 4 30 18 11 саij сbij 15 21 аij bij Рис.4.5.6. Примем tij = аij (выделено жирным шрифтом), тогда Ткрmin = 15, Са = (i,j)саij=16+13+30=59, Rп12=3, Rп23=3, Rп13=0. Определим цены сокращения работ на единицу, согласно (8.3) имеем: y12=(16 – 10)/(6 – 4)=3, y13=(30 – 18)/(21–15)=2, y23=(13–10)/(11– 8)=1, т.е. увеличение продолжительности работы (1,2) на единицу удешевляет ее на 3 и т.д. Увеличим продолжительность некритических работ (1,2), (2,3) в пределах их полных резервов (т.к. они находятся на одном пути, то полный резерв у них общий). Если увеличить продолжительность работы (2,3) на 3, то это удешевит первоначальный план на 3y23=3, если же удлинить работу (1,2), а ее можно удлинить только на 2 дня, то стоимость уменьшится на 2y12=6, и еще на 1 можно будет увеличить продолжительность работы (2,3), что даст экономию еще на 1, – всего сокращение стоимости составит 6+1=7. Мы получили самый дешевый план при Ткрmin = 15, стоимость которого Сd =59 – 7=52. И мы получили общее правило для выбора работ – приоритетом является «цена» сокращения. Мы рассматривали зависимости между затратами и временем выполнения работы, имея в виду лишь прямые затраты, поскольку выявить изменение косвенных (накладных) расходов от изменения продолжительности отдельной работы весьма затруднительно. Косвенные затраты существенно зависят от времени завершения всей программы в целом, причем известно, что с увеличением срока выполнения проекта косвенные затраты возрастают. В предположении линейной зависимости косвенных затрат от срока завершения проекта (что отображено на рис. 4.5.6 прямой LN) оптимальному плану (с учетом прямых и косвенных затрат) будет соответствовать точка М. С график функции суммарных прямых и косвенных Сd M затрат Сb N L Рис 4.5.6. Ткрmin Топт Ткрmах С помощью вышерассмотренной модели “затраты – время” можно решить иную по сути, но аналогичную по математической постановке задачу минимизации общего числа исполнителей, необходимых при выполнении проекта при заданном сроке его окончания. Будем трактовать саij как количество исполнителей, необходимое для выполнения работы (i,j) в минимально возможное время аij; соответственно сbij – количество исполнителей, необходимое для выполнения работы (i,j) в максимально возможное время bij. Имеем аналогичные (4.5.2) соотношения аij  tij  bij , сbij  сij  саij, где сij – количество исполнителей, соответствующее времени выполнения tij. В рассматриваемой задаче “цена” сокращения yij вычисляется также по формуле (4.5.3) и показывает, сколько исполнителей надо добавить, чтобы сократить время выполнения работы на единицу времени. Рассмотрим пример (рис. 4.5.7). обозначения 12 11 3 5 6 6 6 yij 4 8 5 10 3 8 аij bij 10 4 Рис. 4.5.7 Пусть заданное время Т=22. Поставим на каждую работу минимально возможное количество исполнителей, тогда продолжительности работ будут максимальные, т.е. tij = bij. Время выполнения всего проекта в данном случае будет 8+10+8=26 (длина другого пути 8+11+6=25), что на 4 единицы больше заданного времени. Кажется естественным найти на критическом пути работу с наименьшей ценой сокращения (это будет работа (4,5)) и сократить ее продолжительность на 4 единицы, что потребует дополнительно 34=12 исполнителей. Теперь другой путь стал критическим, и наименьшая цена сокращения у работы (3,5). Для сокращения ее продолжительности на 3 единицы потребуется дополнительно 53=15 исполнителей, таким образом, всего понадобится дополнительно 12+15=27 исполнителей. Однако существует лучшее решение. Работу (1,2), которая является общей для обоих путей, сократим на 4 единицы времени. Это потребует 64=24 дополнительных исполнителей. Ткр=Т=22. Еще более эффективное решение может быть получено следующим образом: работу (1,2) сокращаем на 3 единицы, что потребует дополнительно 63=18 исполнителей, и работу (4,5) на 1 единицу с привлечением дополнительно 31=3 человек. Получили Ткр=Т=22, число дополнительных рабочих 18+3=21. Подобный подход и критерий оптимальности применяется в некоторых системах управления строительным производством, где план, обеспечивающий своевременный ввод объекта в эксплуатацию с минимальной суммой интенсивностей потребления ресурсов, считается наилучшим. В каких случаях целесообразно оптимизировать план возведения объекта по этому критерию? Это целесообразно тогда, когда затраты на возведение объекта существенно зависят от общего количества привлеченных рабочих, например, при строительстве объектов в малоосвоенных районах страны, при прокладке линий электро-передач, газопроводов, железных дорог и т.п. При строительстве объектов в районах массовой застройки оптимизация по указанному критерию не имеет смысла, т.к. получим план выполнения работ на каждом из объектов меньшим количеством ресурсов, но при более длительном их использовании, тогда как лучшим может оказаться план, при котором на каждом из объектов концентрируется большее число рабочих, которые выполняют отдельные работы за более короткие сроки и переходят на другие объекты. Кроме того, критерий эффективности – “суммарная интенсивность выполнения работ” – представляет собой сумму интенсивностей потребления ресурсов различного вида на работах, выполняемых в различные промежутки времени. Относительная дефицитность ресурсов различных видов значительно изменяется во времени в зависимости от производственной ситуации, складывающейся на всем множестве объектов, питаемых ресурсами из одного “резервуара”. Поэтому возможна ситуация, при которой в некоторый период времени легче, например, добавить 50 отделочников, чем 10 монтажников. Расчеты сетевой модели отличаются простотой, но в то же время дают весьма важную информацию для календарного планирования сложных проектов. Вследствие этого сетевые методы пользуются большой популярностью на практике. Эффективность этих методов обеспечивается благодаря наличию широкого спектра программных средств на ЭВМ, позволяющих строить, анализировать и корректировать сетевые модели проектов. 4.5.4. Многопроектные задачи сетевого планирования с учетом ограниченности ресурсов и сроков. Выше мы рассматривали задачи календарного планирования для одного проекта, тогда как крупная организация может одновременно выполнять несколько проектов, располагая единым резервуаром ресурсов. При этом возникают задачи оптимальной очередности проектов, когда их последовательность не ограничена или частично ограничена. В общем виде задача оптимальной очередности проектов формулируется следующим образом. Требуется найти такую последовательность выполнения проектов, которой соответствует непротиворечивый календарный план, доставляющий экстремум целевой функции при соблюдении заданных ограничений. В зависимости от вида целевой функции и ограничений задача очередности может иметь различные постановки, учитывающие специфику конкретных условий проектной организации. Например, для строительной организации в качестве критериев оптимальности для многопроектных задач используют минимум общей продолжительности строительства комплекса объектов, его пусковых очередей или этапов работ; минимум простоев бригад и механизмов или перерывов работ на объектах; минимум отклонений расчетных сроков выполнения работ от директивных и др. Ограничения в многопроектных задачах сетевого планирования формулируются как требования к использованию общего резервуара накапливаемых и ненакапливаемых ресурсов, соблюдение заданных сроков или продолжительности выполнения отдельных проектов или их групп, соблюдение нормативных заделов и объемов незавершенного производства. На практике применяются следующие критерии: f= f1+f2min, где  – коэффициент взвешивания цели;  предполагается существенно меньшим единицы. Первое слагаемое целевой функции f1 определяет меру соответствия полученных при временном расчете сроков ввода объектов директивным срокам для объектов zМ1 – подлежащих вводу в планируемый период. Второе слагаемое f2 определяет меру соответствия выполнения объемов работ по задельным объектам zМ2 согласно выделенным ассигнованиям. При достаточно малом значении взвешивающего коэффициента  (<<1) влияние второго слагаемого целевой функции на расписание работ по объектам zМ1 неощутимо, что соответствует принципу концентрации ресурсов на сдаточных объектах. Второе слагаемое вводится в выражение целевой функции для определения приоритетности работ по задельным объектам при включении их в расписание. Пусть Тz* – расчетный срок ввода объекта z, Тzдир – директивный срок, тогда мера соответствия расчетных сроков ввода объектов директивным может быть выражена с помощью следующих функций: f1=zМ1[Тz*– Тzдир], (4.5.4) f1=zМ1[Тz*– Тzдир]2, (4.5.5) f1=zМ1 Тz*– Тzдир, (4.5.6) f1=zМ11[Тz*– Тzдир], (4.5.7) где М11М1–множество объектов, для которых получено Тz*> Тzдир, f1=zМ1[Тz*– Тzдир]z, (4.5.8) где z = 1z для zМ11, 2z для zМ12 (М12М1 – множество объектов, для которых получено Тz* < Тzдир), f1=махzМ1[Тz*– Тzдир]. (4.5.9) Коэффициенты 1z, 2z характеризуют соответственно потери или прибыль от задержки или досрочного ввода объекта в эксплуатацию. В случае критерия (4.5.4) оптимальный план, которому соответствует минимальная алгебраическая сумма отклонений, допускает форсирование строительства одних объектов за счет других. Критерий (4.5.5) является одной из лучших мер равномерности. Однако, использование этой функции не всегда целесообразно, так как она в равной мере оценивает как досрочный ввод, так и превышение директивного срока, что не совсем соответствует действительности. Все, сказанное относительно (4.5.5), справедливо и для (4.5.6), причем при сложении абсолютных значений отклонений двухмесячное отклонение по одному объекту эквивалентно месячным отклонениям по двум объектам, что еще менее адекватно требованиям строительного производства. Функции (4.5.7) присущи те же недостатки, что и (4.5.4), но в существенно меньшей степени, что определяет допустимость использования такого критерия для решения практических задач. Функция (4.5.8) наилучшим образом отвечает специфике строительного производства. Однако, использование критерия такого вида предполагает обоснованное определение для каждого объекта коэффициентов 1z, 2z. Функция (4.5.9) достаточно хорошо характеризует степень достижения основных целей строительной организации. И хотя экономическое «содержание» этой функции беднее, чем у (4.5.8), сравнительная простота алгоритмов решения задач на минимум максимального превышения расчетных сроков над директивными предопределяет ее выбор для практического использования. Функция f2 может принимать выражения, аналогичные (4.5.4) -(4.5.9), где множество М1 заменено на М2, Тz*– на Тz**( Тz** срок завершения фрагмента сети, состоящей из работ объекта z, упорядоченных по возрастанию поздних сроков их начала, суммарная сметная стоимость которых равна выделенным ассигнованиям на данный объект), Тzдир на Тпл. В силу принятых обозначений условие выполнения заданного объема работ в стоимостном выражении по объекту zМ2 в течение планируемого периода может быть представлено как Тz**  Тпл. Тема 4.6. Задачи управления запасами 4.6.1. Экономическое содержание задач управления запасами. Для обеспечения непрерывного и эффективного функционирования практически любой организации необходимо создание запасов. В любой задаче управления запасами требуется определять количество заказываемой продукции и сроки размещения заказов. Спрос можно удовлетворить путем однократного создания запаса на весь рассматриваемый период времени или посредством создания запаса для каждой единицы времени этого периода. Эти два случая соответствуют избыточному запасу (по отношению к единице времени) и недостаточному запасу (по отношению к полному периоду). При избыточном запасе требуются более высокие удельные (отнесенные к единице времени) капитальные вложения, но дефицит возникает реже и частота размещения заказов меньше. С другой стороны, при недостаточном запасе удельные капитальные вложения снижаются, но частота размещения заказов и риск дефицита возрастают. Для любого из указанных крайних случаев характерны большие экономические потери. Таким образом, решения относительно размера заказа и момента его размещения могут основываться на минимизации общих издержек, включающих затраты, обусловленные потерями от избыточного запаса и дефицита. В дальнейшем мы будем учитывать расходы трех типов: 1. Расходы, вызываемые оформлением и получением заказа при закупке или производстве. 2. Затраты на хранение запаса на складе. Сюда включаются, например, затраты на переработку, амортизационные и эксплуатационные расходы, процент на инвестированный капитал, расходы на страхование и налоги. 3. Расходы (штрафы), возникающие при истощении запасов, когда происходит задержка в обслуживании или спрос вообще невозможно удовлетворить. Эти расходы связаны с ухудшением репутации поставщика у потребителя и с потенциальными потерями прибыли. Чрезвычайно трудно построить обобщенную модель управления запасами, которая учитывала бы все разновидности условий, наблюдаемых в реальных системах. Приведем (далеко не полный) перечень подобных условий: 1. Все затраты могут оставаться постоянными или изменяться от времени (например, в зависимости от сезона может меняться стоимость хранения продукции на складе). Затраты могут зависеть также от объема запасов (размером партии может, например, определяться оптовая скидка при покупке или стоимость хранения на складе). 2. Спрос может быть известным или неизвестным, постоянным (спрос на хлеб) или зависящим от времени (спрос на мороженое). Величина, характеризующая спрос, может быть как дискретной (плиты перекрытия), так и непрерывной (раствор). 3. Заказы на пополнение запасов могут выполняться немедленно или с определенной задержкой. Величина задержки может быть детерминированной или случайной. Заказы можно делать в любые или только в определенные моменты времени. 4. Процесс пополнения запаса может осуществляться мгновенно (заказы поступают от внешнего источника) или равномерно во времени (запасаемая продукция производится самой организацией). Размер заказа может измеряться дискретной или непрерывной величиной и может быть как постоянным, так и переменным. 5. В зависимости от отрезка времени, на котором можно надежно прогнозировать, период времени, в течение которого осуществляется регулирование уровня запаса, принимается конечным или бесконечным. 6. В систему управления запасами может входить несколько пунктов хранения запаса, образующих иерархическую структуру с различными периодами пополнения и временем поставки заказов, с возможностью обмена запасами между складами и т.п. 7. В системе управления запасами может фигурировать более одного вида продукции. Этот фактор учитывается при наличии зависимости между различными видами продукции. Так, для различных изделий может использоваться один и тот же склад или же их производство может осуществляться при ограничениях на общие производственные мощности. Рассмотренные далее в этой теме модели соответствуют самым простым системам управления запасами. Маловероятно, что эти модели могут точно подойти для реальных условий, однако они приведены с целью разъяснения различных подходов к решению некоторых конкретных задач управления запасами. 4.6.2. Детерминированная статическая модель без дефицита. Данная модель характеризуется постоянным во времени спросом, мгновенным пополнением запаса и отсутствием дефицита (т.е. нехватка товара не допускается, штраф при неудовлетворенном спросе бесконечно велик). Такую модель можно применять в следующих типичных ситуациях: а) использование осветительных ламп в здании; б) использование канцелярских товаров крупной фирмой; в) использование таких промышленных изделий, как гайки, болты и т.п.; г) потребление основных продуктов питания (например, хлеба и молока). Предположим, что интенсивность спроса (в единицу времени) равна . Пусть q – размер заказа, ts – интервал времени между поступлениями заказов, R – полный спрос за все время планирования T. В данной модели наивысшего уровня запас достигает в момент поставки заказа размером q и падает до нуля спустя время ts (рис.4.6.1). q q q q q ts ts ts ts ts Т Рис. 4.6.1. Кривая запасов. Модель без дефицита. Тогда q /2 – средний запас в течение ts,  = R/Т, ts = q/. Чем меньше размер заказа q, тем чаще нужно размещать новые заказы. Однако, при этом средний уровень запаса будет уменьшаться. С другой стороны, с увеличением размера заказов уровень запаса повышается, но заказы размещаются реже. Так как затраты зависят от частоты размещения заказа и объема хранимого запаса, то величина q выбирается из условия обеспечения сбалансированности между двумя видами затрат (минимизации их суммы). Пусть с1 – затраты на оформление заказа, имеющие место всякий раз при его размещении (при покупке или производстве), с2 – затраты на хранение единицы продукции в единицу времени, тогда суммарные затраты в единицу времени можно представить как функцию от q в виде: с(q) = затраты на оформление заказа в единицу времени + затраты на хранение запасов в единицу времени = = с1/ ts + с2 q/2 = с1/q + с2q /2. (4.6.1) В точке минимума функции с(q) ее производная равна нулю: c′(q) = - с1/q2 + с2/2 = 0, откуда находим оптимальное значение размера заказа q* = 2 с1/ с2. (4.6.2) Полученное выражение обычно называют формулой экономичного размера заказа Уилсона. Подставляя q* в (4.6.1) определим минимальные ожидаемые суммарные накладные расходы: С* = Тс(q*) =Т2с1с2 . (4.6.3) Время расхода оптимальной партии равно ts* = q* / = 2 с1/( с2). (4.6.4) Пример 4.6.1. Ежедневный спрос на некоторый товар составляет 100 ед. Затраты на размещение каждого заказа постоянны и равны 1000 руб. Ежедневные затраты на хранение единицы запаса составляют 0.2 руб. Требуется определить оптимальный размер партии, оптимальную продолжительность цикла поставок и вычислить минимум общих ожидаемых годовых затрат. Подстановка исходных данных примера в уравнения (4.6.2)-(4.6.4) нам дает q* = 21001000/0.2 = 1000 ед. С* =365210010000.2 = 73000 руб. ts* = 21000/(1000.2) = 10 дней. Для большинства реальных ситуаций существует (положительный) срок выполнения заказа от момента размещения до его действительной поставки. Тогда необходимо определять точку возобновления заказа, как правило, через уровень запаса, соответствующий моменту возобновления заказа. На практике это реализуется путем непрерывного контроля уровня запаса до момента достижения очередной точки возобновления заказа. Возможно, по этой причине модель экономичного размера заказа называют моделью непрерывного контроля состояния заказа. Пример 4.6.2. Предположим в условиях примера 4.6.1, что срок выполнения заказа L равен 12 дням. Так как оптимальная продолжительность цикла составляет 10 дней, возобновление заказа в условиях налаженного производства происходит, когда уровень запаса достаточен для удовлетворения спроса на 12 – 10 = 2 дня. Таким образом, заказы должны делаться регулярно при достижении уровня запаса 2100=200 ед. После стабилизации системы можно считать, что срок выполнения заказа равен L – ts* при L  ts*. В описанных условиях в любой момент времени имеется более одного размещенного, но еще не выполненного заказа, и «эффективный» срок выполнения заказа принят равным 2 дням. 4.6.3. Детерминированная статическая модель с дефицитом. Эта модель отличается от предыдущей только тем, что превышение спроса над запасами уже допускается, т.е. штраф за нехватку конечный. График изменения уровня запаса в этом случае представлен на рис. 4.6.2. Убывание запаса в область отрицательных значений в отличие от графика на рис. 4.6.1 характеризует накопление дефицита. Каждый период пополнения запаса ts состоит в данном случае из суммы двух интервалов, где t1 – время, в течение которого производится потребление запаса, t2 – время, когда накапливается дефицит, который будет перекрыт в момент поступления следующей партии. s q t1 t2 t1 t2 t1 t2 t1 t1 t2 ts ts ts ts ts Т Рис. 4.6.2. Кривая запасов. Модель с дефицитом. Необходимость покрытия дефицита приводит к тому, что максимальный уровень запаса s теперь не равен размеру заказа q, а меньше его на величину дефицита q - s, накопившегося за время t2. Из подобия треугольников на рис.4.6.2 имеем t1 / ts = s / q, t2 / ts = (q – s) / q. (4.6.5) Средний запас за время t1 равен s/2. Поэтому затраты на хранение за время t1 составляют t1c2s/2. Пусть c3 – величина штрафа за нехватку одной единицы продукции в единицу времени, тогда при среднем уровне дефицита за время t2, равном (q – s)/2, штраф за это время составляет t2c3(q – s)/2. Таким образом, ожидаемые суммарные расходы за время ts равны c1 + t1c2s/2 + t2c3(q – s)/2 или, поделив на ts, получаем общие затраты в единицу времени: c1/ ts + (t1 /ts)c2s/2 + (t2 /ts)c3(q – s)/2. Подставляя сюда (4.6.5) и ts = q / , получаем выражение для общих затрат в единицу времени как функции от q и s: с(q, s) = с1/q + с2s2/(2q) + c3(q – s)2/(2q). (4.6.6) Из уравнения (4.6.6) находим оптимальные значения объема заказа q* и максимального уровня запаса s*, при которых функция с (4.6.6) принимает минимальное значение. Для этого приравниваем частные производные с/q, с/s к нулю и после упрощений получаем систему уравнений: s = qс3 /(с2 + с3), (4.6.7) q2 с3 - (с2 + с3)s2 = 2с1. Решая эту систему относительно q и s, находим q* = 2 с1/ с2 (с2 + с3)/ с3 и s* = q*с3 /(с2 + с3). (4.6.8) Определим минимальные ожидаемые суммарные накладные расходы за весь период Т: С* = Тс(q*, s*) =Т2с1с2с3 /(с2 + с3). (4.6.9) Оптимальный интервал времени между заказами равен: ts* = q* / = 2 с1/( с2) (с2 + с3)/ с3 . (4.6.10) При сравнении результатов, полученных для моделей без дефицита и с дефицитом, можно заметить, что уравнения (4.6.2)-(4.6.4) можно получить из уравнений (4.6.8)-(4.6.10), если с3  , действительно, отсутствие дефицита соответствует бесконечно большому штрафу за неудовлетворенный спрос. Отметим также, что ожидаемые суммарные расходы в модели с дефицитом меньше, чем в модели без дефицита, т.к. они отличаются на величину  =с3/(с2+с3)  1. Коэффициент  называется плотностью убытков из-за неудовлетворительного спроса и играет важную роль в управлении запасами. Пример 4.6.3. Пусть сохраняются все условия примера 4.6.1, но только штраф с3 за нехватку теперь равен 0.4 руб. за одно изделие в день. Из уравнений (4.6.8)-(4.6.10) получаем: q* = 21000100/0.2(0.2 + 0.4)/ 0.4 = 1225 ед., s* = 12250.4 /(0.2 + 0.4) = 817 ед., С* = 365210000.21000.4 /(0.2 + 0.4) = 59604 руб., ts* = 1225 /100 = 12.25 дней. При оптимальной стратегии ожидаемый дефицит к концу каждого периода составлял бы 1225 – 817 = 408 изделий. 4.6.4. Простая вероятностная модель (I). Рассмотрим вначале приближенный метод, сохраняющий простоту модели экономичного размера заказа и в то же время учитывающий вероятностный характер спроса. Этот метод предусматривает создание некоторого (постоянного) резервного запаса на всем горизонте планирования. Размер резерва определяется таким образом, чтобы вероятность истощения запаса в течение периода выполнения заказа L не превышала наперед заданной величины . Тогда размер резервного запаса В определяется из условия: x  В + L  , где L представляет собой потребление в течение времени L. Пример 4.6.4. Предположим, что ежедневный спрос в примере 4.6.2 является случайной величиной, распределенной по нормальному закону со средним  =100 и средним квадратичным отклонением =10. Определим размер резервного запаса таким образом, чтобы вероятность истощения запаса в течение срока выполнения заказа не превышала 0.05. Из примера 4.6.2 этот срок равен 2 дням. Так как ежедневный спрос распределен нормально, запаздывание спроса xL также имеет нормальное распределение со средним L = 2100 = 200 и средним квадратичным отклонением L = 2102= 14.14. Таким образом, нам необходимо найти В, удовлетворяющее x L  В + L  , (x L – L)/ L  В/ L   , или (x L – L)/ L  В/ 14.14   0.05. Используя формулу доверительной вероятности для нормального распределения (3.3.12), получим Ф(В/14.14)  0.9. Из таблицы значений функции Лапласа Ф(x) (приложение 2) получаем В/14.14  1.645, или В23.26. В этой модели определяющим фактором является среднее квадратичное отклонение. Действительно, если среднее квадратичное отклонение равно нулю (детерминированный случай), размер резервного запаса должен быть нулевым. 4.6.5. Простая вероятностная модель (II). При построении этой модели штрафы, связанные с дефицитом запасов, считаются конечными, и данная модель имеет следующие особенности: 1. Спрос и пополнение запасов оцениваются на основе опытных данных. 2. Рассматривается производство и потребление дискретного продукта. 3. Распределения по времени спроса и заказов на пополнение дискретные и неравномерные. 4. Известно и постоянно время выполнения заказов. Здесь учитываются только расходы на приобретение запасных деталей, которые могут оказаться лишними, и убытки, возникающие при их нехватке. Пусть спрос r является случайной величиной и задан закон (ряд) распределения (r). Тогда запасу в s деталей будут соответствовать следующие затраты: (s - r)с2, если r  s , т.е. запас оказался чрезмерным, и (r - s)с3, если s  r , т.е. запасных деталей не хватило. Тогда среднее значение суммарных затрат (математическое ожидание) имеет вид: C(s) = с2s – r) (r) + с3r – s)(r). (4.6.11) Задача управления запасами при вероятностном спросе состоит в отыскании такого запаса s*, при котором математическое ожидание суммарных затрат (4.6.11) принимает минимальное значение. Опуская доказательство, получаем, что значение s* должно удовлетворять неравенствам P(s* – 1)  с3 /(с2 + с3)  P(s*), (4.6.12) где P(s) =(r) – эмпирическая функция распределения спроса (вероятность того, что спрос r  s). Пример 4.6.5. Пусть стоимость одной детали, если ее заказывать заранее, составляет 100 руб. Отсутствие этой детали в запасе при поломке приводит к простою оборудования и срочный заказ детали обходится в 200 руб. Опытные данные о частоте выхода этой детали из строя приведены в табл. 4.6.1. Таблица 4.6.1. Потребовалось запасных деталей (r) 1 2 3 4 5 6 и более Сколько случаев потребовало данное число деталей 10 20 25 20 15 10 Эмпирическая вероятность (r) 0.10 0.20 0.25 0.20 0.15 0.10 Подсчитаем значение с3 /(с2 + с3) = 200/(100 + 200) = 0.67. Оптимальное решение получается в результате построения эмпирической функции распределения спроса (табл. 4.6.2). Таблица 4.6.2 s 1 2 3 4 5 P(s) 0.10 0.30 0.55 0.75 0.90 1.00 Так как P(2) = 0.55  0.67  0.75 = P(3), то оптимальное значение s* = 3. Полученным аналитическим решением можно воспользоваться для оценки потерь, возникающих при недостаточных запасах. Предположим, что нам неизвестна зависимость штрафа от размера дефицита, а уровень запасов, который предприниматель стремится поддерживать, равен трем деталям. Для какого штрафа этот уровень запасов будет оптимальным? Подставляя в (4.6.12) s* = 3, получим P(2)  с3 /(с2 + с3)  P(3), 0.55  с3 /(100 + с3)  0.75. Определим минимальное значение с3: с3/(100 + с3) = 0.55, откуда с3 = 122. Определим максимальное значение с3: с3 /(100 + с3) = 0.75, откуда с3 = 300. Следовательно, предприниматель считает, что размер штрафа за дефицит заключен в пределах от 122 до 300 руб. Заключение. Общее решение задачи выбора оптимальных размеров и сроков размещения заказов на запасаемую продукцию нельзя получить на основе одной модели. Мы рассмотрели некоторые простые частные случаи. В реальных условиях потери от дефицита обычно наиболее сложно оценить, так как они могут быть обусловлены нематериальными факторами, например, ухудшением репутации. С другой стороны, хотя оценку затрат на оформление заказа получить нетрудно, включение в модель этих расходов существенно усложняет математическое описание задачи. Известные модели управления запасами редко точно описывают реальную систему. Поэтому решения, получаемые на основе моделей этого класса, следует рассматривать скорее как принципиальные выводы, а не конкретные рекомендации. В ряде сложных случаев приходится прибегать к методам динамического программирования и даже имитационного моделирования системы, чтобы получить достаточно надежное решение. Тема 4.7. Задачи массового обслуживания 4.7.1. Общие понятия теории очередей. Ожидание того или иного вида обслуживания является частью нашей повседневной жизни. Мы ожидаем, чтобы пообедать в ресторане, мы стоим в очереди к кассам в магазинах и выстраиваемся в очередь в почтовых отделениях. Очередь возникает практически во всех присутственных местах: налоговых инспекциях, паспортных столах, страховых компаниях и пр. Феномен ожидания характерен не только для людей: работы, поставленные в очередь для выполнения; группа пассажирских самолетов, ожидающих разрешения на посадку в аэропорту; автомобили, движение которых приостановлено сигналом светофора на пути их следования, грузовые суда, ожидающие погрузки/разгрузки в порту, и т.п. Изучение очередей в системах массового обслуживания позволяет определить критерии функционирования обслуживающей системы, среди которых наиболее значимыми являются среднее время ожидания в очереди и средняя длина очереди. Эта информация используется затем для выбора надлежащего уровня обслуживания, что продемонстрировано в следующем примере. Пример 4.7.1. Физические лица, сдающие декларацию о доходах, жалуются на медленное обслуживание. В настоящее время в данном подразделении работают три налоговых инспектора. В результате расчетов, формулы для которых мы рассмотрим ниже, обнаружена следующая зависимость между числом инспекторов и временем ожидания обслуживания. Число инспекторов 1 2 3 4 5 6 7 Среднее время ожидания 80.2 50.3 34.9 24.8 14.9 12.9 9.4 (минуты)_________________________________________________________ Приведенные данные свидетельствуют о том, что при работающих в настоящее время трех инспекторах среднее время ожидания обслуживания примерно равно 35 минут. По мнению посетителей, приемлемо было бы 15 минут ожидания. Как следует из этих же данных, среднее время ожидания становится меньше 15 минут, если число инспекторов больше или равно пяти. Результаты исследования системы обслуживания также можно использовать для оптимизации модели со стоимостными характеристиками, в которой минимизируется сумма затрат, связанных с предоставлением услуг, и потерь, обусловленных задержками в их предоставлении. На рис. 4.7.1 изображена типичная стоимостная модель системы обслуживания, где затраты на обслуживание возрастают с ростом его уровня. В то же время потери, обусловленные задержками в предоставлении услуг, уменьшаются с возрастанием уровня обслуживания. Уровень обслуживания Рис. 4.7.1 Главной проблемой, связанной с применением стоимостных моделей, является трудность оценки потерь в единицу времени, обусловленных задержками в предоставлении услуг. Задачи массового обслуживания возникают в том случае, когда заявки на обслуживание (или требования) не могут быть выполнены в силу занятости обслуживающего персонала (оборудования) или сама обслуживающая система оказывается бездействующей в силу отсутствия заявок. При моделировании данных задач используются фундаментальные понятия теории вероятности, т.к. случайными оказываются поток требований или длительность времени обслуживания, или и то и другое. При решении этих задач приходится определять либо оптимальное число обслуживающих каналов, либо оптимальную скорость потока (или находить моменты поступления заявок). Класс моделей, пригодных для решения подобных задач, называют еще теорией очередей. При решении задач, связанных с очередями, возможны две ситуации: а) число заказов слишком велико; имеет место большое время ожидания (недостаточный объем обслуживающего оборудования); б) поступает недостаточное число заказов; имеет место простой оборудования (избыток оборудования). Необходимо найти оптимальное соотношение между потерями, вызванными простоем оборудования, и потерями из-за ожидания. 4.7.2. Одноканальные системы массового обслуживания. Найдем сначала среднюю длину очереди и вероятность появления очереди заданной длины на единственной станции обслуживания. Предположим, что скорость поступления и обслуживания случайны и не зависят от неограниченной длины очереди. Модель 1. Обозначим Рn – вероятность образования очереди из n заказов (включая и находящийся в обслуживании) в произвольный момент времени,  – средняя скорость появления заказов,  – средняя скорость обслуживания одного заказа. Вероятность Рn имеет четкий смысл: она показывает среднее относительное время наличия очереди длиной n при функционировании системы в стационарном режиме. Например, если Р0 = 1/2, то это означает, что в среднем половину рабочего времени очереди нет (оборудование простаивает). Справедливы следующие формулы: Рn = n(1 – ). (4.7.1) Величина  =  / называется интенсивностью потока заявок или интенсивностью нагрузки станции. Она выражает среднее число заявок, приходящих за среднее время обслуживания одной заявки. Найдем n – среднюю длину очереди. n = /( –  ). (4.7.2) Для tw – среднее время ожидания обслуживания, справедливо tw = 1/( –  ) – 1/. (4.7.3) Пример 4.7.2. Пусть заказы на обслуживание поступают со средней интенсивностью  = 5 заявок в час. Продолжительность выполнения одной заявки в среднем равна 10 мин., т.е.  =60/10=6 з/ч. Поскольку =/= 5/6 1, система может функционировать в стационарном режиме. Найдем среднее время ожидания обслуживания tw = 1/( –)–1/ =1/(6–5)–1/6=5/6 (50мин), тогда среднее число клиентов, ожидающих обслуживания, равно nw=tw=25/6=4.17 ≈ 4. Для «разумного» обеспечения местами прибывающих клиентов зададимся целью обеспечить одновременно сидячими местами, например, 80% клиентов. Это эквивалентно выполнению условия Р0 + Р1 + Р2 + …+ Рw ≥ 0.8, где w – подлежащее определению число мест. Используя (4.7.1) (1 – ) + (1 – ) +…+ w(1 – ) ≥ 0.8. учитывая, что (1 – ) + (1 – ) +…+ w(1 – ) =(1 – )(1 +  +…+ w) = 1 –w+1, получаем w+1 ≤ 0.2 и окончательно w ≥ ln(0.2)/ln(5/6) – 1 = 7.8 ≈ 8. Таким образом, для одновременного размещения, по крайней мере, 80% прибывающих клиентов минимальное число сидячих мест должно быть в два раза больше среднего числа ожидающих обслуживания клиентов. Важной характеристикой является также доля времени, в течение которого станция обслуживания простаивает. Вероятность такого события Р0 =1 –  ≈ 0.17. Вероятности того, что на станции обслуживается ровно один клиент (или два – один обслуживается, второй ждет) равны соответственно: Р1 =(1 – ) ≈ 0.139, Р2 = 2(1 – ) ≈ 0.116. Модель 2. Рассмотрим случай ограниченной очереди, когда при наличии в системе N требований ни одна из дополнительных заявок на обслуживание не принимается либо сам клиент отказывается присоединиться к очереди из-за отсутствия места в блоке ожидания. Формулы для параметров такой системы массового обслуживания: Рn = n(1 – )/(1 – N+1), n ≤ N (4.7.4) Рn = 0, n > N. Следует отметить, что в этой модели параметр = / не обязательно должен быть меньше единицы, поскольку число допускаемых в систему требований ограничено, и для  = 1 Рn =1/(N +1). Выражение для среднего числа находящихся в системе заявок принимает следующий вид n = (1 – (N+1)N + NN+1 )/(1 – )/(1 – N+1), для  ≠1, (4.7.5) N/2, для =1. Поскольку вероятность того, что заказ не имеет возможности попасть в очередь, равняется РN , доля заказов, поступающих в систему, равняется 1 – РN. Отсюда характеристики системы имеют вид: Для nw – среднее число заказов, ожидающих обслуживания: nw = n – (1 – РN )/, (4.7.6) для tw – среднее время ожидания обслуживания: tw = nw/ /(1 – РN ), (3.4.7) Пример 4.7.3. Пусть в условиях примера 4.7.2 станция располагает пятью местами для ожидающих клиентов. В данном примере N =5+1=6, =5/6, а РN =(5/6)6(1 – 5/6)/(1 – (5/6) 7) = 0.0774, N = 6. Отсюда следует, что частота случаев, когда клиент не попадает на станцию равняется РN =50.0774=0.387 заявки в час, т.е. при 8-часовом режиме работы станция теряет за день 3 клиента. Применяя (4.7.5) – (4.7.7), получаем n = (5/6)(1 – 7(5/6)6 + 6(5/6)7)/(1 – 5/6)/(1 – (5/6)7)= 2.29, nw =2.29 – 5(1 – 0.0774)/6=1.52, tw =1.52/5 /(1 – 0.0774)=0.33 часа (20 мин.). Таким образом, при введении ограничения на количество мест для ожидания (N=6), среднее время ожидания обслуживания сократилось на полчаса. Это было достигнуто за счет «потери» в среднем 3 клиентов в день из-за недостаточности мест для ожидания. Вычислим вероятность того, что в системе обслуживаются 0, 1 или 2 клиента: Р0 =(1 – 5/6)/(1 – (5/6) 7) = 0.231, Р1 =(5/6)(1 – 5/6)/(1 – (5/6) 7) = 0.193, Р2 =(5/6)2(1 – 5/6)/(1 – (5/6) 7) = 0.160. 4.7.3. Многоканальные системы массового обслуживания. Модель 3. Пусть параллельно могут обслуживаться не более s клиентов. Такие модели называются многоканальными (s – число каналов обслуживания). Здесь n = (n0), n = n при n s , n = s при n  s. Рассмотрим случай неограниченной длины очереди. Для данной модели расчетные формулы (Эрланга) имеют вид: Рn = Р0(/)n / n (n  s), (4.7.8) Рn = Р0(/)n / s/sn-s (n  s), (4.7.9) (4.7.10) Для nw – среднее число клиентов, ожидающих обслуживания: nw = Р0(/)s+1/(s–1)/(s–/)2, (4.7.11) для общего числа клиентов, находящихся в системе, имеем n = nw +/, (4.7.12) для tw – среднее время ожидания обслуживания: tw = nw/. (4.7.13) Вероятность обязательного пребывания в очереди равна вероятности занятости всех каналов обслуживания. Обозначим ее через W. Тогда W= Р0(/)s/(s–1)/(s–/). (4.7.14) Известный интерес представляет вероятность того, что суммарное время обслуживания и его ожидания превзойдет заданную величину t. Обозначим эту вероятность через Р(>t). Р(>t)=e–t(1+(W/s)(1– e–st(1–/s–1/s))/(1–/s–1/s)). (4.7.15) Вычисления в соответствии с данной моделью могут оказаться весьма громоздкими, тогда используют приближенные методы. Например, при / 1 можно принять Р0 1 – /, nw (/)s+1/s2, тогда как для значений /, близких к 1, Р0  (s – /)(s – 1)! /ss и nw  (/)/(s – /). Пример 4.7.4. Пусть на нашей станции 3 канала обслуживания (исполнителя), а мест для ожидания неограниченное число. Пусть, как и прежде  = 5 и  =6. Имеем / =0.833, s =3 и Р0 = 1/(0.8330/0+0.8331/1+0.8332/2!+ 0.8333 /(3!(1 –0.833/3))) = 0.432, nw =0.4320.8334/2/(3–0.833)2 = 0.022, tw =0.022/5 = 0.0044 часа.(16 сек.) Таким образом, при данных условиях 43.2% времени станция простаивает, среднее время ожидания обслуживания составляет 16 сек. С точки зрения клиента отлично, но простой оборудования (исполнителей) влетает в копеечку. Кроме того, имеем: Р1 =0.40, Р2 =0.15, Р3 =0.04. Вычислим параметры системы при 2 исполнителях. Р0 = 1/(0.8330/0+0.8331/1+ 0.8332 /(2!(1 –0.833/2))) = 0.412, nw = 0.4120.8333/1/(2–0.833)2 = 0.17, tw = 0.17/5 = 0.034 часа.(2 мин.) Простой составляет 41.2% времени, среднее время ожидания 2 мин. Сравним с результатами примера 4.7.2, где при наличии только одного исполнителя простой составлял 17%, а среднее время ожидания 50 мин. В силу малого времени ожидания параметры W и Р(>t) в данном примере интереса не представляют. Р1 =0.34, Р2 =0.14, Р3 =0.06. Модель 4. Рассмотрим теперь модель, которая отличается от предыдущей только тем, что число мест для ожидания обслуживания ограничено величиной k. Здесь n = при 0≤n < k+s и n =0 при n  k+s; n = n при ns, n = s при s ≤ n ≤ s+k. Формулы для характеристик модели имеют вид: Рn = Р0(/)n / n (n  s), (4.7.16) Рn = Р0(/)n / s/sn-s (s ≤ n ≤ s+k ), (4.7.17) , /≠s, (4.7.18) , /=s, (4.7.19) Для nw – среднее число клиентов, ожидающих обслуживания: nw=Р0(/)s+1(1–(/s)k–k(/s)k(1–/s))/(s–1)/(s–/)2, /≠s, (4.7.20) nw=Р0(/)sk(k+1)/(2s), /=s, (4.7.21) для tw – среднее время ожидания обслуживания: tw =nw//(1– Рk+s). (4.7.22) Пример 4.7.5. Пусть в дополнение к последнему примеру наша станция располагает двумя местами для ожидания обслуживания (k=2 и s=2). Тогда получим: Р0=1/(0.8330/0+0.833/1!+0.8332(1–(0.833/2)2+1)/2!/(1–0.833/2)) = 0.423, nw=0.4230.8333(1–(0.833/2)2–2(0.833/2)2(1–0.833/2))/1/(2–0.833)2=0.25, и tw =0.25/5/(1– Р2+2)= 0.25/5/(1 – 0.4230.8334 /2/22)=0.05 час. Для двух каналов обслуживания входной поток заказов очень слабый, изменим его, пусть =12, тогда /=2= s и мы имеем Р0=1/(20/0 +2/1!+22(2+1)/2!)= 0.111, nw=0.111*22*2*3/(2*2)=0.67, tw=0.67/12/(1–Р2+2)=0.67/12/(1–0.11124/2/22)=0.07 ч. При таком входном потоке простой оборудования составляет 11.1%, а среднее время ожидания обслуживания 0.0760= 4.3 мин. Рассмотрим более крупный пример, на котором нагляднее иллюстрируются формулы моделей 3 и 4. Пример 3.4.6. Вариант 1. Имеем станцию с 4 каналами обслуживания и с неограниченным количеством мест для ожидания. Пусть =20 заявок в час, время обслуживания одной заявки 11.5 мин. (=60/11.5=5.217), тогда /=20/5.217=3.83 и s=4. Используем 4.7.10: Р0 = 1/(3.830/0!+3.83/1!+3.832/2+3.833/3+3.834/4/(1–3.83/4))=0.0042. Из (4.7.11)–(4.7.13) получаем среднее время ожидания : tw =0.00423.835/3!/(4–3.83)2/20= 1 час. Вероятность обязательного пребывания в очереди (4.7.14): W= 0.00423.834/3/(4–3.83)=0.886. Найдем вероятность того, что суммарное время обслуживания и ожидания превзойдет величину t=0.5 (30 мин.). Применим (4.7.15): Р(>0.5) =e–5.217/2(1+0.886/4)(1–e–5.2174/2(1–3.83/4–1/4))/(1–3.83/4–1/4))=0.7. Таким образом, 88.6% клиентов обязательно проходят через очередь, причем 70% находятся в ней более получаса (правда, включая время обслуживания). Вариант 2. Добавим к варианту 1 ограничение на количество мест для ожидания. Пусть k=16, тогда из (4.7.18) находим сначала Р0=1/(1+3.83+3.832/2!+3.833/3+3.834(1–(3.83/4)17)/4!/(1–3.83/4))=0.00759 и, следовательно, из (4.7.20) получаем nw=0.007593.835(1–(3.83/4)16–16(3.83/4)16(1–3.83/4))/3/(4–3.83)2=5.82. Поскольку Р20=3.83200.00759/4!/416=0.03397, используя (4.7.22), имеем для среднего времени ожидания обслуживания: tw =5.82/20/(1–0.03397) =0.301 часа.(18 мин.) Сравнивая варианты 1 и 2, видим, что при ограничении мест для ожидания, продолжительность ожидания сокращается более чем в три раза, причем это достигается ценой потери около 3.4% потенциальных клиентов (Р20=0.03397). 4.7.4. Прикладные аспекты теории массового обслуживания. Рассмотренные модели дают методику определения средней длины очереди и среднего времени ожидания для случаев, когда скорости поступления заказов и их обслуживания являются случайными величинами с известными нам законами распределения (в основном, пуассоновским и экспоненциальным). Возможно построение моделей и с другими распределениями вероятностей. Анализ этих моделей гораздо сложнее и его результаты не позволяют получить такой большой объем полезной информации, как в случае моделей пуассоновского типа. Если издержки, связанные с пребыванием в очереди и обслуживанием, определены, то можно установить и оптимальное отношение между ними. Оптимальный уровень обслуживания выбирается таким образом, чтобы значение суммы прибыли (качества обслуживания), получаемой за счет предоставления услуг, и потерями прибыли (качества обслуживания), обусловленными задержками в предоставлении услуг, было минимальным. Труднее всего количественно определить «цену» ожидания, т.к. связанная с этим потеря потенциальных клиентов не имеет однозначного денежного выражения (хотя оценка простоев оборудования не вызывает серьезных трудностей). Проиллюстрируем прикладные возможности модельного обеспечения задач принятия решений в сфере обслуживания клиентов, рассмотрев два типа стоимостных моделей. Модели первого типа ориентированны на определение оптимальной средней скорости обслуживания при одноканальной системе массового обслуживания, модели второго типа направлены на определение оптимального числа обслуживающих каналов в случае многоканальной системы. Для определения оптимального значения μ построим стоимостную модель на основе одноканальных моделей 1, 2. Пусть с1 – затраты на обслуживание одного заказа, отнесенные к единице времени, с2 – обусловленные вынужденным ожиданием потери в единицу времени в расчете на один заказ, тогда С(μ) =с1μ + с2n – суммарные затраты в единицу времени, минимизация которых даст нам оптимальное значение μ*. Например, для модели 1, применяя (4.7.2), имеем С(μ) = с1μ + с2λ/(μ – λ), откуда, приравнивая к нулю первую производную, получаем μ* = λ + √с2λ/ с1. В случае модели 2 величина N рассматривается тоже как переменная, оптимальное значение которой (вместе с μ) определяется путем минимизации С(μ,N) = с1μ + с2n+ с3N + с4 λPN, где с3– затраты на оборудование одного места в блоке ожидания, с4 – потери, связанные с потерей потенциального клиента (приведены к единице времени). Подставляя (4.7.4)–(4.7.5), получим довольно сложное уравнение, для решения которого необходимо прибегать к соответствующим численным методам. Для определения оптимального числа обслуживающих приборов (каналов) суммарный стоимостной показатель, отнесенный к единице времени, задается формулой С(s) = с1s + с2n(s), где с1 – отнесенные к единице времени затраты на функционирование одного обслуживающего канала, с2 – как и выше, затраты, связанные с ожиданием. Тогда оптимальное значение s* находится из условия n(s*) – n(s*+1) ≤ с1/с2 ≤ n(s*–1) – n(s*). Пример 4.7.7. Пусть заказы поступают на обслуживание со средним числом λ=17.5 заявок в час. Каждое оборудованное обслуживающее место способно удовлетворить в среднем μ=10 заявок в час. Затраты, связанные с добавлением одного обслуживающего места, оцениваются в с1=6 руб. в час. Пусть потери из-за ожидания составляют с2=30 руб. в час. Вычислим по формулам (4.7.10) и (4.7.12) Р0 и n для разных значений s и результаты поместим в таблицу 4.7.2. Таблица 4.7.2 s Р0 n n(s*–1) – n(s*) 1 ∞ – 2 0.067 5.745 ∞ 3 0.156 0.468 5.28 4 0.170 0.092 0.376 5 0.173 0.019 0.073 6 0.174 0.004 0.015 Следует обратить внимание на то, что n(1)= ∞, так как λ > μ. Поскольку с1/с2 = 6/30 = 0.2, имеем n(4) – n(5) = 0.073 ≤ 0.2 ≤ 0.375 = n(3) – n(4). Следовательно, оптимальное количество моечных мест s*=4. Можно учесть еще потери, связанные с простоями оборудования, для этого необходимо по формуле (4.7.8) найти вероятности того, что обслуживаются ровно n (n=0,1,2,…< s) автомашин. Также можно учесть ограничение на вместимость блока ожидания (модель 4), но получаемые стоимостные модели весьма сложны и требуют для своего решения специальных численных методов. При возникновении подобных трудностей, а также в случае невозможности выразить в аналитическом виде характеристики системы массового обслуживания, используют метод статистического моделирования (метод Монте–Карло). Согласно методу Монте–Карло перебирают (с помощью ЭВМ) все возможные состояния системы с различной интенсивностью и разными законами распределения вероятностей входного и выходного потоков. В результате многократного искусственного воссоздания работы системы рассчитывают характеристики обслуживания, как если бы они были получены при наблюдении над реальным потоком клиентов. Для сложных систем обслуживания метод статистического моделирования оказывается проще аналитического. Тема 4.8. Состязательные задачи 4.8.1. Основные понятия теории игр. Решение многих экономических задач для индивидуального участника экономических отношений (производителя, потребителя, продавца, покупателя и т.п.) сводится к максимизации полезности при условии сбалансированности своего бюджета. Задачи часто выражаются альтернативно, как, например, максимизация выпуска продукции при заданных издержках или минимизация издержек при данном выпуске. Каждый индивидуум старается достичь максимума своей прибыли, и на его действия не оказывают влияния действия других индивидуумов. Однако в других экономических ситуациях возникают конфликты интересов, которые должны быть разрешены. Конфликты интересов возникают между продавцом и покупателем, между конкурирующими продавцами (производителями). Более сложные ситуации возникают, если образуются коалиции лиц, участвующих в столкновении интересов, например, в том случае, когда ставки заработной платы определяются союзами рабочих и предпринимателей. Решение таких проблем поднимает более сложные вопросы о стратегиях поведения участников, и соответствующие математические формулировки этих проблем и методы их решения составляют теорию игр. Игра – это совокупность правил и процедур, которым подчиняются ее участники для достижения своей цели. Каждый участник (игрок) имеет множество возможных ходов, выбрать один из них – значит сделать ход. Партия – это последовательность ходов, сделанных в соответствии с правилами игры и приводящих ее к конечному состоянию. Во многих играх достижение цели сопровождается каким-нибудь выигрышем. Выигрыш в игре будем рассматривать в количественном выражении, причем отрицательное значение выигрыша интерпретируется как проигрыш. Игра с нулевой суммой – это такая игра, в которой сумма выигрышей участников равна нулю. Стратегия – это установленный игроком метод выбора решения при каждом ходе в течение игры. Будем рассматривать конечную игру, то есть игру с конечным числом ходов и конечным числом стратегий. Платежная матрица – это таблица, которая определяет, какие выигрыши должны быть получены игроками после завершения игры. Рассмотрим игру двух лиц с нулевой суммой. Обозначим игроков А и В, и пусть А имеет m вариантов хода, а В имеет n вариантов. Пусть игра заключается в том, что игроки делают по одному ходу и А выигрывает у В сумму aij, если А выбрал вариант i (i=1,2,…,m), а В выбрал вариант j (j=1,2,…,n). Тогда платежная матрица для игрока А имеет вид: a11 a12 …a1n A = [aij ] = a21 a22 …a2n ……….. am1 am2…amn Платежную матрицу для игрока В нет необходимости рассматривать самостоятельно, так как В = – А. Лучшая (оптимальная) стратегия игрока заключается в выборе такого варианта хода (из своих возможных), при котором будет получен максимальный выигрыш при отсутствии информации о ходе противника. Определение оптимальных стратегий для игроков составляет решение игры. Игрок следует чистой стратегии в повторяющихся партиях, если в каждой партии он выбирает из всех альтернатив одну и ту же, использование комбинаций чистых стратегий называется смешанной стратегией. Для решения игры будем использовать критерий минимакса – максимина. Этот критерий предписывает игроку А выбирать такую стратегию (чистую или смешанную), которая максимизирует его минимальный выигрыш, причем минимум берется по всем стратегиям игрока В. Игрок В в свою очередь выбирает стратегию, которая минимизирует его максимальный проигрыш, где максимум берется по стратегиям игрока А. Рассмотрим применение данного критерия на примере. Игрок В Пусть задана платежная матрица, определяющая выигрыш –2 –4 игрока А. Если игрок А выбирает первую стратегию, его А= –1 3 выигрыш будет не меньше min–2, –4= –4 независимо 1 2 от поведения игрока В. При выборе игроком А второй стратегии гарантированный выигрыш будет равен min–1, 3= –1, и, наконец, если он выберет третью стратегию, гарантированный выигрыш будет равен min1,2= 1. Тогда игрок А, выбирая третью стратегию, максимизирует свой минимальный выигрыш. Его значение равно mах–4, –1, 1=1. Выбранная игроком А стратегия называется максиминной стратегией, а соответствующее ей значение выигрыша – максиминным (нижним) значением игры. Игрок В хочет минимизировать свой проигрыш. Выбрав первую стратегию, он может проиграть не более чем mах–2, –1, 1=1 независимо от выбора своего противника. При второй стратегии проигрыш составит не более mах–4, 3, 2=3. Игрок В выберет тогда первую стратегию, для которой проигрыш составит min1, 3=1. Эта стратегия называется минимаксной, а соответствующее ей значение проигрыша игрока В – минимаксным (верхним) значением игры. 4.8.2. Математическая модель игры. В математических обозначениях «максимин для А» выражается mахiminj aij, аналогично, «минимакс для В» есть minjmахi aij, причем, очевидно, имеет место mахi minj aij  minj mахi aij. В случае, когда имеет место равенство, т.е. mахi minj aij = minj mахi aij =аi0j0, соответствующие чистые стратегии (i0 для игрока А и j0 для В) будут оптимальными, а про игру говорят, что она имеет седловую точку. Тогда аi0j0 является значением игры. Легко видеть, что игра имеет седловую точку тогда и только тогда, когда в платежной матрице имеется элемент аi0j0, наименьший для всех элементов своей строки i0 и наибольший для всех элементов своего столбца j0. При отсутствии седловой точки невозможно получить оптимальное решение, пользуясь чистыми стратегиями. В этом случае для получения решения игры будем пользоваться смешанными стратегиями, которые заключаются в применении чистых стратегий с некоторыми частотами (вероятностями). Пусть р1,р2,..,рm и q1,q2,..,qn – наборы вероятностей, с которыми игроки А и В соответственно выбирают свои чистые стратегии. Естественно =1, рi , qj ≥0 для всех i и j. Если игрок А выбирает свои чистые стратегии с вероятностями рi, то его ожидаемый выигрыш должен составить a11р1+ a21р2+…+ am1рm , при ответном выборе игроком В своей первой чистой стратегии, a12р1+ a22р2+…+ am2рm , при ответном выборе игроком В своей второй чистой стратегии, и т.д. a1nр1+ a2nр2+…+ amnрm при выборе игроком В n-й чистой стратегии. С другой стороны, если игрок В выбирает свои чистые стратегии с вероятностями qj, то его ожидаемый проигрыш должен составить a11q1+ a12q2+…+ a1nqn , если игрок A выберет свою первую чистую стратегию, a21q1+ a22q2+…+ a2nqn, если игрок A выберет свою вторую чистую стратегию и am1q1+ am2q2+…+ amnqn, при выборе игроком A m-й чистой стратегии. Если игрок А выбрал стратегию (р1,р2,..,рm) и при этом игрок В выбрал (q1,q2,..,qn), то ожидаемый выигрыш игрока А (он же проигрыш игрока В) составит g= . Тогда игрок А при выборе рi стремится максимизировать свой наименьший ожидаемый выигрыш по столбцам, тогда как игрок В выбирает qj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Справедлива теорема фон.Неймана[12], которую мы примем без доказательств, утверждающая, что для любой конечной игры существуют оптимальные стратегии игроков А (р1*,р2*,..,рm*) и В (q1*,q2*,..,qn*), при этом максимум наименьшего ожидаемого выигрыша игрока А совпадает с минимумом наибольшего ожидаемого проигрыша игрока В (обозначим это значение игры через g). Таким образом, математическую модель конечной игры для игрока А можно представить в следующем виде: Найти такие рi ≥0, для которых выполняются соотношения р1+р2+…+рm=1, a11р1+ a21р2+…+ am1рm ≥ g, a12р1+ a22р2+…+ am2рm ≥ g, (4.8.1) ……………………. …… a1nр1+ a2nр2+…+ amnрm≥ g, и функция Z=g принимает максимальное значение. Упростим полученную задачу, разделив все ограничения (4.8.1) на значение игры g > 0 и положив хi =рi/g для всех i. (Проведение аналогичных рассуждений для случая g ≤ 0 предоставляется читателю). В силу того, что max g =min 1/g = min(р1/g+р2/g+…+рm/g) = min(x1+x2+…+xm) задача принимает вид минимизировать Z= x1+x2+…+xm при ограничениях a11x1+ a21x2+…+ am1xm ≥ 1, a12x1+ a22x2+…+ am2xm ≥ 1, (4.8.2) ……………………. …… a1nx1+ a2nx2+…+ amnxm≥ 1, x1, x2,…,xm ≥ 0. Мы получили задачу линейного программирования (см. 4.2). Решая ее (например, симплекс–методом), находим оптимальное решение x1*, x2*,…,xm*, откуда, разделив на Z*=x1*+x2*+…+xm*, получаем оптимальную стратегию для игрока А (р1*,р2*,..,рm*), которая заключается в применении i-й чистой стратегии с частотой рi*= хi*/ Z*. Проиллюстрируем использование рассмотренных методов при описании и решении некоторых состязательных задач. Пример 4.8.1. Пусть ежедневный спрос на булочки в магазине задается следующим распределением вероятностей: спрос 100 150 200 250 300 Вероятность спроса 0.20 0.25 0.30 0.15 0.10 Магазин закупает булочки по 2.5 руб. и продает по 4.9 руб. за штуку. Если булочка не продана в тот же день, то она реализовывается по 1.5 руб. Какое наибольшее число булочек необходимо заказывать ежедневно, если величина заказа может принимать одно из возможных значений спроса? Прибыль от продажи «свежей» булочки составляет 4.9–2.5=2.4 руб. Потеря от продажи «черствой» составляет 2.5–1.5=1 руб. Представим модель данной задачи в виде игры магазина со спросом. Стратегия магазина – ежедневный объем заказа, при этом спрос может принимать одно из своих возможных значений. Составим платежную матрицу игры для магазина: Заказ маг-на Возможный ежедневный спрос Ожид. прибыль 100 150 200 250 300 100 240 240 240 240 240 240 150 240-50 360 360 360 360 326 200 240-100 360-50 480 480 480 369.5 250 240-150 360-100 480-50 600 600 362 300 240-200 360-150 480-100 600-50 720 329 На пересечении строки с некоторым объемом заказа и столбца с возможным спросом находится элемент aij – ожидаемая прибыль магазина в этой ситуации. В последней колонке вычислена ожидаемая (средняя) прибыль в случае распределения вероятностей спроса в соответствии с условиями примера. Например, для третьей строки имеем 1400.2+3100.25+4800.3+4800.15+4800.1=369.5. Кстати, выбор этой стратегии (ежедневный заказ – 200 булочек) и будет оптимальным, т.к. обеспечивает максимальную прибыль. Пример 4.8.2. Рассмотрим схожую с предыдущей задачу управления запасами. Пусть спрос на некоторый товар описывается следующим рядом распределения вероятностей: Спрос 1 2 3 4 5 Вероятность спроса 0.10 0.15 0.40 0.15 0.10 0.10 Определить уровень запасов, при котором вероятность полного истощения запасов не превышает 0.45. Определить также уровень запасов при условии, что средние значения дефицита и превышения запасов не должны быть больше 1 и 2 единиц соответственно. Будем анализировать данную задачу как игру уровня запасов со спросом. Для каждого значения уровня запасов последовательно вычисляем вероятность его полного истощения. Она равна сумме вероятностей событий, когда спрос превышает данный запас. Затем вычисляем средний дефицит для каждого уровня запаса. Для уровня 0 средний дефицит равен 10.15+20.4+30.15+40.1+50.1=2.3, для уровня 1 получаем 10.4+20.15+30.1+40.1=1.4 и т.д. Аналогично вычисляем среднее превышение запасов, например, для уровня 0 превышения нет, для уровня 1 среднее превышение составляет 10.1=0.1, для уровня 2 получаем 20.1+10.15=0.35 и т.д. Сведем все результаты расчетов в таблицу 4.8.1. Таблица 4.8.1 Уровень запаса Q Вероятность полного истощения Средний дефицит Среднее превышение запасов 0.9 2.3 1 0.75 1.4 0.1 2 0.35 0.65 0.35 3 0.2 0.3 1.0 4 0.1 0.1 1.8 5 2.7 Из табл. 4.8.1 получаем ответы на все интересующие нас вопросы: При Q ≥2 вероятность полного истощения запасов не превышает 0.45. При 4≥Q≥2 средние значения дефицита и превышения запасов не больше 1 и 2 единиц соответственно. Пример 4.8.3. Введем в пример 4.8.2 условие, чтобы ожидаемый дефицит был меньше превышения хотя бы на 1. Тогда из табл. 4.8.1 находим уровень запасов, удовлетворяющий этому условию, Q ≥4. Правила упрощения платежной матрицы: Если к каждому элементу платежной матрицы прибавить одно и то же число, то решение (р1*,р2*,..,рm*) не изменится, а цена игры изменится ровно на добавленную величину. Если каждый элемент платежной матрицы умножить на одно и то же число, то решение (р1*,р2*,..,рm*) не изменится, а цена игры изменится ровно во столько же раз. Если какая-либо строка платежной матрицы доминирует над другой строкой (или линейной комбинацией строк), то доминируемые строки не войдут в оптимальную смешанную стратегию и их можно удалить. Пример 4.8.4. Рассмотрим тотализатор на ипподроме. Пусть выплаты в случае победы одной из трех лошадей относятся к ставке как 1:1, 3:1 и 4:1. Тогда платежная матрица игрока на скачках примет вид: 1 –1 –1 Если прибавить к каждому элементу матрицы число К, то А= –1 3 –1 оптимальные стратегии не изменятся, а значение игры –1 –1 4 увеличится на К. Для упрощения матрицы добавим К=1, тогда получим: 2 0 0 В соответствие с (4.8.2) задача принимает вид: А= 0 4 0 минимизировать Z= x1+x2+x3 0 0 5 при ограничениях 2x1+ 0x2+0x3 ≥ 1, 0x1+ 4x2+0x3 ≥ 1, 0x1+ 0x2+5x3≥ 1, x1, x2,x3 ≥ 0. Легко заметить, что решение этой задачи: x1*=1/2, x2*=1/4, x3* =1/5. Значение упрощенной игры 1/Z*=1/( x1*+x2*+x3*)=20/19, откуда (при К=1) значение исходной игры равно 20/19 – 1 = 1/19, р1*=х1*/Z*=10/19, р2*=х2*/Z*=5/19, р3*=х3*/Z*=4/19. Таким образом, оптимальная стратегия игрока на скачках в данном примере заключается в смешанной стратегии делать ставки на всех трех лошадей в пропорции 10:5:4, при этом выигрыш игрока (игра имеет положительное значение!) будет равным 1/19 суммы его ставок, независимо от результата гонок. (Если цена игры отрицательна, то не следует в нее играть, так как даже при оптимальной стратегии гарантирован проигрыш, правда, минимальный). Пример 4.8.5. Предлагается три варианта инвестиций в сельское хозяйство и прогноз получения доходов за год (дивиденды и повышение стоимости капитала) при различных перспективах на урожай. Варианты инвестиций Перспективы на урожай хорошие средние плохие 1. АО «Сельхозтехника» 40 30 20 2. АО «Агроимпорт» 100 250 3. АО «Агроэкспорт» 150 50 –50 Доходы в платежной матрице приведены в процентах от вложенного капитала. Как распорядиться капиталом, чтобы получить наибольший доход? Рассматриваем «игру» против природных сил, руководствуясь максиминным принципом, т.е. хотим получить максимальный доход, принимая во внимание наихудшее, что может случиться. Искомые переменные р1, р2, р3 определяют пропорции вложений. Заметим, что элементы первой строки платежной матрицы меньше средних арифметических соответствующих элементов второй и третьей строк, и она может быть удалена (первый вариант инвестиций заведомо неэффективен по сравнению с комбинацией второго и третьего вариантов – вкладывать деньги поровну во второй и третий проект). Получаем задачу линейного программирования минимизировать Z= x2+x3 при ограничениях 0x2 + 150x3 ≥ 1, 100x2+50x3 ≥ 1, 250x2 – 50x3≥ 1, x1=0, x2, x3 ≥ 0. Решая данную задачу стандартными средствами (см.4.2) получим следующее решение x1*=0, x2*=1/150, x3* =1/150. Значение игры 1/Z*=1/( x1*+x2*+x3*)=150/2=75, откуда р1*=0, р2*=х2*/Z*=75/150=1/2, р3*=х3*/Z*=75/150=1/2. Таким образом, оптимальной стратегией является вложение капитала равными долями во второй и третий варианты, при этом гарантированный доход составит 75%. 4.8.3. Понятие коалиционных игр. Ситуация значительно усложняется, когда в игре принимают участие более двух игроков. Водится понятие коалиции игроков, которые пользуются согласованной стратегией против интересов игроков, не входящих в их коалицию. Тогда могут быть вычислены ожидаемые выигрыши (значения игры) для каждой коалиции. В частности, вычисляются значения игры для каждого игрока в предположении, что он играет против коалиции всех других игроков. Обозначим эти значения g1,g2,…,gn. Нормальный выигрыш игрока должен быть не меньше соответствующего значения игры, назовем такой выигрыш обязательством. Таким образом, (s1,s2,…,sn) – обязательство, если si≥gi для i=1,2,…,n и ∑isi=G, где G – значение игры (суммарный выигрыш всех игроков, не обязательно равный нулю). Тогда решением для игры n лиц будет такое множество обязательств, что ни одно обязательство этого множества не доминирует над другими обязательствами того же множества и для любого обязательства, не принадлежащего этому множеству, найдется обязательство нашего множества, доминирующее над ним. (Теорема фон Неймана и Моргенштейна). Отношение доминирования используется только для двух игроков или больше и заключается в превышении выигрышей этих игроков в одном обязательстве по отношению к выигрышам этих же игроков в другом обязательстве. В заключение приведем оценку теории игр, данную Вильямсом: «…хотя в настоящее время уже выяснены, несмотря на множество ограничений теории, многие ее специфические приложения, ее наибольший, пока неявный, вклад состоит в том, что она дает людям, имеющим дело со сверхсложными проблемами, самую общую ориентацию. Даже если эти проблемы не подаются строгому решению, она дает основу для работы над ними. Идея стратегии, различия между игроками, роль случайных событий, понятие матрицы выигрышей, идеи чистой и смешанной стратегии и т.д. дают драгоценную ориентацию лицам, которым необходимо обдумывать сложные конфликтные ситуации». Тема 4.9. Динамическое программирование 4.9.1. Область применения моделей динамического программирования. Элементы динамики и учет времени играли важнейшую роль в некоторых прикладных задачах исследования операций, рассмотренных в предыдущих темах. Однако ранее основное внимание уделялось эффективным методам отыскания численных решений задач большой размерности. В данной теме решающее значение по-прежнему имеет одновременный учет всех ограничений системы, однако излагаемый здесь материал в основном посвящен динамическим структурным зависимостям оптимизационных моделей. Вначале рассматриваются детерминированные задачи, так что в каждой из них процесс решения приводит к однозначному результату. Затем исследуются вероятностные модели. Ниже мы изучим условия, которым должен удовлетворять оптимальный многошаговый процесс принятия решений, и покажем, каким образом использовать эти условия для нахождения лучшего варианта. Подобный анализ часто называют динамическим программированием. Будем рассматривать конечный плановый период, в конце темы обсудим особенности оптимизации в условиях бесконечного планового периода с учетом дисконтирования во времени и приведения экономических показателей к исходному моменту времени. Вот некоторые типичные области применения моделей динамического программирования при принятии решений: • Разработка правил управления запасами, устанавливающих момент пополнения запасов и размер пополняющего заказа. • Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию. • Определение необходимого объема запасных частей, гарантирующего эффективное использование дорогостоящего оборудования. • Распределение дефицитных капитальных вложений между возможными новыми направлениями их использования. • Выбор методов проведения рекламной кампании, знакомящей покупателя с продукцией фирмы. • Систематизация методов поиска ценного вида ресурса. • Составление календарных планов текущего и капитального ремонта сложного оборудования. • Разработка долгосрочных правил замены выбывающих из эксплуатации основных фондов. 4.9.2. Основные идеи динамического программирования. Общей особенностью всех моделей динамического программирования является сведение задачи принятия решений к получению рекуррентных соотношений. Для тех, кто не пользовался подобными формализованными методами для решения задач, связанная с этим система математических обозначений может показаться странной, поэтому рекомендуется прочитать текст не менее двух раз. При первом чтении следует постараться понять смысл поставленной задачи и хорошо ознакомиться с условными обозначениями; при втором чтении больше внимания целесообразно уделить деталям постановки и характеру математических выражений (это правило относится, кстати, и к изучению других тем). На небольшом примере объясним важные идеи динамического программирования, а также введем необходимые условные обозначения. Пример 4.9.1. Рассмотрим транспортную сеть (задача о кратчайшем маршруте). 10 7 2 12 5 3 1 5 5 10 1 7 4 4 15 7 13 1 Рис. 4.9.1. Задача о кратчайшем маршруте. Пусть сij – расстояние (или стоимость переезда) от пункта i в пункт j (на рисунке заданы числами у каждой стрелки). Необходимо выбрать такой путь от пункта 1 до пункта 10, для которого его длина (или общая стоимость переезда) является минимальной. Из пункта 1 можно переехать в пункт 2, 3 или 4; из пункта 2 в пункт 5 или 6 и т.д. Назовем нахождение в пункте – состоянием системы, переезд из пункта в пункт – процессом перехода из одного состояния в другое. Таким образом, переезд из пункта 1 в пункт 3 есть одношаговый процесс, а скажем, из пункта 1 в пункт 10 – многошаговый процесс перехода из состояния 1 в состояние 10. Выбор процесса перехода из состояния i в состояние j назовем стратегией. Допустим, мы нашли оптимальный (в данном случае минимальный) маршрут и находимся в его промежуточном пункте, тогда, независимо от пути достижения этого пункта (состояния), оптимальный путь из данного пункта до конечного состояния есть часть общего оптимального пути. Этот принцип оптимальности впервые был сформулирован Р.Беллманом в 1953 г. Приведем этот принцип в формулировке Елены Сергеевны Вентцель[11]: Каково бы ни было состояние системы в результате некоторого числа шагов, на текущем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Этот принцип верен для задач динамического программирования, в которых процесс управления происходит без обратной связи, т.е. управление на каждом шаге не оказывает влияния на предшествующие шаги. Введем следующие обозначения: fn(s) – стоимость, отвечающая стратегии минимальных затрат для пути от состояния s до конечного состояния, если до него остается n шагов; хn(s) – решение, позволяющее достичь fn(s). Т.е. хn(s) соответствует пути минимальной длины от состояния s до конечного состояния, которое достигается за n шагов. Вернемся к нашему примеру. Рассмотрим последовательно все состояния от последнего до первого. Имеем f0(10)=0 для х0(10)= остановка. Затем f1(8)=1+0=1 для х1(8)=10, f1(9)=4+0=4 для х1(9)=10. Далее f2(5)=min(7+1,5+4)=8 для х2(5)=8, f2(6)=min(3+1,4+4)=4 для х2(6)=8, f2(7)=min(7+1,1+4)=5 для х2(7)=9. Для третьего (с конца) шага имеем: f3(2)=min(10+8,12+4)=16 для х3(2)=6, f3(3)=min(5+8,10+4,7+5)=12 для х3(3)=7, f3(4)=min(15+4,13+5)=18 для х3(4)=7. И, наконец, f4(1)=min(2+16,5+12,1+18)=17 для х4(1)=3. Мы получили оптимальный путь (наименьшей длины или стоимости) равный 17. Он проходит через события 1-3-7-9-10. (При последовательном рассмотрении всех состояний оптимальные переходы выделялись жирным шрифтом). Заметим, что на каждом шаге мы пользовались динамическим рекуррентным соотношением: fn(s)=min(s,j)( сsj + fn-1(j)), n=1,2,3,4. (4.9.1) Очевидно, динамическое программирование здесь более эффективно, чем прямой перебор всех возможных маршрутов, сопровождаемый их оценкой. В данном примере имеется 14 возможных путей; чтобы для каждого определить оценку, придется суммировать четыре числа. Следовательно, для простого перебора потребуется 314=42 операции сложения, тогда как мы управились за 16 операций. Преимущество рекуррентного подхода может оказаться огромным при практическом применении, когда полный перебор обычно неосуществим. 4.9.3. Распределение Q средств между N предприятиями. Пусть хn – средства, выделенные n-му предприятию; они приносят в конце года прибыль сn(хn). Будем считать, что хn принимает только целые значения, прибыль сn(хn) не зависит от вложения средств в другие предприятия и суммарная прибыль равна сумме прибылей, полученных от каждого предприятия. Тогда модель имеет вид: Найти целочисленные неотрицательные переменные хn (n=1,2,…,N), удовлетворяющие ограничению: ∑nхn = Q, (4.9.2) и обращающие в максимум функцию С=∑n сn(хn). (4.9.3) Здесь процесс распределения средств можно рассматривать как многошаговый, номер шага совпадает с номером предприятия; состояние будет определяться величиной sn – количество средств, подлежащих распределению на n-м шаге (с конца). Обозначим fn(sn) – условную оптимальную прибыль, полученную от последних n предприятий при распределении между ними sn средств и вычисляемую в соответствие с динамическим рекуррентным соотношением: fn(sn)=mахх(сn(хn) + fn-1(sn-1)), n=1,2,…,N. (4.9.4) Пример 4.9.2. Пусть N = 4, Q =5, значения сn(хn) заданы в табл. 4.9.1. Таблица 4.9.1. х с4(х) с3(х) с2(х) с1(х) 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Как и в предыдущем примере начинаем анализ с последнего предприятия. Индекс «1» соответствует последнему предприятию, а индекс «4» - первому. Для n=1 прибыль проставлена в последней колонке. Для n=2 f2(0)=mах[с2(0)+f1(0)]=0 при x2(0)=0, f2(1)=mах[с2(1)+f1(0),с2(0)+f1(1)]=mах[3+0,0+4]=4 при x2(1)=0, f2(2)=mах[с2(2)+f1(0),c2(1)+f1(1),с2(0)+f1(2)]= =mах[4+0,3+4,0+6]=7 при x2(2)=1, f2(3)=mах[с2(3)+f1(0),с2(2)+f1(1),с2(1)+f1(2),с2(0)+f1(3)]= =mах[7+0,4+4,3+6,0+8]=9 при x2(3)=1, f2(4)=mах[с2(4)+f1(0),с2(3)+f1(1),с2(2)+f1(2),с2(1)+f1(3),с2(0)+f1(4)]= =mах[11+0,7+4,4+6,3+8,0+13]=13 при х2(4)=0, f2(5)=mах[с2(5)+f1(0),с2(4)+f1(1),с2(3)+f1(2),с2(2)+f1(3),с2(1)+f1(4),с2(0)+f1(5)] =mах[18+0,11+4,7+6,4+8,3+13,0+16]=18 при x2(5)=5. Для n=3 f3(0)=mах[с3(0)+f2(0)]=0 при x3(0)=0, f3(1)=mах[с3(1)+f2(0),с3(0)+f2(1)]=mах[6+0,0+4,]=6 при x3(1)=1, f3(2)=mах[с3(2)+f2(0),c3(1)+f2(1),с3(0)+f2(2)]= =mах[9+0,6+4,0+7]=10 при x3(2)=1, f3(3)=mах[с3(3)+f2(0),с3(2)+f2(1),с3(1)+f2(2),с3(0)+f2(3)]= =mах[11+0,9+4,6+7,0+9]=13 при x3(3)=1 или 2, f3(4)=mах[с3(4)+f2(0),с3(3)+f2(1),с3(2)+f2(2),с3(1)+f2(3),с3(0)+f2(4)]= =mах[13+0,11+4,9+7,6+9,0+13]=16 при х3(4)=2, f3(5)=mах[с3(5)+f2(0),с3(4)+f2(1),с3(3)+f2(2),с3(2)+f2(3),с3(1)+f2(4),с3(0)+f2(5)] =mах[15+0,13+4,11+7,9+9,6+13,0+18]=19 при x3(5)=1. И, наконец, для n=4 f4(0)=mах[с4(0)+f3(0)]=0 при x4(0)=0, f4(1)=mах[с4(1)+f3(0),с4(0)+f3(1)]=mах[8+0,0+6,]=8 при x4(1)=1, f4(2)=mах[с4(2)+f3(0),c4(1)+f3(1),с4(0)+f3(2)]= =mах10+0,8+6,0+10]=14 при x4(2)=1, f4(3)=mах[с4(3)+f3(0),с4(2)+f3(1),с4(1)+f3(2),с4(0)+f3(3)]= =mах[11+0,10+6,8+10,0+13]=18 при x4(3)=1, f4(4)=mах[с4(4)+f3(0),с4(3)+f3(1),с4(2)+f3(2),с4(1)+f3(3),с4(0)+f3(4)]= =mах[12+0,11+6,10+10,8+13,0+16]=21 при х4(4)=1, f4(5)=mах[с4(5)+f3(0),с4(4)+f3(1),с4(3)+f3(2),с4(2)+f3(3),с4(1)+f3(4),с4(0)+f3(5)] =mах[18+0,12+6,11+10,10+13,8+16,0+19]=24 при x4(5)=1. Теперь соберем оптимальное решение (при последовательном рассмотрении всех состояний оптимальные переходы подчеркивались): Для первого предприятия, когда s4=5, видим, что x4(5)=1, значит, первое предприятие получает 1 и остается s3=s4–x4(5)=5–1=4. Находим лучшее размещение средств для второго предприятия (на третьем с конца шаге) при s3 =4. Это х3(4)=2, остается s2=s3–x3(4)=4–2=2. На втором (с конца) шаге x2(2)=1 и на последнее предприятие (первый с конца шаг) остается s1 = s2 – x2(2)=2–1=1 и x1(1)=1. Максимум суммарной прибыли равен 24 у.е. 4.9.4. Динамическая задача управления запасами. Применим изложенный выше подход к решению простейшей задачи управления запасами. Пример 4.9.3. Необходимо разработать такую календарную программу выпуска изделия на плановый период, состоящий из Т временных отрезков, при которой общая сумма затрат на производство и на содержание запасов минимизируется при условии полного и своевременного удовлетворения спроса. Обозначим: dn – спрос на отрезке n от конца; cn(x,s) – затраты на отрезке n, связанные с выпуском х единиц изделия и с содержанием запасов, объем которых на конец отрезка равен s единиц. В этой системе обозначений подстрочный индекс «1» соответствует конечному, а «Т» - начальному состоянию. Состояние системы в начале каждого отрезка определяется уровнем запасов, поэтому для принятия решения об объеме выпуска не нужно знать, каким образом достигнут этот уровень, т.е. опять же имеем систему без обратной связи. Пусть fn(s) – стоимость, отвечающая стратегии минимальных затрат на n оставшихся отрезках при уровне запасов s на начало n-го от конца отрезка; xn(s) – объем выпуска, обеспечивающий достижение fn(s). Пусть уровень запасов на конец планового периода равен нулю, тогда при уровне запасов s на начало последнего (1-го от конца) отрезка выпуск x1(s)= d1–s и f1(s)= c1(x,0)= c1(d1 – s,0), s=0,1,…,d1. Заметим, что если начальный уровень запасов отрезка n равен s, а объем выпуска – х, то величина (s+х–dn) – есть уровень запасов на конец данного отрезка, отсюда получаем общее рекуррентное соотношение в виде: fn(s) = minx[cn(x, s+х–dn)+ fn-1(s+х–dn)], n=1,…,Т, s=0,1,…,d1+…+ dn. Для упрощения вычислений предположим, что производственные мощности и складские площади ограничены, пусть х=0,1,…,5 и s=0,1,…,4. Допустим также, что спрос и затраты постоянны во времени, и пусть dn=3, а cn(x, s)= c(x)+hs, где первое слагаемое относится к производству, а второе определяется стоимостью содержания запасов (арендная плата за складские помещения, проценты за кредит для создания запасов, страховые взносы и собственно расходы по содержанию запасов). Пусть с(0)=0, с(1)=15, с(2)=17, с(3)=19,с(4)=21, с(5)=23; h=1. Для n=1 f1(0)=с(3)=19 при x1(0)=3, f1(1)=с(2)=17 при x1(1)=2, f1(2)=с(1)=15 при x1(2)=1, f1(3)=с(0)=0 при x1(3)=0. Для n=2 f2(0)=min[с(3)+0+f1(0),c(4)+1+f1(1),c(5)+2+f1(2)]= =min[19+19,21+1+17,23+2+15]=38 при x2(0)=3, f2(1)=min[с(2)+0+f1(0),c(3)+1+f1(1),c(4)+2+f1(2),c(5)+3+f1(3)]= =min[17+19,19+1+17,21+2+15,23+3+0]=26 при x2(1)=5, f2(2)=min[с(1)+0+f1(0),c(2)+1+f1(1),c(3)+2+f1(2),c(4)+3+f1(3)]= =min[15+19,17+1+17,19+2+15,21+3+0]=24 при x2(2)=4, f2(3)=min[с(0)+0+f1(0),c(1)+1+f1(1),c(2)+2+f1(2),c(3)+3+f1(3)]= =min[0+19,15+1+17,17+2+15,19+3+0]=19 при x2(3)=0, f2(4)=min[с(0)+1+f1(1),c(1)+2+f1(2),c(2)+3+f1(3)]= =min[0+1+17,15+2+15,17+3+0]=18 при x2(4)=0. Для n=3 f3(0)=min[с(3)+0+f2(0),c(4)+1+f2(1),c(5)+2+f2(2)]= =min[19+38,21+1+26,23+2+24]=48 при x3(0)=4, f3(1)=min[с(2)+0+f2(0),c(3)+1+f2(1),c(4)+2+f2(2),c(5)+3+f2(3)]= =min[17+38,19+1+26,21+2+24,23+3+19]=45 при x3(1)=5, f3(2)=min[с(1)+f2(0),c(2)+1+f2(1),c(3)+2+f2(2),c(4)+3+f2(3),c(5)+4+f2(4)]= =min[15+38,18+26,21+24,24+19,23+4+18]=43 при x3(2)=4, f3(3)=min[с(0)+0+f2(0),c(1)+1+f2(1),c(2)+2+f2(2),c(3)+3+f2(3),c(4)+4+f2(4)]= =min[0+38,16+26,19+24,22+19,25+18]=38 при x3(3)=0, f3(4)=min[с(0)+1+f2(1),c(1)+2+f2(2),c(2)+3+f2(3),c(3)+4+ f2(4)]= =min[1+26,17+24,20+19,23+18]=27 при x3(4)=0. И, наконец, для n=4 f4(0)=min[с(3)+0+f3(0),c(4)+1+f3(1),c(5)+2+f3(2)]= =min[19+48,21+1+45,23+2+43]=67 при x4(0)=3 или 4, f4(1)=min[с(2)+0+f3(0),c(3)+1+f3(1),c(4)+2+f3(2),c(5)+3+f3(3)]= =min[17+48,19+1+46,21+2+43,23+3+38]=64 при x4(1)=5, f4(2)=min[с(1)+f3(0),c(2)+1+f3(1),c(3)+2+f3(2),c(4)+3+f3(3),c(5)+4+f3(4)]= =min[15+48,18+45,21+43,24+38,23+4+27]=54 при x4(2)=5, f4(3)=min[с(0)+0+f3(0),c(1)+1+f3(1),c(2)+2+f3(2),c(3)+3+f3(3),c(4)+4+f3(4)]= =min[0+48,16+45,19+43,22+38,25+27]=48 при x4(3)=0, f4(4)=min[с(0)+1+f3(1),c(1)+2+f3(2),c(2)+3+f3(3),c(3)+4+ f3(4)]= =min[1+45,17+43,20+38,23+27]=46 при x4(4)=0. Сведем результаты вычислений в таблицу 4.9.2. Таблица 4.9.2. s n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 х1 f1 x2 f2 x3 f3 x4 f4 x5 f5 x6 f6 x7 f7 x8 f8 3 19 3 38 4 48 3,4 67 5 79 4 96 3,4 115 5 127 1 2 17 5 26 5 45 5 64 5 74 5 93 5 106 5 123 2 1 15 4 24 4 43 5 54 4 72 4 91 5 102 4 120 3 19 38 48 67 79 96 115 4 18 27 46 65 75 94 107 Читателю предоставляем возможность проверить результаты вычислений для n = 5  8. Теперь, задаваясь различным уровнем запасов на начало планового периода, можно определить оптимальные стратегии для любого Т от 1 до 8. Так, например, если исходный уровень запасов на начало планового периода равен нулю, то оптимальный календарный план при Т=4 будет: x4(0)=3, x3(0)=4, x2(1)=5, x1(3)=0 или x4(0)=4, x3(1)=5, x2(3)=0, x1(0)=3 и минимальная общая сумма затрат составит 67. Пусть Т=8, тогда минимальная общая сумма затрат составит 127 и x8(0)=5, останется на следующий отрезок 5-3=2, имеем x7(2)=5, значит на следующий отрезок останется 2+5-3=4 и x6(4)=0, останется 4-3=1 и x5(1)=5, останется 1+5-3=3, x4(3)=0, останется 3-3=0, x3(0)=4, останется 4-3=1, x2(1)=5, останется 1+5-3=3 и x1(3)=0. В таблицу 4.9.3 сведем оптимальные стратегии (планы выпуска) для плановых периодов длительностью Т и начальным уровнем запасов равным нулю. Обратим внимание на Т=4. Здесь два оптимальных решения, дающих минимальные затраты 67. При Т=7 имеем три решения с одинаковым значением целевой функции 115. Таблица. 4.9.3 Плановый период Т n=8 янв n=7 фев n=6 мар n=5 апр n=4 май n=3 июн n=2 июл n=1 авг Общая сумма затрат Средне- месячные затраты 1 3 19 19 2 3 3 38 19 3 4 5 48 16 4 3 4 4 5 5 3 67 16.75 5 5 5 5 79 15.8 6 4 5 4 5 96 16 7 3 4 4 4 5 5 5 3 4 4 4 5 5 5 3 115 16.43 8 5 5 5 4 5 127 15.9 Анализ оптимальных вариантов производственной программы, приведенных в табл. 4.9.3, свидетельствует о том, что январский выпуск поначалу возрастает с ростом Т, а затем колеблется около 5, аналогично, среднемесячные затраты испытывают колебания (при минимальном их значении 15.8). Проводя подобный анализ для следующих месяцев (при достаточно большом Т), получим оптимальное решение для бесконечного периода планирования. В условиях настоящего примера таким решением будет повторение производственного цикла (5,5,0,5,0,…) при среднемесячных затратах 15.8. (вычисления опускаем). Приведем общую оценку отличительных особенностей метода динамического программирования. В его основе лежит разбиение задачи с многими ограничениями и большим числом переменных на последовательность шагов, на каждом из которых решается оптимизационная задача меньшей размерности, т.е. задача сводится к следующему виду: 1) Управляемые переменные и соответствующие ограничения группируются по шагам, и многошаговый процесс принятия решений исследуется в определенной последовательности. 2) Для выбора оптимальных значений переменных на рассматриваемом шаге используется значение состояния только на данном шаге. 3) Решение, принимаемое при заданном текущем состоянии системы, оказывает прогнозируемое влияние на состояние системы на последующем шаге. 4) Оптимальность текущего решения оценивается в терминах прогнозируемого экономического эффекта для рассматриваемого шага и всех последующих шагов. 4.9.5. Стохастическое динамическое программирование. В рассмотренных примерах управляемые переменные, а также переменные состояния и шага принимали только целочисленные значения. (Задачи такого рода называют задачами дискретного программирования.) Кроме того, на результаты и переходы из одного состояния в другое не оказывали влияния случайные факторы. Учет случайного характера параметров модели есть предмет анализа стохастического динамического программирования. Рассмотрим небольшой пример, иллюстрирующий основные идеи и методы стохастического динамического программирования. Пример 4.9.4. Задача садовника. Предположим, что каждый год почва может находиться в одном из трех состояний: хорошем (1), удовлетворительном (2) или плохом (3). Пусть k=1 и 2 – две возможные стратегии поведения садовника: не удобрять или удобрять. Оптимальное поведение садовника определяется такой стратегией, при которой он получает наибольший ожидаемый доход через N лет. Обозначим рij(k) – вероятность перехода почвы из состояния i в состояние j при применении садовником стратегии k. Пусть 0.2 0.5 0.3 0.3 0.6 0.1 {рij(1)}= 0 0.5 0.5 , {рij(2)}= 0.1 0.6 0.3 0 0 1 0.05 0.4 0.55 Поясним суть приведенных данных: Если садовник не применяет удобрения (k=1), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.2, в удовлетворительное – 0.5 и в плохое – 0.3. При плохом состоянии (строка 3) с вероятностью 1 почва остается плохой. Если садовник применяет удобрения (k=2), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.3, в удовлетворительное – 0.6 и в плохое – 0.1. При плохом состоянии (строка 3) с вероятностью 0.05 почва станет хорошей, с вероятностью 0.4 удовлетворительной и с вероятностью 0.55 останется плохой. Обозначим rij(k) – доход (или убыток), который получит садовник за одногодичный период, если почва перейдет из состояния i в состояние j при применении садовником стратегии k. Пусть 7 6 3 6 5 – 1 {rij(1)}= 0 5 1 , {rij(2)}= 7 4 0 . 0 0 –1 6 3 –2 Поясним суть приведенных данных: Если садовник не применяет удобрения (k=1), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 7 единиц, в удовлетворительное – 6 и в плохое – 3. При переходе из плохого состояния (строка 3, вспомним, что в этом случае с вероятностью 1 почва остается плохой) доход составит –1 (убыток). Если садовник применяет удобрения (k=2), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 6, в удовлетворительное – 5 и в плохое – убыток в размере 1 (не в коня корм). При переходе из плохого состояния (строка 3) в хорошее доход составит 6, в удовлетворительное – 3 и в плохое – убыток 2. Обозначим vi(k) – ожидаемый доход, обусловленный одним переходом из состояния i при стратегии k, тогда vi(k)=∑jpij(k)rij(k). Если удобрения не применяются (k=1), тогда v1(1)=0.27+0.56+0.33=5.3, v2(1)=00+0.55+0.51=3, v3(1)=00+00+1 (–1)= –1. При использовании удобрений (k=2) имеем v1(2)=0.36+0.65+0.1 (–1)=4.7, v2(2)=0.17+0.64+0.30=3.1, v3(2)=0.056+0.43+0.55 (–2)=0.4. Как и прежде будем анализировать плановый период с конца, обозначим fn(i) – оптимальный ожидаемый доход за n лет до конца периода, тогда рекуррентные соотношения примут вид: f1(i)=maxk{vi(k)}, fn(i)=maxk{vi(k)+∑jpij(k)fn-1(j)}, n=2,3,…,N. (4.9.4) Проведем вычисления при N=4. Результаты поместим в таблицы 4.9.4 – 4.9.7. n=1 Таблица. 4.9.4 i vi(k) Оптимальное решение k=1 k=2 f1(i) k* 1 5.3 4.7 5.3 1 2 3 3.1 3.1 2 3 –1 0.4 0.4 2 n=2 Таблица. 4.9.5 i vi(k)+pi1(k)f1(1)+pi2(k)f1(2)+pi3(k)f1(3) Оптимальное решение k=1 k=2 f2(i) k* 1 5.3+.25.3+.53.1+.3.4= =8.03 4.7+.35.3+.63.1+.1.4= =8.19 8.19 2 2 3+05.3+.53.1+.5.4= =4.75 3.1+.15.3+.63.1+.3.4= =5.61 5.61 2 3 –1+05.3+03.1+10.4= = –0.6 .4+.055.3+.43.1+.55.4= =2.13 2.13 2 n=3 Таблица. 4.9.6 i vi(k)+pi1(k)f2(1)+pi2(k)f2(2)+pi3(k)f2(3) Оптимальное решение k=1 k=2 f3(i) k* 1 5.3+.28.19+.55.61+.32.13= =10.38 4.7+.38.19+.65.61+.12.13= =10.74 10.74 2 2 3+08.19+.55.61+.52.13= =6.87 3.1+.18.19+.65.61+.32.13= =7.92 7.92 2 3 –1+08.19+05.61+12.13= = 1.13 .4+.058.19+.45.61+.552.13= =4.23 4.23 2 n=4 Таблица. 4.9.7 i vi(k)+pi1(k)f3(1)+pi2(k)f3(2)+pi3(k)f3(3) Оптимальное решение k=1 k=2 f4(i) k* 1 5.3+.210.74+.57.92+.34.23= =12.68 4.7+.310.74+.67.92+.14.23= =13.097 13.10 2 2 3+010.74+.57.92+.54.23= =9.075 3.1+.110.74+.67.92+.34.23= =10.195 10.19 2 3 –1+010.74+07.92+14.23= = 3.23 .4+.0510.74+.47.92+.554.23=6.4315 6.43 2 Из оптимального решения следует, что в 1-й,2-й и 3-й годы садовник должен применять удобрения (k*=2) при любом состоянии почвы, а в 4-й год (n=1) садовнику следует применять удобрения только при условии, что состояние почвы удовлетворительное или плохое. Суммарный ожидаемый доход за четыре года составит f4(1)=13.10 при хорошем состоянии почвы в первый год, f4(2)= 10.19 при удовлетворительном состоянии и f4(3)=6.43 при плохом состоянии. Приведенный выше метод решения задачи называют еще методом итераций по стратегиям. Задачу садовника можно обобщить в двух отношениях. Во-первых, переходные вероятности и значения дохода не обязательно одни и те же в любой год; в этом случае они являются функциями n-го этапа: pij(k,n) и rij(k,n). Во-вторых, можно использовать коэффициент дисконтирования ожидаемых доходов, вследствие чего значения fN(i) будут представлять собой приведенные величины ожидаемых доходов по всем этапам. Если α – годовой коэффициент дисконтирования, вычисляемый по формуле α=1/(1+t), где t – годовая норма процента, то рекуррентное соотношение (4.9.4) преобразуется к виду: fn(i)=maxk{ vi(k)+α∑jpij(k)fn-1(j)}, n=2,3,…,N. (4.9.5) Упражнение. Решите задачу садовника при коэффициенте дисконтирования α=0.6. (ответ приводится в таблице 4.9.8). Таблица. 4.9.8 i n=1 n=2 n=3 n=4 f1(i) k* f2(i) k* f3(i) k* f4(i) k* 1 5.3 1 6.94 1 7.77 1 8.26 1 2 3.1 2 4.61 2 5.43 2 5.92 2 3 0.4 2 1.44 2 2.19 2 2.66 2 Заметим, что использование коэффициента дисконтирования приводит к другим оптимальным стратегиям. В данном случае при хорошем состоянии почвы удобрения не требуются в течение всех четырех лет. Для определения оптимальной долгосрочной стратегии применяют два метода. Первый метод основан на переборе всех возможных стационарных стратегий управления и может быть использован при их малом числе. Второй метод (итераций по стратегиям) более эффективен в том смысле, что определяет оптимальную стратегию за малое число итераций. Идея метода заключается в использовании соотношения (4.9.4) при n → ∞. Итак, задача стохастического динамического программирования включает в себя матрицу переходных вероятностей системы из состояния i в момент времени tn-1 в состояние j в момент tn. Матрица переходных вероятностей совместно с исходными вероятностями состояний полностью определяет марковскую цепь. Можно задачу стохастического динамического программирования (Марковскую задачу принятия решений) сформулировать как задачу линейного программирования (см. тему 4.2), однако в вычислительном отношении метод итераций по стратегиям более эффективен. Для задач с К альтернативами решений на каждом шаге и N состояниями соответствующая модель линейного программирования включает (N+1) ограничений и NК переменных. 4.9.6. Задачи износа и замены оборудования Основными задачами теории замен являются прогноз затрат, связанных с обновлением оборудования, и выработка наиболее экономичной стратегии замен. В зависимости от характера оборудования процессы замен делятся на два класса. Первый связан с оборудованием, которое, устаревая в процессе эксплуатации, становится менее производительным физически вследствие износа или морально в результате появления новых, более совершенных машин (сюда относятся, например, металлорежущие станки, автомобили и т.д.). Эксплуатация устаревшего оборудования связана с ростом производственных затрат, удлинением времени простоя, увеличением числа отказов и длительности ремонта и т.д. Вместе с тем замена старого оборудования новым также сопряжена с расходами. Необходимо определить такой срок службы оборудования, при котором экономия за счет приобретенного нового оборудования начинает превышать компенсацию его первоначальной стоимости. При аренде оборудования необходимо учитывать подобные соображения: при увеличении срока аренды уменьшается арендная плата в единицу времени, зато возрастают эксплутационные расходы. Второй класс задач связан с оборудованием со случайной длительностью срока службы (например, лампы освещения, элементы микросхем). При решении задач второго класса приходится определять, какие именно единицы оборудования следует заменить и как часто следует проводить замену с тем, чтобы минимизировать общие затраты. Если замену оборудования производить лишь после его выхода из строя, то при минимуме затрат на обновление возрастают расходы, связанные с простоями, тогда как замена деталей до их поломки приводит к высокой стоимости оборудования, но зато к малым затратам на некомплектность. Базой для решения этих задач является наличие закона распределения вероятностей повреждения (отказа) оборудования в зависимости от срока его службы, для чего должны быть задействованы методы математической статистики. Пусть сi – затраты на приобретение (включаются в с1) и эксплуатацию оборудования в период i. Здесь учитываются только эксплутационные затраты, которые изменяются с ростом срока службы. Тогда период n, после которого должна быть произведена замена, определяется из следующих соображений: 1. Если издержки в следующем периоде ниже средней величины прошлых затрат, то оборудование заменять не следует. 2. Если же издержки в следующем периоде превосходят величину средних затрат, то оборудование следует заменить. Т.е. должны выполняться следующие неравенства сn <(с1+ с2 +…+сn-1)/(n – 1), (4.9.6) сn+1 >(с1 + с2+…+сn)/n. (4.9.7) Пример 4.9.5. Пусть расходы, связанные с приобретением и заменой оборудования, представлены в табл. 4.9.9. Таблица 4.9.9 Период затраты средние 1 50 50 2 10 30 3 20 26,7** 4 30 27,5 5 40 30 6 50 33,3 В третьей колонке вычисляем средние значения затрат и видим, что замена оборудования должна производиться в третий период, т.к. с3 =20 <(с1+ с2)/2=30, а с4 =30 >(с1 + с2+с3)/3=26,7. Цена денег, ввиду наличия процентов на капитал, меняется со временем. Проведем расчеты с учетом коэффициента дисконтирования. Пусть r – учетный процент в течение каждого периода, тогда обозначим d=1/(1+r/100). В правой части неравенств (4.9.6) – (4.9.7) средние затраты заменяются на средневзвешенные затраты: сn <(с1+ с2 d +…+сn-1 d n-2)/(1+ d+…+d n-2), (4.9.8) сn+1 >(с1 + с2 d +…+сn d n-1)/(1+ d+…+ d n-1). (4.9.9) Пример 4.9.6. Пусть расходы, связанные с приобретением и заменой оборудования, аналогичны предыдущему примеру и r =5%. В колонке 3 табл. 4.9.10 вычисляем средневзвешенные затраты (d=0,952): Таблица 4.9.10 Период i Затраты ci Средне-взвешенные 1 50 50 2 10 30.49 3 20 27.16* 4 30 28.82 5 40 30.02 6 50 32.96 В данном случае замена оборудования должна производиться также в третий период, т.к. соотношения (4.9.8)-(4.9.9) выполняются для n=3. В обоих примерах мы предполагали, что затраты на эксплуатацию стареющего оборудования возрастали со временем. Рассмотрим теперь задачу замены оборудования как многошаговый процесс динамического программирования. Пусть величина cij представляет собой сумму покупной цены и ожидаемых расходов на ремонт и обслуживание оборудования, приобретенного в начале года i, за вычетом остаточной стоимости этого оборудования на начало года j. Примем следующее обозначение: fi – величина затрат, соответствующая стратегии замены, минимизирующей эти затраты в интервалах i, i+1,…, n, в предположении, что новое оборудование приобретается в год i. Тогда для нахождения оптимальной стратегии нам необходимо вычислить f1(минимальные затраты и соответствующую стратегию с первого шага), пользуясь следующим рекуррентным соотношением: fn+1 =0, fi =minj>i{cij + fj}, i=n, n-1, …, 1. (4.9.10) Предположим, что затраты, отвечающие некоторой стратегии замены, включают две составляющие: рik – стоимость замены оборудования возраста k на интервале i за вычетом его остаточной стоимости; rik – стоимость эксплуатации оборудования возраста k на интервале i. Пусть fi(k) – стратегия, минимизирующая затраты на интервалах i, i+1,…, n, при условии, что в начале интервала i возраст оборудования составляет k лет. Если оптимальное решение состоит в сохранении оборудования в интервале i, то fi(k) =rik+1 +fi+1(k+1), но если оптимальное решение сводится к его замене, то fi(k) =рik +ri1 +fi+1(1). Таким образом, имеем fi(k) =min{rik+1 +fi+1(k+1), рik +ri1 +fi+1(1)}, i=1,2,…,n, (4.9.11) где fn+1(k)=0 для всех k. Пусть К – возможный срок службы оборудования. Мы планируем на n лет, поэтому начало (n+1)-го периода соответствует концу нашего планового периода. Нахождение оптимального решения заключается в вычислении f1(k0), где k0 – возраст оборудования на начало планового периода. Если в это время рассматриваемая единица оборудования отсутствует, то нет смысла говорить о его сохранении при i=1, а решение о замене есть просто покупка нового оборудования. Пример 4.9.7. Необходимо составить план замены оборудования на пять лет при условии отсутствия его в начале первого года, прогнозируемые затраты сведены в таблицы 4.9.11 и 4.9.12. Таблица 4.9.11. Значения rik Таблица 4.9.12. Значения рik 1 2 3 4 5 1 2 3 4 1 10 1 100 2 8 16 2 55 3 6 12 18 3 60 80 4 4 8 12 20 4 65 85 105 5 10 15 20 5 70 90 110 115 Пустые клетки в таблицах образовались из того факта, что в начале планового периода оборудования нет, оно только приобретается, поэтому нет нужды прогнозировать некоторые затраты, например, в год 3 не будет оборудования с возрастом 4, или на начало любого года не будет оборудования с пятилетним возрастом, поэтому колонка 5 в табл. 4.9.12 отсутствует. Применим рекуррентное соотношение (4.9.11): f6(k) =0 для всех k. i=5 (в начале года 5 возраст не может быть больше 4): f5(4) =min{r55 +f6(5), р54 +r51 +f6(1)}=min{200+0,115+10+0}=125, f5(3) =min{r54 +f6(4), р53 +r51 +f6(1)}=min{85+0,110+10+0}=85, f5(2) =min{r53 +f6(3), р52 +r51 +f6(1)}=min{40+0,90+10+0}=40, f5(1) =min{r52 +f6(2), р51 +r51 +f6(1)}=min{20+0,70+10+0}=20. i=4 (в начале года 4 возраст не может быть больше 3): f4(3) =min{r44 +f5(4), р43 +r41 +f5(1)}=min{120+125,105+14+20}=139, f4(2) =min{r43 +f5(3), р42 +r41 +f5(1)}=min{52+85,85+14+20}=119, f4(1) =min{r42 +f5(2), р41 +r41 +f5(1)}=min{28+40,65+14+20}=68. i=3 (в начале года 3 возраст не может быть больше 2): f3(2) =min{r33 +f4(3), р32 +r31 +f4(1)}=min{68+139,80+16+68}=164, f3(1) =min{r32 +f4(2), р31 +r31 +f4(1)}=min{32+119,60+16+68}=144. i=2 (в начале года 2 возраст не может быть больше 1): f2(1) =min{r22 +f3(2), р21 +r21 +f3(1)}=min{36+164,55+18+144}=200. Т.к. по условию примера в начале первого года мы приобретаем новое оборудование, то f1(0) = р11 +r11 +f2(1)=100+20+200=320. Таким образом, оптимальная стратегия заключается в следующем: В начале третьего года заменяем оборудование, купленное в начале первого года, и эксплуатируем его до конца планового периода. Выше мы рассматривали детерминированный вариант задачи о замене оборудования, где с индексом k была связана продолжительность нормально эксплуатируемого устройства. В стохастическом варианте задачи восстановления допускается, что устройство может выйти из строя еще до запланированного момента замены (тогда оно заменяется в следующий за поломкой момент времени). Пусть нам известны pj – вероятности того, что поломка оборудования произойдет в j–й момент его использования (j