Заболотников_9373_ПР1
.pdfМИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра Информационных систем
ПРАКТИЧЕСКАЯ РАБОТА по дисциплине «Теория принятия решений»
Тема: "Применение методов линейного и динамического программирования для решения практических задач"
Вариант №42 (394)
Студент гр. 9373 |
|
Заболотников М.Е. |
|
Преподаватель |
|
Пономарев А. В. |
|
|
|||
|
|
|
|
Санкт-Петербург
2022
1
|
СОДЕРЖАНИЕ |
|
|
Ведение…………………………………………………………..... |
3 |
1. |
Задача о магистрали……………………………………………… |
4 |
1.1.Условие задачи…………………………………………………… 4
1.2.Формализация задачи…………………………………………….. 5
1.3.Решение задачи…………………………………………………… 7
Заключение………………………………………………………... 11
Приложение А…………………………………………………….. 12
2
ВВЕДЕНИЕ
Цель работы: определить план перевозок, обеспечивающий минимум стоимости доставки грузов для двух периодов. Провести анализ чувствительности плана к изменению цен перевозок из первого промежуточного склада.
3
1.ЗАДАЧА О МАГИСТРАЛИ
1.1.Условие задачи
На строительство магистрали периодически доставляются материалы,
которые со станции железной дороги вначале поступают на 3 промежуточных склада, а затем непосредственно к 5 объектам магистрали. Два первых склада А1, А2 имеют ограниченную емкость 60 т, и поступившие на них грузы расходуются полностью. Склад А3 с неограниченной емкостью допускает резервирование грузов от периода к периоду. Транспортные расходы (в
условных денежных единицах — ДЕ) на перевозку одной тонны груза со станции на промежуточные склады составляют 3, 4, 7 ДЕ, а со складов к объектам В1–В5 представлены в табл. 1; там же приведены потребности объектов (в тоннах) в течение двух периодов.
Таблица 1 – Транспортные расходы
|
В1 |
В2 |
В3 |
В4 |
В5 |
|
|
|
|
|
|
А1 |
4 |
8 |
2 |
6 |
6 |
|
|
|
|
|
|
А2 |
4 |
3 |
11 |
12 |
7 |
|
|
|
|
|
|
А3 |
10 |
4 |
12 |
14 |
8 |
|
|
|
|
|
|
1-й период |
6 |
26 |
60 |
10 |
23 |
|
|
|
|
|
|
2-й период |
21 |
45 |
26 |
13 |
42 |
|
|
|
|
|
|
Рассматривается работа системы в течение двух периодов при условии доставки на станцию по 160 т груза в каждый из периодов.
Требуется определить план перевозок, обеспечивающий минимум стоимости доставки грузов для двух периодов. Провести анализ чувствительности плана к изменению цен перевозок из первого промежуточного склада.
4
1.2.Формализация задачи
Данная задача является задачей линейного программирования.
Пусть:
a) 1, 2 и 3 – объёмы складов А1, А2 и А3 за все периоды;
b) ( ) – объём поставки на -й промежуточный склад в -й период ( = 1. .3, = 1, 2);
c) ( ) – перевоз с -го склада в -й склад за -й период ( = 1. .3, =
1. .5, = 1, 2).
Тогда целевая функция для первого периода:
1 = 3 1 + 4 2 + 7 3 + 4 11(1) + 8 12(1) + 2 13(1) + 6 14(1) + 6 15(1) + 4 21(1) + 3 22(1)
+11 23(1) + 12 24(1) + 7 25(1) + 10 31(1) + 4 32(1) + 12 33(1) + 14 34(1)
+8 35(1)
Ацелевая функция для второго периода:
2 = 3 1 + 4 2 + 7 3 + 4 11(2) + 8 12(2) + 2 13(2) + 6 14(2) + 6 15(2) + 4 21(2) + 3 22(2)
+11 23(2) + 12 24(2) + 7 25(2) + 10 31(2) + 4 32(2) + 12 33(2) + 14 34(2)
+8 35(2)
Рассмотрим теперь ограничения для первого периода: a) Ограничения на целесообразность задачи:
(1) ≥ 0 для всех и ;
b)Ограничения на поставку:
1(1) + 2(1) + 3(1) = 160;
c)Ограничения на потребление:
4 11(1) + 4 21(1) + 10 31(1) = 6 8 12(1) + 3 22(1) + 4 32(1) = 26
2 13(1) + 11 23(1) + 12 33(1) = 60 6 14(1) + 12 24(1) + 14 34(1) = 10
6 15(1) + 7 25(1) + 8 35(1) = 23;
5
d)Ограничения на остаток:
1(1) = 11(1) + 12(1) + 13(1) + 14(1) + 15(1)2(1) = 21(1) + 22(1) + 23(1) + 24(1) + 25(1)3(1) ≥ 31(1) + 32(1) + 33(1) + 34(1) + 35(1);
e)Ограничения на объём складов:
1(1) ≤ 602(1) ≤ 60.
Далее рассмотрим ограничения для второго периода a) Ограничения на целесообразность задачи:
(2) ≥ 0 для всех и ;
b)Ограничения на поставку:
1(2) + 2(2) + 3(2) = 160;
c)Ограничения на потребление:
411(2) + 421(2) + 1031(2) = 21
812(2) + 322(2) + 432(2) = 45
213(2) + 1123(2) + 1233(2) = 26 614(2) + 1224(2) + 1434(2) = 13
615(2) + 725(2) + 835(2) = 42;
d)Ограничения на остаток:
1(2) = 11(2) + 12(2) + 13(2) + 14(2) + 15(2)2(2) = 21(2) + 22(2) + 23(2) + 24(2) + 25(2)3(2) ≥ 31(2) + 32(2) + 33(2) + 34(2) + 35(2);
e)Ограничения на объём складов:
1(2) ≤ 602(2) ≤ 60.
6
1.3.Решение задачи
Данную задачу имеет смысл решать следующим образом. Сначала найдём оптимальное решение и проведём анализ чувствительности для первого и второго периодов. А затем сложим полученные решения для обоих периодов и получим решение задачи.
Работаем с первым периодом.
Запишем целевую функцию:
c = matrix([3,4,7,4,8,2,6,6,4,3,11,12,7,10,4,12,14,8], 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],
7
[0,-1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0]], tc = 'd')
Правую часть неравенств занесём в матрицу h:
h = matrix([60,60,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], tc = 'd')
Для равенств – следующие действия:
m = matrix([160,6,26,60,10,23,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'])
Программа выдаёт следующие результаты:
Рисунок 1 – Результат работы программы для первого периода Проделаем все те же действия для второго периода. Получим такие
результаты:
8
Рисунок 2 – Результаты работы программы для второго периода
По результатам работы программы видно, что оптимальным решением задачи является значение 1268 + 1349 = 2617 ДЕ при опорном плане следующего вида:
Коэффициенты |
Значения |
|
Коэффициенты |
Значения |
|
1-го периода |
|
2-го периода |
|||
|
|
|
|||
|
(1) |
60 |
|
1(2) |
60 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
(1) |
60 |
|
2(2) |
60 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
(1) |
40 |
|
3(2) |
40 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
|
11(2) |
0 |
11 |
|
|
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
|
12(2) |
0 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
(1) |
60 |
|
13(2) |
26 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
(1) |
0 |
14(2) |
13 |
14 |
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
15(2) |
21 |
15 |
|
|
|
|
|
|
|
|
|
|
(1) |
6 |
21(2) |
21 |
21 |
|
|
|
|
|
|
|
|
|
|
(1) |
26 |
22(2) |
39 |
22 |
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
23(2) |
0 |
23 |
|
|
|
|
|
|
|
|
|
|
(1) |
10 |
24(2) |
0 |
24 |
|
|
|
|
|
|
|
|
|
|
(1) |
18 |
25(2) |
0 |
25 |
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
31(2) |
0 |
31 |
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
32(2) |
6 |
32 |
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
33(2) |
0 |
33 |
|
|
|
|
|
|
|
|
|
|
(1) |
0 |
34(2) |
0 |
34 |
|
|
|
|
|
|
|
|
|
|
(1) |
5 |
35(2) |
21 |
35 |
|
|
|
|
|
|
|
|
|
По таблице видно, что выгодно распределить поступающий груз следующим образом: на первый склад – 60 тонн, на второй – 60 тонн и на третий – 40 тонн.
Так как в данной задаче присутствуют ограничения-равенства, нас будут интересовать теневые цены в solution['y'].
10