Оптимизация графика работ по проекту с помощью Поиска решений в MS EXCEL

Решим задачу об оптимизации плана-графика работ по проекту с помощью Поиска решений MS EXCEL 2010. В качестве примера разберем задачу из сборника "Методы оптимизации управления и принятия решений" авторы Зайцев М.Г. и Варюхин С.Е. (2008г.). Задача 3.7 "Проект комапании Мегашоп".

Сборник задач "Методы оптимизации управления и принятия решений" довольно популярен в качестве задачника для Вузов, поэтому ссылки на него встречаются повсеместно в интернете. Приятно, что для каждой задачи имеется ответ в конце книги - можно сравнить получившееся решение с решением, которое найдено авторами с помощью Поиска решения (в году так 2000-м, я полагаю). 

Условия задачи

Компания МегаШоп планирует развертывание сети магазинов в южном регионе России. Отдел развития компании составил план работы по развертыванию сети, состоящий из 21 этапа (здесь они обозначены буквами от A до U). В таблице приведена информация длительности этапов в рабочих днях:

Сетевая диаграмма проекта, показывающая порядок выполнения работ приведена на рисунке.

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

Срочный запрос служащим и подразделениям, исполняющим отдельные этапы проекта, выявил, что некоторые этапы можно сократить на три дня. В таблице указаны стоимости ускорения выполнения этапов проекта. Если стоимость не указана, сокращение невозможно.

Задания:

a. Определите минимальную стоимость сокращения длительности проекта на две недели.

b. Допустим, что альтернативой сокращению проекта на 2 недели является найм дополнительных складских площадей по соседству, но это обойдется в 15 единиц в день (оплата услуги, перегрузки товара, доп. охрана и проч.). Какой срок сокращения длительности проекта оптимален по издержкам?

В сборнике сразу доступен ответ. Вот он.

Разбор условия задачи

Сначала несколько слов о стилистике формулирования условия (по мелочи). 

Работы по проекту называются то работами ("порядок выполнения работ"), то этапами. Будем называть их работами. Каждой работе соответствует точка на сетевой диаграмме с соответствующей буквой.

В ответе на вопрос а) приведен ответ о длительности проекта (65 дн.). Но, об этом нас не спрашивают в задании, спрашивают только о стоимости сокращения (109 условных единиц денег). Сразу возникает вопрос: "это изначальная длительность проекта или длительность после сокращения?". Выясним это в ходе решения.

Решение

Сначала рассчитаем изначальную длительность проекта. Сделаем это в MS Project. Для этого введем 21 работу, укажем их длительность и связи.

Работы, выделенные красным, лежат на критическом пути. MS Project показывает, что первые работы С, А, Е начинаются 01.01.2016, проект заканчивается 31.03.2016. Длительность проекта - 65 дней.

Напомним, что у проекта длительность может быть указана в календарных днях (31.03.2016-01.01.2016+1=91 дней) и в рабочих днях (без учета выходных, 65 дней). Так как длительность работ указана в рабочих днях, то и длительность проекта разумно вычислять в рабочих днях. Т.е. в ответе указана изначальная длительность проекта в рабочих днях.

Теперь вычислим стоимость сокращения проекта на 2 недели. Обратите внимание на формулировку - 2 недели, а не 14 дней! 2 недели - это календарные дни, т.е. с учетом выходных длительность проекта нужно сократить на 10 дней! Но, сейчас это только наша догадка. Построим модель в MS EXCEL и покажем, что на 14 рабочих дней проект нельзя сократить в принципе, а вот на 10 можно.

Построение модели

Как известно из условия задачи, существует возможность сократить длительность каждой задачи от 1 до 3 дней. Но, за это придется заплатить. Таким образом, нам нужно перебрать все варианты сокращения длительности проекта ровно на "2 недели", чтобы выбрать из них вариант, имеющий минимальную стоимость сокращения.

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

Сначала отправимся из работы (точки) С, затем D; G; J; N; R; U; Окончание. Т.е. обойдем сетевую диаграмму по самому верхнему пути. Последнюю веху Окончание можно не указывать, т.к. ее длительность равна 0. Второй путь располагается чуть ниже: С; D; G; K; O; R; U. Всего путей 7. Вот они.

Как рассчитать длительность путей показано в файле примера (ссылка внизу статьи). Для этого понадобится только простая формула на основе функции ВПР().

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

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

Как мы и предполагали, в этом случае сокращение общей длительности проекта составит 10 рабочих дней. Нет, конечно, это 2 календарные недели, но ведь и не 14 дней ))). Не сомневаюсь, что авторы сборника, очень креативные люди, которые формулируют заковыристые условия для студентов (чтобы те подумали), но, лично мое мнение, таких студентов не более 10%. Остальные просто запутаются и сдадутся не получив ответ. Тем более, что точный ответ (109 ед.) и получить-то проблематично в сегодняшних условиях. Об этом ниже.

Для нахождения оптимального варианта сокращения длительности проекта на 2 недели будем использовать инструмент MS EXCEL Поиск решения

Чтобы построить модель для Поиска решения (ПР) в EXCEL нужно определить 3 ее составляющих:

  •  целевая функция (то, что мы будем оптимизировать, например в нашем случае - минимизировать стоимость сокращения длительности проекта), это формула в одной ячейке (ячейку выделим красным);
  •  переменные модели, это то что будет изменять ПР в ходе поиска (ячейки выделим зеленым). В нашем случае - это вариант сокращения длительности каждой работы на 1, 2 или 3 дня;
  •  ограничения модели, например, вариант сокращения длительности работы должен быть только один (либо сократить на 1 день, либо на 2 (если можно по условию), либо на 3 (если можно) или вообще не сокращать) (ячейки выделим синим/голубым). Также потребуется несколько технических ограничений: все переменные должны быть бинарными, т.е. 0 или 1.

Заполним окно Поиска решения.

В качестве еще одного ограничения добавим, что длительность проекта должна сократиться ровно на 10 рабочих дней. Задача нелинейная, т.к. для вычисления целевой функции мы использовали функцию ВПР(), а не только линейные операции умножения и сложения. Запустим ПР с использованием нелинейного метода ОПГ. Через несколько секунд получим решение: 81 условная денежная единица. Т.е. меньше 109 ед.! 

Почему можно получить разные ответы с помощь Поиска решения (в нелинейном случае)? Причин может быть несколько.

1) Разные модели. Обе правильные (надеюсь), но разные;

2) Разные методы решения: Нелинейный метод ОПГ или Эволюционный;

3) Разные параметры решения (точность ограничения, число подзадач и т.д.), которые устанавливаются пользователем в окне ПР (кнопка Параметры).

4) Версия MS EXCEL. Алгоритм оптимизации надстройки Solver (Поиск решения) может отличаться в зависимости от версии. Так в EXCEL 2010 в надстройку был включен новый метод решения нелинейных задач Эволюционный поиск решения (Evolution solver), основанный на генетических алгоритмах. Возможно были внесены и другие изменения в алгоритм расчета нелинейных задач.

Например, мной с помощью Эволюционного метода был получен вариант со стоимостью сокращения 64! Это на 40% лучше ответа, приведенного в ответе сборника (это полностью заслуга разработчиков Поиска решения). Правда, эволюционный метод требует более тонких настроек параметров, в отличие от Нелинейного ОПГ, а также он считает дольше.

Но, может, 109 ед., приведенные в ответе, это просто ошибка? Существует ли такой вариант сокращения длительности работ, который приводит к такой стоимости? Да, существует и расчет приведен на листе Как в ответе в файле примера.

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

Расчет приведен на листе Задание Б в файле примера.

Сразу зададим себе вопрос: "Почему стоимость хранения на дополнительных складах составляет именно 15 ед., а не 100 ед. или 5 ед.". Понятно, что если эта стоимость будет слишком высока, то арендовать новые склады будет слишком дорого и бессмысленно (проще сократить проект на 2 недели за 64 ед.). Если наоборот, склады будут слишком дешевы, то тратить деньги на сокращение длительности проекта не имеет смысла, дешевле будет арендовать доп.склады.

Так как в нашем распоряжении более мощный Поиск решения, который позволяет найти очень эффективный (более дешевый) вариант сокращения длительности проекта, то 15 ед. будет слишком высокой ценой за склады. Выгоднее сокращать длительность проекта. Снизим стоимость аренды складов до 7 единиц и немного подкорректируем модель: общая стоимость минимизируемых затрат будет складываться из затрат на сокращение длительности проекта (как раньше) + затраты на хранение (хранить будем то количество дней, которое не хватает, чтобы сократить проект на 10 рабочих дней). Ниже приведен один из найденных вариантов: сокращение длительности - 5 дней, остальные 5 дней (10-5) храним на складе за 7 ед./день.

Конечно, в модели убрано одно из ограничений - количество дней, на которое нужно сократить проект, теперь оно не обязательно должно быть равно 10.

Связанные статьи

Похожие задачи
Прочитайте другие статьи, решающие похожие задачи в MS Excel. Это позволит Вам решать широкий класс подобных задач.
Средняя: 5 (2 оценок)