«Н.А. ЮКАЕВА КОЛИЧЕСТВЕННЫЕ МЕТОДЫ В МЕНЕДЖМЕНТЕ Учебное пособие Рекомендовано Дальневосточным региональным учебно-методическим центром в качестве учебного пособия для студентов вузов региона Владивосток 2010 Настоящее ...»

Федеральное агентство по образованию

Дальневосточный государственный технический университет

(ДВПИ им. Куйбышева)

Н.А. ЮКАЕВА

КОЛИЧЕСТВЕННЫЕ МЕТОДЫ

В МЕНЕДЖМЕНТЕ

Учебное пособие

Рекомендовано Дальневосточным региональным

учебно-методическим центром в качестве учебного пособия

для студентов вузов региона Владивосток 2010 Настоящее пособие предназначено для слушателей Президентской программы, студентов второго высшего образования, обучающихся по специальности “Экономика и управление на предприятии”, а так же для студентов всех специальностей, изучающих предметы “Исследование операций”, “Математические методы в экономике” и др.

В пособии, в кратком изложении, содержатся основные сведения о методах математики, которые можно применять для численного решения задач экономики.

Рассмотрены методы линейной оптимизации, количественные методы управления запасами и методы управления проектами. Для анализа примеров использованы электронные таблицы MS-Excel. При рассмотрении темы управления проектами привлекается MS-Project. Изложение основано на рассмотрении реалистичных управленческих ситуаций, их формализации, оптимизации и анализе с использованием компьютерных методов.

Количественные методы в менеджменте Предисловие Курс “Количественные методы в менеджменте” – обязательная часть программы профессиональной подготовки и переподготовки современных управленцев. В нм рассматриваются модели и методы оптимизации управления и принятия решений. Основой курса является раздел математики “Исследование операций”. Все эти модели и методы возникли как ответ науки на заказ от бизнеса, поэтому распространены на практике.

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

Количественные методы позволяют просчитать последствия выбора различных альтернатив решения и выбрать наилучшую альтернативу, т.е.

количественные методы применяются в менеджменте для повышения эффективности управления.

Основная задача курса “Количественные методы в бизнесе” состоит в том, чтобы подготовить менеджеров к использованию методов для принятия эффективных управленческих решений.

Цели курса “Количественные методы в бизнесе” в программах МВА научить специалистов правильно применять готовые компьютерные программы, разработанную технику анализа количественных моделей управления для принятия эффективных управленческих решений. При этом специалист должен уметь построить модель, определить е входные и выходные параметры, а также провести анализ результатов и принятия лучшего решения.

Для реализации отмеченных целей, в основу преподавания курса положены:

а) анализ практических управленческих проблем и ситуаций (кейсов); б) необходимость решать поставленные задачи и анализировать их результаты, т.е.

проводить анализ чувствительности решения к изменениям входных параметров задачи. Для более эффективного анализа примеров предлагается использовать программу электронных таблиц MS-Excel с несколькими дополнительными надстройками к ней и MS Project. Весь материал курса разбит на пять частей.

Часть первая. “Оптимизация в условиях полной определнности”. Методы линейной оптимизации.

Часть вторая. Транспортные задачи и логистика. Задачи о назначениях и отборе.

Часть третья. Сетевые модели, оптимизация на графах и сетях.

Планирование и анализ проектов.

Часть четвртая. Теория игр. Методы принятий решения в условиях неопределнности и риска.

Часть пятая. Оптимальное управление запасами.

Часть І Оптимизация в условиях полной определнности 1.1. Метод линейной оптимизации В этой части рассмотрены теория и примеры использования количественных методов и моделей, цель которых – найти оптимальную стратегию управления в условиях, когда все параметры и правила управления системой чтко определены и не подвержены никаким случайным воздействиям. В таких задачах используется метод линейной оптимизации, цель которого – составление оптимальных планов производства, продаж, закупок, перевозок, оптимальное финансовое планирование, оптимальная организация рекламных кампаний и др. Планирование – одна из основных функций менеджмента.

Примеры ЗЛО. 1). Оптимальный производственный план. Пусть предприятие может производить несколько видов продукции А1, А2,…, Аn. Для производства каждого вида из них, требуется разное количество одних и тех же ресурсов B1, B2,…, Bn (материалы, электроэнергия, рабочая сила и т. д.). Продажа одного изделия каждого типа приносит определенную прибыль с 1, с2,…,сn. Так как из имеющихся на предприятии ресурсов можно ежедневно производить различное количество изделий, то и прибыль будет неодинаковой. Отсюда, может существовать множество различных производственных планов, каждому из которых соответствует определенное значение прибыли P и определенный расход каждого ресурса, который в свою очередь может быть ограниченным. В задаче требуется найти такой вариант производственного плана, при котором прибыль была бы максимальной.

2). Организация транспортных перевозок. Пусть имеется сеть оптовых баз А1,А2,…,Аm, с которых однотипная продукция может доставляться потребителям в магазины B1,B2,…,Bn. Продукцию можно привезти с любой базы Ai в любой магазин Bj. Стоимость перевозки единицы груза разная, она известна и для любой пары AiBj равна cij. Ясно, что лучше выбирать такие пары (база-магазин), для которых эта стоимость наименьшая. Запасы продукции на базах, а также потребности магазинов ограничены. В задаче требуется составить план перевозок {Хij}, чтобы суммарные транспортные расходы P были наименьшими, а также удовлетворены все требования потребителей, а груз, имеющийся на базах, весь вывезен.

3). Выбор инвестиционных проектов. Инвестиционный отдел банка рассматривает множество возможных проектов вложения денег на следующий год J1, J2, …, Jn. Каждый проект в конце года должен принести определенную прибыль P1, P2,…, Pn. Для каждого проекта определен количественный индекс надежности r1, r2,…,rn. Каждый проект Ji в течение года требует определенное ежемесячное финансирование а, а,…,а. Банк рассчитывает, что его денежные поступления в следующем году составят S1, S2,…, S12 д.ед. Какие проекты выбрать, а какие отвергнуть, чтобы планируемого притока наличности хватило для финансирования отобранных проектов?

4). Реклама и маркетинг. Рекламная компания хочет, чтобы е рекламные объявления достигли, по крайней мере, 1 млн. человек. Она планирует провести рекламу через местное TV, радио, почту, газеты и электронную почту. Известна маркетинговая оценка эффективности рекламы в различных каналах, данные о количестве объектов, размещения рекламы, средней аудитории, охватывающей данные СМИ и цены на рекламную акцию. Компанию интересует минимальная стоимость рекламы, а также, сколько денег следует вложить в каждый канал.

Можно привести еще ряд примеров, но все они имеют некоторые общие черты, их можно объединить по составлению математической модели.

Область исследования операций, которая занимается оптимизацией, называется математическим программированием. Теоретической основой линейной оптимизации (ЛО) является линейное программирование, которое является одной из составляющих математического программирования. Модели линейного программирования очень важны, так как много задач в самых разных сферах деятельности, которые могут быть проанализированы с помощью моделей линейного программирования. Существуют эффективные и универсальные алгоритмы решения ЗЛП, реализованные на ЭВМ, а также, методы анализа моделей ЛП позволяют исследовать модель на чувствительность при изменении е параметров.

Постановка ЗЛО. При построении математической модели задачи линейной оптимизации, прежде всего, необходимо определить количественную характеристику цели, которой надо достичь в процессе оптимизации, - целевую функцию. Это может быть максимальная прибыль или минимальные издержки (в денежном, временном или в каком-либо другом выражении). Целевая функция показывает, почему одно рассматриваемое решение лучше или хуже другого.

Целевая функция зависит от величин, называемых переменными решения (неизвестными), которые можно изменять, разыскивая оптимальное решение.

Цель оптимизации – найти такие значения переменных решения, при которых целевая функция достигает максимума или минимума.

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

а) вторичными целями (например, рассматривая задачу о минимизации рисков инвестиционного портфеля, мы, одновременно, хотим добиться ожидаемой прибыли);

б) ограниченностью ресурсов, находящихся в распоряжении (денежных, временных, материальных и др.);

в) установленными “правилами игры” (рыночные ограничения, нормативные акты, любые требования субъекта, принимающего решения и т.д.) Любой набор переменных решения, удовлетворяющих ограничениям, называют допустимым решением (или допустимым планом). Таких планов может быть множество. Допустимое решение, которое отвечает наибольшему или наименьшему значению целевой функции, называется оптимальным решением.

Обычно это решение одно, но встречаются модели, когда одному оптимальному плану соответствует множество допустимых решений.

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

В линейных моделях, кроме неизвестных, присутствуют постоянные числа, их называют параметрами. Параметры модели (например, тарифы перевозок) определяют вид и значение целевой функции, оптимальное решение также зависит от параметров модели, т.е. если их изменить, изменится и оптимальное решение.

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

Для решения задач ЛО можно использовать надстройку к программе электронных таблиц MS Excel, которая называется “Поиск решения”.

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

Существуют эффективные и универсальные алгоритмы решения ЗЛП, реализованные на ЭВМ, а также, методы анализа моделей ЛП позволяют исследовать модель на чувствительность при изменении е параметров.

Математическая модель ЗЛО. Рассмотрим “Линейную модель оптимального планирования”.

Мини-кейс : “Оптимальный план производства”.

Задача №1.1 “Оптимальный план выпуска продукции мебельного цеха” Цех может выпускать два вида продукции: шкафы и тумбы для телевизора.

На каждый шкаф расходуется 3,5м стандартных ДСП, 1м листового стекла, и человека-день трудозатрат. На тумбу расходуется 1м ДСП, 2м стекла, и человеко-день трудозатрат. Прибыль от продажи 1 шкафа составляет 200у.е., а тумба – 100у.е. Материальные и трудовые ресурсы ограничены: в цехе работают 150 рабочих, запасы ДСП на день составляют 350м, а стекла – 240м. Какое количество шкафов и тумб должен выпустить цех, чтобы получить максимальную прибыль? Оформим данные задачи в виде таблицы 1.1.

Таблица 1.1. Параметры задачи №1. Решение. 1) Прежде всего определим цель задачи и вид целевой функции. В данном случае мы хотим максимизировать прибыль, следовательно, целевая функция должна вычислять полную прибыль. В задаче задана прибыль, которую приносит каждый вид произведнной мебели. Поэтому полная прибыль P будет определяться этой прибылью и количеством произведнной мебели каждого вида.

Пусть X и Y – соответственно количество шкафов и тумб, выпускаемых цехом.

Прибыль от продажи одного шкафа равна 200у.е., значит, прибыль от продажи X шкафов будет 200X. Аналогично прибыль от продажи Y тумб равна 100Y. Общая прибыль от продажи шкафов и тумб будет равна P=200X+100Y. Глядя на выражение целевой функции, можно легко увидеть, что, чем больше будут значения X и Y, тем больше будет прибыль P. Но увеличивать беспредельно ежедневный выпуск шкафов и тумб невозможно, так как ресурсы ограничены.

2. На этом этапе надо выяснить, при каких ограничениях надо найти максимальную прибыль. Запишем эти ограничения. Начнем с трудовых ресурсов.

Поскольку каждый рабочий за 1 день может сделать либо 1 шкаф, либо 1 тумбу, ясно, что общее количество выпущенных изделий не должно превышать числа рабочих в цехе. То есть, общий расход труда на X шкафов и Y тумб, будет 1X+1Y150. Аналогично записывается неравенство, отражающее ограниченность ежедневных запасов ДСП. Поскольку на 1 шкаф расходуется 3,5м ДСП, а на тумбу – 1м, то суммарный расход ДСП будет 3,5X+Y, что не должно превышать ежедневного запаса ДСП в цехе, т.е. 350м. Получим неравенство 3,5X+Y350. Рассуждая точно также относительно третьего ресурса – стекла, получим ограничение 1X+2Y240. Осталось добавить, что переменные решения не могут быть отрицательными, X0,Y0.

Получим математическую модель ЗЛО или ЗЛП.

Найти max P=200X+100Y, при ограничениях:

Определение переменных решения, целевой функции и ограничений – это почти все, что должен сделать менеджер, чтобы воспользоваться результатами оптимизации и анализа линейной модели. Дальше необходимо только правильно организовать данные для компьютера на листе MS Excel и запустить задачу на решение.

При организации данных ЗЛП на листе MS-Excel следует отвести отдельные ячейки для параметров, переменных, целевой функции и левых частей ограничений. Ячейки для переменных можно оставить пустыми или ввести в них любые допустимые значения переменных, а в ячейки для целевой функции и ограничений ввести формулы, отражающие их функциональную зависимость от переменных и параметров.

Требование линейности означает, что и целевая функция, и ограничения могут представлять собой только суммы произведений коэффициентов на переменные решения. В MS-Excel имеется стандартная математическая функция СУММПРОИЗВ (или SUMPRODUCT), позволяющая быстро вычислять такие суммы произведений. Далее на листе MS-Excel надо сделать все необходимые расчты для задания ограничений. Когда будем иметь всю информацию, необходимую надстройке “Поиск решения”, приступаем к решению.

1. Организовать данные на листе MS-Excel: а) ввести целевую функцию P=200X+100Y; б) ввести формулы, отражающие расход ресурсов.

Для этого надо:

2. Выбрать пункт меню “Сервис” (Tools), внутри найти пункт “Поиск решения” (Solver). В появившемся диалоговом окне следует задать параметры поиска, а именно: а) в окошке “Установить целевую ячейку” указать ячейку, содержащую целевую функцию; б) установить переключатель на отметке “Равной максимальному значению”; в) в поле окна “Изменяя ячейки” указать ячейки, соответствующие переменным решения; г) щелкая по кнопке “Добавить”, ввести ограничения в окне “Добавление ограничения”.

3. Щелкнуть по кнопке “Параметры”, в появившемся окне “Параметры поиска решения” установить “Линейная модель”. Вернуться к окну “Поиск решения”.

4. Щелкнуть по кнопке “Выполнить”. Оптимизационная программа MS Excel выполнит поиск решения, после чего появится окно “Результаты поиска решения”. Если все сделано правильно, программа сообщит: “Решение найдено.

Все ограничения и условия оптимальности выполнены”.

5. В этом случае надо “Сохранить найденное решение”.

В случае если программа не может найти решения, надо вернуться в положение “Восстановить исходные данные” и проверить организацию данных на листе Excel.

Организация данных задачи об оптимальном плане производства мебельного цеха с помощью MS-Excel смотрите в таблице 1.2.

Таблица 1.2. Организация данных задачи №1.1 на листе MS Excel

А B C D E F G

Решение задачи определения оптимального плана мебельного цеха в табл. 1.3.

Таблица 1.3. Результаты решения примера №1.1 на листе MS Excel

А B C D E F

Оптимальный план производства мебельного цеха В случае если оптимизационная программа не может найти решение, в окне появится сообщения: “Значения целевой ячейки не сходятся” или “Поиск не может найти решения”, или “Условия линейной модели не выполняется”. В этом случае надо переставить переключатель в окне “Результаты поиска решения” в положение “Восстановить исходные данные”, щлкнуть по кнопке Ok и проверить организацию данных на листе Excel и в установках окна “Поиск решения”.

Возможно, неверно задан знак ограничений, или неверно введены формулы для целевой функции и ограничений.

Графическое решение задачи “об оптимальном плане выпуска продукции В задаче требовалось найти максимум целевой функции:

Алгоритм решения задачи. 1) Строим область допустимых решений задачи, определяемую системой неравенств (1.2). Для этого построим линии, изображающие предельные расходы ресурсов за день: 3,5x1+x2=350, x1+2x2=240, x1+x2=150.

Получим многоугольник решений ОАВС, имеющий конечное число угловых точек (рис.1.1).

2) Строим одну из линий уровня, соответствующую целевой функции (1), проходящую через т. О (так называемую линию постоянной прибыли).

3) Находим вектор-градиент функции (1), p(, По своим свойствам, вектор-градиент указывает в сторону роста целевой функции и перпендикулярен к линии уровня (1.3).

4) Строим линию наивысшего уровня целевой функции, для этого перемещаем линию (3) в направлении вектора p через многоугольник решений.

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

5) Находим координаты этой точки и вычисляем значение в ней целевой функции. У нас максимальное значение целевой функции достигается в т. С, P (max)=20080+10070=23000(у.е.) 1.2. Анализ оптимального решения задачи линейного Хотя сам оптимальный план очень полезен, часто бывает интересно знать, как можно изменить те или иные параметры системы (до этого постоянные), чтобы улучшить решение, получить еще большую прибыль или уменьшить издержки. Значение параметров определяет оптимальное значение переменных и целевой функции. С целью улучшения решения многие параметры могут быть изменены. В наших примерах трудно поменять параметры, характеризующие технологический процесс, но изменить количество ресурсов (запасы), а также отпускные цены на товары вполне возможно. Обычно это связывают с привлечением дополнительных финансовых ресурсов, при этом необходимо ответить на ряд вопросов:

- какой ресурс наиболее сильно влияет на изменение прибыли (издержек)?

- как изменится решение и целевая функция при изменении количества того или иного ресурса?

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

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

Поиск ответов на подобные вопросы и составляет сущность анализа решения. В задачах ЛП существенную информацию о влиянии изменений параметров можно получить из “отчета об устойчивости” в ходе поиска решения в MS-Excel. Для ответа на другие вопросы типа “что, если” необходимо дополнительное исследование. Некоторое представление о том, как может меняться решение ЗЛП при изменении параметров, можно получить из анализа графического решения задачи.

I. Изменение оптимального решения при изменении целевых коэффициентов В задаче №1.1 целевая функция имеет вид: P=200x1+100x2.

Если уменьшить цену шкафа от 200у.е. до 150у.е. и далее до 50у.е., линия уровня будет менять наклон. Проведем линию уровня 200x+100x=10000, (1) на рис.1.1, а теперь 150x+100x=10000, (2) на рис.1.1. В этом случае т.C остается оптимальной. Изменим цену шкафа на 50у.е., оптимальной станет т.B(60;90).

Отсюда вывод: “существует определенный интервал устойчивости, в котором изменение целевых коэффициентов не приводит к изменению оптимального решения”. Конечно, значение целевой функции в точке оптимума изменится (за счет коэффициентов). Но дальнейшее изменение коэффициентов целевой функции (цены) может привести к изменению оптимального решения и целевой функции. Т.е., если значение целевого коэффициента выходит за пределы интервала устойчивости, оптимальное значение резко изменится, перейдет в другую угловую точку области допустимых планов. В этом случае надо заново решать ЗЛП.

В нашей задаче, если C1=150; C2=100; P=15080+10070=12700.

Вывод: 1. Изменение коэффициентов целевой функции cj не изменяют область допустимых решений. В этом случае изменяется вектор p gradF(x) и направление линий уровня, изображающих целевую функцию.

1. До тех пор, пока изменение наклона вектора p gradF(x) не превышает некоторых пределов, оптимальное решение задачи x *j не меняется, значение самой целевой функции конечно изменится.

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

4. “Допустимое увеличение” и “Допустимое уменьшение” для каждого целевого коэффициента cj, при котором оптимальное решение не изменится, приводится в табл.1.4 “Изменяемые ячейки” отчта Excel об устойчивости. Как его получить, читайте ниже. При этом: а) если xj0, т.е. товар входит в оптимальный план, имеется верхний и нижний пределы для изменения соответствующего j - того коэффициента целевой функции; б) если xj=0, то ”Допустимое уменьшение” может быть как угодно велико (товар вс равно не войдт в оптимальный план). Верхний предел “Допустимое увеличение” покажет, насколько надо увеличить cj, чтобы j – тый продукт вошл в оптимальный план.

Величина, противоположная этому увеличению, называется нормированной стоимостью и показывает, насколько нынешняя цена товара ниже минимальной цены (или издержки выше максимальной), при которой этот товар может войти в оптимальный план. Если некоторый продукт не входит в оптимальный план, его нормированная стоимость 1, оптимальное решение x *j изменится, если 0.

т.е. i – ресурс не полностью использован при производстве продукции по оптимальному плану, то его теневая цена равна нулю: yi=0.

в) Если xj>0, т.е. j–й продукт вошл в оптимальный план, то в соответствующем ограничении двойственной задачи реализуется знак равенства, это соответствует тому, что выручка от продажи ресурсов, идущих на производство единицы этого продукта, равна прибыли от его производства:

г) Если xj=0, т.е. j–й продукт не входит в оптимальный план, то в соответствующем ограничении двойственной задачи реализуется знак “>”, что означает – выручка от продажи ресурсов, идущих на производство единицы этого продукта, больше прибыли от е производства:

3. Теневые цены yi показывают, на сколько увеличится значение Pmax, если запасы ресурса увеличить на единицу:

Убедимся в этом на нашем примере.

II. Изменение оптимального решения при изменении правых частей Для практического использования теневых цен в решении задачи оптимального управления надо связать ценность ресурсов (теневые цены) и прибыль от производства. Увеличим запас одного из ресурсов, например, ДСП на малую величину b1=1, т.е. b1=351. Но b1, b2, b3 – это коэффициенты целевой функции двойственной задачи. Как было сказано ранее, при изменении целевых коэффициентов существует некоторый интервал устойчивости. Если значение изменнного коэффициента остатся внутри интервала устойчивости, оптимальное решение не изменится, т.е. изменение ресурса ДСП на единицу не приведт к изменению цен y1, y2, y3. Целевая функция при этом увеличится и составит Но Сmin Pmax, это означает, что прибыль от производства увеличится на Отсюда вывод: “теневая цена” ресурса показывает, насколько увеличится прибыль от производства при увеличении данного ресурса на единицу.

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

1. При решении симплекс-методом исходной задачи сразу же решается и двойственная задача. Отчт Excel об устойчивости включает таблицу “Ограничения” и в ней колонку “Теневая цена”. Теневые цены – это оценки Yi двойственной задачи. Они показывают, как меняется целевая функция при малом изменении bi: P=Yibi (см. ниже).

2. Эти оценки верны только в пределах устойчивости решения, т.е. пока изменение bi не изменяет угловую точку области допустимых решений, в которой достигается максимум целевой функции. При этом численные значения переменных решения Xj, конечно, изменяются. При выходе bi за пределы устойчивости все теневые цены изменятся.

3. Пределы изменения правых частей системы ограничений (bi), в которых оптимальное решение соответствует той же самой угловой точке, тоже даны в таблице “Ограничения”. Это столбцы - “Допустимое увеличение” и “Допустимое уменьшение” (табл. 1.4). Причем, если ресурс используется полностью (дефицитный), то существует как верхний, так и нижний пределы. Если же ресурс используется не полностью, верхний предел устойчивости равен бесконечности (1030).

4. Пределы устойчивости для изменения bi даются при условии, что все остальные значения bk (k i) остаются неизменными, иначе будут меняться теневые цены.

5. Для оценки влияния одновременного изменения нескольких значений bi следует вычислить относительные изменения для каждой правой части системы ограничений, где max bi – это предел либо увеличения, либо уменьшения bi (в зависимости от знака bi), и вычислить сумму этих относительных изменений. Если эта сумма больше 1, теневые цены изменятся, если – меньше 1, то не изменятся.

Рассмотрим на нашей задаче “Об оптимальном плане мебельного цеха” как повлияет изменение запасов некоторых ресурсов. Ответим на следующий вопрос:

Как изменится целевая функция (прибыль) при изменении запасов ресурса bi? Все вычисления внесм в табл. 1.7.

Таблица 1.7. Расчет прибыли при изменении запасов ресурсов Уменьшить запас стекла на 20м. 220м P4= Уменьшить ресурс труда на 40ч/дн 110ч P5=- Эти расчеты получены согласно интервалам устойчивости по ресурсам (табл.1.4), а именно: ДСП(350-50;350+175), стекло(240-20; ), труд(150-50; 150+8,333).

Рассмотрим более сложные примеры задач ЛП, с большим количеством переменных решения, которые позволят продемонстрировать дополнительные технические приемы, полезные при исследовании моделей линейного программирования.

Задача №1.3 “На кондитерской фабрике”. Небольшая кондитерская фабрика должна закрыться на реконструкцию. Необходимо реализовать оставшиеся запасы сырья для производства конфет из ассортимента фабрики, получив максимальную прибыль. Запасы и расход каждого вида сырья для производства единицы продукции каждого вида, а также получаемая при этом прибыль представлены в таблице 1.6. Мастер цеха, используя свой большой опыт, предлагает выпустить по 200 пакетов каждого вида конфет из ассортимента, утверждая, что ресурсов должно хватить, а прибыль получится 1080у.е. Молодой менеджер, только что окончивший экономический институт, утверждает, что такие проблемы не решаются на глазок, а с помощью линейного программирования. Хозяин фабрики обещает менеджеру всю прибыль сверх 1080у.е., если он предложит лучший план, чем многоопытный мастер. Все параметры занесм в таблицу 1. Таблица 1.8. Основные параметры задачи “На кондитерской фабрике” Математическая модель задачи №1.3. За переменные решения примем количество пакетов каждого из 5 видов конфет, выпускаемых фабрикой.

Обозначим их как Xi, i=1,2,3,4,5. Тогда целевая функция, прибыль от производства данного количества пакетов каждого вида продукции, будет равна P=1X1+0,7X2 +1,1X3 +2X4 +0,6X5.

Ограничения на переменные: расход каждого вида сырья (в кг) на производство одного пакета каждого продукта можно найти на пересечении строки (сырье) и столбца (продукта) в таблице параметров. Это так называемые технологические коэффициенты производства. Расход темного шоколада на X1, X2, X3, X4, X5 пакетов каждого их продуктов не должен превышать запаса этого ресурса. Т.е. ограничение на темный шоколад будет иметь вид:

Аналогично можно получить ограничения по другим ресурсам, кроме того, из экономического смысла задачи следует, что все Xi0.

Решение мини-кейса “На кондитерской фабрике” с помощью MS-Excel Организуем данные на листе MS-Excel так, как это показано в табл.1.9.

Таблица 1.9. Организация данных на листе MS-Excel задачи ”На кондитерской фабрике”

A B C D E F G

Темный шок. =Суммпроизв($C$13:$G$13;C4:G4) Светлый шок. =Суммпроизв($C$13:$G$13;C5:G5) Карамель =Суммпроизв($C$13:$G$13;C7:G7) В ячейках с C13 по G13 содержатся переменные решения. В ячейки B16 по B20 введены формулы, отражающие расход ресурсов на единицу каждого продукта. Повторив алгоритм решения задачи с помощью MS Excel (зад. № 1), получим решение. После команды “Выполнить” в ячейках с C13 по G (табл.1.10) можно прочесть ответ. Поскольку количество произведенных пакетов должны быть целыми числами, надо округлить значения полученных переменных до целых так, чтобы ограничения на ресурсы были строго соблюдены. В ячейках с C13 по G13 содержатся значения расходов ресурсов, которые необходимы для получения оптимального плана.

Таблица 1.10. Результаты решения задачи “На кондитерской фабрике”

A B C D E F G

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

больше, чем по плану мастера, т.е. он заработал более 400 у.е., с другой стороны, в оптимальный план не вошл его любимый “Батончик”. Как исправить ситуацию.

Менеджеру необходимо ответить на следующие вопросы:

1. Как надо изменить норму прибыли для “Батончика”, чтобы он вошл в оптимальный план?

2. Если ввести это изменение в данные и решить задачу заново, как изменится оптимальный план?

3. Какой ресурс является наиболее дефицитным (т.е. максимально влияет на прибыль)?

4. Можно ли сказать (не решая задачу снова), как изменится прибыль от производства, если количество этого ресурса оценено: а) с избытком в 10 весовых единиц; б) с недостатком в 5 единиц?

5. Есть ли другой способ добиться производства “Батончика” кроме изменения нормы прибыли?

Для того, чтобы ответить на эти вопросы, необходимо получить отчт об устойчивости MS-Excel (табл. 1.11).

Таблица 1.11. Отчт об устойчивости MS Excel задачи “На кондитерской фабрике” Отчт об устойчивости решения задачи “На кондитерской фабрике” Изменяемые ячейки Переменные Ограничения Имя (расход) Ответ на вопросы 1 и 2. Согласно отчту об устойчивости (табл. 1.10), нормированная стоимость конфеты “Батончик”, не вошедшей в оптимальный план, составляет 0,00874у.е. Абсолютная величина этого числа показывает, на сколько надо увеличить прибыль от одного пакета этих конфет, чтобы “Батончик” вошл в оптимальный план. Для этого решим задачу ещ раз, изменив один параметр, а именно, увеличив цену “Батончика” на 0,01у.е. В этом случае прибыль станет равной 1,11у.е. (табл. 1.12).

Таблица 1.12. Оптимальный план задачи “На кондитерской фабрике” Видим, что малые изменения параметров приводят к серьзным изменениям решения. Для сравнения, ниже прибыли, записаны результаты с прежней ценой на “Батончик”. В этом случае говорят, что решение задачи неустойчиво. Решение называется неустойчивым, если малые изменения параметров приводят к огромным изменениям решения. Эта неустойчивость особенно опасна при рассмотрении методов выбора решения в условиях риска. В нашей задаче прибыль в обоих случаях почти одинаковая, т.е. неустойчивость решения не страшная.

Если ввести целочисленные ограничения на количество пакетов каждого вида продуктов, или потребовать ограничение: количество пакетов “Батончика” было не менее 100, 200, 300, получим альтернативные решения, сильно различающиеся по значениям переменных, но очень близких по прибыли. Это хорошо, т.к.

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

Ответ на вопросы 3 и 4. Для ответа на эти вопросы посмотрим отчт об устойчивости (табл.1.11). Согласно ему, наибольшей теневой ценой обладает ресурс - “светлый шоколад”. Но интервал устойчивости, соответствующий этой цене, очень маленький (149-11,87;149+1,04). Если запас этого ресурса уменьшить на 10 ед., то реальная прибыль будет ниже:

Эту формулу можно использовать, так как b2=-10 попадает в интервал устойчивости. Если запас данного ресурса увеличить на 5 ед., предсказать увеличение прибыли нельзя, т.к. b2=5 выходит за рамки интервала устойчивости.

В этом случае задачу надо решать заново.

Ответ на вопрос 5. Необходимо обратить внимание на то, что какой-либо из ресурсов для производства “Батончика” является дефицитным и востребован другим продуктом. “Батончик” конкурирует с “Белкой” за ресурсы: сахар и орехи.

Расход этих ресурсов на эти два продукта наибольший. Увеличение запасов этих ресурсов может привести к вхождению “Батончика” в оптимальный план. Так, если увеличить запасы сахара на 40 ед. и заново решить задачу на максимум, получим новый оптимальный план, где “Батончика” будет произведено более пакетов, прибыль при этом будет P=1547,8 у.е.

В окне ”Добавление ограничения” существует возможность потребовать целочисленности переменных решения. Для этого надо из предлагаемых ограничений выбрать ограничение “цел”. Решение ЗЦЛП в Excel делает невозможным получение информации об устойчивости решения и о теневых ценах. Поэтому “Поиск решения” MS Excel не формирует отчта об устойчивости, если хотя бы для одной переменной введено условие целочисленности.

Рассмотрим задачу.

Мини-кейс “Производство деталей для автомобилей” Задача №1.4. Завод – производитель высокоточных элементов для автомобилей выпускает два различных типа деталей в количествах X и Y. Завод располагает фондом рабочего времени в 4000 чел. час в неделю. Для производства одной детали 1-го типа требуется 1 чел. час в день, а для производства одной детали 2-го типа – 2 чел. час в день. Производственные мощности завода позволяют выпускать максимум 2250 деталей 1-го типа и 1750 деталей 2-го типа в неделю. Каждая деталь 1-го типа требует 2кг металлических стержней и 5кг листового металла, а деталь 2-го типа – 5кг металлических стержней и 2кг листового металла Уровень запасов каждого вида металла составляет 10000кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей 1-го типа своему постоянному заказчику. Существует профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук. Сколько деталей каждого типа надо производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали 1-го типа составляет $30, а второго - $40. Решить задачу в MS-Excel, найти интервалы устойчивости для запасов ресурсов и цен на детали.

Математическая модель задачи. Общий доход за неделю P 30 x 40 y Найти max P 30x 40 y при ограничениях:

Решение задачи в табл.1.13, отчт об устойчивости в табл.1.14.

Таблица№1.13. Решение задачи №1. Производство деталей Таблица №1.14. Отчт об устойчивости задачи №1. Изменяемые ячейки Ограничения Итак: прибыль завода $95000 в неделю, для этого надо изготовить деталей 1-го типа и 1250 деталей 2-го типа.

Задача №1.5. На тему: “Оптимальный состав смеси”. Фармацевтическая компания исследует возможность продвижения на рынок новой пищевой добавки, которая должна содержать микроэлементы: железо, кальций и фосфор. Добавка может быть получена путм смешивания ингредиентов, которые компания обозначает: Т5, N1 и Т4. Количество трх микроэлементов (мг на 100мл), содержащихся в каждом из ингредиентов, минимальный и максимальный уровень каждого микроэлемента в 1,2 – литровой бутылке и издержки на производство мл каждого ингредиента приведены в табл. 1.15. Менеджер хочет найти комбинацию ингредиентов в пищевой добавке, минимизирующие издержки на их производство. Составить математическую модель задачи и решить е. Менеджер внс предложение продавать компонент N1 по 0,7руб за 100мл. В этом случае новую пищевую добавку придтся готовить только из смеси Т5 и Т4. Стоит ли принимать это решение?

Таблица 1.15. Данные задачи №1.5.

Издержки Решение задачи №1.5. Составим математическую модель задачи.

Пусть X1(мг) – количество ингредиента T5 в пищевой добавке на 100мл;

X2(мг) – количество ингредиента N1 в пищевой добавке на 100мл;

X3(мг) – количество ингредиента T4 в пищевой добавке на 100мл.

Целевая функция F – издержки на производство 100 мл пищевой добавки.

Тогда F= 0,75X1+0,60X2+0,55X3.

В задаче надо найти minF при ограничениях:

где 8,33–минимальный уровень железа в 100мл (100/12=8,33), т.к.

1,2л=1200мл; 12,5 – максимальный уровень железа в 100мл (150/12=12,5) и т.д.

Решая задачу в MS-Excel, получим следующий результат (табл. 1.16).

В расчте на бутылку, содержащую 1,2 л, ответ будет следующим:

Fmin =36,598*12=439(руб); при этом X1=0; X2=143(мг); X3=643(мг).

В таблице 1.17 напечатан отчт об устойчивости задачи №5.

Согласно отчту по устойчивости, существует интервал изменения целевых коэффициентов (стоимость ингредиентов). Так, для N1 интервал – (0,6-0,1875;0,6+0,1333)=(0,4125;0,7333). Это означает, увеличение стоимости N до 0,7руб за 100мл, не меняет оптимальный план. Но целевая функция увеличится, станет равна 37,784 руб (за бутылку 453,5руб), т.е. издержки будут больше, а значит продавать кальций по 0,7 руб за 100 мл не выгодно.

Таблица 1.16. Результаты решения задачи №1. Таблица 1.17. Отчт об устойчивости задачи №1. Изменяемые ячейки Ограничения Но на практике встречаются задачи, в которых необходимо введение условия целочисленности. Например, задачи, требующие решить, какие элементы из большого их набора нужно выбрать (“брать, не брать”), чтобы оптимизировать целевую функцию. К такой схеме сводятся некоторые задачи, например, при выборе оптимального набора проектов для инвестирования, оптимального набора мест размещения новых предприятий, проблема постоянных издержек при выборе оптимального плана производства и т.п. Во всех этих случаях необходимо ввести специальную целочисленную переменную, которая может принимать только два значения: 0 и 1. Такие логические переменные в математике называют “булевыми” переменными. В качестве примера рассмотрим задачу “Об оптимальном плане размещения предприятий”.

Задача №1.6. На тему: “Оптимальный план размещения предприятий” Управляющий таксомоторной компанией хочет определить оптимальное расположение для стоянок своих такси. В таблице 1.18 собрана необходимая информация относительно предполагаемых точек стоянки. Важной характеристикой положения стоянки является способность персонала своевременно обслуживать заказы из тех районов города, которые находятся в зоне ответственности данной стоянки. Машина должна прибывать по заказу за время не превышающее некоторое максимальное.

Таблица 1.18. Информация о стоянках Точка стоянки Обслуживающие районы Стоимость аренды, Из таблицы видно, места для стоянок позволяют обслужить по 2 или района города. Управляющий должен выбрать некоторые из них так, чтобы каждый район города мог быть обслужен хотя бы одной из стоянок, и чтобы стоимость аренды была минимальной.

Математическая модель задачи №1.6. Занумеруем районы в очевидном порядке: A-1; B-2; C-3; D-4; E-5. Введм булевы параметры aij, равные 1, если с i й стоянки можно обслужить j - й район, и равные нулю – если нельзя. Значения aij приведены в таблице параметров (табл.1.19). Введм также переменные решения Xi, принимающие только значения 1 или 0 в зависимости от того, выбрана данная точка стоянки управляющим или нет.

Таблица 1.19. Параметры задачи об оптимальном размещении стоянок такси Целевой функцией в данной задаче являются затраты на выбранные места аренды. Очевидно это:

В качестве ограничений нужно подсчитать, сколько выбранных стоянок могут обслужить данный район. Для района (А) число стоянок будет:

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

Организация данных на листе MS-Excel. Для практического решения задачи с помощью MS-Excel организуем данные так, как показано в табл.1.20.

Таблица 1.20. Организация данных задачи № 1.6 на листе MS-Excel

A B C D E F G H

Оптимальный план размещения стоянок После введения целевой функции: Суммпроизв($H$5:$H$9;G5:G9) в ячейку C10 и ограничений Суммпроизв($H$5:$H$9;B5:B9), распространив формулу на все районы (ячейки C10:F10), надо в установках “Поиска решений” ввести требования для булевских переменных, а именно:

После вызова “Поиск решения” и выполнения необходимых установок получим решение в ячейках H5:H9, в ячейке D10 найдм значение целевой функции (табл. 1.21), а в ячейках B10:F10 значения чисел Ni (число районов, обслуживаемых каждой стоянкой).

Таблица 1.21. Решение задачи об оптимальном плане размещения стоянок такси Оптимальный план размещения стоянок Введение ограничения целочисленности переменных не позволит получить информацию об устойчивости решения и о теневых ценах.

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

Мини-кейс ”Оптимизация инвестиционного портфеля” Задача №1.7. Частный инвестор предполагает вложить 500 тыс. рублей в разные ценные бумаги. После консультаций со специалистами фондового рынка он отобрал три типа акций, два типа государственных облигаций. Часть денег предполагает положить на срочный вклад в банк. Из качественных соображений и личных предпочтений, инвестор выдвигает следующие требования к портфелю ценных бумаг:

а) все 500 тыс. руб. должны быть инвестированы;

б) по крайней мере, 100 тыс. руб. должны быть на срочном вкладе в банке (не меньше);

в) по крайней мере, 25% средств, инвестированных в акции, должны быть инвестированы в акции с низким риском (не меньше);

г) в облигации надо инвестировать, по крайней мере, столько же средств сколько в акции (не меньше);

д) не более чем 125 тыс. руб. должно быть вложено в бумаги с доходом менее чем 10%.

Данные о предполагаемых доходах по ценным бумагам см. в таблице 1.22.

В задаче требуется ответить на вопросы:

1. Определить портфель бумаг инвестора, который удовлетворяет всем требованиям и максимизирует годовой доход. Какова величина этого дохода?

2. Если инвестор вносит дополнительные средства в портфель бумаг, сохраняя все ограничения, как изменится ожидаемый годовой доход?

3. Ожидаемый годовой доход по той или иной бумагах (особенно по акциям) – это не более чем оценка. На сколько оптимальный портфель и ожидаемая величина дохода от портфеля выбранных бумаг чувствительны к этим оценкам?

Какая именно бумага портфеля наиболее сильно влияет на оценку суммарного ожидаемого дохода?

4. Дать интерпретацию значений теневых цен для правых частей каждого из ограничений.

Таблица 1.22. Данные к задаче №1.7.

Математическая модель задачи. В качестве переменных решения примем суммы, вложенные в каждый вид ценных бумаг {yi, i=1,2,3,4,5,6}.

Целевая функция F(Y) - это суммарный доход (ожидаемая доходность портфеля) будет равна сумме произведений долей акций в портфеле на их доходность. При этом максимально возможная доходность портфеля акций равна доходности самой прибыльной из акций, а минимально возможная доходность портфеля – доходность самой непривлекательной акции. В этих крайних случаях портфель акций будет содержать только акции одного вида.

Ограничения задачи: а) Требование инвестировать всю сумму доходности должно быть в виде равенства: y1 y2 y3 y4 y5 y6 500 ;

б) Не меньше 100 тыс. руб. должны быть на срочном вкладе, т.е. y6 100 ;

По аналогии можно описать остальные ограничения, так Получили задачу ЛП, которую можно решить в MS-Excel, для этого организуем данные, как в таблице 1.23.

Таблица 1.23. Организация данных задачи №1.7 на листе MS-Excel 1 Оптимизация инвестиционного портфеля Таблица 1.24. Оптимальное решение задачи№1. Оптимизация инвестиционного портфеля Ограничения Исследуем задачу на чувствительность и ответим на поставленные вопросы, для этого обратимся к отчту об устойчивости (табл. 1.25).

Таблица 1.25. Отчт об устойчивости задачи №1.7.

Изменяемые ячейки Долгосрочные облиг. – X Краткосрочные облиг. X 1) Максимальный годовой доход портфеля равен 52,5 тыс. руб., который получен при инвестициях: в акции “А” надо инвестировать 75 тыс. руб., доход от них равен 11,25 тыс. руб. В акции “B” – 0. В акции “C” надо инвестировать 25 тыс.

руб., доход от которых – 2,25 тыс. руб. В долгосрочные облигации надо вложить 300 тыс. руб., доход от них будет - 33 тыс. руб. Краткосрочные облигации покупать не выгодно. Срочный вклад – 100 тыс. руб., доход от него 6 тыс. руб.

Итого: 11,25+2,25+33+6=52,5 (тыс. руб.).

2) Обозначим теневые цены за xi. Так как общая интерпретация теневых цен связана с формулой каждый дополнительный рубль, инвестированный в портфель, даст 11% прибыли, т.к. теневая цена переменной, соответствующей первому ограничению 0,11(руб).

3) Все дополнительные инвестиции должны идти в долгосрочные облигации, это не нарушит ни одного ограничения и это выгодно.

4) Теневая цена второго ограничения 0, то план №2 оптимальный.

Распределительный метод. При распределительном методе решения ТЗ последовательно используются расчтные таблицы, соответствующие очередному шагу решения. Для проверки очередного плана на оптимальность последовательно вычисляют оценки всех свободных клеток до первой отрицательной (в задаче на min), положительной (в задаче на max), если таких нет – план оптимальный.

Клетка, имеющая отрицательную оценку, является выгодной в смысле уменьшения целевой функции. Е следует запомнить, т.е. произвести перераспределение поставок в цикле, построенном для этой клетки. Оценка ij для построенного цикла равна разности между суммой затрат нечтных и чтных клеток. Нумерация клеток для определения чтных и нечтных начинается с клетки, для которой строится цикл (ей присваивается №1), а дальше нумерация ведтся продвижением по циклу то клетки к клетке в любом направлении стрелки.

Проверим на оптимальность распределительным методом план №1 задачи №8.

Решение. Для клетки (1,3): 13 =4-5+4-6=-3; клетки (2,1): 21 =8-3+6-4=7.

Так как 131, не имеющий циклов, называется деревом (рис.3.2). У дерева с “n” вершинами число ребер равно (n-1).

Конечный связный ориентированный граф без петель G (X,T) называется сетью, если: а) граф имеет только две такие вершины, когда одна не имеет входящих дуг, это начало графа (х0), а другая – выходящих, конец графа (хn).

Вершину x0 ещ называют источником, хn - стоком, остальные вершины промежуточными;

б) всем дугам графа G (X,T) поставлено в соответствие число dij (количественная характеристика). Это может быть длина дуги (расстояние между пунктами), пропускная способность дуги, оценки времени, стоимость перевозок и т.д. Графы можно задать с помощью матриц.

1. Матрица смежности А(aij): А(аij ) Свойства матрицы смежности: а) матрица А квадратная, размерности (nn), где n число вершин графа; б) матрица А симметричная, т.е. aij=aji, i,j=1,n; в) единицы, стоящие по главной диагонали соответствуют петлям при данной вершине; с) изолированной вершине соответствует строка и столбец, состоящий из нулей; г) число единиц в матрице равно числу дуг графа. Для графа, изображнного на рис.1(а) матрица смежности имеет вид (рис.3(а)):

2. Матрицей инциденции В(bij). В(bij ) 0, если xi ( xij ), Свойства матрицы инциденции: а) матрица В(bij) размерностью (nxm), где n число вершин, m - число дуг графа; б) количество (+1) или (-1) в строках определяет степень соответствующей вершины; в) вершина, соответствующая строка которой, содержит только (+1), называется входом в граф, вершина, соответствующая строка которой, содержит только (-1), называется выходом из графа. Матрицей инциденции орграфа (рис.1(б)) является матрица B(bij) размерностью (5х7) (рис.3(б)). Можно составить матрицу инцидентности для неориентированного графа. В этом случае элементами матрицы будут только 1 и 0.

Причм, 1 – если вершина является концом ребра, 0 – в противном случае.

Кроме перечисленных матриц, существуют матрицы основных и простых циклов. А так же матрица достижимости (в данном курсе не изучаются).

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

1. “Дерево решений”. Своевременная разработка и принятие правильного решения – главные задачи работы управленческого персонала любой организации.

На практике результат одного решения заставляет нас принимать следующее решение и т.д. Когда надо принять несколько решений в условиях неопределнности, когда каждое решение зависит от исхода предыдущего или исходов испытаний, то применяют схему, называемую “деревом решений”.

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

Рисуют дерево слева на право (или сверху вниз). Вершинам графа ставят в соответствие моменты, в которых принимают решения, обычно их обозначают квадратом, места появления исходов – кругами. Для каждой альтернативы считают ожидаемую стоимостную оценку (EMV) – максимальную из сумм оценок выигрышей, умноженных на вероятности реализации выигрышей, для всех возможных вариантов.

Задача №3.1. Главному инженеру компании надо решить, монтировать или нет новую производственную линию, использующую новейшую технологию. Если новая линия будет работать безотказно, компания получит прибыль 200млн. руб., если откажет, компания может потерять 150млн. руб. По оценкам главного инженера существует 60% шансов, что новая линия откажет. Можно создать экспериментальную установку, а затем уже решать, монтировать или нет линию.

Эксперимент обойдтся в 10млн. руб. Существует 50% вероятность, что установка будет работать. Если она будет работать, то 90% шансов за то, что производственная линия также будет работать, если установка не будет работать, то только 20% шансов, что производственная линия заработает. Следует ли производственную линию? Какова ожидаемая стоимостная ценность наилучшего решения? Строим граф-дерево (рис.3.4).

Решение. В узле F линия работает с вероятностью 0,4, прибыль 200млн.руб. и не работает с вероятностью 0,6, убыток 150млн.руб.

EMV(F)=0,4200+0,6(-150)=-10, EMV(G)=0. Очевидно, в узле 4 выбираем EMV(4)=max{-10,0}=0, т.е. на этом этапе принимаем решение - линию не монтировать.

В узле B, EMV(B)=0,9200+0,1(-150)=165, EMV(C)=0. Таким образом, в узле 2 выбираем EMV(2)=max{165,0}=165, т.е. линию монтировать.

В узле D, EMV(D)=0,2200+0,8(-150)=-80, EMV(E)=0. В узле 3 выбираем EMV(3)=max{-80,0}=0, т.е. линию не монтировать.

В узле А, EMV(А)=0,5165+0,50-10=72,5. Тогда в узле 1 выбираем EMV(1)=max{72,5;0}=72,5. Вывод: Ожидаемая стоимостная ценность наилучшего решения 72,5 млн. руб. Строим установку, если она работает, то монтируем линию, если не работает, то линию монтировать не надо.

Принять лучшее решение в задачах такого типа можно с помощью MS-Excel.

С помощью надстройки “Дерево решений” можно нарисовать и проанализировать дерево решения. Подробно построение “дерева решений” рассмотрено на примере следующей задачи. Для задачи №3.1 “дерево решений” выглядит следующим образом (рис.3.5).

3.3. Построение и анализ дерева решений с помощью MS-Excel Задача №3.2. “Компания Полт” рассматривает проект по обслуживанию служебных перелтов на некоторой территории. На услуги компании имеется определнный спрос. Проект рискованный. Существует вероятность 40%, что в первый год спрос будет низким. Если он будет низкий в первый год, то с вероятностью 60% он останется низким и во все последующие годы. Если он будет высокий в первый год, то с вероятностью 80% он останется таким и во все последующие годы. Первое решение, которое должна принять компания, какой самолт надо купить: новый турбовинтовой - $550тыс. или подержанный поршневой - $250тыс. Эксперты полагают, что в следующие годы такой самолт будет стоить ещ меньше -$150тыс.

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

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

Таблица 3.1. Финансовые потоки при различных вариантах спроса 1) Какой самолт купить? 2) Правильная ли идея, расширить деятельность компании за счт покупки второго поршневого самолта после первого года при высоком спросе? 3) Рассмотреть идею свртывания бизнеса после первого года работы в случае низкого спроса. По имеющимся оценкам турбовинтовой самолт через год может быть продан за $500 тыс. Провести анализ чувствительности выбора оптимальной альтернативы в обоих вариантах. Построить и проанализировать дерево с помощью надстройки “Дерево решений”. При расчтах необходимо учесть, что будущие финансовые потоки надо дисконтировать по ставке, например, 10% для получения чистой приведнной стоимости по формуле:

Для построения “дерева решений” надо:

1. Открыть новую книгу MS Excel. Выбрать кнопку “Организация диаграмм” на стандартной панели инструментов и щлкнуть по кнопке “Создать новое дерево” в появившемся окне надстройки “Дерево решений”. Появится лист MS Excel, надпись P(i) будет означать вероятность каждой ветви дерева, а ni означает переменную состояния дерева, которая будет различна на каждой ветви (рис.3.6).

2. Если переменных n>1, надо щлкнуть по вкладке “Переменные и расчты” и увеличить число переменных на n-1 (рис.3.7).

3. Затем поставить курсор на звздочку в ячейке, следующей после P(i) - это место, с которого дерево начнт расти, (никогда не стирайте такие звздочки, и всегда выделяйте ту, из которой надо продолжить дерево). Затем выбрать вкладку “Редактировать дерево” и щлкнуть по кнопке ”Добавить развилку «Выбор решения»”, предварительно убедившись, что вы задали 2 ветви в этой развилке.

Обратите внимание, чтобы на месте звздочки появился синий ноль, под которым можно разглядеть формулу, например, =МАКС(R2:R3). Если ноль оказался красным и формула под ним другая, значит сделана ошибка, вы добавили развилку «Варианты будущего» вместо развилки «Выбор решения». В этом случае надо курсор поставить в начало развилки в красный ноль, щлкнуть по клавише “Удалить поддерево” и заново ввести правильную развилку (рис.3.8).

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

После этого поставить курсор на верхнюю из двух звздочек и вставить развилку «Варианты будущего» (рис.3.9).

5. На данном этапе изменить названия вариантов и вставить вероятности сценариев и прогнозируемые финансовые потоки. После этого, вернув курсор в точку развилки, щлкнуть по кнопке «Копировать поддерево» или «Копировать развилку». Поставив курсор на звздочку, где планируете продолжить дерево решений, щлкнуть по кнопке «Вставить поддерево». Развилка из предыдущей ячейки будет скопирована в данную ячейку. Останется только поменять начальные данные для этого этапа (числа финансовых потоков). В ячейку Z5 вставить развилку решений “Купить 2-ой самолт” или нет (с отражением инвестиций первого года в покупку 2-го самолта на соответствующей ветке), а в каждую из ветвей этой развилки скопировать развилку вариантов будущего ”Высокий или Низкий спрос во втором году” (рис.3.10).

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

7. После введения формул, надстройка сделает все необходимые вычисления и порекомендует, какие решения следует принимать в каждой развилке решений.

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

Рассмотрим все эти этапы на задаче №3.2.

Теперь, анализируя дерево, можно ответить на все вопросы задачи и провести анализ на возможность выхода из бизнеса после первого неудачного года: 1) Очевидно, компания должна купить поршневой самолт. Цена вопроса $148,18 тыс. Поршневой самолт выгоднее турбовинтового.

2) Идея купить второй поршневой самолт после первого года при высоком спросе правильная.

3) Если после первого года работы спрос будет низким, потери компании составят 300,4+500,4-550-250=-768($тыс.). С учтом продажи турбовинтового самолта потери составят (-268$тыс.).

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

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

Эффект от СПУ обусловлен в первую очередь внесением строгих логических элементов в формирование плана, которые позволяют привлечь современный математический аппарат и средства вычислительной техники. СПУ применяется во всех видах строительства, в индивидуальном и мелкосерийном производстве, в научно – исследовательских, проектных организациях, в производстве кинофильмов и т.д.

Назначение, характеристика и структура системы СПУ. Системы предназначены для управления деятельностью, направленной на достижение определнной цели. Объектом управления является коллектив, располагающий определнными ресурсами и выполняющий комплекс работ.

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

В настоящее время широко распространены две методики количественного анализа проекта – СРМ (английская версия Critical Path Method, т.е. метод критического пути) и PERT (Program Eval Uation и Review Technique, т.е. метод анализа и обзора проекта). Метод СРМ предполагает анализ проекта в условиях, полной определнности, (длительность всех операций, необходимых для выполнения проекта, определено вероятностными методами). Метод СРМ/Cost – исследует проект на оптимальность (“Длительность проекта - издержки”), а также влияние ограничений в использовании ресурсов. Эти методы можно реализовать в MS-Excel и MS-Project (русская версия).

Для отображения процесса выполнения проекта используется сетевая модель.

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

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

Правила построения сетевого графика: 1. Исходное событие только одно.

2. Завершающее событие только одно.

3. Любые два события связаны не более чем одной работой.

4. В сетевом графике не должно быть замкнутых контуров.

5. Если для выполнения одной из работ необходимо получить результаты всех работ, входящих в предшествующее для не событие, а для другой работы достаточно получить результат нескольких из этих работ, то нужно ввести дополнительное событие, отражающее результаты только этих последних работ, и фиктивную работу, связывающую новое событие с прежним. Фиктивные работы изображаются пунктирными стрелками.

С самого начала планирования и анализа проекта необходимо чтко представлять себе взаимосвязи между отдельными работами и установить соотношение “предшественник - последователь” для всех стадий проекта.

Пусть задан граф (рис.3.12). Показать последовательность выполнения работ этого сетевого графа. Здесь для начала работы D достаточно окончания работы А.

Для начала же работы С нужно окончание работ А и В.

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

Рассмотрим граф (рис.3.13). Разобьм условно сетевой график на несколько вертикальных слов. Поместив в первом слое начальное событие (0), (рис.3.14) мысленно вычеркнем из графика это событие и все выходящие из него работыстрелки. Тогда без входящих стрелок останется событие (1), образующее второй слой.

Вычеркнув событие (1) и все выходящие из него работы, увидим, что без входящих стрелок остаются события (4) и (2), которые образуют третий слой.

Продолжаем процедуру вычркивания: четвртый слой с событиями (5) и (3);

пятый слой – с событием (7); шестой – с событием (8) и (6); седьмой – с событием (10); восьмой слой – с событием (9); и девятый слой – с событием (11).

Теперь видим, что первоначальная нумерация событий не совсем правильная:

так событие (6) лежит в шестом слое, событие (7) (больший номер) лежит в пятом слое. То же самое можно сказать о событиях (9) и (10). Надо изменить нумерацию событий в соответствии с их расположением на графике.

Этот метод используется для управления проектами с фиксированным временем выполнения работ. Он позволяет ответить на следующие вопросы:

1. Сколько времени потребуется на выполнение всего проекта?

2. В какое время должны начинаться и заканчиваться отдельные работы?

3.Какие работы являются критическими и должны быть выполнены в точно определнный срок, чтобы не сорвать время выполнения проекта?

4. На какое время можно отложить выполнение некритических работ, чтобы они не повлияли на сроки выполнения проекта?

Основные временные параметры сетевого графика. Резервы времени.

Пусть tij – продолжительность работы с начальным событием i и конечным j (рис.3.16).

Основными временными параметрами сетевого графа являются ранние и поздние сроки свершения события.

Ранний срок tр(j) свершения события j – это самый ранний момент (возможный наименьший срок окончания работы (i,j)), к которому завершаются все работы, предшествующие этому событию (рис.3.16(а)).

Поздний срок tп(i) свершения события i – это такой предельный момент (максимально допустимый), после которого остатся ровно столько времени, сколько необходимо для выполнения всех работ, следующих за этим событием (рис.3.16(б)).

Резерв времени пути равен разности между временем критического пути (наибольшего) и времени данного пути Резерв времени R(i) события i показывает, на какой предельно допустимый срок может задержаться свершение этого события без нарушения срока наступления завершающего события:

События, у которых tп(i)=tр(i) называются критическими событиями.

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

ранний срок начала работы (i,j): tрн(i,j)=tр(i);

ранний срок окончания работы tро(i,j)=tp(i)+tij;

поздний срок начала работы tпн(i,j)=tп(j)-tij;

поздний срок окончания работы tпо(i,j)=tп(j).

Различают четыре резерва времени работы: полный, свободный, независимый и гарантийный резервы.

1. Полным резервом времени Rn(i,j) работы (i,j) называется максимальный запас времени, на которое можно задержать начало работы или увеличить е продолжительность, не изменяя продолжительности критического пути.

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

3. Независимый резерв времени Rн(i,j) работы (i,j) – это запас времени, который имеет исполнитель, когда предшествующие работы заканчиваются в неудобное для него сроки, а он заканчивает свою работу в ранний срок, не расходуя резервов следующих за ней работ.

4. Гарантийный резерв времени Rг(i,j) работы (i,j) – это резерв времени, который имеет исполнитель, когда предшествующие работы заканчиваются в неудобное для него поздние сроки, но и он сдат свою работу в поздний срок.

Если свободный и независимый резервы времени отрицательные, их заменяют нулями. Критические работы, как и критические события, резервов времени не имеют.

Задача №3.3. Построить сетевой график работ (табл.3.2). Найти критический путь, его время. Ответить на вопросы: 1. Можно ли отложить выполнение работы “Д” без отсрочки выполнения проекта. 2. На сколько недель можно отложить выполнение работы “С” без отсрочки выполнения проекта?

Таблица 3.2. Начальные данные задачи № Решение. Рисуем сетевой график, помня основные правила (рис.3.18). Для того, чтобы было одно начальное и одно завершающее событие вводим фиктивные работы K=(6,8) и L=(7,8), которые делать не нужно. Время выполнения этих работ равно 0.

Для определения критического пути находим ранние и поздние сроки свершения событий: tp(1)=0; tp(2)=5; tp(3)=3; tp(4)=max(5+6,3+7)=11;

tp(5)=max(5+7,11+3)=14; tp(6)=11+10=21; tp(7)=14+8=22;

Tkp=tп(8)=22; tп(7)=22-0=22; tп(6)=22-0=22; tп(5)=22-8=14;

tп(4)=min(22-10,14-3)=11; tп(3)=11-7=4; tп(2)=min(11-6,14-7)=5;

Критические события те, у которых tp(j)=tп(j). Это события: 1, 2, 4, 5, 7, 8, т.е.

критический путь проходит через эти вершины, на рис.11 он показан жирным шрифтом. Вывод: для завершения проекта необходимо 22 недели.

1. Работа “Д=(2,4)” лежит на критическом пути, т.е. е отложить нельзя без увеличения времени критического пути.

2. Работа С=(2,5) не лежит на критическом пути, е можно задержать на Rпoл(2,5)=tп(5)-tp(2)-t25=14-5-7=2(недели).

видны критические и некритические работы сетевого графа. Чтобы их Построим график Ганта для графа (рис.3.17) задачи №3.3.

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

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

2. Вторым этапом анализа может быть классификация и группирование работ по величинам резервов (полных и свободных). Определить степень трудности выполнения в срок каждой группы работ некритического пути можно с помощью коэффициента напряжнности. Опр. Коэффициент напряжнности работ – это отношение времени отрезка наибольшего из некритических путей, проходящих через данную работу (t(Lmax)), ко времени несовпадающего отрезка критического пути, проходящего через эту работу.

где t(Tmax) – продолжительность максимального пути через (i,j); tкр – длина отрезка рассматриваемого пути, совпадающего с критическим путм, Tкр- время критического пути, проходящего через эту работу. 0Кн1. Очевидно, что для всех критических работ Кн(i,j)=1. Чем коэффициент ближе к 1, тем сложнее выполнить данную работу в установленный срок, чем Кн меньше, тем большим относительным резервом обладает данный путь в сети. По вычисленным К н все работы распределяются по зонам: критические, подкритические и резервные.

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

Найдм Кн для работы С=(2,5) задачи №3.3. Ранние и поздние сроки для всех событий уже найдены. Отметим, на каких событиях xi и xj достигается максимум tп и минимум tр. Отметки слева показывают, из какого события надо двигаться в данное, чтобы получился наиболее ранний срок tр, а справа - в какое событие надо двигаться из данного, чтобы получился наиболее поздний срок tп. По этим отметкам можно найти максимальный путь через данную работу.

Для работы (2,5): в событие 2 (начало работы) надо двигаться из события 1, т.е. отрезок максимального пути от 1 до начала работы будет (1,2). Из события (конец работы) надо двигаться в событие 7, т.е. отрезок максимального пути от до 7 будет (5,7), т.е. max(2,5)=(1,2,5,7)=20. Tкр=22. Сравнивая Tкр и max находим нужный для расчта К(2,5) отрезок кр, не совпадающий с max(2,5).

кр=(2,4,5)=6+3=9. Rпoл(2,5)=tп(5)-tp(2)-t25=14-5-7=2. К(2,5)=1-2/(22-13)=0,78.

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

t a. Перебрасывая людей и технику с ненапряжнных работ на напряжнные работы критического пути, можно сократить сроки всего проекта. Обычно на практике устанавливается директивный срок (Tдир) выполнения проекта и расчтный (Tk). Если предположить, что срок окончания работ является случайной нормально распределнной величиной, то можно найти t2 - дисперсия i – той работы критического пути, n – число работ критического пути. Для этой вероятности устанавливаются определнные пределы – границы допустимого риска. По данным практики при PT Tдир 0,65 можно утверждать, что на этапах критического пути имеются избыточные ресурсы. Т.е.

общая продолжительность работ критического пути может быть сокращена. При PT Tдир 0,35 велика опасность того, что заданный срок выполнения работ критического пути будет сорван и поэтому необходимо перераспределение ресурсов.

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

В настоящее время распространены две методики количественного анализа проектов – СРМ (метод критического пути) и PERT (метод анализа и обзора проекта).

Метод СРМ предполагает анализ проекта в условиях, когда длительности различных стадий проекта чтко определены. Существует метод СРМ/COST, который исследует проект по принципу оптимизации “длительность - издержки”, а также влияние ограничений в использовании ресурсов на расписание проекта.

Для решения всех этих задач можно использовать русскую версию MS Project 2003.

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

Оптимизация сетевого проекта это процесс улучшения организации выполнения комплекса работ, с учтом сроков его выполнения. Проводится с целью сокращения длительности критического пути, выравнивания коэффициентов напряжнности работ, рационального использования ресурсов. Задержка с выполнением некритических работ не отразится на сроках выполнения проекта, а увеличение времени выполнения критических работ ведт к срыву графика (отсрочки выполнения всего проекта). Может оказаться, что для выполнения всех работ с.г. установлен директивный срок Tдир и он меньше Tкр. Ясно, что уложиться в Tдир можно только путм сокращения длительности работ критического пути. Это возможно за счт привлечения на эти работы дополнительных ресурсов (людей, механизмов и т.д.) или путм расчленения какой – либо работы на части и параллельное их выполнение. Высвободить ресурсы можно, взяв их с некритических работ, за счт удлинения сроков их выполнения в пределах резервов, а это требует новых затрат. Для анализа таких ситуаций в сетевом планировании разработан метод “время - стоимость, или длительность – издержки”, смысл которого в том, что процесс сокращения продолжительности работ достигается за счт минимально необходимого приращения затрат, т.е.

проводится оптимизация с.г. по затратам.

Оптимизационные задачи могут быть “по критерию стоимости”: при заданной общей длительности проекта Tдир найти вариант с наименьшими затратами. И по “критерию времени”: при заданной стоимости S проекта найти минимальное время его выполнения. Оптимизация С.Г. может быть условно разделена на частную и комплексную: частная – только по критерию времени или только по критерию стоимости; комплексная – нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от целей, стоящих при его реализации.

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

Затраты в первом случае - Сij, во втором - Сij, очевидно, tij tij, Cij Cij. Зная эти величины, можно вычислить затраты на ускорение каждой работы Для определения длительности выполнения всего комплекса операций и возможная стоимость, строятся графики при нормальном и при срочном режимах работ. Определяют критические пути, их длины Tкр, Tкр и стоимости S кр, S кр, затем проводится анализ сетевых графиков. В результате получают набор вариантов оптимальных сетевых графиков по двум критериям – времени исполнения и стоимости.

1. Снижать стоимость можно за счет увеличения сроков выполнения тех работ, которые приводят к наибольшему сокращению затрат (принцип “наибольшей эффективности”), т.е. ij больше. Удешевление не может отдельно затрагивать только критические работы, его проводят также за счт увеличения частного резерва времени некритических работ (т.е. увеличение времени работы, у которой ij положительная величина).

2. Снижать время выполнения с.г. можно за счт уменьшения сроков выполнения тех критических работ, затраты на ускорение которых минимальны.

Задача №3.4. В табл. 3.4 приведены характеристики работ сетевого графика при нормальном и срочном режимах их выполнения. Предполагается, что в пределах между нормальным и срочным режимами возможен любой срок выполнения работ. Определить: 1. Критический путь для каждого режима.

2. Резервы времени работ, затраты на ускорение критических работ. 3.

Ответить на вопросы: а) на сколько дней можно максимально сократить выполнение работ, исходя из выделенных на это средств –6 млн. руб? б).

Определить минимальное увеличение затрат на комплекс работ при сокращении общего срока выполнения на 5 суток.

Таблица 3.3. Параметры работ сетевого графика примера №3. Решение. Сетевой график имеет вид (рис.3.20).

1. а) Для определения критического пути, находим ранние и поздние сроки свершения события для нормального режима.

tp(1)=0, tp(2)=4, tp(3)=6, tp(4)=max(4+15,6+16)=22, tp(5)=max(6+11,22+6)=28, tp(6)=max(22+19,28+6)=41. Tkp=41.

tп(6)=41, tп(5)=41-6=35, tп(4)=min(41-19,35-6)=22, tп(3)=min(22-16,35-5)=6, tп(2)=22-15=7, tп(1)=min(7-4,6-6,22-5)=0.

Критические события: 1, 3, 4, 6. Критические работы: А, E, L (рис.3.21).

Б) Вычисляем ранние и поздние сроки событий при срочном режиме: tр(1)=0, tр(2)=3, tр(3)=5, tр(4)=max(3+13,5+13)=18, tp(5)=max(5+4,18+4)=22, tp(6)=34. Tkp=34.

tп(6)=34, tп(5)=30, tп(4)=min(34-16,30-4)=18, tп(3)=min(30-4,18-13)=5, tп(2)=18-5=13, tп(1)=min(13-3,5-5)=0. Критический путь тот же.1-3-4-6.

2. Для расчта резервов времени работ, составляем табл.3.4.

3. Для ответа на вопросы задачи об оптимизации, составляем табл.6, перечень возможных сетевых графиков.

Таблица 3.4. Временные параметры сетевого графика Таблица 3.5. Перечень возможных сетевых графиков В табл.3.5 представлены восемь вариантов возможных сетевых графиков.

а). Если в задаче требуется снизить время с.г., это можно сделать за счт уменьшение длительности выполнения тех работ критического пути, которые приводят к наименьшему увеличению затрат. Так, например, в задаче дополнительно выделено 6 млн. руб., т.е. S1=123+6=129 (млн. руб.), то нас устроит вариант №4. Вывод: минимальное количество дней, на которое можно сократить с.г. равно 41-38=3 (суток).

б) Если в задаче требуется снизить стоимость с.г., это можно сделать за счт увеличения длительности выполнения тех работ, которые приводят к наибольшему сокращению в затратах (по наибольшему приросту затрат). В этом случае надо анализировать вариант сетевого графика со срочным временем выполнения работ и в первую очередь увеличивать продолжительность тех работ, которые не принадлежат критическому пути. В этом случае надо заранее вычислить продолжительностью t(i,j), которая может находиться в пределах a(i,j) – минимально возможная продолжительность работы, b(i,j) – нормальная продолжительность выполнения работы. Продолжительность каждой работы, имеющей резерв времени, увеличивают до тех пор, пока не будет исчерпан этот резерв или пока не будет достигнуто верхнее значение продолжительности b(i,j). При этом стоимость выполнения проекта, равная до оптимизации S S (i, j ) уменьшиться на величину Продолжительность каждой работы t(i,j) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного резерва времени Rc.

2. В нашей задаче требуется сократить общий срок выполнения с.г. на суток с минимальными затратами. Это график №6, при этом дополнительно потребуется 135-123=12 млн. руб. Таблица 3.5 позволяет для руководителей проекта выбрать из 8 вариантов лучший, который устраивает их и по деньгам и по времени.

1. Вызвать MS-Project и создать пустой проект. В столбец ”Название задачи” ввести обозначения этапов проекта, а в столбец ”длительность” – их продолжительность (эти данные можно вставить целой группой, если они есть в MS-Excel). В таблице слева можно добавлять или убирать столбцы. Ещ в один столбец надо ввести информацию о предшественниках. Если другие столбцы не нужны, можно их убрать, чтобы освободить место.

2. При вводе исходных данных MS-Project начинает строить диаграмму Ганта (график Ганта), который дат графическое представление сетевого графа.

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

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

можно указать, начинается этап сразу после окончания предыдущего (ОН) – окончание-начало или с некоторым запаздыванием (ОД) – столбец запаздывает. По умолчанию последний этап начнтся так рано, как только это возможно после окончания предшествующего этапа. После того, как указаны все предшественники этапа, нажимаем «ОК» и вызываем такое же окно для другого этапа.

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

Уменьшить диаграмму можно инструментом «Уменьшить» (значок в виде лупы со знаком (-)). В задачах, связанных с оптимизацией проектов, удобно добавить к проекту суммарную задачу «Сервис/Параметры/Вид», (внизу диалогового окна).

При этом на диаграмме Ганта будет добавлена задача (проект) с указанием полной длительности проекта. При сокращении проекта изменение его длительности будет немедленно изображено на графике.

3. После построения диаграммы, длительность проекта можно посмотреть, используя меню «Проект/Сведения» и далее кнопка «Статистика». На диаграмме Ганта легко видны критические и некритические работы сетевого графа. Чтобы их увидеть, надо отформировать диаграмму. Для этого: вызвать в меню «Формат»

команду «Мастер диаграмм Ганта». В появившемся окне нажать кнопку «Далее».

В следующее окне нажать кнопку-переключатель «Критический путь» и снова «Далее». В появившемся окне отметить возможность «Настроить сведения о задаче» и опять «Далее». В новом окне полезно попросить, чтобы рядом с отрезком. Изображающим этап, отображалось его «Название». Далее выбираем кнопку «Готово», в появившемся окне написать «Форматировать». После этого появится заключительное окно «Выход из мастера». На полученной диаграмме Ганта критические работы окрашены красным цветом. Построим график Ганта и критический путь на примере задачи №19.

Задача №3.5. Компания планирует развртывание сети магазинов в одном из регионов России. Отдел развития компании составил план работы по развртывания сети, состоящий из 21 этапа. Информация о нормальной длительности этапов в рабочих днях приведена в табл. 3.6. Сетевая диаграмма проекта, показывающая порядок выполнения этапов приведена на рис.3.21. После того, как план был доложен, выяснилось, что он не годится. Товар под новую сеть уже заказан, и поставки начнутся за 4 недели до планируемого завершения проекта.

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

В задаче требуется: 1. Построить критический путь и определить его время.

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

Таблица 3.6. Длительность этапов (дни) Таблица 3.7. Стоимость сокращения длительности этапов на 1-ый, 2-ой и 3 день Решение. Для решения задачи используем программу MS Project 2003. В табл. 3.6 и 3.7 для каждой стадии (работы) проекта указаны длительность е проведения и стоимость е сокращения на один день. Первый вопрос, который возникает в задаче: сколько времени требуется для выполнения всего проекта? Т.е.

надо построить критический путь и рассчитать Ткр. Для этого надо упорядочить график, установить соотношения «предшественник - последователь» для всех стадий проекта (у нас сетевой график уже есть). Далее используем MS Project, для построения диаграммы Ганта и детального анализа проекта.

Ответ на вопрос 1. Длительность проекта 65 дней или 13 недель.

По условию задачи длительность проекта надо сократить на 2 недели ( дней). Очевидно, это можно сделать за счт критических работ, а это работы 3, 4, 7, 10, 14, 18 и 21. Любое сокращение проекта приводит к его удорожанию. Чтобы получить минимальную стоимость сокращения, надо сокращать, в первую очередь, те работы, которые имеют наименьшую стоимость сокращения. Т.е. основная тактика сокращения длительности проекта состоит в том, чтобы проводить сокращение на единицу длительности за каждый шаг и выбирать ту критическую работу, сокращение которой стоит дешевле всего. Сокращать сразу на две и более единицы времени лучше не делать, т.к. на каком-то шаге работа может стать не критической, дальнейшее е сокращение только увеличит бесполезные затраты средств. Иногда сокращение проекта приводит к появлению нескольких критических путей, естественно имеющих одинаковое время. В этом случае приходится сокращать каждый из этих путей на одну единицу, чтобы сократить весь проект, например на один день. Обычно сетевой график задан в двух режимах, «Нормальном» и «Срочном», расчт стоимости ускорения производят по формуле (3.12).

а) Т.к. затраты на ускорение работы связаны с использованием различных ресурсов, начинать надо с введения данных об этапах проекта. В диалоговом окне «Сведения о задаче» (вызывается двойным щелчком мыши по имени стадии), на вкладке «Ресурсы» можно задать ресурсы для каждой стадии проекта.

б) После ввода всех ресурсов надо открыть меню «Окно Разделитель».

Появится дополнительное окно «Ресурсы и предшественники», по щелчку правой кнопкой мыши появится меню, в котором можно выбрать окно «Трудозатраты ресурсов», в котором нужно задать стоимости ресурсов. Двойным щелчком левой кнопки мыши щлкнуть по названию ресурса, в диалоговом окне «Сведения о ресурсе», на вкладке «Затраты», задать величины нормальной («Стандартная ставка») и срочной стоимости работы («Ставка сверхурочных»). Нажимаем «OK» и переходим к другому ресурсу. После введения стоимости ресурсов, можно посмотреть статистку проекта, чтобы убедиться, что есть сведения о стоимости работ. В нашей задаче не надо рассчитывать стоимость ускорения каждого этапа проекта, она задана в табл.3.7.

с) Самая дешвая для сокращения работа у нас – (Э3), удорожание проекта на 4 ед. Для е сокращения щлкнем название стадии в верхней таблице и после этого в нижней таблице в столбце «Сверхурочный труд» поставим 1 рабочий день. После ввода и перехода в верхнюю таблицу длительность работы изменится с 9 до 8 дней. Соответственно изменится диаграмма Ганта. Статистика проекта покажет: длительность проекта сократилась до 324 дней, а его стоимость возросла на 4 ед. Далее самая дешвая работа – (Э4), с удорожанием проекта на 4 ед. После каждого сокращения работы, надо обращать внимание, чтобы она оставалась критической, тогда, если возможно, сократить е ещ раз. При этом в столбце «Сверхурочный труд» надо поставить 2 дня. И т. д.

г) Как только предел сокращения достигнут, для ответа на второй вопрос, можно снова проследить график сокращений и посмотреть статистику.

В нашей задаче стоимость ускорения работ задана табл. 3.7. Самый дешевый для сокращения этап Э3, поэтому сокращаем этот этап на 1 день.

Итак, последовательность сокращения следующая:

1) Э3- 1день (4у.е.), Ткр=64дня, S=124+4=128(у.e.), критический путь 1;

2) Э4- 1день (4ед.) Ткр=63дня, S=128+4=132(у.e.), критический путь 1;

3) Э21- 1день (7ед.) Ткр=62дня, S=132+7=139(у.e.), критический путь 1;

4) Э18- 1день (8ед.) Ткр=61день, S=139+8=147(у.e.), критических пути три;