第5講 生產(chǎn)與服務(wù)管理中的優(yōu)化問(wèn)題一

第5講:生產(chǎn)與服務(wù)管理中的優(yōu)化問(wèn)題(一)

0-1規(guī)劃問(wèn)題補(bǔ)充生產(chǎn)與銷(xiāo)售計(jì)劃問(wèn)題有瓶頸設(shè)備的多級(jí)生產(chǎn)計(jì)劃問(wèn)題疏散問(wèn)題5/22/20240-1變量作為邏輯變量（Logicalvariable），常常被用來(lái)處理“選擇問(wèn)題”。如：假定現(xiàn)有的m種資源對(duì)可供選擇的n個(gè)項(xiàng)目進(jìn)行投資,每個(gè)項(xiàng)目可獲取的利潤(rùn)為cj元，則求利潤(rùn)最大的數(shù)學(xué)模型為求一組決策變量x1,x2,…,xn,使

其中，cj表示投資第j項(xiàng)目獲得的期望收益（價(jià)值系數(shù)），aij表示第i種資源投于第j項(xiàng)目的數(shù)量，bi表示第i種資源的限量。一0-1整數(shù)規(guī)劃問(wèn)題補(bǔ)充1）如果在可供選擇的k(k≤n)個(gè)項(xiàng)目中，必須且只需選擇一項(xiàng)，則在(2)中加入新的約束條件

2）如果可供選擇的k(k≤n)個(gè)項(xiàng)目相互排斥的，則在(2)中加入新的約束條件

3）如果可供選擇的k(k≤n)個(gè)項(xiàng)目中，至少應(yīng)選擇一項(xiàng)投資，則在(2)中加入新的約束條件4）如果項(xiàng)目j的投資必須以項(xiàng)目i的投資為前提，則可在(2)中加入新的約束

5）如果項(xiàng)目i與項(xiàng)目j要么同時(shí)被選中，要么同時(shí)不被選中，則在(2)中加入新的約束

6）如果對(duì)第r種資源與第t種資源的投資的是相互排斥的，即只能對(duì)資源br與bt中的一種進(jìn)行投資，則可將(2)的第r個(gè)和第t個(gè)約束條件改寫(xiě)為

其中y為新引入的0—1變量，M為充分大的正數(shù)。

7）若在m個(gè)約束中只有k個(gè)起作用，則（2）改為

其中yi為0—1變量，M為充分大的正數(shù)。則，（2）表示為：8）約束條件的右端項(xiàng)可能是r個(gè)值（b1,b2,…br）中的某一個(gè)，即9）兩組條件中滿(mǎn)足其中一組若x1≤4，則x2≥1；否則（即x1>4時(shí)）,x2≤3.

定義yi為0—1變量，M為充分大的正數(shù),則問(wèn)題可表述為10）可以用以表示含固定費(fèi)用的函數(shù)如若用xj代表產(chǎn)品j的生產(chǎn)數(shù)量,其生產(chǎn)費(fèi)用函數(shù)通?？杀頌?其中Kj是同產(chǎn)量無(wú)關(guān)的生產(chǎn)準(zhǔn)備費(fèi)用。問(wèn)題的目標(biāo)是使所有產(chǎn)品的總生產(chǎn)費(fèi)用為最小.即同樣,定義yj為0—1變量，當(dāng)xj=0時(shí),yj=0;當(dāng)xj>0,yj=1.因此,引進(jìn)一個(gè)特殊的約束條件:所以線(xiàn)性規(guī)劃模型為由(7)看出當(dāng)xj=0時(shí)，為使z極小化，應(yīng)有yj=0例1

試用0-1變量對(duì)下列各題分別表示成一般線(xiàn)形約束條件：(1)X1+X2≤2或2X1+3X2≥8；(2)變量X3只能取0，5，9，12；(3)若X2≤4,則X5≥0,否則X5≤3;(4)以下四個(gè)約束條件中至少滿(mǎn)足2個(gè)5/22/2024解：5/22/2024例2將以下問(wèn)題表示為混合整數(shù)規(guī)劃模型5/22/20245/22/2024解目標(biāo)函數(shù)為：約束條件：5/22/2024例3應(yīng)用0-1變量解決含互斥約束條件問(wèn)題設(shè)：工序B有兩種方式完成方式（1）的工時(shí)約束為0.3X1+0.5X2≤150方式（2）的工時(shí)約束為0.2X1+0.4X2≤120問(wèn)題是完成工序B只能從兩種方式中任選一種，如何將這兩個(gè)互斥的約束條件統(tǒng)一在一個(gè)線(xiàn)性規(guī)劃模型中呢？引入0-1變量y1=0若工序B采用方式（1）完成1若工序B不采用方式（1）完成y2=0若工序B采用方式（2）完成1若工序B不采用方式（2）完成于是前面兩個(gè)互斥的約束條件可以統(tǒng)一為如下三個(gè)約束條件：0.3X1+0.5X2≤150+M1y1

0.2X1+0.4X2≤120+M2y2

y1+y2=1其中M1，M2都是足夠大的正數(shù)。例4某公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙）。甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價(jià)分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫(kù)存量分別為500噸和1000噸，還可以從市場(chǎng)上買(mǎi)到不超過(guò)1500噸的原油A。原油A的市場(chǎng)價(jià)為：購(gòu)買(mǎi)量不超過(guò)500噸時(shí)的單價(jià)為10000元/噸；購(gòu)買(mǎi)量超過(guò)500噸但不超過(guò)1000噸時(shí)，超過(guò)500噸的部分8000元/噸；購(gòu)買(mǎi)量超過(guò)1000噸時(shí)，超過(guò)1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購(gòu)和加工。二生產(chǎn)與銷(xiāo)售計(jì)劃問(wèn)題5/22/20242.1問(wèn)題分析安排原油采購(gòu)、加工的目標(biāo)是利潤(rùn)最大，題目中給出的是兩種汽油的售價(jià)和原油A的采購(gòu)價(jià)，利潤(rùn)為銷(xiāo)售汽油的收入與購(gòu)買(mǎi)原油A的支出之差。這里的難點(diǎn)在于原油A的采購(gòu)價(jià)與購(gòu)買(mǎi)量的關(guān)系比較復(fù)雜，是分段函數(shù)關(guān)系，能否及如何用線(xiàn)性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關(guān)鍵所在。5/22/2024模型建立設(shè)原油A的購(gòu)買(mǎi)量為x（噸），根據(jù)題目所給數(shù)據(jù)，采購(gòu)的支出c(x)可表為如下的分段線(xiàn)性函數(shù)（以下價(jià)格以千元/噸為單位）：(1)設(shè)原油A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x11和x12（噸），原油B用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x21和x22（噸），則總的收入為4.8(x11+x21)+5.6(x12+x22)（千元）。于是本例的目標(biāo)函數(shù)（利潤(rùn)）為(2)5/22/2024約束條件包括加工兩種汽油用的原油A、原油B庫(kù)存量的限制，和原油A購(gòu)買(mǎi)量的限制，以及兩種汽油含原油A的比例限制，它們表示為（3）（4）（5）（6）（7）（8）由于（1）式中的c(x)不是線(xiàn)性函數(shù)，（1）~（8）給出的是一個(gè)非線(xiàn)性規(guī)劃。而且，對(duì)于這樣用分段函數(shù)定義的c(x)，一般的非線(xiàn)性規(guī)劃軟件也難以輸入和求解。能不能想辦法將該模型化簡(jiǎn)，從而用現(xiàn)成的軟件求解呢？5/22/20242.2求解模型將原油A的采購(gòu)量x分解為三個(gè)量，即用x1，x2，x3分別表示以?xún)r(jià)格10、8、6千元/噸采購(gòu)的原油A的噸數(shù)，總支出為c(x)=10x1+8x2+6x3，且(9)這時(shí)目標(biāo)函數(shù)（2）變?yōu)榫€(xiàn)性函數(shù)：(10)應(yīng)該注意到，只有當(dāng)以10千元/噸的價(jià)格購(gòu)買(mǎi)x1=500（噸）時(shí)，才能以8千元/噸的價(jià)格購(gòu)買(mǎi)x2（>0），這個(gè)條件可以表示為 (11)5/22/2024同理，只有當(dāng)以8千元/噸的價(jià)格購(gòu)買(mǎi)x2=500（噸）時(shí)，才能以6千元/噸的價(jià)格購(gòu)買(mǎi)x3（>0），于是(12)此外，x1，x2，x3的取值范圍是(13)5/22/2024由于有非線(xiàn)性約束(11),(12)，(3)~(13)構(gòu)成非線(xiàn)性規(guī)劃模型。LINGO程序：5/22/2024將文件存儲(chǔ)并命名為exam0501a.lg4，執(zhí)行菜單命令“LINGO|Solve”，運(yùn)行該程序得到：5/22/2024最優(yōu)解:用庫(kù)存的500噸原油A、500噸原油B生產(chǎn)1000噸汽油甲，不購(gòu)買(mǎi)新的原油A，利潤(rùn)為4800（千元）但是此時(shí)LINGO得到的結(jié)果只是一個(gè)局部最優(yōu)解可以用菜單命令“LINGO|Options”在“GlobalSolver”選項(xiàng)卡上啟動(dòng)全局優(yōu)化（UseGlobalSolver）選項(xiàng)，然后重新執(zhí)行菜單命令“LINGO|Solve”,得到：5/22/2024

此時(shí)LINGO得到的結(jié)果是一個(gè)全局最優(yōu)解（Globaloptimalsolution）：購(gòu)買(mǎi)1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B一起，共生產(chǎn)2500噸汽油乙，利潤(rùn)為5000（千元），高于剛剛得到的局部最優(yōu)解對(duì)應(yīng)的利潤(rùn)4800（千元）。5/22/2024在給定的外部需求和生產(chǎn)能力等限制條件下，按照生產(chǎn)總費(fèi)用最小編制未來(lái)若干個(gè)生產(chǎn)周期的最優(yōu)生產(chǎn)計(jì)劃，這種問(wèn)題在文獻(xiàn)上一般稱(chēng)為批量問(wèn)題（LotsizingProblems）。我們通過(guò)下面的具體例子來(lái)說(shuō)明這種多級(jí)生產(chǎn)計(jì)劃問(wèn)題的優(yōu)化模型。這里“多級(jí)”的意思是需要考慮產(chǎn)品是通過(guò)多個(gè)生產(chǎn)階段（工藝過(guò)程）生產(chǎn)出來(lái)的。三有瓶頸設(shè)備的多級(jí)生產(chǎn)計(jì)劃問(wèn)題5/22/2024例5某工廠的主要任務(wù)是通過(guò)組裝生產(chǎn)產(chǎn)品A，用于滿(mǎn)足外部市場(chǎng)需求。A產(chǎn)品的產(chǎn)品構(gòu)成與組裝過(guò)程見(jiàn)圖5-2：即D、E、F、G是從外部采購(gòu)的零件，先將零件D、E組裝成部件B，零件F、G組裝成部件C，然后將部件B、C組裝成產(chǎn)品A出售。圖中弧上的數(shù)字表示的是組裝時(shí)部件（或產(chǎn)品）中包含的零件（或部件）的數(shù)量（可以稱(chēng)為消耗系數(shù)），例如DB弧上的數(shù)字“9”表示組裝1個(gè)部件B需要用到9個(gè)零件D；BA弧上的數(shù)字“5”表示組裝1件產(chǎn)品A需要用到5個(gè)部件B；依此類(lèi)推。5/22/2024瓶頸設(shè)備加工ABCDEFG579111315圖5-2產(chǎn)品構(gòu)成與組裝過(guò)程圖5/22/2024表5-1生產(chǎn)計(jì)劃的原始數(shù)據(jù)5/22/2024假設(shè)該工廠每次生產(chǎn)計(jì)劃的計(jì)劃期為6周（即每次制定未來(lái)6周的生產(chǎn)計(jì)劃），只有最終產(chǎn)品A有外部需求，目前收到的訂單的需求件數(shù)按周的分布如表5-1第2行所示。部件B、C是在該工廠最關(guān)鍵的設(shè)備（可以稱(chēng)為瓶頸設(shè)備）上組裝出來(lái)的，瓶頸設(shè)備的生產(chǎn)能力非常緊張，具體可供能力如表5-1第3行所示（第2周設(shè)備檢修，不能使用）。B、C的能力消耗系數(shù)分別為5和8，即生產(chǎn)1件B需要占用5個(gè)單位的能力，即生產(chǎn)1件C需要占用8個(gè)單位的能力。對(duì)于每種零部件或產(chǎn)品，如果工廠在某一周訂購(gòu)或者生產(chǎn)該零部件或產(chǎn)品，工廠需要付出一個(gè)與訂購(gòu)或生產(chǎn)數(shù)量無(wú)關(guān)的固定成本（稱(chēng)為生產(chǎn)準(zhǔn)備費(fèi)用）；如果某一周結(jié)束時(shí)該零部件或產(chǎn)品有庫(kù)存存在，則工廠必須付出一定的庫(kù)存費(fèi)用（與庫(kù)存數(shù)量成正比）。這些數(shù)據(jù)在表5-1第5、6行給出。5/22/2024按照工廠的信譽(yù)要求，目前接收的所有訂單到期必須全部交貨，不能有缺貨發(fā)生；此外，不妨簡(jiǎn)單地假設(shè)目前該企業(yè)沒(méi)有任何零部件或產(chǎn)品庫(kù)存，也不希望第6周結(jié)束后留下沒(méi)有任何零部件或產(chǎn)品庫(kù)存。最后，假設(shè)不考慮生產(chǎn)提前期，即假設(shè)當(dāng)周采購(gòu)的零件馬上就可用于組裝，組裝出來(lái)的部件也可以馬上用于當(dāng)周組裝成品A。在上述假設(shè)和所給數(shù)據(jù)下，如何制定未來(lái)6周的生產(chǎn)計(jì)劃？5/22/20243.1問(wèn)題分析這個(gè)例子考慮的是在有限的計(jì)劃期內(nèi),給定產(chǎn)品結(jié)構(gòu)、生產(chǎn)能力和相關(guān)費(fèi)用及零部件或成品（以下統(tǒng)稱(chēng)為生產(chǎn)項(xiàng)目）在離散的時(shí)間段上（這里是周，也可以是天、月等）的外部需求之后,確定每一生產(chǎn)項(xiàng)目在每一時(shí)間段上的生產(chǎn)量(即批量),使總費(fèi)用最小.由于每一生產(chǎn)項(xiàng)目在每一時(shí)間段上生產(chǎn)時(shí)必須經(jīng)過(guò)生產(chǎn)準(zhǔn)備(Setup),所以通常的討論中總費(fèi)用至少應(yīng)考慮生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用.

其實(shí)，如果是現(xiàn)實(shí)問(wèn)題，應(yīng)該還有生產(chǎn)的直接成本（如原材料成本、人力成本、電力成本等）等費(fèi)用。由已知條件可知，計(jì)劃期初和末期庫(kù)存都是0，所以6個(gè)周期內(nèi)A的總產(chǎn)量等于總銷(xiāo)量。從而可以考慮本題直接成本為一個(gè)常數(shù)。5/22/20243.2符號(hào)說(shuō)明為了建立這類(lèi)問(wèn)題的一般模型，我們定義如下數(shù)學(xué)符號(hào)：N--------生產(chǎn)產(chǎn)品（部件）總數(shù)（本例中N=7）;T--------計(jì)劃期長(zhǎng)度（本例中T=6）;M--------一個(gè)充分大的正數(shù)，在模型中起到使模型線(xiàn)性化的作用;-----第t周生產(chǎn)產(chǎn)品i的數(shù)量;t=1,‥T,;i=1,‥,N.-----生產(chǎn)（組裝）一個(gè)產(chǎn)品j需要產(chǎn)品i的個(gè)數(shù);i,j=1,‥,N.5/22/2024-----產(chǎn)品j在第t周的外部需求量；（只有A有）-----產(chǎn)品j在第t周末的庫(kù)存量，-----產(chǎn)品i在t周是否生產(chǎn)的標(biāo)志(0：不生產(chǎn),1：生產(chǎn));S(i)-----產(chǎn)品結(jié)構(gòu)中項(xiàng)目i的直接后繼項(xiàng)目集合;-----產(chǎn)品i在t時(shí)段生產(chǎn)時(shí)的生產(chǎn)準(zhǔn)備費(fèi)用;-----產(chǎn)品i在t時(shí)段的單件庫(kù)存費(fèi)用;-----資源在t時(shí)段的能力上限;---產(chǎn)品i在t時(shí)段生產(chǎn)時(shí),生產(chǎn)單個(gè)產(chǎn)品占用

的能力上限;5/22/2024在上述數(shù)學(xué)符號(hào)中，只有為決策變量;其余均為已知的計(jì)劃參數(shù)。目標(biāo)函數(shù)3.3模型的建立這個(gè)問(wèn)題的目標(biāo)是使生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用的總和最小。因此，目標(biāo)函數(shù)應(yīng)該是每個(gè)項(xiàng)目在每個(gè)時(shí)段上的生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用的總和，即(0)5/22/2024約束條件這個(gè)問(wèn)題中的約束有這么幾類(lèi)：每個(gè)項(xiàng)目的物流應(yīng)該守恒、資源能力限制應(yīng)該滿(mǎn)足、每時(shí)段生產(chǎn)某項(xiàng)目前必須經(jīng)過(guò)生產(chǎn)準(zhǔn)備和非負(fù)約束（對(duì)Yi,j是0-1約束）。所謂物流守恒（假設(shè)Ii,0=0）(1)資源能力限制比較容易理解，即(2)5/22/2024(3)每時(shí)段生產(chǎn)某項(xiàng)目前必須經(jīng)過(guò)生產(chǎn)準(zhǔn)備，也就是說(shuō)當(dāng)Xit=0時(shí)Yit=0；Xit>0時(shí)Yit=1。這本來(lái)是一個(gè)非線(xiàn)性約束，但是通過(guò)引入?yún)?shù)M（很大的正數(shù)，表示每個(gè)項(xiàng)目每個(gè)時(shí)段的最大產(chǎn)量）可以化成線(xiàn)性約束，即：總結(jié):這個(gè)問(wèn)題的優(yōu)化模型就是在約束（1）（2）（3）下使目標(biāo)函數(shù)（0）達(dá)到最小。5/22/20243.4求解模型本例生產(chǎn)項(xiàng)目總數(shù)N=7(A、B、C、D、E、F、G)，計(jì)劃期長(zhǎng)度T=6（周），只有A有外部需求，所以di,t中只有d1,t可以取非零需求，即表5-1中的第2行的數(shù)據(jù)，其他全部為零。參數(shù)si,t、hi,t只與項(xiàng)目i有關(guān)，而不隨時(shí)段t變化，所以可以略去下標(biāo)t，其數(shù)值就是表5-1中的最后兩行數(shù)據(jù)。

aI,t只與項(xiàng)目i有關(guān)，而不隨時(shí)段t變化，所以可以同時(shí)略去下標(biāo)t，即a2=5，a3=8（其他ai為0）。從圖6-2中容易得到項(xiàng)目i的直接后繼項(xiàng)目集合S(i)和消耗系數(shù)。5/22/2024由于本例中，A的外部總需求為240，所以任何項(xiàng)目的產(chǎn)量不會(huì)超過(guò)240×7×15<25000（從圖6-2可以知道，這里7×15已經(jīng)是每件產(chǎn)品A對(duì)任意一個(gè)項(xiàng)目的最大的消耗系數(shù)了），所以取M=25000就已經(jīng)足夠了。本例中的具體模型可以如下輸入LINGO軟件：得到其數(shù)學(xué)模型為5/22/2024另解：準(zhǔn)備以下的數(shù)據(jù)文件（文本文件exam0502.LDT，可以看到其中也可以含有注釋語(yǔ)句）：具體模型可以如下輸入LINGO軟件：LINDO求解:得到最優(yōu)目標(biāo)函數(shù)值為9245,結(jié)果如下：表5-2

生產(chǎn)計(jì)劃的最后結(jié)果

5/22/2024四疏散問(wèn)題例6甲市一家大公司由五個(gè)部門(mén)（A,B,C,D,E）組成，現(xiàn)要將它的幾個(gè)部門(mén)遷出甲市，遷至乙或丙市（假設(shè)每個(gè)部門(mén)允許接收的部門(mén)不超過(guò)3個(gè)）.除政府鼓勵(lì)外，還有用房便宜、招工方便等好處.其好處的數(shù)量估計(jì)如下表遷市部門(mén)A部門(mén)B部門(mén)C部門(mén)D部門(mén)E乙101510205丙1020151515疏散后部門(mén)間每年增加的通訊量如下部門(mén)BCDEA0100015000B140012000C02000D7005/22/202