線性規(guī)劃和單純形法

線性規(guī)劃和單純形法第一頁，共七十七頁，編輯于2023年，星期三目錄線性規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法單純形法原理改進(jìn)單純形法應(yīng)用第二頁，共七十七頁，編輯于2023年，星期三目錄線性規(guī)劃實(shí)例與模型第三頁，共七十七頁，編輯于2023年，星期三實(shí)用舉例

某公司通過市場調(diào)研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進(jìn)該公司3個(gè)月內(nèi)的全部產(chǎn)品。拉桿箱生產(chǎn)需經(jīng)過原材料剪裁、縫合、定型、檢驗(yàn)和包裝4過程。通過分析生產(chǎn)過程，得出：生產(chǎn)中檔拉桿箱需要用7/10小時(shí)剪裁、5/10小時(shí)縫合、1小時(shí)定型、1/10小時(shí)檢驗(yàn)包裝；生產(chǎn)高檔拉桿箱則需用1小時(shí)剪裁、5/6小時(shí)縫合、2/3小時(shí)定型、1/4小時(shí)檢驗(yàn)包裝。由于公司生產(chǎn)能力有限，3月內(nèi)各部的最大生產(chǎn)時(shí)間為剪裁部630小時(shí)、縫合部600小時(shí)、定型部708小時(shí)、檢驗(yàn)包裝部135小時(shí)。通過市場調(diào)研部和會計(jì)部的調(diào)查核算得出結(jié)論：生產(chǎn)中檔拉桿箱的利潤是10元，高檔拉桿箱的利潤是9元。公司應(yīng)各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤最大？第四頁，共七十七頁，編輯于2023年，星期三實(shí)用舉例某公司通過市場調(diào)研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進(jìn)該公司3個(gè)月內(nèi)的全部產(chǎn)品。拉桿箱生產(chǎn)需經(jīng)過原材料剪裁、縫合、定型、檢驗(yàn)和包裝4過程。通過分析生產(chǎn)過程，得出：生產(chǎn)中檔拉桿箱需要用7/10小時(shí)剪裁、5/10小時(shí)縫合、1小時(shí)定型、1/10小時(shí)檢驗(yàn)包裝；生產(chǎn)高檔拉桿箱則需用1小時(shí)剪裁、5/6小時(shí)縫合、2/3小時(shí)定型、1/4小時(shí)檢驗(yàn)包裝。由于公司生產(chǎn)能力有限，3月內(nèi)各部的最大生產(chǎn)時(shí)間為剪裁部630小時(shí)、縫合部600小時(shí)、定型部708小時(shí)、檢驗(yàn)包裝部135小時(shí)。通過市場調(diào)研部和會計(jì)部的調(diào)查核算得出結(jié)論：生產(chǎn)中檔拉桿箱的利潤是10元，高檔拉桿箱的利潤是9元。公司應(yīng)各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤最大？可以通過線性規(guī)劃求解！第五頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃模型的建立

設(shè)生產(chǎn)中、高檔拉桿箱數(shù)量分別為：稱為決策變量。目標(biāo)函數(shù)約束條件第六頁，共七十七頁，編輯于2023年，星期三一般線性規(guī)劃模型Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1(

0) a21x1+a22x2+…+a2nxn=b2

(

0) :am1x1+am2x2+…+amnxn=bm(

0)

x1,x2,…,xn

0s.t.

為約束限制（Subjectto）的縮寫(LP)x1..xnb1..bma11…a1n…………am1…amnx=b= A=c1..cnc=其中c=(c1,c2,…,cn)，稱為價(jià)值系數(shù)向量；第七頁，共七十七頁，編輯于2023年，星期三稱為資源限制向量

X=(x1,x2,…,xn)T

稱為決策變量向量稱為技術(shù)系數(shù)矩陣(也稱消耗系數(shù)矩陣)一般線性規(guī)劃模型第八頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃模型的標(biāo)準(zhǔn)形式MaxZ=c1x1+c2x2+…+cnxnSubjectto(s.t.) a11x1+a12x2+…+a1nxn

=

b1

a21x1+a22x2+…+a2nxn

=

b2

…… am1x1+am2x2+…+amnxn=

bm

x1

0,x2

0,…,xn

0為了討論方便，把最大化、等式約束型的線性規(guī)劃稱為線性規(guī)劃的標(biāo)準(zhǔn)型，即第九頁，共七十七頁，編輯于2023年，星期三標(biāo)準(zhǔn)化原問題標(biāo)準(zhǔn)化方法目標(biāo)函數(shù)Maxf(x)Maxf(x)Minf(x)Max–f(x)約束條件引入松弛變量和人工變量引入松弛變量,不變變量不變對某個(gè)對某個(gè)是任意的

第十頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃模型的標(biāo)準(zhǔn)化例:將如下線性規(guī)劃模型標(biāo)準(zhǔn)化：minz=x1+5x2-8x3-x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值無約束。

maxz1=-x1-5x2+8x3+x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值無約束。

目標(biāo)優(yōu)化標(biāo)準(zhǔn)化第十一頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃模型的標(biāo)準(zhǔn)化Maxz2=-x1-5y2+5y3+8x3+x4s.t.2x1-3y2+3y3+x3+x4≤20-x1-2y2+2y3-3x3+x4≤

-30-2y2+2y3-2x3-3x4≤

50

x1,x3,x4,y2,y3≥0

決策變量的標(biāo)準(zhǔn)化:y2-y3=x2maxz1=-x1-5x2+8x3+x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值無約束

第十二頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃模型的標(biāo)準(zhǔn)化Maxz2=-x1-5y2+5y3+8x3+x4

s.t.2x1-3y2+3y3+x3+x4+x5=20-x1-2y2+2y3-3x3+x4+x6=

-30-2y2+2y3-2x3-3x4+x7=50

x1,x3,x4,x5,x6,x7,y2,y3≥0約束關(guān)系標(biāo)準(zhǔn)化Maxz2=-x1-5y2+5y3+8x3+x4

s.t.2x1-3y2+3y3+x3+x4≤20-x1-2y2+2y3-3x3+x4≤

-30-2y2+2y3-2x3-3x4≤

50

x1,x3,x4,y2,y3≥0

第十三頁，共七十七頁，編輯于2023年，星期三可行解:滿足所有約束條件的解x=（x1，x2，….，xn），所有可行解的集合稱為可行域?；涸O(shè)A是約束方程組的m×n階系數(shù)矩陣，秩為m，是A中階非奇異子矩陣（即），則稱是線性規(guī)劃問題的一個(gè)基矩陣，簡稱基。B中的列向量稱為基向量，與基向量對應(yīng)的變量x稱為基變量，其它變量稱為非基變量。

基本解：令非基變量值為0，由Ax=b可求出一個(gè)解，這個(gè)解x稱為基本解?；究尚薪猓簼M足非負(fù)條件的基本解稱為基本可行解。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解。線性規(guī)劃的解

第十四頁，共七十七頁，編輯于2023年，星期三可行解、基本解、基本可行解的關(guān)系可行解基本解基本可行解第十五頁，共七十七頁，編輯于2023年，星期三目錄線性規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法與基本性質(zhì)第十六頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃的圖解法當(dāng)只有兩個(gè)決策變量時(shí)，可用圖解法求解！例：用圖解法求解以下線形規(guī)劃問題。maxz=4x1+3x2

s.t.x1≤62x2≤82x1+3x2≤18x1≥0，x2≥0x1

x2

L3：2x1+3x2=18可行域L1：x1=6L2：x2=4最優(yōu)解B4x1+3x2第十七頁，共七十七頁，編輯于2023年，星期三解的特殊情況——多個(gè)最優(yōu)解第十八頁，共七十七頁，編輯于2023年，星期三解的特殊情況——無可行解第十九頁，共七十七頁，編輯于2023年，星期三解的特殊情況——無界解第二十頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃的基本性質(zhì)

X可行域內(nèi)部的點(diǎn)可行解?是最優(yōu)解?不若線性規(guī)劃有最

優(yōu)解，則最優(yōu)解必在可行域的頂點(diǎn)上達(dá)到。第二十一頁，共七十七頁，編輯于2023年，星期三凸集的概念

凸集是線性規(guī)劃中一個(gè)很重要的概念，凸集的一般定義為：如果在集合C中任意取兩個(gè)點(diǎn)x1，x2，其連線上的所有點(diǎn)也都在集合C中，則稱集合C為凸集合。用數(shù)學(xué)解析式表達(dá)為：對任意，均有，則稱C是凸集合。非凸集非凸集凸集第二十二頁，共七十七頁，編輯于2023年，星期三線性規(guī)劃的基本性質(zhì)定理2.1：線性規(guī)劃的可行域：是凸集（凸多面體）。

引理2.1：線性規(guī)劃的可行解為基本可行解的充分必要條件是x的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的，即每個(gè)正分量都是一個(gè)基變量。定理2.2：線性規(guī)劃問題的基本可行解x對應(yīng)于可行域的頂點(diǎn)

定理2.3：若線性規(guī)劃有最優(yōu)解，則最優(yōu)解必在可行域的頂點(diǎn)上達(dá)到。第二十三頁，共七十七頁，編輯于2023年，星期三目錄線性規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法單純形法原理第二十四頁，共七十七頁，編輯于2023年，星期三一、初始基本可行解的確定考慮如下形式的線性規(guī)劃問題maxz=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2(2.17）

……….am1x1+am2x2+…+amnxn≤bmx1，x2，….，xn≥0（2.18）對每個(gè)不等式約束引入一個(gè)非負(fù)松弛變量，得標(biāo)準(zhǔn)形式：maxz=c1x1+c2x2+…..+cnxns.t.a11x1+……+a1nxn+xn+1=b1a21x1+……+a2nxn+xn+2=b2（2.19）

……………..am1x1+……+amnxn+xn+m=bm

x1，x2，….，xn，xn+1，…，xn+m≥0第二十五頁，共七十七頁，編輯于2023年，星期三是線性規(guī)劃(2.19)的一個(gè)可行基。令

得由此得到一個(gè)初始基本可行解為第二十六頁，共七十七頁，編輯于2023年，星期三二、最優(yōu)性檢驗(yàn)

定理2.4：在最大化問題中，對于某個(gè)基本可行解，如果所有的，則這個(gè)基本可行解是最優(yōu)解。在最小化問題中，對于某個(gè)基本可行解，如果所有的，則這個(gè)基本可行解是最優(yōu)解。第二十七頁，共七十七頁，編輯于2023年，星期三單純形法求解步驟將所給問題化為標(biāo)準(zhǔn)形找出一個(gè)初始可行基,建立初始單純形表檢查所有檢驗(yàn)數(shù)(若全為非負(fù),則已得到最優(yōu)解,計(jì)算停止.否則繼續(xù)下一步)考察是否無解(若是,計(jì)算停止,否則繼續(xù)下一步)確定入基變量,出基變量對初始單純形表進(jìn)行單純形變換第二十八頁，共七十七頁，編輯于2023年，星期三單純形方法的一般步驟確定一個(gè)初始可行角點(diǎn)根據(jù)某種法則進(jìn)行角點(diǎn)的最優(yōu)性判斷不是最優(yōu)角點(diǎn)是最優(yōu)角點(diǎn)考察與當(dāng)前角點(diǎn)相鄰的“更好”的一個(gè)角點(diǎn)，并置為當(dāng)前角點(diǎn)。根據(jù)某種法則進(jìn)行LP的無界或不可行判斷無界或不可行還不能做出判斷求解結(jié)束第二十九頁，共七十七頁，編輯于2023年，星期三單純形法舉例解：引進(jìn)松馳變量x3,x4，化為標(biāo)準(zhǔn)形得：第三十頁，共七十七頁，編輯于2023年，星期三

4300CBXBb

x1

x2x3x4b/y00x3x42426

231024/2

320126/3

043004=4－（0×3+0×2）；3=3－（0×2+0×3）……

4300CBXBbx1x2x3x4b/y04x3x120/326/305/31-2/312/301/3

-104/301/30-4/3第三十一頁，共七十七頁，編輯于2023年，星期三

4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5

3600-1/5-6/5表中最后一行的所有檢驗(yàn)數(shù)均為非正數(shù)，表明目標(biāo)函數(shù)已達(dá)到最大值，上述表為最優(yōu)表。從表中可得到最優(yōu)解為X=（x1,x2,x3,x4）=（6，4，0，0），最優(yōu)值為Z=36

4300CBXBbx1

x2x3x4b/y04x3x120/326/305/31-2/3412/301/313

-104/301/30-4/3第三十二頁，共七十七頁，編輯于2023年，星期三單純形法的進(jìn)一步討論人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第三十三頁，共七十七頁，編輯于2023年，星期三單純形法的進(jìn)一步討論人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第三十四頁，共七十七頁，編輯于2023年，星期三單純形法的進(jìn)一步討論人工變量法故人為添加兩個(gè)單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；再用前面介紹的單純形法求解該模型，計(jì)算結(jié)果見下表。

第三十五頁，共七十七頁，編輯于2023年，星期三單純形法的進(jìn)一步討論人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0000x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第三十六頁，共七十七頁，編輯于2023年，星期三單純形法的進(jìn)一步討論人工變量法

解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解。（檢驗(yàn)數(shù)為負(fù)數(shù)或0）2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有無窮多最優(yōu)解（檢驗(yàn)數(shù)為負(fù)數(shù)或0）。3）無界解判別：某個(gè)檢驗(yàn)數(shù)>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri>0時(shí)，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個(gè)基變量為零的基本可行解。第三十七頁，共七十七頁，編輯于2023年，星期三大M法基本思想：在約束條件中增加人工變量，同時(shí)修改目標(biāo)函數(shù)，對目標(biāo)函數(shù)加上具有很大正系數(shù)M的懲罰項(xiàng)，為使人工變量不影響目標(biāo)函數(shù)取值，在迭代過程中，應(yīng)把人工變量從基變量中退出，使其成為非基變量。

其中，M是很大的正數(shù)，同時(shí)增加兩個(gè)人工變量。

不容易找到初始可行解第三十八頁，共七十七頁，編輯于2023年，星期三找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00要求最后得到的基變量中不含人工變量X1進(jìn)基，x7出基11-300MMbi/yibx1x2x3x4x5x6x7-3X340011/3-2/32/3-5/31X210100-11-211X191002/3-4/34/3-7/30001/31/3M-1/3M-2/3可以從表中移去，然后繼續(xù)求解經(jīng)過幾次變換，得到基變量為x1，x2，x3第三十九頁，共七十七頁，編輯于2023年，星期三兩階段法原理兩階段法的第一階段是用單純形法消去人工變量，即把人工變量都變?yōu)榉腔兞?，求出原問題的一個(gè)基本可行解。如果第一階段求解結(jié)果表明問題有可行解時(shí)，進(jìn)行第二階段，就是從得到的基本可行解出發(fā)，用單純形方法求原問題的最優(yōu)解。第四十頁，共七十七頁，編輯于2023年，星期三5.2退化

LP問題

有退化最優(yōu)解第四十一頁，共七十七頁，編輯于2023年，星期三單純形法計(jì)算中用θ規(guī)則確定換出變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，這就出現(xiàn)退化解。

這時(shí)換出變量xl=0，迭代后目標(biāo)函數(shù)值不變。這時(shí)不同基表示為同一頂點(diǎn)。有人構(gòu)造了一個(gè)特例，當(dāng)出現(xiàn)退化時(shí)，進(jìn)行多次迭代，而基從B1,B2，…又返回到B1，即出現(xiàn)計(jì)算過程的循環(huán)，便永遠(yuǎn)達(dá)不到最優(yōu)解。第四十二頁，共七十七頁，編輯于2023年，星期三兩階段法舉例例：第一階段：第二階段：用單純形法求得第一階段的解為：用單純形法求解規(guī)劃問題得最優(yōu)解

目標(biāo)函數(shù)的最優(yōu)解是

第四十三頁，共七十七頁，編輯于2023年，星期三ExcelSolver（規(guī)劃求解）

Excel采用了電子表格的形式，幫助管理者提高數(shù)據(jù)管理的能力，因而得以廣泛應(yīng)用。Solver插件專門用于求解帶約束的最優(yōu)化問題。Solver——“規(guī)劃求解”，可在Excel的工作表中根據(jù)對話框提示調(diào)用該項(xiàng)功能。第四十四頁，共七十七頁，編輯于2023年，星期三

可能出現(xiàn)以下情況：①進(jìn)行進(jìn)基、出基變換后，雖然改變了基，但沒有改變基本可行解（極點(diǎn)），目標(biāo)函數(shù)當(dāng)然也不會改進(jìn)。進(jìn)行若干次基變換后，才脫離退化基本可行解（極點(diǎn)），進(jìn)入其他基本可行解（極點(diǎn)）。這種情況會增加迭代次數(shù)，使單純形法收斂的速度減慢。②在特殊情況下，退化會出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形迭代將永遠(yuǎn)停留在同一極點(diǎn)上，因而無法求得最優(yōu)解。3.單純形法第四十五頁，共七十七頁，編輯于2023年，星期三

在單純形法求解線性規(guī)劃問題時(shí)，一旦出現(xiàn)這種因退化而導(dǎo)致的基的循環(huán)，單純形法就無法求得最優(yōu)解，這是一般單純形法的一個(gè)缺陷。但是實(shí)際上，盡管退化的結(jié)構(gòu)是經(jīng)常遇到的，而循環(huán)現(xiàn)象在實(shí)際問題中出現(xiàn)得較少。盡管如此，人們還是對如何防止出現(xiàn)循環(huán)作了大量研究。1952年Charnes提出了“攝動(dòng)法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”，3.單純形法第四十六頁，共七十七頁，編輯于2023年，星期三

這些方法都比較復(fù)雜，同時(shí)也降低了迭代的速度。1976年，Bland提出了一個(gè)避免循環(huán)的新方法，其原則十分簡單。僅在選擇進(jìn)基變量和出基變量時(shí)作了以下規(guī)定：①在選擇進(jìn)基變量時(shí)，在所有j

>0的非基變量中選取下標(biāo)最小的進(jìn)基；②當(dāng)有多個(gè)變量同時(shí)可作為出基變量時(shí)，選擇下標(biāo)最小的那個(gè)變量出基。這樣就可以避免出現(xiàn)循環(huán),當(dāng)然，這樣可能使收斂速度降低。3.單純形法第四十七頁，共七十七頁，編輯于2023年，星期三加載“規(guī)劃求解”如果在您的Excel中，沒有在“工具”菜單中發(fā)現(xiàn)“規(guī)劃求解”，請?jiān)谙聢D所示的界面中點(diǎn)擊“加載宏”。第四十八頁，共七十七頁，編輯于2023年，星期三加載“規(guī)劃求解”點(diǎn)擊“加載宏”后，顯示界面如下：如果列表中沒有“規(guī)劃求解”，表明您還沒有安裝該插件。這時(shí)，您需要插入MicrosoftOffice安裝盤，選擇“添加安裝”后選擇該插件的安裝。第四十九頁，共七十七頁，編輯于2023年，星期三第1步導(dǎo)入已知數(shù)據(jù)可采用‘復(fù)制粘貼’或‘直接輸入’的方式導(dǎo)入數(shù)據(jù)。第五十頁，共七十七頁，編輯于2023年，星期三第2步確定‘可變單元格’

可變單元格存放決策變量的取值，可變單元格數(shù)目等于決策變量個(gè)數(shù)圖中，規(guī)定B16、C16為可變單元格第五十一頁，共七十七頁，編輯于2023年，星期三第3步確定‘目標(biāo)單元格’

在目標(biāo)單元格中，需要填入計(jì)算目標(biāo)函數(shù)值的公式。第五十二頁，共七十七頁，編輯于2023年，星期三第4步確定‘約束單元格’

在約束單元格中，需要填入計(jì)算約束函數(shù)值的公式。第五十三頁，共七十七頁，編輯于2023年，星期三第5步調(diào)用‘規(guī)劃求解’模塊在上圖顯示的界面中，需要輸入目標(biāo)單元格、可變單元格，添加約束條件，另外還可能需要進(jìn)行選項(xiàng)設(shè)置。第五十四頁，共七十七頁，編輯于2023年，星期三第6步填寫目標(biāo)單元格和可變單元格第五十五頁，共七十七頁，編輯于2023年，星期三第7步添加約束第五十六頁，共七十七頁，編輯于2023年，星期三第8步“選項(xiàng)”設(shè)置選擇：采用線性模型，假定非負(fù)。如果求解過程在找到結(jié)果之前即達(dá)到最長運(yùn)算時(shí)間或最大迭代次數(shù)，則會彈出“顯示中間結(jié)果”對話框。第五十七頁，共七十七頁，編輯于2023年，星期三第9步保存求解結(jié)果第五十八頁，共七十七頁，編輯于2023年，星期三顯示求解結(jié)果第五十九頁，共七十七頁，編輯于2023年，星期三使用Excel求解例2.10第六十頁，共七十七頁，編輯于2023年，星期三第六十一頁，共七十七頁，編輯于2023年，星期三

合理利用線材問題：如何下料使用材最少。

配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。

投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。4.線性規(guī)劃應(yīng)用建模

一、線性規(guī)劃---第六十二頁，共七十七頁，編輯于2023年，星期三

產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。

勞動(dòng)力安排：用最少的勞動(dòng)力來滿足工作的需要。

運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。4.線性規(guī)劃應(yīng)用第六十三頁，共七十七頁，編輯于2023年，星期三

數(shù)學(xué)規(guī)劃的建模有許多共同點(diǎn)，要遵循下列原則：(1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實(shí)際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實(shí)際問題。(2)容易查找模型中的錯(cuò)誤。這個(gè)原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯(cuò)誤有：書寫錯(cuò)誤和公式錯(cuò)誤。4.線性規(guī)劃應(yīng)用第六十四頁，共七十七頁，編輯于2023年，星期三

(3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個(gè)數(shù)和約束條件的個(gè)數(shù)。這條原則的實(shí)現(xiàn)往往會與(1)發(fā)生矛盾，在實(shí)現(xiàn)時(shí)需要對兩條原則進(jìn)行統(tǒng)籌考慮。4.線性規(guī)劃應(yīng)用第六十五頁，共七十七頁，編輯于2023年，星期三

建立線性規(guī)劃模型的過程可以分為四個(gè)步驟：

(1)設(shè)立決策變量；(2)明確約束條件并用決策變量的線性等式或不等式表示；(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）；(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。4.線性規(guī)劃應(yīng)用第六十六頁，共七十七頁，編輯于2023年，星期三

例2.:明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？生產(chǎn)計(jì)劃的問題第六十七頁，共七十七頁，編輯于2023年，星期三解：設(shè)x1,x2,x3

分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。

生產(chǎn)計(jì)劃的問題第六十八頁，共七十七頁，編輯于2023年，星期三

求xi

的利潤:利潤=售價(jià)-各成本之和可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下數(shù)學(xué)模型：目標(biāo)函數(shù):Max15x1+10x2+7x3+13x4+9x5

約束條件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0

生產(chǎn)計(jì)劃的問題第六十九頁，共七十七頁，編輯于2023年，星期三

例2.:永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對B工序,只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應(yīng)如何制定產(chǎn)品加工方案？

生產(chǎn)計(jì)劃的問題第七十頁，共七十七頁，編輯于2023年，星期三解：設(shè)xijk表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量.

利潤=[（銷售單價(jià)-原料單價(jià)）×產(chǎn)品件數(shù)]之和-（每臺時(shí)的設(shè)備費(fèi)用×設(shè)備實(shí)際使用的總臺時(shí)數(shù)）之和。

生產(chǎn)計(jì)劃的問題第七十一頁，共七十七頁，編輯于2023年，星期三這樣我們建立如下的數(shù)學(xué)模型:Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123

s.t

5x111+10x2