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章中给出。