Международныйинститут
экономикии права
МАТЕМАТИЧЕСКИЕ МЕТОДЫ ЭКОНОМИЧЕСКИХ ИССЛЕДОВАНИЙ
Контрольная работа
Тема 1. Системы, системный подход, системныйанализ. Основные термины, определения, технологии
1. Понятие системы.
2. Системный подход, принципы системного подхода.
3. Системный анализ: постановка задачи, декомпозиция, композиция системы,исследование системы.
4. Структура системы.Краткое содержание темы
Вообще строго определенного понятия системы в настоящее время не существует.Однако, для целей экономического исследования наиболее приемлемым будет следующееопределение:
Система — это целостная совокупность элементов любого типа, взаимосвязанныхмежду собой, взаимодействие которых обеспечивает достижение поставленной цели.
Таким образом, для системы характерно наличие:
· совокупностиэлементов;
· взаимосвязиэлементов через структуру;
· взаимодействия;
· целенаправленности.
Элемент системы — это структурная единица системы, не подлежащая делениюв данных условиях рассмотрения системы.
Основным свойством системы является то, что она обладаетхарактеристиками, принципиально отличными от характеристик составляющих ее элементов.Только интегративное взаимодействие ее элементов позволяет системе достигнуть уникальныхсвойств.
Системный подход — это конкретно-научный метод диалектической методологии,имеющей общенаучное значение. Методология изучения системы как единого целого, состоящегоиз отдельных частей, с различных точек зрения формализации позволяет сформулироватьследующие принципы системного подхода.
Принцип конечной цели: абсолютный приоритет конечной (глобальной) цели.
Принцип единства: совместное рассмотрение системы как целогои как совокупности частей (элементов).
Принцип связности: рассмотрение любой части совместно с ее связями с окружением.
Принцип модульного построения: выделение модулей (подсистем)в системе и рассмотрение ее как совокупность подсистем.
Принцип иерархии: выделение иерархии частей (элементов) и (или) их ранжирование.
Принцип функциональности: совместное рассмотрение структуры и функций с приоритетомфункций над структурой.
Принцип развития: учет изменяемости системы, ее способности к развитию, расширению,замене частей, накапливанию информации.
Принцип децентрализации: сочетание в принимаемых решениях управления централизациии децентрализации.
Принцип неопределенности: учет неопределенностей и случайностей в системе.
Совокупность приемов и методов для изучения сложных системпредставляет собой системный анализ. Системный анализ — это средство и технологиясистемного подхода.
Рассмотрим основные этапы системного анализа.
1. Постановка задачи. Она включает:
· определениеобъекта исследования;
· постановкуцелей;
· заданиекритериев для изучения объекта и управления им.
Этап слабоформализуем. Успех постановки задачи определяетсяв основном искусством и опытом системного аналитика, глубиной понимания им поставленнойпроблемы.
2. Структуризация и очертание границ (декомпозиция) изучаемой системы. Онавключает:
· разбиениесовокупности всех объектов и процессов, отвечающих поставленной цели, на два класса:собственно исследуемую систему и внешнюю среду;
· изучениепроцессов взаимодействия объектов (элементов) системы и внешней среды.
Этап слабоформализуем. Он основан на искусстве и опыте проводящихэтот этап специалистов.
Разбиение объектов и процессов осуществляется в результате последовательногоперебора и включения в систему объектов и процессов, оказывающих заметное влияниена процесс достижения поставленной цели.
3. Составление модели изучаемой системы (как правило, математической).
Параметризация — первый этап этого процесса. Осуществляетсяописание элементов системы и элементарных воздействий с помощью тех или иных параметров.Параметры могут принимать как непрерывные, так и дискретные числовые значения, атакже значения в виде признаков, которые не могут быть охарактеризованы с помощьюобычных числовых параметров, а различаются качественно (например: теплый, холодный,плохой, хороший).
Установление различного рода зависимостей между введенными параметрами. Характерэтих зависимостей может быть любым. Количественные (числовые) параметры связываютсязависимостями типа систем уравнений (обыкновенных алгебраических или дифференциальных).Качественные параметры связываются зависимостями типа таблиц. В общем случае могутвстречаться комбинации зависимостей различных типов.
Зависимости между параметрами в системах задаются в общемслучае не простыми формулами, а произвольными алгоритмами с использованием любыхсредств как количественных, так и описательных.
Выделение подсистем и установление их иерархии преследует цель не толькоупрощения описания системы. Этот процесс дает возможность осуществлять уточнениепервоначальной структуризации (разбиения на элементы) и параметризации системы.
Результатом этого этапа является законченная математическая модель системы,описанная на формальном языке.
4. Исследование полученной (построенной) системы — четвертый этап системногоанализа.
Первая задача этапа — прогноз развития изучаемой системы.
Для решения этой задачи задают различные предположения о внешних воздействияхна систему в течение рассматриваемого периода и с помощью модели определяют распределениезначений, характеризующих систему параметров для любых фиксированных моментов времени.
Термин “прогноз развития” подчеркивает то обстоятельство, что для системынельзя определить единственную траекторию развития, можно определить лишь множествотаких траекторий. При этом каждая траектория может реализоваться в действительностилишь с той или иной степенью вероятности.
Получив прогноз развития изучаемой системы, производят анализ его результатовна соответствие заданным целям и критериям и вырабатывают предложения по улучшениюуправления и т.д., пока не получится удовлетворяющий результат.
Под структурой системы понимается организация системы из отдельных элементовс их взаимосвязями, которые определяются распределением функций и целей, выполняемыхсистемой.
Структура — это способ организации целого из составных частей .
Эффективность структуры определяется качеством, значением,формой и содержанием ее составных частей, а также местом, которое занимают они вцелом, и существующими между ними отношениями.
По принципам управления и подчиненности различают структуры (системы): централизованные,децентрализованные, смешанные.
Централизованная система: задания отдельным элементам системы выдаются лишьодним элементом более высокого уровня.
Децентрализованная система: решения отдельными элементами системы принимаютсянезависимо и не корректируются системой более высокого уровня.
В смешанной системе некоторые функции или этапы выполняются по централизованнойсистеме, а другие — по децентрализованной.
По числу уровней иерархии различают системы: одноуровневые, многоуровневые.
Многоуровневые могут быть однородными и неоднородными.
По выполняемым функциям и целевому назначению различают системы: физические,экономические, биологические, общественные, информационные и т.д.
В зависимости от числа элементов системы и связей между ними различают системыфиксированной (жесткой) и изменяемой (управляемой или переменной) структуры.
По принципам разбиения систем на подсистемы различают структуры систем, вкоторых элементы объединяются по функциональному и (или) объектному принципам. Приобъектном разбиении различают структуры отраслевых систем, региональных систем,территориальных систем.
Тема 2. Экономико-математическиеметоды. Состав, структура, направленность, классификация
1. Методы математической статистики.
2. Методы исследования операций и оптимизации.
3. Кибернетические методы.
4. Методы экспертных оценок.Краткое содержание темы
Основой моделирования экономических систем и протекающих в них процессовявляются экономико-математические методы. Рассмотрим состав и структуру экономико-математическихметодов, применяемых в современной экономической науке и практике.
К старейшим и наиболее используемым классам экономико-математических методовотносятся методы математической статистики. Эти методы используются для анализадеятельности экономических систем и включают в себя следующие направления:
· расчети интерпретация статистических характеристик экономических процессов;
· регрессионныйи корреляционный анализ;
· планированиеэксперимента.
Следующим классом экономико-математических методов являютсяметоды исследования операций и оптимизации. Это наиболее разработанная группа экономико-математическихметодов, позволяющих осуществить формализованный анализ экономических систем и процессов.
Среди методов исследования операций и оптимизации различаютследующие направления:
· методыматематического программирования;
· теориюмассового обслуживания и расписаний;
· сетевыеметоды планирования и управления;
· теориюигр;
· методыэвристики.
Основными направлениями методов кибернетики в экономике являются следующие:
· методыраспознавания образов;
· методыклассификации;
· методыАСУ;
· методытеории автоматического регулирования;
· имитационноемоделирование.
Наконец, одним из направлений экономико-математических методов являются методыэкспертных оценок. Эти методы используются для исследования сложных слабоформализуемыхсистем. Появление мощных программно-математических средств типа экспертных оболочекпозволяет надеяться, что в недалеком будущем метод экспертных оценок станет преобладающим,вобрав в себя все лучшие качества других экономико-математических методов, так какосновная цель практически всех экономических исследований сводится к оценке текущегосостояния исследуемого объекта (процесса) и выдаче прогнозов по его дальнейшемуразвитию.
Тема 3. Межотраслевойбаланс. Состав, структура, схема
1. Состав, структура и схема межотраслевогобаланса.
2. Задача и матрица Леонтьева.Краткое содержание темы
Идея сбалансированности является основой всякого рационального хозяйствования.
Рассмотрим схему народного хозяйства, состоящую из n отраслей, каждая изкоторых выпускает свой продукт.
В народнохозяйственном механизме все отрасли связаны между собой. Поэтомучасть продукции, произведенной i-ой отраслью, потребляется (затрачивается) при функционированииj-ой отраслью. Пусть xij — величина продукции i-ой отрасли, затрачиваемой (используемой)j-ой отраслью. Кроме того, потребителями продукции i-ой отрасли является населениеи непроизводственные сферы (коммунальные хозяйства, культурно-просветительные учреждения,сфера услуг и т.п.).
Пусть далее, vj — объем конечного продукта j-ой отрасли. Очевидно, он включаетdj — непроизводственное потребление (включая вложения в непроизводственные фонды)и bj — накопления производственных фондов.
Пусть далее, wj — общий объем производства j-ой отрасли, тогда имеем следующиесоотношения:
/>, j = 1, 2, ..., n, (3.1)
где />–общее промышленное и производственное потребление, далее:
/>,
где vj — непроизводственное потребление и накопление.
В принципе формула (3.1) представляет математическую модель межотраслевогобаланса в сфере потребления.
Отрасль можно анализировать не только с точки зрения распределения ее продукции,но и с точки зрения затрат на производство в данной отрасли. Пусть в этом случаев i-ой отрасли имеются затраты на заработную плату zi, кроме этого в балансе необходимопредусмотреть доход Di(i = 1, 2, ..., n). Тогда баланс по затратам будет иметь для i-ой отрасли следующийвид:
/>, i = 1, 2, ..., n,
т.е. стоимость продукции i-ой отрасли равна стоимости продукции, затраченнойот всех n отраслей, плюс заработная плата и доход от реализации продукции этой отрасли.
Введем определение коэффициента прямых затрат в виде соотношения:
/> , или /> .
Подставляя последнее соотношение в (3.1), получим:
/>,
или в векторной форме:
w = Aw + v. (3.2)
Пусть себестоимость производства одной единицы продукции j-ой отрасли будетравна cj. Тогда общие народнохозяйственные расходы выражаются соотношением:
/>.
Ставится следующая задача оптимизации плана />, когда:
/>,
а линейная форма L обращается в минимум.
Таким образом, приходим к так называемой статической модели межотраслевогобаланса.
Очевидно, что условиям задачи может удовлетворять множество наборов значенийxi (i = 1, 2, ..., n). Каждый такой набор носит название допустимого решения (стратегии,управления, плана). То решение, которое доставляет минимум целевой функции (линейнойформе L) называется оптимальным.
Поиск решения задачи межотраслевого баланса путем обращения матрицы (I — A) в различных аспектах был предложен Леонтьевым В., и в научных кругах задача сматрицей (I — A) называется задачей Леонтьева.
Матрица A получила название матрицы Леонтьева. Матрица (I-A)-1называется матрицей коэффициентов полных затрат. Основной результат межотраслевогоанализа может быть сформулирован в виде матричного равенства:
w = (I — A)-1v. (3.3)
Матрица A называется продуктивной, если матрица /> (положительная). Нормойматрицы A назовем максимум сумм элементов ее столбцов. Она обозначается ||A||. Можнодоказать, что если A положительная матрица и />, причем хотя бы для одного столбцасумма его элементов строго меньше 1, то A будет продуктивной матрицей.
Тема 4. Задачи на смеси
1. Постановка задачи на смеси.
2. Графический метод решения.
3. Общий алгоритм решения задач линейного программирования.Краткое содержание темы
Задачи на смеси являются одним из показательных классов задач по линейномупрограммированию в области планово-экономических исследований. На примере такихзадач могут быть рассмотрены основные методы решения задач линейного программированиякак одного из крупных разделов математических методов экономических исследований.
Классическая задача на смеси ставится следующим образом. Из различных видовсырья объемом соответственно b1, b2,..., bm-1,bm можно изготовить n видов продукции. Пусть цена единицы j-го вида продукциибудет cj и для изготовления единицы j-го продукта требуется затратитьi-ый вид сырья в количестве aij единиц. Возникает вопрос, какие видыпродукции и в каком количестве нужно производить, чтобы получить наибольшую выручку?
Таким образом, нужно определить количество производимой продукции при ограниченныхресурсах, при этом реализация произведенной продукции должна дать максимальную выручку.
Математически описанную задачу можно представить следующим образом.
Пусть /> - количество j-ой продукции, тогдастоимость всей произведенной продукции можно выразить функцией:
/> ‑ целевая функция.
Следовательно, в задаче идет речь о достижении максимума целевой функцииL на множестве различных допустимых значений />. Другими словами, критерием оптимальностизадачи является: />.
Очевидно, далее, что /> ³ 0 для j = 1, 2,..., n. Количество произведеннойпродукции не может быть отрицательным. Далее, на единицу j-го вида продукции требуется/> единиц i-госырья, т.е. для изготовления /> единиц j-го продукта потребуется /> единиц i-го сырья.
Так как один и тот же вид сырья может использоваться для производства любогоj-го продукта, то суммарные потребности i-го сырья на все j-ые продукты не должныпревышать имеющихся ресурсов b1, b2, ..., bm сырья,т.е.
/>.
Таким образом, приходим к следующей математической задаче.
Найти: /> при условии, что /> и />.
Очевидно, что условиям задачи может удовлетворить множество наборов значенийxj, где j = 1, 2, ..., n. Каждый из таких наборов носит название допустимогорешения (стратегии, управления, плана). Решение, при котором достигается max целевойфункции, называется оптимальным.
Графический метод решения задачи на смеси вытекает из следующих основныхсвойств задач линейного программирования:
· существуетвыпуклый многоугольник (многогранник) допустимых решений;
· оптимальноерешение задачи достигается в одной из вершин многоугольника допустимых решений.
Следовательно, если построить гиперплоскость целевой функции (критерия) нулевогоуровня, то, передвигая ее в сторону возрастания значений переменных, можно определитьпервую или последнюю вершину многоугольника допустимых решений для поставленнойзадачи, с которой передвигаемая гиперплоскость впервые встречается или покидаетобласть многоугольника. В частном случае гиперплоскость может представлять прямуюлинию. Соответственно первая вершина встречи будет определять минимальное значениецелевой функции, а последняя вершина встречи — максимальное.Общий алгоритм решениязадач линейного программирования
Без ограничения общности имеем следующую задачу линейного программирования:
/>, (4.1)
/>.
Найти среди допустимых />, j = 1, 2, ..., n, такие, что:
/>.
Основные шаги решения сформулированной задачи следующие.
1. Находится хотя бы одно из неотрицательных решений />.
2. Подставляем в систему полученное решение, в результате чего получаем новуюсистему, эквивалентную исходной:
/>.
3. Подставляем выражения основных переменных в L:
/>.
4. Применяем последовательность тождественныхпреобразований к полученной системе и линейной форме до тех пор, пока не исчезнутположительные коэффициенты при переменных в линейной форме, т.е. нарушатся условияее существования.
После конечного числа указанных шагов(если нет зацикливания) находится оптимальное решение поставленной задачи. В этомзаключается суть симплекс-метода.
Возникает вопрос. Как найти хотя бы однонеотрицательное решение системы (4.1)?
Сводим исходную систему (4.1) к виду:
/>, i = 1, 2, ..., m. (4.2)
Если в этой системеимеется переменная, входящая только в одно уравнение, и коэффициент при ней имеетзнак «+», то уравнение можно разрешить относительно этой переменной.
Считаем, что в (4.2) уравнения разрешеныотносительно всех таких переменных, тогда, сделав перенумерацию, имеем:
/> (4.3)
l = 1, 2, ..., l0; = 1, 2, ..., 0;
l0+ 0= m; l0+ k =n; />.
Любое уравнение в (4.3), неразрешенноеотносительно какой-либо переменной, будем называть 0-уравнением.
Для системы (4.3) неотрицательное решениеотыскивается последовательными тождественными преобразованиями, удовлетворяющимиследующим условиям:
1. Отыскиваем 0-уравнение, у которогосвободный член /> (если такого свободного члена нет, то значения переменных xl = bl, />, l = 1, 2, ..., l0; j = 1, 2,..., k образуют неотрицательное решение системы (4.3)). Пусть это будет i-ое уравнение.
2. Отмечаем в i-ом уравнении положительный коэффициент />.
3. Находим разрешающий элемент /> и производимторжественное преобразование (4.3).
4. i-ое 0-уравнениеиспользуется до тех пор, пока либо разрешим его, либо придем к несовместимости системы(4.3).
5. После разрешения i-го уравнения отыскиваем следующее 0-уравнение с положительным свободным членоми производим с ним аналогичные действия.
6. Процесс продолжается до тех пор, покане освободимся от всех 0-уравнений.
В результате можем получить:
а) после конечного числа тождественныхпреобразований система освободится от 0-уравнений. Тогда система будет совместимой.Совокупность значений переменных, получаемых приравниванием неосновных переменныхнулю, а основных — свободным членам в системе, не содержащей 0-уравнений, являетсянеотрицательным решением исходной системы;
б) После конечного числатождественных преобразований обнаружится, что используемое 0-уравнение превращаетсяв уравнение вида:
/>,
где />, т.е. для всех j — система несовместна;
в) система не освобождается полностьюот 0-уравнений, а условия тождественных преобразований не нарушаются. Число 0-уравненийне увеличивается, а некоторые из них имеют по крайней мере один положительный коэффициентв правой части, но разрешающий элемент ему не принадлежит.Тема 5. Транспортнаязадача
1. Постановка транспортной задачи.
2. Общий подход к решению транспортной задачи.Краткое содержание темы
Среди задач линейного программирования выделяется классзадач, условия постановки которых в определенной степени позволяют упростить процедуруих решения и определить специфические алгоритмы нахождения этих решений. Этот классзадач получил название «Транспортные задачи».
Рассмотрим постановку таких задач.
Пусть имеем m предприятий A1, A2,..., Am,производящих один и тот же продукт в количествах соответственно a1, a2,...,am.
Пусть, далее, имеется n потребителей (складов) B1, B2,...,Bn с потребностями (вместимостями) соответственно b1, b2,...,bn.
Пусть весь произведенный продукт может быть размещен на складах B1,B2,..., Bn при полном их заполнении.
Пусть, наконец, перевозка единицы продукции из пункта Ai в пунктBj оценивается величиной cij (cij — заданы).
Необходимо определить наилучший план перевозок по стоимости, т.е. такой план,который давал бы минимальную стоимость перевозок всей произведенной продукции насклады.
Строим математическую модель. Пусть xij — количество продукта,перевозимого из пункта Ai в пункт Bj. Из постановки задачиочевидно, что каждый склад вмещает:
/>.
А так как производится столько продукции, сколько ее потребляется (складируется),то:
/>
(продукт с предприятия вывозится полностью).
Далее, очевидным является то, что количество перевозимой с предприятия насклад продукции не может быть отрицательным, т.е. /> (i = 1, 2, ..., m; j = 1, 2, ...,n).
Так как необходимо определить наилучший план перевозок по стоимости, то строимцелевую функцию суммарных затрат на перевозки. Она должна быть минимизирована. Такаяцелевая функция имеет вид:
/>.
Таким образом, имеем следующую математическую постановку задачи. Найти такиеxij, которые доставляют минимум линейной форме L, т.е. /> и удовлетворяютусловиям:
/> (1)
/> (2)
/> (3)
(Из (1) и (2) следует, что />. Именно в этом соотношении заключаетсяосновная специфика выделенного класса задач, так как это соотношение определяетдополнительное условие (как бы скрытое), которое позволяет произвольным образомраспорядиться одной из переменных xij, а тем самым упростить решениезадачи).
Рассмотрим теперь подходы к решению транспортной задачи в общем виде, т.е.задачи размерности m x n.
Введем следующие понятия:
· прямоугольнаяцепь;
· независимыерасположения;
· подходящиерешения.
Понятие прямоугольной цепи исходит из следующих соображений.Пусть имеется некоторое допустимое решение задачи, которое может быть не оптимизируетрешение. Тогда это решение необходимо изменить. Но изменение хотя бы одной компонентырешения (количества продукции, перевозимой хотя бы по одному из путей) приводитк изменению общей суммы перевозок в соответствующей строке и столбце таблицы решений.Следовательно, в свою очередь необходимо изменить другие компоненты решения так,чтобы были «восстановлены» первоначальные значения указанных сумм. Схематическитакое «восстановление» может быть наглядно изображено в виде прямоугольнойдиаграммы или, иначе, цепи, которая связывает четыре клетки в таблице перевозок.Например:
/>
Очевидно, что любое множество допустимых изменений плана перевозок (т.е.изменений, которые сохраняют значения сумм по столбцам и строкам) должно быть эквивалентносерии прямоугольных цепей.
Будем говорить, что клетки матрицы перевозок, определяющей допустимое решение,расположены независимо, если прямоугольная цепь, содержащая эти клетки матрицы,имеет хотя бы одну нулевую клетку.
Подходящие решения — это последовательность допустимых решений, удовлетворяющихусловиям:
· матрицаперевозок каждого решения содержит ровно (m+n-1) ненулевых клеток;
· клеткиматрицы перевозок независимо расположены.
Можно указать способ нахождения последовательности подходящих решений, длякоторых транспортные издержки будут постоянно уменьшаться до тех пор, пока не будетдостигнуто оптимальное решение с минимальными затратами.
Существуют разные методы, упрощающие процедуру исследованиявсех допустимых изменений размещения грузов и позволяющие быстро находить нужныерешения. Одним из таких методов является метод теневых затрат.
Тема 6. Метод динамическогопрограммирования (ДП)
1. Понятие метода ДП.
2. Принцип решения задачи ДП.
3. Задача распределения ресурсов.
4. Практические рекомендации по постановкезадач ДП.Краткое содержание темыОбщее понятие методаДП
Динамическое программирование (или «динамическое планирование»)- это метод оптимизации так называемых многошаговых (многоэтапных) операций (задач).Пусть имеем задачу G, распадающуюся на ряд последовательных шагов или этапов, например,деятельность отрасли промышленности в течение ряда хозяйственных лет (m -лет). Пустьэффективность решения задачи (операции) описывается показателем W (назовем его «выигрыш»)и пусть он складывается из выигрышей на отдельных шагах, т.е.: /> - аддитивный критерий.
Пусть операция (задача) является управляемой, т.е. выбираются какие-то параметры,которые влияют на ход и исход. На каждом шаге выбирается какое-то решение, от которогозависит выигрыш на данном шаге и выигрыш на операции в целом, — шаговое управление.Совокупность всех шаговых управлений есть управление операцией (задачей) в целом.Обозначив его Х, а шаговое управление х1, x2, ..., хm,имеем:
/>, хi — может принимать любые значения (числа, векторы, функции и т.д.).
Требуется найти такое управление Х, при котором выигрыш W обращается в максимум:/>.
x = x *, при котором это случается, называется оптимальным управлением: />.
Пусть />, максимум берется по всем управлениямх, (возможным в данных условиях), т.е. возможна запись: />.Принцип решения задачиДП.
Метод ДП не предполагает, что каждый шаг оптимизируется отдельно, независимоот других.
Пусть, например, планируется работа группы предприятий, часть из которыхвыпускает предметы потребления, а остальные производят для них машины. Задача — за m лет получить максимальный объем предметов потребления.
Пусть планируются инвестиции на первый год. Если исходить из узких интересовэтого шага (года), то можно было бы вложить все наличные средства в производствопредметов потребления. Но такое решение не было бы правильным (эффективным) с точкизрения операции в целом. Конечно, вкладывая средства в производство машин, мы сокращаемобъем производства предметов потребления в данном году, но, однако, вместе с этимсоздаются условия для увеличения производства в последующие годы.
Итак, планируя многошаговую задачу, необходимо выбирать управление на каждомшагу с учетом всех его будущих последствий на еще предстоящих шагах.
Управление на i-том шаге выбирается так, чтобы была максимальной сумма выигрышейна всех оставшихся до конца шагах плюс данный.
Однако, последний шаг является исключением из этого правила. Здесь можнопланировать так, чтобы он сам, как таковой, принес наибольшую выгоду.
Следовательно, процесс ДП обычно разворачивается от конца к началу, т.е.сначала планируется m-й шаг. Но как его спланировать, если не знаем, чем кончаетсяпредпоследний шаг. Как быть?
Планируя последний шаг, нужно сделать разные предположения о том, чем кончитсяпредпоследний (m-1)-й шаг, и для каждого из этих предположений найти условное оптимальноеуправление на m-ом шаге [условное, так как оно выбирается, исходя из условия, чтопредпоследний шаг кончился так-то и так-то (каким-то образом)].
Предположим, что это сделано, и для каждого из возможных исходов предпоследнегошага известно условное оптимальное управление и соответствующий ему условный оптимальныйвыигрыш на m — ом шаге.
Теперь можно оптимизировать управление на предпоследнем (m-1)-ом шаге. Сноваделаем возможные предположения о том, чем может кончиться предыдущий (m-2)-й шаги для каждого из этих предположений находим такое управление на (m-1)-ом шаге, прикотором выигрыш за последние два шага ( m-й уже оптимизирован) максимален. Так находятсядля каждого исхода (m-2)-го шага условное оптимальное управление на (m-1)-м шагеи условный оптимальный выигрыш на двух последних шагах. И так, «пятясь назад»,оптимизируем управление на (m-2)-м шаге и т.д., пока не дойдем до первого. Предположим,что все условные оптимальные управления и выигрыши за весь" хвост" процесса(на всех шагах, начиная от данного и до конца) известны. Теперь можно найти не условныеоптимальные управления x* и w*.
Действительно, пусть известно, что в каком-то состоянии S0управляемаясистема (объект управления S) была в начале первого шага. Тогда можно выбрать оптимальноеуправление х1* на первом шаге. Применив его, меняем состояние системына некоторое новое S1*. В этом состоянии подходим ко второмушагу. Тогда тоже известно условное оптимальное управление x2*,которое к концу второго шага переводит систему в состояние S2*и т.д. Оптимальный выигрыш w* за всю операцию известен, так как именно на основеего максимальности выбиралось управление на первом шаге.
Таким образом, в процессе оптимизации управления методом ДП многошаговыйпроцесс «проходится» дважды:
· от концак началу — поиск условных оптимальных управлений и выигрышей за оставшийся «хвост»процесса;
· от началак концу — осуществляется «чтение» уже готовых рекомендаций и поиск безусловногооптимального управления x*, состоящего из оптимальных шаговых управлений x1*, x2*,..., xm*.Задача о распределенииресурсов
Имеется некий запас ресурсов (средств) К, который нужно распределить междупредприятиями А1, А2, ..., Аm. Каждое i-ое предприятиепри вложении в него каких-то средств x приносит доход в виде функции />. Все /> заданы (пусть онинеубывающие). Как распределить средства К между Ai (i =1,2,...,m), чтобыв сумме они дали максимальный доход?
Здесь нет параметра времени. Однако, операцию распределения средств можномысленно развернуть в какой-то последовательности, считая за первый шаг вложениев предприятие А1, за второй — вложение в предприятие А2 ит.д.
Управляемая система S в данном случае — это ресурсы (средства). Состояниесистемы S перед каждым шагом характеризуется одним числом S -наличным запасом ещене вложенных средств.
Шаговыми управлениями являются средства х1, x2, ...,хm, выделяемые конкретным предприятиям.
Требуется найти оптимальное управление, т.е. совокупность х1,x2, ..., хm, при которой суммарный доход максимален:
/>.Решение в общем виде
Находим для каждого i-го шага условный оптимальный выигрыш (от этого шагаи далее до конца), если к данному шагу подошли с запасом средств S. Обозначаем условныйоптимальный выигрыш wi(S), а соответствующее ему условное оптимальное управление- средства, вкладываемые в i-е предприятие, — xi(S).
Начинаем оптимизацию с последнего m-го шага.
Пусть подошли к этому шагу с остатком средств S. Вкладываем всю сумму S целикомв предприятие Аm. Следовательно, условное оптимальное управление на m-ом шаге: отдатьпоследнему предприятию все имеющиеся средства S:
/>,
а условный оптимальный выигрыш:
/>.
Задаваясь последовательностью значений S (располагая их достаточно тесно),для каждого значения S будем знать xm(S) и wm(S). Последний шаг оптимизирован.
Переходим к предпоследнему (m-1)-му шагу. Пусть подошли к нему с запасомсредств S. Обозначим wm-1(S) условный оптимальный выигрыш на двух последних шагах:(m-1)-ом и m-ом (последний оптимизирован). Если на (m-1)-ом шаге (m-1)-му предприятиювыделим средств x, то на последний останется S-x. Выигрыш на двух последних шагахбудет:
/>
и нужно найти такое x, при котором этот выигрыш максимален:
/>
Знак max означает, что берется максимальное значение по всем x, какие тольковозможны при x £ S (вложить больше,чем S нельзя) от выражения в { }. Этот максимум и есть условный оптимальный выигрышза два последних шага, а то значение x, при котором max достигается, — условноеоптимальное управление на (m-1)-ом шаге.
Далее оптимизируем (m-2)-й, (m-3)-й и т.д. шаги. Для любого i-го шага условныйоптимальный выигрыш за все шаги с этого и до конца находятся по формуле:
/>
и соответствующее ему условное оптимальное управление xi(S) — то значениеx, при котором этот максимум достигается.
Продолжая этот процесс, доходим до первого предприятия А1. Варьировать значениямиS нет нужды, так как знаем, что запас средств перед первым шагом есть K, т.е.:
/>.
Итак, максимальный выигрыш (доход) от всех предприятий найден. Значение x,при котором достигается max в последнем соотношении и есть оптимальное управление/> на первомшаге.
После того, как эти средства вложены в первое предприятие, остается />. Читая рекомендациюдля этого значения S, выделяем второму предприятию оптимальное количество средств:
/> и т.д. до конца.Практические рекомендациипо постановке задач ДП
1. Выбрать параметры (фазовые координаты), характеризующие состояние S управляемойсистемы перед каждым шагом.
2. Расчленить операцию (задачу) на этапы (шаги).
3. Выяснить набор шаговых управлений xi для каждого шага и налагаемые наних ограничения.
4. Определить, какой выигрыш приносит на i-ом шаге управления xi, если передэтим система была в состоянии S, т.е. записать «функции выигрыша»:
/>. (6.1)
5. Определить, как изменяется состояние S системы под влиянием управленияxi на i-м шаге; оно переходит в новое состояние:
/>. (6.2)
Эти функции изменения состояния тоже должны быть записаны.
6. Записать основное рекурентное уравнение ДП, выражающее условный оптимальныйвыигрыш wi(S) (начиная с i-го шага и до конца) через уже известную функцию wi+1(S):
/>. (6.3)
Этому выигрышу соответствует условное оптимальное управление на i-м шагеxi(S) (в уже известную функцию wi+1(S) нужно вместо S подставить измененное состояниеS = ji(S,xi) ).
7. Произвести условную оптимизацию последнего m-го шага, задаваясь гаммойсостояний S, из которых можно за один шаг дойти до конечного состояния, вычисляядля каждого из них условный оптимальный выигрыш по формуле:
/>,
и находя условное оптимальное управление xm(S), для которого этот максимумдостигается.
8. Провести условную оптимизацию (m — 1)-го, (m — 2)-го и т.д. шагов по формуле(6.3), полагая в ней i = (m — 1), (m — 2), ..., и для каждого из шагов указать условноеоптимальное xi(S), при котором достигается максимум. Если состояние системы в начальныймомент известно (что является обычным), то на первом шаге варьировать состояниесистемы не нужно — сразу находится оптимальный выигрыш для данного начального состоянияS0. Это и есть оптимальный выигрыш за всю операцию:
/>.
9. Провести безусловную оптимизацию управления, «читая» соответствующиерекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге/>, изменитьсостояние системы по формуле (6.2), для вновь найденного состояния найти оптимальноеуправление на втором шаге /> и т.д. до конца.
Тема 7. Сетевые методыпланирования
1. Понятие сетевых методов.
2. Разработка сетевых графиков.
3. Параметры сетевых графиков.
4. Расчет сетевых моделей.Краткое содержание темы
В последние годы в планировании и управлении различными экономическими объектамивсе чаще применяются сетевые методы или, как их иначе называют, сетевые графики.
Эти методы далеко не универсальны, и многие вопросы не могут быть решеныс их помощью, однако на своем месте, там, где их применение целесообразно, они весьмаэффективны.
Первое, что подлежит сделать, — это составить список всех работ, которыенеобходимо совершать с начала какого-либо процесса и вплоть до его завершения.
Существенную роль в выборе работ имеет продолжительность или время выполнения.Обычно подразделение на работы осуществляется так, что продолжительности их достаточноблизки, с той степенью детализации, которая достаточна для желаемой точности.
В принципе этот список может включать многие сотни работ.
Все работы в списке могут быть естественным способом упорядочены, т.е. можносказать, какая работа должна быть выполнена сначала, а какая за ней. Можно такжеуказать, какие работы будут выполняться одновременно.
Процесс упорядочения списка работ является наиболее существенной и трудоемкойчастью всего исследования.
Как только это сделано, можно приступать к созданию сетевой модели.
Результаты работ будем изображать кружком с соответствующим номером внутри.При этом, если работа i предшествует работе j, то будем изображать так:
/>
Пусть далее tij означает, что работа j может быть завершена через время tijпосле окончания работы i. Будем считать, что величины tij для всего списка работизвестны. Стрелка на этой модели обозначает собственно работу, а кружки — результат.
Эту простую схему применим для всего спектра работ.
В результате получим следующую схему, изображенную в виде графика:
/>
Модель готова. В чем ее польза?
С ее помощью можно ответить на вопрос, за какое наименьшее время может бытьзавершен весь процесс. Для этого из всего комплекса выделим две особо значимые работы.Первую — с нее начинается процесс и последнюю — ею заканчивается процесс. Ясно,что время завершения процесса не может быть меньше суммы длительностей (временивыполнения ) всех операций, взятых вдоль самого неблагоприятного, самого длинногопути, соединяющего первую и последнюю работы на построенном графике. Такой путь,т.е. путь, на котором достигается наибольшее возможное время окончания процесса,носит название критического пути. Те работы, через которые проходит критическийпуть, называются критическими. Эти работы следует выполнять, как только это будетвозможным.
Если задержаться с выполнением критической работы, то заведомо отодвигаетсямомент окончания всего процесса. Для каждой некритической работы имеется некоторыйинтервал свободы, в течение которого она может быть выполнена без ущерба для завершениясрока всего процесса.
Сетевая модель, отображающая процесс выполнения комплекса работ, направленныхна достижение единой цели, может быть изображена либо в виде сетевого графика (см.выше), либо в виде таблицы:Шифр работ
i j Продолжительность работ, tij Количество исполнителей 1 2 5 — 10 4 1 4 7 — 11 16 1 8 5 — 7 4 2 3 3 — 5 6 3 6 2 — 3 2 4 5 6 — 10 14 4 7 5 — 7 4 5 6 5 — 7 8 6 9 6 — 8 10 7 9 3 — 4 20 8 9 10 — 12 4
В таком виде модель используется для расчета вручную или для ввода данныхв ЭВМ.
Работа и событие ( результат ) — важнейшие понятия для сетевых моделей.
Работой в сетевом графике называется любой производственный процесс, событием- результат одной или нескольких работ, т.е. результат производственного процесса.
В сетевом графике встречается несколько типов работ и событий.
Это прежде всего реальные хозяйственные и технологические процессы, требующиезатрат времени и ресурсов для их осуществления. Такие работы обозначаются сплошнымистрелками. Но работой могут быть процессы, требующие только затрат времени.
Например: ожидание результата какого-нибудь процесса (естественная сушкаматериалов), ожидание какого-либо решения или данных не нуждаются в затратах ресурсов.Такие работы называются ожиданиями и обозначаются штрих- пунктирной линией.
Третий тип работ — это так называемые фиктивные работы. Они не требуют затратни материальных ресурсов, ни времени, они показывают зависимость какого-либо событияот другого. На сетевых графиках они показываются пунктирными стрелками.
Традиционно планы базируются только на работах, а результаты работ (события)подразумеваются. Введение в сетевые графики понятия «событие» позволяетболее четко вести процесс управления, так как язык событий не допускает двусмысленности.
Событие наступает или, как говорят, свершается тогда, когда закончены всепредшествующие ему работы.
Совершение события — предпосылка для начала следующих за ним работ. Событиене имеет продолжительности.
В связи с этим к его формулировке предъявляются особые требования. Каждоесобытие должно быть полно, точно и всесторонне определено, его формулировка должнавключать в себя результат выполнения всех непосредственно предшествующих ему работ,необходимый для начала последующих работ.
Сетевой график начинается с исходного события. Предполагается, что для егосвершения не нужны какие-либо предшествующие работы.
Обычно исходное событие — это принятое решение о начале какого-либо процесса(комплекса работ). Например: 7.
Завершающее событие — это конечный результат всего комплекса работ. Например:9.
Есть еще несколько типов событий.
Начальное событие — событие, непосредственно предшествующее каждой работе.
Конечное событие — событие, которым оканчивается какая-либо работа.
Например: на предыдущем графике для работы 2 — 3 событие 2 — начальное, 3- конечное.
Граничными событиями называются события, фиксирующие окончание работ какого-либоисполнителя (организации). Например: факт передачи исходных данных, выпуск чертежейи т.п.
Сетевой график обычно содержит одно исходное и одно завершающее события.
Если завершающих событий несколько, то такой график называется многоцелевым.
Сетевые графики обладают важным свойством — наглядностью.
Отображение логической последовательности работ, четкость их взаимосвязейдают возможность анализировать состав и порядок проведения предстоящего комплексаработ, уже это имеет организующее воздействие на их ход.
Графическое представление сетевой модели значительно упрощает ее составление,расчет, анализ и изучение.
Сетевой график — это не только график, но и модель какого-либо производственногопроцесса.
Важной особенностью сетевых методов является способ оценки параметров предстоящихработ. Оценку дает либо непосредственный исполнитель, либо эксперт, имеющий большойопыт работ в соответствующей области. Каждая работа оценивается по времени. Частос временными характеристиками даются оценки:
· количестваисполнителей;
· трудоемкости;
· стоимостии т.п.
Одним из важнейших понятий сетевых методов является понятие критическогопути. Его определяют при расчете сетевого графика (сетевой модели).
Критическим путем называется такая последовательность взаимосвязанных работи событий, которая имеет наибольшую продолжительность по времени.
Продолжительность критического пути характеризует продолжительность всегокомплекса работ в целом.
Понятие критического пути является основой оптимизации планов, координациии контроля выполнения работ.
Критический путь указывает на наиболее важные работы, от которых зависятсроки выполнения всего комплекса работ.
Как показывает опыт, количество работ и событий, входящих в критический путь,обычно не превышает 10% всех работ, что позволяет исключить из поля усиленного контроляте работы, которые в данный момент не влияют на своевременное достижение цели (аих большинство). Следовательно, имеется возможность выделить главное в работе.
Кроме выявления критического пути, расчет сетевого графика позволяет получитьцелый ряд других показателей:
· ранниеи поздние сроки начала и окончания работ;
· резерввремени;
· вероятностьнаступления событий и т.д.
Эти показатели применяются для оптимизации плана и для принятия решения порациональной организации выполнения всего комплекса работ.
Сетевые методы включают в себя ряд процедур, обеспечивающих управление навсем протяжении производственного процесса. Эти процедуры предусматривают поступлениеот исполнителей информации о ходе работ и о возможных изменениях их оценок или содержания.В соответствии с этой информацией сетевой график (модель) периодически уточняется.
Таким образом, сетевые методы сводятся к использованию для целей управления:
· сетевоймодели комплекса работ, которая является математическим описанием какого-либо процессаи показывает состав работ, их взаимосвязи и зависимость друг от друга, а также содержитоценки параметров работ;
· сетевогографика как наглядного отображения сетевой модели;
· специальныхметодов расчета сетевых графиков, позволяющих определять критический путь, резервывремени и другие параметры, используемые для планирования и координации работ;
· специальныхпроцедур сбора, обработки и подготовки информации для принятия решений.
Следовательно, сетевые методы — это совокупность приемов и способов, позволяющихна основе применения сетевых графиков (моделей) рационально осуществлять управленческийпроцесс: планировать, организовывать, координировать и контролировать любую сложнуюработу.
Рассмотрим способы определения параметров конкретного сетевого графика.
Пусть tij — продолжительность работы, которая измеряется, например, в днях.Индексы i и j указывают на начальное и конечное события работы.
В процессе расчета сетевого графика (модели) определяются и анализируютсяследующие основные параметры:
t (L) — продолжительность пути L;
t кр — продолжительность критического пути Lкр;
ti(p), ti(п) — ранний и поздний сроки совершения событий;
tij(pн), tij(пн) — ранний и поздний сроки начала работы;
tij(ро), tij(по) — ранний и поздний сроки окончания работы;
R(L) — полный резерв времени пути;
Rij(п) — полный резерв времени работы;
/> — частныерезервы времени.
Путем на сетевом графике называется любая непрерывная последовательностьработ, направленная к завершающему событию.
Продолжительность пути t(L) есть сумма продолжительности работ, составляющихэтот путь.
Для простых графиков расчет продолжительности критического пути можно сделатьна “глазок”. Для сложных графиков для этих целей служат математические методы.
Рассмотрим один из них.
Введем ряд дополнительных условий. Если сетевой график не содержит отрезка,соединяющего работы i и j, то считаем tij = — m. Далее положим tii = 0. Тогда с математической точкизрения задача состоит в следующем: найти такой путь />, где Еj — работы, n — число работ,при котором величина /> достигает максимума.
В основе метода лежит метод динамического программирования. Обозначим черезvi (i = 1, 2, ..., n-1) величину максимального пути от вершины i до конечной вершины.(Предполагается, что вершины занумерованы так, что начальная имеет номер 1, а последняя,завершающая, ‑ номер n).
Поиск критического пути осуществляется в несколько этапов.
На первом этапе определяем величины:
/>, i = 1, 2, ..., n-1;
/>, i = 1, 2, ..., n-1.
Ясно, что они выражают продолжительности времени, необходимого для того,чтобы достичь вершины n от i-ой вершины за один шаг.
Далее переходим к вычислению:
/>, i = 1, 2, ..., n-1; />, j = 1, 2, ...,n,
выражающих величины максимальных путей, соединяющих вершины сетевого графикас вершиной n и состоящих из двух звеньев.
Рассуждая аналогично, шаг за шагом, вычисляем:
/>, i = 1, 2, ..., n-1,
/>, j = 1, 2, ..., n,
до тех пор, пока не окажется, что выполнены условия:
/>, i = 1, 2, ..., n.
Найденное значение vi(k) будет выражать величину критическогопути, соединяющего первую и n-ую вершины, а число k укажет, из скольких звеньевэтот путь состоит. Можно указать, что если график состоит из n вершин, то для нахождениякритического пути достаточно n-2 этапа последовательных вычислений.
Тема 8. Методы теорииигр
1. Основные понятия теории игр.
2. Подход к решению задач теории игр.Краткое содержание темы
Методы теории игр применяются для анализа и выбора решений в конфликтныхситуациях, когда налицо две стороны, преследующие противоположные цели.
Типичным примером конфликтных ситуаций в экономической системе является конкурентнаяборьба, например борьба за рынок.
Результат или исход игры, даже в том случае, когда он не имеет прямой количественнойоценки, обычно характеризуется некоторым числом, например: выигрыш +1, проигрыш– -1, ничья – 0.
Игра может быть парной или множественной (многие участники).
Наиболее полно разработана теория парных игр с нулевой суммой, т.е. такихигр, в которых одна сторона выигрывает то, что проигрывает другая.
Процесс (развитие) игры происходит в результате последовательного выполнениятех или иных ходов.
Стратегией игрока называется совокупность правил, по которым он анализируетситуацию и делает ходы от начала игры до ее завершения.
Задание пары стратегий (А и В) (своей и противника) в парной игре полностьюопределяет ее исход, т.е. выигрыш одного и проигрыш другого (при случайных ходахопределяются математические ожидания выигрыша и проигрыша).
Игра называется конечной, если у каждого игрока имеется лишь конечное числостратегий.
Результаты конечной парной игры с нулевой суммой (КПИНС), можно задать матрицей,строки и столбцы которой соответствуют различным стратегиям, а ее элементы естьсоответствующие выигрыши одной стороны (равные проигрышам другой). Эта матрица называетсяплатежной матрицей или матрицей игры. При этом удобно проигрыш первой стороны рассматриватькак ее отрицательный выигрыш, а выигрыш второй — как ее отрицательный проигрыш.
Если первая сторона имеет m стратегий, а вторая – n, то имеем дело с игройm´n.
Рассмотрим игру m´nсо следующей матрицей:
B1
B2 ...
Bj ...
Bn
A1
a11
a12 ...
a1j
a1n
A2
a21
a22 ...
a2j
a2n ... ... ... ... ... ... ...
Ai
ai1
ai2 ...
aij
ain ... ... ... ... ... ... ...
Am
am1
am2 ...
amj
amn
где Ai (i = 1, 2, ..., m) — стратегии первого игрока, Bj (j = 1, 2, ...,n) — стратегии второго игрока, аij — плата в сеансе игры со стратегиями Ai и Bj.
Если первый игрок применяет стратегию Аi, то другой будет стремитьсяк тому, чтобы выбором соответствующей стратегии свести выигрыш первого игрока кминимуму. Из «арсенала» — набора своих стратегий второй выбирает такуюстратегию Вj, чтобы величина аij была бы минимальной, т.е.если i есть величина этого минимума,то:
/>.
C точки зрения первого игрока (при любых ответах противника) целесообразностремиться найти такую стратегию, при которой i будет обращаться в максимум. Пусть этот максимум равен. Он называется нижней ценой игры. Так как значение вычисляется по формуле:/> или />, то его называютмаксимином. Ему соответствует максиминная стратегия (их может быть несколько), придерживаяськоторой первый игрок при любых стратегиях противника обеспечит себе выигрыш, неменьший чем (в зависимостиот знака это может бытьпроигрыш, который в этом случае окажется минимальным).
Аналогичным образом определяется минимальный проигрыш (которыйможет быть в действительности и выигрышем) для второго игрока:
/>.
Величина называетсяверхней ценой игры или минимаксом. Ей соответствует минимаксная стратегия второгоигрока.
Имеет место неравенство: />.
При
Смешанная стратегия С состоит в том, что при повторении игры происходит случайныйвыбор стратегий из некоторого множества смешиваемых стратегий и для каждой смешиваемойстратегии указывается вероятность ее выбора.
Известно, что для любой КПИНС существует пара оптимальных стратегий (вообщеговоря смешанных).
Свойство оптимальности означает, что любое отступление одного из игроковот оптимальной стратегии (при условии, что второй игрок продолжает придерживатьсясвоей оптимальной стратегии) при многократном повторении игры может только уменьшатьего средний выигрыш (увеличить средний проигрыш).
Величина выигрыша (может быть, отрицательного) первого игрока при пользованиипарой оптимальных стратегий называется ценой игры и обозначается .
Цена игры заключена между нижней и верхней ценой игры:
/>.
Стратегии, которые смешиваются для получения оптимальной стратегии, будемназывать полезными.
Решить игру — это значит найти пару оптимальных стратегий и цену игры. Решениеигры обладает одним важным свойством: если один из игроков использует свою оптимальнуюстратегию, а другой смешивает свои полезные стратегии в любых пропорциях (не обязательнооптимальных), то средний выигрыш продолжает оставаться равным цене игры. При этом,правда, как при любых отступлениях от оптимальной стратегии, соответствующее изменениестратегии противником может привести к увеличению его среднего выигрыша.
Известно, что у игры m´nчисло полезных стратегий с каждой стороны не превосходит минимального из чисел mи n.
В области чистых стратегий решение может быть получено непосредственно. Еслиже решение нужно искать в области смешанных стратегий />, то в общем случае m´n матрицы /> применяетсяследующий прием.
Считая все m стратегий первого игрока полезными, определяют вероятность ихприменения в смешанной оптимальной стратегии (если какая-то стратегия в действительностибесполезна, то соответствующая вероятность обратится в нуль). Пусть искомые вероятностиобозначаются />, а цена игры (пока неизвестная) — .
Так как при оптимальной стратегии средний выигрыш первого игрока не меньшепри любой стратегии противника, то ищемn неравенств:
/>
Вводим новые неизвестные:
/>.
Чтобы исключить деление на нуль, можно всегда добиться />. Для этой цели достаточноко всем элементам матрицы /> прибавить одно и тоже положительноечисло с и все ее элементы сделать положительными. Эта операция увеличит цену игрына с, но не изменит искомых оптимальных стратегий.
Так как
/> = 1,то />.
Таким образом, имеем систему неравенств:
/> , (8.1)
где все />.
Так как цель оптимальной стратегии – максимизация выигрыша, то при ее достижениилинейная функция:
/>
должна обратиться в минимум. Итак, оптимальная стратегия первого игрока (т.е.набор вероятностей />) находятся в результате минимизациифункции:
/>
при />,удовлетворяющих системе неравенств (8.1).
Таким образом, получили задачу линейного программирования. Методы решениятаких задач известны. В результате ее решения находим не только оптимальную стратегиюпервого игрока, но и цену игры />.
Зная цену игры, оптимальную стратегию (а1, а2, ..., аn) второго игрока можнонаходить уже без решения задачи линейного программирования (хотя оптимальную стратегиювторого игрока можно находить и через решение этой задачи, если поменять игроковместами). Для этого выбирается n-1 полезных стратегий первого игрока (имея возможностьменять местами игроков можно считать, что/>) и для каждой из них записываетсясредний выигрыш, который при этом должен быть обязательно равен цене игры />. Например, еслидля первого игрока полезна стратегия Аi, то ей соответствует уравнение:
/>.
Кроме этого имеется еще одно уравнение:
/>.
Всего имеем n уравнений для n величин q1, q2, ..., qn.
Игровые методы могут применяться для изучения ситуаций, которые не являютсяв строгом смысле слова конструктивными. Например, ситуации, где вторым игроком являетсяприрода.
Тема 9. Имитационноемоделирование
1. Понятие имитационного моделирования.
2. Общая постановка задачи имитационного моделирования.
3. Метод Монте-Карло.Краткое содержание темы
До сих пор рассматривались методы решения задач, в которых была известнацель (или несколько целей), достижение которой (которых) считалось желательным.Однако далеко не все ситуации таковы. Особенно ими изобилует современный этап прикладныхисследований, когда приходится иметь дело со сложными системами, когда наличествуетне только множество целевых функций, но далеко не все ясно с количественным выражениемэтих функций. В данном случае речь может идти не столько о решении тех или иныхзадач (хотя это присутствует и здесь), сколько об исследовании поведения сложныхсистем, о прогнозировании их будущих состояний в зависимости от выбираемых стратегийуправления.
Итак, практике потребовался метод для исследования сложных систем, и такойметод появился — это имитационное моделирование («simulation modeling»).
Поскольку для сложных систем многие функции, параметры, характеристики носятслучайный характер, то для оценки этих атрибутов, как правило, используется аппаратстатистических оценок, а сам метод имитационного моделирования иногда называют методомстатистических испытаний. Другими словами, это метод вероятностных оценок, а отсюда,по аналогии с игровыми ситуациями Монте-Карло, его также называют методом Монте-Карло.
Идея метода Монте-Карло чрезвычайно проста и состоит в следующем. Вместотого, чтобы описывать исследуемый процесс (как правило случайный) с помощью аналитическогоаппарата, производится «розыгрыш» процесса (явления) с помощью какой-либопроцедуры, дающей случайный результат. Так же как и в реальности конкретное осуществление(реализация) случайного процесса складывается каждый раз по-разному, также и в результатестатистического моделирования (розыгрыша) получаем каждый раз новую, отличную отдругих, искусственную реализацию процесса. Множество получаемых таким образом реализацийдалее обрабатывается как статистический материал, и из него получаются нужные вероятностныехарактеристики требуемого результата.
При получении множества реализаций мы пользуемся случайностью как аппаратомисследования, заставляя случайность работать на себя.
Метод имитационного моделирования, как правило, используется для анализафункционирования сложных систем, когда возникают непреодолимые сложности при попыткепостроить «строгую» математическую модель изучаемого объекта, содержащегомного связей между элементами, разнообразные нелинейные ограничения, огромное количествопараметров и т.п. Иногда можно построить такую модель, но использовать ее из-заотсутствия математического аппарата не представляется возможным. В некоторых случаяхдля исследуемой системы не существует стройной теории, объясняющей все аспекты еефункционирования, а, следовательно, представляется затруднительным формулированиетех или иных правдоподобных гипотез ее поведения.
Далее, реальные системы, как правило, подвержены влиянию различных случайныхфакторов, учет которых аналитическим путем представляет порой непреодолимые трудности.
С другой стороны, использование математического аппарата дает возможностьсопоставить модель и оригинал только в начале и после применения соответствующегоаппарата, что затрудняет верификацию модели.
В основе метода имитационного моделирования лежит возможность максимальногоиспользования всей имеющейся в распоряжении исследователя информации о системе стем, чтобы получить возможность преодолеть аналитические трудности и найти ответына поставленные вопросы о поведении системы.
Имитационное моделирование, как правило, используется в сугубо практическихцелях.Основными этапами методаявляются:
1. Формулировка основных вопросов о поведении системы и задание параметров,характеризующих состояние системы, т.е. определение вектора состояния.
2. Декомпозиция (разбиение) системы на более простые части — блоки. В одинблок объединяются «родственные», т.е. преобразующиеся по близким правилам,компоненты вектора состояния и процессы, их преобразую щие.
3. Формулируются правила и «правдоподобные» гипотезы относительноповедения системы в целом и ее отдельных частей. В каждом блоке может использоватьсясвой математический аппарат (алгебраические дифференциальные уравнения, математическоеи динамическое программирование и т.п.). Именно это, т.е. блочный способ (принцип),дает возможность установить необходимые пропорции между точностью описания каждогоблока, обеспеченностью его информацией и необходимостью достижения цели моделирования.
4. Вводится так называемое системное время, которое моделирует ход временив реальной системе.
5. Формализованным образом задаются необходимые феноменологические свойствасистем в целом и отдельных ее частей. (Часто эти свойства не могут быть обоснованына современном уровне знаний, а опираются на опыт — длительное наблюдение за поведениемсистемы). Иногда одно такое свойство оказывается эквивалентным множеству сложныхматематических соотношений и с успехом их заменяет, что, конечно, требует глубокогознания системы.
6. Случайным параметрам, фигурирующим в модели, сопоставляются некоторыеих реализации, сохраняющиеся в течение одного или нескольких тактов системного времени.Далее отыскиваются новые реализации.
Как правило, пятый и шестой этапы наиболее просто осуществимына ЭВМ, поэтому имитационные модели обычно реализуются с использованием специализированныхпрограмм, описывающих функционирование отдельных блоков и правила взаимодействиямежду ними.
Использование реализаций случайных величин требует многократного повторенияэкспериментов с моделью с последующим статистическим анализом полученных результатов.Общая постановка задачи
Под имитационным моделированием будем понимать пошаговое моделирование поведенияобъекта с помощью ЭВМ. Это означает, что фиксируются определенные моменты времениt1,t2,...,tn, и состояние модели определяется (вычисляетсяна ЭВМ) последовательно в каждом из этих моментов времени. Для реализации этогонеобходимо задать правило (алгоритм) перехода модели из одного состояния в следующее,т.е. преобразование: />, где Yi — состояние моделив i-й момент времени.
Пусть, как обычно, состояние модели определяется вектором: />, т.е. m — числами,состояние среды вектором: />, n — числами, а состояние управлениявектором: />,q — числами.
Тогда имитационная модель определяется оператором F, с помощью которого можноопределить состояние модели в последующий момент времени, т.е. определить векторYi+1, зная состояние модели в предыдущий момент времени Yiи значения Хi+1 и Ui+1, т.е. />.
Таким образом, в имитационной модели состояние модели определяется рекуррентнона каждом шаге, исходя только из предыдущего шага. Этот алгоритм можно записатьв виде рекуррентной формулы:
/>,
где F — оператор имитаций изменения состояния модели. Он и определяет имитационнуюмодель объекта.
Можно рассмотреть частный случай имитационной модели под воздействием окружающейсреды в виде:
/>.
Но имитационное моделирование (или модели) тем и хорошо, что позволяет учитыватьнеконтролируемые факторы Е объекта, т.е. его стохастичность, в этом случае модельможно представить рекуррентным соотношением вида:
/>, i = 1,...,N, (9.1)
где необходимо знать, каким образом фактор Е влияет на состояние Y объекта,т.е. следует хорошо разобраться в объекте и указать точно, как входит неконтролируемыйфактор Е в оператор объекта с тем, чтобы эти данные отразить в операторе F объекта.Для работы с такой моделью необходимо знать конкретные значения фактора E, который,как известно, ненаблюдаем. Возникает противоречие, которое решает так называемыйметод Монте-Карло. Собственно, как правило, он и является основным методом имитации.
Для реализации метода Монте-Карло необходимо знать некоторые статистическиесвойства фактора Е (например, закон его распределения). Эти свойства, вообще говоря,могут зависеть от Y, X и U. Располагая этими сведениями, можно моделировать ненаблюдаемыйфактор в виде случайных рядов:
/>, j = 1, 2, ..., N,
где индекс внизу соответствует дискретному времени, а верхний ‑ номерумоделируемого ряда (всего моделируется N таких статистически эквивалентных рядов).Естественно, ни один из этих рядов не является точной реализацией действительности,но каждый имеет такие же статистические свойства, что и реальный. Именно поэтомуряды /> позволяютисследовать статистические свойства модели (9.1).
Так поведение модели " в среднем" описывается как:
/>, />,
где Yij — j-я реализация поведения модели в i-ый моментвремени:
/> i=1,2,....,N.
Дисперсия выхода модели вычисляется по формуле:
/>.
Таким образом, метод Монте-Карло позволяет оценить статистические свойстваповедения объекта путем вероятностного «разыгрывания» поведения модели,причем одна реализация поведения отличается от другой различными значениями ненаблюдаемогофактора Е.
В сущности методом Монте-Карло может быть решена любая вероятностнаязадача, но оправданным он становится только тогда, когда процедура розыгрыша проще,а не сложнее аналитического расчета.
В задачах исследования операций метод Монте-Карло применяется в трех основныхролях:
1. Моделирование сложных, комплексных объектов и операций, где присутствуетмного взаимодействующих случайных факторов.
2. Проверка применимости более простых аналитических методов и выясненийусловий их применимости.
3. В целях выработки поправок к аналитическим формулам «типа эмпирическихформул» в технике.
Таким образом, этот метод является своеобразным ОТК математических методов.При этом статистические модели не требуют серьезных допущений и упрощений. В такуюмодель вписывается все, что угодно — любые законы распределения, любая сложностьсистемы, множественность ее состояний.
Главный же недостаток таких моделей — их громоздкость и трудоемкость. Огромноечисло реализаций, необходимое для нахождения искомых параметров с приемлемой точностью,требует большого расхода машинного времени. Кроме этого, результаты такого моделированиятруднее осмыслить, чем расчеты аналитическими методами и, соответственно, труднееоптимизировать решение (в основном, наощупь). Наиболее целесообразным является сочетаниеаналитических и имитационных методов. Как правило, аналитическими методами рассчитываютсяотдельные элементы и блоки сложной системы, а затем, как из «кирпичиков»,строится большая сложная имитационная модель.
Основным элементом, из совокупности которых складывается статистическая модель,является одна случайная реализация моделируемого явления.
Реализация — это как бы один экземпляр случайного явления со всеми присущимиему случайностями. Этим реализации отличаются одна от другой. Отдельная реализацияразыгрывается с помощью специально разработанной процедуры (алгоритма), в которойосновную роль играет «жребий» или, как говорят, «бросание жребия».Каждый раз, когда в ход явления вмешивается случай, его влияние учитывается не расчетом,а жребием.
Понятие «жребия». Пусть в ходе процесса наступил момент, когдаего дальнейшее развитие (а значит и результат) зависит от того, произошло или неткакое-то событие А.
Тогда нужно «бросанием жребия» решить вопрос:произошло событие или нет? Как можно осуществить этот жребий? Необходимо привестив действие какой-либо механизм случайного выбора.
Если жребий бросается для того, чтобы узнать, произошло ли событие А, егонужно организовать так, чтобы условный результат розыгрыша имел ту же вероятность,что и событие А.
Кроме случайных событий на ход и исход операции могут влиять различные случайныевеличины.
С помощью жребия можно разыграть как значение любой случайной величины, таки совокупности значений нескольких величин.
Условимся называть «единичным жребием» любой опыт со случайнымисходом, который отвечает на один из следующих вопросов:
1. Произошло или нет событие А?
2. Какое из событий А1, А2, ..., Аk произошло?
3. Какое значение приняла случайная величина Х?
4. Какую совокупность значений приняла система случайных величин Х1, Х2,..., Хk?
Любая реализация случайного явления методом Монте-Карлостроится из цепочки единичных жребиев, перемежающихся с обычными расчетами. Имиучитывается влияние исхода жребия на дальнейший ход событий (в частности на условия,в которых будет разыгран следующий жребий).
Единичный жребий может быть разыгран разными способами, но есть один стандартныймеханизм, с помощью которого можно осуществить любую разновидность жребия. А именно,для каждой из них достаточно уметь получать случайное число R, все значения которогоот 0 до 1 равновероятны (т.е. обладают одинаковой плотностью вероятности).
Условно назовем величиной R «случайное число от 0 до 1». С помощьютакого числа можно разыграть любой из четырех видов единичного жребия.
Тема 10. Методы теориимассового обслуживания
1. Основные понятия теории массового обслуживания.
2. Постановка задачи теории очередей.
3. Подходы решения задач теории очередей.Краткое содержание темы
Практическая деятельность человека тесно связана с различного рода системамимассового обслуживания. В области экономики — это банковское обслуживание, пользованиеобъектами торговли и услугами сферы обслуживания и многие другие виды экономическойдеятельности.
Любая система массового обслуживания может включать в себя следующие элементы:
Входящий поток требований или заявок на обслуживание. Этот элемент являетсяосновным. Изучение входящего потока требований и его описание необходимо при организациилюбой системы массового обслуживания.
Очередь. В тех случаях, когда поступающие в систему массового обслуживаниятребования не могут быть удовлетворены немедленно, возникает очередь. В такой ситуацииинтерес может представлять длина этой очереди, порядок, по которому ожидающие требованиянаправляются на обслуживание (как говорят, дисциплина очереди), время ожидания.
В отдельных случаях систем массового обслуживания очереди не допускаются,т.е. требование, заставшее систему занятой, не обслуживается (получает отказ).
Обслуживающее устройство. Этот элемент присутствует в любой системе массовогообслуживания. От характеристик и параметров, способов организации обслуживающегоустройства зависят не только время, необходимое на обслуживание одного требования,но и длина очереди и время ожидания.
Выходящий поток обслуженных требований. Этот элемент может оказаться оченьважным в тех случаях, когда выходящий поток обслуженных требований является входящимдля другой системы массового обслуживания.
Как правило, число требований на входе системы массового обслуживания закакой-либо промежуток времени и время обслуживания одного требования являются случайнымивеличинами. Функционирование системы массового обслуживания в таком случае представляетсобой случайный процесс, и методы исследования таких систем используют имитационноемоделирование. Однако понять сущность задач и методов теории массового обслуживанияможно на примерах детерминированных моделей систем массового обслуживания и преждевсего моделей теории очередей.
Основными компонентами модели очереди являются:
· описаниевходящего потока требований;
· описаниеспособа, которым выполняется обслуживание (т.е. описание дисциплины обслуживания);
· описаниедисциплины очереди (т.е. каким образом из очереди выбираются клиенты на обслуживание:“первый пришел — первый обслужен”, “последний пришел — первый обслужен”, “по указаннымприоритетам” и т.п.).
При конструировании модели очереди первоочередной задачей является символическоепредставление основных компонент, после чего изучаются соотношения между ними.
Принципиальными характеристиками очереди являются:
· длинаочереди в различные моменты времени;
· общаяпродолжительность нахождения требования в системе обслуживания (т.е. время, потраченноена ожидание в очереди, плюс собственное время обслуживания);
· время,в течение которого обслуживающее устройство было свободно.
Основной целью исследования систем массового обслуживания является установлениеравновесия между допустимыми нагрузками обслуживающего устройства, ограниченнойпропускной способностью системы и раздражением клиента, с одной стороны, и допустимойстоимостью обслуживающих точек, с другой.
Рассмотрим систему массового обслуживания, имеющую один источник требований,проходящих через единственное обслуживающее устройство. Пусть имеют место следующиепредположения:
1. Требования поступают через одинаковые интервалы времени. Каждый интервалимеет длину a единиц.
2. Требования обслуживаются за одинаковые интервалы времени, каждый интервалимеет длину b единиц. При этом, как только закончится обслуживание одного требования,обслуживающее устройство готово к обслуживанию следующего требования.
3. Дисциплина очереди устанавливается по правилу “Первый пришел — первыйобслуживается”. Другими словами, ожидающие требования образуют очередь, и, когдаобслуживающее устройство освободится, на обслуживание поступает требование, имеющеебольшее время ожидания.
Определим длину очереди как общее число требований, находящихся на обслуживаниии ожидающих в очереди. Представим сформулированную задачу в виде следующей схемы:
/>
Поведение системы зависит от того, как связаны между собой величины a и b.Возможны три случая: 1) b > a; 2) b = a; 3) b
1) Случай b > a. Это значит, что скорость обслуживания 1/b меньше, чемскорость поступления требований 1/a, т.е. требования обслуживаются и покидают системумедленнее, чем прибывают. Следовательно, в этом случае будет образовываться очередьи она будет постоянно возрастать.
2) Случай b = a. Если в очереди нет требований, то первое поступившее требованиесразу начнет обслуживаться. Его обслуживание закончится в тот же самый момент, вкоторый поступит на обслуживание следующее требование. Следовательно, требований,ожидающих обслуживания, не будет.
Если же первоначально имеется очередь, то ее длина будет оставаться постоянной.
3) Случай b
Пусть в начале процесса число требований в очереди r ³ 2 (если первоначальноесть только одно требование (r = 1), то оно будет обслужено прежде, чем поступятна обслуживание следующие требования, и очередь будет пустой).
В общем случае, пусть имеем r требований, стоящих в очереди перед началомобслуживания. Тогда число требований (N), поступивших после начала процесса обслуживаниядо тех пор, пока сохраняется очередь, можно определить по формуле:
/>, (10.1)
где обозначение [x] означает целую часть числа x. Действительно, очередьбудет отсутствовать, если через обслуживающее устройство полностью пройдет N+r требований.Для этого потребуется (N+r)b единиц времени. За это время на обслуживание поступитN требований, так что к поступлению (N+1)-го требования обслуживающее устройствобудет свободно и готово обслужить его сразу без всякой очереди. Но (N+1)-е требованиепоступит на обслуживание через (N+1)a единиц времени, при этом будет выполнено соотношение:
/>.
Отсюда,
/>. (10.2)
Докажем, что в полученном соотношении N больше правой части не более чемна 1. Действительно, первое стоящее в очереди требование будет уже обслужено, апервое вновь поступающее на обслуживание требование еще не появится в очереди (a> b). Поэтому справедливо соотношение:
aN /> (N+r-1)b или />.
Таким образом, если к правой части соотношения /> добавим 1, то оно будет тождественноравно правой части соотношения />. То есть прибавление 1 к правой частисоотношения /> приводитего к соотношению /> – смысл неравенства меняется на противоположный.Это и требовалось доказать.
Очевидным является то, что N есть целое число. Следовательно, если от правойчасти в соотношении (10.2) взять целую часть и добавить к ней 1, то, исходя из предыдущихрассуждений, получим для вычисления N выражение (10.1).
Аналогичными рассуждениями и используя (10.1) можно найти, что для вычислениявремени, которое необходимо для обслуживания всех ожидающих требований, справедливаформула:
/>. (10.3)
В теории очередей важной функцией является функция времени ожидания обслуживания.Обозначим ее через W(t). Определим W(t) как время, которое необходимо затратитьна ожидание обслуживания требования, поступившего в момент времени t (считаем, чтоt = 0 соответствует началу процесса обслуживания).
Определим формулу для W(t). Легко видеть, что требование, поступившее наобслуживание в момент t ³T-b (величина T определяется с использованием формулы (10.3)), найдет систему обслуживанияпустой или только что освободившейся. Такому требованию не придется стоять в очереди.Требование, поступившее в момент времени t£T-b, найдет впереди себя /> требований, стоящих в очереди,причем первое из них в этот же момент поступит на обслуживающее устройство. Этавеличина получается следующим образом:
(начальная (число требований, обслужен- (число поступ-
очередь) — ных к моменту времени t) + лений)
r — /> + />.
Таким образом, время ожидания W(t) для рассматриваемого требования можетбыть выражено формулой:
/>. (10.4)
Рассмотрим i-е требование в начальной очереди (0
Обобщая полученные результаты относительно функции W(t), получим для нееследующее выражение:
/>,
где i — номер i-го требования в начальной очереди; требования поступают вмоменты времени a, 2a, ...; b = na (n = 1, 2, ...).
Тема 11. Управление запасами
1. Понятие задачи управления запасами.
2. Основная задача управления запасами.
3. Управление запасами в условиях производственных поставок.
4. Управление запасами в условиях дефицита.Краткое содержание темы
Класс задач по управлению запасами является достаточно специфичным как поразнообразию постановки задач, так и по методам их решения. Здесь успешно применяютсяметоды линейного и динамического программирования, методы теории массового обслуживанияи многие другие. В данном разделе рассматриваются простые методы математическогоанализа для решения задач управления запасами.
Предприятия в процессе своей деятельности делают различные запасы. Запасы- это совокупность предметов (товаров), представляющих собой временно неиспользуемыеэкономические ресурсы.
Причины создания запасов могут быть различными.
Если в нужный момент производства необходимые материалы или товары не поступаютот поставщиков и их нет на складе в запасе (т.е. имеет место дефицит), процесс производстваможет задержаться или совсем остановиться. Однако, если запасы достаточно велики,то возрастает плата за них и за их хранение.
Таким образом, возникает задача управления запасами, т.е. необходимо выбратьнекоторое компромиссное решение по созданию запасов или выработать стратегию управлениязапасами.
Основные типы принимаемых решений по управлению запасами следующие:
1. Определить какое, количество товара должно быть в запасе.
2. Определить, в какое время необходимо производить пополнение запасов.
В настоящее время существует множество подходов к решению подобного родазадач.
Рассмотрим три простейшие математические модели, включающие:
а) основную модель управления запасами — определение оптимального размерапартии;
б) модель производственных поставок;
в) модель, учитывающую штрафы.
Итак, предмет изучения — количество D запаса на складе и время t, для которого рассматриваетсяэтот запас, т.е. исследуется функция D = f(t), соответствующая величине запаса в момент времени t. Графиктакой функции называется графиком изменения запаса.
/>
По поводу изменения функции запасов сделаем следующие предположения:
1.При наличии заявки на товар, он отпускается и D уменьшается. Величина спроса непрерывна во времени.
2. Если D = 0, тоимеет место дефицит товара.
3. При поступлении товаров на склад (запасы пополняются) и D увеличивается. Пусть сначалапополнение запасов будет мгновенным, затем допустим, что пополнение идет непрерывно,в течение некоторого интервала времени.
Издержки, связанные с запасами, можно представить следующим образом:
Организационные издержки — расходы, связанные с оформлением и доставкой товаров,необходимые для каждого цикла складирования. Это подготовительно-заключительныеоперации при поступлении товаров и подаче заявок.
Если запасы нужно пополнить, то на склад завозится очередная партия. Издержкина поставку — организационные издержки.
Количество товаров, поставляемое на склад, — размер партиитоваров.
Издержки содержания запасов — затраты, связанные с хранением. Расходы этогорода возникают из-за ренты складирования и амортизации в процессе хранения (товарымогут портиться, устаревать, их количество может уменьшаться и т.п.).
Издержки, связанные с дефицитом (штрафы). Если поставка со склада не можетбыть выполнена, то возникают дополнительные издержки, связанные с отказом. Это можетбыть реальный денежный штраф, уплачиваемый лицу, делающему заявку на товар, илиущерб, не осязаемый непосредственно (ухудшение бизнеса в будущем, потеря потребителей).
Математическая модель должна учитывать все эти издержки, и цель моделированиязаключается в том, чтобы найти такую стратегию управления запасами, при которойсуммарные издержки, связанные с запасами, сводились бы к минимальным.Основная задача
Итак, имеем следующую таблицу параметров модели и предположения (допущения)по изменению их величин.Название параметра Обозначение Единицы измерения Предположения Интенсивность спроса d Ед-цы товара в год Спрос постоянен и непрерывен. Весь спрос удовлетворяется. Организационные издержки s $ за одну партию Организационные издержки постоянны, не зависят от размера партии Стоимость товара c $ за ед-цу товара Цена ед-цы товара постоянна, имеем только один вид товара Издержки содержания запасов h $ за ед-цу товара в год Стоимость хранения ед-цы товара в течение года постоянна Размер партии q Ед-ца товара в одной партии Постоянная величина, поступление мгновенное, как только уровень запаса становится равным 0.
Задача управления: определить значение q, при котором минимизируются годовыезатраты.
Рассмотрим график изменения запасов. В соответствии с предположениямиэтот график имеет вид:
/>
Чтобы полностью удовлетворить годовой спрос d в размере поставки, равномq, нужно за год сделать /> поставок. Партия — это поставка.
Средний уровень запасов равен />.
Составляем уравнение издержек. Это будет:
/>.
Чтобы найти минимум С, считаем функцию f(q) дифференцируемой. Тогда значениеq находится из уравнения:
/> или />,
откуда
/>,
где q* — оптимальный размер партии, называемый также оптимальным заказом.Модель производственныхпоставок
Рассмотрим теперь модель производственных поставок, когда поступление товаровна склад производится непосредственно с производственной линии, т.е. уже не будетмгновенным (т.е. партия не поставляется в течение одного дня).
Считаем, что заказы поступают непрерывно.
Допущения в таблице остаются такими же за исключением тех, которые касаютсяпоступления продукции. Эта величина теперь будет определяться скоростью производства,p — количество товаров, выпускаемых производственной линией за год.
За каждый цикл изменения запасов на склад поступает q единиц товара. Этоколичество идет с производственной линии, работающей со скоростью p. Спрос в течениегода постоянен и его интенсивность d. Как только уровень запасов станет нулевым,с линии начнет поступать следующее количество товаров. Величина q — размер партии,т.е. количество товара в одной поставке. Описанная картина представлена на следующемграфике:
/>
Эффективная скорость пополнения запасов в течение времени поставки равнаp — d.
Уравнение издержек:
С = С1 + С2 + С3.
Для С1 имеем следующее. Спрос равен d товаров в год. Следовательно, еслиодна поставка содержит q — товаров, то за год нужно сделать /> поставок, а именно:
/>.
Для С2 имеем:
С2 = сd.
Для С3 (затраты на хранение запасов) имеем:
С3 = (средний уровеньзапасов) × h.
Средний уровень запасов находится следующим образом:
1. Максимальный уровень RT = (p — d)t,где t ‑ продолжительность поставки.
2. pt = q (количество товаров в одной поставке).
Отсюда:
(средний уровень запасов)=/>(максимальныйуровень запасов) = />.
Следовательно:
/>.
Оптимальный размер партии находится из уравнения:
/>.
Отсюда
/> .Модель, учитывающая штрафы
Рассмотрим третью модель, которая включает штрафы.
Считаем, что существуют периоды дефицита товаров (нулевые запасы), которыйпокрывается при последующих поставках, и штрафов за несвоевременную поставку.
Пусть по контракту предприятие должно поставить q единиц товара в течениекаждого промежутка времени продолжительностью L, за единицу времени поставляетсяd единиц товара (q = Ld). Значения q и L постоянны. Пусть далее в начале каждогопериода L предприятие делает запас единиц товара y
За несвоевременную поставку на предприятие налагается штраф, величина которогозависит от того, на сколько была задержана поставка. (Иногда выгоднее заплатитьштраф, чем расходовать средства на хранение запасов, превышающих величину у).
Задача управления в этом случае состоит в том, чтобы выбрать такое значениеу, которое ведет к минимизации всех затрат.
Рассмотрим издержки одного цикла. Общие издержки в модели пусть будут:
h — издержки хранения единицы товара за единицу времени;
p — затраты на штраф в расчете на единицу товара за один день отсрочки.
График изменения запасов будет:
/>
Находим издержки одного цикла.
Для С1 имеем следующее. Товары находятся на складе в течение периода АВ,средний уровень запасов за этот период равен у/2. Продолжительность периода АВ равнау/d. Отсюда:
/>.
Для С2. Штраф выплачивается за невыполнение поставок в течение периода />. Общее количество«товаро-дней», за которые налагается штраф, равно площади DBCD. Но
SDBCD = />.
Отсюда:
/>.
Cледовательно:
/>.
Оптимальное значение у находим из условия:
/>,
отсюда:
/>, />.
Таким образом, взяв значение у* в качестве уровня запасов в начале каждогоцикла, при условии, что невыполненные заявки в дальнейшем будут удовлетворены, сведемсуммарные расходы С к минимуму.
Тема 12. Методы экспертныхоценок
1. Основные понятия методов экспертных оценок.
2. Понятие множества неулучшаемых альтернатив.
3. Основные подходы к поиску предпочтительных экспертных оценок.
4. Основные этапы подготовки и проведения экспертных оценок.Краткое содержание темы
Как показывает опыт практической экономической деятельности, особенно в тойее части, которая связана с управлением в области экономики, где существенную рольиграет такой аспект действий как принятие решений, одного арсенала формально решаемыхзадач в большинстве случаев бывает недостаточно. В таких случаях приходится обращатьсяк компетентным специалистам, в интуиции которых сосредоточен иррациональный опытхозяйствования и управления и рационального познания экономики в виде формализованныхмоделей. Такие специалисты, которые в “совершенстве” владеют определенной проблемой,называются экспертами. Результатом их труда являются различного рода оценки, рекомендациии предложения. При привлечении значительного количества экспертов к выработке вариантоврешений встает задача обработки результатов работы экспертов. Здесь опять встаетпроблема использования формализованных методов — методов экспертных оценок.
Как правило, результат работы каждого эксперта представляется в виде альтернативы,поскольку безальтернативные результаты работы различных экспертов могут быть представленыв виде результата работы коллективного эксперта и каких-либо методов обработки такихрезультатов не требуется.
Таким образом, методы экспертных оценок можно рассматривать как методы преодоленияальтернатив.
Технология проведения экспертных оценок включает в себя три составляющие:
· интуитивно-логическийанализ;
· формированиеи выдача характеристик (собственно оценка, результат решения);
· обработкарезультатов экспертизы ‑ различных альтернатив.
Интуитивно-логический анализ строится на логическом мышлении (возможно наиспользовании формализованных экономико-математических моделей) и интуиции экспертов,их знании и опыте. В принципе это — индивидуальный процесс, в котором каждый экспертпроводит сравнительный анализ различных альтернатив решения, их количественные икачественные измерения (оценки) в разных условиях.
Формирование и выдача результатов экспертизы является, как правило, многокритериальнойзадачей, решение которой не сводится к достижению какой-либо одной цели.
На заключительном этапе, когда в общей экспертизе участвует не один эксперт(не одна группа экспертов), полученные от экспертов результаты используются дляобобщения и формирования результирующей характеристики проблемы явления, объектав виде обобщенной итоговой оценки. В этом процессе используется вся мощь методовэкспертных оценок. Именно на этом этапе осуществляется процесс преодоления альтернатив.
С преодолением альтернатив связаны два фундаментальных понятия:
· множестворазличных вариантов решений (альтернатив), обозначим его {X};
· принципвыбора, т.е. правила, по которым осуществляется выбор, обозначим его через Ф.
Задача экспертизы может быть записана в следующем виде:
/>, (12.1)
где {X*} — выбранные альтернативы.
В зависимости от степени формализации введенных понятий различают следующиетипы задач:
1. Задача оптимального выбора — если множество {X} однозначно определено,а принцип выбора Ф формализован (т.е. может быть описан, передан и результаты егоприменения к элементам из {X} не зависят от субъективных условий).
2. Задача выбора (просто) — если множество {X} однозначно определено, нопринцип выбора Ф не может быть формализован или просто фиксирован. Выбор зависитот того, кто и на основе какой информации его делает.
3. Общая задача выбора — если множество {X} не имеет определенных границ(может дополняться и видоизменяться), а принцип выбора Ф неформализуем или дажене фиксирован. В этом случае разные субъекты могут выбирать в качестве решения теальтернативы, которые другими субъектами и не рассматривались, а один и тот же субъектпри использовании одного и того же принципа выбора (неформализованного, но для негосущественного) может изменять свое решение при обнаружении им новой альтернативы.
С формальной точки зрения может показаться, что последняя задача являетсянастолько расплывчатой, что теряет смысл — т.е. не знаем из чего выбирать и чемруководствоваться при выборе. Однако именно эта задача с некоторыми естественнымиограничениями наиболее характерна для практики.
Каковы же эти естественные ограничения?
Во-первых, в реальной задаче, как правило, всегда существует так называемоеначальное множество альтернатив {X(0)}, на основе которого приступаютк принятию решения. В дальнейшем это множество изменяется, но можно считать, чтона любой момент процесса экспертизы мы имеем дело с фиксированным множеством {X(i)}:
/>.
Во-вторых, подразумевается, что альтернатива X из множества всех мыслимых альтернатив {X(M)} можетбыть оценена с точки зрения полезности включения ее в множество {X}. Это делаетсяпри помощи некоторого вспомогательного принципа выбора Ф(M). Чаще всегоэтот принцип неформализован. Таким образом, и само множество {X}, вообще говоря,является итогом экспертной оценки, которую можно представить в виде:
/>. (12.2)
В-третьих, считается, что существуют хотя бы неформализованные принципы выбора,относящиеся к принимаемому решению. Часто (но не всегда) есть уверенность, что применениетаких принципов различными субъектами дает пересекающиеся или в каком-то смыслеблизкие результаты.
Перечисленные условия дают уверенность в том, что общая задача выбора 3 можетбыть решена в той или иной степени обоснованно.
Практические пути решения не полностью определенных задач 3 и 2 состоят виспользовании для этой цели ряда задач с фиксированным, но меняющимся от задачик задаче множеством {X} и фиксированным (хотя необязательно формализованным) принципомвыбора Ф. Это происходит с применением ряда приемов. Первый из них — организацияитерационного процесса решения набора задач вида 1. Она состоит в начальном решенииодной или нескольких формализованных задач, анализе результатов их решения, назначенияизмененных множеств альтернатив {X} и измененных принципов выбора Ф, нового решениянабора задач и т.д. до получения удовлетворительного результата. Другой прием заключаетсяв решении ослабленного варианта задачи 1, когда принцип выбора формализован не полностью,а допускает участие экспертов, каждый из которых по-своему, обычно неформальнымобразом, фиксирует принцип Ф. В этом случае каждый из экспертов порождает свою задачутипа 1, а решение исходной задачи формируется на основе их решений. Следующей приемблизок к первому. Здесь задачам типов 3 или 2 сопоставляется некоторый аналог, выбранныйсреди задач типа 1, а полученное решение служит основой для неформального поискарешения требуемой задачи.
Таким образом, задача типа 1 является ядром в процессе решения других типовзадач.
Общепринятым принципом, который облегчает принятие решения, является переходот сравнения альтернатив в целом к сравнению их отдельных частей и свойств (аспектов,характеристик, признаков, преимуществ и т.п.). Основная идея такого перехода состоитв том, что в отношении отдельной части и (или) отдельного свойства существенно легческазать, какая из альтернатив предпочтительней.
Но сравнение по отдельным частям (свойствам) порождает серьезные проблемыобратного перехода к требуемому сравнению альтернатив в целом.
Выделение частей и/или свойств альтернатив является не чем иным, как декомпозициейальтернативы.
Сравнение альтернатив по отдельным частям (свойствам) может быть выполненоследующими способами:
1) на основе парного (реже группового) сравнения альтернатив по данному свойству;
2) на основе введения естественных числовых характеристик выделенного свойства;
3) на основе введения искусственных числовых характеристик выделенного свойства.
Рассмотрим эти способы сравнений.
Парное сравнение. Пусть для двух альтернатив X1 и X2из множества {X} можно произвести выбор наиболее предпочтительной по данному свойству.Способ выбора в общем случае не конкретизируется. Если он связан с использованиемчисловых характеристик, то такая ситуация относится к способу (2) или (3). Возникаетвопрос: «Существует ли объективный способ выбора, не связанный с числами?» С практическойточки зрения можем считать вполне объективными и не основанными на числовых характеристикахтакие утверждения: “Этот вариант размещения пунктов потребления более предпочтителендля развертывания широкой торговли”, “Этот человек более удачно справится с поставленнойзадачей” и т.п.
С формальной точки зрения для альтернатив X1 и X2 из{X} вводится бинарная операция сравнения по признаку (свойству) R. Запись этогособытия можно представить в виде:
X1RX2, (12.3)
что означает: альтернатива X1 предпочтительней (или “не хуже”)альтернативы X2 по признаку R. Указанная операция может быть примененакак к любой паре (X1, X2) из {X}´{X}, так и не ко всем из них. В последнемслучае допускается, что относительно некоторых пар нельзя сделать выбор, как говорится,элементы множества {X} только частично сравнимы по признаку R.
Для операции R естественной является аксиома транзитивности, которая заключаетсяв том, что из X1RX2 и X2RX3 следуетX1RX3.
На основе бинарного сравнения может быть выполнена специальная операция ранжирования(упорядочивания). Результатом такой операции является то, что альтернативы в зависимостиот их свойства R располагаются в определенном порядке: от наиболее до наименее предпочтительной.Математически эта операция эквивалентна определенной перестановке.
Введение числовых характеристик. Сравнение элементов на основе сопоставленияим числа представляется наиболее аргументированным способом выбора. Необходима толькоуверенность, что выполненное сопоставление объективно. Как правило, это имеет место,если числовая характеристика обладает физическим смыслом. Можно утверждать, чтов процессе экспертной оценки следует стремиться довести декомпозицию экспертируемогообъекта до уровней, на которых возможны числовые оценки.
Свойства, для которых существуют объективные численные характеристики, принятоназывать критериями.
Таким образом, получение набора критериев — наилучший итог процесса декомпозиции.Он настолько привлекателен, что к его аналогу прибегают и тогда, когда естественныечисловые характеристики отсутствуют. В этом случае вводятся искусственные оценкитипа баллов. Они проставляются экспертами, каждый из которых может исходить из своегонеформального принципа выбора. Этим решается задача количественной оценки качественныхсторон явления или проблемы. Примерами таких оценок могут служить: коэффициент трудовогоучастия, разрядная сетка рабочих специальностей, процент износа механизма.
Искусственные оценки практически непрерывно переходят в естественные. Однаков ряде случаев процесс перехода осложнен, и тогда эксперт обладает определеннойсвободой выбора. Это имеет место при присвоении рабочих разрядов, назначении коэффициентовв эмпирически подобранные зависимости, определении отдельных внутренних параметрови т.п.
Дополнительным приемом, который в ряде случаев облегчает все приведенныевыше способы сравнения, является распределение элементов по подмножествам. Тогдалюбая альтернатива X из {X} в целом или по своему свойству R относится к одномуиз фиксированных подмножеств {X1}, {X2},…. Такое распределениеназывается задачей классификации и может как сводиться к перечисленным способамсравнения, так и быть самостоятельной задачей. Частным случаем классификации являетсяделение свойств альтернатив по степени важности в данной задаче. Смысл этого приемасостоит в сужении числа свойств, принимаемых во внимание в первую очередь.
Процесс декомпозиции альтернативы является мощным орудием анализа проблемы,оценки ее отдельных свойств. Однако, смысл любой экспертизы заключается в оценкепроблемы в целом, т.е. в обобщенной оценке. Процесс обобщения отдельных экспертныхоценок, полученных на этапе декомпозиции альтернативы, носит название композицииоценок и сравнений. Сразу следует отметить, что непростой процесс анализа альтернативына этапе декомпозиции намного усложняется на этапе композиции.
Множество неулучшаемых альтернатив получило название множества Парето.
Ясно, что точки, не принадлежащие множеству Парето, не могут претендоватьна то, чтобы считаться лучшей альтернативой.
Выделение множества Парето — это только первый шаг в сравнении альтернатив.Вообще можно ограничиться только этим шагом и считать лучшими все те альтернативы,которые попали в это множество. Однако в большинстве случаев проведения экспертизтребуется в итоге выбрать только одну альтернативу. Как действовать на множествеПарето?
Приемов такого выбора, основанных на столь же естественных предположениях,которые привели к выделению множества Парето, к сожалению не существует. Здесь частоиспользуются специфические, порой спорные приемы.
Выше рассмотрены основные методы экспертных оценок, которые могут применятьсяв ходе проведения экспертиз и обработки их результатов. Но, как организуется экспертиза?Формы организации экспертизы могут быть достаточно разнообразными и многочисленнымив зависимости от условий проведения экспертизы и контингента привлекаемых экспертов.Классические формы работы с экспертами — это заполнение анкет (таблиц), интервью,запрос аналитического отчета.
Первая из этих форм является наиболее распространенной. В вопросники какправило включаются простые вопросы, которые для ответа не нужно разбивать на отдельныечасти. Интервью предпочтительнее анкет, если оно проводится высококвалифицированнымспециалистом, способным подстроиться под интервьюируемого, помочь ему выбрать болееобоснованные ответы, но одновременно не привнести в них свое мнение.
Следует иметь в виду, что человек более обосновано приводит качественныеответы, чем количественные.
Экспертизы различаются и по форме взаимодействия экспертов. Обмен мнениямиможет быть свободным, регламентированным и недопустимым. Все эти способы имеют своипреимущества и недостатки.
При свободном общении ряд экспертов может доминировать над другими, и чье-томнение может оказаться неучтенным.
Регламентированное общение требует более сложной организации; его известныйвид — это метод “мозговой атаки”, когда сначала мнения высказываются без обсужденияи только через некоторое время дискутируются, как правило, под руководством хорошоподготовленного ведущего.
Изолированная работа с экспертами чревата попаданием в дальнейшую обработкуискаженных или просто неверных оценок, которые могли бы быть выявлены и измененыпри свободном или регламентированном способе.
Причинами неудовлетворительных ответов могут быть нарушения целого ряда требованийк экспертам — от неполной компетентности и предвзятости до неспособности решатьнестандартные задачи и предвидеть неочевидные последствия.
Предполагается, что правильно обработанное коллективное мнение экспертовболее достоверно и надежно, чем индивидуальные мнения отдельных экспертов, и чтоистинная величина изучаемого явления находится внутри диапазона оценок группы экспертов.Надежность экспертных оценок определяется в первую очередь подбором специалистов-экспертов,их информированностью в изучаемых проблемах, а также возможностью математико-статистическойобработки полученных результатов экспертизы.
В подборе экспертов могут быть применены разные подходы, наиболее надежнымиз них является статистический подход.
Статистический подход к подбору экспертов состоит в проверке эрудиции и аналитическихспособностей эксперта, а также проверки точности его прошлых оценок.
Интересной реализацией получения обобщенной экспертной оценки, учитывающейуказанные особенности организации и проведения экспертиз, является метод Дельфы.
Этот метод представляет ряд последовательно осуществляемых процедур, направленныхна выявление группового мнения по той или иной проблеме. Метод получил наименованиепо названию города Дельфы, ставшего известным из-за прорицателей-оракулов, жившихв нем и предсказывающих будущее. Пророчества обнародовались после тщательного обсужденияна совете дельфийских мудрецов.
Метод Дельфы представляет обобщение оценок экспертов, касающихся прежде всегоперспектив развития. Особенность метода состоит в последовательном анонимном индивидуальномопросе экспертов, исключающем их непосредственный контакт для уменьшения групповоговлияния, возникающего при совместной работе экспертов и состоящего в приспособлениик мнению большинства. Работа проводится в несколько этапов. Результаты первого этапаподвергаются статистической обработке. Выявляются преобладающие суждения экспертови сближаются их точки зрения. Всех экспертов, оценки которых находятся в границахсогласованности, знакомят с обоснованиями причин расхождений суждений тех экспертов,оценки которых выходят за указанные границы. Эксперт может изменить свое суждение.Для выявления этого проводится второй тур и т. д.
Метод Дельфы дает возможность улучшить простое усреднение оценок экспертов.
Итак, теперь можно перечислить основные этапы подготовки и проведения экспертизы.Они включают:
· постановкузадачи (проблемы), подлежащей экспертизе;
· подбори выбор экспертов;
· выполнениеэкспертизы;
· получениеобобщенной экспертной оценки;
· формированиеи оформление результатов экспертизы.
Для примера представим название некоторых задач и проблем, в решении которыхприменяются методы экспертных оценок.
Это:
· распределениеразличных видов ресурсов с установлением приоритетности;
· установлениеноменклатуры подлежащих выполнению работ для достижения определенных целей в условияхограничений по различным ресурсам;
· установлениеудельных ресурсных затрат на выполнение каких-либо работ, норм расхода материалов,нормативной трудоемкости изготовления изделия и его составляющих, стоимости отдельныхэтапов научно-исследовательских и опытно-конструкторских работ;
· установлениевозможных и допустимых границ колебания экономических показателей;
· установлениепараметров календарно-плановых нормативов, размеров партий запуска-выпуска изделий(деталей), величины заделов;
· определениеперспективных направлений развития производственной системы, организационно-функциональнойструктуры;
· многокритериальнаяоценка деятельности предприятия;
· определениепоследовательности выполнения работ;
· научно-техническоеи экономическое прогнозирование.
Процесс подготовки и проведения экспертизы сопряжен с процессом обработкиогромных объемов информации с использованием громадного арсенала экономико-математическихсредств, методов и моделей. Поэтому получение более достоверных и надежных результатовэкспертизы на современном этапе развития программно-технических средств не мыслимбез привлечения в процесс экспертирования современных электронно-вычислительныхкомплексов.
Появление интерактивных режимов функционирования в программно-технологическихкомплексах дает прекрасную возможность оптимально сочетать неформализуемую интуитивнуюдеятельность, присущую человеку, с неограниченными возможностями ЭВМ по решениюформализованных задач.
В настоящее время разработан достаточно представительный набор программныхсредств типа экспертных и логико-расчетных систем (оболочек), позволяющих за приемлемообозримое время настроиться на решаемый класс экспертных задач, доведя их до уровня“дружественного” общения между человеком и машиной. Существенной особенностью такихсистем является так называемая база знаний, построенная на основе формализуемойчасти труда экспертов по определенным и конкретным проблемам. Некоторые из этихсистем доведены до такого “совершенства”, что позволяют проводить экспертные оценкибез участия экспертов-специалистов, которые могут привлекаться только в отдельныхслучаях, когда система начинает давать значительные сбои.
ДОПОЛНИТЕЛЬНАЯ ТЕМАТИКА Тема А. Элементы теории вероятности
1. Понятие вероятности. Общие свойствавероятности.
2. Основные формулы теории вероятности.
3. Понятие случайной величины. Дискретнаяи непрерывная случайная величина.
4. Понятие распределения случайной величины.Основные законы распределения.Краткое содержание темы
Изложение содержания данной темы в настоящей работе не представляется целесообразным,так как его можно без труда найти в широком круге литературных источников, в томчисле тех, которые перечислены в данной работе. Тема Б. Нелинейное программирование
1. Постановка общей задачи нелинейного программирования.
2. Метод множителей Лагранжа.
3. Выпуклое программирование.
4. Градиентные методы.
5. Метод штрафных функций.Краткое содержание темы
Постановка общей задачи нелинейного программирования состоит в следующем.Определить максимум (минимум) значения функции:
f(x1, x2,..., xn) (Б.1)
при условии, что переменные удовлетворяют соотношениям:
/>, (Б.2)
где, f и gi некоторые известные функции, bi — заданныечисла.
Решение этой задачи X * = (x1*, x2*, ..., xn*),удовлетворяющее (Б.1) и (Б.2), такое, что для любого другого X = (x1,x2, ..., xn), удовлетворяющего (Б.2), имеем:
f(x1*, x2*,..., xn*) ³f(x1, x2, ..., xn) — для задачи максимизации;
f(x1*, x2*,..., xn*) £f(x1, x2, ..., xn) — для задачи минимизации.
Соотношения (Б.2) называются системой ограничений. Условия неотрицательностипеременных могут быть заданы непосредственно. В евклидовом пространстве E n(Б.2) определяет область допустимых решений поставленной задачи (в отличие от задачлинейного программирования эта область может быть не выпуклой).
Если область допустимых решений определена, то нахождение решения задачи(Б.1)-(Б.2) сводится к определению такой точки этой области, через которую проходитгиперповерхность наивысшего (наинизшего) уровня: f(x1, x2,..., xn) = h.
Эта точка может быть как на границе, так и внутри области.
Процесс решения задачи в геометрической интерпретации включает этапы:
· определениеобласти допустимых решений, соответствующих (Б.2) (если она пуста, то решений задачи- нет);
· построениегиперповерхности f(x1, x2, ..., xn) = h;
· определениегиперповерхности наивысшего (наинизшего) уровня или установление неразрешимостизадачи из-за неограниченности (Б.1) сверху (снизу) на множестве допустимых решений;
· нахождениеточки области допустимых решений, через которую проходит гиперповерхность наивысшего(наинизшего) уровня и определение в ней значения (Б.1). Метод множителей Лагранжа
Общая постановка задачи состоит в нахождении максимума (минимума) функции:f(x1, x2, ..., xn) при условии: g(x1,x2,...,xn) = bi, i = 1, 2, ..., m.
Условия неотрицательности xj могут отсутствовать. Имеем задачуна условный экстремум — классическая задача оптимизации.
Задача решается следующим образом. Вводят набор переменных li (i = 1, 2, ...,m) — множителей Лагранжа и составляют функцию:
/>.
Далее определяют частные производные:
/> (j = 1, 2, ..., n) и />, (i = 1, 2, ...,m).
На следующем шаге рассматривают систему n + m уравнений:
/>
Любое решение этой системы определяет точку />, в которой может иметь место экстремумфункции f (x1, x2, ..., xn). Таким образом, разрешивпостроенную систему, определяют все точки, в которых функция f может иметь экстремум.Дальнейшее исследование идет как в случае безусловного экстремума.
Итак, этапы решения задачи нелинейного программирования методом множителейЛагранжа заключаются в следующем:
1.Составляют функцию Лагранжа.
2.Находят частные производные функции Лагранжа по xjи li и приравниваютих 0.
3.Решая полученную систему, находят точки, в которыхцелевая функция задачи может иметь экстремум.
4.Среди точек, подозрительных на экстремум, находятточки, в которых достигается экстремум, вычисляют значения f(x1, x2,...,xn)в этих точках и среди них выбирают те, которые удовлетворяют условиям задачи.Выпуклое программирование
Суть общей постановки задачи состоит в определении максимального (минимального)значения функции:
f(x1, x2,...,xn)
при условиях:
gi(x1,x2, ..., xn) £ bi (i = 1, 2, ...,m), xj ³0 (j = 1, 2, ..., n).
Универсальных методов решения поставленной задачи в общем виде не существует.Однако, при определенных ограничениях решение этой задачи может быть найдено.
Несколько определений.
Функция f(x1, x2, ..., xn) на выпуклом множествеX называется выпуклой, если для любых двух точек X2 и X1 изXи любого 0 £l £ 1, выполнено соотношение:
f[lX2 + (1 — l)X1] ³ lf(X2) + (1 — l)f(X1).
Множество допустимых решений удовлетворяет условию регулярности, если существуетхотя бы одна точка Xi этой области такая, что gk(Xi)
Задача выпуклого программирования возникает, если функция f является вогнутой(выпуклой), а gi — выпуклы.
Любой локальный максимум (минимум) является глобальным максимумом (минимумом).Наиболее характерным методом решения задач выпуклого программирования является методмножителей Лагранжа. При этом точка (X0, L0) называется седловой точкой функцииЛагранжа, если:
F(x1, x2,..., xn, />) £ F(/>)£
£ F(/>), для всех xj³ 0 и li ³ 0.
Для задачи выпуклого программирования, множество допустимых решений которойобладает свойством регулярности, точка X0= (/>) является оптимальным решениемтогда, когда существует такой вектор L0= (/>), что точка (X0, L0) является седловойточкой функции Лагранжа, построенной для исходной задачи.
Для задачи определения максимума, условиями седловой точки будут:
/>
(частные производные берутся в седловой точке).
Для задачи нахождения минимума седловая точка определяется соотношениями:
F(/>) £ F(/>)£
£ F(/>).
Условия седловой точки в этой задаче представляются в виде:
/>,
/>.Градиентные методы
Градиентными методами можно найти решение любой задачи нелинейного программирования.Однако в общем случае эти методы позволяют найти точку локального экстремума. Наиболеецелесообразным является использование этих методов для решения задач выпуклого программирования,где всякий локальный экстремум является глобальным.
Суть метода заключается в том, что начиная от некоторой точки X(k)осуществляется последовательный переход к другим точкам до тех пор, пока не будетполучено приемлемого решения исходной задачи. Методы можно разделить на две группы.
Первая группа, когда исследуемые точки не выходят за пределы области допустимыхрешений (здесь используется метод Франка-Вулфа).
Вторая группа, когда эти точки не обязательно входят только в область допустимыхрешений, однако в итерационном процессе такие точки будут. (Здесь используется методштрафных функций и метод Эрроу-Гурвица).
Нахождение решения идет итерационным процессом до тех пор, пока градиентфункции f(x1, x2, ..., xn) в очередной точке X(k+1)не станет равным 0, или пока | f(X(k+1)) — f(X(k)) |Метод Франка-Вулфа
Найти максимум вогнутой функции: f(x1, x2, ..., xn),при условии:
/>.
Здесь имеем линейные неравенства. Эта особенность является основой для заменыв окрестности исследуемой точки нелинейной функции линейной, тогда решение исходнойзадачи сводится к последовательному решению ряда задач линейного программирования.
Начинается процесс решения с определения точки, принадлежащей области допустимыхрешений. Пусть это точка X(k). В ней вычисляют градиент функции f:
Ñf(X(k)) =/>
и строят линейную функцию:
F = />.
Находят максимум функции F при сформулированных ограничениях. Пусть решениеэтой задачи Z(k). Тогда за новое допустимое решение принимают:
X(k+1) = X(k) + lk(Z(k) — X(k)),
где lk‑ некоторое число, называемое шагом вычислений (0 £ lk £ 1). Число lk — произвольное и выбирают его так, чтобызначение функции в точке X(k+1), зависящее от lk, было максимальным.Для этого надо найти решение уравнения /> и выбрать его наименьший корень. Есликорни уравнения больше 1, то берется lk = 1. Затем определяют X(k+1) и f(X(k+1))и выясняют необходимость перехода к точке X(k+2). Если такая необходимостьимеется, то в точке X(k+1) вычисляют градиент целевой функции и переходятк соответствующей задаче линейного программирования и решают ее. Определяют координатыточки X(k+2) и необходимость дальнейших вычислений. После конечного числашагов получают с необходимой точностью решение исходной задачи.
Итак, этапы решения задачи методом Франка-Вулфа заключаются в следующем:
1. Определяют одно из допустимых решений.
2. Находят градиент функции f в точке допустимого решения.
3. Строят функцию F и находят ее максимальное значение при условиях исходнойзадачи.
4. Определяют шаг вычислений.
5. По формуле X(k+1) = X(k) + lk(Z(k) — X(k)) находят следующее допустимое решение.
Проверяют необходимость перехода к следующему допустимому решению. В случаенеобходимости переходят к этапу 2, если такой необходимости нет, то приемлемое решениенайдено.Метод штрафных функций
Пусть имеем вогнутую функцию f(x1, x2, ..., xn).Необходимо найти максимум этой функции при условиях: gi(x1,x2, ..., xn) £ bi, (i = 1, 2, ...,m), xj ³ 0, где gi — выпуклые функции.
Строится функция: F (x1, x2, ..., xn) =f (x1, x2, ..., xn)+H (x1, x2,..., xn), где функция H(x1, x2, ..., xn)определяется системой ограничений и называется штрафной функцией. Она может бытьпостроена многими способами. Чаще всего эта функция строится в виде:
/>, где
/> ai ‑ весовыекоэффициенты,
qi = bi — gi .
Используя H, последовательно переходят от одной точки к другой до тех пор,пока получится приемлемое решение. При этом координаты последующей точки находятпо формуле:
/> (Б.3)
Из (Б.3) следует, что если предыдущая точка находится в области допустимыхрешений, то второе слагаемое в квадратных скобках равно 0, и переход к последующейточке определяется только градиентом целевой функции. Если же предыдущая точка непринадлежит области допустимых решений, то за счет указанного слагаемого на последующихитерациях достигается возвращение в область допустимых решений. При этом, чем меньшеi, тем быстреенаходится приемлемое решение, но точность определения решения снижается. Поэтомув начале i берутмалым, постепенно увеличивая.
Итак, процесс решения включает этапы:
1. Определяют исходное допустимое решение.
2. Выбирают шаг вычислений.
3. Находят по всем переменным частные производные от целевой функции и функций,определяющих область допустимых решений задачи.
4. По (Б.3) определяют координаты точки — возможное новое решение.
5. Проверяют, удовлетворяют ли координаты найденной точки системе ограниченийзадачи. Если не удовлетворяют, то переходят к следующему этапу. Если координатынайденной точки определяют допустимое решение задачи, то исследуют необходимостьперехода к последующему решению. Если такой переход необходим, то переходят к пункту2, иначе решение найдено.
6. Устанавливаются значения весовых коэффициентов и переходят к этапу 4.