{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 }