Chapter 7

← Back to document page

Chapter7TheSimplexMethodInthischapter, ,youwillbeabletoidentifywhenaproblemhasa lternateoptimalsolutions(SOLVERnevertell syouthis:italwaysgiveyouonlyoneoptimalso lution). ,wepointoutthateverylinearprogramcanbeco nvertedinto\standard"formMaxc1x1+c2x2+:: :+cnxnsubjecttoa11x1+a12x2+:::+a1nxn=b1: ::::::::am1x1+am2x2+:::+amnxn=bmx1 0;:::xn 0wheretheobjectiveismaximized, : Iftheproblemisminz,convertittomax z. Ifaconstraintisai1x1+ai2x2+:::+ainxn bi, +ai2x2+:::+ainxn+si=bi,wheresi 0. Ifaconstraintisai1x1+ai2x2+:::+ainxn bi, +ai2x2+:::+ainxn si=bi,wheresi 0. Ifsomevariablexjisunrestrictedinsign,rep laceiteverywhereintheformulationbyx0j x00j,wherex0j 0andx00j 2x1+3x2x1 3x2+2x3 3 x1+2x2 2x1urs;x2 0;x3 0Letus 3x2x1 3x2+2x3+s1=3 x1+2x2 s2=2x1urs;x2 0;x3 0s1 0s2 0Thelaststepistoconverttheunrestrictedva riablex1intotwononnegativevariables:x1=x 01 2x001 3x2x01 x001 3x2+2x3+s1=3 x01+x001+2x2 s2=2x01 0;x001 0;x2 0;x3 0s1 0s2 ,inthiscoursewesolve\byhand"onlythecasew heretheconstraintsareoftheform +x22x1+x2 4x1+2x2 3x1 0;x2 0First,weconverttheproblemintos

90 CHAPTER 7. THE SIMPLEX METHOD z + x 2 4 = 3 Ro w0 3 x 2 + 3 2 4 = Ro w1 x 1 +2 2 + 4 = 3 Ro w2 with basic solution x 2 = 4 =0 1 =3 3 2 z: Whic h piv ot should w ec ho ose? The rst one, of course, since the second yields an

  Solutions, Chapter, Chapter 7