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

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

В этом случае рекуррентные формулы (3; 7) существенно усложняются. Динамическое программирование позволяет учесть все решения (управления), которые вызывают практический интерес.

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

Заключение

Изучив основные вопросы, связанные с календарным планированием, подведем итог.

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

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

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

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

Литература

1. Математические методы и модели исследования операций: Учебник / В.А. Колемаев.- М-: Юнити-Дана, 2007. – С. 592;

2. Формирование и оперативное управление производст­венными системами на базе поточно-группового про­изводства в автоматизированном режиме: Учебное пособие / Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. – С. 60;

3. Задачи и методы конечной оптимизации: Учебное пособие, 3 часть / Д.И. Коган.- Н. Новнород-: ННГУ, 2004. – С. 150;

4. Математика в экономике: Математические методы и модели: Учебник / М.С. Красс, Б.П. Чупрынов.- М-: Финансы и статистика, 2007. – С. 544;

5. Математические методы моделирования экономических систем: Учебное пособие— 2-е изд., перераб. и доп. / Е.В. Бережная — М.: Финансы и статистика, 2006. - С. 432.

30

[1] Формирование и оперативное управление производст­венными системами на базе поточно-группового про­изводства в автоматизированном режиме: Учебное пособие / Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. – С. 14-17.

[2] Математические методы и модели исследования операций: Учебник / В.А. Колемаев.- М-: Юнити-Дана, 2007. – С. 297-298.

[3] Формирование и оперативное управление производст­венными системами на базе поточно-группового про­изводства в автоматизированном режиме: Учебное пособие / Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. – С. 25-29.

[4] Формирование и оперативное управление производст­венными системами на базе поточно-группового про­изводства в автоматизированном режиме: Учебное пособие / Л.В. Михайлова.- М-: ИТЦ МАТИ, 2002. – С. 36-38.

[5] Задачи и методы конечной оптимизации: Учебное пособие / Д.И. Коган.- Н. Новнород-: ННГУ, 2004. – С. 52-53.

[6] Математика в экономике: Математические методы и модели: Учебник / М.С. Красс, Б.П. Чупрынов.- М-: Финансы и статистика, 2007. – С. 306-311.

[7] Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. / Е.В. Бережная — М.: Финансы и статистика, 2006. - С. 368-374