Файл: Курс лекций.doc

Требуется определить количество дополнительных средств x_ij, которые необходимо вложить в работы (i, j), а также время начала и окончаниявы­полнения этих работ, что­бы проект был выполнен в срокt₀, а суммарные дополнительные затраты были минимальными.

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

; (6.3)

; (6.4)

; (6.5)

; (6.6)

; (6.7)

. (6.8)

Ограничение (6.4) определяет время завершения проекта, оно должно быть не больше заданного t_о. Ограничения (6.5) показывают, что продолжительность каждой работы должна быть не менее минимально возможной ее продолжительности. Ограничения-равенства (6.6) показывают зависимость продол­жительности каждой работы от вложенных в нее дополнитель­ных средств. Ограничения (6.7) обеспечивают выполнение ус­ловий предшествования работ: время начала выполнения каж­дой работы должно быть не меньше времени окончания непос­редственно предшествующих ей работ. Ограничение (6.8) — условие неотрицательности.

Задача 2 заключается в сокращении срока выполнения проекта, насколько это возможно за счет вложения суммы дополнительных средств, не превышающей В. Время выполне­ния каждой работы должно быть не меньше минимально воз­можного времени d_ij. Необходимо определить время начала и окончания каждой работы и величину дополнительных средств х_ij, которые нужно выделить на ускорение выполне­ния работы (i,j).

Математическая модель задачи 2 имеет вид:

;(6.9)

; (6.10)

; (6.11)

; (6.12)

. (6.13)

Смысл ограничений (6.10) – (6.13) аналогичен соответствующим огра­ничениям постановки задачи 1 (6.4) - (6.8). Если в последнее событие сети n входят сразу несколько работ, то необходимо добавить фиктивную работу (n, n+1), время выполнения которой равно нулю . Тогда целевая функция запи­шется так.

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

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

. (6.14)

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

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

Увеличение продолжительности работы (i, j) по сравне­нию с минимальным сроком выполнения на () вызовет экономию средств на величинуh_ij () , a стоимость выполнения работы станет равна

C = C_ij - h_ij ().(6.15)

Если t₀ = t_кp, то оптимизация осуществляется за счет увели­чения продолжительности некритических работ; если t_кр < t₀, — то за счет всех работ комплекса.

Математическая запись задачи:

; (6.16)

; (6.17)

; (6.18)

; (6.19)

; (6.20)

. (6.21)

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

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

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

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

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

Лекция 7. Экономико-математические методы и модели теории игр

Учебные вопросы

1 Предмет и задачи теории игр.

2 Матричные игры с нулевой суммой.

3 Решение матричных игр в чистых стратегиях.

4 Решение матричных игр в смешанных стратегиях.

5 Решение статистических игр по различным критериям.

1 Предмет и задачи теории игр

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

На промышленных предприятиях теория игр может исполь­зоваться для выбора оптимальных решений, например, при со­здании рациональных запасов сырья, материалов, полуфабри­катов, когда противоборствуют две тенденции: увеличения запасов, гарантирующих бесперебойную работу производства, и сокращения запасов в целях минимизации затрат на их хранение. В сельском хозяйстве теория игр может применяться при решении таких экономических задач, как выбор для возде­лывания одной из возможных культур, урожай которых зави­сит от погоды, если известны цена единицы каждой культуры и средняя урожайность каждой культуры в зависимости от пого­ды (будет ли лето засушливым, нормальным или дождливым); в этом случае одним из игроков выступает сельскохозяйствен­ное предприятие, стремящееся обеспечить наибольший доход, а другим игроком является природа.

Работникам торговли часто приходится принимать решения в условиях неопределенности, которые в той или иной мере умень­шают активность действий. Эта неопределенность обусловлена вре­менем завоза товаров на розничные и оптовые предприятия торговли, наличием транспортных средств, необходимым количеством продав­цов, кассиров, грузчиков и др. В таких случаях пытаются выбрать удачный вариант решения исходя из собственного опыта, интуиции или советов других лиц. Подобный субъективный подход, когда принятое решение затрагивает интересы большого количества людей, может быть неэффективным и даже ущербным.