運(yùn)籌學(xué)-線性規(guī)劃問(wèn)題最優(yōu)解的確定與改進(jìn)

1、=J最線性規(guī)劃問(wèn)題最優(yōu)解的確定與改進(jìn)線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。自1947年丹捷格(G.B.Dantzig)提出了一般線性規(guī)劃問(wèn)題 求解的方法一一單純形法之后，線性規(guī)劃在理論上趨向成熟，在實(shí)用中日益廣泛與深入。線性規(guī)劃 最優(yōu)解求解問(wèn)題，在運(yùn)籌學(xué)本科版給出了圖解法和單純形法。一般線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為：(1-4)(1-5)(1-6)max (1-4)(1-5)(1-6)i=1 J JZX =b,i=1,2.mj=x. 0,j=1,2,n滿(mǎn)足約束條件(1-5)式、(1-6)式的解X =(氣,x2,xjr，稱(chēng)為線性規(guī)劃問(wèn)題的可行解，其中 使目標(biāo)函數(shù)達(dá)到最大值的可行解稱(chēng)為最優(yōu)解。2009年中國(guó)科教

2、創(chuàng)新導(dǎo)刊，第三十期李高秀寫(xiě)的線性規(guī)劃中最優(yōu)解的準(zhǔn)確確定中詳細(xì)介紹了 圖解法的過(guò)程，圖解法適合于二元線性規(guī)劃問(wèn)題，對(duì)于多元線性規(guī)劃問(wèn)題圖解法相對(duì)較難。圖解法過(guò)程：1線性目標(biāo)函數(shù)最值的分析 a z . a z對(duì)于線性目標(biāo)函數(shù)Z=ax+by，右bN0時(shí)，目標(biāo)函數(shù)可變?yōu)閥 = -丁 x + 丁，則是直線y = -丁 x + -b bb b在y軸上的截距。azb0時(shí)，隨著直線y =-丁x +廠的平移，直線在與可行域有公共點(diǎn)的條件下，它在y軸上的bbzz截距丁 最大時(shí)z最大；當(dāng)丁 最小時(shí)z最小。bbazb 0有最優(yōu)解x*。則x* +為原LP問(wèn)題最優(yōu)解的充要條件是：c = 0，Ax = 0，x * + 0，

3、其中 c = (c , c，,c ) x = (x , x，,x )t， TOC o 1-5 h z 12n12nx* = (x* ,x* ,，x* )t ，A = (a )，b = (b ,b，b )t ，0 = (0,0, ,0)t，1 2nij mx n1 2 mmxlW = (3 ,0，,O )t。2 LPP模型的建立考慮標(biāo)準(zhǔn)型LP問(wèn)題：min cx.s.t Ax = b，x 。設(shè)其某一最優(yōu)解x*，則有與之對(duì)應(yīng)的LPP模型：min cx = 0, AW = 0, W + x* 0。由引理1和LP理論有以下定理：定理1設(shè)&n為L(zhǎng)P問(wèn)題非基變量的判別數(shù)集(N為非基變量下標(biāo)集)則W e N,

4、E 0 0W為零向量。問(wèn)題有惟一最優(yōu)解.3j e N,&j 0 (z為整數(shù))，則與之對(duì)應(yīng)的ILPP模型為min c = 0， s.t A.w = 0， x* + 0， e Z。對(duì)ILPP模型，有以下定理：定理2：(1 Vj e N,弓 0。3為零向量。lLP問(wèn)題有惟一最優(yōu)解.(2)刃e N,弓 0。3為區(qū)間向量。1LP有多重最優(yōu)解.4數(shù)值求解問(wèn)題：現(xiàn)有一投資商對(duì)A、B兩項(xiàng)產(chǎn)品投資，其投資利潤(rùn)及相關(guān)條件如下表：A產(chǎn)品B產(chǎn)品數(shù)量情況變化情況變化(1)(2)利潤(rùn)1千元/件1千元/件機(jī)器216人員4522臺(tái)故障1臺(tái)故障0人請(qǐng)假1人請(qǐng)假問(wèn)：該投資商在正常情況下如何安排生產(chǎn)，利潤(rùn)最大?條件變化又該如何安排

5、生產(chǎn)(A、B產(chǎn)品數(shù)量需 整數(shù))？解 根據(jù)題意，可得下列模型：max z = x + x (x，x分別是A、B的生產(chǎn)數(shù)量).1212I% + x2 6；(ILP)s.t 4x + 5x 0, i 2= 1,2.i本文用割平面法解上述(ILP)，則上述(ILP)問(wèn)題對(duì)應(yīng)的LP松馳問(wèn)題為：max z = x + x .2 x + x + x = 6;(LP) s.t 0, i = 1,2,3,4.I iLP單純性表如下：表一x1x2x3x4min(-z)基01100 x62110 x204501對(duì)表一單純選得最優(yōu)表二表二xxxxsin(-z)基、-13/500-1/6-1/60 x3、5/3102/

6、3-1/60 x8/301-2/31/30s-2/300-1/3-1/31由表二中的x為源行，可得割平面方程：S =-2 +1 x +1 x，將S置于尾行并作為基。11333341對(duì)表二對(duì)偶單純選代得最優(yōu)表三表三xxxxsin(-z)基-40000-1/2x3、2105/60-1/2x201-101s20011-3于是得ILP的一組最優(yōu)解氣=2，x2= 2，maxz = 4。為了考察情況變化是否直接影響投資者利益，我們有必要考慮如下模型ILPP：min( 3 +3 ) = 0.2 3 i +3 2 +3 3 = 0 0；3 - 2, 3 - 2, 3 0；12343 , i G Z , i =

7、 1,2,3, 4.通過(guò)求解ILPP問(wèn)題，可得ILP的最優(yōu)解可表示為：(2 + 3，2-W , 3,-3w ),Q g -2,0, w g Z.111111由ILP最優(yōu)解的參數(shù)表達(dá)式可知：在正常狀況下，投資者有三種方案可供選擇，分別為：方案一 氣二0,氣=2, % = 2.方案二 31 = -1,% -1,x2 = 3.方案三 31 =-2, %1 = 0, % = 4.根據(jù)情況變化(1)，投資者只可選擇方案三；根據(jù)情況變化(2)，投資者只可選擇方案二。通過(guò)LP和ILP模型的轉(zhuǎn)換求出其最優(yōu)解集，可讓決策者更好地對(duì)其可利用資源進(jìn)行更合理的分配， 獲得最佳利潤(rùn)，而不像單純性表法只有一組最優(yōu)解，一次匚？和ILP模型有其優(yōu)越性，可以用于解決 最優(yōu)化問(wèn)題?！緟⒖嘉墨I(xiàn)】：薛聲家，劉惠.一般形式線性規(guī)劃最優(yōu)解集的確定M