Теоретические основы. Одной из основных задач СПУ является нахождение на сетевом графике критического пути, длительность которого определяет время исполнения всего проекта

Одной из основных задач СПУ является нахождение на сетевом графике критического пути, длительность которого определяет время исполнения всего проекта, описываемого с помощью СПУ. Однако часто превосходит плановое время исполнения проекта. Использование дополнительных ресурсов (денежных, трудовых, материальных и т.п.) приводит к сокращению сроков исполнения работ, входящих в проект: , где - время исполнения работы в отсутствие дополнительных ресурсов, - время исполнения работы при использовании ресурсов в количестве , - технологические коэффициенты. Задача оптимизации, связанная с подобным влиянием дополнительных ресурсов на длительности исполнения работ, состоит в следующем. Необходимо при минимальной затрате дополнительных ресурсов исполнить проект за время, не превосходящее плановое . Математическая формулировка задачи такова:

(1)

(2)

где - множество работ проекта, - множество событий проекта, - завершающее событие проекта, - момент окончания (начала) работы , - минимально возможная длительность работы .

Первое соотношение системы (1) означает, что все работы, оканчивающиеся в завершающем событии , завершаются не позднее . Второе соотношение указывает на то, что длительности всех работ не меньше минимальных длительностей этих работ. Третье соотношение дает зависимость длительностей работ от величины дополнительных ресурсов . Четвертое соотношение указывает на то, что все работы , оканчивающиеся в некотором промежуточном узле , имеют более ранние моменты окончания , чем моменты начала работ , исходящих из этого же узла. Пятое соотношение отражает естественное условие неотрицательности рассматриваемых переменных (полагаем, что весь проект начинается в нулевой момент времени). Соотношение (2) представляет собой требование минимальности суммарных дополнительных затрат, т.е. - целевая функция задачи (1)-(2). Искомыми переменными задачи (1)-(2) являются . Задача (1)-(2) является задачей линейного программирования, для решения которой можно использовать симплекс-метод, либо численные методы. Поскольку даже при небольшом количестве работ в проекте, задача (1)-(2) имеет много искомых неизвестных, то эту задачу удобнее решать, например, в EXCEL с использованием надстройки «Поиск решения».

Пример решения задачи (1)-(2) в EXCEL

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

Оптимизационная задача имеет вид:

(3)

(4)

Итак, имеем 15 неизвестных и 18 ограничений, не считая ограничений неотрицательности неизвестных.

Методику задания данных в EXCEL для решения задачи линейного программирования можно почерпнуть, например, из [2]. Для решения в EXCEL задачи (3)-(4) в ячейки D4:T4 вносим значения 0 – это ячейки, значения в которых будут изменяться в процессе поиска решения. Эти значения соответствуют значениям искомых неизвестных, поименованных в ячейках D3:T3. В ячейки D5:T22 вносим коэффициенты из ограничений (3). В ячейки D23:T23 вносим коэффициенты целевой функции (4). В столбец U5:U23 помещаем формулы для нахождения левых частей ограничений (3) и выражения для целевой функции (4). Это делается следующим образом: в ячейку U5 помещаем формулу =СУММПРОИЗВ($D$4:$T$4;D5:T5), далее формула копируется до ячейки U23 включительно. Следует обратить внимание на то, что ячейки $D$4:$T$4 имеют абсолютную адресацию (почему?); абсолютная адресация задается либо вручную, либо нажатием клавиши F4. Отметим, что в ячейке U23 содержится выражение для целевой функции (4). В ячейки W5:W22 помещаем правые части ограничений (3). Столбец V5:V23 является информационным – в нем указаны соотношения между левыми и правыми частями ограничений (3). Лист EXCEL с введенными данными для задачи (3)-(4) приведен на рис.2.

Рис.2. Лист EXCEL с введенными данными задачи (3)-(4). Курсор находится в ячейке U23 с выражением целевой функции.

На рис.3 представлена основная панель надстройки «Поиск решения» с введенными ограничениями задачи (3)-(4) и другими необходимыми для ее решения данными. Эта надстройка вызывается так: Сервис→Поиск решения. Нажатие клавиши Выполнить приводит к сообщению о нахождении решения (см. рис.4); само решение задачи представленно на рис.5.

Итак, получили, что минимальные суммарные затраты ресурсов равны , эти затраты распределены по работам следующим образом: . Временные параметры работ таковы:

Индивидуальные задания.

Решить согласно варианту оптимизационную задачу СПУ с помощью EXCEL, предварительно выписав с использованием своих данных задачу (1)-(2). Сетевой график представлен на рис.6 (один для всех вариантов); данные по вариантам представлены в Таблице 1.

Таблица 1.

Вариант	Параметры	Работа
(1;2)	(1;3)	(1;4)	(2;4)	(3;4)
	0,2	0,4	0,1	0,1	0,5
	0,1	0,3	0,5	0,2	0,25
	0,3	0,1	0,15	0,4	0,2
	0,45	0,2	0,1	0,4	0,1
	0,25	0,1	0,5	0,4	0,4
	0,4	0,5	0,2	0,1	0,15
	0,2	0,4	0,6	0,1	0,7
	0,8	0,6	0,2	0,3	0,35
	0,2	0,7	0,1	0,5	0,18
	0,1	0,3	0,25	0,4	0,3

ЛИТЕРАТУРА

1. Кузнецов А.В, Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.- Мн.: Выш.шк., 2001.

2. Экономико-математические методы и модели / Под общ. ред. С.Ф.Миксюк, В.Н.Комкова. Мн.: БГЭУ, 2006.

Дата добавления: 2015-04-29