Исследование операций. Lab4. Сети

Задание:

Пример 6.2.1. (Замена оборудования) Фирма по прокату автомобилей планирует замену автомобильного парка на очередные пять лет. Автомобиль должен проработать не менее одного года, прежде чем фирма поставит вопрос о его замене. В таблице 6.1 приведены стоимости замены автомобилей (в тысячах долларов), зависящие от времени замены и числа лет в течение которых автомобиль находится в эксплуатации.

Эту задачу можно представить на сети в следующем виде. Каждому году ставится в соответствие определенный узел. «Длина» дуги, соединяющей два узла, равна соответствующей стоимости замены из табл.6.1.

таблица 6.1

	1	2	3	4	5
1		4,0	5,4	9,8	13,7
2			4,3	6,2	8,1
год 3				4,8	7,1
4					4,9

Сеть изображена на рис. 6.4. Задача сводится к нахождению кратчайшего «пути» между узлами 1 и 5.

Оптимальное решение дает путь 1 2 5 со стоимостью 4+8.1=12.1 тыс. долл. Это означает, что каждый автомобиль заменяется через два года, а через пять — списывается.

6.5. Перестройте модель замены оборудования, исходя из того, что автомобиль до замены должен прослужит не менее двух лет.

Решение:

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

Для решения этой сетевой задачи была составлена программа на MATLAB, которая находит кратчайший «путь» алгоритмом Дейкстры.

Файл с данными «Data.m»:

%Fail s dannimi dlya laboratornoy raboti #4 po
%issledovaniyu operaciy

%Eto primer iz TAHA
% A=[
%     1   1   2   3   3   4   4   
%     2   3   3   4   5   2   5
%     100 30  20  10  60  15  50
% ];
% MaxN=5;
% s=1
% e=2;


%Eto primer 6.2.1 iz zadaniy na issledovaniye operaciy
% A=[
%     1       1       1       1       2       2       2       3       3       4   
%     2       3       4       5       3       4       5       4       5       5
%     4       5.4     9.8     13.7    4.3     6.2     7.1     4.8     8.1     4.9
% ];
% MaxN=5;
% s=1;
% e=5;

%Eto moyalaboratornaya rabota zadacha 6.5
A=[
    1       1       1       2       2       3  
    3       4       5       4       5       5
    5.4     9.8     13.7    6.2     7.1     8.1
];
MaxN=5;
s=1;
e=5;

%Fail s dannimi dlya laboratornoy raboti #4 po

%issledovaniyu operaciy

%Eto primer iz TAHA

% A=[

% 1 1 2 3 3 4 4

% 2 3 3 4 5 2 5

% 100 30 20 10 60 15 50

% ];

% MaxN=5;

% s=1

% e=2;

%Eto primer 6.2.1 iz zadaniy na issledovaniye operaciy

% A=[

% 1 1 1 1 2 2 2 3 3 4

% 2 3 4 5 3 4 5 4 5 5

% 4 5.4 9.8 13.7 4.3 6.2 7.1 4.8 8.1 4.9

% ];

% MaxN=5;

% s=1;

% e=5;

%Eto moyalaboratornaya rabota zadacha 6.5

A=[

1 1 1 2 2 3

3 4 5 4 5 5

5.4 9.8 13.7 6.2 7.1 8.1

];

MaxN=5;

s=1;

e=5;

Главный файл «lab4.m»:

%Glavniy fail laboratornoy raboti #4
Data
Result=MinimumWay(MaxN,A,s,e);
s
e
MWWriteDecision(Result,s,e);

%Glavniy fail laboratornoy raboti #4

Data

Result=MinimumWay(MaxN,A,s,e);

MWWriteDecision(Result,s,e);

Программа, реализующая алгоритм Дейкстры «MinimumWay»:

function u=MinimumWay(MaxN,A,s,e)
%Obyavleniye:
%   function u=MinimumWay(A)
%Vhodniye parametri:
%MaxN - kolichestvo uzlov v graphe.
%A-massiv reber grapha.
%s - nachalniy uzel
%e - konechniy uzel
%
%Primer vhodnih parametrov:
%Mnoshestvo vershin: {1,2,3,4,5}
%Mnoshestvo reber: {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5))}
% S cenami:           21    32  34      34    34    45    34    34
%V etom sluchae chislo MaxN dolshno ravnyatsya 5;
%V etom sluchae vhodnoy massiv A dolshen bit takim:
%A=[1   1   2   2   3   3   4   4
%   2   3   3   5   4   5   2   5
%  21   32  34  34  34  45  34  34]
%   ^   ^   ^
%   |   |   |
%(1,2)(1,3)(1,4)...
%
%Funkciya vozvrashaet  spisok metok, poluchennih algoritmom Deykstri
%u(:,1) - pervaya metka
%u(:,2) - vtoraya metka
%...
%Ispolzuyte funkciyu MWWriteDecision dlya togo, chtobi vivesti reshe-
%niye na ekran.
%
%
%Posetite http://www.urvanov.ru



%Vichislim razmer massiva A
[n,SizeA]=size(A);
%Vashna tolko peremennaya SizeA. kolichestvo strok n vseg-
%da ravno 3.

%Massiv u.
for n=1:MaxN u(1,n)=NaN; u(2,n)=NaN; end;
Post=zeros(MaxN,1);

%ETAP 0.
%Ishodnomu uzlu prisvaivaetsya postoyannaya metka [0,-]
CONST=2;
TEMP=1;
u(1,s)=0;

Post(s)=CONST;
LastPost=s;

%polagaem i=1;
i=1;

yes=1;
while yes
%ETAP 1.
%a)Vichislyaem vremenniye metki [ui+dij,i] dlya vseh uzlov j,
%kotoriye moshno dostich neposredstvenno iz uzla i i kotorie
%ne imeyut postoyannih metok.
for n=1:SizeA
    if (  (A(1,n)==LastPost)&&(Post(A(2,n))~=CONST)  )
        Newu=u(1,LastPost)+A(3,n);
        
        %Esli uzel A(2,n) ushe imeet metku, poluchennuyu ot
        %drugogo uzla, i, esli Novaya metka menshe staroy,to
        %to zamenim staruyu metku na novuyu.
        if not (u(1,A(2,n))<=Newu)
            u(1,A(2,n))=Newu;
            u(2,A(2,n))=LastPost;
            Post(A(2,n))=TEMP;
        end;
    end;
end;

%b)Esli vse uzli imeyut postoyanniye metki, to process vichi-
%sleniy zakanchivaetsya. V protivnom sluchae vibiraetsya metka
%[umax,s] s naimenshim znacheniyem rasstoyaniya u sredi xseh vre-
%mennih metok (esli takih metok neskolko, to vibor proizvolniy).
%Polagaem i=r i povtoryaem etap i.
max=1;
for n=1:MaxN
    if (  (Post(n)==TEMP)&& ((u(1,n)<u(1,max))||(max==1)) )
        max=n;       
    end;
end;

if (max~=1)
    %Polagaem i=max;
    Post(max)=CONST;
    i=max;
    LastPost=max;
else
    %Esli vse uxli s postoyannimi koefficientami, to zavershaem
    %cikl.
    yes=0;
end;

end;
u;

% Post

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

function u=MinimumWay(MaxN,A,s,e)

%Obyavleniye:

% function u=MinimumWay(A)

%Vhodniye parametri:

%MaxN - kolichestvo uzlov v graphe.

%A-massiv reber grapha.

%s - nachalniy uzel

%e - konechniy uzel

%Primer vhodnih parametrov:

%Mnoshestvo vershin: {1,2,3,4,5}

%Mnoshestvo reber: {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5))}

% S cenami: 21 32 34 34 34 45 34 34

%V etom sluchae chislo MaxN dolshno ravnyatsya 5;

%V etom sluchae vhodnoy massiv A dolshen bit takim:

%A=[1 1 2 2 3 3 4 4

% 2 3 3 5 4 5 2 5

% 21 32 34 34 34 45 34 34]

% ^ ^ ^

% | | |

%(1,2)(1,3)(1,4)...

%Funkciya vozvrashaet spisok metok, poluchennih algoritmom Deykstri

%u(:,1) - pervaya metka

%u(:,2) - vtoraya metka

%...

%Ispolzuyte funkciyu MWWriteDecision dlya togo, chtobi vivesti reshe-

%niye na ekran.

%Posetite http://www.urvanov.ru

%Vichislim razmer massiva A

[n,SizeA]=size(A);

%Vashna tolko peremennaya SizeA. kolichestvo strok n vseg-

%da ravno 3.

%Massiv u.

for n=1:MaxN u(1,n)=NaN; u(2,n)=NaN; end;

Post=zeros(MaxN,1);

%ETAP 0.

%Ishodnomu uzlu prisvaivaetsya postoyannaya metka [0,-]

CONST=2;

TEMP=1;

u(1,s)=0;

Post(s)=CONST;

LastPost=s;

%polagaem i=1;

i=1;

yes=1;

while yes

%ETAP 1.

%a)Vichislyaem vremenniye metki [ui+dij,i] dlya vseh uzlov j,

%kotoriye moshno dostich neposredstvenno iz uzla i i kotorie

%ne imeyut postoyannih metok.

for n=1:SizeA

if ( (A(1,n)==LastPost)&&(Post(A(2,n))~=CONST) )

Newu=u(1,LastPost)+A(3,n);

%Esli uzel A(2,n) ushe imeet metku, poluchennuyu ot

%drugogo uzla, i, esli Novaya metka menshe staroy,to

%to zamenim staruyu metku na novuyu.

if not (u(1,A(2,n))<=Newu)

u(1,A(2,n))=Newu;

u(2,A(2,n))=LastPost;

Post(A(2,n))=TEMP;

end;

%b)Esli vse uzli imeyut postoyanniye metki, to process vichi-

%sleniy zakanchivaetsya. V protivnom sluchae vibiraetsya metka

%[umax,s] s naimenshim znacheniyem rasstoyaniya u sredi xseh vre-

%mennih metok (esli takih metok neskolko, to vibor proizvolniy).

%Polagaem i=r i povtoryaem etap i.

max=1;

for n=1:MaxN

if ( (Post(n)==TEMP)&& ((u(1,n)<u(1,max))||(max==1)) )

max=n;

end;

if (max~=1)

%Polagaem i=max;

Post(max)=CONST;

i=max;

LastPost=max;

else

%Esli vse uxli s postoyannimi koefficientami, to zavershaem

%cikl.

yes=0;

end;

% Post

Программа вывода на экран «MWWriteDecision.m»:

function MWWriteDecision(u,s,e)
%Obyavleniye:
%function MWWriteDecision(u,s,e)
%
%vhodniye parametri:
%u - ispolzuyte funkciyu MinimumWay, chtobi poluchit etot parametr
%s - nachalniy uzel dlya vivoda minimalnogo puti.
%Parametr s dolshen bit raven parametru s, ispolzovannomu dklya 
%polucheniya parametra u.
%
%e - konechniy uzel dlya vivoda minimalnogo puti.
%Funkciya vivodit minimalniy put meshdu uzlami s i e.
uzels(1)=e; n=1;
while (uzels(n)~=s)
 
     n=n+1;
    uzels(n)=u(2,uzels(n-1));
   
end;

uzels
 m=n;
 while m>=1
     
   sprintf('%i-viy uzel - %i',n-m+1,uzels(m))
   m=m-1;
end;
   
 sprintf('Stoimost: %i',u(1,uzels(1)))

function MWWriteDecision(u,s,e)

%Obyavleniye:

%function MWWriteDecision(u,s,e)

%vhodniye parametri:

%u - ispolzuyte funkciyu MinimumWay, chtobi poluchit etot parametr

%s - nachalniy uzel dlya vivoda minimalnogo puti.

%Parametr s dolshen bit raven parametru s, ispolzovannomu dklya

%polucheniya parametra u.

%e - konechniy uzel dlya vivoda minimalnogo puti.

%Funkciya vivodit minimalniy put meshdu uzlami s i e.

uzels(1)=e; n=1;

while (uzels(n)~=s)

n=n+1;

uzels(n)=u(2,uzels(n-1));

end;

uzels

m=n;

while m>=1

sprintf('%i-viy uzel - %i',n-m+1,uzels(m))

m=m-1;

end;

sprintf('Stoimost: %i',u(1,uzels(1)))

В результате работы программы получим:

1-viy uzel — 1

2-viy uzel — 3

3-viy uzel — 5

Stoimost — 1.350000e+001

Это значит, что в третьем году надо заменить автомобили, купленные в первом и в пятом году автомобили, купленные в третьем.

Вывод :

Мы изучили алгоритм Дейкстры, с помощью которого можно найти минимальный «путь».

Скачать ZIP-архив с исходными кодами

Ноябрь 2015
Пн	Вт	Ср	Чт	Пт	Сб	Вс
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

Добавить комментарий Отменить ответ