Календарное планирование

Пример. Дана матрица ресурсов

С=(сij)=

Распределить ресурсы матрицы С по четырем объектам.

Решение. 1-й шаг. Значение минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим матрицу вида

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 5, 0, 0, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим:

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

3-й шаг. Вычеркиваем столбец 1, строку 3, строку или столбец 2. значение минимального невычеркнутого элемента равно 2:

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

Следовательно, оптимальное решение:

          Хопт =

Таким образом, первый ресурс направляем на 3-й объект, второй – 2-й объект, третий ресурс – на 4-й объект, четвертый – на 1-ый объект. Стоимость назначения: 9+4+11+4=28.

Примечания:

1) Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2) Если какой-либо ресурс не может быть назначен на какой-то объект, то соответствующая стоимость полагается равной достаточно большому числу М.

3) Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на -1 и сложить с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем следует решать задачу минимизации целевой функции.

4) Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов (квадратной матрицы), то существует назначение нулевой стоимости.

Пример:

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

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

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

Минимальные элементы в строках равны 3, 4, 4, 6, 4. вычтем их из соответствующих элементов матрицы:

Так как назначение не получено, вычеркиваем строку 2, столбы 2, 4, 5:

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

Оптимальное решение, соответствующее последней матрице:

Суммарная производительность: 6+6+3+6+7=28

Таким образом, наибольшая суммарная производительность станков цеха будет равна 28 деталям в единицу времени, при этом за первым станком надо закрепить 5-ю операцию, за вторым – 1-ю операцию, за третьим – 4-ю операцию, за четвертым – 3-ю операцию, за пятым станком – 2-ю операцию.

2.3 Задача о замене оборудования [7]

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

Оборудование со временем изнашивается, стареет физически и «морально»; в процессе эксплуатации либо падает производительность оборудования, либо растут эксплуатационные расходы, либо и то и другое. Поэтому задача о замене оборудования весьма актуальна.

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

Переход системы S из одного состояния в другое за 1 год в зависимости от принятого решения можно изобразить графически (рисунок 1).

Рисунок 1.Переход системы из одного состояния в другое

Введем в рассмотрение функцию fn(t) - величину суммарного дохода (прибыли) за последние n лет планового периода при условии, что в начале этого периода из n лет имеется машина возраста t.

Функции f1(t), f2(t), ...,fn(t) учитывающие вклад последующих шагов в общий эффект, называются функциями Беллмана — по фамилии американского математика Р. Беллмана, создателя метода динамического программирования. С помощью этих функций ведется анализ задач динамического программирования. Очевидно, если мы сумеем вычислить fn(t0) и найти политику замен, то это и будет решение задачи.

Предположим, что к началу последнего года планового периода n=1 у нас имеется машина возраста t. В нашем распоряжении две возможности. Рассмотрим их.

Возможность 1-я: сохранить машину и, следовательно, получить за последний год доход

                         Z(t) - U(t)                                                                     (1)

Введем следующие обозначения:

t — возраст машины: t=0, 1, 2,..., (t=0 - соответствует использованию новой машины, t=1 — соответствует использованию машины возраста 1 год и т.д.);

Z(t) — стоимость продукции, производимой за 1 год на машине возраста t;

U(t) - эксплуатационные затраты за 1 год на машину возраста г;

S(t) — остаточная стоимость машины возраста t;

Т — текущее время в плановом периоде;

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

T0 - начальный возраст машины;

N — длина планового периода.

Мы сделали ряд упрощений, чтобы не осложнять анализа задачи. Так, например, мы считаем, что функции Z(t), U(t), S(t) не зависят от текущего времени.

В нашей задаче в качестве системы S рассматривается машина, набор параметров, характеризующих ее состояние, состоит из единственного параметра — возраста машины. В качестве возможных управлений рассматриваются два решения — о сохранении имеющейся машины и о ее замене на новую. Условимся считать, что решения принимаются в моменты n = N; N — 1,.. 1. Таким образом, плановый период разбит на шаги длиной в 1 год и в каждый из них решается — сохранить или заменить машину .

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

                      S(t) - Р + Z(0) - U(0).                                                     (2)                                   

Для принятия решения необходимо вычислить функцию Беллмана f1(t), которая для нашего случая имеет вид:

                  Z(t) – U(t)                      сохранение машины;

f1(t)=max S(t) – P + Z(0) – U(0)    замена машины.                                  (3)                                                                                                                                                                   

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

                         fn+1 и fn                                                                        (4)

Если связь между ними будет найдена, то последовательно, двигаясь с конца, где n = 1, и зная f1(t), сможем найти f2(t),…,fn(t),…,fN(t) и тем самым решить задачу

Итак, предположим, что с конца планового периода остается n + 1 год; в нашем распоряжении имеется машина возраста t и мы ищем оптимальную политику для периода длиной n + 1 год. Этот период разбивается на две части (рисунок 2).

                                   1              n-лет

Рисунок 2.Период длиной n+1

Рассмотрим все возможные решения в «первом году» для машины возраста t и для каждого состояния системы найдем оптимальную политику в оставшейся части из n последних лет. Так мы получим политики на весь период из n + 1 последних лет, лучшая из которых и будет условно оптимальной для всего периода.

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

                    Z(t) - U(t) + fn(t+1).                                                          (5)

В случае замены машины аналогичной имеем:

                    S(t) - Р + Z(0) – U(0) + fn(1).                                          (6)

Для принятия окончательного решения вычислим функцию Беллмана вида

                      Z(t) – U(t) + fn(t+1)                      сохранение машины;

fn+1(t)=max                                                                                                      (7)                                                                                                                               

                        S(t) – P + Z(0) – U(0) + fn(1)        замена машины.

Рекуррентные формулы (3; 7) позволяют реализовать концепцию динамического программирования и развернуть процесс нахождения оптимальной политики с конца, последовательно находя f1(t), f2(t),…,fn(t),…,fN(t) для различных значений t.

Пример. Пусть функции Z(t), U(t) и значения ∆ = Z(t) – U(t) заданы табл.

Мы ограничились машиной возраста t < 10 лет, так как из табл. видно, что машина возраста t > 10 лет невыгодна. Будем считать условно (для простоты вычислений), что:

1) остаточная стоимость машины равна 0;

2) цена новой машины со временем не меняется и равна 10 условным единицам;

3) длина планового периода N равна 10 годам, т. е. S(t) = 0; Р=10.

Таблица 4

Исходные данные

Тогда формулы (3 и 7) принимают вид

f1(t) = Z(t) — U(t)       сохранение машины.                                      (8)

                      Z(t) – U(t) + fn(t+1)        сохранение машины;

fn+1(t)=max                                                                                                      (9)                                                                                                                               

                        fn(1)                                замена машины.

Используя полученные формулы, вычислим значения функций Беллмана fn(t) при различных n и t. Значения функций будем вписывать в таблицу 5.

Таблица 5

Решение задачи о замене оборудования с использованием метода

динамического программирования