{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 260 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 261 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 262 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE " " 0 263 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 264 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 265 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {PARA 256 "" 0 "" {TEXT -1 41 "The Tools for Linear Programmin g Problems" }}{PARA 257 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 9 "Jim Herod" }}{PARA 265 "" 0 "" {TEXT -1 32 "Professor Emer itus, Georgia Tech" }}{PARA 259 "" 0 "" {TEXT -1 19 "jherod@mail.tds.n et" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 324 " \+ To a large extent, Mathematics in undergraduate instruction centers around three principal ideas: developing structure, developing algori thms, and constructing models. Especially in the introduction, the ins truction in the topic of linear programming is concerned with these la st two: teaching algorithms and modeling. " }}{PARA 0 "" 0 "" {TEXT -1 529 " It is not the purpose of this worksheet to teach modeling . This task is better left to the classroom and a good teacher, or goo d text. Rather, we illustrate how Maple can be used to compute the alg orithm. After all, the computation of an algorithm is the job of a com puter. Algorithms done by students are often boring after a few introd uctory trials. And, humans make mistakes! Why not spend classroom and \+ study time developing the creativity required to setup the model into \+ a form appropriate for invoking the algorithms?" }}{PARA 0 "" 0 "" {TEXT -1 162 " With this prologue, we present the form for using t he algorithms of Maple. We want a function to maximize (or minimize) a nd constraints. Here is an example: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 260 "" 0 "" {TEXT 256 10 "Maximize: " }{TEXT -1 1 " " } {XPPEDIT 18 0 "4*x-3*y+2*z;" "6#,(*&\"\"%\"\"\"%\"xGF&F&*&\"\"$F&%\"yG F&!\"\"*&\"\"#F&%\"zGF&F&" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "subject to the constraints:" }}{PARA 261 "" 0 "" {TEXT 257 13 "Con straints: " }{TEXT -1 1 " " }{XPPEDIT 18 0 "3*x-5*y+z <= 60,x-y+2*z <= 10,x+y-z <= 20;" "6%1,(*&\"\"$\"\"\"%\"xGF'F'*&\"\"&F'%\"yGF'!\"\"%\" zGF'\"#g1,(F(F'F+F,*&\"\"#F'F-F'F'\"#51,(F(F'F+F'F-F,\"#?" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 " \+ Maple's linear programming tools are found in the package " }{TEXT 258 7 "simplex" }{TEXT -1 150 ". We use these tools to find the values of x, y, and z which maximize the function, subject to the contraints , and evaluate what is the maximum value." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "with(simplex);" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 15 "Z:=4*x-3*y+2*z;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 51 "constraints:=\{3*x-5*y+z<=60,x-y+2*z<=10,x+y-z<=20 \};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "sols1:=maximize(Z,co nstraints);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "subs(sols1,Z );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 198 " A common assumption is that the values of x, y, and z are non-negative. We could add this inequality to the constraints, or simply list this constraint as a th ird value in the call to maximize." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "sols2:=maximize(Z,constraint s,NONNEGATIVE);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "subs(sol s2,Z);" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 72 " Sometimes the issue is not to maximize, but to minimize a fun ction." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 262 "" 0 "" {TEXT 259 10 "Minimize: " }{TEXT -1 1 " " }{XPPEDIT 18 0 "4*x-3*y+2*z;" "6#,(*& \"\"%\"\"\"%\"xGF&F&*&\"\"$F&%\"yGF&!\"\"*&\"\"#F&%\"zGF&F&" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "subject to the constraints:" }} {PARA 263 "" 0 "" {TEXT 260 13 "Constraints: " }{TEXT -1 1 " " } {XPPEDIT 18 0 "3*x-5*y+z <= 60,x-y+2*z <= 10,x+y-z <= 20;" "6%1,(*&\" \"$\"\"\"%\"xGF'F'*&\"\"&F'%\"yGF'!\"\"%\"zGF'\"#g1,(F(F'F+F,*&\"\"#F' F-F'F'\"#51,(F(F'F+F'F-F,\"#?" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 " The syntax is not much dif ferent." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "with(simplex):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "vals:=minimize(4*x-3*y+2*z,\n \+ \{3*x-5*y+2*z<=60,x-y+2*z<=10,x+y-z<=20\},NONNEGATIVE);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "subs(vals,4*x-3*y+2*z);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 171 "There are two final ideas that we illus trate. The first idea is the dual problem and the second is a geometri c understanding for how a maximization with constraints works." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 7 "Du ality" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 100 "This notion of duality involves structure. This structure is The Dual ity Theorem which we state here" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 264 "" 0 "" {TEXT -1 335 "Consider a linear programming problem \+ with constraints where the objective function C is to be minimized. S uch a program has an optimal solution if and only if the dual program, which has constraints and an objective function R to be maximized, h as an optimal solution. In this case, the maximal value of R is the mi nimal value of C." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 122 " We illustrate that Maple can create the dual proble m, and we compute the value of the original problem and its dual." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 14 "with(simplex):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Z:=6*x+8*y;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "constraints:=\{5*x+2*y<=20,x+2*y<=10\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "maxsol:=maximize(Z,constraints,NONNEGATIVE);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "subs(maxsol,Z);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "dualprob:=dual(Z,constraints,y);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "mimsol:=minimize(dualprob, NONNEGATIVE);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "ZZ:=dualpr ob[1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "subs(mimsol,ZZ); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 8 "Geometry" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 191 " It is no \+ surprise that there is geometry here. With complicated problems, the g eometry becomes complicated. The previous problem is not complicated a nd we try to illustrate the geometry." }}{PARA 0 "" 0 "" {TEXT -1 112 " First, we draw the constraints on variables x and y. We can see \+ the graphs of the constraints in the plane." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "plot([(20-5*x)/2,( 10-x)/2],x=0..5,color=[RED,GREEN]);" }}}{PARA 0 "" 0 "" {TEXT -1 200 " The points with non-negative coordinates which satisfy the constraints are the points which meet all these conditions: they lie to the right of the y-axis, above the x-axis, below the green line, and " }{TEXT -1 85 "below the red line. The intersection of the green line and the \+ red line can be found." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "jo int:=solve(\{5*x+2*y=20,x+2*y=10\},\{x,y\});" }}}{PARA 0 "" 0 "" {TEXT -1 214 "We now plot the function whose maximum value we want. Ob serve that the graph is a plane above the region described by the cons traints and that the maximum occurs at the intersection of the green a nd red line above." }{TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "J:=plot3d(6*x+8*y,x=0..5/2,y=0..(10-x)/2,axes=NORMAL, \n orientation=[-105,80]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "K:=plot3d(6*x+8*y,x=5/2..4,y=0..(20-5*x)/2,axes=NORMAL,\n orie ntation=[-105,80]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "with (plots):\ndisplay(\{J,K\});" }}}{PARA 0 "" 0 "" {TEXT -1 90 "Finally, \+ we evaluate the function to be maximized at the joint of the green and red lines." }{TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "subs(joint,6*x+8*y);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{PARA 0 "" 0 "" {TEXT -1 186 " In closing this section on geometr y, note that this geometric method could quickly become complicated wi th constraints in x and y. It becomes impenetrable for more constraint variables." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 24 "Exercise for the reader." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "Maximize x+y+z subject to the c onstraints: each of x, y, and z is nonnegative and " }}{PARA 0 "" 0 " " {TEXT -1 62 " x + 2 y + z 4, 2 x + y + \+ 3 z 6." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }