Заболотников_9373_ПР2

МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра Информационных систем

ПРАКТИЧЕСКАЯ РАБОТА по дисциплине «Теория принятия решений»

Тема: "Применение методов линейного и динамического программирования для решения практических задач"

Вариант №42 (394)

Санкт-Петербург

2022

1

СОДЕРЖАНИЕ

Ведение…………………………………………………………..... 3

1.Задача об оборудовании………………………………………….. 4

1.1.Условие задачи……………………………………………………. 4

1.2.Формализация задачи…………………………………………….. 6

1.3.Решение задачи…………………………………………………… 7

Заключение………………………………………………………... 12

Приложение А…………………………………………………….. 13

2

ВВЕДЕНИЕ

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

3

1.ЗАДАЧА ОБ ОБОРУДОВАНИИ

1.1.Условие задачи

На рынке представлено специализированное технологическое оборудование двух марок: М1 и М2. На производственном предприятии в данный момент используется оборудование марки M1, возраст которого составляет 2 года. Остаточная стоимость оборудования и годовая стоимость обслуживания оборудования в зависимости от срока эксплуатации приведены в табл. 2. Стоимость инструктажа персонала производственной линии при смене типа оборудования 550 тыс. руб. (в любом случае, независимо от того,

был ли ранее опыт работы с оборудованием соответствующей марки),

стоимость нового оборудования марки M1 – 12500 тыс. руб., а М2 – 9500 тыс.

руб.

Таблица 1 – Затраты, связанные с эксплуатацией оборудования

4

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

5

1.2.Формализация задачи

Этапы: этапами являются года.

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

Цель: минимизировать проигрыш.

Управление: {0, 1, 2}, где 0 – не менять оборудование, 1 – поменять оборудование на новое (М1), а 2 – поменять на новое оборудование (М2).

Состояние буем обозначать как: = текущая марка; возраст. При этом

0 = 1; 2.

Проигрыш на -ом шаге:

( ; 0) = обслуживание( ) + +1;

( ; 1) = обновление(М1) – остаточная стоимость( ) + обслуживание(М1) + +1;

( ; 2) = обновление(М2) – остаточная стоимость( ) + обслуживание(М2) + +1.

6

1.3.Решение задачи

Решать данную задачу будем методом динамического программирования, а именно методом обратной прогонки. А перед тем, как проводить сам метод, определим несколько функций:

def win(m, a, u): mark = m

age = a if(u == 0):

w = servicing[mark - 1][age] elif(u == 1):

w = servicing[0][0] + change_cost[0] - sell_price[age][mark - 1] + 550 * int(mark != 1)

elif(u == 2):

w = servicing[1][0] + change_cost[1] - sell_price[age][mark - 1] + 550 * int(mark != 2)

return w

Эта функция будет высчитывать затраты при определённом выборе управления. Следующая функция:

def state_transition(m, a, u): if(u == 0):

age = a + 1 mark = m

else:

age = 1 mark = u

s = 10 * mark + age return s

будет высчитывать то состояние, в которое мы перейдём из текущего путём выбора какого-либо управления. Состояние будет обозначаться двузначным числом, число десятков которого будет показывать тип оборудования, а число единиц – возраст оборудования.

Теперь перейдём непосредственно к алгоритму. Для начала определим список, -й элемент которого будет соответствовать значению функции Беллмана для -ого этапа (года). Каждый элемент этого списка будет

7

представлять из себя словарь, ключами в котором будут состояния, а

значениями – пары (значение функции Беллмана, условно-оптимальное управление):

W_table = [{} for i in range(6)]

Установим заведомо невыгодное значение:

NINF = 10000000

Теперь начинаем расчёт с последнего этапа. Поскольку мы не знаем, в

каком состоянии мы окажемся к началу последнего, шестого года, вычисляем функцию Беллмана для всех возможных состояний:

for marks in [1, 2]: if(marks == 1):

for age in [1, 2, 3, 4, 5, 6, 7]: index = 10 + age W_table[5][index] = (NINF, None) for u in range(3):

if(u == 0):

W = win(1, age, u) - sell_price[age + 1][marks - 1] else:

W = win(1, age, u) - sell_price[1][u - 1] if W_table[5][index][0] > W:

W_table[5][index] = (W, u)

if(marks == 2):

for age in [1, 2, 3, 4, 5]: index = 20 + age

W_table[5][index] = (NINF, None) for u in range(3):

if(u == 0):

W = win(2, age, u) - sell_price[age + 1][marks - 1] else:

W = win(2, age, u) - sell_price[1][u - 1] if W_table[5][index][0] > W:

W_table[5][index] = (W, u)

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

предпоследнего этапа:

for marks in [1, 2]:

8

if(marks == 1):

for age in [1, 2, 3, 4, 5, 6]: index = 10 + age

W_table[4][index] = (NINF, None) for u in range(3):

W = win(1, age, u) + W_table[5][state_transition(1,

age, u)][0]

if W_table[4][index][0] > W: W_table[4][index] = (W, u)

if(marks == 2):

for age in [1, 2, 3, 4]: index = 20 + age

W_table[4][index] = (NINF, None) for u in range(3):

W = win(2, age, u) + W_table[5][state_transition(2,

age, u)][0]

if W_table[4][index][0] > W: W_table[4][index] = (W, u)

Для остальных этапов принцип подсчета будет точно таким же, поэтому

его удобно организовать в виде цикла:

for i in reversed(range(5)): for marks in [1, 2]:

if(marks == 1):

for age in range(i + 3): if(age != 0):

index = 10 + age W_table[i][index] = (NINF, None) for u in range(3):

W = win(1, age, u) + W_table[i + 1][state_transition(1, age, u)][0]

if W_table[i][index][0] > W: W_table[i][index] = (W, u)

if(marks == 2):

for age in range(i + 1): if(age != 0):

index = 20 + age W_table[i][index] = (NINF, None)

9

for u in range(3):

W = win(2, age, u) + W_table[i +

1][state_transition(2, age, u)][0]

if W_table[i][index][0] > W: W_table[i][index] = (W, u)

Посмотрим на результаты выполнения программы:

Если мы посмотрим на рисунок, то, найдя наше изначальное состояние

(оборудование марки М1, возраст которого составляет 2 года), поймём, что этому значению соответствует значение функции Беллмана, равное 128 (тыс.

рублей). Число "0" рядом говорит нам о том, что мы должны путём нулевого управления перейти из состояния 12 в состояние 13. А дальше всё аналогично:

Переход из состояния 21 в 21

10