Оптимизация сетевого графа

ПОСТАНОВКА ЗАДАЧИ

     В издательском предприятии требуется выполнить работу по выпуску изделия, включающую пять операции: набор текста, коррек­тура набора, обработка иллюстраций, верстка, вывод на пленку. Последовательность и нормы средней длительности выполнения опе­раций приводятся в табл. 1.

Таблица 1

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

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

Таблица 2

Сумма доплат по категориям, у. е. в час.
Набор текста	Корректура текста	Обработка иллюстраций	Верстка	Вывод на плёнку
3,0	1,5	2,7	3,8	1,5

Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.

 

 

 

 

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ ЗАДАЧИ

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

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

Рис. 1. Примерный сетевой график выполнения работы.

Ось абсцисс изображает временную ось. Рядом с концами век­торов указаны соответствующие операции. Проекции векторов на временную ось определяют отрезки времени ti, i= 1, 2, 3, 4, 5, в тече­ние которых выполняются соответствующие работы. Стрелки показы­вают направление перехода.

На схеме A0 - это исходная точка, из которой начинается вы­полнение всех работ. В этой точке начинаются две работы, выполнение которых не зависит от каких либо других работ - набор текста и корректура набора текста. Вектора от точки А0 до точек А1 и А2 ото­бражают эти операции.

Точка А2 характеризует общее время t1+t2  завершения двух операций вместе: набор текста и корректура набора. Точка А3 опреде­ляет конец вектора, характеризующего завершение операции по обра­ботке иллюстраций. Эта операция начинается в точке А0 и не зависит от других операций. Операция верстки может выполняться только по­сле завершения корректуры набора и обработки иллюстраций. Так как операция подготовки иллюстраций завершается раньше, чем набор и корректура набора, от точки А3 проведен пунктиром фиктивный век­тор перехода к точке А2 (к верстке).

Критический путь - это минимальное время выполнения всех операций для данной работы без учета операций, не влияющих на это время (в данном случае это обработка иллюстраций). Для рассматри­ваемой задачи получается следующее критическое время:

F = t1+t2+t4+t5                  (1)

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

              (2)

Где Q(x) – целевая функция; х1, х2, х3, х4, х5 – суммы доплаты за выполнение операций сверх основной работы.

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

х0                              (3)

так как доплаты не могут быть отрицательными величинами.

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

                    (4)

где ti - норма времени на продолжительность выполнения i-й опе­рации;

xi/ci - величина уменьшения длительности выполнения i-й операции за счет дополнительной доплаты xi при расценке ci;

ti – xi/ci - длительность i-й операции с учетом доплаты;

Т- требуемое уменьшение критического времени.

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

(xi/ci)(ti/2),   i=1, 2, …., n.                   (5)

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

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

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

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

Для первого варианта модели следует записать два неравенства:

1) для реализации условия, которое состоит в том, что критиче­ский путь не изменяется, записывается неравенство

                 (6)

2) соблюдение условия, при котором время выполнения всей ра­боты должно быть уменьшено на величину, не меньшую, чем T часов:

          (7)

В другом варианте модели должны быть записаны условия для критического пути, в котором длительность обработки иллюстраций больше или равна длительности операций набора и корректировки набора вместе. В этом случае вместо (6) а (7) должны быть запи­саны неравенства

                     (8)

      (9)

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

Если в одном из вариантов решение отсутствует (ограничения противоречивы), то принимается существующее решение.

Окончательно построение модели оптимизации формулируется следующим образом: необходимо решить две задачи линейного про­граммирования для двух вариантов критического пути. С помощью каждой модели требуется определить вектор неизвестных х, при ко­тором обеспечивается минимум дополнительной оплаты - выражение (2), при ограничениях (3)-(9) для первого варианта задачи и ограничениях (3)-(5) и (8)-(9) для второго варианта.

 

 

 

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

Исходные данные для примера даны в табл. 1 и 2.

Для решения задачи линейного программирования в Mathcad используется функция minimize, записанная в следующем виде:

x= minimize(x, Q).

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

Сетевой график работ, приведенный на рис. 1, соответствует исходным данным, указанным в табл. 1 и 2. Как следует из графика, при заданных условиях в критическое время входят все операции, ис­ключая операцию обработки иллюстраций, время выполнения кото­рой не влияет на критическое время. Критическое время для этих ус­ловий согласно формуле (1) равно F = 175 ч.

В приложении 1 дано решение задачи в Mathcad для первого вари­анта критического пути. С помощью функции ORIGIN задается начало отсчета векторов с 1. В начальной части решения до ключевого слова Given приводятся исходные данные. Операции транспонирования вве­дены для компактности представления данных на экране. Вектор х с ну­левыми элементами определяет нулевые начальные условия, необходи­мые для решения задачи линейного программирования в Mathcad.

В фрагменте программы, начинающимся ключевым словом Given и заканчивающимся функцией minimize, содержится блок огра­ничений. Особенность имеет запись ограничения, описывающее ус­ловие (5). Оно выражаются в следующей векторной форме:

                   (10)

где стрелка вверху обозначает операцию векторизации, под кото­рой здесь понимается почленное перемножение элементов векторов (без последующего суммирования, как это выполняется в скалярном произведении). Векторизация осуществляется следующим образом: записывается произведение c∙t, затем оно выделяется мышью и на­жимается кнопка Vectorize () в панели Vector and Matrix. Скобки и стрелка вводятся автоматически.

В приложении 1 приводятся решение задачи оптимизации сете­вой модели методом линейного программирования. Получены мини­мальные суммы доплат по категориям xT= (30  22,5  0   95  15), при которых обеспечивается сокращение критического времени 60 часов, и величина затрат составит f(x) = 162,5 у. е. В приложении 2 приводятся результаты расчетов для второго варианта, когда критическим становится другой путь, включающий время обработки иллюстраций, если это время бу­дет превышать время набора и корректировки набора. В этом случае минимальная сумма доплат составит такое же значение 162,5 у. е.

Окончательно результатом решения задачи является первый  ва­риант модели, в которых критический путь включает операции набора и корректуры текста и обеспечивает уменьшение длительности выпол­нения работы на 60 часов при минимальной сумме доплаты 162,5 у. е.