- •Эконометрика и экономико-математические модели и методы
- •1 Эконометрика Предмет и область применения эконометрики.
- •Вопрос 11. Построение аддитивной и мультипликативной моделей временных рядов
- •Вопрос 12. Автокорреляция уровней временного ряда
- •Вопрос 13. Выбор вида уравнения тренда
- •2 Содержание экономико-математических моделей и методика их построения
- •Вопрос 14. Содержание экономико-математических моделей и методика их построения
- •Вопрос 15. Общая классификация экономико-математических моделей
- •Вопрос 16. Линейные экономико-математические модели
- •Вопрос 17. Формы записи задачи линейного программирования, их эквивалентность и способы преобразования
- •Вопрос 18. Двойственность в задачах линейного программирования
- •Вопрос 19. Экономический анализ решения задач линейного программирования
- •Вопрос 20. Транспортная задача линейного программирования
- •Вопрос 21. Векторная оптимизация
- •Метод линейной комбинации частных критериев
- •Метод ведущего критерия
- •Метод последовательных уступок
- •Метод равных и наименьших относительных отклонений
- •Модели управления однономенклатурными и многономенклатурными запасами
- •1. Входные:
- •2. Выходные:
- •Решение
- •Матричные игры
- •1 Решение матричных игр с нулевой суммой
- •Вопрос 22. Решение матричных игр с нулевой суммой для игр с седловой точкой
- •Вопрос 23. Решение игр с природой по различным критериям
- •3 Решение матричных игр с нулевой суммой для игр без седловой точки
- •Системы и модели массового обслуживания
- •Классификация систем массового обслуживания
- •Основные характеристики систем массового обслуживания
Решение
В пункте 1) условия явно указано, что A, B и C являются исходными работами, поэтому изобразим их тремя стрелками, выходящими из исходного события 1. Пункт 2) условия означает, что стрелки работ A и B должны окончиться в одном событии, из которого выйдет стрелка работы D. Но поскольку стрелки работ A и B также и начинаются в одном событии, то имеет место параллельность работ, которая недопустима правилами построения сетевых моделей (см. рис.4).
Рис.4. Устранение параллельности работ A и B
Для ее устранения введем дополнительное событие 2, в которое войдет работа B, после чего соединим события 2 и 3, в которые входят работы A и B пунктирной стрелкой фиктивной работы. В данном случае фиктивная работа (2,3) не соответствует никакой реальной работе, а лишь отображает логическую связь между работами B и D. Дальнейшее построение рассмотрим с помощью рис.5
Рис.5. Сетевая модель задачи №7.02
Согласно пункту 3) условия задачи из события 2, выходят три стрелки работ E, F и H. Согласно пункту 4) условия задачи стрелки работ C и F должны войти в общее событие, из которого выйдет стрелка работы G. Проблема с параллельностью работ E и H [пункт 5) условия задачи] решается путем введения дополнительного события 5 и фиктивной работы (5,6). Для отображения в сетевой модели пункта 6) условия задачи введем стрелки работ D и J в событие 7, а связь работ F и C с работой K отобразим с помощью фиктивной работы (4,7). Стрелки работ F и C нельзя было напрямую вводить в событие 7, потому что после них должна следовать работа G, которая с работами D и J никак не связана. Стрелка работы L выходит из события 8, т.е. после окончания работы K в соответствии с пунктом 7) условия задачи.
Поскольку в условии не указано, что работы L, I и G предшествуют каким-либо другим работам, то эти работы являются завершающими и их стрелки войдут в завершающее событие 9. Нумерацию событий проводят после построения сетевого графика, следя за тем, чтобы номер начального события каждой работы был меньше номера ее конечного события.
Расчет сетевых моделей
Календарное планирование предусматривает определение моментов начала и окончания каждой работы и других временных характеристик сетевого графика. Это позволяет проанализировать сетевую модель, выявить критические работы, непосредственно определяющие срок выполнения проекта, провести оптимизацию использования ресурсов (временных, финансовых, исполнителей).
Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика (рис.8.1):
–
ранний срок
наступления события i,
минимально необходимый для выполнения
всех работ, которые предшествуют событию
i;
–
поздний срок
наступления события i,
превышение которого вызовет аналогичную
задержку наступления завершающего
события сети;
–
резерв события
i, т.е. время, на которое
может быть отсрочено наступление
события i без нарушения
сроков завершения проекта в целом.
Рис.6. Отображение временных параметров событий на сетевом графике
Ранние сроки свершения событий рассчитываются от исходного (И) к завершающему (З) событию следующим образом:
для исходного события И
;для всех остальных событий I
,
где максимум
берется по всем работам
,
входящим в событие i;
–
длительность работы (k,i)
(рис.8.2).
Рис.7 Расчет раннего срока свершения события i
Поздние сроки свершения событий рассчитываются от завершающего к исходному событию:
для завершающего события З
;для всех остальных событий
,
где минимум берется
по всем работам
,
выходящим из события i;
–
длительность работы (k,i)
(рис.8.3).
Рис.8 Расчет позднего срока свершения события i
Временные параметры работ определяются на основе ранних и поздних сроков событий:
–
ранний срок начала
работы;
–
ранний срок
окончания работы;
–
поздний срок
окончания работы;
–
поздний срок
начала работы;
–
полный резерв
работы показывает максимальное время,
на которое можно увеличить длительность
работы
или отсрочить ее начало, чтобы не
нарушился срок завершения проекта в
целом;
–
свободный резерв
работы показывает максимальное время,
на которое можно увеличить продолжительность
работы
или отсрочить ее начало, не меняя ранних
сроков начала последующих работ.
Путь – это последовательность работ в сетевом графике (в частном случае это одна работа), в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы.
Полный путь – это путь от исходного до завершающего события.
Критический путь – максимальный по продолжительности полный путь. Работы, лежащие на критическом пути, называют критическими. Критические работы имеют нулевые свободные и полные резервы.
Подкритический путь – полный путь, ближайший по длительности к критическому пути.
Для проведения
анализа временных параметров сетевой
модели используют график привязки,
который отображает взаимосвязь
выполняемых работ во времени. По
вертикальной оси графика привязки
откладываются коды работ, по горизонтальной
оси – отрезки, соответствующие
длительностям работ (раннее начало и
раннее окончание работ). График привязки
можно построить на основе данных о
продолжительности работ. При этом
необходимо помнить, что работа
может выполняться только после того
как будут выполнены все предшествующие
ей работы
.
Пример расчета сетевой модели
Рис.9. Расчет сетевой модели
Оптимизация комплекса работ по времени
Оптимизация комплекса операций по времени сводится к сокращению продолжительности критического пути. Необходимость проведения оптимизации сетевого графика по времени возникает тогда, когда критическое время выполнения комплекса операций превосходит срок T0, на котором настаивает ЛПР. Очевидно, подобная задача требует проведения определенных мероприятий и (или) вложения дополнительных средств.
Иногда оптимизация достигается за счет перепланировки сетевого проекта (изменения топологии сети). Например, одновременно выполняемые операции, имеющие резервы времени и не лежащие на критическом пути, могут выполняться последовательно (если это допускается технологией). Освободившиеся при этом ресурсы можно использовать на критических операциях, что ускорит их выполнение. Сокращение времени выполнения операций возможно также за счет автоматизации производственных процессов, улучшения организации работ, использования передовых технологий и т.д.
Оптимизация комплекса операций по времени может проводиться с привлечением дополнительных средств и с использованием внутренних резервов.
Приведем математическую формулировку процесса оптимизации по времени.
Пусть задан сетевой график выполнения комплекса операций. Время выполнения каждой операции равно tij. Пусть также вложение дополнительных средств в операцию сокращает время выполнения с tij до t’ij. Естественно, для каждой операции существует минимально возможное время ее выполнения, равное dij. Требуется определить время начала и окончания выполнения операций, а также величину дополнительных средств xij, которые необходимо вложить в каждую из операций (i, j), чтобы общее время выполнения комплекса операций было минимальным. При этом сумма вложенных дополнительных средств не должна превышать заданной величины c, а время выполнения каждой операции должно быть не меньше минимально возможного времени dij.
Математически условия задачи можно записать следующим образом:
Ограничение (2) определяет сумму вложенных дополнительных средств: она не должна превышать величины c. Ограничения (3) показывают, что продолжительность каждой работы должна быть не менее минимально возможной ее продолжительности. Ограничения-равенства (4) показывают зависимость продолжительности каждой работы от вложенных в нее дополнительных средств. Ограничения (5) обеспечивают выполнение условий предшествования работ в соответствии с топологией сети: время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующих ей работ, (6) — условие неотрицательности.
Если в последнее событие сети п входят сразу несколько работ, то необходимо добавить фиктивную работу (n, n+1), время выполнения которой равно нулю (ton,n+1-tнn,n+1=0 добавить в ограничение (4)). Тогда целевая функция запишется так
tкр=ton,n+1 → (min)
Приведенные постановки задачи относятся к классу задач математического программирования и могут быть решены известными методами в зависимости от вида функций fij (хij). Если предположить, что продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением
где kij — технологические коэффициенты использования дополнительных средств, то будем иметь задачу линейного программирования.
Пример.
Для сокращения срока реализации проекта, представленного сетевым графиком (рис.10), заказчик выделил 14 ед. дополнительных средств. Продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением t'ij = tij - kij xij. Известно, что kl2=0,1; k13 = 0,2; k23 = 0,5; k24 = 0,3; k35 = 0,6; k45 = 0,1. Над каждой работой поставлена ее продолжительность tij и минимально возможное время выполнения dij.
Рис.
10
Требуется
оптимизировать сетевой график по
времени, то есть найти такие
,
, xij
чтобы:
а) время выполнения всего проекта было минимальным;
б) сумма дополнительно вложенных средств не превышала 14 ед.;
Ниже приводится образец решения задачи в Excel
Таким образом, при дополнительном вложении 14 ед. комплекс работ может быть выполнен за 30 ед. времени. При этом средства распределятся следующим образом: 4 ед. в работу (2, 3) и 10 ед. в работу (3, 5) (Рис.4).
Постановка задачи 2. Пусть задан срок выполнения проекта to, а расчетное tкр > to. В этом случае оптимизация комплекса работ сводится к сокращению продолжительности критического пути. Задача заключается в определении величины дополнительных вложений xij в отдельные работы проекта, с тем чтобы общий срок его выполнения не превышал заданной величины to, а суммарный расход дополнительных средств был минимальным. Время выполнения каждой работы должно быть не меньше минимально возможного времени dij.
Математическая запись этой задачи:
Смысл ограничений аналогичен соответствующим ограничениям постановки задачи 1 (1) — (6).
Приведенные постановки задачи относятся к классу задач математического программирования и могут быть решены известными методами в зависимости от вида функций fij (хij). Если предположить, что продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением
где kij — технологические коэффициенты использования дополнительных средств, то будем иметь задачу линейного программирования.
Оптимизация проекта по стоимости
В общем случае стоимость выполнения работы зависит от ее продолжительности. Продолжительность каждой работы может изменяться между двумя границами dij и Dij, определяемыми техническими или экономическими соображениями. Если Dij — нормальная продолжительность, ей соответствует минимальная стоимость cij выполнения работы (i, j); если dij — минимально возможная (экстренная) продолжительность работы, при этом стоимость работы будет максимальной Сij;. Если при планировании проекта для каждой работы будет взята ее нормальная (наибольшая) длительность Dij, то стоимость проекта будет минимальной. Если для каждой работы взять ее ускоренную, минимально возможную продолжительность dij, мы получим срочный план. Стоимость выполнения проекта в этом случае будет максимальной.
Зависимость стоимости от продолжительности работы нелинейна, но для упрощения оптимизационных расчетов предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Тогда в расчете на единицу времени дополнительные затраты на сокращение продолжительности работы будут равны
Рассмотрим оптимизацию комплекса работ по стоимости при фиксированном сроке выполнения.
Предполагается, что все работы выполняются в срочном режиме и исходная стоимость проекта
максимальна.
Необходимо минимизировать стоимость
проекта
при фиксированном сроке его завершения
to
за счет увеличения
времени выполнения отдельных работ.
Увеличение продолжительности работы (i,j) по сравнению с минимальным сроком выполнения на (t°ij - tнij - dij) вызовет экономию средств на величину hij (t°ij -tнij - dij), a стоимость выполнения работы станет равна
С = Cij - hij (toij - tнij - dij).
Если to = tкр, то оптимизация осуществляется за счет увеличения продолжительности некритических работ; если tкр < tо, — то за счет всех работ комплекса.
Математическая запись задачи:
Здесь 1 – номер исходного события, п – номер завершающего события.
Рассмотрим оптимизацию комплекса работ по стоимости при нефиксированном сроке выполнения.
Пусть задан сетевой график проекта и известны продолжительность каждой работы и стоимость ее выполнения в нормальном (Dij, cij) и срочном (dij;, Cij) режиме работы. Если все работы выполняются в нормальном режиме, то критический срок будет наибольшим, а стоимость выполнения — наименьшей. Время выполнения проекта может быть уменьшено путем увеличения стоимости. Необходимо сократить критический срок до некоторого минимально возможного значения при наименьшем возрастании стоимости выполнения проекта.
Тема . Экономико-математические методы и модели теории игр
