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

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

С=(сij)=

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

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

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

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

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

Решение. В задаче требуется найти максимум целевой функции, в то время как алгоритм метода дан для задач на минимум. Поэтому умножим матрицу С на -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                                                                                                         (3)                                                                              

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

Задача будет решена, если мы определим прибыль за весь плановый период, т.е. найдем значение функции 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

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

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

Заполнение таблицы будем производить по строкам: сначала заполним первую строку, потом вторую и т. д. Заметим, что согласно формуле (8) первая строка таблицы 5 совпадает с последней строкой таблицы 4.

Теперь перейдем к заполнению второй строки таблицы:

Здесь обе политики - сохранения и замены – обеспечивают одинаковую прибыль — 9 единиц, выбираем в этом случае «старую» машину, к которой «привыкли». Далее

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

Итак, значение f2(6) в таблице будет записано красным цветом.

Можно показать, что f2(7) = f2 (8) = f2 (9) = f2 (10) = 9 и соответствует замене машины.

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

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

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

Величина максимальной прибыли (согласно таблице 5) определяется функцией Беллмана f10(7) = 60. Теперь найдем оптимальную политику, обеспечивающую эту прибыль.

Так как f10(7) вписано в таблицу красным цветом, то для достижения максимальной прибыли необходимо в первом году рассматриваемого периода заменить машину на новую. По истечении одного года мы за 9 лет до конца планового периода будем иметь машину возраста один год. Теперь надо действовать оптимально в оставшийся период, располагая машиной возраста один год, т. е. найти f9(1) из девяти лет. Из таблицы 5 видно, что f9(1) - черное, следовательно, во втором году надо сохранить машину. Рассматривая процесс по годам, замечаем: f8(2) - черное, f7(3) - черное, f6(4) - черное, f5(5) - красное. Последнее выражение (f5(5) - красное) указывает на то, что по истечении пяти лет планового периода машину надо менять на новую. Действуя далее оптимально, найдем последовательно: f4(1) - черное, f3(2) - черное, f2(3) - черное, f1(4) — черное. Итак, используя табл. 2, мы найдем оптимальную политику, которую можно представить схемой

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