線性規(guī)劃常見疑問

1、第一章 線性規(guī)劃 常見疑問解答1.     線性規(guī)劃這一運籌學(xué)重要分支的開創(chuàng)者是誰？這里，必須談到兩個著名的人物，康托洛維奇和丹捷格。1939年著名數(shù)理經(jīng)濟學(xué)者康托洛維奇發(fā)表了生產(chǎn)組織和計劃中的數(shù)學(xué)方法這一運籌學(xué)的先驅(qū)性名著，其中已提到類似線性規(guī)劃的模型和“解乘數(shù)求解法”。但是他的工作直到1960年的最佳資源利用的經(jīng)濟計算一書出版后，才得到重視。1975年，康托洛維奇與T . C . Koopmans 一起獲得了諾貝爾經(jīng)濟學(xué)獎。1947年G . B. Dantzig 在研究美國空軍軍事規(guī)劃時提出了線性規(guī)劃的模型和單純形解法，并很快引起美國著名經(jīng)

2、濟學(xué)家Koopmans的注意。Koopmans為此呼吁當(dāng)時年輕的經(jīng)濟學(xué)家要關(guān)注線性規(guī)劃。今天，單純形法及其理論已成為了線性規(guī)劃的一個重要的部分。2.    線性規(guī)劃模型的形式是什么？目標(biāo)函數(shù)和約束條件都是線性的。3.     線性規(guī)劃模型的三要素是什么？就是資源向量b，價值向量c，系數(shù)矩陣A（一般都假設(shè)A是滿秩的）。其中，資源向量b表示了稀缺資源的種類和限度；價值向量c反映了單位產(chǎn)品（廣義）所創(chuàng)造的收益或形成的成本；而系數(shù)矩陣A是現(xiàn)有生產(chǎn)技術(shù)、生產(chǎn)工藝、管理水平的具體體現(xiàn)。只要這三個要素確定了，相應(yīng)的線性規(guī)劃模型就

3、確定了。4.       線性規(guī)劃模型的經(jīng)濟意義何在？簡言之，線性規(guī)劃模型對于解決經(jīng)濟學(xué)研究的核心問題資源有效配置有比較重要的意義。它不僅為宏觀或微觀的經(jīng)濟研究提供了一個有效的解決問題的平臺，而且，（曾經(jīng)）為經(jīng)濟學(xué)家提供了一個解決資源優(yōu)化配置的新的思路。不僅如此，線性規(guī)劃在企業(yè)的運作管理、物流管理、財務(wù)管理、人力資源管理、戰(zhàn)略管理等諸多方面也能為管理者提供科學(xué)的決策支持。5.       線性規(guī)劃的標(biāo)準(zhǔn)形式是怎樣的？線性規(guī)劃的標(biāo)準(zhǔn)形式有三個特點：a) &#

4、160;    約束條件都是等式；b)       等式約束的右端項為非負(fù)的常數(shù)；c)       每個變量都要求取非負(fù)數(shù)值。下面是線性規(guī)劃標(biāo)準(zhǔn)形式的一般表達(dá)，6.線性規(guī)劃標(biāo)準(zhǔn)形的向量矩陣形式是怎樣的？線性規(guī)劃的標(biāo)準(zhǔn)形式如用向量矩陣形式可簡潔表述為：7.在將線性規(guī)劃的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，要注意哪幾點？要注意兩點：一是某一約束條件為“”或“”形式的不等式時，應(yīng)“+”一個非負(fù)松弛變量或“” 非負(fù)松弛變量；二是某個變

5、量不滿足非負(fù)約束時，這個變量要用一到兩個非負(fù)的新變量替換，以使標(biāo)準(zhǔn)型中所有的變量均滿足非負(fù)要求。8.如何將下述一般形式的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形？Min Z=x12x23x3 s.t. 2x1 x2 x3 93x1 x2 2x3 43x1 2x2 3x36x1 0, x2 0, x3任意。答：令x1' =x1，則x1=x1'（新變量替換），且x1' 0；令x3 = x3' x3”（兩個新變量替換），且x3' ，x3” 0；在第一和第二個不等式約束中分別引入松弛變量：x4，x5 ，且x4，x5 0；同時將第三個約束條件的兩邊同時乘以(1)，以將右邊常數(shù)項“

6、6”轉(zhuǎn)化為“6”。由此，上述線性規(guī)劃的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形。Max Z ' =x1' 2x23 (x3' x3") 2x1' x2 (x3' x3")x4 = 9 3x1' x22( x3' x3") x5 = 4 3x1' 2x23 ( x3' x3") = 6x1', x2 , x3', x3" , x4, x50 .9.        線性規(guī)劃求解所需的基本概念，包含哪些？包含可行解

7、、可行域、最優(yōu)解、基、基向量、基變量、非基變量、基解、基本可行解、退化的基本可行解、可行基、最優(yōu)基等，且概念間存在緊密的關(guān)系。10.     什么是可行解？滿足所有約束條件的解被稱為可行解。11.       什么是可行域？所有可行解的集合被稱為可行域。12.     什么是最優(yōu)解？使目標(biāo)函數(shù)值取得最優(yōu)的可行解被稱為最優(yōu)解。13.         基的定義是什么？基是

8、由系數(shù)矩陣A中的線性無關(guān)的列向量構(gòu)成的可逆方陣。14.    什么是基向量？用來構(gòu)成基的列向量稱為該基的基向量。15.     一個線性規(guī)劃模型的基是唯一的嗎？一般不是。只要構(gòu)成基的列向量不完全相同，基就不同。因此，基一般可能有多個，但數(shù)目最多不超過 .16.        僅有列向量排列順序不同的那些基是否被視為相同的基？是的。僅有列向量排列順序不同的那些基被視為相同的基。17.     

9、60;  什么是基變量？一個線性規(guī)劃模型的系數(shù)矩陣A中的每個列向量實際上是每個變量在所有約束條件中的系數(shù)排成列構(gòu)成的。當(dāng)某個基被選定之后，這個基所含的系數(shù)矩陣的列向量所對應(yīng)的那些變量就被稱為這個基的基變量。18.     什么是非基變量？當(dāng)某個基被選定之后，這個基所含的系數(shù)矩陣的列向量所對應(yīng)的那些變量就被稱為這個基的基變量，而其余的變量就被稱為這個基的非基變量。19.        什么是基解？在一個線性規(guī)劃模型的標(biāo)準(zhǔn)型下，當(dāng)某個基被選定之后，這個基對應(yīng)的非基變量值

10、都被令為0，此時這個線性規(guī)劃模型標(biāo)準(zhǔn)型的約束條件部分就成為了一個僅包含基變量的線性方程組，求解這個線性方程組就可以把此時該基對應(yīng)的基變量的值求出來。這種做法求出的所有變量的值，被稱為該基對應(yīng)的基解。一般地，也常將這種做法得到的該基所有基變量的值稱為基解。20.      什么是基本可行解？當(dāng)某個基被選定之后，如果計算出該基的基解0, 即其中每個基變量的值都是0, 則此基解被稱為基本可行解。21.   什么是可行基？如果某個基對應(yīng)的基解是基本可行解，則該基被稱為可行基。22.   

11、60;  什么是退化的基本可行解？當(dāng)某個基被選定之后，如果計算出該基的基解0, 即其中每個基變量的值都是0, 則此基解被稱為基本可行解。如果這個基本可行解中某個基變量的值0, 則此基本可行解被稱為退化的基本可行解。23.      什么是退化的可行基？如果某個基對應(yīng)的基解是退化的基本可行解，則該基被稱為退化的可行基。24.         什么是最優(yōu)基？如果某個基對應(yīng)的基解是基本可行解，且是使目標(biāo)函數(shù)值取得最優(yōu)的最優(yōu)解，則該基被稱為最優(yōu)

12、基。25.      基、基變量、基解間的關(guān)系如何？基、基變量、基解間具有一一對應(yīng)的關(guān)系。當(dāng)某個基被確定下來后，該基對應(yīng)的那些基變量和非基變量就被確定下來，它們在這個基下的取值，即基解，也被確定下來。所以，當(dāng)談到某個基變量或非基變量時，一定要指出是哪個基下的基變量或非基變量，同樣地，當(dāng)談到某個基解時，一定要指出是哪個基下的基解。26.      求基解可以利用公式是什么？求基解可以利用公式是XB =B1b, 其中B是選定的基（矩陣），B1是選定基的逆矩陣， b是線性規(guī)劃模型的資源向量，

13、即模型約束條件的右端常數(shù)項形成的列向量。這個公式可以求出所選定的基對應(yīng)的基變量向量XB的值。27.     求基解的公式XB =B1b中，基變量向量XB中各分量的排列順序必須與所對應(yīng)的基B中各基向量的排列順序一致嗎？必須保持一致。如基B= (P1 P5 P2), 則基變量向量XB= ( x1 x5 x2 )T .28.    基解僅指基變量（向量）XB 的值嗎？嚴(yán)格地說，基解指的是某個基對應(yīng)的所有基變量和非基變量及其取值。由于，非基變量的值都被設(shè)定是0，故為簡便，基解也常指基變量（向量）XB 的值。29. 

14、;     退化的基本可行解和基本可行解有何區(qū)別？基本可行解只要求基解XB = B1b0. 若某個基解XB = B1b0，但XB = B1b0，即存某基變量的值為0，則此時的基解被稱為退化的基本可行解。同時，此基解對應(yīng)的基被稱為退化的可行基。30.      線性規(guī)劃的幾何意義何在？線性規(guī)劃的幾何意義體現(xiàn)在如下幾點，a)       線性規(guī)劃的可行域是凸多面體，是凸集。b)    線性規(guī)

15、劃的任意一個可行解對應(yīng)于可行域中的某個點。c)     線性規(guī)劃的基本可行解一一對應(yīng)于可行域的頂點。d)  如果線性規(guī)劃的可行域有界，則線性規(guī)劃的可行域中的任意一個（點），都可用頂點的凸組合線性表示。e)     若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可在某個基本可行解上取得，也即在可行域的某個頂點（極點）上取得。31. 圖解法適應(yīng)于哪種線性規(guī)劃問題？圖解法適應(yīng)于那種僅包含兩個變量的線性規(guī)劃問題。32.     用圖解法求解線性規(guī)劃問題的步驟

16、是怎樣的？a)   首先，按約束條件在已建立的坐標(biāo)軸上繪出該線性規(guī)劃問題的可行域；如果可行域不存在，則該線性規(guī)劃問題無可行解，圖解法停止，否則轉(zhuǎn)到步驟b；b)   畫出目標(biāo)函數(shù)值 z=cx=0 時的目標(biāo)函數(shù)等值線；c)   判斷使目標(biāo)函數(shù)值得到改進的目標(biāo)函數(shù)等值線的移動方向；d)      沿所判斷的改進方向，將目標(biāo)函數(shù)等值線平行推移至可行域的邊界，且任何繼續(xù)推移將使可行域內(nèi)無點在等值線上時停住。此時，目標(biāo)函數(shù)等值線上與可行域相切的哪些點，就對應(yīng)著該線性規(guī)

17、劃問題的最優(yōu)解，轉(zhuǎn)到步驟e；如果沿所判斷的改進方向，平移目標(biāo)函數(shù)等值線的過程永無止境，則意味著該線性規(guī)劃問題目標(biāo)函數(shù)值無界，它沒有最優(yōu)解，圖解法停止；e)     觀察或計算出最優(yōu)解。33.     如何用圖解法求解如下線性規(guī)劃模型？Max Z=2x1x2 x1 3 3x1x2 12 x1x2 5 x1, x20答：a)       首先，按約束條件在已建立的坐標(biāo)軸上繪出該線性規(guī)劃問題的可行域，如下圖陰影區(qū)域ABCD所示；b) 

18、0;     畫出目標(biāo)函數(shù)值 z= 2x1x2 =0 時的目標(biāo)函數(shù)等值線；c)   由目標(biāo)函數(shù) Z=2x1x2做等價變形得到x2 = 2x1Z, 知，目標(biāo)函數(shù)值Z即是目標(biāo)函數(shù)等值線的縱截距。在可行域內(nèi)尋求目標(biāo)值Z取最大，即尋求目標(biāo)函數(shù)等值線的縱截距取最大。當(dāng)目標(biāo)函數(shù)等值線從過原點的位置(Z=0, 2x1x2=0)向右移動時，其對應(yīng)的縱截距從0開始增大；d)    這個過程直到目標(biāo)函數(shù)等值線到達(dá)可行域的頂點B為止。e)       

19、60;  B點對應(yīng)的坐標(biāo)(3, 2), 即是該線性規(guī)劃問題的最優(yōu)解。34.    如何實現(xiàn)求最大值的線性規(guī)劃問題與求最小值的線性規(guī)劃問題的相互轉(zhuǎn)化？ 一般而言，只須將求最小值的線性規(guī)劃問題的目標(biāo)函數(shù)系數(shù)反號，并將符號“MIN”轉(zhuǎn)換為“MAX”就可將其轉(zhuǎn)化為求最大值的線性規(guī)劃問題。反之，只須將求最大值的線性規(guī)劃問題的目標(biāo)函數(shù)系數(shù)反號，并將符號“MAX”轉(zhuǎn)換為“MIN”就可將其轉(zhuǎn)化為求最小值的線性規(guī)劃問題。35.  如何求一個線性規(guī)劃問題某個基B下的檢驗向量？利用公式cBB1Ac來求。其中，A是系數(shù)矩陣，c是價值向量，cB是該基基變量的目

20、標(biāo)函數(shù)系數(shù)所形成的行向量。36.    當(dāng)求一個線性規(guī)劃問題某個基B下的檢驗向量時，如何寫出公式cBB1Ac 中的cB 向量？cB是該基基變量的目標(biāo)函數(shù)系數(shù)所形成的行向量，其分量排列順序必須與所對應(yīng)的基B中各基向量的排列順序一致，也即與此時基變量向量XB中各分量的排列順序一致。如基B= (P1 P5 P2), 則基變量向量XB= ( x1 x5 x2 )T, cB= ( c1 c5 c2 ). 37.     求最大值和求最小值的線性規(guī)劃問題，其最優(yōu)判別定理有何區(qū)別？其區(qū)別主要體現(xiàn)在檢驗向量上。當(dāng)線性規(guī)劃

21、模型的目標(biāo)函數(shù)為MAX Z 時，對于某可行基B ( B1b0 ) , 若檢驗向量cBB1Ac0, 則與基B對應(yīng)的基本可行解xB= B1b, xN=0為最優(yōu)解（基本最優(yōu)解），此時的基B稱為最優(yōu)基。當(dāng)線性規(guī)劃模型的目標(biāo)函數(shù)為MIN Z 時，對于某可行基B ( B1b0 ) , 若檢驗向量 cBB1Ac0, 則與基B對應(yīng)的基本可行解xB= B1b, xN=0為最優(yōu)解（基本最優(yōu)解），此時的基B稱為最優(yōu)基。38.   當(dāng)一個線性規(guī)劃問題的基確定后，此時變量 xj 的檢驗數(shù) sj 如何求？利用公式sj =cBB1Pjcj 來求，其中，Pj是系數(shù)矩陣A中變量 xj 對應(yīng)的列向量。cj 是

22、變量 xj 在目標(biāo)函數(shù)中的系數(shù)。39.     *最優(yōu)判別定理是如何推導(dǎo)出的？僅就求MAX的線性規(guī)劃問題且已化為標(biāo)準(zhǔn)形后的情形予以討論。設(shè)x是任一可行解，B是某個可行基(B1b0), 此基下的基解對應(yīng)的目標(biāo)函數(shù)值為 , 且檢驗向量cBB1Ac0, 則在約束條件的左右兩邊同時乘以 ，得到將此式加到F=cx, 則得到因為cBB1Ac0, x0, 所以， . 即任一可行解x對應(yīng)的目標(biāo)函數(shù)值F都不超過基B的基解對應(yīng)的目標(biāo)函數(shù)值 , 故，與基B對應(yīng)的基本可行解xB= B1b, xN=0為最優(yōu)解（基本最優(yōu)解），此時的基B稱為最優(yōu)基。40.  &#

23、160;    是否單純形法的初始基一定要是單位陣？這是不一定的。之所以計算時，初始基一般都用單位陣，原因有兩個：一個是單位陣樣的基確實存在；另一個是單位陣的逆矩陣最簡單易求。實際上，從任何一個基開始單純形法的計算都是可以的。41.     單純形法的思想是怎樣的？因為只要最優(yōu)解存在，就一定可在某個基本可行基上取得。而可行基有多個，不可能用窮舉法逐一驗證，得到最優(yōu)基，故采取換基迭代的方法，從容易計算其逆的初始基對應(yīng)的單純形表開始，逐步得到不同的可行基對應(yīng)的單純形表，直至找到最優(yōu)基對應(yīng)的單純形表為止。42. 

24、0;換基迭代的過程實質(zhì)是什么？換基迭代的過程實質(zhì)上是將一個基對應(yīng)的單純形表轉(zhuǎn)到另一個基對應(yīng)的單純形表的不斷在目標(biāo)函數(shù)值上進行改進的過程。其核心內(nèi)容是利用初等行變換求另一個基的逆矩陣。所以，對于線性代數(shù)比較熟練的人而言，換基迭代還可直接通過初等行變換進行。換基迭代的公式實際上就是這一過程的具體體現(xiàn)。43.    完整的單純形法的計算步驟是怎樣的？ 計算步驟可見下圖。44.     如何用單純形法求解如下線性規(guī)劃問題？Max Z=2x1x2 x1 3 3x1x2 12 x1x2 5 x1, x20答：a) &

25、#160;     引入松弛變量x3, x4, x5化為標(biāo)準(zhǔn)形Max Z=2x1x2 s.t. x1 x3 =3 3 x1x2 x4 =12 x1x2 x5 =5 x1, x2 , x3, x4, x50b)  單純形法求解過程c)    最優(yōu)解為x1=3, x2=2, x3=0, x4=1, x5=0.45.     每張單純形表的基是否相同？每張單純形表的基是不相同的，一個基一一對應(yīng)于一張單純形表。46.     

26、;                                          單純形法出現(xiàn)死循環(huán)的情形如何避免？當(dāng)存在退化的基本可行解時，可能會出現(xiàn)死循環(huán)的情形。為避免此情形的發(fā)生，

27、可運用BLAND法則，即確定誰入基時，若最小負(fù)檢驗數(shù)不唯一，則選位置最靠前的檢驗數(shù)處入基；確定主元素時，若最小比值不唯一，則將取得最小比值的入基列中位置最靠前的元素，作為主元素。其它的方法還有幾種，可自己去尋找相應(yīng)的參考書。47.      如下線性規(guī)劃問題中，單純形法求解過程的每張表所顯示的基本可行解對應(yīng)于圖中可行域上的哪個點？Max Z=2x1x2s.t. x1 3 3 x1x2 12 x1x2 5 x1, x20答：a)      單純形法求解過程b)  &#

28、160; 圖解法c)           對應(yīng)關(guān)系每張單純形表所對應(yīng)的可行基(P3, P4, P5)(P1, P4, P5)(P1, P4, P2)每張單純形表所顯示的基本可行解(0 0 3 12 5)(3 0 0 3 2)(3 2 0 1 0)基本可行解所對應(yīng)的圖示可行域頂點DAB48.     當(dāng)在系數(shù)矩陣A中，找不到單位陣形式的基作為初始基時，怎么辦？當(dāng)在系數(shù)矩陣A中，找不到單位陣形式的基作為初始基時，一種直觀的思想可供借鑒構(gòu)造一個與現(xiàn)在的

29、線性規(guī)劃有密切關(guān)系的新的線性規(guī)劃問題，通過求解這個新的線性規(guī)劃問題，從而找出原線性規(guī)劃的最優(yōu)解。這種思想產(chǎn)生了兩種典型做法：大M法、兩階段法，統(tǒng)稱人工變量法。49.    大M法的參數(shù)M 表示的是無窮大的數(shù)嗎？M在計算時，可看作一個非常大的參數(shù)（非嚴(yán)格的說法，僅為便于檢驗數(shù)含M 時值的正負(fù)判斷），但M并不是無窮大，理論上可以證明，M只要取到某個數(shù)值以上就可以了。50.   大M法的解與原線性規(guī)劃問題解的關(guān)系是什么？大M法的解與原線性規(guī)劃問題解的關(guān)系是    i.   

30、0;  若原線性規(guī)劃問題有最優(yōu)解X*， 則 是線性規(guī)劃問題（大M法）的最優(yōu)解。   ii.       若線性規(guī)劃問題（大M法）有最優(yōu)解 ，則X*是原線性規(guī)劃問題（L）的最優(yōu)解。 iii.       若線性規(guī)劃問題（大M法）沒有最優(yōu)解，則原線性規(guī)劃問題也無最優(yōu)解。 iv.     若線性規(guī)劃問題（大M法）有最優(yōu)解，但其最優(yōu)解 ，則原線性規(guī)劃問題也無最優(yōu)解。51.     如何用大M法求解如下的線性規(guī)劃問題？Min Z=2x13x2x3s.t. x14x22x383x12x2 6x1, x2 , x30答：a)         原問題的標(biāo)準(zhǔn)形式如下，Min Z=2x13x2x3s.t. x14x22x3x4 83x12x2 x56x1, x2 , x3, x4 , x50顯然，該線性規(guī)劃問題沒有單位陣樣的初始基。b)  &#