Taming a Beast called UNIX

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  problem1.result  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  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  problem3.result <==
??? it's a mystery! ???

Problem 3

==> problem4.input  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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s