第二章線性規(guī)劃

第二章線性規(guī)劃第一頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§1對(duì)線性規(guī)劃的回顧線性規(guī)劃定義：求一組變量x1、x2、…、xn的值，使之滿足關(guān)于這組變量的若干個(gè)線性等式或不等式的約束條件，而且使這組變量的一個(gè)線性函數(shù)取到極大值(或極小值)。這些變量稱為決策變量，所要優(yōu)化的函數(shù)稱為目標(biāo)函數(shù)，決策變量是取實(shí)數(shù)值的連續(xù)變量。這樣的問(wèn)題稱為線性規(guī)劃。線性規(guī)劃模型的結(jié)構(gòu)目標(biāo)函數(shù)：max，minmaxz(minf)=∑cjxj

約束條件：≥,=,≤∑aijxj≤(=,≥)bi(i=1,2,…m)變量符號(hào)：≥0,unr,≤0xj≥0(j=1,2,…n)第二頁(yè)，共五十六頁(yè)，編輯于2023年，星期四線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式（標(biāo)準(zhǔn)型）目標(biāo)函數(shù)求最大值函數(shù)約束條件全為等式?jīng)Q策變量全為非負(fù)函數(shù)約束條件右端項(xiàng)全為非負(fù)§1對(duì)線性規(guī)劃的回顧第三頁(yè)，共五十六頁(yè)，編輯于2023年，星期四下述5種情況如何化為標(biāo)準(zhǔn)型？1.約束條件為不等式2.目標(biāo)函數(shù)取最小值3.xj為自由變量4.資源系數(shù)bi<05.m≥n§1對(duì)線性規(guī)劃的回顧第四頁(yè)，共五十六頁(yè)，編輯于2023年，星期四非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式總結(jié)線性規(guī)劃模型化為標(biāo)準(zhǔn)形式變量Xj≥0不變Xj≤0令Xj*

=-Xj,則Xj*

≥0Xj無(wú)約束令Xj*--Xj*’=Xj,則Xj*,Xj*’

≥0約束條件右端項(xiàng)bi≥0不變bi<0約束式兩端同乘以”-1”形式ai1x1+…+ainxn=bi不變ai1x1+…+ainxn≤biai1x1+…+ainxn+xsi=biai1x1+…+ainxn≥biai1x1+…+ainxn-xri=bi目標(biāo)函數(shù)maxz=c1x1+…+cnxn不變minz=c1x1+…+cnxn令z*=-z,化為求maxz*=-c1x1-…-cnxn§1對(duì)線性規(guī)劃的回顧第五頁(yè)，共五十六頁(yè)，編輯于2023年，星期四線性規(guī)劃問(wèn)題解的概念可行解：滿足函數(shù)約束條件和非負(fù)約束條件的解最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解基：設(shè)A是約束方程組的m×n階系數(shù)矩陣，B是矩陣A中m×m階非奇異子矩陣，稱B是線性規(guī)劃問(wèn)題的一個(gè)基基向量：基B中每一個(gè)列向量Pj非基向量：A中其余列向量Pj（不在B中）基變量：與基向量Pj對(duì)應(yīng)的決策變量xj非基變量：與非基向量對(duì)應(yīng)的決策變量基解基可行解：滿足非負(fù)約束條件的基解可行基：對(duì)應(yīng)于基可行解的基§1對(duì)線性規(guī)劃的回顧第六頁(yè)，共五十六頁(yè)，編輯于2023年，星期四1可行解與最優(yōu)解：最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解?；獠灰欢ㄊ强尚薪猓尚薪庖膊灰欢ㄊ腔?。2可行解與基解：3可行解與基可行解：基可行解一定是可行解，但可行解不一定是基可能解。基可行解一定是基解，但基解不一定是基可行解。4基本解與基可行解：非可行解可行解基可行解基本解§1對(duì)線性規(guī)劃的回顧線性規(guī)劃問(wèn)題解的概念第七頁(yè)，共五十六頁(yè)，編輯于2023年，星期四6問(wèn)題：最優(yōu)解與基可行解？最優(yōu)解不一定是基可行解，基可行解也不一定是最優(yōu)解。5最優(yōu)解與基本解：最優(yōu)解不一定是基解，基解也不一定是最優(yōu)解。為什么？§1對(duì)線性規(guī)劃的回顧非可行解可行解基可行解基本解考慮無(wú)窮多最優(yōu)解的情況。線性規(guī)劃問(wèn)題解的概念第八頁(yè)，共五十六頁(yè)，編輯于2023年，星期四線性規(guī)劃解的性質(zhì)定理1

線性規(guī)劃的可行域R

是一個(gè)凸集，且有有限個(gè)頂點(diǎn)。定理3若線性規(guī)劃有最優(yōu)解，則必存在一個(gè)基可行解是最優(yōu)解?！€性規(guī)劃問(wèn)題的可行域是一個(gè)凸集?！€性規(guī)劃的每一個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)(基可行解與可行域頂點(diǎn)一一對(duì)應(yīng))。定理2

X是線性規(guī)劃可行域R

頂點(diǎn)的充要條件是X是線性規(guī)劃的基本可行解?！?對(duì)線性規(guī)劃的回顧——若線性規(guī)劃有最優(yōu)解，則一定在凸集的某個(gè)（些）頂點(diǎn)上達(dá)到最優(yōu)，即此時(shí)一定存在某個(gè)頂點(diǎn)是最優(yōu)解。定理4若線性規(guī)劃在可行域的兩個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則在兩個(gè)頂點(diǎn)的連線上也達(dá)到最優(yōu)?！艟€性規(guī)劃在兩個(gè)頂點(diǎn)以上達(dá)到最優(yōu),則一定有無(wú)窮多個(gè)最優(yōu)解?！顑?yōu)解不一定是基可行解，基可行解也不一定是最優(yōu)解。第九頁(yè)，共五十六頁(yè)，編輯于2023年，星期四單純形法一、單純形法的解題思路從某一基可行解開始，轉(zhuǎn)化到另一個(gè)相鄰的基可行解，并且使相應(yīng)的目標(biāo)函數(shù)值有改進(jìn)。即從可行域的一個(gè)頂點(diǎn)沿約束邊界轉(zhuǎn)換到可行域的另一個(gè)相鄰的且使目標(biāo)函數(shù)值有改進(jìn)的頂點(diǎn)，直到目標(biāo)函數(shù)值到達(dá)最優(yōu)時(shí)的頂點(diǎn)為止。二、單純形法的含義單純形法是一種迭代算法，首先找到一個(gè)初始基可行解，然后判斷它是否為最優(yōu)解，如果是就停止迭代，否則，按照一定的法則，再找到一個(gè)更好且與當(dāng)前基可行解相鄰的基可行解，再進(jìn)行判斷，直到找不到更好的基可行解或判斷問(wèn)題無(wú)解為止?！?對(duì)線性規(guī)劃的回顧第十頁(yè)，共五十六頁(yè)，編輯于2023年，星期四三、單純形法的解題步驟1、找出初始可行基，確定初始基可行解，建立初始單純形表。c1…cmcm+1…cncBxBbx1…xmxm+1…xnc1x1b11…0a1,m+1

…a1,nc2x2b20…0a2,m+1…a2,n………………………cmxmbm0…1am,m+1…am,n0…0…§1對(duì)線性規(guī)劃的回顧單純形法第十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期四例：線性規(guī)劃問(wèn)題數(shù)學(xué)模型的某種標(biāo)準(zhǔn)形式§1對(duì)線性規(guī)劃的回顧單純形法(單純形法的解題步驟)第十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期四2、檢驗(yàn)各非基變量xj（j=m+1，m+2，…，n）的檢驗(yàn)數(shù)δj，若δj≤0，則已得最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入3。3、在δj＞0（j=m+1，m+2，…，n）中，若有某個(gè)δk對(duì)應(yīng)的xk的系數(shù)列向量Pk≤0，則此線性規(guī)劃問(wèn)題存在無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入4。4、根據(jù)，確定xk為換入變量，通過(guò)，計(jì)算確定xl為換出變量，轉(zhuǎn)入5。§1對(duì)線性規(guī)劃的回顧5、以alk為主元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量

將xB列中xl的換為xk，得到新的單純形表，重復(fù)2～5，直至終止。單純形法(單純形法的解題步驟)第十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期四單純形法小結(jié)單純形表中解的表示形式1、唯一最優(yōu)解：最終單純形表中，所有非基變量檢驗(yàn)數(shù)δj＜02、無(wú)窮多最優(yōu)解：最終單純形表中，某非基變量檢驗(yàn)數(shù)δj＝03、無(wú)界解：某檢驗(yàn)數(shù)δj＞0對(duì)應(yīng)變量的系數(shù)列向量Pk≤04、退化基可行解：一個(gè)或幾個(gè)基變量取值‘＝0’的基可行解出現(xiàn)退化基可行解，可能導(dǎo)致從某個(gè)基開始，經(jīng)過(guò)若干次迭代后又回到原來(lái)的基，即單純形法出現(xiàn)了循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解，導(dǎo)致計(jì)算失敗。為避免出現(xiàn)死循環(huán)，法則如下：選擇換入變量時(shí)，若有幾個(gè)正的檢驗(yàn)數(shù)具有相同的最大值，則選擇下標(biāo)最小的對(duì)應(yīng)的非基變量作為換入變量選擇換出變量時(shí)，若按θ規(guī)則計(jì)算，有幾個(gè)比值同時(shí)達(dá)到最小，則選擇下標(biāo)最小的對(duì)應(yīng)的基變量作為換出變量§1對(duì)線性規(guī)劃的回顧第十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期四第十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期四線性規(guī)劃的對(duì)偶理論§1對(duì)線性規(guī)劃的回顧原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個(gè)m個(gè)變量≤≥0≥≤0=無(wú)約束變量n個(gè)n個(gè)約束條件≥0≥≤0≤無(wú)約束=約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)第十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§1對(duì)線性規(guī)劃的回顧對(duì)偶問(wèn)題的性質(zhì)【性質(zhì)1】對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題?！拘再|(zhì)2】弱對(duì)偶原理（弱對(duì)偶性）：設(shè)X

和Y

分別是問(wèn)題（P）和（D）的任一可行解，則必有z(X)≤f(Y).【性質(zhì)3】最優(yōu)性判別定理：若X*

和Y*分別是P和D

的可行解且CX*=Y*b，則X*,Y*分別是問(wèn)題P和D

的最優(yōu)解?！拘再|(zhì)4】(強(qiáng)對(duì)偶性)原規(guī)劃與對(duì)偶規(guī)劃同有最優(yōu)解，且兩者最優(yōu)值相等。【性質(zhì)5】互補(bǔ)松弛定理：設(shè)X、Y各為原規(guī)劃與對(duì)偶規(guī)劃的一個(gè)可行解，則X、Y為最優(yōu)解的充分必要條件為YXS=YSX=0?！拘再|(zhì)6】(基解對(duì)應(yīng)性)原規(guī)劃單純形表中檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶規(guī)劃的一個(gè)基解。推論⑴.若X和Y分別是問(wèn)題（P）和（D）的可行解，則CX是（D）的目標(biāo)函數(shù)最小值的一個(gè)下界；Yb是（P）的目標(biāo)函數(shù)最大值的一個(gè)上界。推論⑵.在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界，則另一個(gè)問(wèn)題不可行；反之不成立。這也是對(duì)偶問(wèn)題的無(wú)界性。推論⑶.在一對(duì)對(duì)偶問(wèn)題（P）和（D）中，若一個(gè)可行（如P），而另一個(gè)不可行，（如D），則該可行的問(wèn)題無(wú)界。第十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期四原規(guī)劃與對(duì)偶規(guī)劃解之間的關(guān)系§1對(duì)線性規(guī)劃的回顧原規(guī)劃（P）對(duì)偶規(guī)劃（D）可行可行不可行可行（無(wú)界）可行（無(wú)界）不可行不可行不可行第十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期四

對(duì)偶單純形法§1對(duì)線性規(guī)劃的回顧基本思想是：從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）。如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程：建立初始對(duì)偶單純形表,對(duì)應(yīng)一個(gè)基本解,所有檢驗(yàn)數(shù)均非正,轉(zhuǎn)2；若b≥0,則得到最優(yōu)解,停止;否則,若有bk<0則選k行的基變量為出基變量,轉(zhuǎn)3若所有akj≥0(j=1,2,…,n)，則原問(wèn)題無(wú)可行解,停止;否則,若有akj<0則選=min{j/akj┃akj<0}=r/akr那么xr為進(jìn)基變量,轉(zhuǎn)4；4.以akr為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。第十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期四<是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計(jì)算計(jì)算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒(méi)有最優(yōu)解沒(méi)有最優(yōu)解單純形法對(duì)偶單純形法單純形法和對(duì)偶單純形法步驟§1對(duì)線性規(guī)劃的回顧第二十頁(yè)，共五十六頁(yè)，編輯于2023年，星期四21例6用單純形表求解例1。（見(jiàn)書P25）解已知該問(wèn)題的標(biāo)準(zhǔn)型為:取初始基變量為松弛變量x3、x4、x5，得初始基可行解X(0)=(0,0,180,400,210)T(此可行解對(duì)應(yīng)圖形法中的O點(diǎn),參見(jiàn)教材p17)。第二十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期四22建立初始單純形表(表1-4)：因σj行中，σ1=31為最大正檢驗(yàn)數(shù)，故選x1為入基變量；又因θi列中最小比值在第一行，故定x3為出基變量。合之，知主元為6，用［］將其標(biāo)出。Cj→3122000θiCBXBbx1x2x3x4x50x3180[6]2100180/60x4400410010400/40x521035001210/3-z03122000表1-431180/6[6]第二十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期四23Cj→3122000θiCBXBbx1x2x3x4x531x13011/31/600900x4280026/3-2/310420/130x51200[4]-1/20130-z-930035/3-31/600作旋轉(zhuǎn)變換得新單純形表：第1行=第1行/6第2行=第2行-4×第1行第3行=第3行-3×第1行得新基可行解X(1)=(30,0,0,280,120)T(此可行解對(duì)應(yīng)圖形法中的D點(diǎn),參見(jiàn)教材p17)。由于只有σ2=35/3>0，故x2為入基變量；又因最小比值在第三行，故x5為出基變量。合之，知主元為4。第二十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期四24

因所有的檢驗(yàn)數(shù)σj≤0(j=1,2,…,5)，故當(dāng)前基可行解X(2)=(20,30,0,20,0)T(此可行解對(duì)應(yīng)圖形法中的C點(diǎn),參見(jiàn)教材p17)為最優(yōu)解，刪去松弛變量，即得原線性規(guī)劃之最優(yōu)解為X*=(20,30)T，最優(yōu)值z(mì)*=1280。Cj→3122000θiCBXBbx1x2x3x4x531x120105/240-1/120x420005/121-13/622x23001-1/801/4-z-128000-89/240-35/12以4為主元作旋轉(zhuǎn)變換得下表：第二十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期四25§2線性規(guī)劃在工商管理中的應(yīng)用§2.1人力資源分配的問(wèn)題§2.2生產(chǎn)計(jì)劃問(wèn)題§2.3配料問(wèn)題§2.4投資問(wèn)題第二十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期四26§2.1人力資源分配的問(wèn)題

例1．某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：

設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?第二十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期四

解：設(shè)xi表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。

目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6

約束條件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0§2.1人力資源分配的問(wèn)題第二十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期四例2．一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問(wèn)應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？§2.1人力資源分配的問(wèn)題第二十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期四29

解：設(shè)xi(i=1,2,…,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。

目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6+x7

約束條件：s.t.x1+x2+x3+x4+x5≥28

x2+x3+x4+x5+x6≥15

x3+x4+x5+x6+x7≥24

x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31

x7+x1+x2+x3+x4≥28

x1,x2,x3,x4,x5,x6,x7≥0§2.1人力資源分配的問(wèn)題第二十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期四例3．某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問(wèn)題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？§2.2生產(chǎn)計(jì)劃問(wèn)題第三十頁(yè)，共五十六頁(yè)，編輯于2023年，星期四

解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤(rùn)：利潤(rùn)=售價(jià)-各成本之和產(chǎn)品甲全部自制的利潤(rùn)=23-(3+2+3)=15產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn)=23-(5+2+3)=13產(chǎn)品乙全部自制的利潤(rùn)=18-(5+1+2)=10產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn)=18-(6+1+2)=9產(chǎn)品丙的利潤(rùn)=16-(4+3+2)=7可得到xi（i=1,2,3,4,5）的利潤(rùn)分別為15、10、7、13、9元。§2.2生產(chǎn)計(jì)劃問(wèn)題第三十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期四通過(guò)以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)：Max15x1+10x2+7x3+13x4+9x5

約束條件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0§2.2生產(chǎn)計(jì)劃問(wèn)題第三十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期四例4．永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過(guò)A、B兩道工序加工。設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工。數(shù)據(jù)如表。問(wèn)：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？§2.2生產(chǎn)計(jì)劃問(wèn)題第三十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期四34解：設(shè)xijk表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量。建立如下的數(shù)學(xué)模型:

s.t.5x111+10x211≤6000（設(shè)備A1）7x112+9x212+12x312≤10000（設(shè)備A2）6x121+8x221≤4000（設(shè)備B1）4x122+11x322≤7000（設(shè)備B2）7x123≤4000（設(shè)備B3）

x111+x112-x121-x122-x123=0（Ⅰ產(chǎn)品在A、B工序加工的數(shù)量相等）

x211+x212-x221=0（Ⅱ產(chǎn)品在A、B工序加工的數(shù)量相等）x312-x322=0（Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3§2.2生產(chǎn)計(jì)劃問(wèn)題第三十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.2生產(chǎn)計(jì)劃問(wèn)題目標(biāo)函數(shù)為計(jì)算利潤(rùn)最大化，利潤(rùn)的計(jì)算公式為：利潤(rùn)=[（銷售單價(jià)-原料單價(jià)）*產(chǎn)品件數(shù)]之和-（每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。這樣得到目標(biāo)函數(shù)：

Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312–300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).經(jīng)整理可得：

Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123第三十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.3配料問(wèn)題

例5．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？

解：設(shè)xij

表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：對(duì)于甲：x11，x12，x13；對(duì)于乙：x21，x22，x23；對(duì)于丙：x31，x32，x33；對(duì)于原料1：x11，x21，x31；對(duì)于原料2：x12，x22，x32；對(duì)于原料3：x13，x23，x33；目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料支出約束條件：規(guī)格要求4個(gè)；供應(yīng)量限制3個(gè)。第三十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.3配料問(wèn)題利潤(rùn)=總收入-總成本=甲乙丙三種產(chǎn)品的銷售單價(jià)*產(chǎn)品數(shù)量-甲乙丙使用的原料單價(jià)*原料數(shù)量，故有目標(biāo)函數(shù)Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

約束條件：

從第1個(gè)表中有：x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)第三十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.3配料問(wèn)題

從第2個(gè)表中，生產(chǎn)甲乙丙的原材料不能超過(guò)原材料的供應(yīng)限額，故有(x11+x21+x31)≤100(x12+x22+x32)≤100(x13+x23+x33)≤60通過(guò)整理，得到以下模型：第三十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.3配料問(wèn)題例5．（續(xù)）目標(biāo)函數(shù)：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

約束條件：s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超過(guò)25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超過(guò)50%）

x11+x21+x31≤100(供應(yīng)量限制）

x12+x22+x32≤100(供應(yīng)量限制）

x13+x23+x33≤60(供應(yīng)量限制）xij≥0,i=1,2,3;j=1,2,3第三十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.3配料問(wèn)題標(biāo)準(zhǔn)汽油辛烷數(shù)蒸汽壓力(g/cm2)庫(kù)存量(L)1107.57.11×10-2380000293.011.38×10-2265200387.05.69×10-24081004108.028.45×10-2130100例6.汽油混合問(wèn)題。一種汽油的特性可用兩種指標(biāo)描述，用“辛烷數(shù)”來(lái)定量描述其點(diǎn)火特性，用“蒸汽壓力”來(lái)定量描述其揮發(fā)性。某煉油廠有1、2、3、4種標(biāo)準(zhǔn)汽油，其特性和庫(kù)存量列于表1中，將這四種標(biāo)準(zhǔn)汽油混合，可得到標(biāo)號(hào)為1，2的兩種飛機(jī)汽油，這兩種汽油的性能指標(biāo)及產(chǎn)量需求列于表2中。問(wèn)應(yīng)如何根據(jù)庫(kù)存情況適量混合各種標(biāo)準(zhǔn)汽油，既滿足飛機(jī)汽油的性能指標(biāo)，又使2號(hào)汽油滿足需求，并使得1號(hào)汽油產(chǎn)量最高？飛機(jī)汽油辛烷數(shù)蒸汽壓力(g/cm2)產(chǎn)量需求1不小于91不大于9.96×10-2越多越好2不小于100不大于9.96×10-2不少于250000表1表2第四十頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.3配料問(wèn)題解：設(shè)xij為飛機(jī)汽油i中所用標(biāo)準(zhǔn)汽油j的數(shù)量(L)。目標(biāo)函數(shù)為飛機(jī)汽油1的總產(chǎn)量：庫(kù)存量約束為：產(chǎn)量約束為飛機(jī)汽油2的產(chǎn)量：由物理中的分壓定律，可得有關(guān)蒸汽壓力的約束條件：同樣可得有關(guān)辛烷數(shù)的約束條件為：第四十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期四綜上所述，得該問(wèn)題的數(shù)學(xué)模型為：§2.3配料問(wèn)題第四十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期四§2.4投資問(wèn)題

例7．某部門現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過(guò)30萬(wàn)元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元。據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺篴）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最??？

解：1）確定決策變量：連續(xù)投資問(wèn)題設(shè)xij(i=1～5，j=1～4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24第四十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期四442）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x11+x12=200；第二年：B次年末才可收回投資，故第二年年初有資金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有資金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有資金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有資金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投資限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(i=1、2、3、4)，x33≤80，x24≤100

xij≥0(i=1、2、3、4、5；j=1、2、3、4）§2.4投資問(wèn)題第四十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期四45b)所設(shè)變量與問(wèn)題a相同，目標(biāo)函數(shù)為風(fēng)險(xiǎn)最小，有

Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在問(wèn)題a的約束條件中加上“第五年末擁有資金本利在330萬(wàn)元”的條件，于是模型如下：Minf=(x11+x21+x31+x41+