Автор работы: Пользователь скрыл имя, 12 Декабря 2012 в 16:01, курсовая работа
Целью курсовой работы является изучение основ календарного планирования с помощью решения задач, характерных для данного вида математического моделирования.
Указанная цель обусловила постановку и решение следующих задач:
рассмотреть основы календарного планирования;
решить основные задачи календарного планирования.
Введение……………………………………………………………………...
3
Глава 1.
Теоретические аспекты календарного планирования……
5
1.1. Понятие календарного планирования ……………………
5
1.2. Характеристика моделей календарного планирования….
6
1.3. Методы решения задач календарного планирования……
7
Глава 2.
Примеры решения основных задач календарного планирования.………………………………………………….
12
2.1. Задача Джонсона о двух станках ……………………….
12
2.2. Задача о назначениях ………………………...…………….
14
2.3. Задача о замене оборудования…………………………….
21
Заключение………………………………………………………………….
29
Литература…………………….……………………
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)
Введем следующие обозначения:
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).
Для принятия решения необходимо вычислить функцию Беллмана f1(t), которая для нашего случая имеет вид:
Z(t) – U(t) сохранение машины;
f1(t)=max S(t) – P + Z(0) – U(0)
замена машины.
(3)
Задача будет решена, если мы определим прибыль за весь плановый период, т.е. найдем значение функции fN(t). Вначале попытаемся установить связь между выражениями
fn+1 и fn
Если связь между ними будет найдена, то последовательно, двигаясь с конца, где 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).
В случае замены машины аналогичной имеем:
S(t) - Р + Z(0) – U(0) + fn(1).
Для принятия окончательного решения вычислим функцию Беллмана вида
Z(t) – U(t) + fn(t+1) сохранение машины;
fn+1(t)=max
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
fn(1) замена машины.
Используя полученные формулы, вычислим значения функций Беллмана fn(t) при различных n и t. Значения функций будем вписывать в таблицу 5.
Таблица 5
Решение задачи о замене оборудования с использованием метода
динамического программирования
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | |
f1(t) |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
f2(t) |
19 |
17 |
15 |
13 |
11 |
9 |
9 |
9 |
9 |
9 |
9 |
f3(t) |
27 |
24 |
21 |
18 |
17 |
17 |
17 |
17 |
17 |
17 |
17 |
f4(t) |
34 |
30 |
26 |
24 |
24 |
24 |
24 |
24 |
24 |
24 |
24 |
f5(t) |
40 |
35 |
32 |
31 |
30 |
30 |
30 |
30 |
30 |
30 |
30 |
f6(t) |
45 |
41 |
39 |
37 |
36 |
35 |
35 |
35 |
35 |
35 |
35 |
f7(t) |
51 |
48 |
45 |
43 |
41 |
41 |
41 |
41 |
41 |
41 |
41 |
f8(t) |
58 |
54 |
51 |
48 |
48 |
48 |
48 |
48 |
48 |
48 |
48 |
f9(t) |
64 |
60 |
56 |
55 |
54 |
54 |
54 |
54 |
54 |
54 |
54 |
f10(t) |
70 |
65 |
63 |
61 |
60 |
60 |
60 |
60 |
60 |
60 |
60 |
Заполнение таблицы будем производить по строкам: сначала заполним первую строку, потом вторую и т. д. Заметим, что согласно формуле (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 (на старую заменять невыгодно).