Bölüm 3 EMKBA

Transkript

Bölüm 3 EMKBA

İrfan MACİT
Bölüm 3 Bilgisayar Programlama Algoritmaları
Bölüm 3 Endüstri
Mühendisliğinde Kullanılan
Bilgisayar Algoritmaları
1.Giriş
Bilgisayar algoritmaları endüstri mühendisliğinin uygulama alanının genişliğinden dolayı
çok fazla kullanılmaktadır. En kısa yol (shortest path), en fazla akış (maximum flow), en az
dallanma (minimum span) gibi endüstri mühendisliğinde kullanılan algoritmalar el ile
sonuçlandırılması düğüm sayısı arttıkça çözüm süresi de uzamaktadır. Bilgisayar yardımı ile
benzer
bir
çok
algoritma
geliştirilen
bilgisayar
programları
ile
çok
kısa
sürede
tamamlanabilmektedir. Bilgisayar programlama dillerinin çeşitliliği de bu algoritmaların
yazılmasını ve uygulanmasını daha da kolaylaştırmıştır.
Bilgisayar programlama dillerindeki gelişme ile birlikte bir çok problem bu programlama
dillerinde modellenerek ve çözüm algoritmaları geliştirilerek oluşturulmaktadır. Bir algoritma
belirli kurallar ile bir problemi incelenmesi ve sonucunun bulunması işlemini, girdi ve çıktı
işlemlerinin hesap yöntemlerinin adımlarını veya genelleştirilen bir veri yapısının işlemsel sıralar
ile yapılması şekline kabaca tarif edilebilir. Uygulanacak olan algoritmalar kolay ve güvenilir
olmalıdır.
Endüstri mühendisliğinde diğer mühendislik bilimlerinde olduğu gibi bir çok problem için
kullanılan veya yeni geliştirilen algoritmalar vardır. Kullanılan algoritmalar daha önceden bilinen
problemlerin çözüm yöntemleri ile oluşturulan algoritmalardır. Geliştirilen algoritmalar ise var
olan problemleri yeni teknolojiler ile çözmeye çalışan algoritmalardır. Her problemin kendine ait
32
İrfan MACİT
çözüm yöntemleri olduğu gibi genel çözümleri de bulunabilmektedir. Genel çözümlerde
mühendislik biliminin ortak problemlerinin çözümünde daha çok karşılaşılır. Genel çözümlerin
uygulandığı grafik yöntemleri yanında matematiksel olarak semboller ile ifade edilen çözüm
yöntemleri vardır. Bilgisayar bilimlerindeki gelişmeler bazı türdeki problemlerin çözümünü
oldukça basitleştirmiş bazıların çözümünü de oldukça kolaylaştırmıştır. En kısa yol (Shortest
Path - SP) algoritmasının düğüm sayılarının arttıkça çözüm uzayının da çok genişlediği
bilinmektedir. El ile çözümlerde çözüm süresinin uzaması düğüm sayısının artması ile daha da
artmaktadır. Gezgin satıcı probleminin (Travel Salesman Problem- TSP) klasik çözümü el ile
yapıldığında düğüm sayısının bir tane daha artması problemin çözüm uzayını tamamen
değiştirebilmekte ve çözüm için geçen süre oldukça artmaktadır. Bunun gibi daha bir çok örnek
verilebilecek problem vardır. Bu tip problemlerin çözümünü bilgisayar yardımı ile nasıl
yapılabileceğini ve algoritmaların bilgisayar programlarında nasıl uygulanacağını anlatılacaktır.
3.2. Sırt Çantası Problemi
Sırt çantası problemi ( Knapsack Problem- SÇP) tam sayılı programlamada en çok uğraşılan
problemlerden birisidir. 1950 yılından beri bu türde problemlerin artması sonucu bilgisayar
teknolojisin ile çözüm aranan ve çözüm sürelerinin iyileştirmeye çalışılan problemdir. Bilgisayar
kullanımı ile birlikte karşılaşılan problemlerin bir çoğu çözüme ulaşmıştır. Bu tip problemleri
incelersek en önemlisinin çözüm sürelerinde görülen uzamalardır. SÇP bilindiği gibi karar
değişkeni kesikli olmasından dolayı çözüm kümesi dış bükey olamamaktadır. Bu da çözüm
süresini kısıtlar arttıkça logaritmik artmasına sebep olmaktadır. Genel olarak matematiksel
gösterimi aşağıdaki gibidir. Modelde n adet parça olma üzere, wi her parçanın ağırlığını, Pi kar
edilecek miktarı ve C çantanın kapasitesini göstermektedir.
Çantaya toplam C kapasitesini geçmeden en fazla karı yakalayacak olan parça miktarını
seçmek istenmektedir. Bu problemi Turbo Pascal bilgisayar programlama dili ile programlamak
istediğimizde aşağıda yazan kodlar ile programlayabiliriz. Bu programda
veri dosyası
oluşturulması gerekiyor. Veri dosyasında parça sayısı, her parçanın kar miktarı, her parçanın
ağırlığı ve toplam kapasite sınırı verilmelidir. Veri dosyasında ilk sıra parça sayısı, ikinci sıra sırt
33
İrfan MACİT
çantasının toplam kapasitesini son sıra ise parçaların ağırlığını göstermektedir. Bu problemin
algoritmasını ise şu şekilde oluşturabiliriz.
Adım 1) max SUM (Pi*Xi) i= 1 to N
Adım 2)
s.t. SUM (Wi*Xi) <= V for i = 1 to N
Xi = 0 or 1
for i = 1 to N
Pi = i değişkenin toplam karı
Wi = i değişkenin ağırlığı
V = en fazla sırt çanta ağırlığı
Adım 3) Değişken değerlerini
P1/W1 >= P2/W2 >= P3/W3 ...>= Pn/Wn
Olacak şekilde düzenle
Max parça sayısını maxobject = 50 olacak şekilde ayarla.
OUTPUT (Çıktı) : Çıktıların dosyadaki durumu
1. Toplam kar ne kadar
2. Hangi parçadan ne kadar alınacağının belirlenmesidir.
program
KnapApproximation(input,output,KnapAppxDatafile,KnapAppxOutfile);
const
INF
=
1000;
maxobject =
50;
CONSTANT
0.33333;
=
34
İrfan MACİT
type
CHARFILE
ARRN
var
=
=
array[1..maxobject] of integer;
KnapAppxDatafile
KnapAppxOutfile
:
:
CHARFILE;
CHARFILE;
N,
Nextint
:
integer;
P,
W
:
ARRN;
X
V,
file of char;
PROFIT
:
ARRN;
:
integer;
EPS
procedure Infile (var Nextint
var N
var P,
W
var V
:
real;
:
integer;
:
integer;
:
ARRN;
:
integer);
var counter : integer;
begin
reset(KnapAppxDatafile);
readln(KnapAppxDatafile, Nextint);
N := Nextint;
readln(KnapAppxDatafile, Nextint);
V := Nextint;
for counter := 1 to N do
begin
read(KnapAppxDatafile, Nextint);
P[counter] := Nextint;
end;
readln(KnapAppxDatafile);
begin
read(KnapAppxDatafile, Nextint);
W[counter] := Nextint;
35
İrfan MACİT
end;
readln(KnapAppxDatafile);
end;
procedure KNAPAPPROX(
N
:integer;
var P,W,X
:ARRN;
var V,PROFIT:integer;
var EPS
:real);
var I,J,K,L,MAXP1,MAXP2,MAXP3,PP,Q,R,S,U,VV:integer;
procedure LB(G,H:integer;var Q,U:integer);
(* LB FINDS PROFIT Q and RESIDUAL WEIGHT OF GREEDY TYPE
SOLUTION WHICH IS ASSUMED to CONTAIN OBJECTS G and H *)
var K:integer;
begin
K:=0;
repeat
K:=K+1;
if (K <> G) and (K <> H) and (W[K] <= U) then begin
Q:=Q+P[K];
U:=U-W[K]
end
until K=N
end;
(* LOWER BOUND *)
procedure MAX;
(* MAX UPDATES MAXP1, MAXP2, and MAXP3: LARGEST, SECOND
and THIRD LARGEST ELEMENTS OF THE PROFIT VECtoR *)
begin
if P[I] > MAXP1 then begin
MAXP3:=MAXP2;
MAXP2:=MAXP1;
MAXP1:=P[I]
end
else
if P[I] > MAXP2 then begin MAXP3:=MAXP2;
else if P[I] > MAXP3 then MAXP3:=P[I]
36
MAXP2:=P[I] end
İrfan MACİT
end;
(* MAX *)
begin
(* MAIN BODY *)
I:=1;
U:=V;
MAXP1:=0;
PROFIT:=0;
MAXP2:=0;
MAXP3:=0;
while W[I] <= U do begin
U:=U-W[I];
MAX;
(* FINDING GREEDY SOLUTION *)
X[I]:=1;
PROFIT:=PROFIT+P[I];
I:=I+1
end;
I:=I-1;
S:=I;
repeat
I:=I+1;
if W[I] <= U then begin
U:=U-W[I];
X[I]:=1;
PROFIT:=PROFIT+P[I]
end
else X[I]:=0;
MAX
until I=N;
Q:=PROFIT;
(* ONE ELEMENT SUBSETS OF OBJECT *)
K:=0;
L:=0;
(* K and L IDENTifY THE OBJECTS WHICH *)
for I:=S to N do
(* ARE ASSUMED to BE IN A SOLUTION *)
if X[I] <> 1 then begin
VV:=V-W[I];
PP:=P[I];
LB(I,I,PP,VV);
if PP > PROFIT then begin PROFIT:=PP;
end;
K:=I end
(*if X[I] <> 1, for I *)
R:=S;
(* TWO ELEMENT SUBSETS OF OBJECTS *)
for I:=1 to N-1 do begin
if I > S then R:=I;
for J:=R+1 to N do begin
VV:=V-W[I]-W[J];
if VV >= 0 then begin
PP:=P[I]+P[J];
LB(I,J,PP,VV);
if PP > PROFIT then begin PROFIT:=PP;
end
37
K:=I;
L:=J end
İrfan MACİT
end
end;
(* for J *)
(* for I *)
if PROFIT > Q then begin
if K > 0 then begin V:=V-W[K];
X[K]:=1
end;
if L > 0 then begin V:=V-W[L];
X[L]:=1
end;
for I:=1 to N do
if (I <> K) and (I <> L) then
if W[I] <= V then begin X[I]:=1;
V:=V-W[I] end
else X[I]:=0
end;
(* if PROFIT > Q *)
EPS:=MAXP3/PROFIT;
if EPS > 0.33333 then EPS:=0.33333
end;
(* KNAPAPPROX *)
procedure Outfile(N : integer;
PROFIT
: integer;
X
: ARRN);
begin
rewrite(KnapAppxOutfile);
writeln (KnapAppxOutfile,' PROFIT is
',PROFIT,'
with
');
begin
writeln(KnapAppxOutfile,'
X',counter:2,' = ',X[counter]);
end;
end;
begin (*
main *)
EPS := CONSTANT;
Infile(Nextint,N,P,W,V);
KNAPAPPROX(N,P,W,X,V,PROFIT,EPS);
Outfile(N,PROFIT,X);
end.
38
İrfan MACİT
3.3 Gezgin Satıcı Problemi ( Travel Salesman Problem-TSP)
Gezgin satıcı problemi (GSP) ulaşılacak olan düğümler arası uzaklığın bilindiği ve her
birisinden yalnızca bir kez geçilerek en kısa yolun (maliyetin) bulunduğu tam sayılı programlama
yöntemidir. Gezgin satıcı problemlerini (GSP) Simetrik atama yöntemli, Asimetrik atama
yöntemli ve çoklu güzergahlı olarak sınıflandırabiliriz. Kesikli optimizasyon problemi olan
Gezgin Satıcı Problemi düğümlerin sıralı olarak gidilmesini gerektiren bir problemdir.
Literatürde de en fazla üzerinde durulan Tam Sayılı Algoritmaların başında gelmektedir. Gezgin
satıcı problemi modeli kurulan sistemdeki istenen parçaları veya nesneleri en kısa zamanda, en az
maliyet ve en çok kar ile toplamak, dağıtmak gibi tanımlayabiliriz. Bu tür problemler her sektöre
uygulanabilir olduğundan günümüz araştırma konularının içerisinde yer almaktadır.
Volgenant and van den Hout tarafından Solving TSP with 1-tree Relaxation (TURBO-PASCAL)
EJOR 49/1 (1990) 153-154 sayılı makaleden alınan Gezgin Satıcı Problemi Turbo Pascal
bilgisayar programlama kodlarını gelişrtirmişler.
{$a+,b-,d-,e-,f-,i+,l-,o-,r-,s+,v-}
{$ifdef cpu87} {$n+} {$else} {$n-} {$endif}
{$m 65000,0,655360}
program tsp1;
uses tspalgo,crt,dos;
var
cat,error,tourlength: longint;
tour: vec;
inputstr,outputstr: string[80];
input: text;
procedure printusage;
var r: real;
begin
clrscr;
write('traveling salesman problem
version 1.2');
if sizeof(r)=8 then writeln('(coprocessor required)':40)
else writeln('(no coprocessor required)':40);
writeln('university of amsterdam, institute of actuarial science
'
39
İrfan MACİT
,'& econometrics
(c)1990');
writeln('usage');
writeln('
file input
:
tsp1 category input output {+}
'
,'(e.g. tsp1 1 b:\file.dta prn)');
writeln('
random input :
tsp1 category n s output {+}
'
,'(e.g. tsp1 5 20 0 file.out +)');
writeln;
writeln('there are six input categories:');
writeln('
1
:
xyco-ordinates from file without
upper bound');
writeln('
2
:
cost matrix from file
without
upper bound');
writeln('
3
:
xyco-ordinates from file with upper
4
:
cost matrix from file
bound');
writeln('
with upper
bound');
writeln('
5
:
random xyco-ordinates');
writeln('
6
:
random cost matrix');
writeln('the other parameters are:');
writeln('
input
:
input filename with path');
writeln('
output
:
output filename with path
'
,'(''con''=screen,''prn''=printer)');
writeln('
n
writeln('
:
s
number of cities');
:
seed
(initializes
random
generator)');
writeln('
+
:
option
for
more
information');
writeln('the input file must be conform some rules:');
writeln('
first line
:
size (<=',maxn
,') and sequence number (optional)');
writeln('
from second
:
xyco-ordinates or '
,'strict lower triangular matrix');
writeln('
final line
:
halt
end;
procedure ranxy;
const mac1: longint= 16807;
40
upper bound (optional)');
detailed
İrfan MACİT
mac2: longint= 2147483647;
var i,j: integer;
ran,xi,yi: longint;
x,y: longvec;
begin
ran:=n*n+nr;
for i:=1 to n do
begin
ran:=ran*mac1+trunc(1.0*ran*mac1/mac2);
if ran<0 then ran:=ran+mac2+1;
yi:=round(ran/mac2*1000); y[i]:=yi;
xi:=round(ran/mac2*1000); x[i]:=xi;
for j:=1 to i-1 do
begin
c[j]^[i]:=round(sqrt(sqr(xi-x[j])+sqr(yi-y[j])));
c[i]^[j]:=c[j]^[i]
end;
if screen then begin gotoxy(17,wherey); write(i) end
end
end;
procedure ransym;
const mac1: longint= 16807;
mac2: longint= 2147483647;
var i,j: integer;
hulp,ran: longint;
begin
ran:=n*n+nr;
for i:=2 to n do
begin
for j:=1 to i-1 do
begin
c[i]^[j]:=round((ran/mac2*1000) + 0.5);
c[j]^[i]:=c[i]^[j]
41
İrfan MACİT
end;
end
end;
procedure xycoord;
var i,j: integer;
xi,yi: longint;
x,y: longvec;
begin
for i:=1 to n do
begin
read(input,xi);
if (i=n)and seekeof(input) then
begin
gotoxy(1,wherey);
writeln('run-time error: not enough data on file'); halt
end;
read(input,yi);
x[i]:=xi; y[i]:=yi;
for j:=1 to i-1 do
begin
c[i]^[j]:=round(sqrt(sqr(xi-x[j])+sqr(yi-y[j])));
c[j]^[i]:=c[i]^[j]
end;
end
end;
procedure symtable;
var i,j: integer;
cij: longint;
begin
for i:=2 to n do
begin
for j:=1 to i-1 do
begin
if (i=n)and(j=n-1)and seekeof(input) then
42
İrfan MACİT
begin
gotoxy(1,wherey);
writeln('run-time error: not enough data on file');
halt
end;
read(input,cij);
c[i]^[j]:=cij; c[j]^[i]:=cij
end;
end
end;
procedure initialize;
const charset=[33,35..41,45,48..57,64..90,92,94..123,125..255];
var i,code: integer;
begin
val(paramstr(1),cat,code);
{ inputcategory
}
if not(cat in [1..6]) then
begin writeln; writeln('run-time error: category incorrect');
halt end;
if cat<=4 then
begin outputstr:=paramstr(3); info:=paramstr(4)='+' end
else
begin outputstr:=paramstr(4); info:=paramstr(5)='+' end;
for
i:=1
to
length(outputstr)
do
outputstr[i]:=upcase(outputstr[i]);
if (outputstr<>'') and not(ord(outputstr[1]) in charset) then
begin
writeln;
writeln('run-time
error:
output
file
incorrect'); halt end;
screen:=(outputstr<>'')and(outputstr<>'con');
}
if not screen then clrscr;
assign(output,outputstr); rewrite(output);
if cat<=4 then
begin
inputstr:=paramstr(2);
43
{ line to screen
İrfan MACİT
for
i:=1
to
length(inputstr)
do
inputstr[i]:=upcase(inputstr[i]);
if
(inputstr='')or(inputstr='con')
or
not(ord(inputstr[1])
in charset)
then
begin
writeln;
writeln('run-time
error:
input
file
incorrect'); halt
end;
if
screen
then
begin
gotoxy(1,wherey);
write('loading
data:') end;
assign(input,inputstr); reset(input);
read(input,n);
{ read size }
if n>maxn then
begin
writeln; writeln('run-time error: inputsize too large');
halt
end;
if n>memavail div sizeof(longvec)+3 then
begin
writeln;
writeln('run-time
error:
not
enough
memory'); halt end;
if seekeoln(input) then nr:=0 else readln(input,nr);
{
read
sequence
number }
for i:=1 to n do new(c[i]);
if cat in [1,3] then xycoord else symtable; { read matrix }
if cat in [3,4] then
if seekeof(input) then
begin
writeln; writeln('run-time error: no upper bound on
file'); halt
end
else read(input,inpub);
bound }
close(input);
end
else
begin
44
{ read upper
İrfan MACİT
val(paramstr(2),n,code);
{ read size }
val(paramstr(3),nr,code);
{ read seed }
if n>maxn then
begin
writeln; writeln('run-time error: inputsize too large');
halt
end;
if n>memavail div sizeof(longvec)+3 then
begin
writeln;
writeln('run-time
error:
not
enough
memory'); halt end;
for i:=1 to n do new(c[i]);
if
screen
then
begin
gotoxy(1,wherey);
write('computing
data:') end;
if cat=5 then ranxy else ransym
{ read matrix }
end;
if screen then gotoxy(1,wherey)
end;
function currenttime: string;
var i: integer;
t1,t2,t3,t4: word;
year,month,day,hour,minute: string[4];
begin
gettime(t1,t2,t3,t4); str(t1,hour); str(t2,minute);
if length(hour)=1 then hour:=' '+hour;
if length(minute)=1 then minute:='0'+minute;
getdate(t1,t2,t3,t4);
if (t1=1980)and(t2=1)and(t3=1) then
currenttime:='
'+hour+':'+minute
else
begin
str(t1,year); str(t2,month); str(t3,day);
if length(day)=1 then hour:=' '+hour;
if length(month)=1 then hour:=' '+hour;
currenttime:=day+'-'+month+'-'+year+'
end
end;
45
'+hour+':'+minute
İrfan MACİT
procedure printtitel;
var l1,l2: integer;
r: real;
tekst: string[20];
begin
writeln(output,'
_______________
tsp
version
1.2
',currenttime
,'
_______________');
writeln(output,'|
institute
of
actuarial
science
&
econometrics'
,'
writeln(output,'|
(c)1990
|');
university of amsterdam
'
,'department of operations research
|');
if info then
begin
writeln(output,'|
for more information see manual or'
,'
|');
writeln(output,'|
''nonoptimal edges for the '
,'symmetric
traveling
salesman
problem''
|');
writeln(output,'|
r.jonker
,'operations
and
a.volgenant,
research
32
'
(1984),
837-846
|')
end;
writeln(output,'|','|':77);
if
sizeof(r)=8
then
writeln(output,'|
coprocessor
utilized','|':54)
else writeln(output,'|
coprocessor not utilized','|':50);
if cat<=4 then
writeln(output,'|
input
:
',inputstr,'|':59-
length(inputstr));
str(cat,tekst);
writeln(output,'|
category
:
',cat,'|':59-length(tekst));
size
:
',n,'|':59-length(tekst));
number
:
',nr,'|':59-length(tekst))
str(n,tekst);
writeln(output,'|
str(nr,tekst);
if cat<=4 then
writeln(output,'|
46
İrfan MACİT
else
writeln(output,'|
seed
:
',nr,'|':59-length(tekst));
if cat in [3,4] then
if inpub>=0 then
begin
if abs(inpub-round(inpub))<tol then str(inpub:0:0,tekst)
else str(inpub:0:2,tekst);
l1:=length(tekst);
write(output,'|
bound
:
',tekst);
if info then
begin
str(trunc(inpub+1+tol),tekst); l2:=length(tekst);
writeln(output,'
( appears as ',tekst,' in output
)'
,'|':27-l1-l2)
end
else
writeln(output,'|':59-l1);
end
else
begin
str(-inpub:0:10,tekst);
while
(tekst[length(tekst)]='0')and(tekst[length(tekst)-
1]<>'.') do
delete(tekst,length(tekst),1);
writeln(output,'|
bound
:
',tekst,'':18-
length(tekst),
'( fraction over initial lower bound )
end;
writeln(output,'|______________________________________'
,'______________________________________|');
writeln(output)
end;
procedure printoptimum;
var i,j: integer;
begin
writeln(output); writeln(output);
47
|')
İrfan MACİT
case error of
1: begin
writeln(output,'stack overflow, solution is possibly not
optimal !');
writeln(output,'you could try solving this problem '
,'with upper bound ',ub)
end;
2: begin
writeln(output,'execution has been ended '
,'without reaching optimality !');
writeln(output,'upper bound was too low.')
end;
3: begin
writeln(output,'execution has been ended '
,'without reaching optimality !');
writeln(output,'the number of available edges was too
large.')
end;
4: writeln(output,'size not correctly initialized.');
5: writeln(output,'costmatrix not correctly initialized.')
end;
if error in [0,1,3] then
begin
writeln(output);
if
error=0
then
writeln(output,'optimal
tour
:',tourlength:8)
else
begin
writeln(output,'upper bound
:',1.0*ub:11:2);
writeln(output,'lower bound
:',lb2:11:2);
writeln(output,'maximum error
:'
,100*(ub/trunc(lb2+1-tol)-1):11:3,' %')
end;
writeln(output);
i:=1; j:=1;
repeat
write(output,i:3,'-'); i:=tour[i];
inc(j); if j=20 then begin j:=1; writeln(output) end
48
İrfan MACİT
until i=1;
writeln(output,'
1')
end
end;
begin
if paramcount=0 then printusage;
initialize;
printtitel;
tsp(error,tourlength,tour);
printoptimum;
close(output)
end.
3.4. Düzeltilmiş Simplex Metodu
Simplex Metodu doğrusal programlama (DP) modellerini çözmek için Yöneylem
Araştırmasından en çok kullanılan yöntemlerden birisidir. Amaç fonksiyonu
n
enk Z = ∑ c j xi olan ve kısıtları ise
j =1
∑a
ij
x j ≥ bi
i = 1,2,..., n ve x j ≥ 0 şeklindedir.
Simplex yöntemi hesaplama sürelerinin çok olmasından dolayı bilgisayar kullanımını
zorunlu kılmaktadır. Çoğu zaman çözüm süresini uzun olması veya dönge girilmesi ile çözüm
zorlaşmaktadır. Bu durum ise bilgisayarın işlemci ve hafızasında taşmalara veya geçici hatalara
sebep olmaktadır. Standart simplex yöntemi bilindiği gibi her tabloyu bir önceki tabloya göre
türetir. Düzeltilmiş simplex yönteminde hazırlanan tablodaki matrisin tersi biliniyorsa herhangi
bir tablonun değerlerini temel tablodan elde etme şansı vardır.
FIRST NUMBER in "DualplexDatafile" represents # of
VARIABLES in Linear Program problem(LP).
SECOND NUMBER represents # of CONSTRINTS in LP.
First number in each of rest of rows in
"DualplexDatafile" represents the Right Hand Side(RHS)
49
İrfan MACİT
vector b.
Initially objective value is 0.
THIRD set of numbers represents the cost matrix C of
then object function. Cost matrix strats on second #.
FOURTH set of numbers represents the constraint MATRIX A
Matrix A also starts on the second number.
Algorithm
: The dual simplex method solves the LP problem in the
following form:
minimize(or maximize)
s.t.
z=cTx+c^Tx^
Ax + Ix^ = b
x, x^ >= 0
Maximum # of variables, and maximum # of constraints are
set to maxvar =100 and maxconstraint=50 respectively.
One can modify them according to their needs. But
maxconstraint is <= maxvar.
EPSis small ral number such that if for ant real
number a, |a|< EPS, then a =0.0
Initially, EPS = 0.0001
INF is maximal real number available in the floating
point number system that is used.
Initially, INF = 999.00
OUTPUT
: Outputs are
1.Check if a LP
2.Determine the
corresponding
3.Determine the
is feasible and optimal solution exists.
optimal basic variables and their
values.
optimal value of the objective function.
*)
program Dualplex (input, output, DualplexDatafile,DualplexOutfile);
const
INF
= 999.00;
maxvar = 100;
maxconstraint = 50;
EPS
= 0.0001;
type
CHARFILE
ARRMN
ARRN
ARRMIN
var
DualplexDatafile : CHARFILE;
DualplexOutfile : CHARFILE;
=
=
=
=
file of char;
array[0..maxconstraint,0..maxvar] of real;
array[0..maxvar] of integer;
array[0..maxvar-maxconstraint] of integer;
50
İrfan MACİT
N,M, NMINM
FOPT
A
U
NOFEAS, NOSOL
Nextint
Nextreal
procedure Infile(var
var
var
var
var
:
:
:
:
:
:
:
integer;
integer;
ARRMN;
ARRN;
boolean;
integer;
real;
N,M,NMINM
Nextint
Nextreal
A
:
:
:
:
integer;
integer;
real;
ARRMN);
row,column : integer;
begin
reset(DualplexDatafile);
readln(DualplexDatafile,Nextint);
N := Nextint;
readln(DualplexDatafile,Nextint);
M := Nextint;
NMINM := N-M;
for row := 0 to M do
begin
if row = 0 then
begin
for column := 0 to N do
begin
read(DualplexDatafile,Nextreal);
A[row,column] := Nextreal;
end;
readln(DualplexDatafile);
end
else
begin
for column := 0 to NMINM do
begin
read(DualplexDatafile, Nextreal);
end;
readln(DualplexDatafile);
end;
end;
end;
procedure DSIMPLEX(
M,N,FOPT
:integer;
var A
:ARRMN;
var U
:ARRN;
EPS,INF
:real;
var NOFEAS,NOSOL:boolean);
var I,J,K,K1,K2,K3,K4,L,W:integer;
MIN,XM,XS
:real;
B,StoP
:boolean;
Z,Z1
:ARRMIN;
begin
51
İrfan MACİT
NOFEAS:=false; NOSOL:=false;
K4:=N-M;
A[0,0]:=0.0;
for I:=0 to K4 do begin
XS:=0.0;
for J:=1 to M do XS:=XS+A[J,I]*A[0,K4+J];
A[0,I]:=XS-A[0,I]
end;
for I:=K4+1 to N do
for J:=1 to M do
if I = K4+J then A[J,I]:=1.0
else A[J,I]:=0.0;
I:=0;
while (not NOFEAS) and (I < K4) do begin
I:=I+1; XS:=A[0,I];
NOFEAS:=(abs(XS) > EPS) and (XS*FOPT < 0);
if not NOFEAS then U[M+I]:=I
end;
if not NOFEAS then begin
for I:=1 to M do U[I]:=K4+I;
StoP:=false;
repeat (* until StoP *)
MIN:=0.0; B:=true; I:=0;
repeat (* until StoP or (I >= M) *)
I:=I+1; J:=M; XS:=A[I,0];
if XS < -EPS then begin
StoP:=true;
while (J < N) and StoP do begin
J:=J+1; W:=U[J];
StoP:=A[I,W] >= -EPS
end;
if StoP then NOSOL:=true
else begin
B:=false;
if XS-MIN < -EPS then begin
MIN:=XS; L:=I
end
end (* else: not StoP *)
end (* if XS < -EPS *)
until StoP or (I >= M);
if not StoP then begin
if B then begin NOSOL:=false; StoP:=true end
else begin
MIN:=INF;
for J:=1 to K4 do Z1[J]:=M+J;
for I:=0 to M do
if (I <> 1) and (not B) then begin
K:=0;
for J:=1 to K4 do Z[J]:=Z1[J];
K3:=1;
for J:=M+1 to N do
if J = Z[K3] then begin
K3:=K3+1; W:=U[J]; XS:=A[L,W];
if XS < -EPS then begin
XS:=abs(A[I,W]/XS); XM:=XS-MIN;
if abs(XM) < EPS then begin
K:=K+1; Z1[K]:=J;
52
İrfan MACİT
B:=false
end
else
if XM < 0.0 then begin
MIN:=XS; K1:=J; K2:=W;
Z1[1]:=1; K:=1;
for W:=2 to K4 do Z1[W]:=0;
B:=true
end
end (* if XS < -EPS *)
end (* if J = Z[K3], for J *)
end; (* if I <> 1 and (not B), for I *)
MIN:=1.0/A[L,K2];
U[K1]:=U[L];
if L = 0 then I:=1 else I:=0;
repeat
XS:=A[I,K2]*MIN;
A[I,0]:=A[I,0]-A[L,0]*XS;
for J:=M+1 to N do begin
W:=U[J];
A[I,W]:=A[I,W]-A[L,W]*XS
end;
if I = L-1 then I:=I+2 else I:=I+1
until I > M;
for J:=M+1 to N do begin
W:=U[J];
A[L,W]:=A[L,W]*MIN
end;
A[L,0]:=A[L,0]*MIN;
for I:=0 to M do
if I = 1 then A[I,K2]:=1.0
else A[I,K2]:=0.0;
U[L]:=K2
end (* else: not B *)
end (* if not StoP *)
until StoP
end (* if not NOFEAS *)
end; (* DSIMPLEX *)
procedure Outfile(NOFEAS,NOSOL : boolean;
M
: integer;
A
: ARRMN;
U
: ARRN);
begin
rewrite(DualplexOutfile);
writeln (DualplexOutfile,'
NOFEAS = ',NOFEAS,'
NOSOL = ',NOSOL);
if (NOFEAS = false) and (NOSOL = false) then
begin
writeln (DualplexOutfile,' Optimal Value is ',A[0,0]:9:2);
writeln (DualplexOutfile,'
Basic-Var
Value ');
for counter := 1 to M do
begin
write(DualplexOutfile,U[counter]);
53
İrfan MACİT
writeln(DualplexOutfile,'
end;
end;
end;
',A[counter,0]:9:2);
begin (* main *)
Infile(N,M,NMINM,Nextint,Nextreal,A);
DSIMPLEX(M,N,FOPT,A,U,EPS,INF,NOFEAS,NOSOL);
Outfile(NOFEAS,NOSOL,M,A,U);
end.
3.5. Gözden geçirilmiş Simplex Yöntemi
(*
INPUT
: The associated datafile for PSIMPLEX (Revised
Simplex Method) is called "SimplexDatafile".
FIRST NUMBER in "SimplexDatafile" represents # of
VARIABLES in Linear Program problem(LP).
SECOND NUMBER represents # of CONSTRINTS in LP.
Third set of number is M x N constraint matrix.
FOURTH set of number is 1 x M Right Hand Side(RHS)
matrix.
FIFTH set of number is 1 x N Cost Matrix in the
objective function.
Algorithm : The Psimplex algorithm
simplex method.
is based on the revised
This algorithm solves the LP problems in STANDARD FORM
minimize
s.t.
cTx
Ax=b
x>= 0
where vector b is non-negative.
Maximum # of variables, and maximum # of constraints are
set to maxvar =50 and maxconstraint=40 respectively.
One can modify them according to their needs. But
maxconstraint is <= maxvar.
EPS is small ral number such that if for ant real
54
İrfan MACİT
number a, |a|< EPS, then a =0.0
EPS is set to 10^-16 <= EPS <= 10^-4.
OUTPUT
NOTE
: Outputs are
1. Check if a LP
2. Determine the
corresponding
3. Determine the
is feasible and optimal solution exists.
optimal basic variables and their
values.
optimal value of the objective function
: This algorithm tests all nonbasic varables as candidates
for entering the basis. This is very time comsuming
*)
program Simplex(input,output,SimplexDatafile,SimplexOutfile);
const
maxvar = 50;
maxconstraint = 40;
EPS
= 0.00001;
type
CHARFILE
ARRM2M2
ARRM2N
ARRM2
ARRN
ARRM
var
Nextreal : real;
N,M
: integer;
A
: ARRM2N;
B,X
: ARRM2;
C
: ARRN;
W
: ARRM;
F
: real;
NOFEAS : boolean;
NOSOL
: boolean;
SimplexDatafile, SimplexOutfile : CHARFILE;
Nextint : integer;
= file of char;
= array[1..maxconstraint+2,1..maxconstraint+2] of real;
= array[1..maxconstraint+2,1..maxvar] of real;
= array[1..maxconstraint+2] of real;
= array[1..maxvar] of real;
= array[1..maxconstraint] of integer;
procedure Infile(var
var
var
var
var
var
N,M
:
A
:
B
:
C
:
Nextreal
Nextint
integer;
ARRM2N;
ARRM2;
ARRN;
: real;
: integer);
var row,column : integer;
begin
reset(SimplexDatafile);
readln(SimplexDatafile,Nextint);
N := Nextint;
readln(SimplexDatafile, Nextint);
M := Nextint;
55
İrfan MACİT
begin
begin
read(SimplexDatafile,Nextreal);
end;
readln(SimplexDatafile);
end;
begin
read(SimplexDatafile, Nextreal);
B[row] := Nextreal;
end;
begin
read(SimplexDatafile,Nextreal);
C[column] := Nextreal;
end;
end;
procedure PSIMPLEX(
M,N
EPS
var A
var B,X
var C
var W
var F
var NOFEAS,NOSOL
:integer;
:real;
:ARRM2N;
:ARRM2;
:ARRN;
:ARRM;
:real;
:boolean);
var I,J,K,L,P,Q :integer;
D,R,S
:real;
U
:ARRM2M2;
Y
:ARRM2;
EX,PHASE,STOP:boolean;
begin
NOFEAS:=false; NOSOL:=false;
P:=M+2; Q:=M+2;
PHASE:=true;
K:=M+1;
for J:=1 to N do begin
A[K,J]:=C[J];
S:=0.0;
for I:=1 to M do S:=S-A[I,J];
A[P,J]:=S
end; (* FOR J *)
S:=0.0;
for I:=1 to M do begin
W[I]:=N+I;
R:=B[I]; X[I]:=R;
S:=S-R
end; (* FOR I *)
56
İrfan MACİT
X[K]:=0.0; X[P]:=S;
for I:=1 to P do begin
for J:=1 to P do U[I,J]:=0.0;
U[I,I]:=1.0
end;
STOP:=false;
repeat (* UNTIL STOP *)
(* PHASE 1 *)
if (X[P] >= -EPS) and PHASE then begin
PHASE:=false; Q:=M+1
end;
D:=0.0;
(* PHASE 2 *)
for J:=1 to N do begin
S:=0.0;
for I:=1 to P do S:=S+U[Q,I]*A[I,J];
if D > S then begin D:=S; K:=J end
end; (* FOR J *)
if D > -EPS then begin
STOP:=true;
if PHASE then NOFEAS:=true
else F:=-X[Q]
end
else begin
for I:=1 to Q do begin
S:=0.0;
for J:=1 to P do S:=S+U[I,J]*A[J,K];
Y[I]:=S
end; (* FOR I *)
EX:=true;
for I:=1 to M do
if Y[I] >= EPS then begin
S:=X[I]/Y[I];
if EX or (S < D) then begin D:=S; L:=I end;
EX:=false
end; (* IF Y[I] >= EPS *)
if EX then begin NOSOL :=true; STOP:=true end
else begin
W[L]:=K; S:=1.0/Y[L];
for J:=1 to M do U[L,J]:=U[L,J]*S;
if L = 1 then I:=2 else I:=1;
repeat
S:=Y[I]; X[I]:=X[I]-D*S;
for J:=1 to M do U[I,J]:=U[I,J]-U[L,J]*S;
if I = L-1 then I:=I+2 else I:=I+1
until I > Q;
X[L]:=D
end (* ELSE: NOT EX *)
end (* ELSE: D <= -EPS *)
until STOP
end; (* PSIMPLEX *)
procedure Outfile(NOFEAS, NOSOL : boolean;
M
: integer;
F
: real;
W
: ARRM);
57
İrfan MACİT
begin
rewrite (SimplexOutfile);
if (NOFEAS = false) and (NOSOL = false) then
begin
writeln(SimplexOutfile,' NOFEAS = NOSOL ', NOFEAS);
writeln(SimplexOutfile,'
Basic-Var
Value');
for counter := 1 to M do
begin
write(SimplexOutfile,W[counter]);
writeln(SimplexOutfile,'
',X[counter]:9:2);
end;
writeln(SimplexOutfile,' Objective value for min problem is
end;
end;
begin (* main *)
Infile(N,M,A,B,C,Nextreal,Nextint);
PSIMPLEX(M,N,EPS,A,B,X,C,W,F,NOFEAS,NOSOL);
Outfile(NOFEAS,NOSOL,M,F,W);
end.
58
',F:9:2);

Bölüm 3 EMKBA

Transkript

Benzer belgeler

Ilahi (Hymn) Texts Music Examples

EFDAL PRIVATE KINDERGARTEN 2009

Göster/Aç

department of information technology school of

Sila 78 bolum.

Ailem Kelimeler

me 375 machine elements i - Department of Mechanical Engineering

The Investigation of Effects of Modelling and Computer