Международный институт
экономики и права
МАТЕМАТИЧЕСКИЕ МЕТОДЫ ЭКОНОМИЧЕСКИХ ИССЛЕДОВАНИЙ
Контрольная работа
Тема 1. Системы, системный подход, системный анализ. Основные термины, определения, технологии
1. Понятие системы.
2. Системный подход, принципы системного подхода.
3. Системный анализ: постановка задачи, декомпозиция, композиция системы, исследование системы.
4. Структура системы.
Таким образом, для системы характерно наличие:
совокупности элементов;
взаимосвязи элементов через структуру;
взаимодействия;
целенаправленности.
Элемент системы - это структурная единица системы, не подлежащая делению в данных условиях рассмотрения системы.
Основным свойством системы является то, что она обладает характеристиками, принципиально отличными от характеристик составляющих ее элементов. Только интегративное взаимодействие ее элементов позволяет системе достигнуть уникальных свойств.
Системный подход - это конкретно-научный метод диалектической методологии, имеющей общенаучное значение. Методология изучения системы как единого целого, состоящего из отдельных частей, с различных точек зрения формализации позволяет сформулировать следующие принципы системного подхода.
Принцип конечной цели: абсолютный приоритет конечной (глобальной ) цели.
Принцип единства: совместное рассмотрение системы как целого и как совокупности частей (элементов).
Принцип связности: рассмотрение любой части совместно с ее связями с окружением.
Принцип модульного построения: выделение модулей (подсистем) в системе и рассмотрение ее как совокупность подсистем.
Принцип иерархии: выделение иерархии частей (элементов) и (или) их ранжирование.
Принцип функциональности: совместное рассмотрение структуры и функций с приоритетом функций над структурой.
Принцип развития: учет изменяемости системы, ее способности к развитию, расширению, замене частей, накапливанию информации.
Принцип децентрализации: сочетание в принимаемых решениях управления централизации и децентрализации.
Принцип неопределенности: учет неопределенностей и случайностей в системе.
Совокупность приемов и методов для изучения сложных систем представляет собой системный анализ. Системный анализ - это средство и технология системного подхода.
Рассмотрим основные этапы системного анализа.
1. Постановка задачи. Она включает:
определение объекта исследования;
постановку целей;
задание критериев для изучения объекта и управления им.
Этап слабоформализуем. Успех постановки задачи определяется в основном искусством и опытом системного аналитика, глубиной понимания им поставленной проблемы.
2. Структуризация и очертание границ (декомпозиция) изучаемой системы. Она включает:
разбиение совокупности всех объектов и процессов, отвечающих поставленной цели, на два класса: собственно исследуемую систему и внешнюю среду;
изучение процессов взаимодействия объектов (элементов) системы и внешней среды.
Этап слабоформализуем. Он основан на искусстве и опыте проводящих этот этап специалистов.
Разбиение объектов и процессов осуществляется в результате последовательного перебора и включения в систему объектов и процессов, оказывающих заметное влияние на процесс достижения поставленной цели.
3. Составление модели изучаемой системы (как правило, математической).
Параметризация - первый этап этого процесса. Осуществляется описание элементов системы и элементарных воздействий с помощью тех или иных параметров. Параметры могут принимать как непрерывные, так и дискретные числовые значения, а также значения в виде признаков, которые не могут быть охарактеризованы с помощью обычных числовых параметров, а различаются качественно (например: теплый, холодный, плохой, хороший).
Установление различного рода зависимостей между введенными параметрами. Характер этих зависимостей может быть любым. Количественные (числовые) параметры связываются зависимостями типа систем уравнений (обыкновенных алгебраических или дифференциальных). Качественные параметры связываются зависимостями типа таблиц. В общем случае могут встречаться комбинации зависимостей различных типов.
Зависимости между параметрами в системах задаются в общем случае не простыми формулами, а произвольными алгоритмами с использованием любых средств как количественных, так и описательных.
Выделение подсистем и установление их иерархии преследует цель не только упрощения описания системы. Этот процесс дает возможность осуществлять уточнение первоначальной структуризации (разбиения на элементы) и параметризации системы.
Результатом этого этапа является законченная математическая модель системы, описанная на формальном языке.
4. Исследование полученной (построенной) системы - четвертый этап системного анализа.
Первая задача этапа - прогноз развития изучаемой системы.
Для решения этой задачи задают различные предположения о внешних воздействиях на систему в течение рассматриваемого периода и с помощью модели определяют распределение значений, характеризующих систему параметров для любых фиксированных моментов времени.
Термин “прогноз развития” подчеркивает то обстоятельство, что для системы нельзя определить единственную траекторию развития, можно определить лишь множество таких траекторий. При этом каждая траектория может реализоваться в действительности лишь с той или иной степенью вероятности.
Получив прогноз развития изучаемой системы, производят анализ его результатов на соответствие заданным целям и критериям и вырабатывают предложения по улучшению управления и т.д., пока не получится удовлетворяющий результат.
Под структурой системы понимается организация системы из отдельных элементов с их взаимосвязями, которые определяются распределением функций и целей, выполняемых системой.
Структура - это способ организации целого из составных частей .
Эффективность структуры определяется качеством, значением, формой и содержанием ее составных частей, а также местом, которое занимают они в целом, и существующими между ними отношениями.
По принципам управления и подчиненности различают структуры (системы): централизованные, децентрализованные, смешанные.
Централизованная система: задания отдельным элементам системы выдаются лишь одним элементом более высокого уровня.
Децентрализованная система: решения отдельными элементами системы принимаются независимо и не корректируются системой более высокого уровня.
В смешанной системе некоторые функции или этапы выполняются по централизованной системе, а другие - по децентрализованной.
По числу уровней иерархии различают системы: одноуровневые, многоуровневые.
Многоуровневые могут быть однородными и неоднородными.
По выполняемым функциям и целевому назначению различают системы: физические, экономические, биологические, общественные, информационные и т.д.
В зависимости от числа элементов системы и связей между ними различают системы фиксированной (жесткой) и изменяемой (управляемой или переменной) структуры.
По принципам разбиения систем на подсистемы различают структуры систем, в которых элементы объединяются по функциональному и (или) объектному принципам. При объектном разбиении различают структуры отраслевых систем, региональных систем, территориальных систем.
Тема 2. Экономико-математические методы. Состав, структура, направленность, классификация
1. Методы математической статистики.
2. Методы исследования операций и оптимизации.
3. Кибернетические методы.
4. Методы экспертных оценок.
расчет и интерпретация статистических характеристик экономических процессов;
регрессионный и корреляционный анализ;
планирование эксперимента.
Следующим классом экономико-математических методов являются методы исследования операций и оптимизации. Это наиболее разработанная группа экономико-математических методов, позволяющих осуществить формализованный анализ экономических систем и процессов.
Среди методов исследования операций и оптимизации различают следующие направления:
методы математического программирования;
теорию массового обслуживания и расписаний;
сетевые методы планирования и управления;
теорию игр;
методы эвристики.
Основными направлениями методов кибернетики в экономике являются следующие:
методы распознавания образов;
методы классификации;
методы АСУ;
методы теории автоматического регулирования;
имитационное моделирование.
Наконец, одним из направлений экономико-математических методов являются методы экспертных оценок. Эти методы используются для исследования сложных слабоформализуемых систем. Появление мощных программно-математических средств типа экспертных оболочек позволяет надеяться, что в недалеком будущем метод экспертных оценок станет преобладающим, вобрав в себя все лучшие качества других экономико-математических методов, так как основная цель практически всех экономических исследований сводится к оценке текущего состояния исследуемого объекта (процесса) и выдаче прогнозов по его дальнейшему развитию.
Тема 3. Межотраслевой баланс. Состав, структура, схема
1. Состав, структура и схема межотраслевого баланса.
2. Задача и матрица Леонтьева.
, j = 1, 2, ..., n, (3.1)
где - общее промышленное и производственное потребление, далее:
,
где vj - непроизводственное потребление и накопление.
В принципе формула (3.1) представляет математическую модель межотраслевого баланса в сфере потребления.
Отрасль можно анализировать не только с точки зрения распределения ее продукции, но и с точки зрения затрат на производство в данной отрасли. Пусть в этом случае в i-ой отрасли имеются затраты на заработную плату zi , кроме этого в балансе необходимо предусмотреть доход i (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)-1 v . (3.3)
Матрица A называется продуктивной, если матрица (положительная). Нормой матрицы A назовем максимум сумм элементов ее столбцов. Она обозначается ||A||. Можно доказать, что если A положительная матрица и , причем хотя бы для одного столбца сумма его элементов строго меньше 1, то A будет продуктивной матрицей.
Тема 4. Задачи на смеси
1. Постановка задачи на смеси.
2. Графический метод решения.
3. Общий алгоритм решения задач линейного программирования.
_ целевая функция.
Следовательно, в задаче идет речь о достижении максимума целевой функции 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. Практические рекомендации по постановке задач ДП.
от конца к началу - поиск условных оптимальных управлений и выигрышей за оставшийся "хвост" процесса;
от начала к концу - осуществляется "чтение" уже готовых рекомендаций и поиск безусловного оптимального управления x*, состоящего из оптимальных шаговых управлений x1*, x2*, ..., xm*.
.
,
а условный оптимальный выигрыш:
.
Задаваясь последовательностью значений 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, выделяем второму предприятию оптимальное количество средств:
и т.д. до конца.
. (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 = i(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. Расчет сетевых моделей.
Пусть далее 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 = - . Далее положим 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. Подход к решению задач теории игр.
|
B1 |
B2 |
... |
Bj |
... |
Bn |
||
|
A1 |
a11 |
a12 |
... |
a1j |
a1n |
||
|
A2 |
a21 |
a22 |
... |
a2j |
a2n |
||
|
... |
... |
... |
... |
... |
... |
... |
|
|
Ai |
ai1 |
ai2 |
... |
aij |
ain |
||
|
... |
... |
... |
... |
... |
... |
... |
|
|
Am |
am1 |
am2 |
... |
amj |
amn |
||
Аналогичным образом определяется минимальный проигрыш (который может быть в действительности и выигрышем) для второго игрока:
.
Величина ? называется верхней ценой игры или минимаксом. Ей соответствует минимаксная стратегия второго игрока.
Имеет место неравенство: .
При ? < ? первый игрок может существенно увеличить свой средний выигрыш по сравнению с ?, если он будет пользоваться не чистой (одной единственной стратегией), а так называемой смешанной стратегией.
Смешанная стратегия С состоит в том, что при повторении игры происходит случайный выбор стратегий из некоторого множества смешиваемых стратегий и для каждой смешиваемой стратегии указывается вероятность ее выбора.
Известно, что для любой КПИНС существует пара оптимальных стратегий (вообще говоря смешанных).
Свойство оптимальности означает, что любое отступление одного из игроков от оптимальной стратегии (при условии, что второй игрок продолжает придерживаться своей оптимальной стратегии) при многократном повторении игры может только уменьшать его средний выигрыш (увеличить средний проигрыш).
Величина выигрыша (может быть, отрицательного) первого игрока при пользовании парой оптимальных стратегий называется ценой игры и обозначается ?.
Цена игры заключена между нижней и верхней ценой игры:
.
Стратегии, которые смешиваются для получения оптимальной стратегии, будем называть полезными.
Решить игру - это значит найти пару оптимальных стратегий и цену игры. Решение игры обладает одним важным свойством: если один из игроков использует свою оптимальную стратегию, а другой смешивает свои полезные стратегии в любых пропорциях (не обязательно оптимальных), то средний выигрыш продолжает оставаться равным цене игры. При этом, правда, как при любых отступлениях от оптимальной стратегии, соответствующее изменение стратегии противником может привести к увеличению его среднего выигрыша.
Известно, что у игры mn число полезных стратегий с каждой стороны не превосходит минимального из чисел m и n.
В области чистых стратегий решение может быть получено непосредственно. Если же решение нужно искать в области смешанных стратегий , то в общем случае mn матрицы применяется следующий прием.
Считая все m стратегий первого игрока полезными, определяют вероятность их применения в смешанной оптимальной стратегии (если какая-то стратегия в действительности бесполезна, то соответствующая вероятность обратится в нуль). Пусть искомые вероятности обозначаются , а цена игры (пока неизвестная) - ?.
Так как при оптимальной стратегии средний выигрыш первого игрока не меньше ??при любой стратегии противника, то ищем n неравенств:
Вводим новые неизвестные:
.
Чтобы исключить деление на нуль, можно всегда добиться . Для этой цели достаточно ко всем элементам матрицы прибавить одно и тоже положительное число с и все ее элементы сделать положительными. Эта операция увеличит цену игры на с, но не изменит искомых оптимальных стратегий.
Так как
= 1, то .
Таким образом, имеем систему неравенств:
, (8.1)
где все .
Так как цель оптимальной стратегии - максимизация выигрыша, то при ее достижении линейная функция:
должна обратиться в минимум. Итак, оптимальная стратегия первого игрока (т.е. набор вероятностей ) находятся в результате минимизации функции:
при , удовлетворяющих системе неравенств (8.1).
Таким образом, получили задачу линейного программирования. Методы решения таких задач известны. В результате ее решения находим не только оптимальную стратегию первого игрока, но и цену игры .
Зная цену игры, оптимальную стратегию (а1, а2, ..., аn) второго игрока можно находить уже без решения задачи линейного программирования (хотя оптимальную стратегию второго игрока можно находить и через решение этой задачи, если поменять игроков местами). Для этого выбирается n-1 полезных стратегий первого игрока (имея возможность менять местами игроков можно считать, что) и для каждой из них записывается средний выигрыш, который при этом должен быть обязательно равен цене игры . Например, если для первого игрока полезна стратегия Аi, то ей соответствует уравнение:
.
Кроме этого имеется еще одно уравнение:
.
Всего имеем n уравнений для n величин q1, q2, ..., qn.
Игровые методы могут применяться для изучения ситуаций, которые не являются в строгом смысле слова конструктивными. Например, ситуации, где вторым игроком является природа.
Тема 9. Имитационное моделирование
1. Понятие имитационного моделирования.
2. Общая постановка задачи имитационного моделирования.
3. Метод Монте-Карло.
Как правило, пятый и шестой этапы наиболее просто осуществимы на ЭВМ, поэтому имитационные модели обычно реализуются с использованием специализированных программ, описывающих функционирование отдельных блоков и правила взаимодействия между ними.
Использование реализаций случайных величин требует многократного повторения экспериментов с моделью с последующим статистическим анализом полученных результатов.
,
где 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 < a. Рассмотрим каждый из этих случаев.
1) Случай b > a. Это значит, что скорость обслуживания 1/b меньше, чем скорость поступления требований 1/a, т.е. требования обслуживаются и покидают систему медленнее, чем прибывают. Следовательно, в этом случае будет образовываться очередь и она будет постоянно возрастать.
2) Случай b = a. Если в очереди нет требований, то первое поступившее требование сразу начнет обслуживаться. Его обслуживание закончится в тот же самый момент, в который поступит на обслуживание следующее требование. Следовательно, требований, ожидающих обслуживания, не будет.
Если же первоначально имеется очередь, то ее длина будет оставаться постоянной.
3) Случай b < a. Это значит, что скорость обслуживания больше, чем скорость поступления требований. Следовательно, какое бы ни было начальное число ожидающих обслуживания требований, длина очереди будет сокращаться до 1 или 0.
Пусть в начале процесса число требований в очереди 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)), найдет систему обслуживания пустой или только что освободившейся. Такому требованию не придется стоять в очереди. Требование, поступившее в момент времени tT-b, найдет впереди себя требований, стоящих в очереди, причем первое из них в этот же момент поступит на обслуживающее устройство. Эта величина получается следующим образом:
(начальная (число требований, обслужен- (число поступ-
очередь) - ных к моменту времени t) + лений)
r - + .
Таким образом, время ожидания W(t) для рассматриваемого требования может быть выражено формулой:
. (10.4)
Рассмотрим i-е требование в начальной очереди (0 <i r), тогда впереди его будет (i - 1) требований, для обслуживания которых потребуется (i - 1)b единиц времени.
Обобщая полученные результаты относительно функции W(t), получим для нее следующее выражение:
,
где i - номер i-го требования в начальной очереди; требования поступают в моменты времени a, 2a, ...; b = na (n = 1, 2, ...).
Тема 11. Управление запасами
1. Понятие задачи управления запасами.
2. Основная задача управления запасами.
3. Управление запасами в условиях производственных поставок.
4. Управление запасами в условиях дефицита.
Количество товаров, поставляемое на склад, - размер партии товаров.
Издержки содержания запасов - затраты, связанные с хранением. Расходы этого рода возникают из-за ренты складирования и амортизации в процессе хранения (товары могут портиться, устаревать, их количество может уменьшаться и т.п.).
Издержки, связанные с дефицитом (штрафы). Если поставка со склада не может быть выполнена, то возникают дополнительные издержки, связанные с отказом. Это может быть реальный денежный штраф, уплачиваемый лицу, делающему заявку на товар, или ущерб, не осязаемый непосредственно (ухудшение бизнеса в будущем, потеря потребителей).
Математическая модель должна учитывать все эти издержки, и цель моделирования заключается в том, чтобы найти такую стратегию управления запасами, при которой суммарные издержки, связанные с запасами, сводились бы к минимальным.
|
Название параметра |
Обозначение |
Единицы измерения |
Предположения |
|
|
Интенсивность спроса |
d |
Ед-цы товара в год |
Спрос постоянен и непрерывен. Весь спрос удовлетворяется. |
|
|
Организационные издержки |
s |
$ за одну партию |
Организационные издержки постоянны, не зависят от размера партии |
|
|
Стоимость товара |
c |
$ за ед-цу товара |
Цена ед-цы товара постоянна, имеем только один вид товара |
|
|
Издержки содержания запасов |
h |
$ за ед-цу товара в год |
Стоимость хранения ед-цы товара в течение года постоянна |
|
|
Размер партии |
q |
Ед-ца товара в одной партии |
Постоянная величина, поступление мгновенное, как только уровень запаса становится равным 0. |
|
Рассмотрим график изменения запасов. В соответствии с предположениями этот график имеет вид:
Чтобы полностью удовлетворить годовой спрос d в размере поставки, равном q, нужно за год сделать поставок. Партия - это поставка.
Средний уровень запасов равен .
Составляем уравнение издержек. Это будет:
.
Чтобы найти минимум С, считаем функцию f(q) ди фференцируемой. Тогда значение q находится из уравнения:
или ,
откуда
,
где q* - оптимальный размер партии, называемый также оптимальным заказом.
.
Для С2 имеем:
С2 = сd.
Для С3 (затраты на хранение запасов) имеем:
С3 = (средний уровень запасов) h.
Средний уровень запасов находится следующим образом:
1. Максимальный уровень RT = (p - d)t, где t _ продолжительность поставки.
2. pt = q (количество товаров в одной поставке).
Отсюда:
(средний уровень запасов) = (максимальный уровень запасов) = .
Следовательно:
.
Оптимальный размер партии находится из уравнения:
.
Отсюда
.
.
Для С2. Штраф выплачивается за невыполнение поставок в течение периода . Общее количество "товаро-дней", за которые налагается штраф, равно площади BCD. Но
SBCD = .
Отсюда:
.
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).
(j = 1, 2, ..., n) и , (i = 1, 2, ..., m).
На следующем шаге рассматривают систему n + m уравнений:
Любое решение этой системы определяет точку , в которой может иметь место экстремум функции f (x1, x2, ..., xn). Таким образом, разрешив построенную систему, определяют все точки, в которых функция f может иметь экстремум. Дальнейшее исследование идет как в случае безусловного экстремума.
Итак, этапы решения задачи нелинейного программирования методом множителей Лагранжа заключаются в следующем:
Составляют функцию Лагранжа.
Находят частные производные функции Лагранжа по xj и i и приравнивают их 0.
Решая полученную систему, находят точки, в которых целевая функция задачи может иметь экстремум.
Среди точек, подозрительных на экстремум, находят точки, в которых достигается экстремум, вычисляют значения 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 1, выполнено соотношение:
f[X2 + (1 - )X1] f(X2) + (1 - )f(X1).
Множество допустимых решений удовлетворяет условию регулярности, если существует хотя бы одна точка Xi этой области такая, что gk(Xi) < bk (k = 1, 2, ..., m).
Задача выпуклого программирования возникает, если функция f является вогнутой (выпуклой), а gi - выпуклы.
Любой локальный максимум (минимум) является глобальным максимумом (минимумом). Наиболее характерным методом решения задач выпуклого программирования является метод множителей Лагранжа. При этом точка (X0, 0) называется седловой точкой функции Лагранжа, если:
F(x1, x2, ..., xn, ) F()
F(), для всех xj 0 и i 0.
Для задачи выпуклого программирования, множество допустимых решений которой обладает свойством регулярности, точка X0 = () является оптимальным решением тогда, когда существует такой вектор 0= (), что точка (X0, 0) является седловой точкой функции Лагранжа, построенной для исходной задачи.
Для задачи определения максимума, условиями седловой точки будут:
(частные производные берутся в седловой точке).
Для задачи нахождения минимума седловая точка определяется соотношениями:
F() F()
F().
Условия седловой точки в этой задаче представляются в виде:
,
.
f(X(k)) =
и строят линейную функцию:
F = .
Находят максимум функции F при сформулированных ограничениях. Пусть решение этой задачи Z(k). Тогда за новое допустимое решение принимают:
X(k+1) = X(k) + k(Z(k) - X(k)),
где k _ некоторое число, называемое шагом вычислений (0 k 1). Число k - произвольное и выбирают его так, чтобы значение функции в точке X(k+1) , зависящее от k, было максимальным. Для этого надо найти решение уравнения и выбрать его наименьший корень. Если корни уравнения больше 1, то берется k = 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) + k(Z(k) - X(k)) находят следующее допустимое решение.
Проверяют необходимость перехода к следующему допустимому решению. В случае необходимости переходят к этапу 2, если такой необходимости нет, то приемлемое решение найдено.
, где
ai _ весовые коэффициенты,
qi = bi - gi .
Используя H, последовательно переходят от одной точки к другой до тех пор, пока получится приемлемое решение. При этом координаты последующей точки находят по формуле:
(Б.3)
Из (Б.3) следует, что если предыдущая точка находится в области допустимых решений, то второе слагаемое в квадратных скобках равно 0, и переход к последующей точке определяется только градиентом целевой функции. Если же предыдущая точка не принадлежит области допустимых решений, то за счет указанного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом, чем меньше ? i, тем быстрее находится приемлемое решение, но точность определения решения снижается. Поэтому в начале ? i берут малым, постепенно увеличивая.
Итак, процесс решения включает этапы:
Определяют исходное допустимое решение.
Выбирают шаг вычислений.
Находят по всем переменным частные производные от целевой функции и функций, определяющих область допустимых решений задачи.
По (Б.3) определяют координаты точки - возможное новое решение.
Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если не удовлетворяют, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему решению. Если такой переход необходим, то переходят к пункту 2, иначе решение найдено.
Устанавливаются значения весовых коэффициентов и переходят к этапу 4.
| Контрольная работа | Концепция информатизации Российской Федерации |
| Контрольная работа | Причины агрессивного поведения. Методы работы с агрессивными детьми |
| Контрольная работа | Алгоритм выбора и реализации предпринимательской идеи |
| Контрольная работа | Современные методы арт-терапии |
| Контрольная работа | Системы управления взаимоотношения с клиентами |
| Контрольная работа | Учет материальных затрат в бухгалтерском учете |
| Контрольная работа | Геополитическое положение России |
| Контрольная работа | Особенности вознаграждения работников в организации |
| Контрольная работа | Виды запасов |
| Контрольная работа | Психоанализ |
| Контрольная работа | Авторское и патентное право |
| Контрольная работа | Основы конституционного строя как институт конституционного права |
| Контрольная работа | Распорядительные документы |
| Контрольная работа | Кодекс этики российского библиотекаря и проблема библиотечно-информационного обслуживания |
| Контрольная работа | Принципы проведения аудита |