Информационные технологии сетевого планирования в управлении

• ТЕМА
• Информационные технологии сетевого планирования в управлении
• Введение
• В практике управления сложными системами широко применяются методы сетевого планирования и управления (СПУ). Эти методы включают несколько разновидностей, наиболее широко используемыми из которых являются PERT (Program Evaluation and Review Technique — метод оценки и обзора программ) и СРМ (Critical Path Method — метод критического пути).
• Метод РЕRТ применяется в планировании научно-исследовательских и опытно-конструкторских разработок, для которых характерна неопределенность в оценке затрат времени, необходимого для выполнения отдельных операций (работ). Метод СРМ применяется тогда, когда оценки времени операций являются детерминированными. В данном пособии мы ограничимся рассмотрением метода CPM.
• Методы СПУ используются при планировании сложных комплексных проектов, таких как:
• · Строительство и реконструкция каких-либо объектов;
• · Выполнение научно-исследовательских и конструкторных работ;
• · Подготовка производства к выпуску продукции;
• · Развертывание системы медицинских или профилактических мероприятий;
• · Перевооружение армии и т. п.
• Характерной особенностью таких проектов является то, что они состоят из ряда отдельных, элементарных работ. Работы обуславливают друг друга так, что выполнение некоторых из них не может быть начато раньше, чем завершены некоторые другие. Например, укладка фундамента не может быть начата раньше, чем будут доставлены необходимые материалы; эти материалы не могут быть доставлены раньше, чем будут построены подъездные пути; любой этап строительства не может быть начат без составления соответствующей технической документации и т. д.
• СПУ состоит из трех основных этапов:
• · Структурное планирование;
• · Календарное планирование;
• · Оперативное управление.
• Структурное планирование начинается с разбиения проекта на четко определенные операции, для которых определяется продолжительность. Затем строится сетевой график, который представляет взаимосвязи работ проекта. Это позволяет детально анализировать все работы и вносить улучшения в структуру проекта еще до начала его реализации.
• Календарное планирование предусматривает построение календарного графика, определяющего моменты начала и окончания каждой работы и другие временные характеристики сетевого графика. Это позволяет, в частности, выявлять критические операции, которым необходимо уделять особое внимание, чтобы закончить проект в директивный срок. Во время календарного планирования определяются временные характеристики всех работ с целью оптимизации сетевой модели, которая улучшает эффективность использования какого-либо ресурса.
• В ходе оперативного управления используются сетевой и календарный графики для составления периодических отчетов о ходе выполнения проекта. При этом сетевая модель может подвергаться оперативной корректировке, вследствие чего будет разрабатываться новый календарный план остальной части проекта.

Построение сетевых графиков

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

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

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

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

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

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

Различают три вида операций:

1) действительная операция () — процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, выполнение монтажных работ и т. д.);

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

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

При построении сетевых графиков необходимо соблюдать определенные правила:

1) в сети не должно быть событий (кроме исходного), в которые не входит ни одна дуга;

2) не должно быть событий (кроме завершающего), из которых не выходит ни одной дуги;

3) сеть не должна содержать контуров;

4) любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если изобразить одновременно выполняемые три различные операции, , с общими начальным и конечным событиями (Рис. 3.1), то возникает путаница из-за того, что различные операции имеют одно и то же обозначение (2,5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (Рис. 3.2);

5) номер начального события любой операции должен быть меньше номера ее конечного события.

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

Эта зависимость представлена на Рис. 3.3, из которого видно, что операция следует за операцией и фиктивной операцией (2,З).

В свою очередь, операция (2,3) следует за операцией. Тогда в силу транзитивности выполнение операции предшествует выполнению операции .

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

После составления списка операций приступают к процедуре построения сети.

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

Таблица 3.1 Описание составных работ проекта

Анализ данных, приведенных в этой таблице, — более конкретно — последовательности и взаимозависимости работ, позволяет построить сетевой график вида

В данном сетевом графике помимо работ, указанных в таблице, использованы две фиктивные работы (3,4) и (5,6), обозначенные штриховыми линиями. Эти работы не требуют времени на их выполнение и используются в графическом представлении проекта лишь для того, чтобы правильно отобразить взаимосвязь между работами.

Расчет временных параметров сетевого графика

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

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

Предшествующий событию путь представляет собой путь от исходного события до данного.

Следующий за событием путь — путь от данного события до завершающего.

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

Рассмотрим процедуру расчета параметров сетевого графика.

Пусть продолжительности выполнения операций известны (Рис. 3.5; продолжительности операций расположены у соответствующих дуг графика).

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

Событие (2) свершится, очевидно, спустя 2 ед. времени после свершения события (1), так как время выполнения операции (1,2) равно 2. Следовательно,

Событию (3) предшествуют два пути

и

Продолжительность первого пути равна 1 ед. времени, а второго — 2 ед. времени, так как

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

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

В событие (4) входят две дуги, исходящие из событий (1) и (3), для которых ожидаемые сроки свершения найдены. Следовательно, ожидаемый срок свершения события (4)

Аналогично находятся ожидаемые сроки свершения событий (5), (6) и (7). Значения, приписаны соответствующим событиям.

Общая формула нахождения ожидаемых сроков свершения событий имеет вид где — подмножество дуг сети, входящих в событие .

Ожидаемый срок свершения события (7) совпадает с критическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь теперь от завершающего события к исходному, выделим операции, принадлежащие критическому пути. Из трех операций, входящих в событие (7), определила операция (5,7), выполнение которой начинается после свершения события (5) и продолжается 3 ед. времени. Момент свершения события (5) определила операция (3,5), так как. В свою очередь момент свершения события (3) определила операция (2,3), а события (2) — операция (1,2). Эти операции на рис. 8.6 выделены жирной линией. Таким образом, критический путь. Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению времени выполнения всего комплекса операций. Напротив, увеличение времени выполнения или задержка с выполнением некритических операций может не отразиться на сроке свершения завершающего события. Так, например, время выполнения операции (4,5) может быть увеличено, или начало ее выполнения может быть отсрочено на 1 ед. времени, и это не отразится на сроке свершения события (5), а, следовательно, и всего комплекса операций.

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

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

где — подмножество дуг сети, исходящих из события .

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

(на Рис. 3.4 предельные сроки свершения событий указаны в скобках). Для критических событий эти сроки совпадают с ожидаемыми.

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

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

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

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

Полный резерв времени операции показывает, насколько можно сдвинуть начало выполнения операции или увеличить ее продолжительность, не изменяя ожидаемого срока свершения начального события, при условии, что конечное для данной операции событие свершится не позднее своего предельного срока. Величина полного резерва времени вычисляется по формуле Свободный резерв времени операции показывает, насколько можно увеличить продолжительность или отсрочить начало выполнения операции, при условии, что начальное и конечное ее события свершаются в ожидаемое время Так резервы времени операции (4,6) сетевого графика составляют (Рис. 3.5)

сетевой график поток стоимость

Оптимизация комплекса операций

А. Оптимизация комплекса операций по времени

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

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

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

Приведем математическую формулировку процесса оптимизации по времени.

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

Математически условия задачи можно записать следующим образом

(3.1)

(3.2)

(3.3)

(3.4)

; (3.5)

(3.6)

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

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

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

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

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

Пример 1.

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

Продолжительность выполнения операций зависит линейно от дополнительно вложенных средств и выражается соотношением

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

Решение Добавив на сетевом графике фиктивную операцию (5,6), запишем целевую функцию в виде Запишем ограничения задачи:

· сумма вложенных средств не должна превышать наличного их количества

· время выполнения каждой операции должно быть не меньше минимально возможного времени

· зависимость продолжительностей операций от вложенных средств дает ограничения-равенства

· время начала выполнения каждой операции должно быть не меньше времени окончания непосредственно предшествующей ей операции (моменты времени

· условие неотрицательности неизвестных для всех дуг сетевого графика.

Создадим на рабочем листе Excel форму для ввода данных, необходимых для решения задачи (Рис. 3.7).

Рис. 3.7. Форма для ввода данных примера 1.

Введем обозначения для переменных согласно Рис. 3.7, и отведем под расчетные значения X1-X20 диапазон ячеек A8: T8. Далее, введем формулы для расчета функций-ограничений в соответствии с приводимой ниже таблицей

Целевой ячейкой является O14.

Вызываем Поиск решения и вводим все необходимые ограничения.

Ответ Таким образом, чтобы выполнить комплекс операций за 29,65 дней, необходимо вложить в операцию (1,3) 0,88 д.е., в операцию (2,3) 3,92 д.е., в (2,4) 0,83 д.е., и в операцию (3,5) — 9,38 д.е.

Б. Оптимизация комплекса операций по стоимости при фиксированном сроке выполнения проекта

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

(3.7)

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

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

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

Рассмотрим более общий случай, когда

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

(3.8)

где. Учитывая, что величины известны, раскроем скобки в правой части (3.8) и обозначим через сумму

В результате получим

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

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

На неизвестные величины задачи налагаются следующие ограничения:

· продолжительность выполнения каждой операции должна быть не меньше и не больше

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

· выполнение комплекса операций должно быть завершено не позже директивного срока :

; - номер завершающего события

· переменные должны быть неотрицательными

; для всех, при этом, .

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

Пример 2

Исходные данные комплекса операций, представленного сетевым графиком (рис. 3.8), приведены в Табл.3.2

Требуется оптимизировать сетевой график по стоимости при

Таблица 3.2

Решение Запишем, для всех, принадлежащих сетевому графику

;

;

;

;

;

;

При записи функции принято, что Так как при параметрах меньше, то оптимизация возможна за счет всех операций сетевого графика.

Запишем ограничения по времени выполнения операций

Ограничения по предшествованию в выполнении операций:

Все неизвестные должны быть неотрицательными, т. е.

для всех операций сети.

Проведем решение задачи в Excel. Введем данные на рабочий лист в соответствии с Рис. 3.9.

Для расчетных значений переменных X1-X12 отведем диапазон ячеек A5: L5.

Далее, введем функции-ограничения и формулу для целевой функции в ячейки в соответствии с приводимой ниже таблицей.

Рис. 3.9 Форма для ввода данных примера 2

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

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

Потоки в сетях

Задача о максимальном потоке

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

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

и

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

Ставится задача определить для заданной сети максимальную величину потока из источника в сток. Под потоком в сети из источника в сток будем понимать совокупность потоков {} по всем дугам сети, где — поток по дуге (),, равный количеству перемещаемой по ней субстанции в единицу времени. Математически задача о максимальном потоке формулируется следующим образом: найти неотрицательные значения для всех, максимизирующие

(3.9)

при ограничениях

; (3.10)

(3.11)

Условие (3.9) отражает величину максимального потока, который равен количеству вещества, вытекающего из источника, или притекающего в сток. Условия (3.10) означают, что поток по каждой дуге должен быть неотрицательным и не превышать ее пропускной способности; из условия (3.11) следует, что количество вещества, притекающего в любую промежуточную вершину, равно количеству вещества, вытекающего из нее.

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

Проиллюстрируем это на примере.

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

Места добычи нефти расположены в географических пунктах. Из мест добычи нефть транспортируется на нефтеперерабатывающие заводы через некоторые промежуточные пункты. Совокупность пунктов с соединяющими их транспортными магистралями изобразим в виде сети на Рис. 3.10, дуги соответствуют транспортным магистралям, а вершины отдельным пунктам (местам добычи, заводам, станциям перекачки или железнодорожным станциям). Пропускные способности транспортных магистралей приписаны дугам сети. Чтобы определить, какое максимальное количество нефти можно транспортировать из мест добычи на нефтеперерабатывающие заводы, необходимо расширить сеть, добавив один фиктивный источник и один фиктивный сток (фиктивные дуги на рисунке нанесены штриховыми линиями).

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

Рис. 3.10 Введение фиктивного источника и стока Пример 3

Приведем пример решения задачи о максимальном потоке в Excel. Рассмотрим некоторую транспортную сеть (Рис. 3.11.). Предположим также, что транспортные потоки могут идти в обоих направлениях некоторых дуг (очевидно, данный случай является более общим и сложным для решения, чем случай односторонних транспортных потоков). На рисунке обозначены максимальные пропускные способности в обоих направлениях: например из пункта 3 в пункт 6 может быть транспортирован поток интенсивностью 4 единицы, и такой же поток — из пункта 6 в пункт 3 (нули у окончаний некоторых дуг означают невозможность транспортировки в соответствующем направлении).

Требуется определить максимальную пропускную способность сети в целом, т. е. максимальное значение потока .

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

Максимизировать при ограничениях:

Введем данные на рабочий лист в соответствии с Рис. 3.12.

Рис. 3.12 Данные для решения задачи о максимальном потоке Диапазон ячеек A6: Q6 отведем под расчетные значения переменных. В ячейки A8: A14, а также в целевую ячейку F13 введем следующие формулы:

После запуска Поиска решения введем следующие ограничения

В окне диалога Поиска решения для диапазона изменяемых ячеек укажем A6: Q6.

В результате решения получим ответ:; потоки в дугах представлены ниже:

Следует отметить, что данная задача имеет неединственное оптимальное решение, то есть при максимальном потоке в 17 единиц может иметь место различное распределение потоков по дугам.

Задача о потоке минимальной стоимости

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

(3.12)

(3.13)

(3.14)

(3.15)

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

Приведем пример решения задачи потока минимальной стоимости в Excel.

Пример 4

Рассмотрим решение задачи, относящейся к классу задач о потоке минимальной стоимости. Рассматривается сеть, представленная на Рис. 3.13.

Цифры в скобках обозначают: в случае узла 1 (источника) — количество имеющегося продукта, в случае узлов 4 и 5 — потребности соответствующих объектов в продукте. Первые числа у стрелок означают удельную стоимость транспортировки продукта (), а вторые — пропускную способность дуги (например, магистрали). Индекс * у дуги (2,3) и (4,5) означает, что пропускные способности данных дуг могут считаться неограниченными (например, они значительно превосходят имеющиеся в наличии запасы продукта).

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

Решение Очевидно, задача сводится к минимизации функции:

при ограничениях

Введем исходные данные на рабочий лист Excel в соответствии с Рис. 3.14. В качестве целевой ячейки выберем E13; для расчетных значений неизвестных интенсивностей потока выделим диапазон ячеек A6: I6. В ячейки A8: A12 и целевую ячейку введем формулы для ограничений задачи и целевой функции в соответствии с приведенной ниже таблицей.

Рис. 3.14 Форма для решения примера 4

После вызова Поиска решения введем следующие ограничения:

В результате решения получим ответ:

и для интенсивностей дуговых потоков

Пример 5

Рассмотрим еще один пример решения задач подобного типа.

Имеется транспортная система, представленная сетевой моделью следующего вида (Рис. 3.15). Цифры у дуг означают удельные стоимости перевозки по дугам, соединяющим соответствующие узлы. Требуется определить маршрут, стоимость которого была бы минимальна.

Решение. Введем данные на рабочий лист в соответствии с Рис. 3.16.

Рис. 3.16 Форма для решения примера 5

Введем следующие формулы в указанные ячейки:

Введем все необходимые ограничения. С помощью Поиска решения получим ответ Маршрут, перевозка по которому имеет наименьшую стоимость, есть: (1−3-5−6-7).

Задача о кратчайшем маршруте

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

Пусть задана сеть, каждой дуге (ребру) которой соответствует некоторое расстояние. Требуется найти кратчайший маршрут из источника в сток .

Математическая постановка задачи имеет вид: минимизировать

при ограничениях

Приведем пример решения подобной задачи с помощью Microsoft Excel.

Пример 6

Транспортная система представлена схематически на Рис. 3.17. Расстояния между узлами сети указаны у соответствующих дуг (масштаб не соответствует реальным расстояниям). Требуется определить кратчайший (по расстоянию) маршрут между узлами 1 и 7.

Очевидно, задача сводится к определению минимума функции

при ограничениях

Смысл ограничений достаточно очевиден: необходимо, чтобы из узла 1 (источник) перевозимый продукт был отправлен (); в узел 7 (сток или приемник) продукт был доставлен (); полный поток через все промежуточные пункты должен быть равен нулю, так как предполагается, что продукт не остается ни в одном из них. Введем данные на рабочий лист в соответствии с Рис. 3.18.

Рис. 3.18. Форма для решения примера 6

Отведем под расчетные значения переменных ячейки A6: K6. Введем следующие функции для ограничений и целевую функцию

В окне диалога Поиска решения введем следующие ограничения:

После запуска Поиска решения получим ответ:

данному значению целевой функции, т. е. кратчайшему расстоянию между пунктами 1 и 7 соответствует маршрут (1,3) — (3,4) — (4,7), на что указывает отличие от нуля лишь переменных X13, X34, X47.