《運(yùn)籌學(xué)》胡運(yùn)權(quán)-第4版-第二章--線性規(guī)劃的對(duì)偶理論及靈敏度分析

1、第二章 線性規(guī)劃的對(duì)偶理論及靈敏度分析,Operational Research( OR ),線性規(guī)劃的對(duì)偶問題與靈敏度分析,線性規(guī)劃的對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃,對(duì)偶原理,對(duì)偶問題概念：任何一個(gè)線性規(guī)劃問題都有一個(gè)伴生的線性規(guī)劃問題，稱為其“對(duì)偶”問題。對(duì)偶問題是對(duì)原問題從另一角度進(jìn)行的描述，其最優(yōu)解與原問題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶

2、線性規(guī)劃的最優(yōu)解，反之亦然。對(duì)偶理論就是研究線性規(guī)劃及其對(duì)偶問題的理論，是線性規(guī)劃理論的重要內(nèi)容之一。,問題的導(dǎo)出,,例2-1,我們引用第一章中美佳公司的例子，如表1,其線性規(guī)劃問題為：,？,假定有某個(gè)公司想把美佳公司的資源收買過來，它至少應(yīng)付出多大代價(jià)，才能使美佳公司愿意放棄生產(chǎn)活動(dòng)，出讓自己的資源？,（LP1）,問題的導(dǎo)出,,例2-1條件：出讓代價(jià)應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活動(dòng)時(shí)獲取的贏利。,y1,y2,y3分別代表單

3、位時(shí)間（h）設(shè)備A、設(shè)備B和調(diào)試工序的出讓代價(jià)。 y1,y2,y3的取值應(yīng)滿足：,,美佳公司用6h設(shè)備B和1h調(diào)試可生產(chǎn)一件家電I,贏利2元,用5h設(shè)備A,2h設(shè)備B及1h調(diào)試可生產(chǎn)一件家電Ⅱ，贏利1元,該公司希望用最小代價(jià)把美佳公司的全部資源收買過來，即：,問題的導(dǎo)出,,例2-1,綜上所述，,（LP2）,LP1和LP2兩個(gè)線性規(guī)劃問題，通常稱LP1為原問題，LP2為前者的對(duì)偶問題。,對(duì)偶問題的定義,,對(duì)稱形式的對(duì)偶問題,對(duì)偶問題的定義

4、,,對(duì)稱形式的對(duì)偶問題,對(duì)偶問題的定義,對(duì)偶問題的特點(diǎn)若原問題目標(biāo)是求極大化，則對(duì)偶問題的目標(biāo)是極小化，反之亦然原問題的約束系數(shù)矩陣與對(duì)偶問題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣極大化問題的每個(gè)約束對(duì)應(yīng)于極小化問題的一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問題的一個(gè)約束。,,,,,對(duì)偶問題的定義,一般線性規(guī)劃問題的對(duì)偶問題,,,對(duì)偶問題的定義,對(duì)偶問題對(duì)應(yīng)表,對(duì)稱形式下的對(duì)偶問題,例2－2 標(biāo)準(zhǔn)型對(duì)偶問題,對(duì)稱形式下的對(duì)偶問題,例2－3,非對(duì)偶形

5、式的原-對(duì)偶問題,例2-4 寫出下列問題的對(duì)偶問題,（2.4a）（2.4b）（2.4c）（2.4d）,對(duì)偶變量y1 y2′ y2″ y3′,先轉(zhuǎn)換成對(duì)稱形式，如下：,非對(duì)偶形式的原-對(duì)偶問題,例2-4令各約束對(duì)應(yīng)的對(duì)偶變量分別為y1、y2′、y2″、 -y3′,令y2= y2′-y2″， y3=-y3′，原問題的對(duì)偶問題為,對(duì)應(yīng)關(guān)系總結(jié),線性規(guī)劃的對(duì)偶問題與靈敏度分析,線性規(guī)劃的對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子

6、價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃,對(duì)偶問題的基本性質(zhì),單純形法計(jì)算的矩陣描述對(duì)稱形式線性規(guī)劃矩陣表達(dá)式加上松弛變量Xs后為：,其中松弛變量Xs=（xn+1,xn+2,...,xn+m）,I為m×m單位矩陣,選取I為初始基，對(duì)應(yīng)基變量為Xs。設(shè)迭代若干步后，基變量為XB，XB在初始單純形表中的系數(shù)矩陣為B。A中去掉B的若干列后剩下的列組成矩陣N。,進(jìn)一步迭代,新的單純形表如下：,對(duì)偶問題的基本性質(zhì),對(duì)應(yīng)初始單純形表

7、中的單位矩陣I，迭代后的單純形 表中為B-1初始單純形表中基變量Xs=b，迭代后的表中XB=B-1b初始單純形表中約束系數(shù)矩陣為 [A,I]=[B,N,I]， 迭代后的表中約束系數(shù)矩陣為 [B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]若初始矩陣中變量xj的系數(shù)向量為Pj，迭代后為 Pj′，則有Pj′=B-1Pj當(dāng)B為最優(yōu)基時(shí)，表中應(yīng)有 CN-CBB-1N≤0,-CBB

8、-1≤0,對(duì)偶問題的基本性質(zhì),例2-5參看例2-1中的原問題和對(duì)偶問題，并分別加上松弛變量和剩余變量，如下：,對(duì)偶變量y1y2y3,對(duì)偶變量x1x2,對(duì)偶問題的基本性質(zhì),兩個(gè)問題的最終單純形表如下：,對(duì)偶問題的基本性質(zhì),1.弱對(duì)偶性 如果xj（j=1，...，n）是原問題的可行解，yi（i=1，...，m）是其對(duì)偶問題的可行解，則恒有,對(duì)偶問題的基本性質(zhì),弱對(duì)偶性的推論：(1) 原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)

9、偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。,(2) 如原問題有可行解且目標(biāo)函數(shù)值無界(具有無界解)，則其對(duì)偶問題無可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解。注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問題無可行解時(shí)，其原問題或具有無界解或無可行解，反之亦然。,對(duì)偶問題的基本性質(zhì),(3) 若原問題有可行解而其對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無

10、可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。,對(duì)偶問題的基本性質(zhì),對(duì)偶問題的基本性質(zhì),最優(yōu)性如果 (j=1,...,n)是原問題的可行解，(i=1,...,m)是其對(duì)偶問題的可行解，且有,則 (j=1,...,n)是原問題的最優(yōu)解， (i=1,...,m)是其對(duì)偶問題的最優(yōu)解。,對(duì)偶問題的基本性質(zhì),強(qiáng)對(duì)偶性(或稱對(duì)偶定理) 若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等

11、。,對(duì)偶問題的基本性質(zhì),互補(bǔ)松弛性 在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。也即,若 >0，則有 ，即,若 ，即 ，則有,因此一定有 ，,線性規(guī)劃的對(duì)偶問題與靈敏度分析,線性規(guī)劃的對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子價(jià)

12、格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃,影子價(jià)格,對(duì)偶最優(yōu)解的經(jīng)濟(jì)含義――影子價(jià)格,代表著當(dāng)?shù)趇個(gè)右端常數(shù)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值的相應(yīng)增量。 其含義是在目前已給定的情況下，最優(yōu)目標(biāo)值隨資源數(shù)量變化的變化率； 其經(jīng)濟(jì)含義是為約束條件所付出的代價(jià)。 當(dāng)B是原問題的最優(yōu)基時(shí)，Y=CBB-1就是影子價(jià)格向量。,影子價(jià)格,資源的市場(chǎng)價(jià)格是其價(jià)值的客觀體現(xiàn)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源

13、的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。影子價(jià)格是一種邊際價(jià)格。資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。隨著資源的買進(jìn)賣出，其影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。,影子價(jià)格,生產(chǎn)過程中如果某種資源未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。影子價(jià)格反映單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。

14、一般說對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。,影子價(jià)格舉例,y1=5/3, y2=1/3 即工時(shí)的影子價(jià)格為5/3，材料的影子價(jià)格為1/3。如果目前市場(chǎng)上材料的價(jià)格低于1/3，則企業(yè)可以購(gòu)進(jìn)材料來擴(kuò)大生產(chǎn)，反之可以賣掉部分材料。 如果有客戶以高于5/3的價(jià)格購(gòu)買工時(shí)，則可以出售一些工時(shí)，反之則反,線性規(guī)劃的對(duì)偶問題與靈敏度分析,線性規(guī)劃

15、的對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃,對(duì)偶單純形法,對(duì)偶單純形法并不是求解對(duì)偶問題解的方法，而是利用對(duì)偶理論求解原問題的解的方法。求解單純形法的基本思路： 對(duì)原問題的一個(gè)基可行解，判別是否所有檢驗(yàn)數(shù)cj-zj≤0(j=1,…,n)。若是，又基變量中無非零人工變量，即找到了問題最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進(jìn)行到找出最優(yōu)解為止。,對(duì)

16、偶單純形法,對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：,可行基B 若B對(duì)應(yīng)的基本解是可行解最優(yōu)基B 若B對(duì)應(yīng)的基本解是最優(yōu)解對(duì)偶可行基B 若CBB-1是對(duì)偶問題可行解 即 C-CBB-1A≤0 或 檢驗(yàn)數(shù)≤0,對(duì)偶單純形法,對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：,對(duì)偶單純形法,對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問題：,① 找一個(gè)基，建立初始對(duì)偶單純形表，檢驗(yàn)數(shù)全部非正；② 若b列元素非負(fù)，則已經(jīng)是最優(yōu)基。反之，則取相應(yīng)行的基變量為出基變量；③ 為

17、保證能對(duì)基的可行性有所改進(jìn)，則將來的主元應(yīng)該為負(fù)數(shù)；為保證下一個(gè)基還能是對(duì)偶可行基，應(yīng)使檢驗(yàn)數(shù)仍為非正的。④ 主元變換,對(duì)偶單純形法舉例,例2－6 用對(duì)偶單純形法求解：,,,,,對(duì)偶單純形法舉例,,,,,對(duì)偶單純形法,練習(xí)：用對(duì)偶單純形法求解,線性規(guī)劃的對(duì)偶問題與靈敏度分析,線性規(guī)劃的對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃,靈敏度分析,在生產(chǎn)計(jì)劃問題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企

18、業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場(chǎng)狀況，在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計(jì)劃和最大利潤(rùn)由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。 在實(shí)際生產(chǎn)過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計(jì)劃，而在計(jì)劃實(shí)施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計(jì)劃還是不是最優(yōu)，如果不是應(yīng)該如何修訂原來的最優(yōu)計(jì)劃。更進(jìn)一步，為了防止在各類狀況發(fā)生時(shí)，來不及隨時(shí)對(duì)其變化作出反應(yīng)，即所謂“計(jì)劃不如變化快”，

19、企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項(xiàng)因素變化時(shí)，應(yīng)當(dāng)作出什么樣的反應(yīng)。,靈敏度分析的步驟,靈敏度分析的步驟可歸納如下：1.將參數(shù)的改變通過計(jì)算反映到最終單純形表上來。2.檢查原問題是否仍為可行解。3.檢查對(duì)偶問題是否仍為可行解。4.按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。,靈敏度分析,若B是最優(yōu)基，則最優(yōu)表形式如下,,靈敏度分析總是在最優(yōu)表上進(jìn)行,靈敏度分析,當(dāng)系數(shù)A，b，C發(fā)生改變時(shí)，目前最優(yōu)基是否還最優(yōu)？ 為保持目前最優(yōu)基

20、還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？假設(shè)每次只有一種系數(shù)變化①目標(biāo)系數(shù)C變化 基變量系數(shù)發(fā)生變化； 非基變量系數(shù)發(fā)生變化；②右端常數(shù)b變化③增加一個(gè)變量④增加一個(gè)約束⑤技術(shù)系數(shù)A發(fā)生變化,靈敏度分析舉例,分析cj的變化例2-7 在第一章例1的美佳公司例子中：（1）若家電Ⅰ的利潤(rùn)降至1.5元/件，而家電Ⅱ的利潤(rùn)增至2元/件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化?,,,,即美佳公司隨家電Ⅰ，Ⅱ的利潤(rùn)

21、變化應(yīng)調(diào)整為生產(chǎn)2件Ⅰ，生產(chǎn)3件Ⅱ。,,,（2）若家電Ⅰ的利潤(rùn)不變，則家電Ⅱ的利潤(rùn)在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？ 設(shè)家電Ⅱ的利潤(rùn)為（1+λ）元，如下,為保證最優(yōu)解， -1/4+1/4λ≤0， -1/2-3/2λ ≤0解得-1/3 ≤ λ≤1即家電Ⅱ的利潤(rùn)c2的變化范圍應(yīng)滿足2/3 ≤c2 ≤2,靈敏度分析舉例,分析bi的變化例2-8 在美佳公司的例子中：（1）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備

22、B每天的能力增加到32h，分析公司最優(yōu)計(jì)劃的變化；,靈敏度分析舉例,,靈敏度分析舉例,例2-8 （2）設(shè)設(shè)備A和設(shè)備B每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變。 設(shè)調(diào)試工序每天可用能力為（5+λ）h，因有,最終單純形表中b列數(shù)字為,因b>0時(shí)最優(yōu)基不變，故-1≤λ≤1。調(diào)試工序的能力應(yīng)在4h~6h之間。,,增加一個(gè)變量xj的分析 若企業(yè)在計(jì)劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單

23、位利潤(rùn)，單件資源消耗量時(shí)，可以在最優(yōu)表中補(bǔ)充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗(yàn)數(shù)行也可以由與其它列相同的方法計(jì)算得到。若檢驗(yàn)數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗(yàn)數(shù)為正時(shí)，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。,增加一個(gè)變量xj的分析,靈敏度分析舉例,增加一個(gè)變量在實(shí)際問題中反映為增加一種新的產(chǎn)品。其分析步驟為：,3. 若 σj′≤0，原最優(yōu)解不變，只需將計(jì)算得到的Pj

24、′和σj′直接寫入最終單純形表中；若σj′>0，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。,例2-9 設(shè)美佳公司又計(jì)劃推出新型號(hào)的家電Ⅲ，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為3h、4h、2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何影響。 設(shè)生產(chǎn)x6件家電Ⅲ，有c6=3，P6=（3，4，2）T,靈敏度分析舉例,靈敏度分析舉例,,最優(yōu)生產(chǎn)計(jì)劃應(yīng)為每天生產(chǎn)7/2件家電Ⅰ，51/

25、4件家電Ⅲ。,靈敏度分析舉例,分析參數(shù)aij的變化,例2-10 在美佳公司的例子中，若家電Ⅱ每件需設(shè)備A,B和調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品的利潤(rùn)變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃。設(shè)生產(chǎn)工時(shí)變化后的新家電Ⅱ的生產(chǎn)量為x2′，其中：,靈敏度分析舉例,原問題和對(duì)偶問題均為非可行解,上表中第二階段第一行的約束為：x3+4x4-24x5=-9 -x3-4x4+24x5+x

26、6=9替換后重新得表：,靈敏度分析舉例,,最優(yōu)生產(chǎn)計(jì)劃為每天生產(chǎn)11/4臺(tái)家電Ⅰ，15/8臺(tái)家電Ⅱ,靈敏度分析舉例,增加一個(gè)約束條件在企業(yè)的生產(chǎn)過程中，經(jīng)常有一些突發(fā)事件產(chǎn)生，造成原本不緊缺的某種資源變成為緊缺資源，對(duì)生產(chǎn)計(jì)劃造成影響。若把目前的最優(yōu)解代入新增加的約束，能滿足約束條件，則說明該增加的約束對(duì)最優(yōu)解不構(gòu)成影響，即不影響最優(yōu)生產(chǎn)計(jì)劃的實(shí)施。若當(dāng)前最優(yōu)解不滿足新增加的約束，則應(yīng)把新的約束添到原問題的最優(yōu)表內(nèi)新的一行中去

27、，用對(duì)偶單純形方法來進(jìn)行迭代，求出新的最優(yōu)解。,增加一個(gè)約束條件,靈敏度分析舉例,例2-11 設(shè)家電Ⅰ，Ⅱ經(jīng)調(diào)試后，還需經(jīng)過一道環(huán)境試驗(yàn)工序。家電Ⅰ每件需環(huán)境試驗(yàn)3h，家電Ⅱ每件需2h，又環(huán)境試驗(yàn)工序每天生產(chǎn)能力為12h。試分析增加該工序后的美佳公司最優(yōu)生產(chǎn)計(jì)劃。,（1）檢驗(yàn)原問題的最優(yōu)解是否仍適用。將x1=7/2，x2=3/2代入3x1+2x2≤12，27/2>12，所以不適用。（2）加入松弛變量x6，得3x1+2x2+x6

28、=12（3）單純形表求解。,靈敏度分析舉例,注：表中①′②′③′同①②③，④′=④-3×②-2×③。,線性規(guī)劃的對(duì)偶問題與靈敏度分析,線性規(guī)劃的對(duì)偶問題對(duì)偶問題的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃,參數(shù)線性規(guī)劃,當(dāng)目標(biāo)函數(shù)中cj值連續(xù)變化時(shí)，其參數(shù)線性規(guī)劃的形式為：,當(dāng)約束條件右端項(xiàng)連續(xù)變化時(shí)，其參數(shù)線性規(guī)劃的形式為：,參數(shù)線性規(guī)劃分析步驟,分析步驟：（1）令λ=0求解得最終單純形表；

29、（2）將λC*或λb*項(xiàng)反映到最終單純形表中去；（3）隨λ值的增大或減小，觀察原問題或?qū)ε紗栴}，一是確定表中現(xiàn)有解（基）允許λ值得變動(dòng)范圍，而是當(dāng)λ值的變動(dòng)超出這個(gè)范圍時(shí)，用單純形法或?qū)ε紗渭冃畏ㄇ笕⌒碌慕?；?）重復(fù)（3），一直到λ值繼續(xù)增大或減小時(shí)，表中的解（基）不再出現(xiàn)變化時(shí)為止。,參數(shù)線性規(guī)劃舉例,例2-11 分析λ值變化時(shí)，下述參數(shù)線性規(guī)劃問題最優(yōu)解的變化。,（1）令λ=0求得最優(yōu)解，并將λC*反映到最終單純形表中，得下表

30、。,表中，當(dāng)-1/5≤λ≤1時(shí)，表中解為最優(yōu)，且z=17/2+13/2 λ。,參數(shù)線性規(guī)劃舉例,（2）當(dāng)λ>1時(shí)，x4的檢驗(yàn)數(shù)>0，用單純形表繼續(xù)迭代：,當(dāng)λ≥1，表中解即為最優(yōu)解。這時(shí)有z=7+8λ。,參數(shù)線性規(guī)劃舉例,（3）當(dāng)λ≤-1/5時(shí)，變量x5的檢驗(yàn)數(shù)>0，用單純形法迭代：,當(dāng)-2≤λ≤-1/5時(shí)，z=8+4λ;當(dāng)λ≤-2時(shí)，z=0。,參數(shù)線性規(guī)劃舉例,討論題,1－7 在極大化問題的下列表中，六個(gè)常數(shù)?,?

31、1,?2, ?3,?1, ?2,之值未知（假定無人工變量），分別寫出對(duì)六個(gè)未知數(shù)的約束條件，使以下各小題關(guān)于該表的說法為真。① 現(xiàn)行解最優(yōu)，但不唯一；② 現(xiàn)行解不可行（指出哪個(gè)變量造成）；③ 一個(gè)約束條件有矛盾；④ 現(xiàn)行解是退化的基本可行解；⑤ 現(xiàn)行解可行，但問題無有限最優(yōu)解；⑥ 現(xiàn)行解是唯一最優(yōu)解；⑦ 現(xiàn)行解可行，但將x1取代x6后，目標(biāo)函數(shù)能改進(jìn)。,討論題,① 現(xiàn)行解最優(yōu)，但不唯一；② 現(xiàn)行解不可行；③ 一個(gè)約束

32、條件有矛盾；④ 現(xiàn)行解是退化的基本可行解；⑤ 現(xiàn)行解可行，但問題無有限最優(yōu)解；⑥ 現(xiàn)行解是唯一最優(yōu)解；⑦ 現(xiàn)行解可行，但將x1取代x6后，目標(biāo)函數(shù)能改進(jìn)。,?>=0; ?1<=0, ?2<=0,且至少一個(gè)為零,?<0,?0或 ?2>0,?=0,?>=0; ?2>0, ?1<=0,?>=0; ?1<0, ? 2<0,?>=0; ?1>0, ? 3>