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

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

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

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

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

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

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

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

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

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

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

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

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

0.2X1+0.4X2≤120+M2y2

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

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

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

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

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

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

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