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

Автор работы: Пользователь скрыл имя, 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

Литература…………………….……………………

Файлы: 1 файл

КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ.doc

— 312.50 Кб (Скачать файл)

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

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

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

 

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 (на старую заменять невыгодно).

Информация о работе Календарное планирование