Решение задачи. Эта задача относится к области управления проектами

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

Диаграмма, данная нам в условии задачи, в области управления проектами называется сетевой диаграммой. На любой такой диаграмме можно выделить так называемые «пути». Путь – это последовательность этапов проекта, по которой можно пройти, двигаясь по стрелкам от старта проекта до его финиша. Например в нашем проекте это Старт- B - D - I - Q - R -Финиш или Старт- A - C - J - M - S -Финиш. Всего в данном проекте можно выделить 8 путей.

Пути на сетевой диаграмме имеют несколько интересных свойств. Каждому пути можно приписать определенную длительность, равную сумме длительностей составляющих его этапов проекта. Так как этапы проекта выделяются таким образом, что каждый этап, отделенный от другого входящей стрелкой, может начаться только после того, как предшественник закончится, то выполнить все работы по пути Старт- A - C - J - M - S -Финиш, например, невозможно меньше, чем за 51 неделю. Отсюда следует, что и весь проект не может быть выполнен быстрее, чем будут выполнены все работы по самому длительному пути. Поэтому в теории управления проектами самый длинный путь (или пути, если их несколько) называют критическим. Для нас в данном случае важно, что определив длительность критического пути, мы сразу определим длительность проекта в целом.

Для этого построим следующую Excel таблицу (Рис. 162).

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

Длит. нед.

A

B

C

D

Е

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

BDIQR

BHPR

GLO

GKNS

FKNS

AEMS

ACJMS

ACJTS

ß Длительность критического пути

Рис. 161

В ячейку В3 вставляется формула =СУММПРОИЗВ($C$2:$V$2;C3:V3); в ячейку В12 вставляется формула =МАКС(B11:B23)

В строках 1 и 2 перечислены названия этапов и их длительности. В столбце A 3: A 10 приведены названия всех 8 путей на диаграмме (для краткости Старт и Финиш опущены). Если теперь в ячейках C 3: V 10 отметить единицами, какие из этапов принадлежат данному пути (в столбце A 3: A 10 слева), то формулы вида =СУММПРОИЗВ($ C $2:$ V $2; C 3: V 3) в ячейках B 3: B 10 покажут длительности путей. Разумеется, длительности путей можно было бы подсчитать и так, вручную. Но мы хотим, чтобы эти длительности легко пересчитывались при изменении длительностей этапов, так как эти длительности будут меняться при сокращении длительности проекта. Кстати говоря и саму табличку C 3: V 10 можно заполнять автоматически, используя могучие возможности E xcel.

Для этого в ячейке C 3 следует написать такую, может быть на вид устрашающую, но на деле простую формулу =ЕСЛИ(ЕОШИБКА(ПОИСК(C $1;$ A 3));0;1). Функция ПОИСК(C $1;$ A 3) ищет текст C 1 в тексте A 3. В случае успеха функция возвращает номер символа, с которого в A 3 идет текст C 1, а в случае, если такого текста в A 3 нет возвращает ошибку #ЗНАЧ. Так как ни то ни другое нам не интересно, а нужно знать есть заданная буква в названии пути или нет, то мы используем функцию ЕОШИБКА(). Эта функция возвращает значение ИСТИНА, если результат выполнения функции ПОИСК() дал ошибку #ЗНАЧ, и значение ЛОЖЬ, если буква была найдена. Так как нам нужно, чтобы в ячейке С3 стоял 0, если буквы этапа в названии пути нет и единица, если есть, то далее мы используем функцию ЕСЛИ(). В том виде, как она записана выше, эта функция возвращает как раз нужные нам значения: если ЕОШИБКА() дает ИСТИНА (есть ошибка), то 0 (буквы нет), если ЕОШИБКА() дает ЛОЖЬ (нет ошибки), то 1 (буква найдена). Как часто бывает в E xcel, такую функцию легче сконструировать, чем описать, как она работает.

Знаки $ добавлены так, чтобы функцию можно было протянуть на всю таблицу C 3: V 10. При протягивании получаем результат, показанный в таблице 1.28.

Как мы видим в столбце B 3: B 10 длительности путей заключены в интервале от 32 до 56 недель. При этом самый длинный путь – BDIQR. Таким образом длительность проекта Омикрон составит не менее 56 недель. Эта величина и является ответом на вопрос a. Если записать в ячейке B 12 формулу =МАКС(B 11: B 23), то длительность проекта, при изменении длительностей этапов, будет показываться автоматически. Это удобно для подбора сокращаемых этапов.

После проделанной нами работы становится понятно, что нет никакого смысла сокращать длительность этапов O и L - ведь они вообще не входят в состав критического пути BDIQR. Очевидно, что сокращать нужно только те этапы, которые входят в критический путь. Может показаться даже, что для сокращения проекта на пять недель нужно сократить каждый из этапов пути BDIQR на одну неделю! Тем более, что сокращение любого этапа на первую неделю значительно дешевле, чем на вторую.

Пробуем! Изменяем длительность B с 9 до 8 недель, D – с 10 до 9 и т.д. И наконец в ячейке B 12 читаем новую длительность проекта – 54 недели. А вовсе не нужные нам 51 неделю. Сразу видно, что критический путь теперь ACJMS, а не BDIQR, который перестал быть критическим после сокращения третьего этапа на 1 неделю.

Таким образом, после сокращения пути BDIQR на 2 недели путь ACJMS также становится критическим. Теперь, для сокращения длительности проекта в целом придется сокращать и путь BDIQR, и путь ACJMS. А кроме того мы забыли про стоимость сокращения. Если мы хотим, чтобы стоимость сокращения была наименьшей, то первые 2 сокращаемых этапа должны быть самыми дешевыми (из пяти возможных). Так как при дальнейшем сокращении длительности проекта придется сокращать длительность сразу двух этапов, то нужно будет отбирать их так, чтобы сумма стоимостей их сокращения была минимальной из других возможных сумм. А что будет, когда количество критических путей станет равной 3? В общем, ясно, что сложность задачи быстро растет с увеличением срока сокращения.

Давайте не будем больше мучиться и построим задачу линейной оптимизации – пусть Поиск решения отыщет наилучший метод сокращения длительности проекта.

Для этого немного перестроим нашу таблицу (Рис. 163). Во-первых, вставим 6 строк между 2-ой и 3-ей строчками и занесем в строки C 3: V 3 и C 4: V 4 информацию о стоимости сокращения на первую и вторую недели соответственно. Числа 999 соответствуют запрету на сокращение. Мы нигде не будем оговаривать такой запрет, но используем большие числа, как индикатор запрещенного сокращения. В пятую строку занесем исходную длительность каждого этапа. Строки 7 и 8 будут содержать информацию о сокращении этапов. Так как стоимость сокращения на первую и вторую недели различна, мы не может выбрать в качестве переменных длительность сокращения для каждого этапа (на 1 или 2 недели). Поэтому переменные будут двоичные. Единица в соответствующей ячейке будет означать, что сокращение данного этапа на одну неделю сделано, ноль – сокращения не было. В строке C 6: V 6 по формуле типа = C 7+ C 8 подсчитывается общая величина сокращения каждого этапа. По этим данным в строке C 2: V 2 будем вычислять новую длительность для всех этапов.

При таких изменениях ячейки B 9: B 16 содержат, как и раньше, длительности путей, но теперь эта длительность вычисляется с учетом проводимых сокращений.

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

A

B

C

D

Е

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

Новая длитель

Стоим.сокращ.1-я нед.

-

Стоим.сокращ.2-я нед.

-

-

Исходная длительность

Общ.сокращ.

1-я нед.

2-я нед.

BDIQR

BHPR

GLO

GKNS

FKNS

AEMS

ACJMS

ACJTS

Стоимость сокращения

ß Длительность критического пути ß Заданная длительность

ß Заданная длительность  

Рис. 162

В ячейку В9 вставляется формула =СУММПРОИЗВ($C$2:$V$2;C9:V9); в ячейку В12 вставляется формула =МАКС(B11:B23)

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

Сумма произведений =СУММПРОИЗВ(C 3: V 3; C 7: V 7) даст нам полную стоимость сокращений на первую неделю. Аналогичная операция для строк C 4: V 4 и строки C 8: V 8 – стоимость сокращения всех выбранных этапов на вторую неделю.

Запишем в ячейку V 18 сразу сумму этих двух формул:

=СУММПРОИЗВ(C 3: V 3; C 7: V 7) + СУММПРОИЗВ(C 4: V 4; C 8: V 8).

Это и будет наша целевая функция.

Желаемая длительность сокращенного проекта будет параметром нашей задачи оптимизации. Запишем эту величину - желаемую длительность проекта, в ячейку B 19. А также, для справки, исходную его длительность – 56 недель – занесем в ячейку A 1.

У нас практически все готово для постановки задачи Поиску решения.

Вы можете заметить, что в ячейках C 9: V 16 у нас содержится довольно хитрая формула, причем явно не линейная. Как же быть с ней? На самом деле она не должна нам помешать. Ведь при поиске решения значения в этих ячейках не пересчитываются, они вычислены один раз и не меняются при решении задачи. Тем не менее, если возникает какая-то проблема, и

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

Итак, вызываем Поиск решения и отмечаем в параметрах, что задача линейная. Указываем в качестве целевой ячейку V 18, а в качестве цели минимум издержек.

Переменные задачи C 7: V 8.

Теперь зададим ограничения. Первое ограничение состоит в том, что переменные – двоичные: C 7: V 8 = двоичное.

Второе ограничение должно задать длительность проекта. Так как формулу =МАКС(B 9: B 16) мы использовать в вычислениях не можем, потребуем просто, чтобы все длительности путей были меньше или равны заданной длительности проекта в целом: B 9: B 16 <= B 20.

И, наконец, техническое ограничение. Каждый этап должен быть сокращен сначала на первую, а уже потом на вторую неделю. Для этого потребуем, чтобы C 7: V 7 >= C 8: V 8. Так как в нашей задаче сокращение на вторую неделю стоит не меньше, чем сокращение на первую неделю для всех этапов, то это условие не особенно нужно. Обычно оно удовлетворяется автоматически (кроме этапов K и P). Но при чуть других условиях задачи оно бы потребовалось, поэтому не мешает испытать такое ограничение, в расчете на будущее использование.

Теперь все ограничения заданы. Запускаем Поиск решения на выполнение и получаем следующий результат (Рис. 164). Общая стоимость сокращения на 5 недель - 380000. При этом следует сократить этапы B, C, I, M, Q, S на одну неделю и этап R на две недели.

A

B

C

D

Е

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

Новая длитель

Стоим.сокращ.1-я нед.

-

Стоим.сокращ.2-я нед.

-

-

Исходная длительность

Общ.сокращ.

1-я нед.

2-я нед.

BDIQR

BHPR

GLO

GKNS

FKNS

AEMS

ACJMS

ACJTS

Стоимость сокращения

ß Длительность критического пути ß Заданная длительность

ß Заданная длительность  

Рис. 163

Следует отметить, что для дальнейшего сокращения проекта придется сокращать несколько этапов на каждом шаге сокращения. Как можно увидеть в таблице (Рис. 164), после того, как длительность проекта достигла 51 недели, три пути являются критическими.

Для ответа на следующий вопрос задачи (c) можно перестроить нашу задачу. Однако значительно быстрее просто решить полученную задачу несколько раз, подставляя разные желаемые длительности проекта. Так как каждый этап можно сократить не более чем на 2 недели, а критический путь содержал 5 этапов, то ясно, что более чем на 10 недель сократить проект невозможно. Значит, полное исследование задачи займет немного времени.

Построим табличку, в которой будем записывать результаты расчетов. Пусть таблица содержит данные об итоговой длительности проекта, номере недели сокращения проекта, сокращенных этапах, стоимости сокращения на данную неделю, суммарной стоимости сокращения проекта с нарастающим итогом и финансовом результате сокращения с учетом полученной премии. Чтобы заполнить таблицу начнем с сокращения проекта на 1 неделю. Заданная длительность проекта – 55 недель. Вызываем Поиск решения и получаем рекомендацию, сократить этап R на первую неделю. Стоимость сокращения – 3 (30000). Меняем заданную длительность на 54 недели. Повторяем оптимизацию. Получаем рекомендацию, сократить этап R на вторую неделю. Стоимость сокращения – 4 (40000), общая стоимость сокращения 70000. Финансовый результат – 330000. Продолжаем заполнять таблицу до тех пор, пока не получим ответ, что решение не найдено. Как вы видите, это произошло при попытке сократить проект до 45 недель, как мы и ожидали. Рассмотрим полученную итоговую таблицу (Рис. 165).

Длительность ролекта	Неделя сокращения	Этапы	Стоимость данного сокращения	Итого	Выигрыш
		R
		R
		QM
		CI
		BS
		AD
		QS
		IJK
		BCK
		ADG

Рис. 164

Видно, что выигрыш сначала увеличивался, а затем стал уменьшаться. Очевидно, что максимальный выигрыш (670 тыс.) как раз и соответствует оптимальному (для строительной фирмы) сроку сокращения длительности проекта (7 недель). При этом проект будет выполнен за 49 недель. Сокращение на 8-ю неделю стоит 200 тыс. и полностью поглощает премию за сокращение на очередную неделю, а сокращение на 9 и 10 неделю стоит строительной фирме

дороже, чем предложенные премиальные. Таким образом, строителям следует договариваться о выполнении проекта за 49 недель. Сокращение проекта на максимально возможный срок – 10 недель – принесет строительной фирме (дополнительно к сметной прибыли) только 590

тыс.

П-4. Научно-просветительский центр планирования семьи в

Дата добавления: 2015-07-20