管理科學(xué)基礎(chǔ)-1線性規(guī)劃03課件

1線性規(guī)劃問題及其數(shù)學(xué)模型

圖解法單純形法線性規(guī)劃模型的應(yīng)用線性規(guī)劃2

設(shè)備產(chǎn)品

A

B

C

D利潤（元/件）

P121402

P222043有效臺時1281612例：已知信息如右表所示，問如何安排生產(chǎn)才能獲得最大利潤？模型:maxZ=2x1+3x2

s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0線性規(guī)劃問題及其數(shù)學(xué)模型3目標(biāo)函數(shù)：約束條件：①②③價值系數(shù)技術(shù)系數(shù)限額系數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式4也可以記為如下形式：目標(biāo)函數(shù)：約束條件：5向量形式：決策變量向量價值向量資源向量系數(shù)列向量6矩陣形式：系數(shù)矩陣7特征：⑴目標(biāo)函數(shù)為求最大值；⑵所有約束條件（非負(fù)條件除外）都是等式，右端常數(shù)項大于零；⑶變量為非負(fù)。①②③線性規(guī)劃模型的標(biāo)準(zhǔn)形式8標(biāo)準(zhǔn)型轉(zhuǎn)換方式：(1)如果極小化原問題minZ=CX，則令Z'=-Z，轉(zhuǎn)為求maxZ'=-CX(2)若某個bi<0，則以－1乘該約束兩端，使之滿足非負(fù)性的要求。(3)對于≤型約束，在左端加上一個非負(fù)松弛變量，使其為等式。(4)對于≥型約束，在左端減去一個非負(fù)剩余變量，使其為等式。(5)若某決策變量xk無非負(fù)約束，令xk=x'k-x"k

，(x'k≥0,x"k≥0)。9轉(zhuǎn)換方式：

⑴目標(biāo)函數(shù)的轉(zhuǎn)換也就是：令，可得到上式。即如果是求最小值即，則可將目標(biāo)函數(shù)乘以（－1），可化為求最大值問題。10⑵約束條件的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量11⑶變量的變換例1：將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式為無約束（無非負(fù)限制）若存在取值無約束的變量，可令其中：12

解:用x4-x5替換x3，且x4,x5>=0，將第3個約束方程兩邊乘以（－1），再將最小值問題反號，變?yōu)榍笞畲笾?。?biāo)準(zhǔn)形式如下：引入變量13例2：將線性規(guī)劃問題化為標(biāo)準(zhǔn)型為無約束解：作業(yè)1將下面的線性規(guī)劃模型轉(zhuǎn)換成標(biāo)準(zhǔn)形式（標(biāo)準(zhǔn)型）15⑴可行解：滿足所有約束條件的解為可行解。所有解的集合稱為可行解的集或可行域。⑵最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解。⑶基：若B是矩陣A的一個m×m階非奇異子矩陣（∣B∣≠0），則B是一個基。則稱Pj

(1≤j≤m)為基向量?！鄕j(1≤j≤m)為基變量，其他變量為非基變量。線性規(guī)劃問題的解16

⑷基解(基本解)：非零分量的數(shù)目不大于約束方程個數(shù)m的解（對應(yīng)著一個基），最多為個。

⑸基可行解：滿足所有非負(fù)約束條件的基解

⑹可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解17一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量，但需將一般形式變成標(biāo)準(zhǔn)形式線性規(guī)劃模型的求解方法18

建立直角坐標(biāo)，圖中陰影部分及邊界上的點均為其解，是由約束條件來反映的。例一:⑴⑵⑶⑷圖解法19012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4,x2=2，有唯一最優(yōu)解，Z=14x2

x1(42)⑴⑵⑶⑷可行域20例二：例三：⑴⑵⑶無窮多最優(yōu)解⑴⑵無界解x1x1x2

x2

21⑴⑵x1x2

無可行解例四:練習(xí)122解的情況唯一解無窮多最優(yōu)解（多重最優(yōu)解）無界解無可行解有最優(yōu)解無最優(yōu)解23凸集凸集不是凸集頂點線性規(guī)劃問題的幾何意義幾個概念：1.凸集2.凸組合3.頂點24是否凸集？abcd25K是n維歐氏空間En的一個點集，若任意兩點

的連線上的所有點，則稱K為凸集。凸集：凸組合：26頂點：則稱X為K的一個頂點（或極點）。27幾個定理定理1.

若線性規(guī)劃問題存在可行域，則其可行域證明.

設(shè)28引理1.

線性規(guī)劃問題的可行解X為基可行解的充要條件是X的正分量對應(yīng)的系數(shù)列向量線性無關(guān)。幾個定理29定理2.

線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。證明.

不失一般性，設(shè)基可行解X的前m個分量為正，則分兩步證明：（1）若X不是基可行解，則它不是可行域D的頂點。根據(jù)引理1，若X不是基可行解，則其正分量對應(yīng)的系數(shù)列向量

線性相關(guān)，即存在不全為0的數(shù)使得(1-8)-μ×(1-9)：(1-8)(1-9)幾個定理30(1-8)-μ×(1-9)：(1-8)+μ×(1-9)：取當(dāng)μ充分小時，有幾個定理31（2）若X不是可行域D的頂點，則它不是基可行解。因為X不是可行域D的頂點，因此D內(nèi)存在不同的兩點設(shè)X是基可行解，對應(yīng)的向量組線性無關(guān)。當(dāng)j>m時，線性相關(guān)，矛盾！幾個定理32引理2.

若K是有界凸集，則任何一點可表示為K的頂點的凸組合。定理3.

若可行域D有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點達(dá)到最優(yōu)。幾個定理33思路：先找一個基可行解（頂點），如不是最優(yōu)，繼續(xù)尋找下一個基可行解（頂點），直到找出最優(yōu)為止。⑴線性規(guī)劃問題的可行域（非空）是凸集（凸多邊形）。（定理1）⑵若可行域是有界凸集，則最優(yōu)解一定是在凸集的某一頂點實現(xiàn)（頂點數(shù)目不超過個）（定理3）結(jié)論：(3)線性規(guī)劃如果有可行解，則一定有基可行解；如果有最優(yōu)解，則一定有基可行解是最優(yōu)解。求解線性規(guī)劃的一種有效方法（1947，丹捷格/丹齊克），該方法被譽(yù)為20世紀(jì)十大算法之一。20世紀(jì)創(chuàng)造經(jīng)濟(jì)效益最多的算法。將模型的一般形式轉(zhuǎn)化成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型從可行域中找一個基可行解，并判斷是否最優(yōu)解。如果不是，繼續(xù)尋找另一個基可行解，當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)時，得到最優(yōu)解?；舅枷雴渭冃畏?5例1：轉(zhuǎn)換成標(biāo)準(zhǔn)型：單純形法36約束條件的系數(shù)矩陣為基變量為非基變量I為單位矩陣37令：則：∴基可行解為（0，0，8，16，12）T

此時，Z=0然后，找另一個基可行解（需要將非基變量換入基變量中，并從基變量中找到一個換出變量）。如此循環(huán)下去，直到找到最優(yōu)解為止。38找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更優(yōu)的基可行解）最優(yōu)解是否循環(huán)結(jié)束其步驟總結(jié)如下：39為換入變量，令確定換出變量：為換出變量接下來將在x2與x5的位置對換，得到下式：40用高斯消去法，將的系數(shù)列向量換為單位列向量，其步驟是：結(jié)果是：41即將的系數(shù)列向量(2,0,4)T轉(zhuǎn)化為單位列向量(0,0,1)T。此時線性規(guī)劃變成：42把x2、x3、x4代入目標(biāo)函數(shù)可得：

x1有正系數(shù)表明：還有潛力可挖，目標(biāo)沒有達(dá)到最大值；此時：令得到另一個基可行解（0，3，2，16，0）T如此循環(huán)進(jìn)行，直到找到最優(yōu)為止。再迭代兩次，得到最優(yōu)解：（4，2，0，0，4）T根據(jù)上式可知所有非基變量的系數(shù)都是負(fù)數(shù)，目標(biāo)函數(shù)達(dá)到最大值。初始基可行解的確定最優(yōu)性檢驗與解的判別唯一最優(yōu)解的判別無窮多最優(yōu)解的判別無界解判別基變換確定換入變量（進(jìn)基變量）確定換出變量（出基變量或離基變量）

(*)迭代（旋轉(zhuǎn)運(yùn)算，用高斯消去法進(jìn)行初等行變換）(*)一般線性規(guī)劃模型的求解過程1.初始基可行解的確定方法：構(gòu)造單位矩陣的可行基所有約束條件是“≤”的不等式1.初始基可行解的確定常用方法：構(gòu)造單位矩陣的可行基所有約束條件是“≤”的不等式1.初始基可行解的確定約束條件是等式人造基方法人工變量1.初始基可行解的確定約束條件是等式人造基方法令非基變量為0，可得初始基解：1.初始基可行解的確定約束條件是“≥”的不等式人工變量2.最優(yōu)性檢驗與解的判別2.最優(yōu)性檢驗與解的判別（2-25）（2-26）（2-27）檢驗數(shù)2.最優(yōu)性檢驗與解的判別最優(yōu)解的判別定理無窮多最優(yōu)解的判別定理無界解的判別定理2.最優(yōu)性檢驗與解的判別無界解的判別定理證明：進(jìn)基變量的確定3.基變換選擇作為進(jìn)基變量離基變量的確定最小比值規(guī)則：3.基變換4.迭代第l個分量增廣矩陣的初等行變換主元素4.迭代主元列主元行增廣矩陣的初等行變換4.迭代代數(shù)形式的單純形法：例子

maxZ=3x1+5x2+0x3+0x4+0x52x1+x3=162x2+x4=103x1+4x2+x5=32

x3=16-2x1

x4=10-2x2x5=32-3x1-4x2

maxZ=3x1+5x2

+0x3+0x4+0x5

x3=16x4=10-2x2x5=32-4x2無關(guān)x2x22x1=162x2=103x1+4x2=32x1x24812590ABC(4,5)DX0=(0,0,10,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T不斷改進(jìn)，不斷追求完美！單純形法的基本原理最優(yōu)解解釋最優(yōu)解:X*=(4,5,8,0,0)T松弛變量解釋：X3=8,設(shè)備A有8小時剩余X4=0,條件（2）等式成立，設(shè)備B是瓶頸設(shè)備X5=0,條件（3）等式成立，設(shè)備C是瓶頸設(shè)備61（四）單純形表6263（四）單純形表64表格形式的單純形法：例題2008-9-1ByDr.HuangHuiyu65cj230000cBXBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001σj0

23000012/28/2－12/4cj230000cBXBb

x1x2x3x4x5x6000x3x4x5

σj3x23010001/42620100-1/2100100-1/2初始單純形表164000102008-9-1ByDr.HuangHuiyu66cj230000cBXBb

x1x2x3x4x5x60003x3x4x5x26216320100-1/210010-1/2400010010001/4σj-9

20000-3/46/2216/4－cj230000cBXBb

x1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412σj-13000-201/42008-9-1ByDr.HuangHuiyu67cj230000cBXBb

x1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100σj-1400-1/2-100000-201/4-13σj4－412001-201/2

10010-1/2000-412010001/42283x3x1x5x20203

x1x2x3x4x5x6bXBcB230000cj2008-9-1ByDr.HuangHuiyu68cj230000cBXBb

x1x2x3x4x5x60203x3x1x6

x2

0442001-1-1/4010001/40

000-21/210101/2-1/80σj-14000-3/2-1/80000-201/4-13σj4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203

x1x2x3x4x5x6bXBcB230000cj

maxZ=3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32

Cj比值CBXBb檢驗數(shù)jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8表格單純形法：例子162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb檢驗數(shù)jx1x2x3x4x535000檢驗數(shù)j80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最優(yōu)解:X*=(4,5,8,0,0)T，Z*=37表格單純形法：例子71

目標(biāo)函數(shù)：max,min

設(shè)規(guī)劃模型約束條件為，需加入人工變量

，而得到一個m×m的單位矩陣，即基向量組合。因人工變量為虛擬變量，且存在于初始基可行解中，需要將它們從基變量中替換出來。若基變量中沒有非零的人工變量，表示原問題有解。若當(dāng)，而還有非零人工變量時，則表示原問題無可行解。如何確定人工變量的目標(biāo)價值系數(shù)而又不影響原來目標(biāo)函數(shù)的取值?兩種方法處理：大M法和兩階段法人工變量法72如果是求最小值，人工變量在目標(biāo)函數(shù)中的系數(shù)為M（任意大的正數(shù)）；如果是求最大值，需取-M。⑴大M法如：73cj-31100MMcBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011σj-3+6M1-M1-3M0M00cBXBbx1x2x3x4x5x6x70x4103-20100-1－Mx610100-11-211x31-2010001－σj-11-M00M03M-174cj-31100MMcBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2－1x31-2010001－σj-2-10001M-1M+1cBXBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3σj20001/31/3M-1/3M-2/3∴最優(yōu)解為（4，1，9，0，0）T，Z=－275用計算機(jī)處理數(shù)據(jù)時，只能用很大的數(shù)代替M,可能造成計算機(jī)上的錯誤，故多采用兩階段法。

第一階段：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：⑵兩階段法：76對上述模型求解（單純形法），若W=0,說明問題存在基可行解，可以進(jìn)行第二個階段；否則，原問題無可行解，停止運(yùn)算。第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計算的初始純形表。例：第一階段：2008-9-1ByDr.HuangHuiyu77cj0000011cBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011σj46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－σj10-1001030x4123001-22-50x210100-11-20x31-2010000σj0000001178cj-31100cBXBbx1x2x3x4x50x4123001-241x210100-1－1x31-20100－σj-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3σj20001/31/3第二階段∴最優(yōu)解為（4，1，9，0，0）T，目標(biāo)函數(shù)Z=-279退化：計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中有一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。其特例是出現(xiàn)循環(huán),永遠(yuǎn)達(dá)不到最優(yōu)解。需用勃蘭特規(guī)則處理：⑴.選中下標(biāo)最小的非基變量為換入變量；⑵.當(dāng)θ中出現(xiàn)兩個以上最小值時，選下標(biāo)最小的基變量為換出變量。80-M0令z′=-ZminZ=－maxz′不處理減去xs加入xa加入人工變量xa加松弛變量xs約束條件兩端同乘以-1不處理令

xj

=-xj令xj

=

xj′

-xj″

xj′

≥0xj″

≥0不處理單純形法圖解法、單純形法求解

xaxs

minZmaxZ≥=≤bi<0

bi

≥0xj

≤0xj無約束xj≥0三個以上兩個新加變量系數(shù)極大或極小等式或不等式右端項取值個數(shù)建立模型根據(jù)上表列出初始單純形表A線性規(guī)劃小結(jié)：81A基變量中有非零的人工變量關(guān)于線性規(guī)劃的進(jìn)一步討論Subtitle學(xué)習(xí)要點線性規(guī)劃的目標(biāo)函數(shù)和約束條件的表達(dá)技巧了解企業(yè)管理中典型線性規(guī)劃問題的數(shù)學(xué)模型理解靈敏度分析的基本原理和經(jīng)濟(jì)意義能夠?qū)r值系數(shù)和資源數(shù)量進(jìn)行靈敏度分析計劃鏈的層次粗能力計劃定單可行不可行CRP主生產(chǎn)計劃MPS物料需求計劃MRP能力需求計劃車間作業(yè)計劃銷售計劃可行否作業(yè)統(tǒng)計與控制物料清單庫存管理外購計劃供應(yīng)商成品、在制品信息生產(chǎn)計劃大綱預(yù)測當(dāng)前條件經(jīng)營計劃產(chǎn)值計劃或利潤計劃絕對數(shù)量或增長幅度期限:年度單位:萬元大類產(chǎn)品銷售收入或臺套

產(chǎn)品品種和數(shù)量如何確定期限:年度單位:萬臺具體產(chǎn)品在具體時段的出產(chǎn)計劃合同訂單和預(yù)測轉(zhuǎn)換為生產(chǎn)任務(wù)將產(chǎn)品出產(chǎn)計劃轉(zhuǎn)換成物料需求表大類產(chǎn)品年度生產(chǎn)計劃確定產(chǎn)品的品種和數(shù)量期限:年度單位:萬臺線性規(guī)劃的適用層次某企業(yè)存在兩個供貨源（產(chǎn)地），已知原有供貨源每月的供貨能力是5萬臺產(chǎn)品，新增供貨源的生產(chǎn)能力可以滿足產(chǎn)品的需求，且兩個貨源的價格相同。有三個區(qū)域目標(biāo)市場（銷地或銷售商），各銷地每月的市場需求量為5萬臺、10萬臺、5萬臺。在分銷渠道中，擬定在2個地點中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的轉(zhuǎn)運(yùn)任務(wù)。各地之間的單位運(yùn)輸物流成本（由距離和運(yùn)輸方式?jīng)Q定）如下圖所示。應(yīng)如何選址、調(diào)運(yùn)？線性規(guī)劃的典型案例——配送中心選擇決策變量：設(shè)從供貨源到分銷中心的運(yùn)輸量為，從分銷中心到需求市場的運(yùn)輸量為。選址規(guī)劃在于二者的實際取值。如果，則不設(shè)置分銷中心；反之，則設(shè)置,其規(guī)模為如果，則不設(shè)置分銷中心；反之，則設(shè)置，其規(guī)模為目標(biāo)函數(shù)：各條路段上的實際運(yùn)輸量乘以物流運(yùn)輸?shù)膯挝毁M(fèi)用之總和最小，即存在供應(yīng)能力約束、市場需求約束、配送中轉(zhuǎn)約束，如下：線性規(guī)劃的典型案例——配送中心選擇供應(yīng)能力平衡約束：市場需求平衡約束配送中心不存留產(chǎn)品所有變量大于等于零線性規(guī)劃的典型案例——配送中心選擇例：現(xiàn)要做100套鋼架，每套需用長為2.9m，2.1m和1.5m的元鋼各一根。已知原料長7.4m，問應(yīng)如何下料，使用的原材料最省。解：最簡單做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元鋼各一根組成一套，每根原材料剩下料頭0.9m（7.4-2.9-2.1-1.5=0.9)。為了做100套鋼架，需用原材料100根，共有90m料頭。若改為用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以考慮采用。線性規(guī)劃的典型案例——合理下料為了得到100套鋼架，需要混合使用各種下料方案。設(shè)按Ⅰ方案下料的原材料根數(shù)為x1,Ⅱ方案為x2，Ⅲ方案為x3，Ⅳ方案為x4,Ⅴ方案為x5。根據(jù)表1-11的方案，可列出以下數(shù)學(xué)模型：線性規(guī)劃的典型案例——合理下料例：某建筑公司要用鋁型材作為構(gòu)架，制作100個鋁合金窗子，每個窗子需要2.8米的材料3根，1.8米的2根，1.17米的4根，0.6米的4根，原材料每根6米，怎樣下料，才能使余料最少?123456789102.810000010101.811203001101.1712200223030.603010161124合計5.775.945.946.006.005.945.745.915.805.91余料0.230.060.06000.060.260.090.200.09下料的可能方案決策x1x2x3x4x5x6x7x8x9x10線性規(guī)劃的典型案例——合理下料數(shù)學(xué)模型：設(shè)長度為2.8米的材料多余根數(shù)為s1，1.8米多余s2，1.17米多余s3，0.6米多余s4。線性規(guī)劃的典型案例——合理下料例：假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇(當(dāng)然可以擴(kuò)充到n種食品)，它們每千克所含的熱量和營養(yǎng)成分和市場價格見表2-3。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最?。烤€性規(guī)劃的典型案例——營養(yǎng)配餐問題建模：設(shè)xj為第種食品每天的購入量，則配餐問題的線性規(guī)劃模型為：線性規(guī)劃的典型案例——營養(yǎng)配餐問題例：某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。已知產(chǎn)品的規(guī)格要求，產(chǎn)品單價，每天能供應(yīng)的原材料數(shù)量及原材料單價，分別見表2-14和表2-15。該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大?

解：如以AC表示產(chǎn)品A中C的成分，AP表示產(chǎn)品A中P的成分，依次類推。表2-14線性規(guī)劃的典型案例——配料問題根據(jù)表2-14有：這里AC+AP+AH=A；BC+BP+BH=B(1-40)將(1-40)逐個代入(1-39)并整理得到線性規(guī)劃的典型案例——配料問題表2-15表明這些原材料供應(yīng)數(shù)量的限額。加入到產(chǎn)品A、B、D的原材料C總量每天不超過100kg，P的總量不超過100kg，H總量不超過60kg。表2-15線性規(guī)劃的典型案例——配料問題由此得約束條件AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60在約束條件中共有9個變量，為計算和敘述方便，分別用x1,…,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.線性規(guī)劃的典型案例——配料問題約束條件可表示為：線性規(guī)劃的典型案例——配料問題98目標(biāo)函數(shù)目的是使利潤最大，即產(chǎn)品價格減去原材料的價格為最大。產(chǎn)品價格為：50(x1+x2+x3)——產(chǎn)品A35(x4+x5+x6)——產(chǎn)品B25(x7+x8+x9)——產(chǎn)品D原材料價格為：65(x1+x4+x7)——原材料C25(x2+x5+x8)——原材料P35(x3+x6+x9)——原材料H為了得到初始解，在約束條件中加入松弛變量x10～x16，得到數(shù)學(xué)模型：線性規(guī)劃的典型案例——配料問題線性規(guī)劃模型例：某部門在今后五年內(nèi)考慮給下列項目投資，已知：項目A，從第一年到第四年每年年初需要投資，并于次年末回收本利115%；項目B，第三年初需要投資，到第五年末能回收本利125%，但規(guī)定最大投資額不超過4萬元；項目C，第二年初需要投資，到第五年末能回收本利140%，但規(guī)定最大投資額不超過3萬元；項目D，五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項目每年的投資額，使到第五年末擁有的資金的本利總額為最大?線性規(guī)劃的典型案例——投資問題

解：

(1)確定決策變量這是一個連續(xù)投資問題，與時間有關(guān)。但這里設(shè)法用線性規(guī)劃方法，靜態(tài)地處理。以xiA,xiB,xiC,xiD(i=1,2,…，5)分別表示第i年年初給項目A，B，C，D的投資額，它們都是待定的未知變量。表2-17線性規(guī)劃的典型案例——投資問題(2)投資額應(yīng)等于手中擁有的資金額

由于項目D每年都可以投資，并且當(dāng)年末即能回收本息。所以該部門每年應(yīng)把資金全部投出去，手中不應(yīng)當(dāng)有剩余的呆滯資金。因此第一年：該部門年初擁有100000元，所以有x1A+x1D=100000第二年：因第一年給項目A的投資要到第二年末才能回收。所以該部門在第二年初擁有資金額僅為項目D在第一年回收的本息x1D(1+6%)。于是第二年的投資分配是x2A+x2C+x2D=1.06x1D第三年初的資金額是從項目A第一年投資及項目D第二年投資中回收的本利總和：x1A(1+15%)及x2D(1+6%)。于是第三年的資金分配為

x3A+x3B+x3D=