管理運(yùn)籌學(xué)第02章線性規(guī)劃簡介

1、管理運(yùn)籌學(xué)第2章 線性規(guī)劃簡介 線性規(guī)劃是運(yùn)籌學(xué)中研究最早，理論和算法比較成熟的一個(gè)重要分支，其應(yīng)用十分廣泛。早在1939年，前蘇聯(lián)的數(shù)學(xué)家康托洛維奇（1975年諾貝爾經(jīng)濟(jì)學(xué)獲得者）就提出了生產(chǎn)組織和管理中的線性規(guī)劃模型。20世紀(jì)40年代末，美國的Dantzig提出了求解一般線性規(guī)劃的單純形方法。Charnes對于線性規(guī)劃的理論和應(yīng)用也作出了突出的貢獻(xiàn)。目前可供計(jì)算大規(guī)模線性規(guī)劃問題的計(jì)算機(jī)軟件也較為成熟。因此，線性規(guī)劃在工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事行動和科學(xué)研究的各個(gè)方面都得到了重要的應(yīng)用。2.1 線性規(guī)劃模型在了解線性規(guī)劃的理論和應(yīng)用前，必須先對線性規(guī)劃模型有一個(gè)形象的映像。這一節(jié)將繼續(xù)緒論

2、中的討論，首先介紹如何將真實(shí)問題轉(zhuǎn)化為數(shù)學(xué)模型。下面通過兩個(gè)示例（最優(yōu)投資組合問題和投資決策問題）來介紹這一問題?！纠?-1】一個(gè)投資者希望用一定數(shù)量的資金進(jìn)行投資。他對10種不同的股票進(jìn)行投資，并估計(jì)在1年內(nèi)投資的收益。表2-1給出了每種股票的國別、風(fēng)險(xiǎn)類別（R為高風(fēng)險(xiǎn)，N為低風(fēng)險(xiǎn)）和期望投資收益率（ROI）。投資者確定了某些約束條件。為了分?jǐn)傦L(fēng)險(xiǎn)，他希望對每種股票的投資最多占總資金的30。進(jìn)一步，他希望資金的一半能夠投資在北美的股票和最多 是高風(fēng)險(xiǎn)投資。這些資金應(yīng)該怎樣在各種股票中進(jìn)行分配才能達(dá)到最大化的收益的目的呢？2.1 線性規(guī)劃模型編號描述國別風(fēng)險(xiǎn)類型期望收益率1國庫券加拿大N52硬

3、件美國R173劇院美國R264電信美國R125釀酒英國N86高速公路法國N97汽車德國N78銀行盧森堡N69軟件印度R3110電子日本R21表2-1 股票的國別和估計(jì)投資收益列表2.1 線性規(guī)劃模型解：為了構(gòu)建數(shù)學(xué)模型，首先要確定問題的解中包含的決策變量：在當(dāng)前的案例中，希望知道整個(gè)投資中每種股票的投資數(shù)量。因此，定義決策變量 表示股票 在投資資金中所占的比例。這也就意味著所有變量都必須是一個(gè)在0和1之間的分?jǐn)?shù)（其中1代表整個(gè)資金的100）。事實(shí)上，每個(gè)變量都有一個(gè)最大值約束，即投資者期望的投資每種股票最多占整個(gè)資金的30。以下約束條件建立了所有變量的邊界：將 作為股票 的期望ROI，在這里表

4、示：2.1 線性規(guī)劃模型投資者希望將所有的資金都進(jìn)行投資，也就是說不同股票的分?jǐn)?shù)之和必須為100。這可以表達(dá)為以下等式約束：現(xiàn)在仍然需要兩個(gè)約束條件來表達(dá)投資者的特殊要求。至多1/3的資金是高風(fēng)險(xiǎn)股票，即投資到這個(gè)類型股票的資金之和不能超過整個(gè)資金的1/3：投資者同樣堅(jiān)持對北美的股票的投資最少50：這兩個(gè)約束條件為不等式約束。2.1 線性規(guī)劃模型投資者的目標(biāo)是最大化所有股票投資的收益，也就是說最大化下面的表達(dá)式：這就是數(shù)學(xué)模型的目標(biāo)函數(shù)?？偨Y(jié)以上不同部分，可以得到以下整個(gè)數(shù)學(xué)模型的表達(dá)式：2.1 線性規(guī)劃模型通過對這個(gè)問題的解讀，已經(jīng)將以上的模型建立起來了。其中，“maximize”表示最大化

5、。S.t.是英文“subject to”的縮寫，“使得”的意思。下面來回憶一下整個(gè)建模過程和線性規(guī)劃的一些特點(diǎn)：（1）全面了解問題。（2）描述目標(biāo)。（3）描述約束條件。（4）定義決策變量。（5）用決策變量寫出目標(biāo)和約束條件。2.1 線性規(guī)劃模型以上問題就是線性規(guī)劃模型或者線性規(guī)劃。正如前面所述，該問題有目標(biāo)和約束條件，這是所有線性規(guī)劃所共有的特點(diǎn)。并且它的目標(biāo)函數(shù)和約束條件都是關(guān)于決策變量的線性函數(shù)。線性函數(shù)是指函數(shù)中的每個(gè)變量都是分離的并且冪次為1。在剛才的模型中，目標(biāo)函數(shù)是線性函數(shù)，因?yàn)樗械臎Q策變量都是分離的，并且都是一次冪。約束條件的左邊都是線性函數(shù)，因此稱此問題為線性規(guī)劃。線性規(guī)劃有

6、3個(gè)基本的假設(shè)：比例性、可加性和可分性。比例性是指目標(biāo)函數(shù)值和約束條件所對應(yīng)的資源值與決策變量值成比例?？杉有允侵改繕?biāo)函數(shù)的值和使用資源總量分別可以通過匯總所有的決策變量對目標(biāo)函數(shù)的貢獻(xiàn)和各個(gè)決策變量使用資源數(shù)量而得到?？煞中允侵笡Q策變量是連續(xù)的。非負(fù)條件和可分性假設(shè)意味著決策變量可以是大于或者等于零的一切數(shù)值。2.1 線性規(guī)劃模型【例2-2】 某公司有100萬的資金可供投資。該公司有六個(gè)可選的投資項(xiàng)目，其各自的數(shù)據(jù)如表2-2所示：表2-2 六個(gè)可選投資項(xiàng)目的有關(guān)數(shù)據(jù)投資項(xiàng)目風(fēng)險(xiǎn)（）紅利（）增長率（）信用度118422426571031091224478105126154688862.1 線性

7、規(guī)劃模型該公司想達(dá)到的目標(biāo)為：投資風(fēng)險(xiǎn)最小，每年的紅利至少為6.5萬元，最低平均增長率為12，最低平均信用度為7。解：首先面對這一問題，要抓住決策變量、目標(biāo)以及約束條件。(1)決策變量：本問題的決策變量是在每種投資項(xiàng)目上的投資額。設(shè)Xi為項(xiàng)目i的投資額( )。(2)目標(biāo)函數(shù)：本問題要求總投資最小，即：2.1 線性規(guī)劃模型(3)約束條件：本問題共有5個(gè)約束條件。這些約束可以表示為：A.各項(xiàng)目投資總額為100萬； B.每年的紅利至少為6.5萬： C.最低平均增長率為12： D.最低平均信用度為7： E.非負(fù)約束： 2.1 線性規(guī)劃模型于是得到以下的線性規(guī)劃模型：這是一個(gè)典型的成本（或者風(fēng)險(xiǎn)）最小化

8、問題。模型的意義是在給定的限制條件下，求使得目標(biāo)函數(shù)達(dá)到最小時(shí)的每個(gè)項(xiàng)目投資額。可以看到，以上問題是線性規(guī)劃模型。該問題有目標(biāo)和約束條件，其目標(biāo)函數(shù)和約束條件都是決策變量的線性函數(shù)，也滿足線性規(guī)劃的3個(gè)基本假設(shè)。2.2 線性規(guī)劃圖解法對模型中只含有2個(gè)變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解。通過圖解法，可以對線性規(guī)劃問題及其求解過程有一個(gè)直觀的認(rèn)識，便于建立N維空間中線性規(guī)劃問題的概念，同時(shí)幫助讀者更好地理解求解一般線性規(guī)劃問題的單純形法的思路。2.2 線性規(guī)劃圖解法2.2.1 線性規(guī)劃問題圖解法的步驟為了便于理解，下面將通過抽象出來的數(shù)學(xué)規(guī)劃模型來具體說明線性規(guī)劃問題圖解法的步驟

9、，以便理解?！纠?-3】 考慮只有兩個(gè)變量的線性規(guī)劃問題，用圖解法解答：max z=x1+3x22.2 線性規(guī)劃圖解法1.在平面上建立直角坐標(biāo)系2.根據(jù)圖示約束條件，找出可行域3.圖示目標(biāo)函數(shù)4.尋找最優(yōu)解最優(yōu)解的目標(biāo)函數(shù)值為：2.2 線性規(guī)劃圖解法例2-3的線性規(guī)劃問題的可行域如圖2-1中陰影部分所示。2.2 線性規(guī)劃圖解法2.2.1 線性規(guī)劃問題圖解法的步驟1.有唯一的最優(yōu)解2.有無窮多最優(yōu)解3.無界解4.無解，或無可行解2.2 線性規(guī)劃圖解法以上幾種情況的圖示見圖2-2：2.3 線性規(guī)劃的基本概念2.3.1 線性規(guī)劃問題的標(biāo)準(zhǔn)形式由于目標(biāo)函數(shù)和約束條件在內(nèi)容與形式上的差別，導(dǎo)致線性規(guī)劃問

10、題表達(dá)多種多樣，為了便于討論線性規(guī)劃問題的求解方法和解的性質(zhì)，需要規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形式。如果一個(gè)線性規(guī)劃問題滿足以下條件，就稱為標(biāo)準(zhǔn)形式的線性規(guī)劃問題：(1)求目標(biāo)函數(shù)的最大值;(2)所有變量均要求取非負(fù)值;(3)所有的約束條件（變量非負(fù)約束除外）必須為等式;(4)約束條件右端常數(shù)項(xiàng)bi全為非負(fù)值。2.2 線性規(guī)劃圖解法具有n個(gè)變量的線性規(guī)劃問題的標(biāo)準(zhǔn)形式如下：2.2 線性規(guī)劃圖解法 標(biāo)準(zhǔn)形式的矩陣表達(dá)式如下： max zCTX AXb X0其中， ， ， ，s.t.2.3 線性規(guī)劃的基本概念對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，總可以通過以下的變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。（1）極小化目標(biāo)函數(shù)

11、的問題：（2）約束條件不為等式的問題：（3）變量無符號限制的問題：（4）變量小于等于零的問題：2.3 線性規(guī)劃的基本概念2.3.2 線性規(guī)劃問題的解 在圖解法中，已經(jīng)比較直觀地討論了線性規(guī)劃問題的可行解和最優(yōu)解等概念，但圖解法無法解決三個(gè)及其三個(gè)變量以上的線性規(guī)劃問題，為了用代數(shù)方法求得可行域的極點(diǎn)，還需要引入以下一些有關(guān)線性規(guī)劃可行域和解的概念。定義2.1 在n維空間中，滿足條件：ai1x1+ai2x2+ainxn=bi的點(diǎn)集X=(x1，x2，xn)T稱為一個(gè)超平面。定義2.2 滿足條件ai1x1+ai2x2+ainxn（或）bi的點(diǎn)集X=(x1，x2，xn)T稱為n維空間中的一個(gè)半空間。2

12、.3 線性規(guī)劃的基本概念定義2.3 有限個(gè)半空間的交集，即同時(shí)滿足以下條件的非空點(diǎn)集： a11x1+a12x2+a1nxn（或）b1a21x1+a22x2+a2nxn（或）b2am1x1+am2x2+amnxn（或）bm稱為n維空間中的一個(gè)多面體。2.3 線性規(guī)劃的基本概念定義2.4 線性規(guī)劃的基：對于線性規(guī)劃的約束條件AX=bX0其中A為mn的矩陣，nm，秩A=m，b為m1向量。設(shè)B是A矩陣中的一個(gè)非奇異的mm子矩陣，則稱B為線性規(guī)劃的一個(gè)基。定義2.5 線性規(guī)劃問題的基解、基可行解和可行基：線性規(guī)劃的解:稱為線性規(guī)劃與基B對應(yīng)的基解。2.4 線性規(guī)劃的計(jì)算機(jī)求解2.4.1 用Excel“規(guī)

13、劃求解”功能求解線性規(guī)劃1.在Excel電子表格中建立線性規(guī)劃模型2.利用Excel“規(guī)劃求解”功能求解線性規(guī)劃問題（1）“Set Target”（設(shè)置目標(biāo)單元格）：在這一欄中，輸入表示目標(biāo)函數(shù)值的單元格地址“B10”(也可以直接單擊B10單元格)。（2）“Equal to”（等于）：選中“min”;（3）在“By changing cells:”中輸入：B4:G4表示決策變量的位置。（4）在“subject to the constraints”一欄中通過“Add”添加約束條件。2.4 線性規(guī)劃的計(jì)算機(jī)求解（5）單擊“Options”按鈕，在彈出的“Solver Options”對話框中，設(shè)

14、置求解運(yùn)算中的有關(guān)參數(shù)。本問題需要選擇“Assume Linear Model”和“Assume Non-Negative”。這是采用線性模型和假定非負(fù)的復(fù)選框，單擊確定，如圖26所示：（6）單擊左上角的“Solve”按鈕，則開始進(jìn)行規(guī)劃求解。（7）在彈出的“Solver Results”對話框中（注意：當(dāng)模型沒有可行解或者目標(biāo)值為無窮的時(shí)候，規(guī)劃求解結(jié)果的內(nèi)容將不同），選中“keep Solver Solution”,保存結(jié)果，單擊“OK”，如圖2-7所示。2.4 線性規(guī)劃的計(jì)算機(jī)求解2.4.2 用LINDO/LINGO求解線性規(guī)劃問題1.LINDO軟件求解線性規(guī)劃安裝好LINDO軟件包以后

15、，點(diǎn)擊執(zhí)行文件。此時(shí)會彈出LINDO軟件的空白對話框。在空白對話框中就可以直接書寫命令了。下面給出其結(jié)果的一般解釋（劃線的部分表示需要的求解結(jié)果）：“LP OPTIMUM FOUND AT STEP 3”表示LINDO 在（用單純形法）3次迭代或旋轉(zhuǎn)后得到最優(yōu)解?！癘BJECTIVE FUNCTION VALUE 1) 8.25”表示最優(yōu)目標(biāo)值為8.25?！癡ALUE”給出最優(yōu)解中各變量的值。2.4 線性規(guī)劃的計(jì)算機(jī)求解要得到以上結(jié)果，必須遵循以下簡單的軟件規(guī)則：（） 目標(biāo)函數(shù)及各約束條件之間一定要有“Subject to (ST) ”分開。（） 變量名不能超過個(gè)字符。（） 變量與其系數(shù)間可以有空格，單不能有任何運(yùn)算符號（如乘號“”等）。（） 要輸入=約束，相應(yīng)以代替即可。（） 一般LINDO 中不能接受括號“（）“和逗號“，“，例：400(X1+X2) 需寫成400X1+400X2；10,000 需寫成10000。（） 表達(dá)式應(yīng)當(dāng)已