1.2 理論基礎

1.2.1 配套生產問題

配套生產(或稱配套加工、套材下料等)問題的核心是弄清楚產品的構成，也就是一件完整的產品所包括的各部件的相應數量，以保證生產的部件能夠組裝成完整的產品(end item，即最終產品)。通常，根據產品結構文件來完成這項工作。

產品結構文件，在運作管理中稱為物料清單(Bill of Material，BOM)文件或物料生產文件，記錄了產品所有部件(subassembly)、父項—組件之間的關系，以及從技術和工藝設計中得出的組件用量(usage quantity)數據。通常以圖來表述產品結構文件，因該圖形似一顆樹，故更形象地稱之為產品結構樹或產品樹。圖1-2是一個產品A的結構樹。在該產品結構樹中，產品A由1個B部件、1個C部件、2個D組件和4個E部件構成。而B部件由2個F組件和4個G組件構成，C部件則由4個H組件和1個I組件構成，E部件則由4個F組件構成。其實，除產品A之外的所有產品都是組件，組件可構成父項。父項至少有一個組件，這里的產品A，B，C和E都是父項。一個組件可能有兩個或兩個以上的父項，比如組件F的父項就有兩個，即B部件和E部件。沒有父項的產品就是最終產品，也就是通常出售給消費者的產品。當然，于廠家而言，最終產品具有相對的意義，比如，對于專門生產組件F，G，H和I的廠家來說，F，G，H和I就成了最終產品。

圖1-2 A產品的物料清單(產品結構樹)

1.2.2 容器設計問題

容器設計問題的關鍵是計算出容器的體積、表面積(底面積以及側面積之和)，這屬于平面幾何與立體幾何的范疇。對于本案例而言，需要計算體積的立體圖形為正棱臺，需要計算底面積的平面圖形為正方形，需要計算側面積的平面圖形為等腰梯形。盡管這是非常基礎的內容，考慮案例分析之需要仍給出其理論。它們各自的計算公式分別如下：

正棱臺的體積計算公式為

其中，h為正棱臺的高，S1，S2 為上下底面的面積。

底面正方形面積的計算公式為

其中，ai( i = 1，2)為上下底面的邊長。

側面等腰梯形面積的計算公式為

其中，h＇為側面梯形的高。

對于一般的四棱臺(底面為平行四邊形)，其體積的計算公式為

其中，a，b為一個底面的邊長，a＇，b＇為另一個底面的邊長。

1.2.3 線性規劃與非線性規劃的概念

線性規劃與非線性規劃是運籌學中的重要分支，是最優化理論和方法中的重要領域之一，主要研究在一定的約束條件下，使某一目標取得極值(最大值或最小值)的問題。如果目標函數(對要實現的目標的數學描述)和約束條件(資源的限制等)均為決策變量(待確定的未知因素)的線性函數關系，則為線性規劃(linear planning)；如果目標函數和約束條件中至少有一個是決策變量的非線性函數關系，則為非線性規劃(nonlinear planning)。

所有的線性規劃與非線性規劃都包含以下三個要素。

(1) 決策變量：需要解決的問題中有待確定的未知因素。例如，案例1中各車間開工的次數，案例2中容器的底面邊長，等等。決策變量可分為主要決策變量和輔助決策變量，前者是根據問題中涉及的直接求解結果建模時所設置的變量，后者是因建模需要而與主要決策變量有數量關系或因數學表達需要所設置的變量。

(2) 目標函數：對要實現的目標的數學描述和表達。例如，案例1中的產品銷售額最大，案例2中的成本最小，等等。

(3) 約束條件：實現問題目標的限制因素或相關要求。例如，案例1中原材料的供應量，案例2中容器的容量和總質量等，它們限制了目標值所能實現的程度。

線性規劃的數學模型的一般形式可表示為

其中，z為目標函數，只有兩種形式：max(“maximize”的縮寫，含義為最大化)或min(“minimize”的縮寫，含義為最小化)；常數fj(j =1，2，…，n)為目標函數系數、價值系數或費用系數；xj(j =1，2，…，n) 為決策變量，通常要求非負，當然應視具體情況而定；“{”中的關系式是約束條件，其上面部分是m個資源約束，分為等式約束( =)和不等式約束(≤，≥)；常數bi( i = 1，2，…，m)為函數約束右端常數或資源常數；常數aij( i = 1，2，…，m；j = 1，2，…，n)為約束系數、技術系數或工藝系數，下面部分是n個非負約束；“s.t.”是“subject to”的縮寫，含義為“滿足于……”。

因此，線性規劃模型的含義可以表述為：在給定的m個資源約束和n個非負約束下，求使得目標函數z達極值(最大或最小)時決策變量xj(j =1，2，…，n)的取值。求得的決策變量xj(j =1，2，…，n)的取值就是要尋求的方案，每一組值就是一個方案。

為提升效率，在實際生產運作中，對于線性規劃與非線性規劃的求解，通常需要借助應用軟件。能夠實現線性規劃與非線性規劃求解的軟件較多，比如MATLAB，Excel，本書主要介紹軟件求解的MATLAB實現。

1.2.4 線性規劃的MATLAB求解

在MATLAB優化工具箱中，求解線性規劃的函數為“linprog”，利用該函數求解的線性規劃的一般(標準)形式為

分別記價值系數向量F = (f1，f2，…，fn)T，決策變量向量X = (x1，x2，…，xn)T，不等式約束系數矩陣，不等式右端常數向量B = (b1，b2，…，bn)T，等式約束系數矩陣Aeq =，等式右端常數向量，決策變量下界(Lower Bound，LB)向量LB = (lb1，lb2，…，lbn)T和決策變量上界(Upper Bound，UB)向量UB = (ub1，ub2，…，ubn)T。則式(1-6)轉化為

在調用linprog函數求解線性規劃問題時，首先需要將線性規劃問題轉化為上述MATLAB能處理的標準形式。linprog函數的調用格式如下。

(1) x=linprog(F，A，B)用于求解只含有不等式約束的問題，即

min z = FTX

s.t.AX≤B

(2) x=linprog(F，Aeq，Beq)用于求解只含有等式約束的問題，即

min z = FTX

s.t.AeqX = Beq

(3) x=linprog(F，A，B，Aeq，Beq)用于求解同時包含不等式與等式約束的問題，即

(4) x=linprog(F，A，B，Aeq，Beq，LB，UB)用于求解同時包含不等式約束、等式約束和上下界約束的問題，即

當X的某個分量xi沒有上界時，則置UB(i) =inf；當X的某個分量xi沒有下界時，則置LB(i)= -inf；

(5) x=linprog(F，[]，[ ]，Aeq，Beq，LB，UB)用于求解不含有不等式約束的問題，即

(6) x=linprog(F，A，B，[]，[]，LB，UB)用于求解不包含等式約束的問題，即

(7) [X，FVAL，EXITFLAG，OUTPUT，LAMBDA] = linprog(F，A，B，Aeq，Beq，LB，UB)用于將最優目標值返回到變量FVAL中，其他輸出項的含義如下：

EXITFLAG的值描述程序運行的情況，當EXITFLAG=1時，說明程序收斂于解X；當EXIT-FLAG=0時，說明函數的計算達到了最大次數；當EXITFLAG<0時，說明的情況較多(包括-2，-3，-4，-5，-7)，讀者可在MATLAB的Help中通過搜索函數linprog查閱(在MATLAB的命令窗口中輸入“help linprog”即可查看相關信息)。

OUTPUT中的iterations表示程序的迭代次數，OUTPUT中的algorithm表示程序所用的算法。

LAMBDA中的Lagrange為解X處的Lagrange乘子，其中LAMBDA. lower是對應于LB的，LAMBDA.upper是對應于UB的，LAMBDA.ineqlin輸出不等式約束的影子價格(shadow price)①，LAMBDA.eqlin輸出等式約束的影子價格。

①影子價格(shadow price)：線性規劃對偶問題的解。每個線性規劃問題，稱為原問題，都對應一個對偶問題。例如，利潤最大化問題是成本最小化問題的對偶問題，成本最小化問題又是利潤最大化問題的對偶問題。因此，原問題與對偶問題是互為對偶關系的。例如，原問題maxz = FTX，的對偶問題為minz＇ = BTY，，這里的yi ( i = 1，2，…，n)就是對應于相應要素的影子價格。

實際上，第(7)種調用格式是linprog函數的通用調用格式，可以根據需要選擇其輸出參數，通常情況下選擇輸出X和FVAL；應視具體情況確定輸入參數，當某輸入參數不存在時，將其設定為“[ ]”。具體應用將在后續章節中給出。

1.2.5 非線性規劃的MATLAB求解

在MATLAB優化工具箱中，求解非線性規劃問題的函數有多個，如fmincon、fminimax、fgoalat-tain和fseminf等函數。這些函數均可以求解很一般的非線性規劃問題，只是在應用之前，首先應將非線性規劃問題轉換成MATLAB能處理的標準形。

為說明問題，這里僅以fmincon函數為例來給出其所處理的標準形，其余函數的標準形可查閱MATLAB幫助。使用fmincon求解非線性規劃問題的標準形為

其中，F(x) 為非線性目標函數，G(x) 為非線性不等式約束條件，Heq(x) 為非線性等式約束條件，其余符號含義同前。

應用fmincon函數求解非線性規劃問題的調用格式如下。

(1) x=fmincon(F，X0，A，B)用于求解只包含不等式線性約束條件在給定初始點x0 情況下的問題，即

min z = F(x)

s.t.AX≤B

(2) x=fmincon(F，X0，A，B，Aeq，Beq)用于求解同時包含不等式線性約束和等式線性約束條件在給定初始點x0 情況下的問題，即

(3) x=fmincon(F，X0，A，B，Aeq，Beq，LB，UB)用于求解同時包含不等式線性約束、等式線性約束和上下界約束條件在給定初始點x0 情況下的問題，即

(4) x=fmincon(F，X0，A，B，Aeq，Beq，LB，UB，NONLCON)用于求解標準形式(1-8)在給定初始點x0 情況下的問題。其中，輸入參數NONLCON為非線性約束函數。

(5) x =fmincon(F，X0，A，B，Aeq，Beq，LB，UB，NONLCON，OPTIONS)用于求解標準形式(1-8)在給定初始點x0 和優化選項OPTIONS情況下的問題。其中，OPTIONS的數目較多，各選項的具體含義可參閱MATLAB幫助。

該調用格式可以作為fmincon函數的通用調用格式，可以視具體情況將約束條件中的某些項置為空“[]”。例如，求解只包含非線性約束條件在給定初始點x0 情況下的問題時，可將調用格式寫為

    x=fmincon(F,X0,[],[],[],[],[],[],NONLCON,OPTIONS)

(6) x=fmincon(PROBLEM)用于解決由PROBLEM指定的優化問題。

(7) [X，FVAL，EXITFLAG，OUTPUT，LAMBDA] =fmincon(…)用于將最優目標值返回到變量FVAL中，其他輸出項的含義如下：

EXITFLAG的值描述程序退出的狀態，情況較多，包括1，0，-1，-2，2，3，4，5，-3幾種情況，讀者可在MATLAB的Help中通過搜索函數fmincon查閱；OUTPUT的結構返回結果信息；LAMBDA中的Lagrange為解X處的Lagrange乘子信息。

(8) 當目標函數F和非線性約束條件NONLCON是由MATLAN函數文件給出時，則在fmincon的調用格式中需要用到句柄創建操作符“@”，具體調用格式如下：

    x=fmincon(@ MYFUN,X0,A,B,Aeq,Beq,LB,UB,@ MYCON,OPTIONS)

其中，MYFUN和MYCON是MATLAB函數，例如：

    function F = MYFUN(X)           % 創建目標函數
        F =……                     % 目標函數的表達式
    function [G,Heq] = MYCON(X)     % 創建約束函數
        G =……                     % 非線性不等式約束條件的表達式
        Heq =……                   % 非線性等式約束條件的表達式

(9) 當目標函數F和非線性約束條件NONLCON帶有可變參數時，則需要調用匿名函數，調用格式如下：

    x = fmincon(@ (x)MYFUN1(x,a1),X0,A,B,Aeq,Beq,LB,UB,@ (x)MYCON1(x,a2)
,OPTIONS)

其中，MYFUN1和MYCON1是MATLAB匿名函數，例如：

    function F = MYFUN1(X,a1)          % 創建匿名目標函數
        F =x(1)^2 + a1* x(2)^2         % 目標函數的表達式
    function [G,Heq] = MYCON1(X,a2)    % 創建匿名約束函數
        G =a2/x(1) - x(2)              % 非線性不等式約束條件的表達式
        Heq = []                       % 非線性等式約束條件的表達式

需要指出的是，在此情況下運行fmincon指令之前需要事先對可變參數a1和a2進行賦值。

另外，對于非線性規劃問題的求解，MATLAB的優化工具箱中提供了不止一個函數，之所以這樣做，是出于效率的考慮，不用一個函數“包治百病”。關于其他函數的調用，請查閱相關書籍。

1.2.6 整數線性規劃的MATLAB求解

對于資源利用問題，在決策變量沒有取整數的要求時，自然可用線性規劃求解，但是，在決策變量必須要求取整數時(比如機器設備的臺數、物品的件數、工作人員的數量等)，則線性規劃不可用，需要用整數線性規劃求解。到目前為止，由于MATLAB軟件中沒有專門求解整數線性規劃的函數，因此需要自行編程加以實現。下面，在介紹整數線性規劃的概念及求解方法的基本思想之后，給出MATLAB實現程序。

(1) 整數線性規劃的概念

為了滿足整數的要求，初看起來似乎只要把用線性規劃求得的非整數解按照“四舍五入”的法則化整就可以了。實際上，化整后的數不見得是可行解和最優解，所以應該有特殊的方法來求解最優整數解的問題，稱這樣的問題為整數線性規劃問題(Integer Linear Programming，ILP)。

根據整數線性規劃與線性規劃的定義可知，整數線性規劃的模型與線性規劃的模型只是在決策變量的取值約束上存在差異。因此，在一般的線性規劃中，增加限定：決策變量為整數，即為整數線性規劃。

在整數線性規劃中，如果所有變量都限制為整數，則稱為純整數線性規劃或全整數線性規劃；如果僅一部分變量限制為整數，則稱為混合整數線性規劃。整數線性規劃的一種特殊情形是0-1規劃，它的決策變量的取值僅限于0或1，譬如分配問題、背包問題、旅行商推銷問題、集合覆蓋問題(布點問題)等。

(2) 整數線性規劃的求解

根據整數線性規劃問題的定義可知，放松整數約束后的整數線性規劃問題就變成了線性規劃問題，稱為整數線性規劃的線性規劃松弛問題。由此可知，整數線性規劃問題的解集是線性規劃問題的解集的子集。當松弛問題有界時，由于自變量取值的組合是有限的，從而整數線性規劃的可行解數量有限，我們自然會想到采用窮舉法逐一分析而獲取最優解。然而，其弊端是計算量隨著整數變量數目的增加而呈指數增長。于是，用于求解整數線性規劃問題的普遍方法得以開發。目前，常用分支定界法來求解整數線性規劃問題。

分支定界法的基本思想就是：首先求線性規劃松弛問題，然后視求解情況進行分支定界迭代，直至找到最優解。求解線性規劃松弛問題可能得到以下情況之一。

情況1 線性規劃松弛問題有可行解，而此時整數線性規劃問題卻沒有可行解，則停止。

情況2 線性規劃松弛問題有最優解且解的各分量均為整數，因而它就是整數線性規劃問題的最優解，則停止。

情況3 線性規劃松弛問題有最優解，但不符合整數線性規劃問題中的整數條件要求，此時需要進一步迭代以找到整數解。迭代的基本過程如下：

記線性規劃松弛問題最優解下的目標函數值為f0，如果記整數線性規劃問題的最優目標函數值為f，則一定有f≥f0。

第1步，分支。在線性規劃松弛問題的最優解中任選一個不符合整數條件的變量xj (通常情況下選取最大值的非整數分量構造添加約束條件)，設其值為vj，構造兩個約束條件xj≤[vj]和xj≥[ vj] +1，將這兩個條件分別加入線性規劃松弛問題，從而將線性規劃松弛問題分為兩個后繼子問題——松弛問題1和松弛問題2。不考慮整數條件要求，分別求解松弛問題1和松弛問題2。

第2步，定界。以每個后繼子問題為一分支并標明求解的結果，與其他問題的解進行比較，找出最優目標函數值最小者作為新的下界，替換f0；從已符合整數條件的各分支中，找出目標函數值的最小者作為新的上界f*，從而得知f0 ≤f≤f*。

第3步，比較與剪支。各分支的最優目標函數中若有大于f*者，則剪掉這一分支(說明這一支所代表的子問題已無繼續分解的必要)；若小于f*，且不符合整數條件，則重復上述過程，直至得到最優目標函數值f = f* 為止，從而得到最優整數解。

(3) 分支定界算法的MATLAB實現

根據上述分支定界算法的原理和步驟，這里給出可供調用的分支定界法的MATLAB通用函數程序(命名：Ch1 FZDJ)。程序源碼的具體內容，請參見附錄B(程序01)。該程序是求解純整數線性規劃的通用函數程序。

有時整數規劃問題的解中部分要求取整，部分沒有取整要求，即為混合整數規劃問題。混合整數線性規劃求解的MATLAB實現將在第5章中給出。