{VERSION 3 0 "IBM INTEL NT" "3.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 
0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" 
-1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 
-1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Co
urier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 }1 0 0 -1 -1 -1 0 0 0 0 0 0 
-1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 
0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 
0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 
-1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 18 "Midterm, Problem 1" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}{PARA 7 "" 
1 "" {TEXT -1 32 "Warning, new definition for norm" }}{PARA 7 "" 1 "" 
{TEXT -1 33 "Warning, new definition for trace" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 17 "Define functions:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 79 "E_2 := proc(n, i, alpha)\n   mulrow(array(identity, 1
..n,1..n), i, alpha);\nend:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 73 "Pivot:=proc(A,i,j) linalg[pivot](E_2(rowdim(A),i,1/A[i,j]) &* A,
i,j) end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&PivotGR6%%\"AG%\"iG%\"
jG6\"F*F*-&%'linalgG6#%&pivotG6%-%#&*G6$-%$E_2G6%-%'rowdimG6#9$9%*&\"
\"\"F=&F:6$F;9&!\"\"F:F;F@F*F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
37 "Text, p. 121, no. 20:                " }{TEXT 272 4 " max" }{TEXT 
-1 3 " \{ " }{TEXT 256 1 "c" }{TEXT -1 3 "^T " }{TEXT 257 1 "x" }
{TEXT -1 6 " :  A " }{TEXT 258 1 "x" }{TEXT -1 4 " <= " }{TEXT 259 1 "
b" }{TEXT -1 2 ", " }{TEXT 260 1 "x" }{TEXT -1 3 " >=" }{TEXT 261 2 " \+
0" }{TEXT -1 7 " \} with" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 
"A:=matrix(3,4,[2,1,3,1,2,3,0,4,3,1,2,0]);b:=vector(3,[8,12,18]);c:=ve
ctor(4,[1,2,1,1]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'matrixG
6#7%7&\"\"#\"\"\"\"\"$F+7&F*F,\"\"!\"\"%7&F,F+F*F." }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%\"bG-%'vectorG6#7%\"\")\"#7\"#=" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%\"cG-%'vectorG6#7&\"\"\"\"\"#F)F)" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 25 "Introduce slack variables" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 41 "A1:=augment(A,array(1..3,1..3,identity));" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A1G-%'matrixG6#7%7)\"\"#\"\"\"\"\"$
F+F+\"\"!F-7)F*F,F-\"\"%F-F+F-7)F,F+F*F-F-F-F+" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 18 "Ab:=augment(A1,b);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#AbG-%'matrixG6#7%7*\"\"#\"\"\"\"\"$F+F+\"\"!F-\"\")7
*F*F,F-\"\"%F-F+F-\"#77*F,F+F*F-F-F-F+\"#=" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 33 "c1:=vector(8,[1,2,1,1,0,0,0,0]);;" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#>%#c1G-%'vectorG6#7*\"\"\"\"\"#F)F)\"\"!F+F+F+" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Abc:=stackmatrix(-c1,Ab);" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$AbcG-%'matrixG6#7&7*!\"\"!\"#F*F*
\"\"!F,F,F,7*\"\"#\"\"\"\"\"$F/F/F,F,\"\")7*F.F0F,\"\"%F,F/F,\"#77*F0F
/F.F,F,F,F/\"#=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,
2,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*\"\"!#!\"$\"
\"##\"\"\"F+#!\"\"F+F,F(F(\"\"%7*F-F,#\"\"$F+F,F,F(F(F07*F(F+F*F3F/F-F
(F07*F(F.#!\"&F+F)F)F(F-\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 13 "Pivot(%,3,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7
*\"\"!F(#!\"(\"\"%#\"\"(F+#!\"\"F+#\"\"$F+F(F-7*\"\"\"F(#\"\"*F+F.F0F.
F(F17*F(F3#!\"$\"\"##F1F9#F/F9#F3F9F(F97*F(F(#!#8F+#F8F+F)#F3F+F3F-" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,2,3);" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*#\"\"(\"\"*\"\"!F+#\"#9F*#\"\"
\"\"\"$#\"\"&F*F+#\"#GF07*#\"\"%F*F+F/#!\"\"F*F.F8F+#F7F07*#\"\"#F0F/F
+F:F+F.F+F77*#\"#8F*F+F+#!#5F*#!\"#F0F8F/#\"#MF0" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 12 "The vector [" }{TEXT 268 11 "1/3, 5/9, 0" }{TEXT 
-1 34 "] (in row 1, slack columns) is an " }{TEXT 269 16 "optimal solu
tion" }{TEXT -1 8 " of the " }{TEXT 270 12 "dual problem" }}{PARA 0 "
" 0 "" {TEXT -1 76 "                                                  \+
                          " }{TEXT 271 3 "min" }{TEXT -1 2 " \{" }
{TEXT 262 1 "b" }{TEXT -1 3 "^T " }{TEXT 263 1 "y" }{TEXT -1 7 " : A^T
 " }{TEXT 264 2 "y " }{TEXT -1 3 ">= " }{TEXT 265 1 "c" }{TEXT -1 2 ",
 " }{TEXT 266 1 "y" }{TEXT -1 4 " >= " }{TEXT 267 1 "0" }{TEXT -1 2 " \+
\}" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 273 12 "Dual Me
thod," }{TEXT -1 30 " illustrated below, maintains " }{TEXT 274 16 "du
al feasibility" }{TEXT -1 15 ", and improves " }{TEXT 275 18 "primal f
easibility" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "Abc;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#%$AbcG" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 9 "evalm(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrix
G6#7&7*!\"\"!\"#F(F(\"\"!F*F*F*7*\"\"#\"\"\"\"\"$F-F-F*F*\"\")7*F,F.F*
\"\"%F*F-F*\"#77*F.F-F,F*F*F*F-\"#=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 43 "First we iterate to obtain dual feasibility" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,4,1);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#-%'matrixG6#7&7*\"\"!#!\"&\"\"$#!\"\"F+F-F(F(#\"\"\"F+\"\"'7*F(F
.#\"\"&F+F/F/F(#!\"#F+!\"%7*F(#\"\"(F+#F6F+\"\"%F(F/F4F(7*F/F.#\"\"#F+
F(F(F(F.F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,3,2);
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7&7*\"\"!F(#!\"*\"\"(#
\"#8F+F(#\"\"&F+#!\"\"F+\"\"'7*F(F(F,#\"\"$F+\"\"\"F0#!\"%F+F87*F(F6F7
#\"#7F+F(F4#!\"#F+F(7*F6F(#F2F+F7F(F0F4F2" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 13 "Pivot(%,4,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%
'matrixG6#7&7*#\"\"$\"\"#\"\"!F+\"\"\"F+#F,F*F-\"#:7*#!#8\"\"'F+F+#\"
\"&F)F,#F,F2#!\"$F*!#<7*#F*F)F,F+#\"\"%F)F+#F,F)F+F<7*#\"\"(F2F+F,#!\"
#F)F+#!\"\"F2F-F@" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "This table r
epresents the " }{TEXT 277 3 "BS " }{TEXT -1 1 " " }{TEXT 276 25 "x2 =
 4, x3 = 7, x5 = -17." }{TEXT -1 12 " This BS is " }{TEXT 278 15 "dual
ly feasible" }{TEXT -1 2 ", " }{TEXT 279 19 "primally infeasible" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "Dual iteration:" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 13 "Pivot(%,2,7);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#-%'matrixG6#7&7*#\"\"(\"\"*\"\"!F+#\"#9F*#\"\"\"\"\"$#
\"\"&F*F+#\"#GF07*#\"#8F*F+F+#!#5F*#!\"#F0#!\"\"F*F/#\"#MF07*#\"\"#F0F
/F+#\"\"%F0F+F.F+FD7*#FDF*F+F/F<F.F<F+FC" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 3 "An " }{TEXT 280 44 "optimal solution x2 = 4, x3 = 4/3, x7 \+
= 34/3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "26 0 \+
1" 44 }{VIEWOPTS 1 1 0 1 1 1803 }