УСР №4. РЕШЕНИЕ С ИСПОЛЬЗОВАНИЕМ EXCEL ОДНОЙ ИЗ ЗАДАЧ ОПТИМИЗАЦИИ ПРИ СЕТЕВОМ ПЛАНИРОВАНИИ И УПРАВЛЕНИИ (СПУ)
Теоретические основы
Одной из основных задач СПУ является нахождение на сетевом графике критического пути, длительность которого 
определяет время исполнения всего проекта, описываемого с помощью СПУ. Однако часто превосходит плановое время 
исполнения проекта. Использование дополнительных ресурсов (денежных, трудовых, материальных и т.п.) приводит к сокращению сроков исполнения работ, входящих в проект: 
, где 
- время исполнения работы 
в отсутствие дополнительных ресурсов, 
- время исполнения работы при использовании ресурсов в количестве 
, 
- технологические коэффициенты. Задача оптимизации, связанная с подобным влиянием дополнительных ресурсов на длительности исполнения работ, состоит в следующем. Необходимо при минимальной затрате дополнительных ресурсов исполнить проект за время, не превосходящее плановое . Математическая формулировка задачи такова:
(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.