Учебно-методический комплекс дисциплины обсужден на заседании кафедры компьютерных систем «03» октября 2012 г. Составитель (ли): Т.

ЛАБОРАТОРНЫЕ ЗАНЯТИЯ (36час.)

Цикл работ с использованием методов интерактивного/активного обучения –методов компьютерного моделирования и проектного обучения(32 час.)

РАБОТА 1. Математическое моделирование (2 час.)

Задание.Построение математических моделей средствами редактора формул

Объект моделирования: математическая формула прямолинейного равноускоренного движения тела (изменение координаты х с течением времени).



Цель моделирования: построение математической модели.

Инструмент моделирования: редактор формул Microsoft Equation.

Технология выполнения работы

1. 
   Откройте текстовый процессор MS Word по команде Пуск/Все программы/ Microsoft Word.
   
2. 
   Выбрать в меню Вставка команду Объект.
   
3. 
   Выбрать Microsoft Equation 3.0.
   
4. 
   Составить формулу с помощью наборов символов и шаблонов.
   
5. 
   Щелкнуть в окне документа Word.
   
6. 
   Ниже формулы поясните обозначения, используемые в записи формулы.
   
7. 
   Покажите результат работы преподавателю.
   

РАБОТА 2. Математические модели управления проектами (8 час.)

Задание. Управления проектами

Цель работы:ознакомиться с оптимизацией проекта по времени, по стоимости и по ресурсам

1 Общие сведения

Оптимизация проекта по времени

Сокращение времени завершения проекта, как правило, связано с привлечением дополнительных средств (количество рабочих, сверхурочное время). Рассмотрим два примера постановки задачи оптимизации проекта по времени с привлечением дополнительных средств.

Постановка задачи 1. Для сокращения времени выполнения проекта выделяется некоторая сумма дополнительных средствB. Задан сетевой график выполнения проекта, где Е — множество событий, а e— множество работ. Продолжительность каждой работы равна t_ij. Известно, что вложение дополнительных средств x_ij в работу (i, j) сокращает время ее выполнения от t_ij до t'_ij, причем эта зависимость выражается как

(f_ij — известные функции).

Для каждой работы существует минимально возможное время ее выполнения d_ij.

Требуется определить время начала Ј^н_ij и окончания t°_ijвыполнения работ, а также количество дополнительных средств x_ij, которые необходимо вложить в работы (i, j), чтобы общее время выполнения проекта было минимальным, сумма вложенных дополнительных средств не превышала величины B, время выполнения каждой работы было не меньше минимально возможного времени d_ij.

Математически условия задачи можно записать следующим образом:



Ограничение (2) определяет сумму вложенных дополнительных средств: она не должна превышать величины B. Ограничения (3) показывают, что продолжительность каждой работы должна быть не менее минимально возможной ее продолжительности. Ограничения-равенства (4) показывают зависимость продолжительности каждой работы от вложенных в нее дополнительных средств. Ограничения (5) обеспечивают выполнение условий предшествования работ в соответствии с топологией сети: время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующих ей работ. (6) — условие неотрицательности.

Если в последнее событие сети п входят сразу несколько работ, то необходимо добавить фиктивную работу (n, n+1), время выполнения которой равно нулю (t^o_n,n+1-t^н_n,n+1=0 добавить в ограничение (4)). Тогда целевая функция запишется такt_кр=t^o_n,n+1(min).

Постановка задачи 2. Пусть задан срок выполнения проекта t_o, а расчетное t_кр> t_o. В этом случае оптимизация комплекса работ сводится к сокращению продолжительности критического пути. Задача заключается в определении величины дополнительных вложений x_ijв отдельные работы проекта, с тем чтобы общий срок его выполнения не превышал заданной величины t_o, а суммарный расход дополнительных средств был минимальным. Время выполнения каждой работы должно быть не меньше минимально возможного времени d_ij.

Математическая запись этой задачи:Смысл ограничений аналогичен соответствующим ограничениям постановки задачи 1 (1) — (6).

Приведенные постановки задачи относятся к классу задач математического программирования и могут быть решены известными методами в зависимости от вида функций f_ij (х_ij).

Если предположить, что продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношениемгде k_ij — технологические коэффициенты использования дополнительных средств, то будем иметь задачу линейного программирования.

Оптимизация проекта по стоимости

В общем случае стоимость выполнения работы зависит от ее продолжительности. Продолжительность каждой работы может изменяться между двумя границами d_ijи D_ij, определяемыми техническими или экономическими соображениями. Если D_ij— нормальная продолжительность, ей соответствует минимальная стоимость c_ij выполнения работы (i, j); если d_ij — минимально возможная (экстренная) продолжительность работы, при этом стоимость работы будет максимальной С_ij;. Если при планировании проекта для каждой работы будет взята ее нормальная (наибольшая) длительность D_ij, то стоимость проекта будет минимальной. Если для каждой работы взять ее ускоренную, минимально возможную продолжительность d_ij, мы получим срочный план. Стоимость выполнения проекта в этом случае будет максимальной.

Зависимость стоимости от продолжительности работы нелинейна, но для упрощения оптимизационных расчетов предполагают, что уменьшение продолжительности работы пропорционально возрастанию ее стоимости. Тогда в расчете на единицу времени дополнительные затраты на сокращение продолжительности работы будут равны

Рассмотрим оптимизацию комплекса работ по стоимости при фиксированном сроке выполнения.

Предполагается, что все работы выполняются в срочном режиме и исходная стоимость проектамаксимальна. Необходимо минимизировать стоимость проекта при фиксированном сроке его завершения t_o за счет увеличения времени выполненияотдельных работ.

Увеличение продолжительности работы (i,j) по сравнению с минимальным сроком выполнения на (t°_ij - t^н_ij - d_ij) вызовет экономию средств на величину h_ij (t°_ij -t^н_ij - d_ij), a стоимость выполнения работы станет равнаС = C_ij - h_ij (t^o_ij - t^н_ij - d_ij).Если t_o = t_кр, то оптимизация осуществляется за счет увеличения продолжительности некритических работ; если t_кр< t_о, — то за счет всех работ комплекса.Математическая запись задачи:

Здесь 1 — номер исходного события, п — номер завершающего события.

Рассмотрим оптимизацию комплекса работ по стоимости при нефиксированном сроке выполнения.Пусть задан сетевой график проекта и известны продолжительность каждой работы и стоимость ее выполнения в нормальном (D_ij, c_ij) и срочном (d_ij;, C_ij) режиме работы. Если все работы выполняются в нормальном режиме, то критический срок будет наибольшим, а стоимость выполнения — наименьшей. Время выполнения проекта может быть уменьшено путем увеличения стоимости. Необходимо сократить критический срок до некоторого минимально возможного значения при наименьшем возрастании стоимости выполнения проекта.

Оптимизация проекта по ресурсам

Пусть проект задан сетевым графиком. Для выполнения проекта выделено R единиц ресурса. Каждая работа характеризуется продолжительностью выполнения t_ijи интенсивностью потребления ресурса r_ij. Под интенсивностью потребления будем понимать требуемое количество ресурса для выполнения работы (i, j) в единицу времени. Для простоты допустим, что интенсивности постоянные.

Под оптимальным распределением ресурса понимается такое размещение работ во времени, при котором в любой момент времени потребность в ресурсах не превышает имеющегося в наличии количества ресурса, а время выполнения проекта минимально.

Технологиявыполнения работы

- ознакомится с методическими указаниями, изложенными в п.1;

- решить задачи.

РАБОТА 3. Модели теории оптимального управления (8 час.)

Задание. Решение задач оптимизации с использованием информационной технологии. Решение задач линейного программирования

Цель работы:

1. Приобретение навыков решения оптимизационных задач в табличном редакторе Microsoft Excel.

2. Научиться составлять экономико-математические модели линейных задач и находить оптимальное решение

Краткая справка

Для того чтобы решить задачу ЛП в табличном редакторе Microsoft Excel, необходимо выполнить следующие действия.

1. 
   Ввести условие задачи:
   

создать экранную форму для ввода условия задачи:

• 
  переменных,
  
• 
  целевой функции (ЦФ),
  
• 
  ограничений,
  
• 
  граничных условий.
  

ввести исходные данные в экранную форму:

• 
  коэффициенты ЦФ,
  
• 
  коэффициенты при переменных в ограничениях,
  
• 
  правые части ограничений.
  
1. 
   Ввести зависимости из математической модели в экранную форму:
   
   • 
     формулу для расчета ЦФ,
     
   • 
     формулы для расчета значений левых частей ограничений.
     
2. 
   Задать ЦФ (в окне "Поиск решения"):
   
   • 
     целевую ячейку,
     
   • 
     направление оптимизации ЦФ;
     
3. 
   Ввести ограничения и граничные условия (в окне "Поиск решения"):
   
   • 
     ячейки со значениями переменных,
     
   • 
     граничные условия для допустимых значений переменных,
     
   • 
     соотношениямежду правыми и левыми частями ограничений.
     
4. 
   Решить задачу:
   

- установить параметры решения задачи (в окне "Поиск решения");

- запустить задачу на решение (в окне "Поиск решения");

- выбрать формат вывода решения (в окне "Результаты поиска решения").

Рассмотрим пример нахождения решения для следующей задачи ЛП:

(1.1)