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 Bölüm 3 Bilgisayar Programlama Algoritmaları çö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 Bölüm 3 Bilgisayar Programlama Algoritmaları ç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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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); for counter := 1 to N do begin read(KnapAppxDatafile, Nextint); W[counter] := Nextint; 35 İrfan MACİT Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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); var counter : integer; begin rewrite(KnapAppxOutfile); writeln (KnapAppxOutfile,' PROFIT is ',PROFIT,' with '); for counter := 1 to N do 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları ,'& 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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; ran:=ran*mac1+trunc(1.0*ran*mac1/mac2); if ran<0 then ran:=ran+mac2+1; 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 ran:=ran*mac1+trunc(1.0*ran*mac1/mac2); if ran<0 then ran:=ran+mac2+1; c[i]^[j]:=round((ran/mac2*1000) + 0.5); c[j]^[i]:=c[i]^[j] 41 İrfan MACİT Bölüm 3 Bilgisayar Programlama Algoritmaları end; if screen then begin gotoxy(17,wherey); write(i) 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; if screen then begin gotoxy(15,wherey); write(i) 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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; if screen then begin gotoxy(15,wherey); write(i) 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları : : : : : : : 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); A[row,column] := 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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ölüm 3 Bilgisayar Programlama Algoritmaları 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); var counter : integer; 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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; for row := 1 to M do 55 İrfan MACİT Bölüm 3 Bilgisayar Programlama Algoritmaları begin for column := 1 to N do begin read(SimplexDatafile,Nextreal); A[row,column] := Nextreal; end; readln(SimplexDatafile); end; for row := 1 to M do begin read(SimplexDatafile, Nextreal); B[row] := Nextreal; end; readln(SimplexDatafile); for column := 1 to N do begin read(SimplexDatafile,Nextreal); C[column] := Nextreal; end; readln(SimplexDatafile); 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 Bölüm 3 Bilgisayar Programlama Algoritmaları 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); var counter : integer; 57 İrfan MACİT Bölüm 3 Bilgisayar Programlama Algoritmaları 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);