【文章內(nèi)容簡介】 001/41/2由些可得，問題的最優(yōu)解為x1=7/2，x2=3/2，最優(yōu)值max z=17/21用大M法求解如下線性規(guī)劃模型：min z =5x1＋2x2＋4x3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：max z/ =－5x1－2x2－4x3.增加人工變量xx7，得到：max z/ =－5x1－2x2－4x3－Mx6－Mx7大M法單純形表求解過程如下：CBXBb－5－2－400－M－MθLx1x2x3x4x5x6x7－Mx64（3）12－10104/3－Mx7106350－1015/3－9M－4M－7MMM－M－M9M－5↑4M－27M－4－M－M00－5x14/311/32/3－1/301/30——－Mx72011（2）－1－211－5M－5/3M－10/32M+5/3M2M－5/3M0M－1/3M－2/32M－5/3↑－M－3M+5/30－5x15/311/25/60－1/601/610/30x410（1/2）1/21－1/2－11/22－5－5/2－25/605/60－5/601/2↑1/60－5/6－M－M+5/6－5－2x12/3101/3－11/31－1/3x220112－1－21－－5－2－11/311/3－1－1/300－1/3－1－1/3－M+1－M+1/3∴x*=（，2，0，0，0）T最優(yōu)目標(biāo)函數(shù)值min z =－max z/ =－（－）=1用大M法求解如下線性規(guī)劃模型：min z =540x1＋450x2＋720x3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：max z/ =－540x1－450x2－720x3.增加人工變量xx7，得到：max z/ =－540x1－450x2－720x3－Mx6－Mx7大M法單純形表求解過程如下：CBXBb－540－450－72000－M－MθLx1x2x3x4x5x6x7－Mx670359－101070/3－Mx730（9）530－10130/9=10/3－12M－10M－12MMM－M－M12M－540↑10M－45012M－720－M－M00－Mx660010/3（8）－11/31－1/360/8=－540x110/315/91/30－1/901/910/3/1/3=10300+10/3M8M－180－M－M/3+60－MM/3－600150+10/3M8M540↑MM/3－600－M/3+60－720x315/205/121－1/81/241/8－1/2415/2/5/12=18－540x15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450x320/3－1011/61/61/6－1/6x2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴該對偶問題的最優(yōu)解是x*=（0，2，0，0）T最優(yōu)目標(biāo)函數(shù)值min z =－（－5700）=5700 1用單純形法求解線性規(guī)劃問題化成標(biāo)準(zhǔn)形式有加入人工變量則為列出單純形表Cj－30100－MMCBXBbx1x2x3x4x5x6x70MMx4x6x74191201[1]3111100010010001Z10M2M34M10M0000Mx4x2x731632[6]010214100113113001Z6M6M304M+103M4M0003x4x2x103100101001/3[2/3]1001/201/21/201/21/21/31/6Z300303/2M3/2M+1/2001x4x2x305/23/201/23/20100011001/21/43/41/21/43/41/21/41/4Z3/29/20003/4M+3/4M1/4人工變量已不在基變量中，X*=(0,5/2,3/2,0,0,0,0)’ Z*=3/21用單純形法求解線性規(guī)劃問題解 化為標(biāo)準(zhǔn)形式有列表計算Cj－3－200MCBXBbx1x2x3x4x50Mx3x521223[1]410010123Z12M3M+34M+20M02Mx2x5242510140101Z44M5M104M2M0X*=(0,2,0,0,4)’ Z*=4M4 說明原問題無解216。 寫對偶問題 寫出下列線性繪畫問題的對偶問題 解： 寫出下述線性規(guī)劃的對偶問題解寫出下列線性規(guī)劃的對偶問題解：寫出下列線性規(guī)劃的對偶問題解216。 對偶性質(zhì)已知線性規(guī)劃問題如下：Max Z= 已知該問題的解為（2，4）利用對偶性質(zhì)寫出對偶問題的最優(yōu)解。解：該問題的對偶問題為： 將X=（2，4）T代入原問題可知：〉1 為嚴(yán)格不等式，所以由對偶問題性質(zhì)可知： 解之得： 所以Y=（1/5，0，1）T Min Z=14 已知線性規(guī)劃問題 用圖解法求對偶問題的解；利用(b)的結(jié)果及對偶性質(zhì)求原問題解。答案：(對偶問題的最優(yōu)解為；(依據(jù)z*=w*及互補松弛性，有x4=0,且 解得愿問題最優(yōu)解X*=(7/5,0,1/5,0)。已知線性規(guī)劃問題 已知其對偶問題的最優(yōu)解為，最優(yōu)值為。試用對偶理論找出原問題的最優(yōu)解。解 先寫出它的對偶問題 . ① ② ③ ④ ⑤ 將的值代入約束條件，得②，③，④為嚴(yán)格不等式；設(shè)原問題的最優(yōu)解為，由互補松弛性得。因 ；原問題的兩個約束條件應(yīng)取等式，故有求解后得到；故原問題的最優(yōu)解為 ；最優(yōu)值為。 已知下列問題的最優(yōu)解為X*=(1/7,11/7),用互補松弛定理求其對偶問題的最優(yōu)解。解：第一步，寫出對偶問題第二步，將LP，DP都化為標(biāo)準(zhǔn)型第三步：將最優(yōu)解代入標(biāo)準(zhǔn)型中，確定松弛變量取值第四步：利用互補松弛定理∴ Y3*=0∴ Y1S=0 Y2S=0第五步：將Y3*=0 Y1S=0 Y2S=0 代入約束條件則有∴ 對偶問題的最優(yōu)解為Y*=(4/7,5/7,0)’已知線性規(guī)劃問題：，試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。證明：首先看到該問題存在可行解，例如，而上述問題的對偶問題為： 由第一約束條件可知對偶問題無可行解，因而無最優(yōu)解。由此，原問題也無最優(yōu)解。已知線性規(guī)劃問題（1）寫出其對偶問題；（2）用圖解法求對偶問題的解；（3）利用（2）的結(jié)果及對偶性質(zhì)求原問題解。解：（1）原線性規(guī)劃問題可化為：其對偶問題為：（2）用圖解法解得 （3）由互補松弛性定理知道，又由解之，可得原問題最優(yōu)解216。 對偶單純形法用對偶單純形法解下列線性規(guī)劃問題解：先化為標(biāo)準(zhǔn)型約束條件兩邊同乘(1) 列單純形表Cj－15－24－500CBXBbx1x2x3x4x500x4x5－2－10－5[6]2111001152450045240x2x51/31/305101/6[2/3]1/61/30115014033/212245x2x31/41/25/415/210011/41/21/43/215/2007/23/2X*=(0,1/4,1/2)’ Y*=(7/2,3/2)用對偶單純形法解下列線性規(guī)劃問題解：改寫為標(biāo)準(zhǔn)形式列單純形表如下：Cj－4－12－1800CBXBbx1x2x3x4x500x4x5－3－5－100[2]321001412180069012x4x235/21001[3]11001/24060642121812x3 x213/21/31/301101/31/301/2200