Оптимизация сетевого графа
Ниже приведено условие задачи и текстовая часть решения. Закачка полного решения, файлы doc и mcd в архиве zip, начнется автоматически через 10 секунд.
ПОСТАНОВКА ЗАДАЧИ
В издательском предприятии требуется выполнить работу по выпуску изделия, включающую пять операции: набор текста, корректура набора, обработка иллюстраций, верстка, вывод на пленку. Последовательность и нормы средней длительности выполнения операций приводятся в табл. 1.
Таблица 1
№ операции |
Наименование операции |
На какие опирации опирается |
Время выполнения операции, ч. |
А1 |
Набор текста |
- |
65 |
А2 |
Корректура набора |
А1 |
30 |
А3 |
Обработка иллюстраций |
- |
70 |
А4 |
Верстка |
А2, А3 |
60 |
А5 |
Вывод издания на пленку |
А4 |
20 |
Необходимо построить временной сетевой график выполнения работы, определить на графике критический путь всей работы, а также нормативное время критического пути.
Требуется за счет дополнительных доплат уменьшить продолжительность критического пути на 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 у. е.
Имя файла: 3.rar
Размер файла: 71.54 Kb
Если закачивание файла не начнется через 10 сек, кликните по этой ссылке