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

Название	Применение методов линейного и динамического программирования для решения практических задач (по
Дата	10.06.2019
Размер	34.38 Kb.
Формат файла
Имя файла	kursach.docx
Тип	Курсовая #81227

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра Информационных систем

Курсовая РАБОТА

по дисциплине «Теория принятия решений»

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

Вариант: 18

Студентка гр. 6373		Хетеева М.Р.
Преподаватель		Понамарев А.В.

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

2019

ЗАДАНИЕ

на курсовую работу

Студентка Хетеева М.Р.
Группа 6373
Тема работы: Применение методов линейного и динамического программирования для решения практических задач (по вариантам)
Исходные данные: Текст индивидуального задания на курсовую работу в соответствии с назначенным вариантом (см. https://avponomarev.bitbucket.io/tasks/18.pdf).
Содержание пояснительной записки: «Содержание», «Введение», «Задача о магистрали», «Задача об оборудовании», «Задача об акциях», «Заключение», «Список использованных источников».
Преолагаемый объем пояснительной записки: Не менее 15 страниц.
Дата выдачи задания:
Дата сдачи реферата:
Дата защиты реферата:
Студентка		Хетеева М.Р.
Преподаватель		Понамарев А.В.

Аннотация
Кратко (в 8-10 строк) указать основное содержание курсового проекта (курсовой работы), методы исследования (разработки), полученные результаты.

Summary
Briefly (8-10 lines) to describe the main content of the course project, research methods, and the results.
содержание

	Введение	4
1.	Задача	5
Условие		0
1.2.		0
2.		0
2.1.		0
2.2.		0
3.		0
3.1.		0
3.2.		0
	Заключение	0
	Список использованных источников	0
	Приложение А. Название приложения	0

введение
Кратко описать цель работы, основные задачи им методы их решения.

1. Задача о магистрали

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

На строительство магистрали периодически доставляются материалы, которые со станции железной дороги вначале поступают на 3 промежуточных склада, а затем непосредственно к 5 объектам магистрали. Два первых склада А1, А2 имеют ограниченную емкость 60 т, и поступившие на них грузы расходуются полностью. Cклад А3 с неограниченной емкостью допускает резервирование грузов от периода к периоду. Транспортные расходы (в условных денежных единицах — ДЕ) на перевозку одной тонны груза со станции на промежуточные склады составляют 6, 6, 6 ДЕ, а со складов к объектам В1–В5 представлены в табл. 1; там же приведены потребности объектов (в тоннах) в течение двух периодов.

Таблица 1: Транспортные расходы

	В1	В2	В3	В4	В5
А1	7	12	10	7	3
А2	1	4	12	9	4
А3	1	10	2	3	10
1-й период	65	10	23	22	15
2-й период	18	23	8	45	9

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

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

Данная задача является задачей линейного программирования.

Пусть:

x1, x2, x3 - объём на A1, A2, A3 за все периоды

xi(k) - объём поставки на i-й промежуточный склад в k-й период, i = 1..3, k = 1,2.

xij(k) - Перевоз с i склада в j склад в k-й период, i = 1..3, j = 1...5, k = 1,2.
Тогда целевая функция для первого периода:

6x1 + 6x2 + 6x3 + 7x11(1) + 12x12(1) + 10x13(1) + 7x14(1) + 3x15(1) +1x21(1)+ +4x22(1) + 12x23(1) + 9x24(1) + 4x25(1) +1x31(1) + 10x32(1) + 2x33(1) + 3x34(1)++ 10x35(1)  min

Целевая функция для второго периода:

6x1 + 6x2 + 6x3 + 7x11(2) + 12x12(2) + 10x13(2) + 7x14(2) + 3x15(2) +1x21(2) + +4x22(2) + 12x23(2) + 9x24(2) + 4x25(2) +1x31(2) + 10x32(2) + 2x33(2) + 3x34(2)+ + 10x35(2)  min

Ограничения для первого периода:

Ограничения на целесообразность задачи:

xij(1) >= 0 для всех i, j

Ограничения на поставку:

x1(1) + x2(1) + x3(1) = 140

Ограничения на потребление:

7x11(1) + 1x21(1) + 1x31(1) = 65

12x12(1) + 4x22(1) + 10x32(1) = 10

10x13(1) + 12x23(1) + 2x33(1) = 23

7x14(1) + 9x24(1) + 3x34(1) = 22

3x15(1) + 4x25(1) + 10x35(1) = 15

Ограничения на остаток:

x1(1) = x11(1) + x12(1) + x13(1) + x14(1) + x15(1)

x2(1) = x21(1) + x22(1) + x23(1) + x24(1) + x25(1)

x3(1) >= x31(1) + x32(1) + x33(1) + x34(1) + x35(1)

Ограничения на объём складов:

x1(1) <= 60

x2(1) <= 60
Ограничения для второго периода:

Ограничения на целесообразность задачи:

xij(2) >= 0 для всех i, j

Ограничения на поставку:

x1(2) + x2(2) + x3(2) = 140

Ограничения на потребление:

7x11(2) + 1x21(2) + 1x31(2) = 18

12x12(2) + 4x22(2) + 10x32(2) = 23

10x13(2) + 12x23(2) + 2x33(2) = 8

7x14(2) + 9x24(2) + 3x34(2) = 45

3x15(2) + 4x25(2) + 10x35(2) = 9

Ограничения на остаток:

x1(2) = x11(2) + x12(2) + x13(2) + x14(2) + x15(2)

x2(2) = x21(2) + x22(2) + x23(2) + x24(2) + x25(2)

x3(2) >= x31(2) + x32(2) + x33(2) + x34(2) + x35(2)

Ограничения на объём складов:

x1(2) <= 60

x2(2) <= 60

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

Данную задачу будем решать в два шага. Первый шаг – нахождение оптимального решения и проведение анализа чувствительности для первого периода, второй – то же самое для второго периода. Затем сложим полученные решения для обоих периодов и получим решение задачи.
Код решения на Python для первого периода:

# для первого периода

from cvxopt import matrix,solvers

c = matrix([-6,-6,-6,-7,-12,-10,-7,-3,-1,-4,-12,-9,-4,-1,-10,-2,-3,-10], tc = 'd')

G = matrix([[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1],

[0,0,-1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1]], tc = 'd')
A = matrix ([[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0],

[0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0],

[0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0],

[0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0],

[0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1],

[-1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],

[0,-1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0]], tc = 'd')
h = matrix([60,60,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], tc = 'd')
m = matrix([140,65,10,23,22,15,0,0], tc = 'd')
solution = solvers.lp(c, G.T, h, A.T, m, solver = 'glpk')
print('Status:', solution['status'])

print('Objective:', solution['primal objective'])

print('x = \n', solution['x'])
#анализ чувствительности

print('analis rav,', solution['y'])
Результат работы программы:

Status: optimal

Objective: -1989.0

x =

[ 6.00e+01]

[ 5.00e+01]

[ 3.00e+01]

[ 6.00e+01]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 5.00e+00]

[ 0.00e+00]

[ 2.30e+01]

[ 2.20e+01]

[ 0.00e+00]

[ 0.00e+00]

[ 1.00e+01]

[ 0.00e+00]

[ 0.00e+00]

[ 1.50e+01]
analis rav, [ 6.00e+00]

[ 1.00e+00]

[ 1.00e+01]

[ 1.20e+01]

[ 9.00e+00]

[ 1.00e+01]

[ 6.00e+00]

[-0.00e+00]
Код программы решения для второго периода:
#для второго периода
from cvxopt import matrix,solvers

c = matrix([-6,-6,-6,-7,-12,-10,-7,-3,-1,-4,-12,-9,-4,-1,-10,-2,-3,-10], tc = 'd')

G = matrix([[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0],

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1],

[0,0,-1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1]], tc = 'd')
A = matrix ([[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],

[0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0],

[0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0],

[0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0],

[0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0],

[0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1],

[-1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0],

[0,-1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0]], tc = 'd')
h = matrix([60,60,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], tc = 'd')
m = matrix([140,18,23,8,45,9,0,0], tc = 'd')
solution = solvers.lp(c, G.T, h, A.T, m, solver = 'glpk')
print('Status:', solution['status'])

print('Objective:', solution['primal objective'])

print('x = \n', solution['x'])
#анализ чувствительности

print('analis rav,', solution['y'])
Результат:

Status: optimal

Objective: -1833.0

x =

[ 4.10e+01]

[ 5.30e+01]

[ 4.60e+01]

[ 1.80e+01]

[ 2.30e+01]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 8.00e+00]

[ 4.50e+01]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 0.00e+00]

[ 9.00e+00]
analis rav, [ 6.00e+00]

[ 7.00e+00]

[ 1.20e+01]

[ 1.20e+01]

[ 9.00e+00]

[ 1.00e+01]

[-0.00e+00]

[-0.00e+00]
Таким образом, мы можем сделать вывод, что

оптимальным решения нашей задачи является значение 1989+1833 = 3822 ДЕ при опорном плане, равном:

Таблица 2 : опорный план оптимального решения.

Коэффициенты 1-ого периода	Значения	Коэффициенты 2-ого периода	Значения
х1(1)	60	х1(2)	41
x2(1)	50	x2(2)	53
x3(1)	30	x3(2)	46
x11(1)	60	x11(2)	18
x12(1)	0	x12(2)	23
x13(1)	0	x13(2)	0
x14(1)	0	x14(2)	0
x15(1)	0	x15(2)	0
x21(1)	5	x21(2)	0
x22(1)	0	x22(2)	0
x23(1)	23	x23(2)	8
x24(1)	22	x24(2)	45
x25(1)	0	x25(2)	0
x31(1)	0	x31(2)	0
x32(1)	10	x32(2)	0
x33(1)	0	X33(2)	0
x34(1)	0	x34(2)	0
x35(1)	15	x35(2)	9

оптимальное решение изменится на 0+6 = 6 ДЕ при изменении цен перевозок из первого промежуточного пункта

2. Задача об оборудовании

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

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

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

Возраст	М1		М2
Возраст	Остаточная стоимость, тыс.руб.	Обслуживание, тыс.руб	Остаточная стоимость, тыс.руб.	Обслуживание, тыс.руб
0	-	400	-	600
1	10800	480	8550	720
2	9720	576	7695	936
3	8748	691	5540	1216
4	7000	829	4432	1460
5	5598	995	3545	1752
6	4478	1194	2800	2100
7	3583	1433	2200	2100
8	2866	1500	2200	2100
9	2800	1500	2200	2100
10	2800	1500	2200	2100

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

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

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

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

Управление: u{0; 1; 2}

0 – не менять оборудование.

1 – поменять оборудование на новое M1.

2 – поменять оборудование на новое М2.

Состояние: S_i = текущая марка;возраст.

S₀ = M1;2.

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

W_i (S_i;0)= обслуживание(S_i) + W_i₊₁

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

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

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

Код решения задачи на Python:

class NaiveKnapsackSolver:

def __init__(self, mark, years, total):

self.q1 = years

self.q2 = mark

self.p = total
def W(self, stage):

if stage > self.p:

return 0, None
best_w = None

best_u = None

for u in [0, 2]:

if u == 0:

self.q1 += 1

wi = -1 * (self.q2 - 2) * m1[self.q1] + (self.q2 - 1) * m1[self.q1] + self.W(stage + 1)[0]

print(wi, self.q1, self.q2)

elif u == 1:

oldq1 = self.q1

oldq2 = self.q2

self.q1 = 0

self.q2 = 1

wi = m1[0] + zamena[0] - ostatok[oldq1][oldq2 - 1] + 500*(oldq2-1) + self.W(stage + 1)[0]

elif u == 2:

oldq1 = self.q1

oldq2 = self.q2

self.q1 = 0

self.q2 = 2

wi = m2[0] + zamena[1] - ostatok[oldq1][oldq2 - 1] - 500*(oldq2 - 2) + self.W(stage + 1)[0]

if stage == self.p:

wi -= ostatok[self.q1][self.q2-1]

if best_w is None or wi < best_w:

best_w = wi

best_u = u

return best_w, best_u
def solve(self):

return self.W(0)

ostatok = [[0, 0], [10800, 8550], [9720, 7695], [8748, 5540], [7000, 4432], [5598, 3545],

[4478, 2800], [3583, 2200], [2866, 2200], [2800, 2200], [2800, 2200]]

m1 = [400, 480, 576, 691, 829, 995, 1194, 1433, 1500, 1500, 1500]

m2 = [600, 720, 936, 1216, 1460, 1752, 2100, 2100, 2100, 2100, 2100]

zamena = [13500, 10500]

myself = NaiveKnapsackSolver(1, 1, 5)

solve = myself.solve()

new_solve = solve

print(solve)

zamena_save = zamena[0]

заключение
Кратко подвести итоги, проанализировать соответствие поставленной цели и полученного результата.
список использованных источников

1.Пономарев А.В. Динамическое программирование с помощью GNU Octave за 7 простых шагов // Теория принятия решений – тематический сайт. URL: http://cais.iias.spb.su/ponomarev/DP_Octave.pdf (дата обращения: 15.02.2018).

2.ГОСТ 7.32–2001. Межгосударственный стандарт. Отчет о научно-исследовательской работе. Структура и правила оформления. М.: Изд-во стандартов, 2001.
Ниже представлены примеры библиографического описания, В качестве названия источника в примерах приводится вариант, в котором применяется то или иное библиографическое описание.

3.Иванов И. И. Книга одного-трех авторов. М.: Издательство, 2010. 000 с.

4.Книга четырех авторов / И. И. Иванов, П. П. Петров, С. С. Сидоров, В. В. Васильев. СПб.: Издательство, 2010. 000 с.

5.Книга пяти и более авторов / И. И. Иванов, П. П. Петров, С. С. Сидоров и др.. СПб.: Издательство, 2010. 000 с.

6.Описание книги под редакцией / под ред. И.И. Иванова СПб., Издательство, 2010. 000 с.

7.Иванов И.И. Описание учебного пособия и текста лекций: учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2010. 000 с.

8.Описание методических указаний / сост.: И.И. Иванов, П.П. Петров. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2010. 000 с.

9.Иванов И.И. Описание статьи с одним-тремя авторами из журнала // Название журнала. 2010, вып. (№) 00. С. 000–000.

10.Описание статьи с четырьмя и более авторами из журнала / И. И. Иванов, П. П. Петров, С. С. Сидоров и др. // Название журнала. 2010, вып. (№) 00. С. 000–000.

11.Иванов И.И. Описание тезисов доклада с одним-тремя авторами / Название конференции: тез. докл. III международной науч.-техн. конф., СПб, 00–00 янв. 2000 г. / СПбГЭТУ «ЛЭТИ», СПБ, 2010, С. 000–000.

12.Описание тезисов доклада с четырьмя и более авторами / И. И. Иванов, П. П. Петров, С. С. Сидоров и др. // Название конференции: тез. докл. III международной науч.-техн. конф., СПб, 00–00 янв. 2000 г. / СПбГЭТУ «ЛЭТИ», СПБ, 2010, С. 000–000.

13.Описание электронного ресурса // Наименование сайта. URL: http://east-front.narod.ru/memo/latchford.htm (дата обращения: 00.00.2010).

14.ГОСТ 0.0–00. Описание стандартов. М.: Изд-во стандартов, 2010.

15.Пат. RU 00000000. Описание патентных документов / И. И. Иванов, П. П. Петров, С. С. Сидоров. Опубл. 00.00.2010. Бюл. № 00.

16.Иванов И.И. Описание авторефератов диссертаций: автореф. дисс. канд. техн. наук / СПбГЭТУ «ЛЭТИ», СПБ, 2010.

17.Описание федерального закона: Федер. закон [принят Гос. Думой 00.00.2010] // Собрание законодательств РФ. 2010. № 00. Ст. 00. С. 000–000.

18.Описание федерального постановления: постановление Правительства Рос. Федерации от 00.00.2010 № 00000 // Опубликовавшее издание. 2010. № 0. С. 000–000.

19.Описание указа: указ Президента РФ от 00.00.2010 № 00 // Опубликовавшее издание. 2010. № 0. С. 000–000.

приложение А

Название приложения