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

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

2、 為此呼吁當(dāng)時年輕的經(jīng)濟(jì)學(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ī)劃模型就確定了。4. 線性規(guī)劃模型的經(jīng)濟(jì)意義何在？簡言之，線性規(guī)劃模型對于解決經(jīng)濟(jì)學(xué)研究的核心問題資源有效配置有比較重要的意義。它不僅為宏

3、觀或微觀的經(jīng)濟(jì)研究提供了一個有效的解決問題的平臺，而且，（曾經(jīng)）為經(jīng)濟(jì)學(xué)家提供了一個解決資源優(yōu)化配置的新的思路。不僅如此， 線性規(guī)劃在企業(yè)的運作管理、物流管理、 財務(wù)管理、 人力資源管理、戰(zhàn)略管理等諸多方面也能為管理者提供科學(xué)的決策支持。5. 線性規(guī)劃的標(biāo)準(zhǔn)形式是怎樣的？線性規(guī)劃的標(biāo)準(zhǔn)形式有三個特點：a) 約束條件都是等式；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)形式時，要注意哪幾點？要注意兩點：一是某一約束

4、條件為“”或“”形式的不等式時，應(yīng)“+”一個非負(fù)松弛變量或“”非負(fù)松弛變量；二是某個變量不滿足非負(fù)約束時，這個變量要用一到兩個非負(fù)的新變量替換，以使標(biāo)準(zhǔn)型中所有的變量均滿足非負(fù)要求。10. 什么是可行解？滿足所有約束條件的解被稱為可行解。11. 什么是可行域？所有可行解的集合被稱為可行域。12. 什么是最優(yōu)解？使目標(biāo)函數(shù)值取得最優(yōu)的可行解被稱為最優(yōu)解。13. 基的定義是什么？基是由系數(shù)矩陣A 中的線性無關(guān)的列向量構(gòu)成的可逆方陣。14. 什么是基向量？用來構(gòu)成基的列向量稱為該基的基向量。15. 一個線性規(guī)劃模型的基是唯一的嗎？一般不是。只要構(gòu)成基的列向量不完全相同，基就不同。因此，基一般可能有多

5、個，但數(shù)目最多不超過.17. 什么是基變量？一個線性規(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)的非基變量值都被令為 0，此時這個線性規(guī)劃模型標(biāo)準(zhǔn)型的約束條件部分就成為了一個僅包含基變量的線性方程組， 求解這個線性方程組就可以把此時該基對

6、應(yīng)的基變量的值求出來。這種做法求出的所有變量的值， 被稱為該基對應(yīng)的基解。一般地， 也常將這種做法得到的該基所有基變量的值稱為基解。20. 什么是基本可行解？當(dāng)某個基被選定之后，如果計算出該基的基解0, 即其中每個基變量的值都是0, 則此基解被稱為基本可行解。21. 什么是可行基？如果某個基對應(yīng)的基解是基本可行解，則該基被稱為可行基。22. 什么是退化的基本可行解？當(dāng)某個基被選定之后，如果計算出該基的基解0, 即其中每個基變量的值都是0, 則此基解被稱為基本可行解。如果這個基本可行解中某個基變量的值0, 則此基本可行解被稱為退化的基本可行解。24. 什么是最優(yōu)基？如果某個基對應(yīng)的基解是基本可行

7、解，且是使目標(biāo)函數(shù)值取得最優(yōu)的最優(yōu)解，則該基被稱為最優(yōu)基。25. 基、基變量、基解間的關(guān)系如何？基、基變量、基解間具有一一對應(yīng)的關(guān)系。當(dāng)某個基被確定下來后，該基對應(yīng)的那些基變量和非基變量就被確定下來，它們在這個基下的取值，即基解，也被確定下來。所以，當(dāng)談到某個基變量或非基變量時，一定要指出是哪個基下的基變量或非基變量，同樣地， 當(dāng)談到某個基解時，一定要指出是哪個基下的基解。26. 求基解可以利用公式是什么？求基解可以利用公式是X B =B 1b, 其中 B 是選定的基 （矩陣），B 1 是選定基的逆矩陣，b 是線性規(guī)劃模型的資源向量，即模型約束條件的右端常數(shù)項形成的列向量。這個公式可以求出所選

8、定的基對應(yīng)的基變量向量X B 的值。27. 求基解的公式 XB =B 1 b 中，基變量向量 XB 中各分量的排列順序必須與所對應(yīng)的基 B 中各基向量的排列順序一致嗎？必須保持一致。如基 B= (P 1 52B= ( x1 52TPP ), 則基變量向量Xxx) .28. 基解僅指基變量（向量） XB 的值嗎？嚴(yán)格地說，基解指的是某個基對應(yīng)的所有基變量和非基變量及其取值。由于，非基變量的值都被設(shè)定是0，故為簡便，基解也常指基變量（向量）X B 的值。29. 退化的基本可行解和基本可行解有何區(qū)別？基本可行解只要求基解X B = B 1b 0. 若某個基解 X B = B 1b 0，但 X B =

9、 B 1b 0，即存某基變量的值為0，則此時的基解被稱為退化的基本可行解。同時，此基解對應(yīng)的基被稱為退化的可行基。30. 線性規(guī)劃的幾何意義何在？線性規(guī)劃的幾何意義體現(xiàn)在如下幾點，a) 線性規(guī)劃的可行域是凸多面體，是凸集。b) 線性規(guī)劃的任意一個可行解對應(yīng)于可行域中的某個點。c) 線性規(guī)劃的基本可行解一一對應(yīng)于可行域的頂點。d) 如果線性規(guī)劃的可行域有界，則線性規(guī)劃的可行域中的任意一個（點），都可用頂點的凸組合線性表示。e)若線性規(guī)劃有最優(yōu)解，則最優(yōu)解一定可在某個基本可行解上取得，也即在可行域的某個頂點（極點）上取得。31. 圖解法適應(yīng)于哪種線性規(guī)劃問題？圖解法適應(yīng)于那種僅包含兩個變量的線性規(guī)

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

11、標(biāo)函數(shù)值無界，它沒有最優(yōu)解，圖解法停止；e) 觀察或計算出最優(yōu)解。33. 如何用圖解法求解如下線性規(guī)劃模型？Max Z=2 x1 x2x1 33x1 x212x1 x25x1, x2 0答：a) 首先，按約束條件在已建立的坐標(biāo)軸上繪出該線性規(guī)劃問題的可行域，如下圖陰影區(qū)域ABCD 所示；b) 畫出目標(biāo)函數(shù)值 z= 2 x1 x2 =0 時的目標(biāo)函數(shù)等值線；c)由目標(biāo)函數(shù)Z=2 x1 x2 做等價變形得到x2 = 2 x1 Z, 知，目標(biāo)函數(shù)值Z 即是目標(biāo)函數(shù)等值線的縱截距。在可行域內(nèi)尋求目標(biāo)值Z 取最大，即尋求目標(biāo)函數(shù)等值線的縱截距取最大。當(dāng)目標(biāo)函數(shù)等值線從過原點的位置(Z=0, 2 x1 x

12、2=0) 向右移動時，其對應(yīng)的縱截距從0 開始增大；d)這個過程直到目標(biāo)函數(shù)等值線到達(dá)可行域的頂點B 為止。e) 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 下的檢驗向量？利用公式 cBB 1A c 來求

13、。其中， A 是系數(shù)矩陣， c 是價值向量， cB 是該基基變量的目標(biāo)函數(shù)系數(shù)所形成的行向量。38. 當(dāng)一個線性規(guī)劃問題的基確定后，此時變量xj 的檢驗數(shù)j如何求？利用公式 j =cBB 1Pj cj 來求，其中， Pj 是系數(shù)矩陣 A 中變量 xj 對應(yīng)的列向量。 cj 是變量 xj 在目標(biāo)函數(shù)中的系數(shù)。39. *最優(yōu)判別定理是如何推導(dǎo)出的？僅就求 MAX的線性規(guī)劃問題且已化為標(biāo)準(zhǔn)形后的情形予以討論。設(shè) x 是任一可行解，B 是某個可行基 (B 1b 0), 此基下的基解對應(yīng)的目標(biāo)函數(shù)值為, 且檢驗向量 cBB 1A c 0,則在約束條件的左右兩邊同時乘以，得到將此式加到F=cx, 則得到因

14、為 cBB 1A c 0, x 0, 所以，. 即任一可行解x 對應(yīng)的目標(biāo)函數(shù)值F都不超過基B 的基解對應(yīng)的目標(biāo)函數(shù)值, 故，與基B 對應(yīng)的基本可行解xB= B 1b,xN=0 為最優(yōu)解（基本最優(yōu)解），此時的基B 稱為最優(yōu)基。40. 是否單純形法的初始基一定要是單位陣？這是不一定的。之所以計算時，初始基一般都用單位陣，原因有兩個：一個是單位陣樣的基確實存在；另一個是單位陣的逆矩陣最簡單易求。實際上， 從任何一個基開始單純形法的計算都是可以的。41. 單純形法的思想是怎樣的？因為只要最優(yōu)解存在，就一定可在某個基本可行基上取得。而可行基有多個，不可能用窮舉法逐一驗證，得到最優(yōu)基， 故采取換基迭代的

15、方法，從容易計算其逆的初始基對應(yīng)的單純形表開始， 逐步得到不同的可行基對應(yīng)的單純形表，直至找到最優(yōu)基對應(yīng)的單純形表為止。42. 換基迭代的過程實質(zhì)是什么？換基迭代的過程實質(zhì)上是將一個基對應(yīng)的單純形表轉(zhuǎn)到另一個基對應(yīng)的單純形表的不斷在目標(biāo)函數(shù)值上進(jìn)行改進(jìn)的過程。其核心內(nèi)容是利用初等行變換求另一個基的逆矩陣。所以，對于線性代數(shù)比較熟練的人而言，換基迭代還可直接通過初等行變換進(jìn)行。換基迭代的公式實際上就是這一過程的具體體現(xiàn)。43. 完整的單純形法的計算步驟是怎樣的？計算步驟可見下圖。44. 如何用單純形法求解如下線性規(guī)劃問題？MinZ=-2 x1-x2x1 33x1 x212x1 x25x1, x2

16、 0答：a) 引入松弛變量 x3 , x4, x5 化為標(biāo)準(zhǔn)形MinZ=-2 x1-x2s.t.x1x3=33 x x2 x4=121x1 x2 x5=5x1, x2 , x3 , x4, x5 0b) 單純形法求解過程c)最優(yōu)解為x1 =3, x2=2, x3=0, x4 =1, x5 =0.45. 每張單純形表的基是否相同？每張單純形表的基是不相同的，一個基一一對應(yīng)于一張單純形表。46. 單純形法出現(xiàn)死循環(huán)的情形如何避免？當(dāng)存在退化的基本可行解時，可能會出現(xiàn)死循環(huán)的情形。為避免此情形的發(fā)生，可運用BLAND法則，即確定誰入基時，若不唯一，則選位置最靠前的檢驗數(shù)處入基；確定主元素時，若最小比

17、值不唯一，則將取得最小比值的入基列中位置最靠前的元素，作為主元素。其它的方法還有幾種，可自己去尋找相應(yīng)的參考書。47. 如下線性規(guī)劃問題中，單純形法求解過程的每張表所顯示的基本可行解對應(yīng)于圖中可行域上的哪個點？Max Z=2 x1 x2s.t.x133 x1 x2 12 x1 x2 5x1, x2 0答：a) 單純形法求解過程b) 圖解法c) 對應(yīng)關(guān)系每張單純形表所對應(yīng)的可行基(P3, P4, P5)(P1 , P4, P5)(P1, P4, P2 )每張單純形表所顯示的基本可行解(003125)(3003 2)(3201 0)基本可行解所對應(yīng)的圖示可行域頂點DAB48. 當(dāng)在系數(shù)矩陣 A 中

18、，找不到單位陣形式的基作為初始基時，怎么辦？當(dāng)在系數(shù)矩陣A 中，找不到單位陣形式的基作為初始基時，一種直觀的思想可供借鑒構(gòu)造一個與現(xiàn)在的線性規(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.若原