Учебное пособие Математические методы в инновационном менеджменте
Работа добавлена на сайт bukvasha.net: 2015-10-30Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
Отчет о разработке раздела учебного пособия
в рамках выполнения тематического модуля №1
дисциплины
“Математические методы в управлении и экономике ”
для подготовки магистров по программе
«Технологии менеджмента качества и инноваций»
Направление «Менеджмент»
Факультет: Экономики и менеджмента
Кафедра: Инновационного менеджмента
Курс – 1
Семестр - 1
Всего часов лекций по курсу | 36 ч | Количество лекций - 18 | ||||
Модуль обеспечивает | 6 ч. | 1-ю, 2-ю и 3-ю лекции | ||||
Объем | Общий | Л1 | Л2 | Л3 | ||
п.л. | 5,50 | 3,43 | 1,3 | 0,77 | ||
рис. | 25 | 16 | 9 | - | ||
табл. | 18 | 6 | 8 | 4 | ||
формул | 60 | 36 | 20 | 4 | ||
Автор
д.в.н., профессор Мардас А. Н.
2007
Федеральное агентство по образованию
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
МАРДАС А.Н.
КОРОЛЕВ А.В.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ В УПРАВЛЕНИИ И ЭКОНОМИКЕ
Учебное пособие для студентов магистратуры
«Технологии менеджмента качества и инноваций»
Санкт-Петербург
2007
ББК 65.290-2я7
УДК 65.012.123
Мардас А.Н., Королев А.В.
Математические методы в управлении и экономике. СПб: Издательство СПбГЭТУ «ЛЭТИ», 2007. - с.
ISBN
Учебное пособие содержит системное рассмотрение методологии экономико-математического моделирования в приложении к менеджменту качества и инноваций. Оно разработано в рамках инновационного образовательного проекта в соответствии с требованиями Государственного образовательного стандарта для подготовки магистров по программе «Технологии менеджмента качества и инноваций».
Пособие будет также полезным аспирантам и преподавателям экономических вузов и колледжей, менеджерам и сотрудникам производственных, торговых, финансовых и консалтинговых фирм.
Ó МАРДАС А.Н., КОРОЛЕВ А.В.
Ó Издательство СПбГЭТУ «ЛЭТИ» , 2007.
СОДЕРЖАНИЕ
стр.
1. Методы дискретной математики в экономике и управлении ……….5
1.1. Обзор общих экономико-математических методов………………..5
1.2. Специальные задачи сетевого планирования и управления………62
1.3. Специальные транспортные задачи и алгоритмы (ч.1)…………..83
1. Методы дискретной математики в экономике и управлении
1.1.Обзор общих экономико-математических методов
Основные понятия экономико-математического моделирования. Отличия операций и математических моделей традиционной и инновационной экономики.
Результат моделирования и стратегия действий в инновационном процессе. Обзор теории графов и классических методов СПУ. Характеристика линейного и нелинейного программирования. Обзор общих методов дискретного программирования.
Моделирование как метод выбора и обоснования решения
Описание экономических систем математическими методами дает заключение о реальных объектах и связях по результатам выборочного обследования или моделирования. Чем сложнее ситуация принятия решения, чем больше альтернатив и неопределенных факторов, тем важнее спрогнозировать результат, проиграть возможные варианты действий. Это и достигается путем моделирования.
Под моделированием понимают научный метод исследования, основанный на наличии определенного соответствия (аналогии) между исследуемым объектом и другим вспомогательным объектом и позволяющий по результатам исследования второго объекта делать обоснованные выводы о первом объекте. Изучаемый объект называют оригиналом (натурой), а вспомогательный – моделью. Таким образом, моделирование дает возможность результаты исследования модели переносить на оригинал, замещать при исследовании оригинал моделью.
Полное сходство между оригиналом и моделью не является необходимым, да и достигнуть его невозможно. Явления объективного мира обладают бесконечным числом свойств. Чтобы построить модель какого-либо явления, рассматривается не вся совокупность его свойств, а только часть, весьма незначительная и самая существенная для целей данной задачи.
Среди признаков, по которым классифицируют модели, выделяют два основных: по характеру подобия и по характеру использования.
По характеру подобия различают модели геометрического подобия, модели аналоги и математические модели.
Пример модели геометрического подобия – модель самолета в аэродинамической трубе.
Пример модели-аналога – глобус.
Под математической моделью понимают систему математических и логических соотношений, описывающих при определенных ограничениях и допущениях структуру и процессы, протекающие в моделируемом объекте. С помощью математической модели можно по известным исходным данным получить новые, заранее неизвестные данные об исследуемом объекте или явлении. Математическая модель является наиболее общей и абстрактной моделью.
Модели без управления являются описательными и не содержат управляемых параметров. В рамках такого подхода познание развивается в соответствии с общим научным методом, предполагающим:
· формулировку гипотезы с учетом соотношений между наблюдаемыми данными;
· сбор статистических данных и представление гипотезы в сжатой или математической форме;
· модификацию или улучшение гипотезы.
Например, известно, что с ростом цены объем спроса сокращается. Опираясь на это утверждение, на этапе представления гипотезы о связи двух данных величин в математической форме (или, как говорят математики, спецификации модели) можно предложить несколько зависимостей, отражающих данный факт. Например, линейную, логарифмическую или некую иную. Выбор формы зависимости определяется выводами экономической теории. Вместе с тем, этот вид может быть обусловлен знаниями о характере связи на основе эмпирических данных, в конце концов, субъективными предположениями исследователя. При этом любая из моделей будет упрощением реальности и только определенным приближением к ней. Поэтому из всех допустимых описательных моделей с помощью стандартных методов следует подобрать ту, которая в наибольшей степени соответствует эмпирическим данным и характеру реальной связи.
Можно выделить три класса подобных (эконометрических) моделей:
1. Модель временных данных (в которых результативный признак является функцией переменной времени или переменных, относящихся к другим моментам времени).
К моделям временных данных, представляющих собой зависимость результативного признака от времени, относятся модели:
• тренда (зависимости результативного признака от трендовой компоненты);
• сезонности (зависимости результативного признака от сезонной компоненты);
• тренда и сезонности.
К моделям временных данных, представляющих собой зависимость результативного признака от переменных, датированных другими моментами времени, относятся модели:
• объясняющие поведение результативного признака в зависимости от предыдущих значений факторных переменных (модели с распределенным лагом);
• объясняющие поведение результативного признака в зависимости от предыдущих значений результативных переменных (модели авторегрессии);
• объясняющие поведение результативного признака в зависимости от будущих значений факторных или результативных переменных (модели ожиданий).
Модели временных данных подразделяют также на модели, построенные по стационарным и нестационарным временным рядам. Стационарные временные ряды - ряды, имеющие постоянное среднее значение и колеблющиеся вокруг него с постоянной дисперсией. В таких рядах распределение показателя - уровня ряда - не зависит от времени, т. е. стационарный временной ряд не содержит трендовой или сезонной компонент. В нестационарных временных рядах распределение уровня ряда зависит от переменной времени.
2. Регрессионная модель с одним уравнением.
В таких моделях результативный признак (зависимая переменная) представляется в виде функции факторных признаков (независимых переменных). Примером регрессионных моделей с одним уравнением. Могут служить функция цены, функция спроса а так же производственная функция представляющая собой зависимость объема производства от затрат капитала и затрат труда.
3. Системы одновременных уравнений.
Эти модели описываются системами взаимосвязанных регрессионных уравнений. Система «объясняет», а также прогнозирует столько результативных признаков, сколько поведенческих уравнений входит в систему. Примером системы одновременных уравнений является модель спроса и предложения, включающая уравнение предложения, уравнение спроса и тождество равновесия.
После выбора математической модели на основе имеющихся статистических данных производят оценку параметров избранной зависимости (этап параметризации). Поэтому вопрос точности статистической информации является одним из ключевых для построения работоспособной модели. Чаще всего для получения численных значений прибегают к методам регрессионного анализа.
Проверка качества найденных оценок параметров, а также соответствие всей модели эмпирическим данным и теоретическим предпосылкам носит название верификация. Она проводится по схеме проверки статистических гипотез. На этом этапе совершенствуется не только форма модели, но и уточняется состав ее объясняющих переменных.
Общая схема эконометрического эксперимента позволяет решать следующие задачи:
· прогнозировать развитие рынка;
· определять параметры инвестиционной, финансовой или социальной политики;
· проводить рациональное ценообразование;
· регулировать распределительные и социально-экономические показатели, в развитии анализируемой экономической системы;
· проводить имитацию сценариев социально-экономического развития страны, региона и т. п.
Под оптимизационными моделями понимают те модели, которые содержат управляемые параметры и позволяют исследовать, как влияют на эффективность системы или операции изменения управляемых параметров, и найти оптимальные значения этих параметров (оптимальное решение).
Построение моделей помогает привести сложные и подчас неопределенные ситуации, в которых приходится менеджеру принимать решение, в логически стройную систему, доступную для детального анализа. Такая модель позволяет выявить альтернативные решения и оценить результаты, к которым они приводят. Другими словами модель является средством формирования четкого представления о действительности.
Проведение математического эксперимента никогда не является самоцелью и происходит в рамках разрешения определенной экономической проблемы, что требует выполнения ряда этапов. Можно выделить следующие этапы:
· постановка (формулировка) задачи;
· построение модели;
· отыскания решения;
· проверка модели и оценка решения;
· внедрение решения и контроль его правильности.
На первом этапе главную роль играет лицо или группа лиц, ответственных за принятие решения в экономической системе. Здесь должны быть сформулированы цель деятельности и возможные пути ее достижения, т.е. определено то, что мы называем «множеством стратегий». Неверный выбор цели может лишить смысла всякие дальнейшие исследования и даже привести к вредным последствиям. Поэтому здесь иногда бывает полезным привлечение математика к выбору цели. Если планируемая операция преследует несколько целей, то необходимо выделить основные и каждой из них поставить соответствие свой критерий эффективности. Как правило, этот критерий и будет результирующим показателем в эконометрической модели.
Второй этап - построение математической модели - поле деятельности математика-экономиста. Для построения модели следует определить множество параметров, которые используются для задания зависимости, характеризующих рассматриваемый процесс. При построении математической модели записывается критерий эффективности процесса, являющийся математическим эквивалентом цели. Уровень достижения цели характеризуется именно этим критерием. В математической модели критерий полностью заменяет цель.
При реализации третьего этапа, состоящего в поиске оптимальных стратегий на основании построенной модели, широкие применения находят различные математические методы, которые могут быть распределены на две группы: аналитические и численные (имитационные). Применение численных методов предусматривает разработку алгоритмов и программ для компьютеров, без которых немыслим масштабный эконометрический эксперимент.
Четвертый этап предусматривает проверку адекватности модели исследуемого процесса и оценку полученного решения. Оценка решения может быть проведена путем сравнения результатов, если бы это решение не принималось, и результатов, к которым приводит принятое решение. Здесь очень важно учесть степень влияния различных колебаний параметров системы на исход процесса при использовании полученного решения.
На пятом этапе полученное решение должно быть сформулировано таким образом, чтобы оно было понятно тем, кто ответственен за принятие этого решения. Здесь может появиться необходимость в проведении дополнительных работ, связанных с совершенствованием имеющейся модели и улучшением полученного решения.
Рассмотрим пример формализации простейшей экономической задачи.
Пример. (Определение оптимального плана выпуска продукции).
Имеется видов резервов в количестве, определяемом вектором , которые могут использоваться для производства видов продукции. Норма расхода -го ресурса на производство одной единицы -й продукции определяется величиной , ; . Эффективность выпуска единицы -й продукции характеризуется показателем , . Цель моделирования состоит в том, чтобы определить такой план выпуска продукции, при котором общий эффект от проведения данной операции окажется максимальным.
Построим математическую модель процесса. Для этого планируемый выпуск продукции обозначим через , .
Критерий эффективности в этом случае может быть записан в виде
.
Учитывая имеющееся количество ресурсов, запишем ограничения, которые определяют допустимую область решений:
, .
Задача такого исследования состоит в поиске неотрицательных значений переменных , которые удовлетворяют ограничениям и обращают в максимум критерий эффективности.
В этой задаче факторы (нормы расхода ресурсов, показатели эффективности единицы продукции) известны и носят детерминированный характер. Это означает, что задача относится к классу детерминированных и может быть решена с помощью методов линейного программирования.
Однако такие задачи в экономике, скорее исключение, чем правило. Мы их будем рассматривать прежде всего при описании внутренней среды предприятия (организации).
Основные понятия теории графов
Теория графов сформировалась в 30-е годы XX в. и широко применяется во многих разделах науки и техники. Ее методы успешно используются в теории информации и коммуникационных сетей, планировании производства, генетике и химии, на транспорте и т. д.
Геометрически граф – это набор вершин (точек), определенные пары которых соединены линиями. Например, сеть дорог между городами можно представить в виде графа следующим образом. Города обозначим точками (вершинами), а дороги - неориентированными линиями (рис. 1.1). То, что линии не ориентированы, означает наличие двустороннего движения между соответствующей парой городов. Пересечения линий не считаются вершинами.
Рассмотрим другой пример.
Производственный участок изготовляет два вида изделий Е9 и Е10. Изделие Е9 собирается из узлов Е6, Е7 и детали Е2, а изделие Е10 — из узлов Е7, Е8 и детали Е5. В свою очередь узел Е6 собирается из двух деталей Е1 и одной детали Е2, узел Е7 — из деталей Е2, Ез и Е5. а узел Е8 — из деталей Е4 и Е5.
Применяемость узлов и деталей при сборке можно изобразить в виде графа (рис. .2). Вершинам графа ставят в соответствие узлы, детали и изделия, а связи между ними (вхождение деталей в узлы и изделия и узлов в изделия) отображают ориентированными линями.
Введем теперь для математической формализации необходимые определения.
Математически конечным графом
G
называется пара (Е, е), где Е — непустое конечное множество элементов (вершин), а е—конечное (возможно, пустое) множество пар элементов из Е (дуг или ребер). Символически граф можно записать G
=(Е,е).
Дугой называется ориентированная пара (Еi
, Е
j
) вершин графа, где Еi
— начальная вершина дуги, а — Еj
конечная. При графическом отображении порядок вершин указывает стрелка на дуге.
Дуга вида (Еj
, Е
j
) называется петлей. Дуги называются кратными, если их начальные и конечные вершины совпадают. В некоторых случаях дугу обозначают одной буквой с индексом. Пару дуг с одинаковыми номерами вершин и противоположной ориентацией объединяют и изображают линией без стрелки (см. рис. 1.1). Такое объединение дуг называют ребром.
Два ребра (две дуги) называются смежными, если они имеют хотя бы одну общую вершину. Ребра (одинаково направленные дуги) называются кратными, если их концевые точки совпадают.
Рис. 1.1. Рис. 1.2.
Различают графы ориентированные, неориентированные (реберные) и смешанные. Граф называется ориентированным или кратко орграфом, если связи между его вершинами заданы дугами (рис. 1.3). Путем в орграфе называется конечная последовательность дуг, в которой начало каждой последующей дуги совпадает с концом предыдущей. При отсутствии кратных дуг путь можно записать в виде последовательности вершин, через которые он проходит. Контуром называется путь, начальная вершина которого совпадает с конечной. Длина пути или контура — число дуг, входящих в путь или контур.
Рис. 1.3.
Под смешанным графом понимается такой, в котором вершины соединены как ребрами, так и дугами.
Граф называется связным, если между каждой парой его вершин существует такая последовательность элементов (дуг или ребер или же и дуг, и ребер), что любая пара соседних элементов в этой последовательности имеет общую вершину. Связный неориентированный граф называется деревом, если он не имеет циклов. В дереве любые две вершины связаны единственной цепью.
Из предыдущего изложения ясно, что возможны различные способы задания графа.
В случаях обработки информации на компьютере, граф удобно задавать в виде матрицы смежности или матрицы инциденций.
Матрицей смежности вершин орграфа называется квадратная матрица А, каждый ij-й элемент которой численно равен количеству дуг, идущих из Еi вершины в Еj
. Если мы имеем неориентированный граф, то ему соответствует симметрическая матрица смежности, так как дуги (Еi, Еj ) и (Еj, Еi
) существуют одновременно. Для орграфа соответствующая ему матрица смежности может не являться симметрической.
Матрица смежности вершин графа, изображенного на рис. 1.1, представлена в табл. 1.1.
Таблица 1.1
Матрица смежности для графа, изображенного на рисунке 1.1.
| | | | | |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
Введем теперь понятие матрицы смежности дуг (ребер) графа. Для простоты предположим, что граф не имеет петель и кратных ребер. Матрицей смежности дуг (ребер) орграфа (графа) называется квадратная матрица А, каждый ij-й элемент которой равен единице, если конечная вершина дуги еi, является начальной вершиной дуги еj (если ребра имеют общую вершину), и нулю во всех остальных случаях.
В табл. 1.2 приведена матрица ребер графа, представленного в левой части рис. 1.3.
Таблица 1.2
| | | | | | | | | |
| 1 | 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | |||
| 1 | 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | |||
| 1 | 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 |
Матрицей инциденций орграфа называют прямоугольную матрицу, строки которой соответствуют вершинам, столбцы – дугам, а элементы равны 1, -1 или 0. При этом на пересечении вершин Е и е ставится 1, если Е начальная вершина дуги е. Если же Е – конечная вершина, то данный элемент матрицы будет равен –1. Если Е и е не связаны между собой (т.е. не инцидентны), то на пересечении соответствующих строки и столбца будет стоять 0.
Кроме матричного способа задания графов, который не всегда приемлем и удобен, применяются и другие. Остановимся на рассмотрении спискового способа, наиболее часто применяемого для задания орграфов и так называемых сетевых графиков, рассмотрение которых начнем в следующем параграфе.
Обозначим через Г множество вершин, соединяемых с вершиной дугами, исходящими из . Орграф, изображенный на рис. 3.3, представим списковым способом: Г ={, , }, Г={, , }, Г= {, ,}, Г={}, Г=Æ.
Поскольку множество дуг {} и отображение Г взаимно определяют друг друга, то орграф можно записать в виде G =(, ) или G=(, Г). Реберные графы можно представить аналогичным образом.
Если конечная вершина дуги является начальной вершиной дуги ,то будем говорить, что дуга непосредственно предшествует дуге , или дуга , опирается на дугу . В табл. 1.3 представлен список дуг орграфа.
Таблица 1.3
Дуга графа | Опирается на дуги |
1 | 2 |
| |
| - |
| - |
| - |
| |
| |
| |
| |
| |
Во второй графе таблицы записаны дуги, на которые опираются соответствующие дуги, на которые опираются соответствующие дуги, указанные в первой графе. Такую таблицу будем называть структурной.
Теперь остановимся на разбиении элементов орграфа по рангам.
Вершина называется вершиной 1-го ранга, если в нее не входит ни одна дуга. Вершина называется вершиной 2-го ранга, если в нее входит одна или несколько дуг из вершин 1-го ранга и не входит ни одна другая дуга из вершин выше 1-го ранга. Вершина называется вершиной -го ранга, если в нее входят дуги из вершин не выше -го ранга и при этом имеется хотя бы одна дуга, исходящая из вершин -го ранга. Дуга называется дугой -го ранга, если она опирается на дугу (дуги) не выше -го ранга.
После разбиения элементов орграфа по рангам им придается новая, часто более удобная нумерация:
· все номера элементов некоторого будут меньше номеров элементов следующего ранга;
· номера элементов 1-го ранга будут наименьшими, а номера элементов последнего ранга – наибольшими;
· порядок номеров элементов внутри одного и того же ранга безразличен (так как вершины, принадлежащие одному рангу, не соединены между собой дугами, а дуги друг на друга не опираются).
Процедура ранжирования элементов графа – необходимое условие упрощения алгоритмических расчетов.
Сетевой график и правила его построения
Одним из математических методов современной теории управления большими системами, широко применяемым на практике, является метод сетевого планирования и управления (СПУ). Методы СПУ были разработаны сравнительно недавно. Так как они разрабатывались в разных странах, возникло несколько их разновидностей: СПУ—в СССР, РЕRТ и СРМ—в США и др.
Метод РЕRТ применяется в планировании научно-исследовательских и опытно-конструкторских разработок, для которых характерна неопределенность в оценке затрат времени, необходимого для выполнения отдельных операций (работ). Метод СРМ применяется тогда, когда оценки времени операций детерминированные.
Основой метода СПУ является сетевой график (сетевая модель), отражающий(ая) логическую взаимосвязь и взаимообусловленность входящих в него элементарных операций (работ).
Сетевые графики, рассматриваемые в данной главе с математической точки зрения, представляют собой орграфы без контуров, дугам или вершинам которых приписаны некоторые числовые значения.
В системах СПУ используются следующие, наиболее распространенные способы построения сетевых графиков:
1) сетевые графики в терминах «дуги-операции». В таких графиках вершины, называемые событиями, соответствуют моментам времени начала или окончания одной или нескольких операций, а дуги — операциям;
2) сетевые графики в терминах «дуги-связи», в которых операции изображаются вершинами сети, а дуги показывают порядок выполнения (взаимосвязь) отдельных операций.
Каждый из способов построения сетевых графиков имеет как преимущества, так и недостатки. Учитывая, однако, что первый способ получил большее практическое применение в нашей стране, в дальнейшем сетевые графики будем рассматривать в терминах «дуги-операции».
В сетевом графике различают три вида событий: исходное, завершающее и промежуточное. Исходное — это такое событие, с которого начинается выполнение комплекса операций. Завершающее соответствует достижению конечной цели, т. е. завершению комплекса операций. Сетевые графики с несколькими завершающими событиями называются многоцелевыми. К промежуточным относятся все прочие события.
События обозначаются кружками или другими геометрическими фигурами. Предполагается, что события не имеют продолжительности и наступают как бы мгновенно.
Моментом свершения события считается момент окончания выполнения всех входящих в это событие операций.
Рис. 1.4.
Рис. 1.5.
Пока не выполнены все входящие в событие операции, не может свершиться само событие, а следовательно, не может быть начата ни одна из непосредственно следующих за ним операций. Различают три вида операций:
1) действительная операция процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, выполнение монтажных работ и т. д.);
2) операция-ожидание процесс, требующий только затрат времени (затвердение бетона, естественная сушка штукатурки перед началом малярных работ, рост растений и т. д.);
3) фиктивная операция, или логическая зависимость, отражает технологическую или ресурсную зависимость в выполнении некоторых операций.
При построении сетевых графиков необходимо соблюдать определенные правила:
1) в сети не должно быть событий (кроме исходного), в которые не входит ни одна дуга;
2) не должно быть событий (кроме завершающего), из которых не выходит ни одной дуги;
3) сеть не должна содержать контуров;
4) любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если изобразить одновременно (параллельно) выполняемые три различные операции b
, с, а с общими начальным и конечным событиями (рис. 1.4), то возникает путаница из-за того, что различные операции имеют одно и то же обозначение (2,5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (рис.1.5);
5) если какие-либо операции могут быть начаты до полного окончания непосредственно предшествующей им операции, то последнюю целесообразно представить как ряд последовательно выполняемых операций, завершающихся определенными событиями. Например, если операции с и d могут быть начаты до полного окончания операции b
, то операцию b
рекомендуется разбить на элементарные операции b
1
,
b
2 и b
з и представить выполнение всех операций в виде графика, изображенного на рис. 1.6.
Для отражения технологической или ресурсной зависимости в выполнении операций применяют фиктивные операции.
Рис. 1.6. Рис.1.7.
Предположим, что операция с может выполняться после завершения операций а и b
, а операция d
— только после завершения операции b
. Эта зависимость представлена на рис. 1.7, из которого видно, что операция с следует за операцией а и фиктивной операцией (2,3). В свою очередь операция (2,3) следует за операцией b
. Тогда в силу транзитивности выполнение операции b предшествует выполнению операции с.
Построение сетевого графика начинается с составления списка операций (работ), подлежащих выполнению (см. табл. 1.4). Последовательность операций в списке произвольная. Порядок нумерации операций осуществляется в соответствии с последовательностью их записи в списке. Перечень операций тщательно продумывается и в зависимости от конкретных условий с определенной степенью детализируется. Операции, включенные в список, характеризуются определенной продолжительностью, которая устанавливается на основе действующих нормативов или по аналогии с ранее выполнявшимися операциями. Такие временные оценки называются детерминированными. Если же нормативные данные временных оценок операций отсутствуют, то определяются вероятностные оценки.
После составления списка операций приступают к процедуре построения сети.
Пример. Необходимо построить укрупненный сетевой график выполнения комплекса операций по реконструкции цеха. Список операций представлен в табл. 1.4. Сетевой график комплекса операций изображен на рис. 1.8.
Решение. Операции графика, за исключением операций (2,3) и (5,6), являются действительными. Числа в скобках, приписанные дугам, означают продолжительность выполнения соответствующих операций. Операции а1 и а2 не опираются ни на какие операции, следовательно, поэтому на графике изобразим их дугами, выходящими из события (1), означающего начало выполнения комплекса операций. Операции а3, а5 и а6 опираются на операцию а1, поэтому на графике эти дуги непосредственно следуют за дугой а1. Событие (2) означает момент окончания операции а1 и начала операций, представленных дугами, выходящими из этого события. Операция а4, опирается на операции а1 и а2. Графически это условие отражено посредством последовательного изображения операций (1,3) и (3,4) и введения фиктивной операции (2,3). Событие (3) инцидентно операциям (1,3) и (2,3), следовательно, моментом свершения события (3} будет такой момент, к которому будут выполнены все входящие в это событие операции и может быть начата операция, отраженная дугой, выходящей из него. Аналогично с учетом технологии выполнения изображены на графике остальные операции. Завершающее событие (9) означает момент окончания выполнения всего комплекса операций по реконструкции цеха. Шифры операций (см. табл. 1.4) состоят из номеров начального и конечного событий и практически в список заносятся после составления графика.
Таблица 1.4
Список операций для построения сетевого графика
Опера-ция | Шифр операции | Наименование операции | Опирается на операции | Продолжитель-ность, дни |
| (1,2) | Подготовительные работы | - | 5 |
| (1,3) | Демонтаж старого оборудования | - | 3 |
| (2,6) | Ремонтные строительно-монтажные работы | | 30 |
| (3,4) | Подготовка фундамента под новое оборудование | , | 16 |
| (2,4) | Подготовка к монтажу нового оборудования | | 10 |
| (2,5) | Электротехнические работы | | 12 |
| (4,5) | Монтаж нового оборудования | , | 8 |
| (5,7) | Подключение оборудования к электросети | , | 2 |
| (7,8) | Наладка и технологические испытания оборудования | | 6 |
| (6,8) | Отделочные работы | , , | 8 |
| (8,9) | Приемка цеха в эксплуатацию | , | 1 |
События и дуги построенного сетевого графика (см. рис. 1.8) имеют упорядоченную по рангам нумерацию. Практически же в исходном сетевом графике элементы, как правило, имеют неупорядоченную нумерацию. Поэтому после построения графика рекомендуется перенумеровать его элементы, используя методы, рассмотренные в предыдущем параграфе.
Построение сетевых графиков скоротечных комплексов операций, когда из-за недостатка времени нет возможности производить оптимизационные расчеты, осуществляется с учетом технологических и ресурсных ограничений. Построение графиков нескоротечных комплексов операций, когда достаточно времени для их исследования, выполняется лишь с учетом технологических ограничений. Такой подход обеспечивает минимальную продолжительность выполнения комплекса операций. После построения графика рассчитываются его временные параметры и производится оптимизация по ресурсам или другим показателям, для чего используются формальные методы оптимизации.
Рис. 1.8.
Для разного уровня руководства составляются графики различной степени детализации. Так на рис. 1.8 изображен укрупненный сетевой график реконструкции цеха. Для конкретных исполнителей составляются частные сетевые графики с большей степенью детализации.
Расчеты на детерминированных сетях
Для управления ходом выполнения комплекса операций, представленного сетевой моделью, оперирующая сторона должна располагать количественными параметрами элементов сети. К таким параметрам относятся: продолжительность выполнения всего комплекса операций, сроки выполнения отдельных операций и их резервы времени. Важнейшим параметром сетевого графика является также критический путь. Различают следующие виды путей: полный, предшествующий событию, следующий за событием.
Путь сетевого графика называется полным, если его начальная вершина совпадает с исходным событием, а конечная - с завершающим.
Предшествующий событию путь — это путь от исходного события до данного.
Следующий за событием путь есть путь от данного события до завершающего.
Критическим называется полный путь, имеющий наибольшую продолжительность во времени, Операции и события, принадлежащие критическому пути, называются соответственно критическими операциями и критическими событиями. Суммарная продолжительность операций, принадлежащих критическому пути, равна критическому времени выполнения комплекса операций в целом. На графике критический путь, как правило, выделяется жирной линией.
Расчет параметров сетевого графика может осуществляться различными методами. Рассмотрим один из них.
Предположим, что продолжительности выполнения операций известны и приписаны у соответствующих дуг графика (рис. 1.9).
Определим, прежде всего, ожидаемые (ранние) сроки свершения событий сетевого графика. Исходное событие означает момент начала выполнения комплекса операций, следовательно, . Событие (2) свершится, очевидно, спустя 2 ед. времени после свершения события (1),так как время выполнения операции (1, 2) равно 2.
Следовательно, . Событию (3) предшествуют два пути: и . Продолжительность первого пути равна 1 ед. времени, а второго 2 ед. времени, так как . Продолжительность второго пути можно найти добавлением к ожидаемому сроку свершения события (2) времени выполнения операции (2.3), т.е.. Поскольку событие (3) может свершиться не раньше момента окончания всех входящих в него операций, то .
Рис. 1.9.
В событие (4) входят две дуги, исходящие из событий (1) и (3), -для которых ожидаемые сроки свершения найдены. Следовательно, ожидаемый срок свершения события (4)
. Аналогично находятся ожидаемые сроки свершения событий (5), (6) и (7). Значения , приписаны соответствующим событиям на рис. 1.9.
Общую формулу для нахождения ожидаемых сроков свершения событий можно записать так:
;
для - подмножества дуг сети, входящих в событие (j
).
Ожидаемый срок свершения события (7) совпадает с критическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь теперь от завершающего события к исходному, выделим операции, принадлежащие критическому пути. Из трех операций, входящих в событие (7), определила операция (5,7), выполнение которой начинается после свершения события (5) и продолжается 3 ед. времени . Момент свершения события (5) определила операция (3, 5), так как. В свою очередь момент свершения события (3) определила операция (2, 3), а события (2) — операция (1, 2). Эти операции на графике рис. 1.9 выделены жирной линией. Таким образом, критический путь . Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению времени выполнения комплекса операций. Увеличение же времени выполнения или задержка с выполнением некритических операций может не отразиться на сроке свершения завершающего события. Например, время выполнения операции (4, 5) может быть увеличено или начало ее выполнения может быть отсрочено на 1 ед. времени, и это не отразится на сроке свершения события (5), а, следовательно, и всего комплекса операций.
Начало выполнения операции (4, 7) может быть отсрочено на 3 ед. времени. Отсюда следует, что для события (4), не лежащего на критическом пути, существует предельный (поздний) срок свершения. Обозначим предельный срок свершения любого события сетевого графика через . Примем, что ожидаемый и предельный сроки свершения завершающего события (п) совпадают , тогда предельный срок свершения любого события сетевого графика равен минимальной разности между предельными сроками окончания операций, исходящих из данного события, и временем выполнения соответствующих операций. Нахождение предельного срока осуществляется по формуле
;
,
для - подмножества дуг сети, исходящих из события .
В нашем примере . Определим этот показатель для оставшихся событий. Из события (5) исходит одна операция, следовательно, . Аналогично . Из события (4) исходят три операции, поэтому . Аналогично находим, что (на рис. 1.9 предельные сроки свершения событий указаны в скобках). Для критических событий эти сроки совпадают с ожидаемыми.
Некритические события имеют резервы времени, которые показывают, на какой предельно допустимый срок может задержаться свершение событий без изменения срока свершения завершающего события. Резерв времени события (i
) равен разности между предельным и ожидаемым сроком его свершения:
.
Ожидаемые и предельные сроки свершения событий находятся в диалектическом единстве со сроками начала и окончания операций:
ранний срок начала выполнения операции (i, j
) равен ожидаемому сроку свершения (i
)-ro события ;
поздний срок окончания операции совпадает с поздним сроком свершения ее конечного события ;
поздний срок начала выполнения операции равен разности между предельным сроком свершения ее конечного события и продолжительностью ;
ранний срок окончания операции равен сумме ожидаемого срока свершения ее начального события и продолжительности .
Сроки выполнения операций находятся в границах, определяемых параметрами: . Следовательно, операции, как и события, могут иметь некоторый резерв времени. Различают четыре разновидности резервов времени операций: полный, свободный, частный первого вида и частный второго вида.
Полный резерв времени операции показывает, насколько можно сдвинуть начало выполнения операции или увеличить ее продолжительность, не изменяя ожидаемого срока свершения начального события, при условии, что конечное для данной операции событие свершится не позднее своего предельного срока. Величина полного резерва времени вычисляется по формуле:
.
Свободный резерв времени операции показывает, насколько можно увеличить продолжительность или отсрочить начало выполнения операции (i
,
j
) при условии, что начальное и конечное ее события свершаются в ожидаемое время:
.
Частный резерв времени первого вида — это запас времени, которым можно располагать при выполнении операции (i
,
j
) в предположении, что начальное и конечное ее события свершаются в предельные сроки;
.
Частный резерв времени второго вида - это запас времени, которым можно располагать при выполнении операции (i
,
j
) в предположении, что ее начальное событие свершится в предельное, а конечное — в ожидаемое время. Для некоторых операций интервал времени между предельным сроком свершения начального события и ожидаемым сроком свершения конечного события может быть меньше их продолжительности. В этом случае,- принимается равным нулю. Определяется частный резерв времени второго вида по формуле:
.
Найдем резервы времени операции (4, 6) сетевого графика (см. рис. 1.9):
;
;
;
.
Расчеты на вероятностных сетях
Сетевые графики комплекса операций могут иметь детерминированную или стохастическую структуру. Если все операции комплекса и их взаимосвязи точно определены, то такая структура графика называется детерминированной. Стохастическая структура означает, что все операции включаются в сеть с некоторой вероятностью. Например, в научно-исследовательских и опытно-конструкторских разработках заранее не известны не только продолжительности отдельных операций, но и их перечень, а также структура сети.
Расчет параметров и анализ сетей случайной структуры связан с известными трудностями. Поэтому на практике обычно применяются детерминированные сети со случайными временными оценками операций. Такие сети называются вероятностными. При исследовании вероятностных сетей могут встретиться два случая:
1) операции не являются новыми, и мы приближенно знаем для каждой из них функцию распределения продолжительности выполнения;
2) операции являются новыми, малоизученными, и для них функции распределения продолжительностей неизвестны.
В первом случае по известной функции распределения нетрудно определить среднее значение продолжительности выполнения каждой операции (математическое ожидание) и дисперсию. Во втором случае применяется метод усреднения. Исходными данными для метода усреднения являются вероятностные оценки продолжительности каждой операции:
а - минимальная продолжительность (оптимистическая оценка) операции;
в - максимальная продолжительность;
т - вероятная продолжительность (мода) операции.
Эти оценки времени задаются ответственным исполнителем или группой экспертов.
Рис. 1.10
Исследования, проведенные в нашей стране и за рубежом, позволили обосновать возможность использования бета-распределения в качестве типового распределения продолжительности операций с оценками а, b
и т.
Функция плотности бета-распределения (рис. 1,10) аналитически представима в виде
где р, q - параметры распределения, зависящие от вида операций, а с - нормирующий множитель, определяемый из условия
=1.
По известной функции распределения f(t) находятся числовые характеристики операций:
среднее значение (математическое ожидание) продолжительности операции
;
дисперсия
’
Статистический анализ, проведенный эмпирико-экспериментальным путем разработчиками математического аппарата системы PERT, позволил установить, что . Следовательно,
; (1.1)
. (1.2)
После определения математических ожиданий продолжительностей операций по формуле (1.1) проводится расчет временных параметров сети, как и в детерминированном случае. Длительность критического пути рассматривают как математическое ожидание случайной величины tкр:
.
Дисперсию продолжительности пути считают равной сумме дисперсий продолжительностей операций, находящихся на критическом пути:
.
Расчет временных параметров сети по средним значениям продолжительностей операций не позволяет строго определить срок завершения комплекса операций. Отклонение случайных величин от их средних значений может быть как в большую, так и в меньшую сторону. Поэтому фактическая продолжительность выполнения комплекса операций tф может быть больше или меньше tкр. В связи с этим представляет большой интерес оценка вероятности завершения комплекса операций к определенному сроку, которая зависит от дисперсии продолжительности критического пути. При одних значениях величин может быть один критический путь, при других - другой. Однако если продолжительности работ отклоняются от своих средних значений на такую малую величину, что критический путь не изменяется, и если на критическом пути лежит значительное число операций (20 или более), то на основании центральной предельной теоремы можно приближенно считать, что его продолжительность подчиняется нормальному закону распределения с параметрами и . Тогда вычисление вероятности того, что фактическая продолжительность выполнения комплекса операций tф меньше планового директивного срока Тпл, производится по формуле:
, (1.3)
где - функция Лапласа, значения которой берутся из таблиц (Приложение 1):
,
а - среднеквадратическое отклонение.
По формуле (1.3) можно вычислить вероятность выполнения любой операции в заданный срок.
Рассмотрим подход к определению математического ожидания и дисперсии операций (ij) сетевого проекта на основе двух оценок: оптимистической а и пессимистической b
. Многочисленные эмпирико-экспериментальные исследования двухоценочной методики показали, что в бета-распределении величины p и q, определенные для большого количества сетевых моделей, близки к постоянным значениям p=1, q=2. Выбрав их в качестве стандартных показателей степени, получим функцию, которая относится к классу бета-распределений и имеет следующие параметры:
математическое ожидание
; (1.4)
дисперсию
(1.5)
Применение двух временных оценок существенно уменьшает объем информации, который требуется от ответственного исполнителя, так как он освобождается от задания наиболее вероятной оценки.
Пример. Найти критическое время tкр выполнения комплекса операций, представленного на рис. 1.11, используя средние оценки продолжительности и дисперсию, а также определить:
1) вероятность выполнения комплекса операций за
а) Тпл =35 дней;
б) Тпл =42 дня,
2) время, за которое комплекс операций будет выполнен с вероятностью, не меньшей
а) Р=0.75;
б) Р=0.35,
3) вероятность завершения операции (2. 5) в 8-й день.
Оптимистическая оценка и пессимистическая оценка для каждой операции заданы в табл. 1.6. Случайные отклонения времени выполнения операций от математических ожиданий не меняют критического пути.
Рис. 1.11.
Решение
По формулам (3.4), (3.5) вычислим и и занесем в две правые графы табл. 1.5.
Осуществив расчет продолжительности критического пути по средним оценкам времени (приписаны дугам графика), получим дней. Такой же расчет по оптимистическим оценкам приводит к величине дня, по пессимистическим - дня. Практически же комплекс операций может быть выполнен с некоторой вероятностью в любой срок из интервала [27,5...53,75].
Критический путь включает 6 операций, поэтому при определении доверительного интервала для продолжительности проекта по нормальному закону распределения ошибка окажется значительной. Заметим, что практически все руководства по методам СПУ этот факт игнорируют, вводя в заблуждение и читателя, и лиц, в интересах которых проводится расчет.
Таблица 1.5
Исходные параметры | Расчетные параметры | |||
(i,j) | | | | |
(1,2) | 1 | 3,5 | 2 | 0,25 |
(2,3) | 2 | 4,5 | 3 | 0,25 |
(2,4) | 2,5 | 6,25 | 4 | 0,56 |
(2,5) | 4 | 6,5 | 5 | 0,25 |
(3,7) | 1,5 | 2,75 | 2 | 0,063 |
(4,6) | 5 | 10 | 7 | 1 |
(5,8) | 5,4 | 8,25 | 6 | 0,56 |
(6,7) | 3 | 5,5 | 4 | 0,25 |
(7,8) | 8 | 10,5 | 9 | 0,25 |
(8,9) | 8 | 18 | 12 | 4 |
Используя функцию Лапласа, получим
и вероятность завершить проект за 38 дней:
.
Аналогично определяется вероятность выполнения комплекса операций за Тпл = 42 дня:
.
Определим теперь время, за которое комплекс операций будет выполнен с вероятностью, не меньшей чем Р = 0,75.
Величине Ф(u) = P – 0,5 = 0,25 соответствует значение u = 0,86.
Следовательно,
дней.
Для Р = 0,35 имеем Ф(u) = 0,35 – 0,5 = -0,15 и . Таким образом,
дней.
Ожидаемый срок свершения 5-го события t5 = 7. Сумма дисперсий операций, принадлежащих пути (1 – 2 – 5), ведущему к 5-му событию,
.
Таким образом,
.
Следовательно, при расчетах с использованием нормального закона с вероятностью 0,921 операция (2, 5) будет завершена в плановый срок.
Обзор методов линейного программирования
Большое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются задачами линейного программирования. Этот термин появился в конце 30-х годов, когда программирование на компьютере еще не было развито, и соответствует не очень удачному переводу с английского. Под линейным программированием понимается линейное планирование, т.е. получение оптимального плана—решения в задачах с линейной структурой. В данной книге встречаются также термины «нелинейное программирование» и «динамическое программирование», которые аналогичным образом подразумевают получение оптимального решения задач с соответствующей структурой.
Составление плана (программы) фирмы, цеха, завода, отрасли промышленности является одной из важнейших задач в менеджменте. Решение таких задач осложняется тем, что приходится находить значения не двух и не трех переменных величин — число переменных может быть от нескольких десятков до нескольких сотен и даже тысяч.
Рассмотрим простейшую задачу составления производственного плана.
Задача. Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий при определенных возможностях четырех видов машин. План выпуска этих изделий надо составить так, чтобы от реализации изготовленной продукции завод получил наибольшую прибыль. Оба вида изделий последовательно обрабатываются этими машинами. В плане должно быть предусмотрено, что первая машина ежедневно может обрабатывать эту продукцию лишь в течение 8 ч, вторая— 12ч, третья — 12ч, четвертая — 9 ч.
В табл. 1.6 указано время, необходимое для обработки каждого изделия этих двух видов (в часах). Нуль означает, что изделие машинами данного вида обрабатывать не надо.
Таблица 1.6
Изделия | Станок | |||
1-й | 2-й | 3-й | 4-Й | |
I | 1 | 0.5 | 1 | 0 |
II | 1 | 1 | 0 | 1 |
Возможное время работы машины (в часах) | 18 | 12 | 12 | 9 |
Завод от реализации одного изделия I вида получает 4 руб., а от реализации одного изделия II вида—6 руб. прибыли.
Построим математическую модель этой задачи. Пусть — число изделий I вида, — число изделий II вида. Так как машины каждого вида (1, 2, 3, 4) могут обрабатывать продукцию не более (18, 12, 12, 9) часов соответственно, то получаем следующую систему ограничений:
(1.6)
Общая прибыль может быть выражена как
(1.7)
где х1 и х2 удовлетворяют условиям задачи (1.6).
Таким образом, построенная математическая модель данной задачи состоит из системы неравенств (1.6), на множестве решений которой надо найти наибольшее значение целевой функции (1.7).
В общем виде задача линейного программирования ставится следующим образом.
Максимизировать (минимизировать) функцию
(1.8)
при ограничениях
(1.9)-(1.11)
Функция (1.8) — линейная, ограничения (1.9) — (1.11) — линейные. Задача содержит п переменных и т ограничений.
Решить задачу линейного программирования это значит найти значения управляющих переменных, удовлетворяющих ограничениям, и при которых целевая функция принимает минимальное или максимальное значение.
В зависимости от вида целевой функции и ограничений можно выделить несколько типов задач линейного программирования или линейных моделей: общая линейная задача, транспортная задача, задача о назначениях.
Если число переменных в задаче линейного программирования (ЗЛП) равно двум, а ограничениями является система неравенств, то задачу можно решать графическим методом, который хорошо известен вам из бакалаврской подготовки, и сводится к следующей последовательности действий.
1) Записывают уравнения прямых, соответствующих ограничениям, и строят их на плоскости.
2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости ХОУ и подставляют ее координаты в левую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств, отражающих ограничения задачи. Определяют область допустимых решений задачи, как область пересечения т полуплоскостей, соответствующих т ограничениям.
3) Определяют направление возрастания (убывания) целевой функции. Это можно сделать двумя способами. Можно построить вектор—нормаль, который показывает направление возрастания функции. В противоположном ему направлении функция убывает. Можно просто построить две линии уровня для целевой функции, приравняв ее двум произвольным константам, и по их расположению определить направление возрастания (убывания) целевой функции.
4) Определяют граничную точку (точки) области допустимых решений, в которых целевая функция принимает максимальное или минимальное значение.
5) Вычисляют значения найденной точки, решая совместно уравнения, задающие прямые, на пересечении которых находится эта точка, или выявляя уравнение прямой на границе области допустимых решений, с которой совпадает линия уровня целевой функции.
Наиболее распространенный метод решения задач линейного программирования — это симплекс-метод.
В случае двух переменных область допустимых решений, как правило, представляет собой замкнутый многоугольник на плоскости. Для n переменных областью допустимых решений является многомерный многогранник, называемый симплексом. Оптимальное решение, как правило, это вершина (граничная точка) такого многогранника. Симплекс-метод заключается в последовательном целенаправленном обходе вершин симплекса. В каждой следующей граничной точке симплекса значение целевой функции, в общем случае, улучшается.
Для применения симплекс-метода задачу следует записать в канонической форме:
(1.12)
В канонической форме записи все переменные неотрицательны, ограничениями являются уравнения, и требуется найти такие назначения переменных, при которых целевая функция имеет максимум.
Переход к канонической форме записи производится с помощью следующих простых действий.
1) Если требуется найти минимум f, то, заменяя f на –f
, переходят к задаче максимизации, так как min
f
=
max
(-
f
).
2) Если ограничение содержит неравенство со знаком <, то от него переходят к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную.
3) Если ограничение содержит неравенство со знаком >, то от него переходят к равенству, вычитая из левой части дополнительную неотрицательную переменную.
4) Если в задаче какая-либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух других неотрицательных переменных. Например, для произвольной переменной , полагают где .
Суть симплекс-метода состоит в направленном переборе решений системы (1.12). Каждое следующее решение улучшает значение целевой функции. Симплекс-метод включает два этапа:
· определение начального решения, удовлетворяющего ограничениям;
· последовательное улучшение начального решения и получение оптимального решения задачи.
Любое решение задачи линейного программирования называется опорным планом задачи.
Система (1.12) содержит т линейно независимых уравнений, их число меньше числа, неизвестных, входящих в систему, следовательно, ее можно разрешить относительно т неизвестных, например , выразив их через остальные неизвестные:
(Коэффициенты в полученной системе, естественно, отличны от коэффициентов системы (1.12), но для простоты обозначены той же буквой).
После указанных преобразований задача приводится к каноническому виду и осуществляется направленный перебор переменных путем перевода свободных в базисные.
Ввод переменной в список базисных переменных означает, что ей приписывается отличное от 0 положительное значение, т.е. ее значение увеличивается. Максимальное значение коэффициента при х1 в формуле для f соответствует максимальному по абсолютной величине отрицательному элементу в последней строке симплекс-таблицы, следовательно, понятен выбор новой базисной переменной.
Для определения переменной, выводимой из списка базисных переменных, надо в соответствии с алгоритмом симплекс-метода найти отношения элементов столбца свободных членов к элементам разрешающего столбца и среди них выбрать минимальное.
Рассмотрим теперь задачу линейного программирования следующего вида:
(1.13)
В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком £, все переменные хj неотрицательны; задача содержит n
управляющих переменных и т ограничений. Коэффициенты при переменных в целевой функции: c1,
c
2, ...,
cn; свободные члены: b
1,
b2.....
bm
.
Двойственная задача линейного программирования имеет вид
(1.14)
В двойственной задаче требуется найти минимум целевой функции, ограничения — неравенства со знаком ³, управляющие переменные y1,
y2...,
ym. неотрицательны. Задача содержит m управляющих переменных и n ограничений. Коэффициенты целевой функции такой задачи b1.b2,...,bm являются свободными членами исходной ЗЛП, а свободные члены двойственной задачи c1,
c
2, ...,
cn
— коэффициентами целевой функции исходной ЗЛП. Матрица коэффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы — строками.
Задачи (1.13) и (1.14) называются парой взаимно двойственных задач линейного программирования. Для двойственных задач верна следующая теорема.
Теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение х*, то другая также имеет оптимальное решение у*. При этом соответствующие им оптимальные значения целевых функций равны. Поясним экономический смысл двойственной модели.
Пусть в качестве управляющих переменных исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами - количество ресурсов -го типа, используемых для изготовления изделий. Через обозначено количество ресурсов -го типа, идущее на изготовление одного изделия -го вида, (- прибыль от реализации одного изделия -го вида). Тогда исходная модель, соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.
Предложим, что предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через , цены на единицу ресурсов его -го вида, . Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается целевой функцией в задаче (1.14), второе условие - ее ограничениями. В левой части каждого из неравенств стоит прибыль от продажи ресурсов всех типов, идущих на изготовление -го изделия, в правой части - прибыль от продажи -го изделия, . Таким образом, двойственная задача (1.14) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов. Значения переменных часто называют «теневыми» ценами.
Построение двойственной задачи позволяет глубже разобраться в поставленной экономической проблеме.
Характеристика методов нелинейного программирования
В общем виде задача нелинейного программирования (ЗНЛП) формулируется следующим образом:
. (1.15)
(1.16)
где - управляющие переменные или решения ЗНП, ;
- фиксированные параметры, ;
- заданные функции от переменных.
Еслиилинейны, то ЗНЛП переходит в задачу линейного программирования.
Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных , которые удовлетворяют системе ограничений (1.16) и доставляют максимум или минимум функции .
Для задачи нелинейного программирования, в отличие от линейных задач, нет единого метода решения. В зависимости от вида целевой функции (1.15) и ограничений (1.16) разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод.
Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономических проблем сводится к линейным моделям, поэтому в данном пособии нелинейные модели и методы расчета рассмотрены достаточно кратко.
Рассмотрим задачу нелинейного программирования, содержащую две переменные.
. (1.17)
(1.18)
Система ограничений (1.18) определяет в -мерном пространстве некоторую область, которая является областью допустимых решений задачи.
Решить ЗНЛП графически - это значит найти точку области допустимых решений (1.18), через которую проходит линия наивысшего (наинизшего) уровня.
Указанная точка может находиться как на границе, так и внутри области допустимых решений, в отличие от задач линейного программирования.
Так же, как и для линейных задач, ЗНЛП удобно решать графически, когда функция и ограничения содержат две переменные. Алгоритм в этом случае состоит в следующем.
Шаг 1. На плоскости строят область допустимых решений, определенную ограничениями (1.18). Если она пуста, т.е. ограничения несовместны, то задача не имеет решения. В противном случае переходят к шагу 2.
Шаг
2
. Строят линию уровня функции , где С - некоторая константа. Переход к шагу 3.
Шаг
3
. Определяют направление возрастания (при максимизации) или убывания (при минимизации) функции .
Шаг 4. Находят точку области допустимых решений, через которую проходит линия уровня с наибольшим (при максимизации) или наименьшим (при минимизации) значением С, либо устанавливают неограниченность функции на области допустимых решений.
Шаг 5. Определяются значения , для точки, найденной на шаге 4, и величину функции в этой точке.
В задачах большей размерности для определения условного экстремума могут быть использованы методы дифференциального исчисления, если имеет не ниже второй производной. Тогда процесс решения ЗНЛП состоит в определении внутри допустимого множества всех стационарных точек функции , удовлетворяющих условию , проверке всех стационарных точек на максимум и сравнении этих значений с максимальными значениями, которых достигает целевая функция на границах допустимого множества.
Этот вывод следует из теоремы об экстремальных значениях Вейерштрасса-Больцано.
Теорема 1. Если - непрерывная функция, определенная на замкнутом и ограниченном множестве , то она достигает на этом множестве, по крайней мере, один раз максимального и минимального значения (теорема существования экстремума).
Следующая теорема определяет возможные местоположения экстремума.
Теорема 2. Если является функцией нескольких переменных, определенной на допустимой области , то максимальное значение , если оно существует, достигается в одной или нескольких точках, которые принадлежат одному из следующих множеств:
· - множество стационарных точек;
· - множество точек границы;
· - множество точек, где не дифференцируема.
Иначе говоря, глобальный максимум (минимум) ищут среди локальных.
Определение 1. Функция достигает относительного (локального) максимума в точках , если для всех точек лежащих в малой окрестности точки , имеет место неравенство:
.
Определение 2. Функция достигает абсолютного (глобального) максимума в точках , если для всех точек справедливо неравенство
.
Остановимся на возможности глобального экстремума в стационарных точках.
Для нахождения стационарных точек можно использовать теорему 3.
Теорема 3. Пусть - дифференцируема в некоторой области . Если в некоторой внутренней точке области функция имеет относительный максимум, то
. (1.19)
Для того чтобы определить, действительно ли являются найденные стационарные точки точками максимума или минимума (или не тем и не другим), необходимо исследовать в окрестности стационарных точек и определить, является она выпуклой или вогнутой.
Определение 3. Пусть - выпуклое множество точек -мерного пространства. Функция , определенная на , называется вогнутой (выпуклой вверх), если для любой пары точек и произвольного выполняется неравенство (рис. 1.12):
. (1.20)
Если
, (1.21)
то функция называется выпуклой (рис. 1.13).
Если (1.20) и (1.21) есть строгие неравенства, то функция называется строго вогнутой или строго выпуклой.
Критерий выпуклости и вогнутости функции переменных может быть сформулирован в виде следующей теоремы.
Рис . 1.12
Рис. 1.13
Теорема 4. Дифференцируемая функция строго вогнута в некоторой окрестности точки , если выполняются следующие условия:
,
т.е. если знаки определителей чередуются, где
. (1.22)
Функция строго выпукла в окрестности точки , если все определители (выписанные выше) положительны. В результате объединения условий теоремы 3 и 4 приходим к следующему утверждению.
Теорема 5. Для того чтобы в точке достигался внутренний относительный максимум, достаточно равенства нулю всех первых частных производных и строгой вогнутости функции в окрестности .
Для того чтобы в точке был относительный минимум, необходимо и достаточно, чтобы все частные производные обращались в 0 в точке , а сама функция в ее окрестности была строго выпукла.
Пример. Пусть . Стационарная точка . Исследуем точку на относительный максимум или минимум:
Так как
,
то функция достигает в точке относительного минимума.
Справедливо следующее утверждение. Если - строго выпуклая (вогнутая) функция на всем множестве , то обладает только одним относительным минимумом (максимумом), который является и абсолютным.
Теорема 6 (о выпуклости допустимого множества решений).
Пусть и - ограничения задачи нелинейного программирования. Если функции - вогнуты, то допустимое множество и является выпуклым.
Теорема 7. Если функции вогнуты (выпуклы) на множестве , то функция также вогнута (выпукла), при условии, что .
Рассмотренные необходимые и достаточные условия экстремума определяют локальный экстремум. Чтобы найти глобальный экстремум, необходимо сравнить значения функции в точках локальных экстремумов и в тех точках, где ее производные не существуют.
В общем случае ЗНЛП являются многоэкстремальными. Поэтому и необходимо изучение области допустимых решений, чтобы выяснить является ли найденный экстремум глобальным.
Установим условие единственного глобального экстремума для задачи
. (1.23)
Для этого рассмотрим функцию одной переменной . Очевидно, что функция достигает экстремуму (минимума) либо внутри допустимой области (при некотором , либо на ее границе (при ). В первом случае и производная в этой точке должна быть равна нулю. Во втором случае и производная должна быть неотрицательная, т.е. , так как в иначе при увеличении (перемещение внутрь допустимой области) можно получить меньшее значение и, следовательно, экстремум будет находиться внутри допустимой области. Таким образом, необходимые условия экстремума для одномерной задачи имеют вид
.
По аналогии можно показать, что для задачи (1.23) минимизации функции переменных необходимые условия экстремума имеют вид
(1.24)
т.е. градиент функции в точке минимума на границе допустимой области должен быть или равен нулю, или направлен внутрь допустимой области.
Для задачи максимизации функции неотрицательных переменных необходимые условия экстремума имеют вид:
(1.25)
В соответствии с вышеизложенными теоремами для выпуклых (вогнутых) функций данные условия являются не только необходимыми, но и достаточными, для глобального экстремума в задачах с отсутствием ограничений на ресурсы.
В нелинейном программировании обычно рассматриваются задачи при наличии ограничений в виде неравенств типа
, (1.26)
т.е. экстремум ищется не на всей полуплоскости, а лишь в определенной ее точке, отвечающей ограничению на ресурсы . В основе методов решения этих задач лежит метод множителей Лагранжа, который позволяет сформулировать необходимые и достаточные условия экстремума для задачи нахождения глобального экстремума.
Объясним идею метода на примере ЗНЛП, содержащей две переменные.
На плоскости уравнение определяет график некоторой функции, представленный на рис. 1.14. На нем показаны несколько линий уровня некоторой функции и выбранное в качестве примера направление ее возрастания.
Рис. 1.14.
В точке А, в которой функция достигает максимального значения, совпадают касательные линии к графикам функций
Следовательно, в точке векторы-нормали к функциям и пропорциональны. Обозначим эти векторы соответственно через и . Получаем
где - некоторый коэффициент пропорциональности. Координатами векторов и как градиентов являются значения частных производных функций и соответственно в точке А
Из условия пропорциональности в точке А имеем
Поскольку не произвольно, а определяется в точке А через , то для определения значений в которых функция достигает максимума, к этим уравнениям надо добавить условие принадлежности точки А графику функции .
Окончательно получаем систему уравнений, которой удовлетворяет оптимальное решение поставленной задачи
Введем новую функцию
Тогда последняя система перепишется в виде
В отличие от задачи для функции поиск экстремума уже идет не в ограниченной области. Следовательно, имеем задачу безусловной оптимизации, которая может быть решена методами дифференциального исчисления.
Функцию F и называют функцией Лагранжа.
Таким образом, алгоритм метода множителей Лагранжа для задачи максимизации (минимизации) функции многих переменных с ограничениями типа равенства сводится к следующему.
Шаг 1. Составляют функцию Лагранжа
Шаг 2. Находят частные производные функции Лагранжа по и приравнивают их к нулю:
(1.27)
Шаг 3. Решают систему (1.27) и определяют точки, в которых функция может иметь экстремум.
Шаг 4. Проверяют полученные на шаге 3 точки на экстремум по ее вогнутости (выпуклости), т.е. изначально выпуклость определяют из вторых производных, а для неотрицательных переменных и без вычисления вторых производных в силу (1.24) и (1.25), и определяют экстремальное значение функции в найденной точке.
Таким образом, в случае ограничений заданных в виде равенств, ЗНЛП может быть решена методом множителей Лагранжа. С учетом неотрицательности переменных и определенных нами условий (1.24), (1.25) может этим же методом быть решена и задача с неравенствами (1.23). Если же какая либо из переменных не ограничена в знаке (т.е. может быть и отрицательной), то необходимые и достаточные условия экстремума в ЗНЛП устанавливаются на основе теорем Куна-Такера и теоремы о седловой точке.
Теорема Куна-Таккера устанавливает необходимые и достаточные условия экстремума для общей задачи нелинейного программирования (НЛП) и формулируется следующим образом: если функции и , дифференцируемы и выпуклы, а допустимое множество содержит внутренние точки, то для оптимальности вектора необходимо и достаточно, чтобы нашелся неотрицательный вектор , который вместе с вектором удовлетворяет системе равенств (1.27) (подразумевается ). Точка в данном случае является седловой точкой функции Лагранжа.
Точка называется седловой точкой функции , если для любых выполняется условие
. (1.28)
Это условие означает, что в седловой точке функция имеет минимум по (левое неравенство) и максимум по (правое неравенство).
Заметим, что условия (1.28) – это необходимые условия минимума функции Лагранжа, записанные по правилу (1.24) для неотрицательных переменных , а условия (6.23) – необходимые условия максимума этой функции, записанные по правилу (6.12) для неотрицательных переменных . Именно поэтому задача НЛП при выполнении условий теоремы Куна-Таккера сводится к задаче отыскания седловой точки функции Лагранжа.
Теорема о седловой точке определяет условия, при которых седловая точка функции Лагранжа определяет оптимальное решение исходной задачи НЛП, и формулируется следующим образом: если , а вектор минимизирует функцию Лагранжа и выполняются условия
, (1.29)
то - седловая точка функции Лагранжа, а - оптимальное решение исходной задачи НЛП.
В отличие от теоремы Куна-Таккера теорема о седловой точке справедлива при любых предположениях, о характере и свойствах целевой функции и функций ограничений, и в силу этого она является не только основной теоремой НЛП, но и основной (фундаментальной) теоремой математического программирования. Она устанавливает достаточные условия экстремума (но не необходимые) для любой задачи математического программирования. Это означает, что в точке экстремума общей задачи НЛП функция Лагранжа может и не иметь седловой точки. Если же функция Лагранжа имеет седловую точку, то эта точка одновременно определяет оптимальное решение исходной задачи.
Градиентные методы оптимизации. Теорема Куна-Таккера, определяя необходимые (в некоторых случаях и достаточные) условия существования оптимального решения, не дает вычислительного алгоритма для отыскания самого решения.
Для этой цели разработан ряд специальных методов, позволяющих, отправляясь от некоторого начального решения, получать последовательно значения, которые находятся все ближе к искомой точке максимума, минимума или седловой точки. Группа методов, основанных на вычислении и сравнении значений функций в ряде точек перед следующим шагом, называется поисковыми методами оптимизации. Среди них особое значение имеют так называемые градиентные методы.
Пусть требуется найти
,
причем на переменные не наложено ограничений. Градиентом функции называется вектор частных производных
(1.30)
Пусть - произвольная начальная точка. Тогда движение представляющей точки описывается следующими уравнением:
, (1.31)
где - величина шага, - состояние до последнего шага. Так как характеризует направление возрастания , то очевидно . В случае, если решается задача минимизации, то движение происходит в направлении антиградиента:
. (1.32)
Можно показать, что для выпуклых функций точка при стремится в область абсолютного экстремума, которая по размерам соизмерима с . Поэтому вместо уравнений (1.31) и (1.32) с постоянным шагом можно перейти к переменному шагу . Выбор может производиться по-разному. В частности можно выбирать из следующего условия:
, (1.33)
т.е. следует двигаться в направлении однажды вычисленного градиента до тех пор, пока не перестанет возрастать. Такую разновидность называют полношаговым градиентным методом (или методом наискорейшего спуска).
Методы случайного поиска применяются в тех случаях, когда нужно найти экстремум функции многих переменных. Методы оказываются предпочтительными по сравнению с градиентным методом, если значения целевой функции измеряются с помехами, и потому точное направление градиента определить невозможно.
Обзор общих методов дискретного программирования
Большинство реальных практических задач (распределения ресурсов, сетевое планирования и управление, календарное планирование, др.) описываются математическими моделями с дискретными состояниями и оказываются задачами дискретного программирования.
Рассмотрим следующую общую задачу максимизации:
найти
(1.34)
при условиях
(1.35)
и (1.36)
где D — некоторое подмножество действительных чисел.
Если множество D является конечным или счетным,то условие (1.36) — это условие дискретности, и данная задача является задачей дискретного программирования. Если вдобавок вводится ограничение хj
— целые числа (j = 1, 2, ..., п), то приходят к задачам целочисленного программирования (ЦП), которое является частным случаем дискретного программирования.
В задачах дискретного программирования область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач недопустимо применение замены дискретной задачи ее непрерывным аналогом с последующим округлением найденного решения до ближайшего целочисленного (кстати, в EXCEL это требование проигнорировано, и Подбором решения пользоваться не рекомендуется).
Методы решения задач дискретного программирования по принципу подхода к проблеме делят на 3 группы: 1) методы отсечения или отсекающих плоскостей; 2) метод ветвей и границ; 3) методы случайного поиска и эвристические методы.
Общая идея всех методов отсечения, независимо от правила формирования дополнительных ограничений, состоит из следующих основных шагов.
1. Находим оптимальное решение задачи линейного программирования без учета условия целочисленности решения. Если полученное решение является целочисленным, то прекращаем вычислительный процесс. В противном случае переходим к п. 2.
2. Вводим дополнительное ограничение, исключающее полученное нецелочисленное решение, и возвращаемся к п. 1.
Практический опыт решения задач целочисленного программирования методом отсечения показал, что этот метод имеет плохую сходимость. Поэтому для повышения эффективности вычислительных алгоритмов были предложены комбинаторные методы (метод ветвей и границ и метод динамического программирования), основанные на упорядоченном переборе наиболее перспективных вариантов.
Идея метода ветвей и границ для решения задач целочисленного программирования достаточно проста и сводится к следующему.
Представляем процесс поиска решения в виде графа типа «дерево». При начале построения дерева первую переменную можно включить или не включить , т.е. из корневой вершины выходят две ветви. Аналогично в каждой из введенных вершин можно поступить со второй переменной (рис. 1.15).Так и образуется дерево возможных вариантов.
Рис. 1.15.
На первом уровне построенного нами дерева . Очевидно, что далее для любого имеем число вершин (т.е. вариантов) .
Значение целевой функции L, вычисленное вдоль ветви, дает границу решения по ней. Очевидно, что, построив дерево полностью и перебрав все 2n
вариантов границ решения, можно определить оптимальный план для данной задачи. Метод ветвей и границ, а также метод динамического программирования и разработаны для исключения полного перебора при расчете границ по всем ветвям.
Основная идея метода динамического программирования заключается в замене одновременного выбора большого количества параметров поочередным их выбором. Поэтому многомерная задача оптимизации сводится к многошаговой задаче меньшей размерности. Основа такой замены – формирование рекуррентного соотношения, получившего название функционального уравнения. В результате решения функционального уравнения получают оптимальную зависимость, по которой обратной прогонкой определяют оптимальный набор переменных задачи.
Контрольные вопросы:
1. Сформулируйте понятие «оптимизации». Приведите примеры сфер деятельности, где можно использовать методы оптимизации.
2. Укажите условия необходимые для постановки задачи оптимизации.
3. Перечислите основные параметры сетевого графика.
4. Как осуществляется моделирование инновационных проектов на сетях?
5. Сформулируйте задачу планирования производства и составьте ее математическую модель.
6. Сформулируйте основную задачу линейного программирования.
7. Что такое целевая функция задачи линейного программирования?
8. Что такое допустимое решение задачи линейного программирования?
9. Что такое оптимальное решение задачи линейного программирования?
10. Как преобразовать к виду основной задачи линейного программирования задачу, в которой ограничения представляют собой неравенства?
11. Может ли задача линейного программирования иметь более одного оптимального решения?
12. Сформулируйте общую задачу нелинейного программирования.
13. Какова геометрическая интерпретация общей задачи нелинейного программирования?
14. Приведите примеры применения задач нелинейного программирования в экономике.
15. В чем состоят необходимые и достаточные условия экстремума функции нескольких переменных?
16. В чем заключается метод Лагранжа поиска условного экстремума?
17. Перечислите методы решения задач целочисленного программирования.
18. В чем состоит сущность метода ветвей и границ?
19. На чем основана основная идея методов динамического программирования?
Упражнения
1. Используя процедуру ранжирования, произвести нумерацию событий в сетевом графике, изображенном на рис. 1.15. Определить продолжительности полных путей, а также путей, предшествующих событиям 5 и 7, и путей, следующих за событиями 2 и 5. Найти критический путь и его продолжительность. Считая продолжительности работ полученными по двухоценочной модели с дисперсией равной 0,3 от ожидаемой продолжительности, определить время, за которое комплекс будет выполнен с вероятностью 0,95.
Рис. 1.15.
2. В сетевом графике, изображенном на рис. 1.16, произвести нумерацию событий на основе процедуры ранжирования и определить ранние и поздние сроки начала и окончания работ. Найти критический путь и его продолжительность. Рассчитать полные резервы времени для некритических работ.
Рис. 1.16.
Считая продолжительности работ средними с дисперсией в 0,2 от ожидаемой продолжительности, определить время, в течение которого проект будет выполнен с вероятностью 0,95
3. Для изготовления различных изделий A и B используется 2 вида сырья. На производство единицы изделия A его требуется затратить: 1-го вида -15кг, 2-го вида - 11кг, 3-го вида - 9кг. На производство единицы изделия B требуется затратить сырья 1-го вида - 4кг, 2-го вида - 5кг, 3-го вида - 10кг.
Производство обеспечено сырьем 1-го вида в количестве 1095кг, 2-го вида - 865кг, 3-го вида -1080кг. Прибыль от реализации единицы готового изделия А составляет 3 рубля, изделия B - 2 рубля.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
Литература для дополнительного изучения
1. Мардас А. Н., Мардас О.А. Краткий курс практического менеджмента. – СПб.: Литера, 2002.
2. Троцкий М. и др. Управление проектами: Пер. с польск. – М.: Финансы и статистика, 2006.
3. Колемаев В. А., Малыхин В. И., Бодров А. П. и др. Математические методы принятия решений в экономике: Учебник. – М.: Финстатинформ, 1999.
4. Карандаев И. С., Малыхин В. И., Соловьев В. И. Прикладная математика: Учебное пособие. – М.: ИНФРА-М, 2001.
5. Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика: Математическое программирование: Учебник. – Минск: Вышэйшая школа, 2001.
6. Кузнецов А. В., Сакович В. А., Холод Н. И. и др. Сборник задач и упражнений по высшей математике: Математическое программирование: Учебное пособие. – Минск: Вышэйшая школа, 2001.
1.2. Специальные задачи сетевого планирования и управления
Оптимизация на сетях с дискретным потреблением ресурсов. Возобновляемые и невозобновляемые ресурсы. Оптимальное распределение ресурсов для последовательно-параллельных графов. Эвристические алгоритмы распределения ресурсов на сетевом графике произвольного вида. Эвристические алгоритмы составления рационального расписания при распределении ограниченных ресурсов.
Понятие о ресурсно-временной оптимизации
Оптимизация комплекса операций по времени, представленного сетевым графиком, сводится к сокращению продолжительности критического пути. Такая задача возникает тогда, когда критическое время выполнения комплекса операций превосходит срок , заданный оперирующей стороной. Естественно предположить, что сокращение времени выполнения комплекса операций требует осуществления определенных мероприятий или вложения каких-то средств.
В некоторых случаях сокращение может быть достигнуто за счет перепланировки сетевого проекта (изменения топологии сети). Так, например, одновременно выполняемые операции, не лежащие на критическом пути с большими резервами времени, целесообразно выполнять последовательно, если такое выполнение допускается технологией. Освободившиеся при этом ресурсы можно использовать на критических операциях, что приведет к ускорению их выполнения. Сокращение времени выполнения операций возможно также за счет автоматизации и механизации производственных процессов, улучшения организации работ, применения передовой технологии и других мероприятий.
Задачи оптимизации комплекса операций по времени решаются с привлечением дополнительных средств и с использованием внутренних резервов.
При оптимизации с использованием дополнительных средств возможны две постановки задачи.
1. Задан сетевой график выполнения комплекса операций. Время выполнения каждой операции равно . Известно, что вложение дополнительных средств в операцию сокращает время выполнения с до . Следует, однако, иметь в виду, что насыщение критических операций ресурсами не беспредельно. Для каждой операции существует минимально возможное время ее выполнения, равное . Требуется определить время начала , и окончания выполнения операций, а также сколько дополнительных средств вложить в каждую из операций , чтобы: общее время выполнения комплекса операций было минимальным; сумма вложенных дополнительных средств не превышала заданной величины ; время выполнения каждой операции было не меньше минимально возможного времени .
Математически условия задачи можно записать следующим образом:
; (1.37)
; (1.38)
для всех ; (1.39)
для всех ; (1.40)
для всех ; (1.41)
для всех . (1.42)
Добавив при необходимости фиктивную операцию, выходящую из последнего события, целевую функцию любого графика можно записать в виде выражения (1.27).
Ограничения-равенства (1.40) показывают зависимость продолжительности выполнения операций от вложенных средств. Ограничения (1.41) обеспечивают выполнение условий предшествования операций в соответствии с топологией сети (время начала выполнения каждой операции должно быть не меньше времени окончания непосредственно предшествующей ей операции).
Критический путь в данной задаче является функцией от объемов дополнительно вкладываемых средств .
Сформулированная задача относится к классу задач математического программирования и может быть решена методами линейного или нелинейного программирования в соответствии с видом функций .
2. Постановка второй задачи отличается от предыдущей тем, что в ней введено ограничение на общее время выполнения комплекса операций.
Продолжительность комплекса не должна превышать величину (директивное время). Задача предполагает определение значений неизвестных величин (объемы дополнительно вкладываемых средств в операции ) таким образом, чтобы:
суммарное количество дополнительно привлекаемых средств было минимальным, т. е.
;
время завершения комплекса операций было не выше заданного срока , а время выполнения каждой операции - не меньше минимально возможного времени , что выражается соотношениями:
;
для всех .
(Здесь предполагается, что зависимость продолжительности выполнения операций от вложенных средств выражается соотношениями для всех );
время окончания любой операции сетевого графика было не больше времени начала непосредственно следующей за ней операции , т.е. для любых смежных операций сети и должно выполняться условие
;
наконец, соблюдалось условие неотрицательности переменных
для всех .
Рассмотрим теперь оптимизацию в случае использования внутренних резервов.
В этом случае комплекс операций задан сетевым графиком. Известно время выполнения каждой операции . В распоряжении оперирующей стороны имеются подвижные средства в количествеед., которые распределены между операциями. Для выполнения каждой операции выделено ед. подвижных средств. Средства , снятые с операции , увеличивают продолжительность выполнения операции с до , а средства , вложенные в операцию, уменьшают продолжительность ее выполнения до величины .
Некритические операции имеют резервы времени, поэтому, перебрасывая средства с некритических операций на критические, можно уменьшить продолжительность выполнения комплекса операций.
Требуется так перераспределить подвижные средства между операциями, чтобы продолжительность выполнения комплекса операций была минимальной.
Обозначим количество средств, перебрасываемых на операцию , через (если с операции снимаются средства, то значениеотрицательно).
Новые продолжительности будут равны:
для операций, с которых снимаются средства,
;
для операций, на которые перебрасываются средства
.
Суммарное количество средств, снятых с каких-либо операций и добавленных другим операциям, должно быть равно нулю, т. е.
.
Количество подвижных средств, снимаемых с операций , не должно превышать соответствующих величин
. (1.43)
Целевая функция, отражающая общую продолжительность выполнения комплекса операций, имеет вид
.
Ограничения (1.43) записываются для всех операций сетевого графика, так как в результате расчетов критические операции могут перейти в некритические и наоборот. По той же причине в целевую функцию включены две суммы. В первую сумму включаются операции, с которых снимаются средства, во вторую - операции, на которые перебрасываются средства, если те и другие входят в критический путь.
Методы решения таких задач определяются видом функции .
Постановки задач оптимального распределения ресурсов
на сетях
В рамках нашего курса под ресурсами будем понимать любые ресурсы организации - от персонала до производственных площадей. Вместе с тем, при всей общности подхода будем учитывать, что существуют две принципиально разные группы ресурсов в силу разницы их использования при выполнении работ:
· складируемые (или невозобновляемые) ресурсы, то есть те, которые полностью используются при выполнении определенной работы (горючее, электричество и т.д.).
· нескладируемые (или возобновляемые) ресурсы, то есть те, которые в процессе выполнения работ не расходуются, не изменяют свою натуральную форму, но производят некоторый расходуемый фактор (человеко-день, тонно-км и т.д.). Чаще всего это исполнители (люди или механизмы, которые могут быть перемещены на другую работу). Их часто называют ресурсами типа «мощность», в то время как складируемые ресурсы это ресурсы типа «материалы».
Расход ресурсов типа «материалы» можно описать функцией «время-стоимость»:
.
Как правило, это функция убывающая (рис. 1.17):
Рис. 1.17.
Здесь:
- минимальная продолжительность работы;
- максимальная продолжительность работы.
В предшествующем параграфе мы предполагали, данная функция линейна и, естественно, при оптимизации комплекса работ, описываемого сетевым графиком, приходили к задаче линейного программирования. На самом деле такое предположение - это чистая утопия. В общем случае функция, связывающая продолжительность работы и потребляемый на ней складируемый ресурс дискретна и нелинейна, что на рис. 1.17 отражено точечной линией.
При оптимизации расхода нескладируемых ресурсов в качестве связи со временем выполнения работы вводят мощность потребления ресурса , т.е. количество единиц ресурса, используемых в единицу времени для выполнения работы .
Таким образом, можно сформулировать две постановки задачи:
1. Заданы ограничения на потребляемые ресурсы. Требуется распределить ресурсы по работам сетевого графика таким образом, чтобы минимизировать критическое время . Такие задачи обычно относятся к нескладируемым ресурсам.
2. Задан - директивный срок выполнения комплекса работ. Необходимо минимизировать ресурсы, которые потребны для выполнения этого комплекса. Такие задачи обычно относят к складируемым ресурсам.
Переходя к рассмотрению методов ресурсно-временной оптимизации в задачах с произвольной функцией «время-стоимость» отметим, что сетевой график сам в силу топологии приводит к нелинейности потребления ресурсов во времени. Связь между временем выполнения работы и затратами ресурсов (стоимостью) также нелинейна. Следовательно, всегда имеем нелинейную задачу оптимизации. А общего метода решения таких задач не существует. В большинстве случаев используются эвристические (построенные на догадках) методы, не гарантирующие оптимальность решения. Вместе с тем, для определенного круга задач точное решение может быть найдено, в частности методами динамического программирования.
Ресурсно-временная оптимизация на сетях
с невозобновляемыми ресурсами
Поскольку о принципах формализации ресурсно-временной оптимизации нескладируемых ресурсов на сетях в предположении линейности функции «время-стоимость» мы уже говорили ранее, то будем рассматривать эвристические алгоритмы для функций произвольного вида.
Сформулируем постановку задачи математически.
Задан комплекс работ в виде сетевого графа , где - сетевой граф.
Для каждой работы заданы стоимость (связь между продолжительностью и затратами невозобновляемых ресурсов) , допустимая продолжительность ее выполнения и директивный срок выполнения всего комплекса, т.е. предполагается, что в итоге критическое время проекта приводится к величине .
Требуется распределить ресурсы между работами так, чтобы минимизировать затраты при выполнении комплекса работ (инновационного проекта) в директивные сроки, т.е. найти
при условии
.
Предположим, что комплекс работ может быть представлен как чисто последовательный граф (рис. 1.18):
Рис. 1.18.
Для определенности зададим продолжительность () и расход ресурсов на каждой операции (табл. 1.7).
Таблица 1.7
Данные о продолжительности и расходе ресурсов на операциях комплекса
Время | Ресурсы | Время | Ресурсы | Время | Ресурсы | Время | Ресурсы | Вариант выполнения |
| | | | | | | | |
2 | 4 | 48 | 20 | 60 | 40 | 16 | 10 | 1 |
| | 32 | 40 | 40 | 50 | 8 | 20 | 2 |
| | 24 | 60 | | | | | 3 |
Для оптимального распределения ресурсов воспользуемся табличным методом решения задач динамического программирования.
Первоначально рассматриваем варианты выполнения сочетания работ (0-1) и (1-2). Поскольку вторая операция может выполняться по трем вариантам, то возможны и три варианта выполнения пути (0-1-2) (табл. 1.8). Продолжительность и расход ресурсов по каждому варианту отражен во внутренних клетках таблицы. Первая строка чисел в этой таблице образуется как сумма продолжительностей работ (0-1) и (1-2) по определенному варианту выполнения. Вторая строка – сумма потребляемых ресурсов. Стрелки символизируют рассматриваемую динамическую последовательность, т.е. возможные варианты времени выполнения пути (0-1-2) при различных затратах ресурсов.
Таблица 1.8
| 48 20 | 32 40 | 24 60 |
2 4 | 50 24 | 34 44 | 26 64 |
Присоединяем к этой последовательности следующую операцию (2-3). В этот раз на очередном шаге также возможны три последовательности (табл. 1.9).
Таблица 1.9
| 50 24 | 34 44 | 26 64 |
60 40 | 110 64 | 94 84 | 86 84 |
40 50 | 90 74 | 74 94 | 66 114 |
Присоединив к вариантам последовательности (0-1-2-3) работу (3-4), получим все возможные варианты выполнения комплекса, строящиеся на основании принципа оптимальности Беллмана (табл. 1.10).
Таблица 1.10
| 110 64 | 90 74 | 74 94 | 66 114 |
16 10 | 126 74 | 106 84 | 90 104 | 82 124 |
8 20 | 118 84 | 98 94 | 82 114 | 74 134 |
Оптимальную динамическую последовательность, а значит и оптимальное распределение ресурсов при минимизации времени выполнения проекта, получаем, строя ее по принципу «минимальное время за те же ресурсы». Такая последовательность в табл. 1.10 выделена жирно и представлена стрелками. Она показывает (выделено цветом), что работу (3-4) следует выполнять, используя 20 единиц ресурсов и с продолжительностью 8 единиц времени. Предшествующий же путь необходимо выполнить за 66 ед. времени, затратив 114 ед. ресурсов. Данным величинам соответствует продолжительность работы (2-3) в 40 ед. времени с затратами 50 ед. ресурсов и предшествующий путь (0-1-2)с продолжительностью 26 и затратами 64 ед. (табл. 1.9).
Продолжая действовать по той же схеме, на основании последовательности, отраженной в табл. 1.8, приходим к заключению, что операцию (1-2) следует выполнять по третьему варианту, т.е. за 24 ед. времени с расходом 60 ед. и, естественно, операцию (0-1) за 2 ед. времени с расходом 4.
Окончательно имеем распределение ресурсов на проект, выделенное цветом в табл. 1.7, и приводящее к реализации проекта за 74 ед. времени с общим расходом невозобновляемых ресурсов в 134 единицы.
Таким образом, метод динамического программирования позволяет точно решить задачу ресурсно-временной оптимизации на последовательном графе.
Этот же метод работает и для чисто «параллельного» графа (рис. 1.19).
Рис. 1.19.
Действительно, по данным о последовательных операциях (0-1), (1-3) и (0-2), (2-3) можно провести вначале «сшивку», подобную той, которая отражена на рис. 1.20. Затем для образовавшегося чисто параллельного графа распределяют ресурсы методом динамического программирования в минимаксной задаче (табл. 1.11).
Рис. 1.20
Таблица 1.11
| 8 10 | 7 15 | 6 20 | 5 30 | 4 40 | 3 70 |
8 5 | 80 15 | 7 20 | 6 25 | 6 35 | 6 45 | 6 75 |
5 10 | 8 20 | 7 25 | 6 35 | 5 40 | 5 50 | 5 80 |
4 20 | | | 6 40 | 5 50 | 4 60 | 4 90 |
3 40 | | | | 5 70 | 4 80 | 3 110 |
Поскольку задача минимаксная, то в последовательность включается вариант, имеющий максимальную продолжительность из параллельных операций, но с потреблением суммы ресурсов на этих операциях. Так в нашем случае имеем:
I путь: =5; =30. II путь: = 5; = 10.
Последовательность завершается в клетке со временем проекта равным (не превышающим) .
Этот метод может быть обобщен на более сложные сетевые графики (рис. 1.21). Свертка в этом случае проводится по отдельным кускам графа, сводимым в одну дугу. К примеру, вначале свертывают операции (1-3) и (1-4) последовательно, а затем пути (1-3-4) и (1-4) параллельно. Далее сшиваем пути (1-4-5) и (1-2-5), и т.д. Однако наличие в графике на рис. 4.5 работы (3-6) не позволит свернуть путь (1-3-4). Аналогично, нельзя осуществить оптимизацию подобным образом для сетевого графика, представленного на рис. 1.22. Поэтому рассмотренный подход (метод динамического программирования) применим только для чисто последовательно-параллельных графов. В определенных случаях для взаимозаменяемых ресурсов решение может быть получено методом ветвей и границ.
Рис. 1.21
Для общего же случая (когда топология графа сложна и ресурсы не взаимозаменяемы) метода нахождения оптимального решения задачи пока не создано. Тогда прибегают к эвристическим методам, которые позволяют получить рациональное (приближенное) решение.
Рис. 1.22.
Эвристические алгоритмы распределения
ресурсов на сетевом графике произвольного вида
Задача минимизации расхода ресурсов при заданном директивном сроке выполнения проекта. Допустим мы уверены в том, что каждая работа комплекса выполнима во временном интервале . Тогда, если на все работы направить максимально возможные ресурсы, иначе говоря, обеспечить , то продолжительность критического пути будет минимальной из возможных (), а расход ресурсов - максимальным (). Если же , то, соответственно, и .
Отметим, что если по первому варианту закрепления ресурсов (при ), рассчитанное критическое время проекта превышает директивное (), то задача минимизации расхода при наличных ресурсах не имеет решения. Если же , то закрепление минимально возможных ресурсов за каждой из работ приводит и к оптимальному решению. Однако возможно условие . Тогда для каждой из работ необходимо определить величину из допустимого промежутка , обеспечивающую минимальность потребления ресурсов всем проектом.
Решение нашей задачи в этом случае отыскивается по следующему эвристическому алгоритму:
1. Примем и найдем первый возможный критический путь с продолжительностью . Если , то распределение ресурсов, обеспечивающее , приводит к оптимальному решению, причем . Если же нет, то осуществляем переход ко второму шагу алгоритма.
2. Для работ произвести оптимальное распределение ресурсов как для последовательного сетевого графика, ориентируясь на условие .
3. На основании полученной динамической последовательности определить продолжительности операций для и исключить из множества критических работ операции с .
4. Положить для и для . Рассчитать (определить) и . Проверить условие . Если оно выполняется, то план распределения ресурсов, полученный на данном шаге, оптимален. В противном случае перейти к п.2.
Задание.
Примените данный алгоритм к численному примеру (рис. 1.23, табл. 1.12).
Рис. 1.23.
Таблица 1.12
| | | | | | | | | |
18 | 32 | 16 | 5 | 8 | 16 | 17 | 6 | 19 | 66 |
12 | 48 | 10 | 16 | 6 | 24 | 14 | 24 | 8 | 74 |
10 | 56 | 8 | 20 | 5 | 32 | 11 | 42 | 6 | 80 |
6 | 72 | | | | | | | | |
Требуется определить минимальную стоимость проекта C при условии =28.
Задача минимизации времени выполнения проекта при заданном количестве ресурсов. Рассмотрим теперь задачу минимизации времени выполнения комплекса работ при заданном количестве ресурсов типа «мощность».
Пусть, к примеру, комплекс работ задан следующим сетевым графиком (рис. 1.24)
Рис. 1.24.
Не принимая в расчет потребление ресурсов (указано в скобках над каждой из операций графика), произведем расчет временных параметров: ранних и поздних сроков наступления событий (левый и правый секторы соответственно в кружке-событии на рис. 1.24). Получим критическое время проекта .
Построим далее таблицу (табл. 1.13) для отражения количества ресурсов (исполнителей), задействованных в каждом временном интервале (в определенный день). В ней символ означает суммарное количество потребных ресурсов на данном временном интервале. В нашем случае выполнение проекта за 9 дней возможно, если мы располагаем 7 исполнителями.
Предположим, однако, что количество исполнителей ограничено и равно С=5. Требуется определить порядок выполнения комплекса, при котором критическое время проекта минимально ().
Таблица 1.13
Код операции | Время | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
0-1 | 4 | 4 | | | | | | | | |
0-2 | 2 | 2 | 2 | 2 | | | | | | |
1-2 | | | 3 | 3 | 3 | | | | | |
1-3 | | | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
2-3 | | | | | | 3 | | | | |
| 6 | 6 | 7 | 7 | 5 | 5 | 2 | 2 | 2 | |
Отыскание точного решения подобного рода задач достаточно сложно, несмотря на неявное предположение о взаимозаменяемости ресурсов. Оптимальный алгоритм решения может быть разработан на основе метода ветвей и границ, который не исключает полного перебора возможных вариантов расписания. Поэтому мы рассмотрим чаще применяемые на практике эвристические алгоритмы, основанные на правилах предпочтения.
Для минимизации времени реализации проекта при ограничении на нескладируемые ресурсы наиболее часто используют следующие два правила предпочтения при выборе работы для включения в расписание:
1-ое правило. При назначении планового срока выполнения работы предпочтение отдается той операции, у которой минимален поздний срок свершения завершающего события .
Возможно применение данного правила и в отношении максимального раннего срока свершения начального события i выбираемой операции.
Физически правило означает, что в первую очередь планируются те работы, за которыми в сетевом графике следуют наиболее длинные последующие пути.
2-ое правило. При включении в расписание предпочтение отдается той работе, которая предполагает большее потребление ресурсов, т.е. с , где означает общие затраты (затраты в единицу времени).
Физический смысл данного правила предпочтения заключается в том, что вначале планируют наиболее крупные работы, требующие наибольшего числа исполнителей, чтобы оставшихся исполнителей направить на мелкие работы (принцип чемодана).
1-ое правило предпочтения требует предварительного расчета параметров сетевого графика ( или ).
2-ое правило более просто в применении, поскольку не предполагает расчета сетевого графика.
Вернемся к примеру, заданному рис. 1.24, и рассмотрим порядок применения 2-ого правила предпочтения (табл. 1.14).
Таблица 1.14
Код операции | Время | |||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
0-1 | 4 | 4 | | | | | | | | | | |
0-2 | | | 2 | 2 | 2 | 2 | | | | | | |
1-2 | | | 3 | 3 | 3 | | | | | | | |
1-3 | | | | | | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
2-3 | | | | | | | 3 | | | | | |
| 4 | 4 | 5 | 5 | 5 | 4 | 5 | 2 | 2 | 2 | 2 | 2 |
Построение данной таблицы осуществлено следующим образом.
В начальном (нулевом) событии графика возможно одновременное начало операций (0-1) и (0-2). В первый день тогда потребовалось бы 6 исполнителей. Но мы ограничены величиной С=5, поэтому, используя второе правило предпочтения, включаем в расписание только работу (0-1), как потребляющую большее количество ресурсов. Это вынуждает начало работы (0-2) сдвигать в третий временной интервал. Однако в третий день освободятся исполнители («мощности»), которые были до этого задействованы на операции (0-1). Поэтому на очередном шаге включаем в расписание работу (1-2), как требующую больших ресурсов и присоединяем к ней еще не выполнявшуюся операцию (0-2), поскольку располагаем достаточным количеством (2 единицы) свободных исполнителей. Суммарное потребление ресурсов в третий, четвертый и пятый дни будет составлять 5 единиц (нижняя строка табл. 1.14).
В шестом временном интервале три исполнителя высвобождаются. Максимальное потребление ресурсов на еще не выполнявшихся операциях равно 3 (работа 2-3). Однако включить ее в расписание сейчас нельзя, поскольку событие 2 еще не наступило. Поэтому в шестой временной интервал планируем начало операции (1-3), требующей две единицы ресурсов и продолжающейся до 12-го дня включительно.
Поскольку в седьмой день освободятся исполнители с работы (0-2), то на него можно спланировать операцию (2-3).
Таким образом, при заданном ограничении на ресурсы весь комплекс, отражаемый сетевым графиком на рис. 1.24, может быть выполнен за 12 единиц времени.
Мы не можем утверждать, что это оптимальное расписание, поскольку воспользовались приближенным методом решения. Эвристические методы можно только в определенной степени оценить (для сравнения вычислительной эффективности) по нижней границе решения, в качестве которой естественно принять максимальную из величин возможного времени исполнения операций проекта наличными «мощностями» без учета топологии сети
и критической продолжительности проекта при отсутствии ограничений на ресурсы.
Применив этот подход к нашему примеру, получим
,
Следовательно,
,
и относительная погрешность результата расчетов по данному алгоритму (которую можно сравнивать с аналогичной по другим алгоритмам), составит величину
,
где через T обозначена величина, получаемая при построении расписания ( в нашем примере T
=12).
Контрольные вопросы:
1. Перечислите основные постановки задач ресурсно-временной оптимизации на сетях.
2. Как осуществляется оптимизация в случае нелинейности функции «время-стоимость»?
3. Как осуществить оптимизацию затрат на инновационный проект?
Упражнение
Для выполнения комплекса операций по ремонту оборудования, представленного сетевым графиком (рис. 1.25), в первые три дня выделено 7 ед., в четвертый и пятый день – 6 ед., а в последующее время – 8 ед. ресурсов. Каждой дуге графика приписаны два числа: первое – временная оценка в днях; второе – количество потребляемых ресурсов при выполнении операции.
7(2)
Рис. 1.25.
Необходимо определить сроки выполнения операций таким образом, чтобы завершить весь комплекс за минимальное время. Операции не допускают перерыва в выполнении.
Литература для дополнительного изучения
1. Мардас А. Н., Мардас О.А. Краткий курс практического менеджмента. – СПб.: Литера, 2002.
2. Вентцель Е.С. Введение в исследование операций. – М.: «Советское радио», 1964.
1.3.
Специальные транспортные задачи и алгоритмы
Критерии оптимальности в транспортных задачах. Минимаксная транспортная задача. Транспортная задача с приоритетами. Динамические транспортные задачи. Динамические транспортные задачи с запаздыванием. Порядок решения специальных задач на компьютере.
Простые модификации транспортной задачи
Транспортная задача находит широкое применение при решении задач материально-технического обеспечения, распределении ресурсов, организации ремонта техники и т.п.
Мы помним, что транспортная задача в классической постановке формулируется следующим образом.
Требуется минимизировать
при ограничениях
где
с
ij — стоимость перевозки единицы груза из i-того пункта отправления до j-того пункта назначения;
x
ij
- количество груза, перевезенного из i
-того пункта отправления в j
-тый пункт назначения;
a
ij
—запасы груза на i-том пункте отправления;
b
ij
—потребности в грузе на j
-том пункте назначения.
Ограничения транспортной задачи означают, что количество груза, вывозимого из i
-го пункта отправления, равно запасам груза в этом пункте и количество груза, ввозимого в j
-ый пункт назначения, равно потребностям в грузе для данного пункта назначения. Из последнего условия следует, что общие запасы и потребности в грузе равны.
Показателем эффективности плана перевозок в классической задаче является стоимость, поэтому сформулированную задачу называют транспортной задачей по критерию стоимости. Однако величина сij
может иметь не только стоимостный смысл. Например, это может быть расстояние, время, расход топлива и т. п.
Классическая транспортная задача (ТЗ) является задачей линейного программирования и может быть решена симплексным методом. Однако основная особенность этой задачи — равенство единице коэффициентов в уравнениях-ограничениях позволила разработать специальные методы ее решения, более эффективные, чем симплексный метод.
В работе Л. В. Канторовича «Математические методы организации и планирования производства», вышедшей в
При решении транспортной задачи на ЭВМ наиболее эффективен венгерский метод, разработанный в конце 50-х годов прошлого века.
Идейно все методы решения транспортной задачи можно разделить на две группы.
В методах первой группы ищется допустимое (опорное) решение, которое удовлетворяет условиям-ограничениям и с помощью последовательности итерации улучшается допустимое решение. В методах второй группы ищется оптимальное решение, для которого могут не удовлетворяться условия-ограничения и последовательно сокращаются невязки ограничений до получения допустимого оптимального плана. Поэтому методы первой группы обычно называют методами последовательного улучшения плана, методы второй группы — методами последовательного сокращения невязок ограничений.
Простейшим способом определения опорного плана является так называемый способ «северо-западного угла».
Сущность его поясним на конкретном примере. Допустим, что требуется определить опорный план для ТЗ, исходные данные для которой приведены в табл. 1.15. Будем заполнять ее перевозками постепенно, начиная с левой верхней клетки («северо-западного» угла таблицы). Первой заполняется клетка A
1 –
B
1. Спрос пункта назначения В1 составляет 30 единиц, запасы пункта отправления а1—40 единиц. Следовательно, спрос В1 можно полностью удовлетворить за счет запасов А1. Следующая клетка A
1 –
B
2. Спрос пункта назначения В2 — 100 единиц, оставшиеся запасы пункта отправления А1—10 единиц. Назначаем перевозку A
1 –
B
2 — 10 единиц. Так как запасы пункта отправления А1 полностью исчерпаны, то переходим к пункту отправления А2. Рассмотрим клетку A
2 –
B
2. Неудовлетворенный спрос В2, составляет 90 единиц, запасы А2—80 единиц. Назначаем перевозку A
2 –
B
2 80 единиц. Запасы пункта отправления А2, полностью исчерпаны, переходим к распределению запасов пункта отправления A
3.
Таблица 1.15
ПН ПО | | | | |
| 10 | 1 | 3 | 40 |
| 6 | 2 | 5 | 80 |
| 12 | 5 | 14 | 60 |
| 30 | 100 | 50 | 80 |
Пункту назначения В2, требуется еще 10 единиц; пункту назначения В3 — 50 единиц. Запасы пункта отправления A
3 составляют 60 единиц. Назначаем перевозку A
3 –
B
2,—10 единиц, A
3 –
B
3— 50 единиц. Полученное распределение перевозок приведено в табл. 1.16. Таким образом, способ «северо-западного угла» весьма прост, но полученный с его помощью план может существенно отличаться от оптимального плана.
Таблица 1.16
ПН ПО | | | | |
| 10 30 | 1 10 | 3 | 40 |
| 6 | 2 80 | 5 | 80 |
| 12 | 5 10 | 14 50 | 60 |
| 30 | 100 | 50 | 80 |
Лучшие результаты дает способ наименьшего элемента в матрице. Сущность этого способа рассмотрим на этом же примере. В табл. 1.15 выбираем клетку с минимальным элементом. Такой клеткой является A
1–
B
2. Потребности пункта назначения В2 составляют 100 единиц, запасы пункта отправления А1 —40 единиц. Назначаем перевозку А1—В2 в 40 единиц. Так как запасы пункта отправления А1 полностью исчерпаны, то первую строку исключаем из дальнейшего рассмотрения. Определяем следующую клетку A
2 –
B
2 с минимальным элементом. Неудовлетворенные запасы пункта назначения В2 - 60 единиц, запасы пункта отправления А2 — 80 единиц, назначаем перевозку A
2–
B
2 — 60 единиц. Аналогичным образом назначаем все остальные перевозки, указанные в табл. 1.17.
Таблица 1.17
ПН ПО | | | | |
| 10 | 1 40 | 3 | 40 |
| 6 | 2 60 | 5 20 | 80 |
| 12 30 | 5 | 14 30 | 60 |
| 30 | 100 | 50 | 80 |
Еще более точное приближение опорного плана к оптимальному дает способ Фогеля (способ предложен американским ученым У. Фогелем).
Процесс решения начинается с определения разностей между двумя наименьшими элементами каждой строки и каждого столбца (табл. 1.18). Обозначим эти разности и соответственно. Например, в строке А1 минимальный элемент равен 1, следующий за ним по величине элемент—3, разность между ними оказывается равной 2. Эта и другие разности по строкам и столбцам выписаны в табл. 1.18. Затем из всех разностей строк и столбцов выбираем наибольшую. В нашем примере это разность =7 в строке A
3. Определяем клетку с минимальным элементом в этой строке A
3 –
B
2 и в эту клетку записываем поставки A
3 –
B
2 60 единиц. Запасы пункта отправления A
3 исчерпаны. Исключаем строку A
3 из рассмотрения и определяем новые разности. В нашем примере разности не изменились, но в общем случае они могут и пересчитываться. Определяем следующую максимальную разность 4, которой соответствует минимальный элемент в клетке A
2 –
B
1, равный 6. Назначаем перевозки A
1–
B
2 и аналогичным образом продолжаем вычислительную процедуру до назначения всех перевозок. Результаты назначения приведены в табл. 1.18.
Таблица 1.18
ПН ПО | | | | | |
| 10 | 1 | 3 40 | 40 | 2 |
| 6 30 | 2 40 | 5 10 | 80 | 3 |
| 12 | 5 60 | 14 | 60 | 7 |
| 30 | 100 | 50 | 80 | |
| 4 | 1 | 2 | | |
Сравним опорные планы, полученные рассмотренными способами.
Опорный план, полученный способом «северо-западного угла», дает следующую стоимость перевозок:
L
1=10*30+1*10+2*80+5*10+14*50= 1220.
Опорному плану, полученному способом наименьшего элемента (см. табл.3.3), соответствует
L
2=1 • 40+2 • 60+5 • 20+ 12 • 30+ 14 • 30= 1040.
Наиболее точные результаты дает опорный план, полученный способом Фогеля (см. табл.3.4):
L
3=5*60+6*30+2*40+5*10+3*40=730.
Однако каждый из этих способов не гарантирует, что полученный опорный план является оптимальным. Для уточнения опорного плана и разработаны метод потенциалов и венгерский метод, с которыми вы знакомились в ходе бакалаврской подготовки.
Транспортная задача по критерию времени (минимаксная ТЗ). Во многих практических задачах эффективность перевозок определяется не их стоимостью, а временем Т, в течение которого все перевозки будут завершены. Тогда наилучшим планом перевозок будет считаться тот план, при котором время окончания всех перевозок минимально.
Обозначим через t
ij время, необходимое на перевозку груза из пункта отправления Аi
, в пункт назначения Вj
. Предполагается, что время t
ij не зависит от количества перевозимого груза хij
. Тогда математически транспортная задача по критерию времени может быть сформулирована следующим образом.
Требуется определить план перевозок, при котором
(1.44)
при ограничениях
, (1.45)
, (1.46)
Задача (1.44) — (1.46) не является задачей линейного программирования. Однако, последовательно решая эту задачу по критерию стоимости (t
ij играет роль стоимости перевозок) и запрещая после каждого решения элементы матрицы стоимости, для которых
tij tij
*
=
max
tij для хij
>0,
можно получить решение задачи (1.44)— (1.46).
Запрещение маршрута (ij) производится заменой данного элемента матрицы tij на достаточно большое число М. Если на следующей итерации окажется, что стоимость перевозок превышает М, то план, полученный на предыдущей итерации, является оптимальным.
Рассмотрим пример. Пусть задана матрица
Значения запасов а и потребностей b указаны около соответствующих строк и столбцов. Решив задачу по критерию стоимости, получим план
Максимальное значение времени для ненулевых перевозок t11 =10. Подставляя t11 =М, получим
,
Вновь решив задачу по критерию стоимости для данной матрицы, получим новый план
,
которому соответствует максимальное время перевозки t21=7. Заменяя все значения tij
> 7 на М, получим новую матрицу
.
Так как все элементы первого столбца равны М, то полученная при решении такой задачи по критерию стоимости целевая функция L
>М. Следовательно, оптимальному решению задачи по критерию времени соответствует план, полученный на предыдущем шаге и Т=7.
Необходимо заметить, что при решении задач по критерию стоимости на первых итерациях могут быть использованы приближенные способы определения допустимого плана. Последняя итерация, которая приводит к L
>М, должна быть выполнена методом потенциалов или венгерским методом, так как эти методы обеспечивают точное решение задачи.
Транспортная задача с приоритетами возникает, если при обеспечении удовлетворения потребителей (поставщиков) необходимо обеспечить обслуживание в определенной очередности. Мы рассмотрим суть данной задачи в рамках динамической транспортной задачи.
Динамические транспортные задачи. Моделирование запаздывания в инновационных процессах
В динамических транспортных задачах (ДТЗ) рассматриваются ситуации, когда и производство и потребление продукции происходит не единовременно, а в течение ряда последовательных периодов. Возможность несовпадения периодов производства и потребления приводит к неприменимости стандартных транспортных алгоритмов, поэтому динамические транспортные задачи редко применялись в реальном планировании, в том числе и по причине невозможности учесть запаздывание в поставках.
Покажем возможность адекватного планирования в рамках ДТЗ.
Рассмотрим производственно-экономическую систему, содержащую множество (=1,...,r) пунктов производства продукции и множество (=l,...,s
) ее потребления. На горизонте планирования [0,T] за интервал (l
=1,…,p)в будет создан запас продукции , поставка которого возможна в момент . Соответственно в к концу интервала потребность составит (k
=1,…,p), возместить которую необходимо в момент времени . Для обеспечения этой потребности из в поставляется единиц продукции, произведенной к моменту . В силу различных причин тогда возможно запаздывание в удовлетворении потребностей, представляющее собой величину
, (1.47)
где - время, затрачиваемое на поставку продукции из в .
Таким образом, можно сформулировать следующую содержательную постановку ДТЗ с запаздыванием: построением плана производственно-экономических связей в системе поставщики-потребители инновационной продукции обеспечить минимальное суммарное запаздывание в удовлетворении всех потребностей (а значит и минимальную упущенную выгоду участников производственно-сбытового процесса) на горизонте [0,T].
Соотношение (1.47) позволяет свести ДТЗ к стандартной (статической) транспортной задаче (ТЗ). Для этого свернем пары индексов, т.е. положим
, (1.48)
. (1.49)
Теперь индекс i
принимает целые значения от 1 до m, где m=rp, а индекс j
– все целые значения от 1 до .
Обозначив , , , и отобразив элементы в множество , содержащее m
пунктов отправления с запасом , (аналогично в множество , содержащее n
пунктов назначения с потребностями ), получаем стандартную ТЗ следующего содержания.
Построить план такой, чтобы
(1.50)
при ограничениях
, (1.51)
, (1.52)
Построенная задача (1.50) – (1.52) представляет собой уже обычную транспортную задачу, в которой в качестве матрицы стоимости выступает и может быть решена стандартными методами.
По компонентам оптимального плана затем вычисляются составляющие решения исходной задачи. Индексы поставщика и периода поставки l
при этом определяются из соотношений
l
={
Аналогично определяются индексы потребителя и k.