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

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

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

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

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

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

2022

1

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 – Транспортные расходы

Рассматривается работа системы в течение двух периодов при условии доставки на станцию по 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 ДЕ при опорном плане следующего вида:

По таблице видно, что выгодно распределить поступающий груз следующим образом: на первый склад – 60 тонн, на второй – 60 тонн и на третий – 40 тонн.

Так как в данной задаче присутствуют ограничения-равенства, нас будут интересовать теневые цены в solution['y'].

10