The year was 1988. Voices hushed in trepidation, the apprentices gathered in a dingy corner of the Engineering building. In the undergraduate computer lab we assembled to offer sacrifices to the mainframe, hunched over the fading amber or green glow of hesitant dumb terminals, all connected to the mighty UNIX (VAX/VMS) mainframe. Poor first year acolytes we were, learning various complex incantations to extract data from the Beast. We learned to navigate the perils of UNIX: using ed, vi, man, fortran, and other strange spells to tame the Beast. For some of those innocent souls, the Beast caused them to cringe in fear and retreat to a “lesser” academic career, or flee gibbering and drooling in fear. Alas, I was an overconfident youth whose world was shattered by the Beast. So it was that I gave up my dream of conquest and glory.
But fate is fickle, and the world ever turns. So it was that seven years later, after a journeyman’s life, I wandered accidentally back into the nether realms of UNIX. However this time, I was different — stronger in body and mind from years of hard labour — and was wary of the nature of the Beast. Also, Unix itself was a different creature, somewhat mellowed with age, more tractable, less hostile: even unto supporting lower-case symbols and X-windows. So it was that an uneasy truce was forged between Unix and I. We learned to work together. Thus it was that I saw the Beast in a different light: a creature of mankind designed to serve, but only those who prove themselves worthy by mastering its secrets.
One of my greatest masterpieces was written in g77, the GNU port of Fortran. This program applies the Revised Simplex Method in two phases to find the optimal solution to a set of linear equations. I can’t remember all the mathematical theory and strategies involved, but the code still looks cool. For posterity I now give it to the world.
program main
implicit none ! Set up variables..
integer o,p
parameter(o=20,p=100)
integer i,j,m,n,r,s
integer apos(o),bpos(o)
real A(o,p),Bi(o,o),b(o),xb(o),cost(p),ca(o+p)
! Read data..
open(unit=8,file='lp.dat',status='old')
open(unit=9,file='lp.out',status='new')
read(8,*) m,n
if (m.gt.o.or.n.gt.p) then
write(9,*)'Exceeded variable/constraint limits'
endif
read(8,*) (cost(j),j=1,n)
write(9,*) 'm ',m
write(9,*) 'n ',n
write(9,*) 'c'' ',(cost(j),j=1,n)
write(9,*)
write(9,*) 'A.x = b'
do i=1,m
read(8,*) (A(i,j),j=1,n),b(i)
write(9,*) (A(i,j),j=1,n),' =',b(i)
enddo
c ------------------extra bit..-----------------
do i=1,m
read(8,*) (Bi(i,j),j=1,m)
write(9,*) (Bi(i,j),j=1,m)
enddo
read(8,*) (bpos(i),i=1,m)
write(9,*) (bpos(i),i=1,m)
read(8,*) (apos(i),i=1,n)
write(9,*) (apos(i),i=1,n)
do i=1,m
do j=1,m
xb(i)=xb(i)+Bi(i,j)*b(j)
enddo
enddo
goto 5
c -----------------------miss out for now------------------------
write(9,*)
write(9,*) 'Phase 1'
do i=1,n ! Phase 1
ca(i)=0 ! Prepare artificial cost,basis,variables
apos(i)=0 ! all original variables are nonbasic
enddo
do i=1,m
do j=1,m
Bi(i,j)=0 ! initially Bi = identity matrix, I
enddo
Bi(i,i)=1
ca(n+i)=1 ! artificial cost vector now constructed
bpos(i)=n+i ! artificial variables fill the basis
xb(i)=b(i) ! initially xb = b (because xb=Bi.b, Bi=I)
enddo
call rsm(m,n,A,Bi,b,xb,ca,bpos,apos,1)
c ---------------------------------------------------------------
5 write(9,*)
write(9,*) 'Phase 2'
! Phase 2
! Now do RSM with the new basis
call rsm(m,n,A,Bi,b,xb,cost,bpos,apos,2)
end
C--------------------------------------------------
subroutine rsm(m,n,A,Bi,b,xb,c,bpos,apos,phase)
parameter(o=20,p=100)
integer apos(n),bpos(m),phase ! variables passed to rsm
real A(o,p),Bi(o,o),b(m),c(n+m) ! "
integer i,j,imax,r,s,note ! introducing new variables
real bestrc,bias(m),pi(m),xb(m),z ! "
character retval
imax=2*(m+n)
tiny=1E-10
i=0
call currentsoln(Bi,b,bpos,c,m,xb,z)
1 if (i.lt.imax) then ! Iterate Revised Simplex Method..
i=i+1
call computedual(Bi,c,bpos,m,n,pi) ! find pi (initially pi=e)
call reducedcost(A,c,pi,apos,m,n,s,bestrc)
if(s.eq.0) then
if(z.gt.tiny.and.phase.eq.1) then
write(9,*) ' Infeasibility detected.'
note=-2
else
write(9,*) ' Optimality reached.'
note=1
endif
goto 3
endif
call mivitwwbias(A,Bi,m,s,bias)
call lvratiotest(xb,bias,m,n,r,phase,bpos)
if (r.eq.0) then
write(9,*) ' Unboundedness detected.'
note=-1
goto 3
endif
write(9,*) 'basisupdate:'
write(9,*) ' bpos',(bpos(j),j=1,m),' apos',(apos(j),j=1,n)
call basisupdate(Bi,bias,c,pi,xb,bpos,apos,m,n,r,s)
write(9,*) ' ->',(bpos(j),j=1,m),' ->',(apos(j),j=1,n)
call currentsoln(Bi,b,bpos,c,m,xb,z)
else
goto 3
endif
2 goto 1
3 write(9,*) ' RSM iterations executed: ',i
end
C-----------------------------------------------------
subroutine currentsoln(Bi,b,bpos,c,m,xb,z)
parameter(o=20)
integer bpos(*) ! old
real Bi(o,o),b(*),c(*),xb(*),z ! old
integer i,j ! new
z=0
do i=1,m
z=z+c(bpos(i))*xb(i)
enddo
write(9,*) 'currentsoln: Bi, xb'
do i=1,m
write(9,*) ' ',(Bi(i,j),j=1,m),' x',bpos(i),' =',xb(i)
enddo
write(9,*)
write(9,*) ' --------------------------- Objective value z =',z
write(9,*)
end
C-----------------------------------------------------
subroutine computedual(Bi,c,bpos,m,n,pi)
parameter(o=20)
integer bpos(*) ! old
real Bi(o,o),c(*),pi(*) ! old
integer i,j,k ! new
do i=1,m
pi(i)=0
do j=1,m
k=bpos(j)
pi(i)=pi(i)+c(k)*Bi(j,i)
enddo
enddo
write(9,*) 'computedual: pi ',(pi(i),i=1,m)
end
C----------------------------------------------------
subroutine reducedcost(A,c,pi,apos,m,n,s,bestrc)
parameter(o=20,p=100)
integer apos(*),s ! old
real A(o,p),c(*),pi(*),bestrc ! old
integer i,j ! new
real rc,pian,tiny ! new
rc=0
bestrc=0
tiny=-1E-10
do i=1,n ! determine entering var x(s)
if(apos(i).eq.0) then !< look at nonbasic columns
pian=0 ! (never price artificials)
do j=1,m
pian=pian+pi(j)*A(j,i)
enddo
rc=c(i)-pian !< red. cost for nonbasic x(i)
if(rc.lt.bestrc) then
bestrc=rc
s=i
endif
endif
enddo
if(bestrc.ge.tiny) then !< This means no ev was found,
s=0 ! optimality has been reached,
endif ! so flag s to 0
write(9,*) 'reducedcost: x',s,' enters with rc',bestrc
end
C----------------------------------------------------
subroutine mivitwwbias(A,Bi,m,s,bias)
parameter(o=20,p=100)
real A(o,p),Bi(o,o),bias(*)
integer i,j,s
do i=1,m ! a quick calculation of bias,
bias(i)=0 ! aka. the most important vector
do j=1,m ! in the whole world.
bias(i)=bias(i)+Bi(i,j)*A(j,s)
enddo
enddo
write(9,*) 'mivitwwbias: bias',(bias(j),j=1,m)
end
C----------------------------------------------------
subroutine lvratiotest(xb,bias,m,n,r,phase,bpos)
integer bpos(*),r,phase ! old
real xb(*),bias(*) ! old
integer i ! new
real ratio,rmin,tiny ! new
r=0 ! r=0 returned if no lv can be found
tiny=1E-10
teeny=-1E-10
rmin=10E+10
do i=1,m
if(bpos(i).gt.n.and.phase.eq.2) then
! Artificial present in phase2 basis:
! Extended lv routine to force out
! artificial variables..
if(bias(i).lt.teeny.or.bias(i).gt.tiny) then
rmin=0
r=i
endif
else ! Usual lv routine..
if(bias(i).gt.tiny) then ! ratio = rate of change of xb(i), as
ratio=xb(i)/bias(i) ! xs increases from 0 (enters)
if(ratio.lt.rmin) then
rmin=ratio ! the leaving variable is xb(r), the
r=i ! basic variable which decreases most
endif ! rapidly as xs enters.
endif
endif
enddo
write(9,*) 'lvratiotest: xb',r,' leaves.'
end
C----------------------------------------------------
subroutine basisupdate(Bi,bias,c,pi,xb,bpos,apos,m,n,r,s)
parameter(o=20)
integer apos(*),bpos(*),m,n,r,s ! old
real Bi(o,o),bias(*),c(*),pi(*),xb(*) ! old
integer i,j ! new
do i=1,m ! do gauss-jordan pivot on rth element
if(i.eq.r) then ! of bias, and thus also on Bi and xb
do j=1,m
Bi(r,j)=Bi(r,j)/bias(r)
enddo
xb(r)=xb(r)/bias(r)
else
do j=1,m
Bi(i,j)=Bi(i,j)-bias(i)/bias(r)*Bi(r,j)
enddo
xb(i)=xb(i)-bias(i)/bias(r)*xb(r)
endif
enddo
if(bpos(r).le.n) then
apos(bpos(r))=0 ! xb(r) now nonbasic; 0 in apos
endif
bpos(r)=s ! xb(r) replaced by xs in bpos
apos(s)=r ! xs located in rth basic position
end
simplex.f
Note: the above code has not been compiled or executed since sometime around 1998.
Here are some problems solved using this glorious program.
==> problem1.input <==
3
6
1 2 3 0 0 0
1 -1 1 1 0 0 4
1 1 0 0 -1 0 0
0 0 1 0 0 1 6
==> problem1.result <==
m 3
n 6
c' 1. 2. 3. 0. 0. 0.
A.x = b
1. -1. 1. 1. 0. 0. = 4.
1. 1. 0. 0. -1. 0. = 0.
0. 0. 1. 0. 0. 1. = 6.
Phase 1
currentsoln: Bi, xb
1. 0. 0. x 7 = 4.
0. 1. 0. x 8 = 0.
0. 0. 1. x 9 = 6.
--------------------------- Objective value z = 10.
computedual: 1. 1. 1.
reducedcost: x 1 enters with rc -2.
mivitwwbias: 1. 1. 0.
lvratiotest: xb 2 leaves basis
basisupdate:
bpos 7 8 9 apos 0 0 0 0 0 0
-> 7 1 9 -> 2 0 0 0 0 0
currentsoln: Bi, xb
1. -1. 0. x 7 = 4.
0. 1. 0. x 1 = 0.
0. 0. 1. x 9 = 6.
--------------------------- Objective value z = 10.
computedual: 1. -1. 1.
reducedcost: x 3 enters with rc -2.
mivitwwbias: 1. 0. 1.
lvratiotest: xb 1 leaves basis
basisupdate:
bpos 7 1 9 apos 2 0 0 0 0 0
-> 3 1 9 -> 2 0 1 0 0 0
currentsoln: Bi, xb
1. -1. 0. x 3 = 4.
0. 1. 0. x 1 = 0.
-1. 1. 1. x 9 = 2.
--------------------------- Objective value z = 2.
computedual: -1. 1. 1.
reducedcost: x 2 enters with rc -2.
mivitwwbias: -2. 1. 2.
lvratiotest: xb 2 leaves basis
basisupdate:
bpos 3 1 9 apos 2 0 1 0 0 0
-> 3 2 9 -> 0 2 1 0 0 0
currentsoln: Bi, xb
1. 1. 0. x 3 = 4.
0. 1. 0. x 2 = 0.
-1. -1. 1. x 9 = 2.
--------------------------- Objective value z = 2.
computedual: -1. -1. 1.
reducedcost: x 5 enters with rc -1.
mivitwwbias: -1. -1. 1.
lvratiotest: xb 3 leaves basis
basisupdate:
bpos 3 2 9 apos 0 2 1 0 0 0
-> 3 2 5 -> 0 2 1 0 3 0
currentsoln: Bi, xb
0. 0. 1. x 3 = 6.
-1. 0. 1. x 2 = 2.
-1. -1. 1. x 5 = 2.
--------------------------- Objective value z = 0.
computedual: 0. 0. 0.
reducedcost: x 0 enters with rc 0.
Optimality reached.
RSM iterations executed: 5
Phase 2
currentsoln: Bi, xb
0. 0. 1. x 3 = 6.
-1. 0. 1. x 2 = 2.
-1. -1. 1. x 5 = 2.
--------------------------- Objective value z = 22.
computedual: -2. 0. 5.
reducedcost: x 6 enters with rc -5.
mivitwwbias: 1. 1. 1.
lvratiotest: xb 2 leaves basis
basisupdate:
bpos 3 2 5 apos 0 2 1 0 3 0
-> 3 6 5 -> 0 0 1 0 3 2
currentsoln: Bi, xb
1. 0. 0. x 3 = 4.
-1. 0. 1. x 6 = 2.
0. -1. 0. x 5 = 0.
--------------------------- Objective value z = 12.
computedual: 3. 0. 0.
reducedcost: x 4 enters with rc -3.
mivitwwbias: 1. -1. 0.
lvratiotest: xb 1 leaves basis
basisupdate:
bpos 3 6 5 apos 0 0 1 0 3 2
-> 4 6 5 -> 0 0 0 1 3 2
currentsoln: Bi, xb
1. 0. 0. x 4 = 4.
0. 0. 1. x 6 = 6.
0. -1. 0. x 5 = 0.
--------------------------- Objective value z = 0.
computedual: 0. 0. 0.
reducedcost: x 0 enters with rc 0.
Optimality reached.
RSM iterations executed: 3
Problem 1
==> problem2.input <==
4
22
0. -0.670320046 -0.449328964 -0.301194212 -0.201896518 -0.135335283
-0.0907179533 -0.0608100626 -0.040762204 -0.0273237224 -0.0183156389 0.
0.670320046 0.449328964 0.301194212 0.201896518 0.135335283 0.0907179533
0.0608100626 0.040762204 0.0273237224 0.0183156389
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
0. 0.2 0.4 0.6 0.8 1. 1.2 1.4 1.6 1.8 2. 0. -0.2 -0.4 -0.6 -0.8
-1. -1.2 -1.4 -1.6 -1.8 -2. 0 0
==> problem2.result <==
m 4
n 22
c' 0. -0.670320046 -0.449328964 -0.301194212 -0.201896518 -0.135335283
-0.0907179533 -0.0608100626 -0.040762204 -0.0273237224 -0.0183156389 0.
0.670320046 0.449328964 0.301194212 0.201896518 0.135335283 0.0907179533
0.0608100626 0.040762204 0.0273237224 0.0183156389
A.x = b
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. = 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. -1. -1. -1. -1. -1. -1. -1. -1.
-1. -1. -1. = 0.
0. 0.2 0.4 0.6 0.8 1. 1.2 1.4 1.6 1.8 2. 0. -0.2 -0.4 -0.6 -0.8
-1. -1.2 -1.4 -1.6 -1.8 -2. = 0.
0. 0.04 0.16 0.36 0.64 1. 1.44 1.96 2.56 3.24 4. 0. -0.04 -0.16
-0.36 -0.64 -1. -1.44 -1.96 -2.56 -3.24 -4. = 0.
**Phase 1**
currentsoln: Bi, xb
1. 0. 0. 0. x 23 = 1.
0. 1. 0. 0. x 24 = 0.
0. 0. 1. 0. x 25 = 0.
0. 0. 0. 1. x 26 = 0.
Objective value z = 1.
------------------------------------
Iteration 1
computedual: 1. 1. 1. 1.
reducedcost: x 11 enters with rc -8.
mivitwwbias: 1. 1. 2. 4.
lvratiotest: xb 2 leaves basis
basisupdate: bpos 23 24 25 26 apos 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0
» 23 11 25 26 » 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
0
currentsoln: Bi, xb
1. -1. 0. 0. x 23 = 1.
0. 1. 0. 0. x 11 = 0.
0. -2. 1. 0. x 25 = 0.
0. -4. 0. 1. x 26 = 0.
Objective value z = 1.
------------------------------------
Iteration 2
computedual: 1. -7. 1. 1.
reducedcost: x 12 enters with rc -8.
mivitwwbias: 2. -1. 2. 4.
lvratiotest: xb 3 leaves basis
basisupdate: bpos 23 11 25 26 apos 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
0
» 23 11 12 26 » 0 0 0 0 0 0 0 0 0 0 2 3 0 0 0 0 0 0 0 0 0
0
currentsoln: Bi, xb
1. 1. -1. 0. x 23 = 1.
0. 0. 0.5 0. x 11 = 0.
0. -1. 0.5 0. x 12 = 0.
0. 0. -2. 1. x 26 = 0.
Objective value z = 1.
------------------------------------
Iteration 3
computedual: 1. 1. -3. 1.
reducedcost: x 20 enters with rc -2.24
mivitwwbias: 1.6 -0.8 0.2 0.64
lvratiotest: xb 3 leaves basis
basisupdate: bpos 23 11 12 26 apos 0 0 0 0 0 0 0 0 0 0 2 3 0 0 0 0 0 0 0 0 0
0
» 23 11 20 26 » 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 3 0
0
currentsoln: Bi, xb
1. 9. -5. 0. x 23 = 1.
0. -4. 2.5 0. x 11 = 0.
0. -5. 2.5 0. x 20 = 0.
0. 3.2 -3.6 1. x 26 = 0.
Objective value z = 1.
------------------------------------
Iteration 4
computedual: 1. 12.2 -8.6 1.
reducedcost: x 1 enters with rc -13.2
mivitwwbias: 10. -4. -5. 3.2
lvratiotest: xb 4 leaves basis
basisupdate: bpos 23 11 20 26 apos 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 3 0
0
» 23 11 20 1 » 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 3 0
0
currentsoln: Bi, xb
1. -1. 6.25 -3.125 x 23 = 1.
0. 0. -2. 1.25 x 11 = 0.
0. 0. -3.125 1.5625 x 20 = 0.
0. 1. -1.125 0.3125 x 1 = 0.
Objective value z = 1.
------------------------------------
Iteration 5
computedual: 1. -1. 6.25 -3.125
reducedcost: x 6 enters with rc -3.125
mivitwwbias: 3.125 -0.75 -1.5625 0.1875
lvratiotest: xb 4 leaves basis
basisupdate: bpos 23 11 20 1 apos 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 3 0
0
» 23 11 20 6 » 0 0 0 0 0 4 0 0 0 0 2 0 0 0 0 0 0 0 0 3 0
0
currentsoln: Bi, xb
1. -17.6666667 25. -8.33333333 x 23 = 1.
0. 4. -6.5 2.5 x 11 = 0.
0. 8.33333333 -12.5 4.16666667 x 20 = 0.
0. 5.33333333 -6. 1.66666667 x 6 = 0.
Objective value z = 1.
------------------------------------
Iteration 6
computedual: 1. -17.6666667 25. -8.33333333
reducedcost: x 12 enters with rc -18.6666667
mivitwwbias: 18.6666667 -4. -8.33333333 -5.33333333
lvratiotest: xb 1 leaves basis
basisupdate: bpos 23 11 20 6 apos 0 0 0 0 0 4 0 0 0 0 2 0 0 0 0 0 0 0 0 3 0
0
» 12 11 20 6 » 0 0 0 0 0 4 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0
0
currentsoln: Bi, xb
0.0535714286 -0.946428571 1.33928571 -0.446428571 x 12 = 0.0535714286
0.214285714 0.214285714 -1.14285714 0.714285714 x 11 = 0.214285714
0.446428571 0.446428571 -1.33928571 0.446428571 x 20 = 0.446428571
0.285714286 0.285714286 1.14285714 -0.714285714 x 6 = 0.285714286
Objective value z = 0.
------------------------------------
Iteration 7
computedual: 0. 0. 0. 0.
reducedcost: x 0 enters with rc 0.
Optimality reached.
**Phase 2**
currentsoln: Bi, xb
0.0535714286 -0.946428571 1.33928571 -0.446428571 x 12 = 0.0535714286
0.214285714 0.214285714 -1.14285714 0.714285714 x 11 = 0.214285714
0.446428571 0.446428571 -1.33928571 0.446428571 x 20 = 0.446428571
0.285714286 0.285714286 1.14285714 -0.714285714 x 6 = 0.285714286
Objective value z = -0.024394591
------------------------------------
Iteration 1
computedual: -0.024394591 -0.024394591 -0.188328974 0.101782873
reducedcost: x 2 enters with rc -0.587936384
mivitwwbias: -0.642857143 0.228571429 0.642857143 0.771428571
lvratiotest: xb 4 leaves basis
basisupdate: bpos 12 11 20 6 apos 0 0 0 0 0 4 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0
0
» 12 11 20 2 » 0 4 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0
0
currentsoln: Bi, xb
0.291666667 -0.708333333 2.29166667 -1.04166667 x 12 = 0.291666667
0.12962963 0.12962963 -1.48148148 0.925925926 x 11 = 0.12962963
0.208333333 0.208333333 -2.29166667 1.04166667 x 20 = 0.208333333
0.37037037 0.37037037 1.48148148 -0.925925926 x 2 = 0.37037037
Objective value z = -0.242148807
------------------------------------
Iteration 2
computedual: -0.242148807 -0.242148807 -1.05934584 0.646168414
reducedcost: x 17 enters with rc -0.277842143
mivitwwbias: -0.25 0.555555556 1.25 -0.555555556
lvratiotest: xb 3 leaves basis
basisupdate: bpos 12 11 20 2 apos 0 4 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0
0
» 12 11 17 2 » 0 4 0 0 0 0 0 0 0 0 2 1 0 0 0 0 3 0 0 0 0
0
currentsoln: Bi, xb
0.333333333 -0.666666667 1.83333333 -0.833333333 x 12 = 0.333333333
0.037037037 0.037037037 -0.462962963 0.462962963 x 11 = 0.037037037
0.166666667 0.166666667 -1.83333333 0.833333333 x 17 = 0.166666667
0.462962963 0.462962963 0.462962963 -0.462962963 x 2 = 0.462962963
Objective value z = -0.288455831
------------------------------------
Iteration 3
computedual: -0.288455831 -0.288455831 -0.549968578 0.414633295
reducedcost: x 0 enters with rc 0.
Optimality reached.
Problem 2
==> problem3.input <== 3 6 -3 -1 2 -3 1 2 1 3 2 4 1 6 10 2 1 0 1 -1 -3 4 0 0 3 -2 0 1 7 ==> problem3.result <== ??? it's a mystery! ???
Problem 3
==> problem4.input <==
3
5
-4 -5 0 0 0
1 0 1 0 0 4
0 2 0 1 0 10
4 3 0 0 1 24
==> problem4.result <==
m 3
n 5
c' -4. -5. 0. 0. 0.
A.x = b
1. 0. 1. 0. 0. = 4.
0. 2. 0. 1. 0. = 10.
4. 3. 0. 0. 1. = 24.
**Phase 1**
currentsoln: Bi, xb
1. 0. 0. x 6 = 4.
0. 1. 0. x 7 = 10.
0. 0. 1. x 8 = 24.
¤~~~ Objective value z = 38. ~~~¤
Iteration 1
computedual: 1. 1. 1.
reducedcost: x 1 enters with rc -5.
mivitwwbias: 1. 0. 4.
lvratiotest: xb 1 leaves basis
basisupdate:
bpos 6 7 8 apos 0 0 0 0 0
» 1 7 8 » 1 0 0 0 0
currentsoln: Bi, xb
1. 0. 0. x 1 = 4.
0. 1. 0. x 7 = 10.
-4. 0. 1. x 8 = 8.
¤~~~ Objective value z = 18. ~~~¤
Iteration 2
computedual: -4. 1. 1.
reducedcost: x 2 enters with rc -5.
mivitwwbias: 0. 2. 3.
lvratiotest: xb 3 leaves basis
basisupdate:
bpos 1 7 8 apos 1 0 0 0 0
» 1 7 2 » 1 3 0 0 0
currentsoln: Bi, xb
1. 0. 0. x 1 = 4.
2.66666667 1. -0.666666667 x 7 = 4.66666667
-1.33333333 0. 0.333333333 x 2 = 2.66666667
¤~~~ Objective value z = 4.66666667 ~~~¤
Iteration 3
computedual: 2.66666667 1. -0.666666667
reducedcost: x 3 enters with rc -2.66666667
mivitwwbias: 1. 2.66666667 -1.33333333
lvratiotest: xb 2 leaves basis
basisupdate:
bpos 1 7 2 apos 1 3 0 0 0
» 1 3 2 » 1 3 2 0 0
currentsoln: Bi, xb
0. -0.375 0.25 x 1 = 2.25
1. 0.375 -0.25 x 3 = 1.75
0. 0.5 0. x 2 = 5.
¤~~~ Objective value z = 0. ~~~¤
Iteration 4
computedual: 0. 0. 0.
reducedcost: x 0 enters with rc 0.
Optimality reached.
**Phase 2**
currentsoln: Bi, xb
0. -0.375 0.25 x 1 = 2.25
1. 0.375 -0.25 x 3 = 1.75
0. 0.5 0. x 2 = 5.
¤~~~ Objective value z = -34. ~~~¤
Iteration 1
computedual: 0. -1. -1.
reducedcost: x 0 enters with rc 0.
Optimality reached.
Problem 4
PS: Hi Professor!
.JPG)
