Задача о замени оборудования

 

 

 

2011

 

Содержание

Введение		3
	Постановка задачи и описание модели	4
	Контрольный пример	6
	Разработка алгоритма
	Разработка блок схем
	Код программы
	Оформление пояснительной записки

 

ВВЕДЕНИЕ

 

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

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

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

 

1. Постановка задачи и описание модели

 

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

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

 

Рис.1 – Переход системы S из состояния «новое» состояние за 1 год

 

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

Функции , , …, , учитывающие вклад последующих шагов в общий эффект, называются функциями Беллмана – по фамилии американского математика Р. Беллмана, создателя метода динамического программирования. С помощью этих функций ведется анализ задач динамического программирования. Очевидно, если мы сумеем вычислить и найти политику замен, то это и будет решение задачи.

 

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

 

t	–	Возраст машины: t = 0, 1, 2, … (t = 0 – соответствует использованию новой машины, t = 1 – соответствует использованию машины возраста 1 год и так далее);
Z(t)	–	Стоимость продукции, производимой за 1 год на машине возраста t;
U(t)	–	Эксплутационные затраты за 1 год  на машину возраста t;
S(t)	–	Остаточная стоимость машины возраста t;
T	–	Текущее время в плановом периоде;
P(T)	–	Цена новой машины в году t;
	–	Начальный возраст машины;
N	–	Длина планового периода.

 

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

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

Z(t) – U(t).

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

S(t) – P + Z(0) – U(0).

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

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

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

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

  (1.1)

 

2. Описание алгоритма решения

 

Входные данные:

 

1. N – длина планового периода;
2. Z(N) – стоимость продукции, производимой в t – м году на машине возраста t;
3. U(N) – эксплуатационные затраты за один год на машину возраста t;
4. S(N) – остаточная стоимость машины возраста t;
5. P(N) – цена новой машины в t-м году.

 

Выполнение операций:

1. проверка корректности входных данных
1. все входные данные не должны быть отрицательными
2. Z(N) – строго убывает
3. U(N) – строго возрастает
2. вычисление и запись в таблицу 2.2;
3. вычисление где n = 1, N – 1, t = 0, N – 1

 

Выходные данные:

1. таблица решения(матрица f), где черным цветом обозначена политика сохранения машины и красным – замена.

 

Дополнительные переменные

 

Save = f(1, t) + f(i, t+1) – промежуточный результат, характерезующая сохранение оборудования;

Zam = s(t) – p(t) +f(1,0)+f(i,1) – промежуточный результат, характерезующая замену оборудования.

 

Функция проверки входных данных

 

Test_data

 

 

 

 

 

 

3. Контрольный пример

 

Пусть функции Z(t), U(t) заданы табл.3 2.1.

Дано:

Длина планового периода N равна 10 годам,

 

Таблица 2.1

t	0	1	2	3	4	5	6	7	8	9	10
Z(t)	20	20	20	19	19	18	18	17	17	16	15
U(t)	10	11	12	12	13	13	14	14	15	15	15

 

Ограничимся машиной возраста меньше 10 лет. Для простоты решения нужно принять:

1. Остаточная стоимость машины равна 0 (S(t) = 0);
2. Цена новой машины со временем не меняется и равна 10 условным единицам (P(t) = P = 0);
3. Длина планового периода равно 10 (N = 10)

 

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

 

Таблица 2.2

 

t	0	1	2	3	4	5	6	7	8	9	10
	10	9	8	7	6	5	4	3	2	1	0
	19	17	15	13	11	9	9	9	9	9	9
	27	24	21	18	17	17	17	17	17	17	17
	34	30	26	24	24	24	24	24	24	24	24
	40	35	32	31	30	30	30	30	30	30	30
	45	41	39	37	36	35	35	35	35	35	35
	51	48	45	43	41	41	41	41	41	41	41
	58	54	51	48	48	48	48	48	48	48	48
	64	60	56	55	54	54	54	54	54	54	54
	70	65	63	61	60	60	60	60	60	60	60

 

Решение:

 

(0) = Z(0) – U(0) = 20 – 10 = 10

(1) = Z(1) – U(1) = 20 – 11 = 9

(2) = Z(2) – U(2) = 20 – 12 = 8

(3) = Z(3) – U(3) = 19 – 12 = 7

(4) = Z(4) – U(4) = 19 – 13 = 6

(5) = Z(5) – U(5) = 18 – 13 = 5

(6) = Z(6) – U(6) = 18 – 14 = 4

(7) = Z(7) – U(7) = 17 – 14 = 3

(8) = Z(8) – U(8) = 17 – 15 = 2

(9) = Z(9) – U(9) = 16 – 15 = 1

(10) = Z(10) – U(10) = 15 – 15 = 0

 

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

Так как  тогда формула (1.1) примет вид:

 

 

 сохранение оборудования

 сохранение оборудования

 сохранение оборудования

 сохранение оборудования

 сохранение оборудования

 сохранение оборудования

 замена оборудования

 замена оборудования

 замена оборудования

 замена оборудования

 замена оборудования

 

Аналогично выполняются следующие  шаги с 3 по 10 ( по ).

 

Утойчивость программы

 

 

Имя проекта  вводится любые символы кроме: «.»; «/»; «,»; «[»; «]»;«{»; «}».

Длина планового  периода это целое число от 2 до 99.

 

 

Z(t), U(t), S(t), P(T), P, S – положительное число дробного типа;

Z(t) – числа строго убывают;

U(t) – числа строго возрастают.

 

Заключение

 

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

К классу задач динамического программирования относится множество различных задач. В данной курсовой работе был расссмотрен раздел «Задачи о замене оборудования» и реализован программный продукт для нахождения оптимального плана замены оборудования.

В роли инструмента для разработки программного продукта была использована среда Delphi.

 

Список используемой литературы

 

1. Вентцель Е.С. Элементы динамического программирования.- М.: Наука, 1964.
2. Карманов В.Г. Математическое программирование. –М.: Наука, 1986.
3. Терехов Л.Л. Экономико-математические методы.- М.: Статистика, 1972.