Учебное пособие

Учебное пособие Математические методы в инновационном менеджменте

Работа добавлена на сайт bukvasha.net: 2015-10-30

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 27.12.2024





Санкт-Петербургский государственный электротехнический

 университет “ЛЭТИ”

                                                                          

Отчет о разработке раздела учебного пособия

в рамках выполнения тематического модуля №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
может иметь не толь­ко стоимостный смысл. Например, это может быть расстояние, время, расход топлива и т. п.

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

В работе Л. В. Канторовича «Математические методы органи­зации и планирования производства», вышедшей в 1939 г., изло­жен метод разрешающих множителей и указано, что он пригоден для решения транспортной задачи. В 1949 г. Л. В. Канторович и М. К. Гавурин предложили один из наиболее эффективных мето­дов решения транспортной задачи — метод потенциалов.

При решении транспортной задачи на ЭВМ наиболее эффекти­вен венгерский метод, разработанный в конце 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.



1. Курсовая Биологические и географические особенности миграции наземных животных
2. Реферат на тему Language In Our Lives Essay Research Paper
3. Сочинение на тему Гоголь н. в. - Образ хлестакова
4. Реферат на тему Getting To The Reader Essay Research Paper
5. Реферат на тему Julius Caesar Flattery Essay Research Paper Flattery
6. Реферат на тему Militias Essay Research Paper Cory SmithEng 101
7. Реферат Кастро Сан-Франциско
8. Реферат Минерально-сырьевые ресурсы РФ
9. Реферат Современная форма концентрации товарного обращения на примере торговой сети Компьютерный Мир
10. Реферат Основные этапы развития социологии в России и их содержание