運籌學第一章作業(yè)答案

第一章作業(yè)對于下列線性規(guī)劃模型，找出頂點和約束之間的對應關系（圖解法）maxz=2x+x'5x<156x2+2x<24S.t< 1 2xi+x2<5x>0,x>0（答案略：任何一個頂點對應兩個約束的交點）用單純形法求解線性規(guī)劃模型maxz=2x+x3x+x<24st<x+x>5x>0,x>0、1 2（答案略：最好兩階段法和大M法均練習一遍）通過觀察，判斷下列線性規(guī)劃模型有無最優(yōu)解、在有解的情況下是否為無界轍說明理由）maxz=2x+x(1)x+x>5(1)s.t<2x+2x<8x>0,x>012因為x+x>5和2x+2x<8是兩個矛盾的條件，所以問題無解1 2 1 2maxz=2x+x+xx一x+2x>5st<3x-2x-5x>8x>0,x>012因為（M,0,0）是模型的一個可行解，所以可認為問題為無界解。4.判斷題（說明理由）最優(yōu)解不唯一，那么一定有兩個最優(yōu)基可行解。錯誤。最優(yōu)解不唯一，可能存在一個基可行解，也可能存在r（r32）個基可行解。舉一例子進行反駁即可。（注意區(qū)分基可行解和可行解）在最優(yōu)單純形表中，如果某個非基變量的檢驗數(shù)值為0，且相應的技術系數(shù)均小于等于0，則相應的線性規(guī)劃有無界解。錯誤。判定無界解的原則有二：（1）某一單純表中某一非基變量的檢驗數(shù)為正（目標函數(shù)求最大值時，求最小值時正好相反），而該變量的技術向量PW0；（2）某一單純表中某一非基變量的技術向量PW0，而該變量的價值系數(shù)又大于0（目標函數(shù)求最大值時，求最小值時正好相反）。（注意：區(qū)分無界解和無窮多最優(yōu)解）5線性規(guī)劃問題maxz=CX,AX=b,X>0，如果X*是該問題的最優(yōu)解，又人〉0為一常數(shù)，分別討論下述情況時最優(yōu)解的變化：

(a)目標函數(shù)變?yōu)閙axz=XCX方法1：使用檢驗數(shù)進行討論最優(yōu)單純表中，變量X的檢驗數(shù)為a=C-CBB-1A,顯然C—CB-1A<0設這時的最優(yōu)解為X*.當價值系數(shù)變?yōu)槿薈時，X*仍然是新問題的可行解，但變量X的檢驗數(shù)變?yōu)閍i=XC-^CB-1A=X(C-CB-1A)仍有a1<0,因而兩個問題具有同樣的最優(yōu)基，進而有同樣的最優(yōu)解，僅僅最優(yōu)目標函數(shù)值變化了人倍.方法2:設X*為原問題的一個最優(yōu)解，X是原問題的任意一個可行解因而必有CX*>CX由于X*和X均也為新問題的可行解，由于x>0，因而XCX*>XCX因而X*也是新問題的最優(yōu)解.(b)目標函數(shù)變?yōu)閙axz=(C+X)X提示：通過選擇具體的例子，分析目標函數(shù)的變化，最優(yōu)解可能發(fā)生改變，也可能不變.已知線性規(guī)劃問題maxz=cx+cx+cxTOC\o"1-5"\h\z11 22 33C... 7ax+ax+ax+x=b111 122 133 4 1st\ax+ax+ax+x=b211 222 233 5 2x>0j=1，2,3,4ijB-B-1=1/2 0-1/61/3已知最優(yōu)單純形表如下CBXBbc1c2c3C4C5x1x2%C3x35/201/21/25/21-1/20-1/61/3c.-z.0-40-4-2試確定模型中各參數(shù)的值解法1：直接使用矩陣變換.解法2:使用B和B-1解題(關鍵知識點)，具體略.(證明題)線性規(guī)劃問題maxz=CX,AX=b,X>0,設X0是問題的最優(yōu)解，若目標函數(shù)中用C*替換C后，問題的最優(yōu)解為X*，則必有(C*-C)(X*-X0)>0證明：對于原問題，由于X0和X*均為可行解，X0為最優(yōu)解，因而有CX0>CX* (7.1)對于替換后的問題，由于X0和X*均為可行解，X*為最優(yōu)解，因而有C*X*>C*X0 （7.2）結合（7.1）和（7.2）命題成立.種方（選做題）對于大M法和兩階段法下面線性規(guī)劃需要引入m個人工變量，你是否可以設計法只引入一個人工變量就可種方mi君cx+cx++cx.11 2 2 nnax+ax+...+ax>b11 122nn1 1ax+ax+...+ax>b11 222nn2 2S.t<...ax+ax+...+ax>bm11m2 2 mnnmx>0,i=1,2,...