線性規(guī)劃的方法及應(yīng)用

1、 線性規(guī)劃的方法及應(yīng)用引言運(yùn)籌學(xué)最初是由于第二次世界大戰(zhàn)的軍事需要而發(fā)展起來(lái)的，它是一種科學(xué)方法，是一種以定量的研究?jī)?yōu)化問題并尋求其確定解答的方法體系.線性規(guī)劃（ Linear Progromming ,簡(jiǎn)稱LP）是運(yùn)籌學(xué)的一個(gè)重要分支，其研究始于20世紀(jì)30年代末，許多人把線性規(guī)劃的發(fā)展列為20世紀(jì)中期最重要的科學(xué)進(jìn)步之一.1947年美國(guó)的數(shù)學(xué)家丹澤格提出了一般的線性規(guī)劃數(shù)學(xué)模型和求解線性規(guī)劃問題的通用方法一一單純形法，從而使線性規(guī)劃在理論上趨于成熟此后隨著電子計(jì)算機(jī)的出現(xiàn)，計(jì)算技術(shù)發(fā)展到一個(gè)高階段，單純形法步驟可以編成計(jì)算機(jī)程序，從而使線性規(guī)劃在實(shí)際中的應(yīng)用日益廣泛和深入目前，從解決工程問

2、題的最優(yōu)化問題到工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、軍事國(guó)防等部門的計(jì)劃管理與決策分析，乃至整個(gè)國(guó)民經(jīng)濟(jì)的綜合平衡，線性規(guī)劃都有用武之地，它已成為現(xiàn)代管理科學(xué)的重要基礎(chǔ)之一線性規(guī)劃的提出經(jīng)營(yíng)管理中如何有效地利用現(xiàn)有人力物力完成更多的任務(wù)，或在預(yù)定的任務(wù)目標(biāo)下，如何耗用最少的人力物力去實(shí)現(xiàn)這類問題可以用數(shù)學(xué)語(yǔ)言表達(dá)，即先根據(jù)問題要達(dá)到的目標(biāo)選取適當(dāng)?shù)淖兞?，問題的目標(biāo)通常用變量的函數(shù)形式 （稱為目標(biāo)函數(shù)） ， 對(duì)問題的限制條件用有關(guān)變量的等式或不等式表達(dá) （稱為約束條件） 當(dāng)變量連續(xù)取值，且目標(biāo)函數(shù)和約束條件為線性時(shí)，稱這類模型為線性規(guī)劃的模型有關(guān)對(duì)線性規(guī)劃問題建模、求解和應(yīng)用的研究構(gòu)成了運(yùn)籌學(xué)中的線性規(guī)劃分支

3、線性規(guī)劃實(shí)際上是: 求一組變量的值，在滿足一組約束條件下，求得目標(biāo)函數(shù)的最優(yōu)解. 從而線性規(guī)劃模型的基本結(jié)構(gòu)為：變量：變量又叫未知數(shù)，它是實(shí)際系統(tǒng)的位置因素，也是決策系統(tǒng)中的可控因素，一般稱為決策變量，常引用英文字母加下標(biāo)來(lái)表示，如x1 ,x2 , xn 等目標(biāo)函數(shù)：將實(shí)際系統(tǒng)的目標(biāo)用數(shù)學(xué)形式表示出來(lái)，就稱為目標(biāo)函數(shù)，線性規(guī)劃的目標(biāo)函數(shù)是求系統(tǒng)目標(biāo)的數(shù)值， 即極大值 （如產(chǎn)值極大值， 利潤(rùn)極大值） 或極小值 （如成本極小值， 費(fèi)用極小值等等） 約束條件：約束條件是指實(shí)現(xiàn)系統(tǒng)目標(biāo)的限制因素它涉及到企業(yè)內(nèi)部條件和外部環(huán)境的各個(gè)方面，如原材料供應(yīng)設(shè)備能力、計(jì)劃指標(biāo)產(chǎn)品質(zhì)量要求和市場(chǎng)銷售狀態(tài)等等，這些

4、因素都對(duì)模型的變量起約束作用，故稱其為約束條件約束條件的數(shù)學(xué)表示有三種，即 , , , 線性規(guī)劃的變量應(yīng)為非負(fù)值，因?yàn)樽兞吭趯?shí)際問題中所代表的均為實(shí)物，所以不能為負(fù)線性規(guī)劃問題有多種形式，函數(shù)有的要求實(shí)現(xiàn)最大化，有的要求最小化；約束條件可以是“ ” ，也可以是“ ” ，還可以是“ ” ，這種多樣性給討論帶來(lái)不便. 為了便于討論其一般解法，我們通常將線性規(guī)劃問題的約束條件歸結(jié)為線性方程和一組非負(fù)性限制條件，并且對(duì)目標(biāo)函數(shù)統(tǒng)一成求最大值 , 也就是說(shuō) , 將線性規(guī)劃問題的數(shù)學(xué)模型化成如下形式, 并稱它為線性規(guī)劃問題的標(biāo)準(zhǔn)形式 :n max f cjxj j1ns.t. aij xjbi(i1,2,

5、m)j1xj0(j1,2,n)n任何非標(biāo)準(zhǔn)形式的線性規(guī)劃問題都能化成上述標(biāo)準(zhǔn)形式, 這是由于不等式約束aijxjbk 等價(jià)j1nn于 約 束 條 件 aij xj xn kbk,xn k 0 ； 不 等 式 約 束aij xjbl 等 價(jià) 于 約 束 條 件j1j1na ij xjxnlbl,xnl 0； 這里增添的變量xnk 和xnl 稱為松弛變量. 還有 , 求函數(shù) f 的最小值解j1可轉(zhuǎn)化為求函數(shù) f 的最 大值解 . 以下討論線性規(guī)劃問題時(shí)以標(biāo)準(zhǔn)型為主.3 線性規(guī)劃的解法3.1 圖解法滿足約束條件的決策變量的一組值叫做這個(gè)線性規(guī)劃的一個(gè)可行解; 把所有可行解構(gòu)成的集合叫做這個(gè)線性規(guī)劃的

6、可行域 . 因此 , 求解一個(gè)線性規(guī)劃的問題 , 使目標(biāo)函數(shù)取得最大值或最小值的可行解稱為線性規(guī)劃的最優(yōu)解. 一般求解線性規(guī)劃問題是討論它的最優(yōu)解下面介紹只有兩個(gè)決策變量的線性規(guī)劃 TOC o 1-5 h z 問題的圖解法.例1用圖解法求解max f x1x2s.t. 2x1x22x12x22x1 x2 5 HYPERLINK l bookmark19 o Current Document x1, x20解第一步先畫出可行域以X1, *2為坐標(biāo)軸作直角坐標(biāo)系，因?yàn)閤1 0, x2 0 ,所以問題的可行解必在第一象限（含坐標(biāo)軸）；約束條件2x X22要求問題的可行解必在直線 2x X22的右下方

7、的半平面上；約束條件 2x22 ,要求問題的可行解必在直線xi 2x22的左上方的半平面上；約束條件x1x25 ,要求問題的可行解必在直線x1x25的左下方的半平面上.因?yàn)樗械募s束條件都必須同時(shí)滿足，所以問題的可行解域必為閉區(qū)域OQ1Q2Q3Q4,如圖3.1.1中的陰影部分.第二步 從可行域中找出最優(yōu)解現(xiàn)在分析目標(biāo)函數(shù)fx1x2 ,在坐標(biāo)平面上，它可以看作是以f為參數(shù)的一族平行線：x2x1f位于同一條直線上的點(diǎn)，都有相同的目標(biāo)函數(shù)值，因而稱它為等值線.當(dāng)f由小變大時(shí)，直線x2 xi f沿其法線方向向左上方移動(dòng).當(dāng)移動(dòng)到Q2點(diǎn)時(shí)，f的取值最大，這就得出了本題的最優(yōu)解，如圖3.1.2 ,此時(shí)f最

8、大，得 max f 114 3.顯然用圖解法求解線性規(guī)劃問題時(shí)，簡(jiǎn)單直觀；但是當(dāng)決策變量多于兩個(gè)的時(shí)候，用圖解法就失效了.3.2單純形法這一方法是丹澤格在1947年提出的，它以成熟的算法理論和完善的算法及軟件統(tǒng)治線性規(guī)劃近30年.單純形法是求解線性規(guī)劃問題的最重要、最基本的方法，它的解題思路7（P27）是：將線性規(guī)劃問題化為標(biāo)準(zhǔn)型后，先找出一個(gè)單位可行基，對(duì)這個(gè)可行基給出可行解，然后用判定定理一一稱為檢驗(yàn)數(shù)，判 定其是否為最優(yōu)解.若是，求解過(guò)程結(jié)束；若不是，在單位可行基的基礎(chǔ)上，進(jìn)行換基迭代，該過(guò)程叫 做迭代，直到得出最優(yōu)解或證明無(wú)最優(yōu)解為止.它有很強(qiáng)的程序性，它的具體操作是從一張叫做初始表的

9、 表格開始的初始表由四部分構(gòu)成7(p27-冽：第一部分B 1A A ( B是單位可行基)即約束方程組的系數(shù)矩陣.第二部分B 1b b ( B是單位可行基 )即約束方程組的常數(shù)項(xiàng)構(gòu)成的列向量.第三部分是檢驗(yàn)數(shù)1 .).CB A C ( Cb為單位可行基變量所對(duì)應(yīng)的目標(biāo)函數(shù)中的系數(shù)列向量；C是目標(biāo)函數(shù)的系數(shù)行向量第四部分CBb該數(shù)為目標(biāo)函數(shù)值.它的表格形式為x1C1x2c2 xncn初a11a12 a1nbi始a21a22 a2nb2表CbXb am1am2 a mnbm檢驗(yàn)數(shù)CBB 1A CCBb例2用單純形法求解max f 6x1 3x2 TOC o 1-5 h z s.t. 3x1 2x24

10、04x1 x221x1,x20解第一步將原問題化為標(biāo)準(zhǔn)型max f 6x1 3x2 0 x3 0 x4s.t. 3x1 2x2x3 404x1 x2x421xj 0 (j1,2,3,4)第二步 觀察原問題是否存在現(xiàn)成的單位可行基因?yàn)榧s束方程組的系數(shù)矩陣為所以原問題存在現(xiàn)成的單位可行基Bi0，、彳(P1, P2, P3, P4)1P3P4第三步 列出初始表，計(jì)算1)B11A A12)B11b b40213）Cbi是目標(biāo)函數(shù)中基變量X3,X4的系數(shù)構(gòu)成的列向量14)CbBA C C (6, 3,0,0)，5)CbR 06)XB1X4由上面計(jì)算結(jié)果，列出初始表（如下表）表 3.2.1初6X13X20

11、X30X始0X3321040表0410121X4檢驗(yàn)數(shù)63000第四步判定由初始表知，檢驗(yàn)數(shù)中含有負(fù)數(shù)，故可行解x （0,0,40,21）T不是最優(yōu)解，還需要進(jìn)行迭代運(yùn)算（若檢驗(yàn)數(shù)均為非負(fù)數(shù)，則可行解即為最優(yōu)解）第五步迭代運(yùn)算 表 3.2.3 迭代一：確定主元在檢驗(yàn)數(shù)中，找出最小負(fù)數(shù)。該題最小負(fù)數(shù)是6,將 6所在列中各個(gè)正數(shù)元素與相應(yīng)的常數(shù)列40 2121各兀素相比，求出 min, 稱為最小比原則，選 4 （a2i）為主元，并加方括號(hào).144換基主元4所在行對(duì)應(yīng)的基變量（初始表左端X4為出基變量；主元4所在列對(duì)應(yīng)的非基變量（初始表最上端）Xi為進(jìn)基變量.這樣將基Bi 換為基 B2 (P3,Pi

12、).1 1 c 1 21一得 1, ,0,(*);444 4迭代運(yùn)算0.即把(*)將主元化為1,即將主元所在行（包括約束常數(shù)）各元素乘以將主元所在列一一稱為主元列，其他元素（包括檢驗(yàn)數(shù)及目標(biāo)函數(shù)值）化為 TOC o 1-5 h z 53 97乘以 3 ,加到第一仃，信 0, ,1,（ *）；4| 4把（*）乘以6加到檢驗(yàn)數(shù)所在行，得 0, -,0,3-63 （*）; HYPERLINK l bookmark38 o Current Document 22 2將以上三次迭代運(yùn)算（與矩陣的初等行變換相同）的結(jié)果，列表如下表 3.2.26300迭X1X2X3X4051397X30-代44461012

13、1一X11444檢驗(yàn)數(shù)030363222 TOC o 1-5 h z 完成第一次迭代后，必須注意仍需B 1b 0 ,再觀察檢驗(yàn)數(shù)中是否有負(fù)數(shù)，若均為負(fù)數(shù)，則迭代停止，該問題已取得最優(yōu)解和最優(yōu)值；若仍有負(fù)數(shù)，則進(jìn)行第二次迭代顯然在迭代一中，檢驗(yàn)數(shù)中有負(fù)數(shù)，且 9為最小負(fù)數(shù)，故進(jìn)行第二次迭代，第二次迭代方法與第2次迭代完全相同.迭代后運(yùn)算的結(jié)果，列表如下迭代6300 x1x2x3x436*2x1c.4301一一551210上5597525檢驗(yàn)數(shù)6300-5560610顯然在迭代二中,檢驗(yàn)數(shù)均為非負(fù),故停止迭代，得最優(yōu)解X (2,97,0,0)、最優(yōu)值f 606 5 5103.3對(duì)偶單純形法在上述線

14、性規(guī)劃問題中，有現(xiàn)成的單位可行基，但在實(shí)際求解過(guò)程中，經(jīng)常會(huì)遇到?jīng)]有現(xiàn)成的單位可行基，這就需要對(duì)約束方程組經(jīng)過(guò)同解變形，那么變形后，得到的新問題與原問題等價(jià)，所以我們通過(guò)同解變形，若變出了一個(gè)單位可行基，就不必添加人工變量，直接用單純形求解；若變不出單位可行基，也一定能夠變出一個(gè)單位基,這就引出了對(duì)偶單純形法的求解問題.下面以具體模型展示對(duì)偶單純形法的基本計(jì)算步驟及其理論.7(p65-69) TOC o 1-5 h z 例3 min fx12x2.t. x1x24x153x1x26x1, x20解(1)化為標(biāo)準(zhǔn)型max fx1 2x2 0 x3 0 x4 0 x5st. x1x2 x34x1

15、x453x1 x2 x56x1,x20顯然不存在現(xiàn)成的單位可行基(2)確定對(duì)偶單位可行基B.寫出它的增廣矩陣，并進(jìn)行初等行變換(同解變形).121004121004A100105100105310016310016變換出了一個(gè)單位基B （P3, P4, P5）,但B并不是單位可行基（因?yàn)槌?shù)列各分量不滿足非負(fù)數(shù)的要求），我們把這樣的基B叫做對(duì)偶單位可行基（其中bi不全為非負(fù)數(shù)）(3)計(jì)算12 10 01B 1A A= 100 10310 0 1B 1b b4,5, 6 T,Cb 0 ,CBb 0 ,CbB 1A C C 1,2,0,0,0 ,XbX3,X4,X5 T（4）列出初始表并進(jìn)行迭代運(yùn)

16、算在該迭代過(guò)程中，確定主元時(shí)要運(yùn)用最大比原則（因?yàn)樵摲椒ㄊ窃跈z驗(yàn)數(shù)非負(fù)的條件下進(jìn)行的）逐次迭代，使bi0,當(dāng)每一個(gè)bi都大于或等于0時(shí),得問題的最優(yōu)解，見下表表 3.3.112000初X1X2X3X4X50X3121004始0100105表0X4310016X5檢驗(yàn)數(shù)120000顯然在上表中常數(shù)列存在非負(fù)數(shù)，所以進(jìn)行第一次迭代， 通過(guò)確定主元、換基、迭代運(yùn)算，得下表:表 3.3.2迭代12000 xix2x3x4x5001x3x4xi0-510-330-101-331100-33232檢驗(yàn)數(shù)0500332進(jìn)行一次迭代后，常數(shù)列仍有負(fù)值存在，所以進(jìn)行第二次迭代.同樣通過(guò)確定主元、換基、迭代運(yùn)算，

17、得下表:表 3.3.3迭代12000 xx2x3x4x5201*2x4x101-0-5500-11-551010-556517585檢驗(yàn)數(shù)001004在迭代二中，所有的A 0,則停止迭代，得最彳解x （之之。,17,。），最優(yōu)值f 4.5 553.4 軟件法解線性規(guī)劃問題還可以用軟件來(lái)做，下面介紹用“人丁1人件件求解線性規(guī)劃問題。應(yīng)用 MATLA就化工具箱解線性規(guī)劃時(shí)，不需要把線性規(guī)劃化為標(biāo)準(zhǔn)形，其相應(yīng)的形式為：Tmin f xs.t. Ax bx 0.它的特點(diǎn)為：求目標(biāo)函數(shù)的最?。?TOC o 1-5 h z 目標(biāo)函數(shù)系數(shù)作為列矩陣f ;約 束 條 件 全 部 為 小 于 等 于 常 數(shù) ,

18、 若 約 束 條 件 中 有 等 式 約 束 以 及 變 量 的 非 負(fù) 約 束也改寫成視為 小于等于 的約束 .把約束條件的系數(shù)作為矩陣A , 把約束條件中的左端作為列矩陣b .具體求解時(shí), 首先給矩陣f , A, b 賦值 , 然后在命令窗口中 , 調(diào)用優(yōu)化程序lp .8(p32-33)例 4 min f 2x1x23x3 5x4 HYPERLINK l bookmark21 o Current Document s.t. x1 2x2 4x3 x462x1 3x2 x3 x412x1x3 x44x1 ,x2,x3,x4 0解 第一步 給矩陣f ,A,b賦值，MATLAB合矩陣賦值是逐行進(jìn)

19、行的，行之間用分號(hào)隔開，每行元素之間可以用逗號(hào) , 也可以用空格隔開. 如此例 f 2, 1,3, 5 (左上角符號(hào)“ ”是作矩陣的轉(zhuǎn)置運(yùn)A 1,2,4, 1;2,3, 1,1;1,0,1,1; 1,0,0,0;0, 1,0,0;0,0, 1,0;0,0,0, 1 ;b 6,12,4,0,0,0,0;第二步 在命令窗口調(diào)用優(yōu)化程序x lp ( f , A, b)回車以后立即執(zhí)行, 執(zhí)行完立即輸出最優(yōu)解: x 0, 2.6667, 0, 4.0若在命令窗口中接著鍵入 ans f * x , 即得最優(yōu)值為 : ans 22.667 .解線性規(guī)劃問題除了以上幾種解法外，還有其它算法，比如：橢球算法和

20、Karmarkar 算法橢球算法從理論上說(shuō)是一個(gè)重要的突破，它提供了解LPW第一個(gè)多項(xiàng)式時(shí)間算法，從而證明了線性規(guī)劃問題屬于瞰問題，但遺憾的是廣泛的實(shí)際檢驗(yàn)表明其計(jì)算效果比單純形方法差，在實(shí)際使用方法尚不能取代單純形方法 .1984 年 Karmarkar 提出了求解線性規(guī)劃問題的另一個(gè)多項(xiàng)式時(shí)間算法. 從理論上說(shuō) Karmarkar算法的復(fù)雜性比橢球方法有所降低 , 從實(shí)際計(jì)算效果來(lái)看也好得多 , 因而引起學(xué)術(shù)界的極大關(guān)注, 掀起了繼單純形方法橢球算法之后研究線性規(guī)劃的第三次高潮4 靈敏度分析在線性規(guī)劃問題中 , 把目標(biāo)函數(shù)表達(dá)式中的系數(shù)c j , 約束條件中的系數(shù)aij 和常數(shù)項(xiàng) bi 等

21、都看做固定常數(shù) , 但在實(shí)際問題中, 這些數(shù)據(jù)大多是測(cè)量, 統(tǒng)計(jì) , 評(píng)估或決策的結(jié)果. 因此 , 有必要分析, 當(dāng)這些數(shù)據(jù)發(fā)生波動(dòng)時(shí), 對(duì)目前的最優(yōu)解和最優(yōu)值, 將帶來(lái)什么影響, 這就是所謂的靈敏度分析 . 通常通過(guò)這種分析，使企業(yè)的經(jīng)營(yíng)管理者明白，當(dāng)產(chǎn)品的價(jià)格浮動(dòng)時(shí)，原有生產(chǎn)計(jì)劃是否需要調(diào)整、何時(shí)調(diào)整、如何調(diào)整最為有利例如 對(duì)于線規(guī)劃問題 min f cxs.t. Ax bx0*假設(shè)已得出最優(yōu)解x* , 靈敏度分析要解決的主要問題是: 當(dāng)數(shù)據(jù) c j , bi 或 aij 發(fā)生波動(dòng)時(shí), 在多大波動(dòng)范圍內(nèi)，當(dāng)刖的最優(yōu)解x仍保持最優(yōu)性，最優(yōu)值如何變化.本文只討論目標(biāo)函數(shù)的系數(shù)Cj變化的情形，其

22、它情形類似設(shè)目標(biāo)函數(shù)表達(dá)式中的系數(shù)向量，由C變化為c C,這里c c(c1C1,cncn)這時(shí)原最優(yōu)單純形表僅檢驗(yàn)數(shù)行需要修改，檢驗(yàn)數(shù)修改為(cBcB)B 1 A (c c) (1);目標(biāo)函數(shù)值修改為1 (cBcB)B 1b (2).若 (2) 中的檢驗(yàn)數(shù)全部非負(fù) , 則原最優(yōu)解仍為最優(yōu)解, 僅目標(biāo)函數(shù)值發(fā)生改變, 改變量為cB B 1 b . 若 (2)中的檢驗(yàn)數(shù)出現(xiàn)負(fù)數(shù) , 則可從原最優(yōu)解表( 修改檢驗(yàn)數(shù)行后) 出發(fā) , 實(shí)行原單純形迭代, 得出新的最優(yōu)解.具體操作過(guò)程, 在以下的應(yīng)用部分會(huì)充分體現(xiàn)出來(lái).5 線性規(guī)劃問題的應(yīng)用上面我們了解了求解線性規(guī)劃的一些方法原理， 但是如何將實(shí)際問題抽

23、象為數(shù)學(xué)模型， 是個(gè)關(guān)鍵 一 般應(yīng)用線性規(guī)劃建立數(shù)學(xué)模型有三個(gè)步驟：明確問題；確定目標(biāo)；列出約束條件收集資料，建立模型模型求解(最優(yōu)解) ，進(jìn)行優(yōu)化后分析生產(chǎn)管理中的應(yīng)用例54（p243-246）某工廠用刈W2兩種原料，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品.各種產(chǎn)品對(duì)原料的單位的單位消耗量如表5.1.1所示.表 5.1.1消耗（公產(chǎn)品 斤/萬(wàn)件）原料、甲乙丙丁M 132104M200212現(xiàn)有原料M118公斤、M23公斤，產(chǎn)品甲、乙、丙、丁的單位價(jià)格（指每萬(wàn)件的價(jià)格）分另J為9,8,50,19萬(wàn)元.問應(yīng)怎樣安排生產(chǎn)，才能使總收益最高 就口果產(chǎn)品丙的價(jià)格波動(dòng)，問波動(dòng)應(yīng)限制在什么范圍內(nèi)，才能使原最優(yōu)解保持最

24、優(yōu)性 ？如果產(chǎn)品丙的單位價(jià)格浮動(dòng)到54萬(wàn)元，生產(chǎn)方案應(yīng)作何改變？解1. 建立模型用X1, X2, X3, X4分別表示甲、乙、丙、丁四種產(chǎn)品的生產(chǎn)數(shù)量（單位：萬(wàn)元），則原問題的數(shù)學(xué)模型為max f 9x1 8x2 50X3 19x4st 3x1 2x2 10 x3 4x4 18一 1 c TOC o 1-5 h z 2 X3 X432Xj 0 （j 1,2,3,4）它的標(biāo)準(zhǔn)形式為max f 9x1 8x2 50 x3 19x4 0 x5 0 x6st. 3x1 2x2 10 x3 4x4 x51812x3-X4 x632Xj 0 （j 1,2, ,6）.求最優(yōu)解使用單純形法，得最優(yōu)單純形表如表

25、5.1.2表 5.1.298501900X1X2X3X4X5X6X4X3195024012/3331101236321檢驗(yàn)數(shù)42001310.33388,產(chǎn)品丁生產(chǎn)兩萬(wàn)件，產(chǎn)品甲和產(chǎn)品乙不生產(chǎn)，對(duì)應(yīng)最顯然對(duì)應(yīng)最優(yōu)生產(chǎn)方案為：產(chǎn)品丙生產(chǎn)一萬(wàn)件大收益為88萬(wàn)件.上述最優(yōu)解對(duì)應(yīng)基B ( p4,p3)101/2，這時(shí)，Cb(19,50).靈敏度分析若產(chǎn)品丙的價(jià)格波動(dòng)，即系數(shù)c3變?yōu)閏3c3，其他數(shù)據(jù)不變.令c3CbCb(19,50),這時(shí)，表5.1.2中的檢驗(yàn)數(shù)應(yīng)修改為(Cb1Cb)B 1A (cc) (19,5043132316當(dāng)且僅當(dāng)(9,8,50,19,0,0)(40,0, 1034310 41

26、三).滿足如下不等式組0,1031由此得出，當(dāng)47 C3 52,即產(chǎn)品丙的價(jià)格在247.5萬(wàn)元到52萬(wàn)元之間波動(dòng)時(shí)，原最優(yōu)解保持最1332時(shí)，新的檢驗(yàn)數(shù)全部非負(fù)88,即對(duì)應(yīng)的最大總優(yōu)性.這時(shí)目標(biāo)函數(shù)f的最優(yōu)值應(yīng)修改為(cbcb)B 1b (19,50)收益為88 萬(wàn)元.42c 、 0,這時(shí)若令X2由0值變?yōu)?3的檢驗(yàn)數(shù)行應(yīng)修改為 TOC o 1-5 h z _ 2當(dāng)產(chǎn)品丙的價(jià)格浮動(dòng)到 54萬(wàn)兀，即 4時(shí)，檢驗(yàn)數(shù)223正值，有可能提高總收益.因此應(yīng)進(jìn)行單純形法迭代.這時(shí)，表5.1.292;2,2八八1126-,0,0,333然后取X2為進(jìn)基變量，取X4為出基變量，經(jīng)變換得表5.1.3.表 5.1.398501900X1X2X3X4X5X6X2X385031093f2422001101423232檢驗(yàn)數(shù)300147293顯見，表5.1.3是最優(yōu)解表.由此得知，生產(chǎn)方案調(diào)整為：產(chǎn)品乙、丙各生產(chǎn)一萬(wàn)五千件 ，產(chǎn)品甲、丁不 生產(chǎn).對(duì)應(yīng)總U益達(dá)93萬(wàn)元.這時(shí)，若仍按原方案，生產(chǎn)產(chǎn)品丙一萬(wàn)件，生產(chǎn)產(chǎn)品丁兩萬(wàn)件，則總收益只有 92萬(wàn)件.5.2 商業(yè)規(guī)劃中的應(yīng)用例6某商業(yè)規(guī)劃處在商場(chǎng)內(nèi)要裝修I、II兩種經(jīng)營(yíng)不同商品的鋪位各若干個(gè)，已知裝修一個(gè)鋪位所需的人數(shù)及A、B兩種裝修材料的消耗