/ Class of 2001 / ClassOf2001.iso / Scinotebook / scinoteb / help / dm12-5.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 25 20 54 68 69 73 20 | 64 6f 63 75 6d 65 6e 74 |%% This |document|
|00000010| 20 63 72 65 61 74 65 64 | 20 62 79 20 53 63 69 65 | created| by Scie|
|00000020| 6e 74 69 66 69 63 20 4e | 6f 74 65 62 6f 6f 6b 20 |ntific N|otebook |
|00000030| 28 52 29 20 56 65 72 73 | 69 6f 6e 20 33 2e 30 0d |(R) Vers|ion 3.0.|
|00000040| 0a 0d 0a 0d 0a 5c 64 6f | 63 75 6d 65 6e 74 63 6c |.....\do|cumentcl|
|00000050| 61 73 73 5b 31 32 70 74 | 2c 74 68 6d 73 61 5d 7b |ass[12pt|,thmsa]{|
|00000060| 61 72 74 69 63 6c 65 7d | 0d 0a 5c 75 73 65 70 61 |article}|..\usepa|
|00000070| 63 6b 61 67 65 7b 61 6d | 73 73 79 6d 62 7d 0d 0a |ckage{am|ssymb}..|
|00000080| 0d 0a 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |..%%%%%%|%%%%%%%%|
|00000090| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000a0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000b0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000c0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000d0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000e0| 25 25 25 25 25 25 0d 0a | 5c 75 73 65 70 61 63 6b |%%%%%%..|\usepack|
|000000f0| 61 67 65 7b 6d 61 6b 65 | 69 64 78 7d 0d 0a 5c 75 |age{make|idx}..\u|
|00000100| 73 65 70 61 63 6b 61 67 | 65 7b 73 77 32 30 6a 61 |sepackag|e{sw20ja|
|00000110| 72 74 7d 0d 0a 0d 0a 25 | 54 43 49 44 41 54 41 7b |rt}....%|TCIDATA{|
|00000120| 54 43 49 73 74 79 6c 65 | 3d 61 72 74 69 63 6c 65 |TCIstyle|=article|
|00000130| 2f 61 72 74 34 2e 6c 61 | 74 2c 6a 61 72 74 2c 73 |/art4.la|t,jart,s|
|00000140| 77 32 30 6a 61 72 74 7d | 0d 0a 0d 0a 25 54 43 49 |w20jart}|....%TCI|
|00000150| 44 41 54 41 7b 3c 4d 45 | 54 41 20 4e 41 4d 45 3d |DATA{<ME|TA NAME=|
|00000160| 22 56 69 65 77 53 65 74 | 74 69 6e 67 73 22 20 43 |"ViewSet|tings" C|
|00000170| 4f 4e 54 45 4e 54 3d 22 | 33 31 22 3e 7d 0d 0a 25 |ONTENT="|31">}..%|
|00000180| 54 43 49 44 41 54 41 7b | 3c 4d 45 54 41 20 4e 41 |TCIDATA{|<META NA|
|00000190| 4d 45 3d 22 47 72 61 70 | 68 69 63 73 53 61 76 65 |ME="Grap|hicsSave|
|000001a0| 22 20 43 4f 4e 54 45 4e | 54 3d 22 33 32 22 3e 7d |" CONTEN|T="32">}|
|000001b0| 0d 0a 25 54 43 49 44 41 | 54 41 7b 3c 4d 45 54 41 |..%TCIDA|TA{<META|
|000001c0| 20 4e 41 4d 45 3d 22 54 | 69 74 6c 65 22 20 43 4f | NAME="T|itle" CO|
|000001d0| 4e 54 45 4e 54 3d 22 4c | 69 6e 65 61 72 20 50 72 |NTENT="L|inear Pr|
|000001e0| 6f 67 72 61 6d 6d 69 6e | 67 22 3e 7d 0d 0a 25 54 |ogrammin|g">}..%T|
|000001f0| 43 49 44 41 54 41 7b 43 | 72 65 61 74 65 64 3d 4d |CIDATA{C|reated=M|
|00000200| 6f 6e 20 41 75 67 20 31 | 39 20 31 34 3a 35 32 3a |on Aug 1|9 14:52:|
|00000210| 32 34 20 31 39 39 36 7d | 0d 0a 25 54 43 49 44 41 |24 1996}|..%TCIDA|
|00000220| 54 41 7b 4c 61 73 74 52 | 65 76 69 73 65 64 3d 4d |TA{LastR|evised=M|
|00000230| 6f 6e 20 4d 61 72 20 33 | 31 20 31 31 3a 32 36 3a |on Mar 3|1 11:26:|
|00000240| 31 33 20 31 39 39 37 7d | 0d 0a 25 54 43 49 44 41 |13 1997}|..%TCIDA|
|00000250| 54 41 7b 4c 61 6e 67 75 | 61 67 65 3d 41 6d 65 72 |TA{Langu|age=Amer|
|00000260| 69 63 61 6e 20 45 6e 67 | 6c 69 73 68 7d 0d 0a 25 |ican Eng|lish}..%|
|00000270| 54 43 49 44 41 54 41 7b | 43 53 54 46 69 6c 65 3d |TCIDATA{|CSTFile=|
|00000280| 4d 61 74 68 48 65 6c 70 | 2e 63 73 74 7d 0d 0a 25 |MathHelp|.cst}..%|
|00000290| 54 43 49 44 41 54 41 7b | 3c 4c 49 4e 4b 20 52 45 |TCIDATA{|<LINK RE|
|000002a0| 4c 3d 22 62 65 67 69 6e | 22 20 48 52 45 46 3d 22 |L="begin|" HREF="|
|000002b0| 44 4d 31 32 2d 31 2e 74 | 65 78 22 3e 7d 0d 0a 25 |DM12-1.t|ex">}..%|
|000002c0| 54 43 49 44 41 54 41 7b | 3c 4c 49 4e 4b 20 52 45 |TCIDATA{|<LINK RE|
|000002d0| 4c 3d 22 63 6f 6e 74 65 | 6e 74 73 22 20 48 52 45 |L="conte|nts" HRE|
|000002e0| 46 3d 22 44 4d 30 2d 30 | 2e 74 65 78 22 3e 7d 0d |F="DM0-0|.tex">}.|
|000002f0| 0a 25 54 43 49 44 41 54 | 41 7b 3c 4c 49 4e 4b 20 |.%TCIDAT|A{<LINK |
|00000300| 52 45 4c 3d 22 65 6e 64 | 22 20 48 52 45 46 3d 22 |REL="end|" HREF="|
|00000310| 44 4d 31 32 2d 36 2e 74 | 65 78 22 3e 7d 0d 0a 25 |DM12-6.t|ex">}..%|
|00000320| 54 43 49 44 41 54 41 7b | 3c 4c 49 4e 4b 20 52 45 |TCIDATA{|<LINK RE|
|00000330| 4c 3d 22 6e 65 78 74 22 | 20 48 52 45 46 3d 22 44 |L="next"| HREF="D|
|00000340| 4d 31 32 2d 36 2e 74 65 | 78 22 3e 7d 0d 0a 25 54 |M12-6.te|x">}..%T|
|00000350| 43 49 44 41 54 41 7b 3c | 4c 49 4e 4b 20 52 45 4c |CIDATA{<|LINK REL|
|00000360| 3d 22 70 61 72 65 6e 74 | 22 20 48 52 45 46 3d 22 |="parent|" HREF="|
|00000370| 44 4d 31 32 2e 74 65 78 | 22 3e 7d 0d 0a 25 54 43 |DM12.tex|">}..%TC|
|00000380| 49 44 41 54 41 7b 3c 4c | 49 4e 4b 20 52 45 4c 3d |IDATA{<L|INK REL=|
|00000390| 22 70 72 65 76 69 6f 75 | 73 22 20 48 52 45 46 3d |"previou|s" HREF=|
|000003a0| 22 44 4d 31 32 2d 34 2e | 74 65 78 22 3e 7d 0d 0a |"DM12-4.|tex">}..|
|000003b0| 25 54 43 49 44 41 54 41 | 7b 3c 4c 49 4e 4b 20 52 |%TCIDATA|{<LINK R|
|000003c0| 45 4c 3d 22 74 6f 70 22 | 20 48 52 45 46 3d 22 44 |EL="top"| HREF="D|
|000003d0| 4d 30 2d 30 2e 74 65 78 | 22 3e 7d 0d 0a 0d 0a 5c |M0-0.tex|">}....\|
|000003e0| 69 6e 70 75 74 7b 74 63 | 69 6c 61 74 65 78 7d 0d |input{tc|ilatex}.|
|000003f0| 0a 5c 62 65 67 69 6e 7b | 64 6f 63 75 6d 65 6e 74 |.\begin{|document|
|00000400| 7d 0d 0a 0d 0a 0d 0a 5c | 73 65 63 74 69 6f 6e 7b |}......\|section{|
|00000410| 5c 6c 61 62 65 6c 7b 4c | 69 6e 65 61 72 20 70 72 |\label{L|inear pr|
|00000420| 6f 67 72 61 6d 6d 69 6e | 67 7d 4c 69 6e 65 61 72 |ogrammin|g}Linear|
|00000430| 20 50 72 6f 67 72 61 6d | 6d 69 6e 67 5c 6c 61 62 | Program|ming\lab|
|00000440| 65 6c 7b 43 6f 6e 73 74 | 72 61 69 6e 74 73 7d 7d |el{Const|raints}}|
|00000450| 0d 0a 0d 0a 41 20 0d 0a | 5c 69 6e 64 65 78 7b 4c |....A ..|\index{L|
|00000460| 69 6e 65 61 72 20 70 72 | 6f 67 72 61 6d 6d 69 6e |inear pr|ogrammin|
|00000470| 67 40 4c 69 6e 65 61 72 | 20 70 72 6f 67 72 61 6d |g@Linear| program|
|00000480| 6d 69 6e 67 7d 5c 74 65 | 78 74 73 6c 7b 6c 69 6e |ming}\te|xtsl{lin|
|00000490| 65 61 72 20 70 72 6f 67 | 72 61 6d 6d 69 6e 67 0d |ear prog|ramming.|
|000004a0| 0a 70 72 6f 62 6c 65 6d | 7d 20 63 6f 6e 73 69 73 |.problem|} consis|
|000004b0| 74 73 20 6f 66 20 6d 69 | 6e 69 6d 69 7a 69 6e 67 |ts of mi|nimizing|
|000004c0| 20 28 6f 72 20 6d 61 78 | 69 6d 69 7a 69 6e 67 29 | (or max|imizing)|
|000004d0| 20 61 20 6c 69 6e 65 61 | 72 20 66 75 6e 63 74 69 | a linea|r functi|
|000004e0| 6f 6e 20 73 75 62 6a 65 | 63 74 20 74 6f 0d 0a 63 |on subje|ct to..c|
|000004f0| 65 72 74 61 69 6e 20 63 | 6f 6e 64 69 74 69 6f 6e |ertain c|ondition|
|00000500| 73 20 6f 72 20 0d 0a 5c | 69 6e 64 65 78 7b 43 6f |s or ..\|index{Co|
|00000510| 6e 73 74 72 61 69 6e 74 | 73 40 43 6f 6e 73 74 72 |nstraint|s@Constr|
|00000520| 61 69 6e 74 73 7d 63 6f | 6e 73 74 72 61 69 6e 74 |aints}co|nstraint|
|00000530| 73 20 65 78 70 72 65 73 | 73 69 62 6c 65 20 61 73 |s expres|sible as|
|00000540| 20 6c 69 6e 65 61 72 0d | 0a 69 6e 65 71 75 61 6c | linear.|.inequal|
|00000550| 69 74 69 65 73 2e 0d 0a | 0d 0a 5c 73 75 62 73 65 |ities...|..\subse|
|00000560| 63 74 69 6f 6e 7b 5c 20 | 5c 6c 61 62 65 6c 7b 53 |ction{\ |\label{S|
|00000570| 69 6d 70 6c 65 78 20 61 | 6c 67 6f 72 69 74 68 6d |implex a|lgorithm|
|00000580| 7d 54 68 65 20 53 69 6d | 70 6c 65 78 20 41 6c 67 |}The Sim|plex Alg|
|00000590| 6f 72 69 74 68 6d 7d 0d | 0a 0d 0a 54 68 65 20 62 |orithm}.|...The b|
|000005a0| 61 73 69 63 20 70 75 72 | 70 6f 73 65 20 6f 66 20 |asic pur|pose of |
|000005b0| 74 68 65 20 73 69 6d 70 | 6c 65 78 20 61 6c 67 6f |the simp|lex algo|
|000005c0| 72 69 74 68 6d 20 69 73 | 20 74 6f 20 73 6f 6c 76 |rithm is| to solv|
|000005d0| 65 20 6c 69 6e 65 61 72 | 20 70 72 6f 67 72 61 6d |e linear| program|
|000005e0| 6d 69 6e 67 0d 0a 70 72 | 6f 62 6c 65 6d 73 2e 20 |ming..pr|oblems. |
|000005f0| 49 6e 20 74 68 65 20 66 | 6f 6c 6c 6f 77 69 6e 67 |In the f|ollowing|
|00000600| 20 65 78 61 6d 70 6c 65 | 2c 20 74 68 65 20 66 75 | example|, the fu|
|00000610| 6e 63 74 69 6f 6e 20 24 | 66 28 78 2c 79 29 3d 78 |nction $|f(x,y)=x|
|00000620| 2b 79 24 20 69 73 20 74 | 6f 20 62 65 0d 0a 6d 61 |+y$ is t|o be..ma|
|00000630| 78 69 6d 69 7a 65 64 20 | 73 75 62 6a 65 63 74 20 |ximized |subject |
|00000640| 74 6f 20 74 68 65 20 74 | 77 6f 20 69 6e 65 71 75 |to the t|wo inequ|
|00000650| 61 6c 69 74 69 65 73 20 | 73 68 6f 77 6e 2e 20 54 |alities |shown. T|
|00000660| 68 65 20 66 75 6e 63 74 | 69 6f 6e 20 24 66 28 78 |he funct|ion $f(x|
|00000670| 2c 79 29 24 20 69 73 0d | 0a 74 68 65 20 0d 0a 5c |,y)$ is.|.the ..\|
|00000680| 69 6e 64 65 78 7b 4f 62 | 6a 65 63 74 69 76 65 20 |index{Ob|jective |
|00000690| 66 75 6e 63 74 69 6f 6e | 40 4f 62 6a 65 63 74 69 |function|@Objecti|
|000006a0| 76 65 20 66 75 6e 63 74 | 69 6f 6e 7d 5c 6c 61 62 |ve funct|ion}\lab|
|000006b0| 65 6c 7b 4f 62 6a 65 63 | 74 69 76 65 20 66 75 6e |el{Objec|tive fun|
|000006c0| 63 74 69 6f 6e 7d 25 0d | 0a 5c 74 65 78 74 73 6c |ction}%.|.\textsl|
|000006d0| 7b 6f 62 6a 65 63 74 69 | 76 65 20 66 75 6e 63 74 |{objecti|ve funct|
|000006e0| 69 6f 6e 7d 2c 20 61 6e | 64 20 74 68 65 20 73 65 |ion}, an|d the se|
|000006f0| 74 20 6f 66 20 6c 69 6e | 65 61 72 20 63 6f 6e 73 |t of lin|ear cons|
|00000700| 74 72 61 69 6e 74 73 20 | 69 73 20 63 61 6c 6c 65 |traints |is calle|
|00000710| 64 20 74 68 65 20 0d 0a | 5c 74 65 78 74 73 6c 7b |d the ..|\textsl{|
|00000720| 6c 69 6e 65 61 72 20 73 | 79 73 74 65 6d 7d 2e 5c |linear s|ystem}.\|
|00000730| 6d 65 64 73 6b 69 70 0d | 0a 0d 0a 5c 62 65 67 69 |medskip.|...\begi|
|00000740| 6e 7b 71 75 6f 74 65 7d | 0d 0a 24 5c 62 6c 61 63 |n{quote}|..$\blac|
|00000750| 6b 74 72 69 61 6e 67 6c | 65 72 69 67 68 74 20 24 |ktriangl|eright $|
|00000760| 20 5c 6c 61 62 65 6c 7b | 53 69 6d 70 6c 65 78 2c | \label{|Simplex,|
|00000770| 20 6d 61 78 69 6d 69 7a | 65 7d 54 6f 20 65 6e 74 | maximiz|e}To ent|
|00000780| 65 72 20 61 20 6c 69 6e | 65 61 72 0d 0a 70 72 6f |er a lin|ear..pro|
|00000790| 67 72 61 6d 6d 69 6e 67 | 20 70 72 6f 62 6c 65 6d |gramming| problem|
|000007a0| 20 77 69 74 68 20 74 77 | 6f 20 63 6f 6e 73 74 72 | with tw|o constr|
|000007b0| 61 69 6e 74 73 0d 0a 5c | 65 6e 64 7b 71 75 6f 74 |aints..\|end{quot|
|000007c0| 65 7d 0d 0a 0d 0a 5c 62 | 65 67 69 6e 7b 69 74 65 |e}....\b|egin{ite|
|000007d0| 6d 69 7a 65 7d 0d 0a 5c | 69 74 65 6d 20 20 43 72 |mize}..\|item  Cr|
|000007e0| 65 61 74 65 20 61 20 24 | 33 5c 74 69 6d 65 73 20 |eate a $|3\times |
|000007f0| 31 24 20 6d 61 74 72 69 | 78 2e 0d 0a 0d 0a 5c 69 |1$ matri|x.....\i|
|00000800| 74 65 6d 20 20 54 79 70 | 65 20 74 68 65 20 66 75 |tem  Typ|e the fu|
|00000810| 6e 63 74 69 6f 6e 20 74 | 6f 20 62 65 20 6d 61 78 |nction t|o be max|
|00000820| 69 6d 69 7a 65 64 20 69 | 6e 20 74 68 65 20 66 69 |imized i|n the fi|
|00000830| 72 73 74 20 72 6f 77 2e | 0d 0a 0d 0a 5c 69 74 65 |rst row.|....\ite|
|00000840| 6d 20 20 54 79 70 65 20 | 74 68 65 20 6c 69 6e 65 |m  Type |the line|
|00000850| 61 72 20 63 6f 6e 73 74 | 72 61 69 6e 74 73 20 69 |ar const|raints i|
|00000860| 6e 20 74 68 65 20 73 75 | 62 73 65 71 75 65 6e 74 |n the su|bsequent|
|00000870| 20 72 6f 77 73 2e 0d 0a | 0d 0a 5c 69 74 65 6d 20 | rows...|..\item |
|00000880| 20 4c 65 61 76 65 20 74 | 68 65 20 69 6e 73 65 72 | Leave t|he inser|
|00000890| 74 69 6f 6e 20 70 6f 69 | 6e 74 20 69 6e 20 74 68 |tion poi|nt in th|
|000008a0| 65 20 6d 61 74 72 69 78 | 2e 0d 0a 0d 0a 5c 69 74 |e matrix|.....\it|
|000008b0| 65 6d 20 20 46 72 6f 6d | 20 74 68 65 20 0d 0a 5c |em  From| the ..\|
|000008c0| 69 6e 64 65 78 7b 53 69 | 6d 70 6c 65 78 20 6d 65 |index{Si|mplex me|
|000008d0| 74 68 6f 64 40 53 69 6d | 70 6c 65 78 20 6d 65 74 |thod@Sim|plex met|
|000008e0| 68 6f 64 7d 5c 6c 61 62 | 65 6c 7b 53 69 6d 70 6c |hod}\lab|el{Simpl|
|000008f0| 65 78 20 6d 65 74 68 6f | 64 7d 5c 74 65 78 74 73 |ex metho|d}\texts|
|00000900| 66 7b 53 69 6d 70 6c 65 | 78 7d 5c 0d 0a 73 75 62 |f{Simple|x}\..sub|
|00000910| 6d 65 6e 75 2c 20 63 68 | 6f 6f 73 65 5c 74 65 78 |menu, ch|oose\tex|
|00000920| 74 73 66 7b 5c 20 4d 61 | 78 69 6d 69 7a 65 7d 2e |tsf{\ Ma|ximize}.|
|00000930| 5c 6d 65 64 73 6b 69 70 | 20 0d 0a 5c 65 6e 64 7b |\medskip| ..\end{|
|00000940| 69 74 65 6d 69 7a 65 7d | 0d 0a 0d 0a 5c 62 65 67 |itemize}|....\beg|
|00000950| 69 6e 7b 71 75 6f 74 65 | 7d 0d 0a 24 5c 62 6c 61 |in{quote|}..$\bla|
|00000960| 63 6b 74 72 69 61 6e 67 | 6c 65 72 69 67 68 74 20 |cktriang|leright |
|00000970| 24 20 5c 74 65 78 74 73 | 66 7b 53 69 6d 70 6c 65 |$ \texts|f{Simple|
|00000980| 78 20 2b 5c 20 4d 61 78 | 69 6d 69 7a 65 7d 0d 0a |x +\ Max|imize}..|
|00000990| 5c 65 6e 64 7b 71 75 6f | 74 65 7d 0d 0a 0d 0a 5c |\end{quo|te}....\|
|000009a0| 62 65 67 69 6e 7b 71 75 | 6f 74 61 74 69 6f 6e 7d |begin{qu|otation}|
|000009b0| 0d 0a 24 5c 6c 65 66 74 | 5b 20 0d 0a 5c 62 65 67 |..$\left|[ ..\beg|
|000009c0| 69 6e 7b 61 72 72 61 79 | 7d 7b 63 7d 0d 0a 78 2b |in{array|}{c}..x+|
|000009d0| 79 20 5c 5c 20 0d 0a 34 | 78 2b 33 79 5c 6c 65 71 |y \\ ..4|x+3y\leq|
|000009e0| 20 36 20 5c 5c 20 0d 0a | 33 78 2b 34 79 5c 6c 65 | 6 \\ ..|3x+4y\le|
|000009f0| 71 20 34 0d 0a 5c 65 6e | 64 7b 61 72 72 61 79 7d |q 4..\en|d{array}|
|00000a00| 0d 0a 5c 72 69 67 68 74 | 5d 20 24 2c 20 4d 61 78 |..\right|] $, Max|
|00000a10| 69 6d 75 6d 20 69 73 20 | 61 74 3a 20 24 5c 6c 65 |imum is |at: $\le|
|00000a20| 66 74 5c 7b 20 78 3d 25 | 0d 0a 5c 66 72 61 63 7b |ft\{ x=%|..\frac{|
|00000a30| 31 32 7d 7b 37 7d 2c 79 | 3d 2d 5c 66 72 61 63 7b |12}{7},y|=-\frac{|
|00000a40| 32 7d 7b 37 7d 5c 72 69 | 67 68 74 5c 7d 20 5c 6d |2}{7}\ri|ght\} \m|
|00000a50| 65 64 73 6b 69 70 20 24 | 0d 0a 5c 65 6e 64 7b 71 |edskip $|..\end{q|
|00000a60| 75 6f 74 61 74 69 6f 6e | 7d 0d 0a 0d 0a 5c 6c 61 |uotation|}....\la|
|00000a70| 62 65 6c 7b 53 69 6d 70 | 6c 65 78 2c 6d 69 6e 69 |bel{Simp|lex,mini|
|00000a80| 6d 69 7a 65 7d 4f 66 20 | 63 6f 75 72 73 65 2c 20 |mize}Of |course, |
|00000a90| 74 68 65 73 65 20 61 72 | 65 20 74 68 65 20 73 61 |these ar|e the sa|
|00000aa0| 6d 65 20 63 6f 6f 72 64 | 69 6e 61 74 65 73 20 74 |me coord|inates t|
|00000ab0| 68 61 74 0d 0a 6d 69 6e | 69 6d 69 7a 65 20 24 2d |hat..min|imize $-|
|00000ac0| 78 2d 79 24 2e 20 49 6e | 20 74 68 65 20 66 6f 6c |x-y$. In| the fol|
|00000ad0| 6c 6f 77 69 6e 67 20 6c | 69 6e 65 61 72 20 70 72 |lowing l|inear pr|
|00000ae0| 6f 67 72 61 6d 6d 69 6e | 67 20 70 72 6f 62 6c 65 |ogrammin|g proble|
|00000af0| 6d 2c 20 63 6c 69 63 6b | 20 74 68 65 0d 0a 6d 61 |m, click| the..ma|
|00000b00| 74 72 69 78 2c 20 61 6e | 64 20 66 72 6f 6d 20 74 |trix, an|d from t|
|00000b10| 68 65 20 5c 74 65 78 74 | 73 66 7b 53 69 6d 70 6c |he \text|sf{Simpl|
|00000b20| 65 78 7d 5c 20 73 75 62 | 6d 65 6e 75 20 63 68 6f |ex}\ sub|menu cho|
|00000b30| 6f 73 65 5c 74 65 78 74 | 73 66 7b 5c 20 4d 69 6e |ose\text|sf{\ Min|
|00000b40| 69 6d 69 7a 65 7d 25 0d | 0a 2e 5c 6d 65 64 73 6b |imize}%.|..\medsk|
|00000b50| 69 70 0d 0a 0d 0a 5c 62 | 65 67 69 6e 7b 71 75 6f |ip....\b|egin{quo|
|00000b60| 74 65 7d 0d 0a 24 5c 62 | 6c 61 63 6b 74 72 69 61 |te}..$\b|lacktria|
|00000b70| 6e 67 6c 65 72 69 67 68 | 74 20 24 20 5c 74 65 78 |nglerigh|t $ \tex|
|00000b80| 74 73 66 7b 53 69 6d 70 | 6c 65 78 20 2b 20 4d 69 |tsf{Simp|lex + Mi|
|00000b90| 6e 69 6d 69 7a 65 7d 0d | 0a 5c 65 6e 64 7b 71 75 |nimize}.|.\end{qu|
|00000ba0| 6f 74 65 7d 0d 0a 0d 0a | 5c 62 65 67 69 6e 7b 71 |ote}....|\begin{q|
|00000bb0| 75 6f 74 61 74 69 6f 6e | 7d 0d 0a 24 0d 0a 5c 62 |uotation|}..$..\b|
|00000bc0| 65 67 69 6e 7b 61 72 72 | 61 79 7d 7b 63 7d 0d 0a |egin{arr|ay}{c}..|
|00000bd0| 2d 78 2d 79 20 5c 5c 20 | 0d 0a 34 78 2b 33 79 5c |-x-y \\ |..4x+3y\|
|00000be0| 6c 65 71 20 36 20 5c 5c | 20 0d 0a 33 78 2b 34 79 |leq 6 \\| ..3x+4y|
|00000bf0| 5c 6c 65 71 20 34 0d 0a | 5c 65 6e 64 7b 61 72 72 |\leq 4..|\end{arr|
|00000c00| 61 79 7d 0d 0a 24 2c 20 | 4d 69 6e 69 6d 75 6d 20 |ay}..$, |Minimum |
|00000c10| 69 73 20 61 74 3a 20 24 | 5c 6c 65 66 74 5c 7b 20 |is at: $|\left\{ |
|00000c20| 79 3d 2d 5c 66 72 61 63 | 7b 32 7d 7b 37 7d 2c 78 |y=-\frac|{2}{7},x|
|00000c30| 3d 5c 66 72 61 63 7b 31 | 32 7d 7b 37 7d 5c 72 69 |=\frac{1|2}{7}\ri|
|00000c40| 67 68 74 5c 7d 20 24 0d | 0a 5c 65 6e 64 7b 71 75 |ght\} $.|.\end{qu|
|00000c50| 6f 74 61 74 69 6f 6e 7d | 0d 0a 0d 0a 5c 20 0d 0a |otation}|....\ ..|
|00000c60| 0d 0a 5c 73 75 62 73 65 | 63 74 69 6f 6e 7b 5c 20 |..\subse|ction{\ |
|00000c70| 5c 6c 61 62 65 6c 7b 46 | 65 61 73 69 62 6c 65 20 |\label{F|easible |
|00000c80| 73 79 73 74 65 6d 7d 46 | 65 61 73 69 62 6c 65 20 |system}F|easible |
|00000c90| 53 79 73 74 65 6d 73 7d | 0d 0a 0d 0a 54 77 6f 20 |Systems}|....Two |
|00000ca0| 74 68 69 6e 67 73 20 6d | 61 79 20 70 72 65 76 65 |things m|ay preve|
|00000cb0| 6e 74 20 74 68 65 20 65 | 78 69 73 74 65 6e 63 65 |nt the e|xistence|
|00000cc0| 20 6f 66 20 61 20 73 6f | 6c 75 74 69 6f 6e 2e 20 | of a so|lution. |
|00000cd0| 54 68 65 72 65 20 6d 61 | 79 20 62 65 20 6e 6f 20 |There ma|y be no |
|00000ce0| 76 61 6c 75 65 73 0d 0a | 6f 66 20 24 78 24 20 61 |values..|of $x$ a|
|00000cf0| 6e 64 20 24 79 24 20 73 | 61 74 69 73 66 79 69 6e |nd $y$ s|atisfyin|
|00000d00| 67 20 74 68 65 20 63 6f | 6e 73 74 72 61 69 6e 74 |g the co|nstraint|
|00000d10| 73 2e 20 45 76 65 6e 20 | 69 66 20 74 68 65 72 65 |s. Even |if there|
|00000d20| 20 61 72 65 20 73 75 63 | 68 20 76 61 6c 75 65 73 | are suc|h values|
|00000d30| 2c 0d 0a 74 68 65 72 65 | 20 6d 61 79 20 62 65 20 |,..there| may be |
|00000d40| 6e 6f 6e 65 20 6d 61 78 | 69 6d 69 7a 69 6e 67 20 |none max|imizing |
|00000d50| 74 68 65 20 6f 62 6a 65 | 63 74 69 76 65 20 66 75 |the obje|ctive fu|
|00000d60| 6e 63 74 69 6f 6e 2e 20 | 49 66 20 74 68 65 72 65 |nction. |If there|
|00000d70| 20 61 72 65 20 76 61 6c | 75 65 73 0d 0a 73 61 74 | are val|ues..sat|
|00000d80| 69 73 66 79 69 6e 67 20 | 74 68 65 20 63 6f 6e 73 |isfying |the cons|
|00000d90| 74 72 61 69 6e 74 73 2c | 20 74 68 65 20 0d 0a 5c |traints,| the ..\|
|00000da0| 69 6e 64 65 78 7b 46 65 | 61 73 69 62 6c 65 20 73 |index{Fe|asible s|
|00000db0| 79 73 74 65 6d 40 46 65 | 61 73 69 62 6c 65 20 73 |ystem@Fe|asible s|
|00000dc0| 79 73 74 65 6d 7d 20 0d | 0a 5c 69 6e 64 65 78 7b |ystem} .|.\index{|
|00000dd0| 53 69 6d 70 6c 65 78 40 | 53 69 6d 70 6c 65 78 21 |Simplex@|Simplex!|
|00000de0| 66 65 61 73 69 62 6c 65 | 40 66 65 61 73 69 62 6c |feasible|@feasibl|
|00000df0| 65 7d 73 79 73 74 65 6d | 20 69 73 20 63 61 6c 6c |e}system| is call|
|00000e00| 65 64 20 5c 74 65 78 74 | 73 6c 7b 66 65 61 73 69 |ed \text|sl{feasi|
|00000e10| 62 6c 65 7d 2e 0d 0a 0d | 0a 54 68 65 20 66 6f 6c |ble}....|.The fol|
|00000e20| 6c 6f 77 69 6e 67 20 65 | 78 61 6d 70 6c 65 20 69 |lowing e|xample i|
|00000e30| 6c 6c 75 73 74 72 61 74 | 65 73 20 61 20 73 65 74 |llustrat|es a set|
|00000e40| 20 6f 66 20 69 6e 65 71 | 75 61 6c 69 74 79 20 63 | of ineq|uality c|
|00000e50| 6f 6e 73 74 72 61 69 6e | 74 73 20 77 69 74 68 20 |onstrain|ts with |
|00000e60| 6e 6f 0d 0a 66 75 6e 63 | 74 69 6f 6e 20 74 6f 20 |no..func|tion to |
|00000e70| 62 65 20 6d 61 78 69 6d | 69 7a 65 64 20 6f 72 20 |be maxim|ized or |
|00000e80| 6d 69 6e 69 6d 69 7a 65 | 64 2e 20 59 6f 75 20 63 |minimize|d. You c|
|00000e90| 61 6e 20 61 73 6b 20 77 | 68 65 74 68 65 72 20 74 |an ask w|hether t|
|00000ea0| 68 65 20 63 6f 6e 73 74 | 72 61 69 6e 74 73 0d 0a |he const|raints..|
|00000eb0| 61 72 65 20 66 65 61 73 | 69 62 6c 65 2d 2d 2d 74 |are feas|ible---t|
|00000ec0| 68 61 74 20 69 73 2c 20 | 77 68 65 74 68 65 72 20 |hat is, |whether |
|00000ed0| 74 68 65 79 20 64 65 66 | 69 6e 65 20 61 20 6e 6f |they def|ine a no|
|00000ee0| 6e 65 6d 70 74 79 20 73 | 65 74 2e 20 4a 75 73 74 |nempty s|et. Just|
|00000ef0| 20 63 6c 69 63 6b 20 74 | 68 65 0d 0a 6d 61 74 72 | click t|he..matr|
|00000f00| 69 78 2c 20 61 6e 64 20 | 66 72 6f 6d 20 74 68 65 |ix, and |from the|
|00000f10| 20 5c 74 65 78 74 73 66 | 7b 53 69 6d 70 6c 65 78 | \textsf|{Simplex|
|00000f20| 7d 5c 20 73 75 62 6d 65 | 6e 75 20 63 68 6f 6f 73 |}\ subme|nu choos|
|00000f30| 65 20 5c 74 65 78 74 73 | 66 7b 25 0d 0a 46 65 61 |e \texts|f{%..Fea|
|00000f40| 73 69 62 6c 65 2e 5c 6d | 65 64 73 6b 69 70 20 7d |sible.\m|edskip }|
|00000f50| 0d 0a 0d 0a 5c 62 65 67 | 69 6e 7b 71 75 6f 74 65 |....\beg|in{quote|
|00000f60| 7d 0d 0a 24 5c 62 6c 61 | 63 6b 74 72 69 61 6e 67 |}..$\bla|cktriang|
|00000f70| 6c 65 72 69 67 68 74 20 | 24 20 5c 74 65 78 74 73 |leright |$ \texts|
|00000f80| 66 7b 53 69 6d 70 6c 65 | 78 20 2b 20 46 65 61 73 |f{Simple|x + Feas|
|00000f90| 69 62 6c 65 3f 7d 0d 0a | 5c 65 6e 64 7b 71 75 6f |ible?}..|\end{quo|
|00000fa0| 74 65 7d 0d 0a 0d 0a 5c | 62 65 67 69 6e 7b 71 75 |te}....\|begin{qu|
|00000fb0| 6f 74 61 74 69 6f 6e 7d | 0d 0a 24 0d 0a 5c 62 65 |otation}|..$..\be|
|00000fc0| 67 69 6e 7b 61 72 72 61 | 79 7d 7b 72 7d 0d 0a 34 |gin{arra|y}{r}..4|
|00000fd0| 78 2b 33 79 5c 6c 65 71 | 20 36 20 5c 5c 20 0d 0a |x+3y\leq| 6 \\ ..|
|00000fe0| 33 78 2b 34 79 5c 6c 65 | 71 20 34 20 5c 5c 20 0d |3x+4y\le|q 4 \\ .|
|00000ff0| 0a 78 5c 67 65 71 20 30 | 20 5c 5c 20 0d 0a 79 5c |.x\geq 0| \\ ..y\|
|00001000| 67 65 71 20 30 0d 0a 5c | 65 6e 64 7b 61 72 72 61 |geq 0..\|end{arra|
|00001010| 79 7d 0d 0a 24 2c 20 49 | 73 20 66 65 61 73 69 62 |y}..$, I|s feasib|
|00001020| 6c 65 3f 20 74 72 75 65 | 0d 0a 0d 0a 24 5c 20 24 |le? true|....$\ $|
|00001030| 0d 0a 0d 0a 24 0d 0a 5c | 62 65 67 69 6e 7b 61 72 |....$..\|begin{ar|
|00001040| 72 61 79 7d 7b 63 7d 0d | 0a 34 78 2b 33 79 5c 6c |ray}{c}.|.4x+3y\l|
|00001050| 65 71 20 36 20 5c 5c 20 | 0d 0a 34 78 2b 33 79 5c |eq 6 \\ |..4x+3y\|
|00001060| 67 65 71 20 37 0d 0a 5c | 65 6e 64 7b 61 72 72 61 |geq 7..\|end{arra|
|00001070| 79 7d 0d 0a 24 2c 20 49 | 73 20 66 65 61 73 69 62 |y}..$, I|s feasib|
|00001080| 6c 65 3f 20 66 61 6c 73 | 65 5c 6d 65 64 73 6b 69 |le? fals|e\medski|
|00001090| 70 0d 0a 5c 65 6e 64 7b | 71 75 6f 74 61 74 69 6f |p..\end{|quotatio|
|000010a0| 6e 7d 0d 0a 0d 0a 53 61 | 79 69 6e 67 20 74 68 61 |n}....Sa|ying tha|
|000010b0| 74 20 74 68 65 20 73 79 | 73 74 65 6d 20 24 0d 0a |t the sy|stem $..|
|000010c0| 5c 62 65 67 69 6e 7b 61 | 72 72 61 79 7d 7b 63 7d |\begin{a|rray}{c}|
|000010d0| 0d 0a 34 78 2b 33 79 5c | 6c 65 71 20 36 20 5c 5c |..4x+3y\|leq 6 \\|
|000010e0| 20 0d 0a 34 78 2b 33 79 | 5c 67 65 71 20 37 0d 0a | ..4x+3y|\geq 7..|
|000010f0| 5c 65 6e 64 7b 61 72 72 | 61 79 7d 0d 0a 24 20 69 |\end{arr|ay}..$ i|
|00001100| 73 20 6e 6f 74 20 66 65 | 61 73 69 62 6c 65 20 69 |s not fe|asible i|
|00001110| 6d 70 6c 69 65 73 2c 20 | 69 6e 20 70 61 72 74 69 |mplies, |in parti|
|00001120| 63 75 6c 61 72 2c 20 74 | 68 61 74 20 74 68 65 72 |cular, t|hat ther|
|00001130| 65 20 61 72 65 20 6e 6f | 20 76 61 6c 75 65 73 0d |e are no| values.|
|00001140| 0a 6d 69 6e 69 6d 69 7a | 69 6e 67 20 74 68 65 20 |.minimiz|ing the |
|00001150| 6f 62 6a 65 63 74 69 76 | 65 20 66 75 6e 63 74 69 |objectiv|e functi|
|00001160| 6f 6e 20 69 6e 20 74 68 | 65 20 70 72 6f 62 6c 65 |on in th|e proble|
|00001170| 6d 20 24 0d 0a 5c 62 65 | 67 69 6e 7b 61 72 72 61 |m $..\be|gin{arra|
|00001180| 79 7d 7b 63 7d 0d 0a 78 | 2b 79 20 5c 5c 20 0d 0a |y}{c}..x|+y \\ ..|
|00001190| 34 78 2b 33 79 5c 6c 65 | 71 20 36 20 5c 5c 20 0d |4x+3y\le|q 6 \\ .|
|000011a0| 0a 34 78 2b 33 79 5c 67 | 65 71 20 37 0d 0a 5c 65 |.4x+3y\g|eq 7..\e|
|000011b0| 6e 64 7b 61 72 72 61 79 | 7d 0d 0a 5c 2c 24 2e 5c |nd{array|}..\,$.\|
|000011c0| 62 69 67 73 6b 69 70 0d | 0a 0d 0a 5c 73 75 62 73 |bigskip.|...\subs|
|000011d0| 65 63 74 69 6f 6e 7b 5c | 20 5c 6c 61 62 65 6c 7b |ection{\| \label{|
|000011e0| 53 74 61 6e 64 61 72 64 | 20 66 6f 72 6d 7d 53 74 |Standard| form}St|
|000011f0| 61 6e 64 61 72 64 20 46 | 6f 72 6d 5c 6c 61 62 65 |andard F|orm\labe|
|00001200| 6c 7b 53 69 6d 70 6c 65 | 78 2c 20 73 74 61 6e 64 |l{Simple|x, stand|
|00001210| 61 72 64 69 7a 65 7d 7d | 0d 0a 0d 0a 41 20 73 79 |ardize}}|....A sy|
|00001220| 73 74 65 6d 20 6f 66 20 | 6c 69 6e 65 61 72 20 69 |stem of |linear i|
|00001230| 6e 65 71 75 61 6c 69 74 | 69 65 73 20 69 73 20 69 |nequalit|ies is i|
|00001240| 6e 20 0d 0a 5c 69 6e 64 | 65 78 7b 4c 69 6e 65 61 |n ..\ind|ex{Linea|
|00001250| 72 20 70 72 6f 67 72 61 | 6d 6d 69 6e 67 40 4c 69 |r progra|mming@Li|
|00001260| 6e 65 61 72 20 70 72 6f | 67 72 61 6d 6d 69 6e 67 |near pro|gramming|
|00001270| 21 73 74 61 6e 64 61 72 | 64 20 66 6f 72 6d 40 73 |!standar|d form@s|
|00001280| 74 61 6e 64 61 72 64 20 | 66 6f 72 6d 7d 25 0d 0a |tandard |form}%..|
|00001290| 5c 74 65 78 74 73 6c 7b | 73 74 61 6e 64 61 72 64 |\textsl{|standard|
|000012a0| 20 66 6f 72 6d 7d 20 77 | 68 65 6e 20 61 6c 6c 20 | form} w|hen all |
|000012b0| 74 68 65 20 69 6e 65 71 | 75 61 6c 69 74 69 65 73 |the ineq|ualities|
|000012c0| 20 61 72 65 20 6f 66 20 | 74 68 65 20 66 6f 72 6d | are of |the form|
|000012d0| 20 24 5c 6c 65 71 20 24 | 2e 20 54 6f 0d 0a 63 6f | $\leq $|. To..co|
|000012e0| 6e 76 65 72 74 20 61 20 | 73 79 73 74 65 6d 20 6f |nvert a |system o|
|000012f0| 66 20 6c 69 6e 65 61 72 | 20 69 6e 65 71 75 61 6c |f linear| inequal|
|00001300| 69 74 69 65 73 20 74 6f | 20 61 20 73 79 73 74 65 |ities to| a syste|
|00001310| 6d 20 69 6e 20 73 74 61 | 6e 64 61 72 64 20 66 6f |m in sta|ndard fo|
|00001320| 72 6d 2c 20 63 68 6f 6f | 73 65 20 0d 0a 5c 74 65 |rm, choo|se ..\te|
|00001330| 78 74 73 66 7b 53 74 61 | 6e 64 61 72 64 69 7a 65 |xtsf{Sta|ndardize|
|00001340| 7d 20 66 72 6f 6d 20 0d | 0a 5c 69 6e 64 65 78 7b |} from .|.\index{|
|00001350| 53 69 6d 70 6c 65 78 40 | 53 69 6d 70 6c 65 78 21 |Simplex@|Simplex!|
|00001360| 73 74 61 6e 64 61 72 64 | 69 7a 65 40 73 74 61 6e |standard|ize@stan|
|00001370| 64 61 72 64 69 7a 65 7d | 74 68 65 20 5c 74 65 78 |dardize}|the \tex|
|00001380| 74 73 66 7b 53 69 6d 70 | 6c 65 78 7d 0d 0a 73 75 |tsf{Simp|lex}..su|
|00001390| 62 6d 65 6e 75 2e 5c 6d | 65 64 73 6b 69 70 0d 0a |bmenu.\m|edskip..|
|000013a0| 0d 0a 5c 62 65 67 69 6e | 7b 71 75 6f 74 65 7d 0d |..\begin|{quote}.|
|000013b0| 0a 24 5c 62 6c 61 63 6b | 74 72 69 61 6e 67 6c 65 |.$\black|triangle|
|000013c0| 72 69 67 68 74 20 24 20 | 5c 74 65 78 74 73 66 7b |right $ |\textsf{|
|000013d0| 53 69 6d 70 6c 65 78 20 | 2b 20 53 74 61 6e 64 61 |Simplex |+ Standa|
|000013e0| 72 64 69 7a 65 7d 0d 0a | 5c 65 6e 64 7b 71 75 6f |rdize}..|\end{quo|
|000013f0| 74 65 7d 0d 0a 0d 0a 5c | 62 65 67 69 6e 7b 71 75 |te}....\|begin{qu|
|00001400| 6f 74 61 74 69 6f 6e 7d | 0d 0a 24 0d 0a 5c 62 65 |otation}|..$..\be|
|00001410| 67 69 6e 7b 61 72 72 61 | 79 7d 7b 72 7d 0d 0a 34 |gin{arra|y}{r}..4|
|00001420| 78 2b 33 79 5c 6c 65 71 | 20 36 20 5c 5c 20 0d 0a |x+3y\leq| 6 \\ ..|
|00001430| 33 78 2b 34 79 5c 6c 65 | 71 20 34 20 5c 5c 20 0d |3x+4y\le|q 4 \\ .|
|00001440| 0a 78 5c 67 65 71 20 30 | 20 5c 5c 20 0d 0a 79 5c |.x\geq 0| \\ ..y\|
|00001450| 67 65 71 20 30 0d 0a 5c | 65 6e 64 7b 61 72 72 61 |geq 0..\|end{arra|
|00001460| 79 7d 0d 0a 24 2c 20 53 | 79 73 74 65 6d 20 69 6e |y}..$, S|ystem in|
|00001470| 20 73 74 61 6e 64 61 72 | 64 20 66 6f 72 6d 20 69 | standar|d form i|
|00001480| 73 3a 20 24 0d 0a 5c 62 | 65 67 69 6e 7b 61 72 72 |s: $..\b|egin{arr|
|00001490| 61 79 7d 7b 63 7d 0d 0a | 34 78 2b 33 79 5c 6c 65 |ay}{c}..|4x+3y\le|
|000014a0| 71 20 36 20 5c 5c 20 0d | 0a 33 78 2b 34 79 5c 6c |q 6 \\ .|.3x+4y\l|
|000014b0| 65 71 20 34 20 5c 5c 20 | 0d 0a 2d 78 5c 6c 65 71 |eq 4 \\ |..-x\leq|
|000014c0| 20 30 20 5c 5c 20 0d 0a | 2d 79 5c 6c 65 71 20 30 | 0 \\ ..|-y\leq 0|
|000014d0| 0d 0a 5c 65 6e 64 7b 61 | 72 72 61 79 7d 0d 0a 24 |..\end{a|rray}..$|
|000014e0| 0d 0a 5c 65 6e 64 7b 71 | 75 6f 74 61 74 69 6f 6e |..\end{q|uotation|
|000014f0| 7d 0d 0a 0d 0a 5c 20 0d | 0a 0d 0a 57 69 74 68 20 |}....\ .|...With |
|00001500| 61 20 6c 69 6e 65 61 72 | 20 66 75 6e 63 74 69 6f |a linear| functio|
|00001510| 6e 20 61 64 64 65 64 2c | 20 79 6f 75 20 63 61 6e |n added,| you can|
|00001520| 20 6d 61 78 69 6d 69 7a | 65 20 74 68 65 20 72 65 | maximiz|e the re|
|00001530| 73 75 6c 74 69 6e 67 20 | 6c 69 6e 65 61 72 0d 0a |sulting |linear..|
|00001540| 70 72 6f 67 72 61 6d 6d | 69 6e 67 20 70 72 6f 62 |programm|ing prob|
|00001550| 6c 65 6d 2e 5c 6d 65 64 | 73 6b 69 70 0d 0a 0d 0a |lem.\med|skip....|
|00001560| 5c 62 65 67 69 6e 7b 71 | 75 6f 74 65 7d 0d 0a 24 |\begin{q|uote}..$|
|00001570| 5c 62 6c 61 63 6b 74 72 | 69 61 6e 67 6c 65 72 69 |\blacktr|iangleri|
|00001580| 67 68 74 20 24 20 5c 74 | 65 78 74 73 66 7b 53 69 |ght $ \t|extsf{Si|
|00001590| 6d 70 6c 65 78 20 2b 20 | 4d 61 78 69 6d 69 7a 65 |mplex + |Maximize|
|000015a0| 7d 0d 0a 5c 65 6e 64 7b | 71 75 6f 74 65 7d 0d 0a |}..\end{|quote}..|
|000015b0| 0d 0a 5c 62 65 67 69 6e | 7b 71 75 6f 74 61 74 69 |..\begin|{quotati|
|000015c0| 6f 6e 7d 0d 0a 24 0d 0a | 5c 62 65 67 69 6e 7b 61 |on}..$..|\begin{a|
|000015d0| 72 72 61 79 7d 7b 72 7d | 0d 0a 78 2b 33 79 20 5c |rray}{r}|..x+3y \|
|000015e0| 5c 20 0d 0a 33 78 2d 79 | 5c 6c 65 71 20 34 20 5c |\ ..3x-y|\leq 4 \|
|000015f0| 5c 20 0d 0a 34 78 2b 33 | 79 5c 6c 65 71 20 36 20 |\ ..4x+3|y\leq 6 |
|00001600| 5c 5c 20 0d 0a 2d 79 5c | 6c 65 71 20 30 20 5c 5c |\\ ..-y\|leq 0 \\|
|00001610| 20 0d 0a 2d 78 5c 6c 65 | 71 20 30 0d 0a 5c 65 6e | ..-x\le|q 0..\en|
|00001620| 64 7b 61 72 72 61 79 7d | 0d 0a 24 2c 20 4d 61 78 |d{array}|..$, Max|
|00001630| 69 6d 75 6d 20 69 73 20 | 61 74 3a 20 24 5c 6c 65 |imum is |at: $\le|
|00001640| 66 74 5c 7b 20 78 3d 30 | 2c 79 3d 32 5c 72 69 67 |ft\{ x=0|,y=2\rig|
|00001650| 68 74 5c 7d 20 24 0d 0a | 5c 65 6e 64 7b 71 75 6f |ht\} $..|\end{quo|
|00001660| 74 61 74 69 6f 6e 7d 0d | 0a 0d 0a 5c 20 0d 0a 0d |tation}.|...\ ...|
|00001670| 0a 5c 73 75 62 73 65 63 | 74 69 6f 6e 7b 5c 20 5c |.\subsec|tion{\ \|
|00001680| 6c 61 62 65 6c 7b 44 75 | 61 6c 20 6f 66 20 61 20 |label{Du|al of a |
|00001690| 6c 69 6e 65 61 72 20 70 | 72 6f 67 72 61 6d 7d 54 |linear p|rogram}T|
|000016a0| 68 65 20 44 75 61 6c 20 | 6f 66 20 61 20 4c 69 6e |he Dual |of a Lin|
|000016b0| 65 61 72 20 50 72 6f 67 | 72 61 6d 7d 0d 0a 0d 0a |ear Prog|ram}....|
|000016c0| 54 68 65 20 6f 74 68 65 | 72 20 69 74 65 6d 20 6f |The othe|r item o|
|000016d0| 6e 20 74 68 65 20 5c 74 | 65 78 74 73 66 7b 53 69 |n the \t|extsf{Si|
|000016e0| 6d 70 6c 65 78 7d 20 6d | 65 6e 75 20 0d 0a 5c 69 |mplex} m|enu ..\i|
|000016f0| 6e 64 65 78 7b 53 69 6d | 70 6c 65 78 40 53 69 6d |ndex{Sim|plex@Sim|
|00001700| 70 6c 65 78 21 64 75 61 | 6c 40 64 75 61 6c 7d 69 |plex!dua|l@dual}i|
|00001710| 73 20 5c 74 65 78 74 73 | 66 7b 44 75 61 6c 7d 2e |s \texts|f{Dual}.|
|00001720| 20 49 74 20 63 6f 6d 70 | 75 74 65 73 20 74 68 65 | It comp|utes the|
|00001730| 20 0d 0a 5c 69 6e 64 65 | 78 7b 44 75 61 6c 20 6f | ..\inde|x{Dual o|
|00001740| 66 20 61 20 6c 69 6e 65 | 61 72 20 70 72 6f 67 61 |f a line|ar proga|
|00001750| 6d 40 44 75 61 6c 20 6f | 66 20 61 20 6c 69 6e 65 |m@Dual o|f a line|
|00001760| 61 72 20 70 72 6f 67 61 | 6d 7d 64 75 61 6c 20 6f |ar proga|m}dual o|
|00001770| 66 20 61 20 6c 69 6e 65 | 61 72 0d 0a 70 72 6f 67 |f a line|ar..prog|
|00001780| 72 61 6d 2e 5c 6d 65 64 | 73 6b 69 70 0d 0a 0d 0a |ram.\med|skip....|
|00001790| 5c 62 65 67 69 6e 7b 71 | 75 6f 74 65 7d 0d 0a 24 |\begin{q|uote}..$|
|000017a0| 5c 62 6c 61 63 6b 74 72 | 69 61 6e 67 6c 65 72 69 |\blacktr|iangleri|
|000017b0| 67 68 74 20 24 20 5c 74 | 65 78 74 73 66 7b 53 69 |ght $ \t|extsf{Si|
|000017c0| 6d 70 6c 65 78 20 2b 20 | 44 75 61 6c 7d 0d 0a 5c |mplex + |Dual}..\|
|000017d0| 65 6e 64 7b 71 75 6f 74 | 65 7d 0d 0a 0d 0a 5c 62 |end{quot|e}....\b|
|000017e0| 65 67 69 6e 7b 71 75 6f | 74 61 74 69 6f 6e 7d 0d |egin{quo|tation}.|
|000017f0| 0a 24 0d 0a 5c 62 65 67 | 69 6e 7b 61 72 72 61 79 |.$..\beg|in{array|
|00001800| 7d 7b 72 7d 0d 0a 78 2b | 79 20 5c 5c 20 0d 0a 34 |}{r}..x+|y \\ ..4|
|00001810| 78 2b 33 79 5c 6c 65 71 | 20 36 20 5c 5c 20 0d 0a |x+3y\leq| 6 \\ ..|
|00001820| 33 78 2b 34 79 5c 6c 65 | 71 20 34 20 5c 5c 20 0d |3x+4y\le|q 4 \\ .|
|00001830| 0a 78 5c 67 65 71 20 30 | 20 5c 5c 20 0d 0a 2d 79 |.x\geq 0| \\ ..-y|
|00001840| 5c 6c 65 71 20 30 0d 0a | 5c 65 6e 64 7b 61 72 72 |\leq 0..|\end{arr|
|00001850| 61 79 7d 0d 0a 24 2c 20 | 44 75 61 6c 20 73 79 73 |ay}..$, |Dual sys|
|00001860| 74 65 6d 20 69 73 3a 20 | 24 0d 0a 5c 62 65 67 69 |tem is: |$..\begi|
|00001870| 6e 7b 61 72 72 61 79 7d | 7b 63 7d 0d 0a 36 73 5f |n{array}|{c}..6s_|
|00001880| 7b 31 7d 2b 34 73 5f 7b | 32 7d 20 5c 5c 20 0d 0a |{1}+4s_{|2} \\ ..|
|00001890| 31 5c 6c 65 71 20 33 73 | 5f 7b 31 7d 2b 34 73 5f |1\leq 3s|_{1}+4s_|
|000018a0| 7b 32 7d 2d 73 5f 7b 34 | 7d 20 5c 5c 20 0d 0a 31 |{2}-s_{4|} \\ ..1|
|000018b0| 5c 6c 65 71 20 34 73 5f | 7b 31 7d 2b 33 73 5f 7b |\leq 4s_|{1}+3s_{|
|000018c0| 32 7d 2d 73 5f 7b 33 7d | 0d 0a 5c 65 6e 64 7b 61 |2}-s_{3}|..\end{a|
|000018d0| 72 72 61 79 7d 0d 0a 24 | 0d 0a 5c 65 6e 64 7b 71 |rray}..$|..\end{q|
|000018e0| 75 6f 74 61 74 69 6f 6e | 7d 0d 0a 0d 0a 5c 20 0d |uotation|}....\ .|
|000018f0| 0a 0d 0a 41 70 70 6c 79 | 69 6e 67 20 74 68 65 20 |...Apply|ing the |
|00001900| 73 69 6d 70 6c 65 78 20 | 61 6c 67 6f 72 69 74 68 |simplex |algorith|
|00001910| 6d 20 74 6f 20 74 68 65 | 73 65 20 74 77 6f 20 6c |m to the|se two l|
|00001920| 69 6e 65 61 72 20 70 72 | 6f 67 72 61 6d 73 20 79 |inear pr|ograms y|
|00001930| 69 65 6c 64 73 20 74 68 | 65 0d 0a 66 6f 6c 6c 6f |ields th|e..follo|
|00001940| 77 69 6e 67 20 72 65 73 | 75 6c 74 73 2e 0d 0a 0d |wing res|ults....|
|00001950| 0a 5c 62 65 67 69 6e 7b | 71 75 6f 74 65 7d 0d 0a |.\begin{|quote}..|
|00001960| 24 5c 62 6c 61 63 6b 74 | 72 69 61 6e 67 6c 65 72 |$\blackt|riangler|
|00001970| 69 67 68 74 20 24 20 5c | 74 65 78 74 73 66 7b 53 |ight $ \|textsf{S|
|00001980| 69 6d 70 6c 65 78 20 2b | 20 4d 61 78 69 6d 69 7a |implex +| Maximiz|
|00001990| 65 7d 0d 0a 5c 65 6e 64 | 7b 71 75 6f 74 65 7d 0d |e}..\end|{quote}.|
|000019a0| 0a 0d 0a 5c 62 65 67 69 | 6e 7b 71 75 6f 74 61 74 |...\begi|n{quotat|
|000019b0| 69 6f 6e 7d 0d 0a 24 0d | 0a 5c 62 65 67 69 6e 7b |ion}..$.|.\begin{|
|000019c0| 61 72 72 61 79 7d 7b 72 | 7d 0d 0a 78 2b 79 20 5c |array}{r|}..x+y \|
|000019d0| 5c 20 0d 0a 34 78 2b 33 | 79 5c 6c 65 71 20 36 20 |\ ..4x+3|y\leq 6 |
|000019e0| 5c 5c 20 0d 0a 33 78 2b | 34 79 5c 6c 65 71 20 34 |\\ ..3x+|4y\leq 4|
|000019f0| 20 5c 5c 20 0d 0a 78 5c | 67 65 71 20 30 20 5c 5c | \\ ..x\|geq 0 \\|
|00001a00| 20 0d 0a 2d 79 5c 6c 65 | 71 20 30 0d 0a 5c 65 6e | ..-y\le|q 0..\en|
|00001a10| 64 7b 61 72 72 61 79 7d | 0d 0a 24 2c 20 4d 61 78 |d{array}|..$, Max|
|00001a20| 69 6d 75 6d 20 69 73 20 | 61 74 3a 20 24 5c 6c 65 |imum is |at: $\le|
|00001a30| 66 74 5c 7b 20 79 3d 30 | 2c 78 3d 25 0d 0a 5c 66 |ft\{ y=0|,x=%..\f|
|00001a40| 72 61 63 7b 34 7d 7b 33 | 7d 5c 72 69 67 68 74 5c |rac{4}{3|}\right\|
|00001a50| 7d 20 24 0d 0a 5c 65 6e | 64 7b 71 75 6f 74 61 74 |} $..\en|d{quotat|
|00001a60| 69 6f 6e 7d 0d 0a 0d 0a | 5c 62 65 67 69 6e 7b 71 |ion}....|\begin{q|
|00001a70| 75 6f 74 65 7d 0d 0a 24 | 5c 62 6c 61 63 6b 74 72 |uote}..$|\blacktr|
|00001a80| 69 61 6e 67 6c 65 72 69 | 67 68 74 20 24 20 5c 74 |iangleri|ght $ \t|
|00001a90| 65 78 74 73 66 7b 53 69 | 6d 70 6c 65 78 20 2b 20 |extsf{Si|mplex + |
|00001aa0| 4d 69 6e 69 6d 69 7a 65 | 7d 0d 0a 5c 65 6e 64 7b |Minimize|}..\end{|
|00001ab0| 71 75 6f 74 65 7d 0d 0a | 0d 0a 5c 62 65 67 69 6e |quote}..|..\begin|
|00001ac0| 7b 71 75 6f 74 61 74 69 | 6f 6e 7d 0d 0a 24 0d 0a |{quotati|on}..$..|
|00001ad0| 5c 62 65 67 69 6e 7b 61 | 72 72 61 79 7d 7b 6c 7d |\begin{a|rray}{l}|
|00001ae0| 0d 0a 36 73 5f 7b 31 7d | 2b 34 73 5f 7b 32 7d 20 |..6s_{1}|+4s_{2} |
|00001af0| 5c 5c 20 0d 0a 31 5c 6c | 65 71 20 34 73 5f 7b 31 |\\ ..1\l|eq 4s_{1|
|00001b00| 7d 2b 33 73 5f 7b 32 7d | 2d 73 5f 7b 34 7d 20 5c |}+3s_{2}|-s_{4} \|
|00001b10| 5c 20 0d 0a 31 5c 6c 65 | 71 20 33 73 5f 7b 31 7d |\ ..1\le|q 3s_{1}|
|00001b20| 2b 34 73 5f 7b 32 7d 2d | 73 5f 7b 33 7d 20 5c 5c |+4s_{2}-|s_{3} \\|
|00001b30| 20 0d 0a 73 5f 7b 31 7d | 5c 67 65 71 20 30 20 5c | ..s_{1}|\geq 0 \|
|00001b40| 5c 20 0d 0a 73 5f 7b 32 | 7d 5c 67 65 71 20 30 20 |\ ..s_{2|}\geq 0 |
|00001b50| 5c 5c 20 0d 0a 73 5f 7b | 33 7d 5c 67 65 71 20 30 |\\ ..s_{|3}\geq 0|
|00001b60| 20 5c 5c 20 0d 0a 73 5f | 7b 34 7d 5c 67 65 71 20 | \\ ..s_|{4}\geq |
|00001b70| 30 0d 0a 5c 65 6e 64 7b | 61 72 72 61 79 7d 0d 0a |0..\end{|array}..|
|00001b80| 24 2c 20 4d 69 6e 69 6d | 75 6d 20 69 73 20 61 74 |$, Minim|um is at|
|00001b90| 3a 20 24 5c 6c 65 66 74 | 5c 7b 20 73 5f 7b 34 7d |: $\left|\{ s_{4}|
|00001ba0| 3d 30 2c 73 5f 7b 31 7d | 3d 30 2c 73 5f 7b 32 7d |=0,s_{1}|=0,s_{2}|
|00001bb0| 3d 5c 66 72 61 63 7b 31 | 7d 7b 33 7d 2c 73 5f 7b |=\frac{1|}{3},s_{|
|00001bc0| 33 7d 3d 5c 66 72 61 63 | 7b 31 7d 7b 33 25 0d 0a |3}=\frac|{1}{3%..|
|00001bd0| 7d 5c 72 69 67 68 74 5c | 7d 20 24 0d 0a 5c 65 6e |}\right\|} $..\en|
|00001be0| 64 7b 71 75 6f 74 61 74 | 69 6f 6e 7d 0d 0a 0d 0a |d{quotat|ion}....|
|00001bf0| 5c 20 0d 0a 0d 0a 5c 73 | 75 62 73 65 63 74 69 6f |\ ....\s|ubsectio|
|00001c00| 6e 7b 5c 20 52 65 6c 61 | 74 65 64 20 74 6f 70 69 |n{\ Rela|ted topi|
|00001c10| 63 73 7d 0d 0a 0d 0a 5c | 68 79 70 65 72 72 65 66 |cs}....\|hyperref|
|00001c20| 7b 53 6f 6c 76 69 6e 67 | 20 45 71 75 61 74 69 6f |{Solving| Equatio|
|00001c30| 6e 73 7d 7b 7d 7b 7d 7b | 44 4d 31 32 2d 31 2e 74 |ns}{}{}{|DM12-1.t|
|00001c40| 65 78 23 49 6e 74 65 67 | 65 72 20 73 6f 6c 75 74 |ex#Integ|er solut|
|00001c50| 69 6f 6e 73 7d 0d 0a 0d | 0a 5c 68 79 70 65 72 72 |ions}...|.\hyperr|
|00001c60| 65 66 7b 49 6e 74 65 67 | 65 72 73 20 4d 6f 64 75 |ef{Integ|ers Modu|
|00001c70| 6c 6f 20 6d 7d 7b 7d 7b | 7d 7b 44 4d 31 32 2d 32 |lo m}{}{|}{DM12-2|
|00001c80| 2e 74 65 78 23 49 6e 74 | 65 67 65 72 73 20 6d 6f |.tex#Int|egers mo|
|00001c90| 64 75 6c 6f 20 6d 7d 0d | 0a 0d 0a 5c 68 79 70 65 |dulo m}.|...\hype|
|00001ca0| 72 72 65 66 7b 4f 74 68 | 65 72 20 53 79 73 74 65 |rref{Oth|er Syste|
|00001cb0| 6d 73 20 4d 6f 64 75 6c | 6f 20 6d 7d 7b 7d 7b 7d |ms Modul|o m}{}{}|
|00001cc0| 7b 44 4d 31 32 2d 33 2e | 74 65 78 23 4d 61 74 72 |{DM12-3.|tex#Matr|
|00001cd0| 69 63 65 73 20 6d 6f 64 | 75 6c 6f 20 6d 7d 0d 0a |ices mod|ulo m}..|
|00001ce0| 0d 0a 5c 68 79 70 65 72 | 72 65 66 7b 50 6f 6c 79 |..\hyper|ref{Poly|
|00001cf0| 6e 6f 6d 69 61 6c 73 20 | 4d 6f 64 75 6c 6f 20 50 |nomials |Modulo P|
|00001d00| 6f 6c 79 6e 6f 6d 69 61 | 6c 73 7d 7b 7d 7b 7d 7b |olynomia|ls}{}{}{|
|00001d10| 44 4d 31 32 2d 34 2e 74 | 65 78 23 50 6f 6c 79 6e |DM12-4.t|ex#Polyn|
|00001d20| 6f 6d 69 61 6c 73 20 6d | 6f 64 75 6c 6f 0d 0a 70 |omials m|odulo..p|
|00001d30| 6f 6c 79 6e 6f 6d 69 61 | 6c 73 7d 0d 0a 0d 0a 5c |olynomia|ls}....\|
|00001d40| 68 79 70 65 72 72 65 66 | 7b 45 78 65 72 63 69 73 |hyperref|{Exercis|
|00001d50| 65 73 20 61 6e 64 20 53 | 6f 6c 75 74 69 6f 6e 73 |es and S|olutions|
|00001d60| 7d 7b 7d 7b 7d 7b 44 4d | 31 32 2d 36 2e 74 65 78 |}{}{}{DM|12-6.tex|
|00001d70| 23 45 78 65 72 63 69 73 | 65 73 7d 0d 0a 0d 0a 5c |#Exercis|es}....\|
|00001d80| 72 75 6c 65 7b 30 2e 36 | 37 69 6e 7d 7b 30 2e 30 |rule{0.6|7in}{0.0|
|00001d90| 31 69 6e 7d 0d 0a 0d 0a | 5c 68 79 70 65 72 72 65 |1in}....|\hyperre|
|00001da0| 66 7b 5c 46 52 41 4d 45 | 7b 69 74 62 70 46 7d 7b |f{\FRAME|{itbpF}{|
|00001db0| 30 2e 35 32 37 35 69 6e | 7d 7b 30 2e 33 33 39 39 |0.5275in|}{0.3399|
|00001dc0| 69 6e 7d 7b 30 2e 30 35 | 31 39 69 6e 7d 7b 7d 7b |in}{0.05|19in}{}{|
|00001dd0| 7d 7b 69 6e 64 65 78 2e | 77 6d 66 7d 7b 5c 73 70 |}{index.|wmf}{\sp|
|00001de0| 65 63 69 61 6c 25 0d 0a | 7b 6c 61 6e 67 75 61 67 |ecial%..|{languag|
|00001df0| 65 20 22 53 63 69 65 6e | 74 69 66 69 63 20 57 6f |e "Scien|tific Wo|
|00001e00| 72 64 22 3b 74 79 70 65 | 20 22 47 52 41 50 48 49 |rd";type| "GRAPHI|
|00001e10| 43 22 3b 64 69 73 70 6c | 61 79 20 22 50 49 43 54 |C";displ|ay "PICT|
|00001e20| 22 3b 76 61 6c 69 64 2d | 66 69 6c 65 0d 0a 22 46 |";valid-|file.."F|
|00001e30| 22 3b 77 69 64 74 68 20 | 30 2e 35 32 37 35 69 6e |";width |0.5275in|
|00001e40| 3b 68 65 69 67 68 74 20 | 30 2e 33 33 39 39 69 6e |;height |0.3399in|
|00001e50| 3b 64 65 70 74 68 20 30 | 2e 30 35 31 39 69 6e 3b |;depth 0|.0519in;|
|00001e60| 6f 72 69 67 69 6e 61 6c | 2d 77 69 64 74 68 0d 0a |original|-width..|
|00001e70| 33 36 2e 38 37 35 70 74 | 3b 6f 72 69 67 69 6e 61 |36.875pt|;origina|
|00001e80| 6c 2d 68 65 69 67 68 74 | 20 32 32 2e 35 36 32 35 |l-height| 22.5625|
|00001e90| 70 74 3b 63 72 6f 70 6c | 65 66 74 20 22 30 22 3b |pt;cropl|eft "0";|
|00001ea0| 63 72 6f 70 74 6f 70 20 | 22 31 22 3b 63 72 6f 70 |croptop |"1";crop|
|00001eb0| 72 69 67 68 74 0d 0a 22 | 31 22 3b 63 72 6f 70 62 |right.."|1";cropb|
|00001ec0| 6f 74 74 6f 6d 20 22 30 | 22 3b 66 69 6c 65 6e 61 |ottom "0|";filena|
|00001ed0| 6d 65 20 27 69 6e 64 65 | 78 2e 77 6d 66 27 3b 66 |me 'inde|x.wmf';f|
|00001ee0| 69 6c 65 2d 70 72 6f 70 | 65 72 74 69 65 73 20 22 |ile-prop|erties "|
|00001ef0| 58 4e 50 45 55 22 3b 7d | 7d 7d 7b 7d 7b 7d 7b 25 |XNPEU";}|}}{}{}{%|
|00001f00| 0d 0a 44 4d 49 6e 64 65 | 78 2e 74 65 78 23 4d 61 |..DMInde|x.tex#Ma|
|00001f10| 74 68 20 49 6e 64 65 78 | 7d 5c 71 75 61 64 20 7b |th Index|}\quad {|
|00001f20| 5c 73 6d 61 6c 6c 20 49 | 6e 64 65 78 20 65 6e 74 |\small I|ndex ent|
|00001f30| 72 69 65 73 3a 20 5c 68 | 79 70 65 72 72 65 66 7b |ries: \h|yperref{|
|00001f40| 41 70 70 6c 69 65 64 20 | 6d 6f 64 65 72 6e 0d 0a |Applied |modern..|
|00001f50| 61 6c 67 65 62 72 61 7d | 7b 7d 7b 7d 7b 44 4d 49 |algebra}|{}{}{DMI|
|00001f60| 6e 64 65 78 2e 74 65 78 | 23 41 70 70 6c 69 65 64 |ndex.tex|#Applied|
|00001f70| 20 6d 6f 64 65 72 6e 20 | 61 6c 67 65 62 72 61 7d | modern |algebra}|
|00001f80| 2c 20 5c 68 79 70 65 72 | 72 65 66 7b 4c 69 6e 65 |, \hyper|ref{Line|
|00001f90| 61 72 0d 0a 70 72 6f 67 | 72 61 6d 6d 69 6e 67 7d |ar..prog|ramming}|
|00001fa0| 7b 7d 7b 7d 7b 44 4d 49 | 6e 64 65 78 2e 74 65 78 |{}{}{DMI|ndex.tex|
|00001fb0| 23 4c 69 6e 65 61 72 20 | 70 72 6f 67 72 61 6d 6d |#Linear |programm|
|00001fc0| 69 6e 67 7d 2c 20 5c 68 | 79 70 65 72 72 65 66 7b |ing}, \h|yperref{|
|00001fd0| 4d 61 74 72 69 63 65 73 | 7d 7b 7d 7b 7d 7b 25 0d |Matrices|}{}{}{%.|
|00001fe0| 0a 44 4d 49 6e 64 65 78 | 2e 74 65 78 23 4d 61 74 |.DMIndex|.tex#Mat|
|00001ff0| 72 69 63 65 73 7d 2c 20 | 5c 68 79 70 65 72 72 65 |rices}, |\hyperre|
|00002000| 66 7b 53 69 6d 70 6c 65 | 78 7d 7b 7d 7b 7d 7b 44 |f{Simple|x}{}{}{D|
|00002010| 4d 49 6e 64 65 78 2e 74 | 65 78 23 53 69 6d 70 6c |MIndex.t|ex#Simpl|
|00002020| 65 78 7d 7d 0d 0a 0d 0a | 5c 65 6e 64 7b 64 6f 63 |ex}}....|\end{doc|
|00002030| 75 6d 65 6e 74 7d 0d 0a |                         |ument}..|        |
+--------+-------------------------+-------------------------+--------+--------+