第一章 習題答案

第一章習題參考答案1.1(1)minz=2x1+3x2解：由圖可知，B和c點最優(yōu)解方程組得x1=6/5,x2=1/5圖1-2∴x*=(6/5,1/5)或（3/2，0）且兩點連線上點圖1-2均為最優(yōu)解,故原問題有沒有窮多最優(yōu)解，z*=3。（3）maxz=x1+x2解：由圖1-2知，可行域有5個頂點A（10，6）,B（10，3）,C（5，3）,D（5，8）和E（，8）將這5點分別代入目標函數(shù)，可知A點最優(yōu)?！鄕*=(10,6)T且為唯一最優(yōu)解，z*=16。1.2將下述線性規(guī)劃問題什成標準形式(1)minz=－3x1+4x2－2x3＋5x4解：令，則有1.3對下述線性規(guī)劃問題找出全部基解，指出哪些是基可行解，并確定最優(yōu)解。（1）解：基是否基可行解Z值（P1，P2，P3）0000×（P1，P2，P4）0100-700×（P1，P2，P5）03000最優(yōu)解3（P1，P2，P6）-4000-12(21/4)×（P2，P3，P6）0000×（P3，P4，P6）00-5/2800×（P1，P3，P4）00-5/2800×（P1，P3，P5）003/2080最優(yōu)解3（P1，P3，P6）10-1/2003×（P1，P4，P5）000350√0（P1，P4，P6）5/400-2015/4×（P2，P4，P6）0100-700×（P3，P5，P6）003/2080最優(yōu)解3（P4，P5，P6）000350√0（P1，P5，P6）3/400023(9/4)√9/4（P2，P5，P6）03007/20最優(yōu)解3由表可知，該線性規(guī)劃問題共有16個基解，7個基可行解，4個最優(yōu)解，如上圖所表示。Z*=31.4（1）解：化作標準形式基常數(shù)34109[5]20181050000110010-160110100∴，（2）解：化作標準形式基常數(shù)351015[6]201242100/0[4]1310400-8011000∴1.7(1)解：化作標準形式方法一：用兩階段法求解。引入輔助問題，求原問題一基可行解基x1x2x3x4x5x6x7x8x9常數(shù)x7111-1001006x8-2010-100102x90[2]-100-100101-3-1111000x710-10106x8-20[1]0-100102x201000001011-00x7[4]00-11--3X3-2010-100102x2-1100--01-4001--0x1100---1/8x3001--(-1/4)x2010---3/8000000111求原問題最優(yōu)解基x1x2x3x4x5x6常數(shù)x1100-1/8x3001--x2010--(-3/8)-z000(-3/8)-21/4(-27/4)∵＞0而＜0，∴原問題有沒有界解。方法二、用大M法求解基常數(shù)111-1001006-2010-10010202-100-100102-M3M-1M+2-M-M-M0008M10-3/2(3/2)-101/210-1/26-2010-10010201-1/200-1/2001/202-M0-M-M1/2M-1/2008M400-13/21/21-3/2-1/23-2010-100102-1100-1/2-1/201/21/214M+500-M1/2M-1/20-5/2M+3/23M-3100-1/43/81/8-3/8-3/8(-1/8)3/4001-1/2-1/41/41/4-1/47/2010-1/4-1/8-3/81/41/83/87/4000-4/5-M-27/4∵，∴原問題有沒有界解。1.7（2）minz=2x1+3x2+x3解:原問題可化為方法一：用兩階段法求解。引入輔助問題基常數(shù)1[4]2-101083200-1016-4-6-211001-002[]0-1-1-1250-21-20301--10---0000011求原問題最優(yōu)解基常數(shù)0110-z000-7∴X*=，Z*=7方法二、用大M法求解。在添加松弛變量和人工變量后，模型為Maxz′=-2x1-3x2-x3-Mx6-Mx7基常數(shù)1[4]2-101083200-10164M-26M-32M-1-M-M0014M1-002[]0-1-1-125/2M-5/40-M-M02M+601--10---000---M+-M+7因為非基變量x3檢驗數(shù)，所以此問題有沒有窮多解，為其中之一，z*=7。1.7（3）解：方法一：用兩階段法，引入輔助問題：基常數(shù)[3]10010343-100161201004-7-4100011/3001/3010[5/3]-10-4/31205/301-1/3030-5/3107/30101/509/15-1/53/501-3/50-4/53/56/500111-11000011求原問題最優(yōu)解基常數(shù)10001-000[1]1100-0100-01000111000∴，因為非基變量對應檢驗數(shù)，所以原問題有唯一最優(yōu)解。方法二、用大M法求解，原問題可化為minz=[3]10010343-100161201004-7M+4-4M+1M000100010[5/3]-10-(-4/3)1205/301-030-M-M0-M-0101/509/15-01-3/50-00[1]11-1100-00M-24/15M+100-0010-000111-11000M-M∴，因為非基變量對應檢驗數(shù)，所以原問題有唯一最優(yōu)解。1.7（4）解：上式可化為方法一：用兩階段法求解MinW=x7[5]3110009-561501001521100-115-2-1-1001013/51/51/50009/509[16]11002403/50-1100101000010000-110010因為最優(yōu)基中含有不為零人工變量，所以原問題無可行解。方法二、用大M法求解[5]3110009-561501001521100-1152M+15M+1200-M013/51/51/50009/509[16]1100240-1/53/5-2/50-117/50-2/5M-20-M0139/8003/16-1/800009/1611/161/16000-43/800-7/16-3/80-110-43/80M+27/80-3/80M-5/8-M0因為最優(yōu)基中含有不為零人工變量7，所以原問題無可行解。1.8解：由單純形表知，x1為換入變量，為換出變量，b為主元素，經(jīng)過換基迭代將b化為1，關(guān)鍵列其余元素全部化為0。故g=1,h=0。而關(guān)鍵行其它元素同除以主元素，則有；；；；。關(guān)鍵列和關(guān)鍵行以外其它元素，依照初等變換得來。檢驗行-1-2a=-7∴a=3；a+2=j，∴j=5;0，∴k=。同理e-(-1)×(-1)=1,∴e=2;3+2=i,∴i=5。因為5為基變量，而基變量對應檢驗數(shù)為0，∴l(xiāng)=0。綜上：a=3;b=2,c=4,d=-2,e=2,f=3,g=1,h=0,,j=5,k=,l=0。1.9若均為某線性規(guī)劃問題最優(yōu)解，證實在這兩點連線上全部點也是該問題最優(yōu)解。證實：設(shè)=b，∴X為可行解。又因(記)，故X為最優(yōu)解，證畢。1.10線性規(guī)劃問題max設(shè)X0為問題最優(yōu)解。若目標函數(shù)中用C*代替C后,問題最優(yōu)解變?yōu)閄*,求證（證實：∴而，證畢。1.11考慮線性規(guī)劃問題模型中為參數(shù)，要求：（1）組成兩個新約束依照、認為基變量，列出初始單純形表；（2）在表中，假定，則為何值，1，2為問題最優(yōu)基；（3）在表中，假定則為何值，1，2為問題最優(yōu)基。解：（1）由題意，得其標準形式為其初始單純形表以下12341101-13201-10-00-(2)由題意得時，為問題最優(yōu)基。（3）由題意得時，最優(yōu)基不變。1.12（1）解：對線性規(guī)劃問題，，假如X*是該問題最優(yōu)解,由最優(yōu)解判別準則知對min（），有仍為最優(yōu)解，即最優(yōu)解不變。（2）對，有除非1-；不然,不再為最優(yōu)解。（3）對于,由(1)知仍為