{VERSION 2 3 "IBM INTEL NT" "2.3" } {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 "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "2 D 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 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 0 1 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 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 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 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 } 0 0 0 -1 4 4 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 "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "newpa ge" -1 256 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 1 0 -1 0 }{PSTYLE "vfill" -1 257 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 "R3 Font 0" -1 258 1 {CSTYLE "" -1 -1 "Courier" 1 18 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2 " -1 259 1 {CSTYLE "" -1 -1 "Lucidabright" 1 19 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 3" -1 260 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 4" -1 261 1 {CSTYLE "" -1 -1 "Lu cida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 5" -1 262 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 6 " -1 263 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 7" -1 264 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 8" -1 265 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 9" -1 266 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 1 0" -1 267 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 11" -1 268 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 12" -1 269 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 13" -1 270 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 14" -1 271 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 15" -1 272 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 16" -1 273 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 17" -1 274 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 18" -1 275 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 19" -1 276 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 20" -1 277 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 21" -1 278 1 {CSTYLE "" -1 -1 "Lucidatypewrit er" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 22" -1 279 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 23" -1 280 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 24" -1 281 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 25" -1 282 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 26" -1 283 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 27" -1 284 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 28" -1 285 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 4 286 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "dblnorm" -1 287 1 {CSTYLE " " -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 2 0 10 4 -1 3 12 3 12 0 0 285 0 }{PSTYLE "xxx" 0 288 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 3 30 3 30 0 0 -1 0 }{PSTYLE "Appendix" 4 289 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 1 0 -1 -1 -1 0 0 0 0 1 0 0 0 }{PSTYLE "dbullet" 15 290 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 2 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 291 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 292 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE " " 0 293 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 294 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 295 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 296 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 297 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 298 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 299 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 300 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 301 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 302 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 303 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 304 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 305 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 306 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 307 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 308 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 309 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 310 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 311 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 312 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 313 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 314 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 315 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 316 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 317 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 318 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 319 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 320 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 321 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 322 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {SECT 0 {PARA 3 "" 0 "" {TEXT 258 14 "Ma 416 Exam 2" }} {EXCHG {PARA 286 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 " 1. a) Write down the dual of the linear programming problem" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 " m aximize " }{XPPEDIT 18 0 "z=3x[1]+2*x[2]" "/%\"zG,&*&\"\"$\"\"\"&%\"x G6#\"\"\"F'F'*&\"\"#F'&F)6#\"\"#F'F'" }{TEXT -1 22 " \n subject to " }{XPPEDIT 18 0 "x[1]+x[2]<=3" "1,&&%\"xG6#\"\"\"\"\"\"&F%6#\"\" #F(\"\"$" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "2*x[1] +x[2]<=5" "1,&*&\" \"#\"\"\"&%\"xG6#\"\"\"F&F&&F(6#\"\"#F&\"\"&" }{TEXT -1 2 ", " } {XPPEDIT 18 0 "x[1]>=0,x[2]>=0" "6$1\"\"!&%\"xG6#\"\"\"1F$&F&6#\"\"#" }}}{EXCHG {PARA 301 "" 0 "" {TEXT -1 0 "" }}{PARA 301 "" 0 "" {TEXT -1 10 "minimize " }{XPPEDIT 18 0 "3*y1+5*y2" ",&*&\"\"$\"\"\"%#y1GF%F %*&\"\"&F%%#y2GF%F%" }}{PARA 302 "" 0 "" {TEXT -1 11 "subject to " } {XPPEDIT 18 0 "y1+2*y2>=3" "1\"\"$,&%#y1G\"\"\"*&\"\"#F&%#y2GF&F&" } {TEXT -1 2 ", " }{XPPEDIT 18 0 "y1+y2>=5" "1\"\"&,&%#y1G\"\"\"%#y2GF& " }{TEXT -1 2 ", " }{XPPEDIT 18 0 "y1>=0" "1\"\"!%#y1G" }{TEXT -1 2 ", " }{XPPEDIT 18 0 " y2>=0" "1\"\"!%#y2G" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 234 "b) In general, what does the duality theorem say about the optimu m feasible solutions of the primal problem and its dual? In particu lar, what can you conclude about the optimum feasible solution of the \+ dual in a) using the solution" }}{PARA 0 "" 0 "" {TEXT -1 17 "given in 2 below." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 292 "" 0 "" {TEXT -1 152 "The duality theorem says that if the primal problem has an opt imum feasible solution, then so does the dual problem and in fact, the shadow costs of the" }}{PARA 293 "" 0 "" {TEXT -1 78 "constraints in \+ the final tableau give an optimum feasible solution to the dual" }} {PARA 294 "" 0 "" {TEXT -1 73 "problem, and the optimum value of the o bjectives are equal. The duality " }}{PARA 295 "" 0 "" {TEXT -1 73 "t heorem also says that if the primal problem has an unbounded objectiv e," }}{PARA 296 "" 0 "" {TEXT -1 40 "then the dual has no feasible sol utions." }}{PARA 297 "" 0 "" {TEXT -1 0 "" }}{PARA 298 "" 0 "" {TEXT -1 79 "In particular, looking at the final tableau of the primal pro blem given below" }}{PARA 299 "" 0 "" {TEXT -1 75 "we see that the so lution to the dual problem is y1=1, y2=1, with a minimum" }}{PARA 300 "" 0 "" {TEXT -1 29 "objective value of by* = 8." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 128 "2. When the maximizat ion problem in #1 is solved with the simplex method, the initial and final tableaux look like this: " }}{PARA 0 "" 0 "" {TEXT -1 56 "Ini tial: Final:" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "MATRIX([[1, -3, -2, 0, 0, 0], [0, 1, 1, 1, 0, 3], [0 , 2, 1, 0, 1, 5]])" "-%'MATRIXG6#7%7(\"\"\",$\"\"$!\"\",$\"\"#F*\"\"!F -F-7(F-\"\"\"\"\"\"\"\"\"F-\"\"$7(F-\"\"#\"\"\"F-\"\"\"\"\"&" } {MPLTEXT 1 0 6 " " }{XPPEDIT 18 0 "MATRIX([[1, 0, 0, 1, 1, 8], [0 , 0, 1, 2, -1, 1], [0, 1, 0, -1, 1, 2]])" "-%'MATRIXG6#7%7(\"\"\"\"\"! F(\"\"\"\"\"\"\"\")7(F(F(\"\"\"\"\"#,$\"\"\"!\"\"\"\"\"7(F(\"\"\"F(,$ \"\"\"F1\"\"\"\"\"#" }}{PARA 291 "" 1 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "a) Explain the significance of the submatrix of the final tableau consisting of columns 1, 4 and 5." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 303 "" 0 "" {TEXT -1 327 "This matrix contain a \+ complete record of the iterations of the simplex algorithm performed o n the initial tableau, so that if we multiply this matrix times the in itial tableau, we get the final tableau. This makes it easier to carr y out sensitivity analysis on the parameters of the problem and also d o parametric programming." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 173 "b) Explain briefly how to use these tableau to carry out sensitivity analysis on on the problem. Illustrate by doi ng the sensitivity analysis of the coefficient of " }{XPPEDIT 18 0 "x[1]" "&%\"xG6#\"\"\"" }{TEXT -1 27 " in the objective function." } }{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "i nit:=matrix([[1, -3, -2, 0, 0, 0], [0, 1, 1, 1, 0, 3], [0, 2, 1, 0, 1, 5]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%initG-%'MATRIXG6#7%7(\"\" \"!\"$!\"#\"\"!F-F-7(F-F*F*F*F-\"\"$7(F-\"\"#F*F-F*\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "fin:=matrix([[1, 0, 0, 1, 1, 8], [0 , 0, 1, 2, -1, 1], [0, 1, 0, -1, 1, 2]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$finG-%'MATRIXG6#7%7(\"\"\"\"\"!F+F*F*\"\")7(F+F+F*\" \"#!\"\"F*7(F+F*F+F/F*F." }}}{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 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "ga :=submatrix(fin,[1,2,3],[1,4,5]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gaG-%'MATRIXG6#7%7%\"\"\"F*F*7%\"\" !\"\"#!\"\"7%F,F.F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "init [1,2]:=-(3+theta):init[1,3]:=-2:evalm(init);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7(\"\"\",&!\"$F(%&thetaG!\"\"!\"#\"\"!F.F .7(F.F(F(F(F.\"\"$7(F.\"\"#F(F.F(\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "evalm(ga&*init);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#- %'MATRIXG6#7%7(\"\"\",$%&thetaG!\"\"\"\"!F(F(\"\")7(F,F,F(\"\"#F+F(7(F ,F(F,F+F(F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "m:=evalm(mat rix(3,3,[1,0,theta,0,1,0,0,0,1]));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"mG-%'MATRIXG6#7%7%\"\"\"\"\"!%&thetaG7%F+F*F+7%F+F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalm(m&*ga&*init);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7(\"\"\"\"\"!F),&F(F(%&thetaG!\"\",& F(F(F+F(,&\"\")F(F+\"\"#7(F)F)F(F0F,F(7(F)F(F)F,F(F0" }}}{EXCHG {PARA 311 "" 0 "" {TEXT -1 15 "By inspection, " }{XPPEDIT 18 0 "theta" "I&th etaG6\"" }{TEXT -1 58 " can range from -1 to 1 before the optimum corn er changes," }}{PARA 312 "" 0 "" {TEXT -1 22 "so the coefficient of " }{XPPEDIT 18 0 "x[1]" "&%\"xG6#\"\"\"" }{TEXT -1 20 " ranges from 2 to 4." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "3. Consider the linear programming problem with parameter " } {XPPEDIT 18 0 "theta" "I&thetaG6\"" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 " maximize " } {XPPEDIT 18 0 "z=3x[1]+2*x[2]" "/%\"zG,&*&\"\"$\"\"\"&%\"xG6#\"\"\"F'F '*&\"\"#F'&F)6#\"\"#F'F'" }{TEXT -1 22 " \n subject to " } {XPPEDIT 18 0 "x[1]+x[2]<=theta" "1,&&%\"xG6#\"\"\"\"\"\"&F%6#\"\"#F(% &thetaG" }{TEXT -1 3 ", " }{XPPEDIT 18 0 "2*x[1] +x[2]<=5" "1,&*&\"\" #\"\"\"&%\"xG6#\"\"\"F&F&&F(6#\"\"#F&\"\"&" }{TEXT -1 4 ", " } {XPPEDIT 18 0 "x[1]>=0,x[2]>=0" "6$1\"\"!&%\"xG6#\"\"\"1F$&F&6#\"\"#" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "(Note t hat the problem has been solved when " }{XPPEDIT 18 0 "theta=3" "/%&t hetaG\"\"$" }{TEXT -1 14 ", in 2 above)" }}{PARA 0 "" 0 "" {TEXT -1 6 " Let " }{XPPEDIT 18 0 "z(theta)" "-%\"zG6#%&thetaG" }{TEXT -1 73 " be the optimum value of the problem. Make a sketch of the graph \+ of " }{XPPEDIT 18 0 "z(theta)" "-%\"zG6#%&thetaG" }{TEXT -1 4 ". " } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "init[1,2]:=-3:init[2,6]:=theta:evalm(init);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7(\"\"\"!\"$!\"#\"\"!F+F+7(F+F(F(F(F+%&th etaG7(F+\"\"#F(F+F(\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "l :=evalm(ga&*init);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"lG-%'MATR IXG6#7%7(\"\"\"\"\"!F+F*F*,&\"\"&F*%&thetaGF*7(F+F+F*\"\"#!\"\",&!\"&F *F.F07(F+F*F+F1F*,&F-F*F.F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 313 "" 0 "" {TEXT -1 27 "By inspection, we see th at " }{XPPEDIT 18 0 "z(theta)=5+theta" "/-%\"zG6#%&thetaG,&\"\"&\"\"\" F&F)" }{TEXT -1 30 ", for theta between 5/2 and 5." }}{PARA 314 "" 0 " " {TEXT -1 68 "At 5/2, we bring the 5th column into solution and take \+ out the 3rd. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "m := gauss (col(l,5),2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG-%'MATRIXG6#7%7 %\"\"\"F*\"\"!7%F+!\"\"F+7%F+F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "evalm(m&*l);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MA TRIXG6#7%7(\"\"\"\"\"!F(\"\"$F),$%&thetaGF*7(F)F)!\"\"!\"#F(,&\"\"&F(F ,F/7(F)F(F(F(F)F," }}}{EXCHG {PARA 315 "" 0 "" {TEXT -1 20 "From 5/2 d own to 0, " }{XPPEDIT 18 0 "z(theta) = 3*theta" "/-%\"zG6#%&thetaG*&\" \"$\"\"\"F&F)" }{TEXT -1 1 "." }}{PARA 316 "" 0 "" {TEXT -1 0 "" }} {PARA 317 "" 0 "" {TEXT -1 76 "Going up from 5, we bring the 4th colum n into solution and take out the 2nd." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "evalm(gauss(col(l,4),3)&*l);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7(\"\"\"F(\"\"!F)\"\"#\"#57(F)F*F(F)F(\" \"&7(F)!\"\"F)F(F/,&!\"&F(%&thetaGF(" }}}{EXCHG {PARA 318 "" 0 "" {TEXT -1 29 "So , for theta from 5 on up, " }{XPPEDIT 18 0 "z(theta)=1 0" "/-%\"zG6#%&thetaG\"#5" }{TEXT -1 13 " is constant." }{MPLTEXT 1 0 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "plot([[0,0],[5/2,15 /2],[5,10],[10,10]]);" }}{PARA 13 "" 1 "" {INLPLOT "6#-%'CURVESG6$7&7$ \"\"!F(7$$\"I+++++++++++++++++++D!#R$\"I+++++++++++++++++++vF,7$$\"\"& F($\"#5F(7$F2F2-%'COLOURG6&%$RGBG$F3!\"\"F(F(" 2 346 157 157 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20030 0 12020 0 0 0 0 0 0 0 1 1 0 0 0 179 157 0 0 0 0 0 0 }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 297 " 4. A fleet of 15 ships is distributed in three ports: 5 shi ps in each of port A, B, and C. These ships need to be sent to pick \+ up stuff at four different ports: 1 ship needed at port D, 4 at port E , 4 at port F, and 6 at port G. The table of travel costs from port \+ X to port Y is given by " }{XPPEDIT 18 0 "MATRIX([[` `, D, E, F, G], \+ [A, 5, 4, 3, 2], [B, 10, 8, 4, 7], [C, 9, 9, 8, 4]]) " "-%'MATRIXG6# 7&7'%\"~G%\"DG%\"EG%\"FG%\"GG7'%\"AG\"\"&\"\"%\"\"$\"\"#7'%\"BG\"#5\" \")\"\"%\"\"(7'%\"CG\"\"*\"\"*\"\")\"\"%" }{TEXT -1 84 ". The prob lem is to decide on a shipping schedule which minimizes total cost. \+ " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 229 "a) \+ Set this problem up as a linear programming problem: Give names to t he decision variables and write down the objective function and constr aints. ( You don't have to write them all down, just say what they are and how many.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 319 "" 0 "" {TEXT -1 5 "Let " }{XPPEDIT 18 0 "x[XY]" "&%\"xG6#%#XYG" }{TEXT -1 59 " denote the number of ships we decide to move from X to Y." }} {PARA 320 "" 0 "" {TEXT -1 33 "Then we want to mimimize the cost" }} {PARA 321 "" 0 "" {XPPEDIT 18 0 "5*x[AD] + 4*x[AE]" ",&*&\"\"&\"\"\"&% \"xG6#%#ADGF%F%*&\"\"%F%&F'6#%#AEGF%F%" }{TEXT -1 11 " + ... + " } {XPPEDIT 18 0 "x[CF]+x[CG]" ",&&%\"xG6#%#CFG\"\"\"&F$6#%#CGGF'" } {TEXT -1 41 " subject to the three supply constraints" }}{PARA 322 " " 0 "" {XPPEDIT 18 0 "x[AB]+x[AE]+x[AF]+x[AG]=5" "/,*&%\"xG6#%#ABG\"\" \"&F%6#%#AEGF(&F%6#%#AFGF(&F%6#%#AGGF(\"\"&" }{TEXT -1 33 ", .., and 4 demand constraints \n" }{XPPEDIT 18 0 "x[AD]+x[BD]+x[CD]=1" "/,(&%\" xG6#%#ADG\"\"\"&F%6#%#BDGF(&F%6#%#CDGF(\"\"\"" }{TEXT -1 6 ", ...." } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 79 "b) Starting with the feasible solution you get fr om the northwest corner rule," }{XPPEDIT 18 0 "MATRIX([[1, 4, 0, 0], [ 0, 0, 4, 1], [0, 0, 0, 5]])" "-%'MATRIXG6#7%7&\"\"\"\"\"%\"\"!F)7&F)F) \"\"%\"\"\"7&F)F)F)\"\"&" }{TEXT -1 59 " , and the reduced cost table for the nonbasic variables, " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {XPPEDIT 18 0 "MATRIX([[b, b, b, -4], [4, 3, b, b], [6 , 7, 7, b]])" "-%'MATRIXG6#7%7&%\"bGF'F',$\"\"%!\"\"7&\"\"%\"\"$F'F'7& \"\"'\"\"(\"\"(F'" }{TEXT -1 134 ", where 'b' stands for 'basic varia ble', perform one iteration of the transportation simplex algorithm. \+ Is this a wasted iteration?" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }} {PARA 304 "" 0 "" {TEXT -1 83 "The reduced cost table tells us to brin g the upper right hand corner into solution." }}{PARA 305 "" 0 "" {TEXT -1 78 "Doing this creates a 2 by 2 cycle in the solution which w e break by taking out" }}{PARA 306 "" 0 "" {TEXT -1 88 "the top of the 3rd column. This is a wasted iteration, since no allocation is chan ged." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "5 . Take home: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 61 "a) Complete the solution of the transportation problem i n 4)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "cost:=matrix( [[ 5, 4, 3, 2], [ 10, 8, 4, 7], [ 9, 9, 8, 4]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%costG-%'MATRIXG6#7% 7&\"\"&\"\"%\"\"$\"\"#7&\"#5\"\")F+\"\"(7&\"\"*F3F0F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "fasttransport2(cost,[5,5,5],[1,4,4, 6],prt);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7&\"\"\"\"\" %\"\"!F*7&F*F*F)F(7&F*F*F*\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%.r educed~costsG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7&%\"bG F(F(!\"%7&\"\"%\"\"$F(F(7&\"\"'\"\"(F/F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%+iteration~G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIX G6#7%7&\"\"\"F(%\"yG%\"eG7&\"\"!F,F)F)7&F,F,F,F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7&\"\"\"\"\"%\"\"!F*7&F*F*F)F(7&F*F*F*\" \"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%.reduced~costsG" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7&%\"bGF(\"\"%F(7&\"\"!!\"\"F(F(7& \"\"#\"\"$\"\"(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%+iteration~G\"\" #" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7&\"\"\"%\"yG\"\"!F )7&F*%\"eGF(F)7&F*F*F*F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG 6#7%7&\"\"\"\"\"$\"\"!F(7&F*F(\"\"%F*7&F*F*F*\"\"&" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%.reduced~costsG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#- %'MATRIXG6#7%7&%\"bGF(\"\"$F(7&\"\"\"F(F(F+7&\"\"#F)\"\"'F(" }}} {EXCHG {PARA 307 "" 0 "" {TEXT -1 73 "The minimal cost is 63 with the \+ shipping schedule send 1 ship from A to D" }}{PARA 308 "" 0 "" {TEXT -1 77 "3 from A to E and 1 from A to G, 1 from B to E and 4 from B to F, and 5 from" }}{PARA 309 "" 0 "" {TEXT -1 7 "C to G." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 "b) Consi der the transportation problem in 4) with travel costs" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "MATRIX([[` `, D, E, F, G], [A, 5, 4, 3, 2], [B, th eta, 8, 4, 7], [C, 9, 9, 8, 4]])" "-%'MATRIXG6#7&7'%\"~G%\"DG%\"EG%\"F G%\"GG7'%\"AG\"\"&\"\"%\"\"$\"\"#7'%\"BG%&thetaG\"\")\"\"%\"\"(7'%\"CG \"\"*\"\"*\"\")\"\"%" }{TEXT -1 9 " . Let " }{XPPEDIT 18 0 "z(theta) " "-%\"zG6#%&thetaG" }{TEXT -1 56 " denote the optimum travel cost. \+ Sketch the graph of " }{XPPEDIT 18 0 "z(theta)" "-%\"zG6#%&thetaG" } {TEXT -1 5 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 18 "cost[2,1]:=theta: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "seq(slowtransport(subs(theta=i,op(cost)),[5,5,5] ,[1,4,4,6]),i=0..10);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6-7$\"#a-%'MATR IXG6#7%7&\"\"!\"\"%F*\"\"\"7&F,F*F+F*7&F*F*F*\"\"&7$\"#bF%7$\"#cF%7$\" #dF%7$\"#eF%7$\"#fF%7$\"#gF%7$\"#hF%7$\"#iF%7$\"#j-F&6#7%7&F,\"\"$F*F, 7&F*F,F+F*F.F@" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 256 27 "By inspection, we see that " }{XPPEDIT 18 0 "z(theta)=54+theta" "/-%\"zG6#%&thetaG,& \"#a\"\"\"F&F)" }{TEXT -1 2 ", " }{TEXT 257 26 "as theta goes from 0 t o 9." }}{PARA 310 "" 0 "" {TEXT -1 14 "From there on " }{XPPEDIT 18 0 "z(theta) = 63" "/-%\"zG6#%&thetaG\"#j" }{TEXT -1 57 ", since that shi pment will never come back into solution." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 30 "plot([[0,54],[9,63],[15,63]]);" }}{PARA 13 "" 1 "" {INLPLOT "6#-%'CURVESG6$7%7$\"\"!$\"#aF(7$$\"\"*F($\"#jF(7$$\"#:F(F.-% 'COLOURG6&%$RGBG$\"#5!\"\"F(F(" 2 254 252 252 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 10030 10061 10056 10074 0 0 0 20030 0 12020 0 0 0 0 0 0 0 1 1 0 0 0 204 213 0 0 0 0 0 0 }}}}{EXCHG {PARA 0 " " 0 "" {HYPERLNK 17 "Table of contents" 1 "ma416s97.mws" "" }{TEXT -1 0 "" }}}}{MARK "1 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }