第一章 线性规划

§1 线性规划

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

上述问题的数学模型：设该厂生产x1台甲机床和x2乙机床时总利润最大，则x1,x2

应满足

（目标函数）maxz=4x1+3x2 (1)

?2x1+x2≤10?x+x≤8?12

s.t.（约束条件）? （2）

≤7x?2??x1,x2≥0

（1）式被称为问题的目标函数，（2）中的几个不等式这里变量x1,x2称之为决策变量，

是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性

函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。

1.2 线性规划的Matlab标准形式

线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab中规定线性规划的标准形式为

min cTx x

?Ax≤b?

s.t. ?Aeq?x=beq

?lb≤x≤ub?

其中c和x为n维列向量，A、Aeq为适当维数的矩阵，b、beq为适当维数的列向量。

-1-

例如线性规划

max cTx s.t. Ax≥b x

的Matlab标准型为

min ?cx s.t. ?Ax≤?b

T

x

1.3 线性规划问题的解的概念

一般线性规划问题的（数学）标准型为

max

z=∑cjxj (3)

j=1

n

?n

?∑aijxj=bii=1,2,L,ms.t. ?j=1 (4)

?x≥0j=1,2,L,n?j

可行解 满足约束条件（4）的解x=(x1,x2,L,xn)，称为线性规划问题的可行解，而使目标函数（3）达到最大值的可行解叫最优解。

可行域 所有可行解构成的集合称为问题的可行域，记为R。 1.4 线性规划的图解法 10987654321z=1200246810x1+x2=8(2,6)x2=72x1+x2=10图1 线性规划的图解示意图

图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一族平行直线。对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*=(2,6)，最优目标值

T

z*=26。

从上面的图解过程可以看出并不难证明以下断言：

（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。

（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。

-2-

（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”。

上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足一线性等式

∑ax

ii=1

n

i

=b的点集被称为一个超平面，而满足一线性不等式

∑ax

ii=1

n

i

≤b（或∑aixi≥b）的点集被称为一个半空间（其中(a1,L,an)为一n维行

i=1

n

向量，b为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集Φ也被视为多胞形）。 在一般n维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。

定义1 称n维空间中的区域R为一凸集，若?x,x∈R及?λ∈(0,1)，有

1

2

λx1+(1?λ)x2∈R。

定义2 设R为n维空间中的一个凸集，R中的点x被称为R的一个极点，若不存在x、x∈R及λ∈(0,1)，使得x=λx+(1?λ)x。

定义1 说明凸集中任意两点的连线必在此凸集中；而定义2 说明，若x是凸集R的一个极点，则x不能位于R中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域R的顶点均为R的极点（R也没有其它的极点）。

1.5 求解线性规划的Matlab解法

单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab解法。

Matlab中线性规划的标准型为

1

2

1

2

min cTx x?Ax≤b?

s.t. ?Aeq?x=beq

?lb≤x≤ub?

基本函数形式为linprog(c,A,b)，它的返回值是向量x的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

这里fval返回目标函数的值，LB和UB分别是变量x的下界和上界，x0是x的初始值，OPTIONS是控制参数。

例2 求解下列线性规划问题 max z=2x1+3x2?5x3

s.t. x1+x2+x3=7 2x1?5x2+x3≥10 x1+3x2+x3≤12

x1,x2,x3≥0

-3-

解 （i）编写M文件 c=[2;3;-5];

a=[-2,5,-1;1,3,1]; b=[-10;12]; aeq=[1,1,1]; beq=7;

x=linprog(-c,a,b,aeq,beq,zeros(3,1)) value=c'*x

（ii）将M文件存盘，并命名为example1.m。

（iii）在Matlab指令窗运行example1即可得所求结果。 例3 求解线性规划问题 min z=2x1+3x2+x3

?x1+4x2+2x3≥8?

?3x1+2x2≥6 ?x,x,x≥0?123

解 编写Matlab程序如下： c=[2;3;1];

a=[1,4,2;3,2,0]; b=[8;6];

[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))

1.6 可以转化为线性规划的问题

很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如： 例4 规划问题为

min|x1|+|x2|+L+|xn|

s. t. Ax≤b

T

其中x=[x1Lxn]，A和b为相应维数的矩阵和向量。

要把上面的问题变换成线性规划问题，只要注意到事实：对任意的xi，存在

ui,vi>0满足

xi=ui?vi，|xi|=ui+vi

|x|?xix+|xi|

事实上，我们只要取ui=i，vi=i就可以满足上面的条件。

22TT

这样，记u=[u1Lun]，v=[v1Lvn]，从而我们可以把上面的问题

变成

min s. t. ?

xi

∑(u

i=1

n

i

+vi)

?A(u?v)≤b

?u,v≥0

例5 min{max|εi|}

yi

其中εi=xi?yi。

对于这个问题，如果我们取x0=max|εi|，这样，上面的问题就变换成

yi

-4-

min

x0

s. t. x1?y1≤x0,L,xn?yn≤x0

此即我们通常的线性规划问题。

§2 运输问题(产销平衡)

例6 某商品有m个产地、n个销地，各产地的产量分别为a1,L,am，各销地的需求量分别为b1,L,bn。若该商品由i产地运到j销地的单位运价为cij，问应该如何调运才能使总运费最省？

解：引入变量xij，其取值为由i产地运往j销地的该商品数量，数学模型为

min

∑∑cx

i=1j=1

mn

ijij

?n

?∑xij=ai,i=1,L,m?j=1?m

s.t. ?∑xij=bj,j=1,2,L,n

?i=1

?xij≥0??

显然是一个线性规划问题，当然可以用单纯形法求解。

对产销平衡的运输问题，由于有以下关系式存在：

?n?n?m?m

?bj=∑?∑?∑xij?=∑?∑xij?=∑ai

j=1i=1?j=1?j=1?i=1?i=1

n

m

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由

康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。

§3 指派问题

3.1 指派问题的数学模型

例7 拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？

容易看出，要给出一个指派问题的实例，只需给出矩阵C=(cij)，C被称为指派问题的系数矩阵。

引入变量xij，若分配i干j工作，则取xij=1，否则取xij=0。上述指派问题的数学模型为

min

∑∑cx

i=1j=1

nn

ijij

s.t. xij=1

j=1

∑

n

-5-

∑x

i=1

n

ij

=1

xij=0 或 1

上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0；可以用1,L,n中的一个置换表示。

问题中的变量只能取0或1，从而是一个0-1规划问题。一般的0-1规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为±1），其非负可行解的分量只能取0或1，故约束xij=0或1可改写为xij≥0而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中

m=n，ai=bj=1。

3.2 求解指派问题的匈牙利算法

由于指派问题的特殊性，又存在着由匈牙利数学家Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C=(cij)一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=(bij) ，则以C或B为系数矩阵的指派问题具有相同的最优指派。

例8 求解指派问题，其系数矩阵为

?16?17

C=?

?24??17?1?0

B1=?

?7??1

1521221919191822

22?18?? 17??16?

解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得

04534216

7?1?? 0??0?

再将第3列元素各减去1，得

?10*37??*?0411? B2=?*

?7500??*?1350??

以B2为系数矩阵的指派问题有最优指派

?1234?

??2134??

??

由等价性，它也是例7的最优指派。

有时问题会稍复杂一些。

例9 求解系数矩阵C的指派问题

-6-

?127979??89666?

??

C=?717121412?

??

15146610?????4107106?

解：先作等价变换如下

容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，

最优指派还无法看出。此时等价变换还可进行下去。步骤如下：

(1) 对未选出0元素的行打∨； (2) 对∨行中0元素所在列打∨；

(3) 对∨列中选中的0元素所在行打∨； 重复（2）、（3）直到无法再打∨为止。

可以证明，若用直线划没有打∨的行与打∨的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令∨行元素减去此数，∨列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得

0?127979??50*2

?89666??2300*???

?7?717121412?→?0*1057

???

?6?15146610?80*0?9

??4?636?4107106???0

∨

?7?6

2?0??5?∨? 4?2??∨

?7

?4? ?0??11??0

0

38842030100504

2?0??3? ?4?0??

现在已可看出，最优指派为??

?12345?

。 ??

?24135?

§4 对偶理论与灵敏度分析

4.1 原始问题和对偶问题

考虑下列一对线性规划模型：

max和

cTx s.t. Ax≤b,x≥0 (P)

minbTy s.t. ATy≥c,y≥0 (D)

-7-

称（P）为原始问题，（D）为它的对偶问题。

不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：

（1） 原始问题中的第j列系数与其对偶问题中的第j行的系数相同； （2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同； （3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同； （4） 在这一对问题中，不等式方向和优化方向相反。 考虑线性规划：

mincTx

min

s.t.Ax=b,x≥0

把其中的等式约束变成不等式约束，可得

?A??b?

cTx s.t. ??x≥??,x≥0

??A???b?

它的对偶问题是

?y?

?AT?1?≤c

?y2?

令y=y1?y2，其中y1和y2分别表示对应于约束Ax≥b和?Ax≥?b的对偶变量组。

max

[b

T

?y?

?bT?1?

?y2?

]s.t. AT

[]则上式又可写成

maxbTy s.t. ATy≤c

原问题和对偶的对偶约束之间的关系：

min max

变量

行约束

?≥0?

?≤0 行约束?无限制??≥0?

?≤0 变量?=0?

?≤0??≥0 ?=0??≥0?

?≤0 ?无限制?

4.2 对偶问题的基本性质

1o 对称性：对偶问题的对偶是原问题。

2o 弱对偶性：若x是原问题的可行解，y是对偶问题的可行解。则存在

cTx≤bTy。

3o 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。

?是原问题的可行解，y?是对偶问题的可行解，4o 可行解是最优解时的性质：设x

?=by?时，x?,y?是最优解。 当cx

5o 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。

?,y?分别是原问题和对偶问题的最优解，则 6o 互补松弛性：若x

?(Ax??b)=0,x?(Ay??c)=0 y

例10 已知线性规划问题

minω=2x1+3x2+5x3+2x4+3x5

s.t. x1+x2+2x3+x4+3x5≥4

-8-

T

T

T

TT

2x1?x2+3x3+x4+x5≥3 xj≥0,已知其对偶问题的最优解为y1=解。

解 先写出它的对偶问题

maxz=4y1+3y2

y1+2y2≤2 ①

y1?y2≤3 ②

2y1+3y3≤5 ③ y1+y2≤2 ④ 3y1+y2≤3 ⑤ y1,y2≥0

将y1,y2的值代入约束条件，得②，③，④为严格不等式；由互补松弛性得

*****x2=x3=x4=0。因 y1,y2>0；原问题的两个约束条件应取等式，故有

**

x1+3x5=4 **2x1+x5=3

*

*

*

j=1,2,L,5

4*3

,y2=;z=5。试用对偶理论找出原问题的最优

55

求解后得到x1=1,x5=1；故原问题的最优解为

X=[10001]';ω=5 。

4.3 灵敏度分析

但实际上这些系数往往是估在以前讨论线性规划问题时，假定aij,bi,cj都是常数。计值和预测值。如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；

*

*

**

bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这

些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者

这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。这里我们就不讨论了。

4.4 参数线性规划

参数线性规划是研究aij,bi,cj这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。

§5 投资的收益和风险

5.1 问题提出

市场上有n种资产si（i=1,2,L,n）可以选择，现用数额为M的相当大的资金风险损失率为作一个时期的投资。这n种资产在这一时期内购买si的平均收益率为ri，

qi，投资越分散，总的风险越少，总体风险可用投资的si中最大的一个风险来度量。

-9-

购买si时要付交易费，（费率pi），当购买额不超过给定值ui时，交易费按购买ui

计算。另外，假定同期银行存款利率是r0，既无交易费又无风险。（r0=5%）

已知n=4时相关数据如表1。

表1

qi

si

s1 s2 s3 s4

ri(%) pi(%) ui(元)

28 2.5 1 103 21 1.5 2 198 23 5.5 4.5 52 25 2.6 6.5 40

试给该公司设计一种投资组合方案，即用给定资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。

5.2 符号规定和基本假设 符号规定：

si：第i种投资项目，如股票，债券

ri,pi,qi：分别为si的平均收益率，交易费率，风险损失率 ui：si的交易定额 r0：同期银行利率

xi：投资项目si的资金 a：投资风险度 Q：总体收益

基本假设：

1． 投资数额M相当大，为了便于计算，假设M=1； 2． 投资越分散，总的风险越小；

3． 总体风险用投资项目si中最大的一个风险来度量； 4． n种资产si之间是相互独立的；

5． 在投资的这一时期内，ri,pi,qi，r0为定值，不受意外因素影响； 6． 净收益和总体风险只受ri,pi,qi影响，不受其它因素干扰。 5.3 模型的分析与建立

1． 总体风险用所投资的si中最大的一个风险来衡量，即 max{qixi|i=1,2,L,n} 2．购买si所付交易费是一个分段函数，即 交易费=?

?pixi,?piui,

xi>uixi≤ui

而题目所给定的定值ui（单位：元）相对总投资M很少，piui更小，可以忽略不计，这样购买si的净收益为(ri?pi)xi。

3． 要使净收益尽可能大，总体风险尽可能小，这是一个多目标规划模型：

-10-

目标函数为

n

?

?max∑(ri?pi)xi

?i=0

?minmax{qx}

ii?

约束条件为

?n

?∑(1+pi)xi=M ?i=0

?x≥0,i=0,1,L,n?i

4． 模型简化

a) 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险

qixi

≤a，可找到相应的投资方案。这样把多目标规划变成一个目标的线M

n

性规划。

模型一 固定风险水平，优化收益

max

∑(r?p)x

i

i

i

i=0

?qixi

≤a?M?

s.t. ?n

?∑(1+pi)xi=M,??i=0

xi≥0,i=0,1,L,n

b) 若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻求相应的投

资组合。

模型二 固定盈利水平，极小化风险 min{max{qixi}}

?n

?∑(ri?pi)xi≥k?i=0

s.t. ?n

?(1+p)x=M,∑ii?i=0?

xi≥0,i=0,1,L,n

c) 投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资

组合。因此对风险、收益分别赋予权重s（0

模型三 mins{max{qixi}}?(1?s) s.t.

∑(r?p)x

i

i

i=0

n

i

∑(1+p)x

i

i=0

n

i

=M,

xi≥0,i=0,1,2,L,n

5.4 模型一的求解

模型一为：

minf=(?0.05,?0.27,?0.19,?0.185,?0.185)(x0,x1,x2,x3,x4)

-11-

T

?x0+1.01x1+1.02x2+1.045x3+1.065x4=1?0.025x≤a

1?

??0.015x2≤a s.t. ?

?0.055x3≤a?0.026x4≤a???xi≥0(i=0,1,L,4)

到底怎样没有一个准则，不同的投资者有不同的风险由于a是任意给定的风险度，

度。我们从a=0开始，以步长Δa=0.001进行循环搜索，编制程序如下： clc,clear a=0; hold on

while a<0.05

c=[-0.05,-0.27,-0.19,-0.185,-0.185];

A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])]; b=a*ones(4,1);

Aeq=[1,1.01,1.02,1.045,1.065]; beq=1;

LB=zeros(5,1);

[x,Q]=linprog(c,A,b,Aeq,beq,LB); Q=-Q;

plot(a,Q,'*r'); a=a+0.001; end

xlabel('a'),ylabel('Q')

5.5 结果分析

1. 风险大，收益也大。

2．当投资越分散时，投资者承担的风险越小，这与题意一致。即： 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。

3．在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a=0.6%，Q=20%，所对应投资方案为：

风险度a=0.006，收益Q=0.2019，x0=0，x1=0.24，x2=0.4，x3=0.1091，

x4=0.2212。

习 题 一

1．试将下述问题改写成线性规划问题：

mm

??m?? max?min?∑ai1xi,∑ai2xi,L,∑ainxi??

xi

i=1i=1?i=1???

?x1+x2+L+xm=1

st.?

x≥i=m0,1,L,?i

2．试将下列问题改写成线性规划问题：

-12-

max

z=∑cj|xj|

j=1

n

?n

?∑aijxj=bi(i=1,2,L,m)

st.?j=1

?x取值无约束?j

3．线性回归是一种常用的数理统计方法，这个方法要求对图上的一系列点(x1,y1),(x2,y2),L,(xn,yn)选配一条合适的直线拟合。方法通常是先定直线方程为

y=a+bx，然后按某种准则求定a,b。通常这个准则为最小二乘法，但也可用其他准

则。试根据以下准则建立这个问题的线性规划模型：

min

∑|y

i=1

n

i

?(a+bxi)|

4．某厂生产三种产品I，II，III。每种产品要经过A,B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A1,A2表示；有三种规格的设备能完成B工序，它们以B1,B2,B3表示。产品I可在A,B任何一种规格设备上加工。产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2与B2设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如表2，求安排最优的生产计划，使该厂利润最大。

表2

设备

产 品

设备有效台时

I II III 5 7 6 4 7 0.25 1.25

10 9 8 0.35 2.00

12 11 0.50 2.80

6000 10000 4000 7000 4000

满负荷时的 设备费用(元)

300 321 250 783 200

A1 A2 B1 B2 B3

原料费(元/件) 单 价(元/件)

5．有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如表3。

表3 工作 工人 甲 乙 丙 丁 A B C D 15 18 21 24 19 23 22 18 26 17 16 19 19 21 23 17 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？

-13-

6．某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米，带轻型炸弹时每升汽油可飞行3千米。又知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4千米）外，起飞和降落每次各消耗100升。有关数据如表4所示。

表4

要害部位

1 2 3 4

离机场距离 （千米） 450 480 540 600

摧毁可能性

每枚重型弹 每枚轻型弹

0.10 0.08 0.20 0.16 0.15 0.12 0.25 0.20

为了使摧毁敌方军事目标的可能性最大，应如何确定飞机轰炸的方案，要求建立这个问

题的线性规划模型。

7．用Matlab求解下列线性规划问题： maxz=3x1?x2?x3

?x1?2x2+x3≤11??4x+x+2x≥3?123

s.t. ?

xx21?+=13???x1,x2,x3≥0

8．用Matlab求解下列规划问题：

minz=|x1|+2|x2|+3|x3|+4|x4|

s.t. x1?x2?x3+x4=0

x1?x2+x3?3x4=1 1

x1?x2?2x3+3x4=?

2

9．一架货机有三个货舱：前舱、中仓和后舱。三个货舱所能装载的货物的最大重量和体积有限制如表5所示。并且为了飞机的平衡，三个货舱装载的货物重量必须与其最大的容许量成比例。

表5 货舱数据

前舱 中仓 后舱 重量限制（吨） 10 16 8 体积限制（立方米） 6800 8700 5300

现有四类货物用该货机进行装运，货物的规格以及装运后获得的利润如表6。

表6 货物规格及利润表

重量（吨） 空间（立方米/吨） 利润（元/吨） 货物1 18 480 3100 货物2 15 650 3800 货物3 23 580 3500 货物4 12 390 2850

-14-

假设：

（1）每种货物可以无限细分；

（2）每种货物可以分布在一个或者多个货舱内；

（3）不同的货物可以放在同一个货舱内，并且可以保证不留空隙。 问应如何装运，使货机飞行利润最大？

-15-

第二章 整数规划

§1 概论

1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类

如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： o

1变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为

minz=x1+x2

x1≥0,x2≥0 55

其最优实数解为：x1=0,x2=,minz=。

44

③有可行解（当然就存在最优解），但最优解值变差。

例2 原线性规划为

minz=x1+x2

2x1+4x2=5,

x1≥0,x2≥0 33

其最优实数解为：x1=0,x2=,minz=。

22

若限制整数得：x1=1,x2=1,minz=2。

（ii） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类：

（i）分枝定界法—可求纯或混合整数线性规划。 （ii）割平面法—可求纯或混合整数线性规划。 （iii）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。

（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v）蒙特卡洛法—求解各种类型规划。

下面将简要介绍常用的几种求解整数规划的方法。

§2 分枝定界法

对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，

-16-

2x1+4x2=6,

这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由Land Doig和Dakin等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。

设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z的上界，记作z；而A的任意可行解的目标函数值将是z的一个下界z。分枝定界法就是将B的可行域分成子区域的方法。逐步减小z和增大z，最终求到z。现用下例来说明：

例3 求解下述整数规划

Maxz=40x1+90x2

*

*

*

?9x1+7x2≤56?

?7x1+20x2≤70

?x,x≥0且为整数?12

解 （i）先不考虑整数限制，即解相应的线性规划B，得最优解为：

x1=4.8092,x2=1.8168,z=355.8779

可见它不符合整数条件。这时z是问题A的最优目标函数值z的上界，记作z。而

*

x1=0,x2=0显然是问题A的一个整数可行解，这时z=0，是z的一个下界，记作z，

*

即0≤z≤356。

（ii）因为x1,x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1

*

进行分枝，把可行集分成2个子集：

x1≤[4.8092]=4，x1≥[4.8092]+1=5

因为4与5之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：

问题B1： Maxz=40x1+90x2

?9x1+7x2≤56?

?7x1+20x2≤70

?0≤x≤4,x≥0

12?

最优解为：x1=4.0,x2=2.1,z1=349。

问题B2： Maxz=40x1+90x2

?9x1+7x2≤56?

?7x1+20x2≤70

?x≥5,x≥0

2?1

最优解为：x1=5.0,x2=1.57,z1=341.4。

再定界：0≤z≤349。

（iii）对问题B1再进行分枝得问题B11和B12，它们的最优解为

-17-

*

B11:x1=4,x2=2,z11=340

B12:x1=1.43,x2=3.00,z12=327.14

再定界：340≤z≤341，并将B12剪枝。

（iv）对问题B2再进行分枝得问题B21和B22，它们的最优解为

*

B21:x1=5.44,x2=1.00,z22=308 B22无可行解。

将B21,B22剪枝。

于是可以断定原问题的最优解为：

x1=4,x2=2,z*=340

从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：

开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。

（i）解问题B可能得到以下情况之一：

（a）B没有可行解，这时A也没有可行解，则停止．

（b）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。

（c）B有最优解，但不符合问题A的整数条件，记它的目标函数值为z。

（ii）用观察法找问题A的一个整数可行解，一般可取xj=0,j=1,L,n，试探，求得其目标函数值，并记作z。以z表示问题A的最优目标函数值；这时有

z≤z≤z 进行迭代。

第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示小于bj的最大整数。构造两个约束条件

*

*

xj≤[bj] 和 xj≥[bj]+1

将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。

定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z，若无作用z不变。

第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，即以后不再考虑了。若大于z，且不符合整数条件，则重复第一步骤。一直到最后得到

z*=z为止。得最优整数解x*j,j=1,L,n。

§3 0?1型整数规划

0?1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时xj称为0?1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件： 0≤xj≤1，整数

-18-

所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 0?1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0?1变量的实际问题，再研究解法。

3.1 引入0?1变量的实际问题

3.1.1 投资场所的选定——相互排斥的计划

例4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai(i=1,2,L,7)可供选择。规定

在东区。由A1,A2,A3三个点中至多选两个； 在西区。由A4,A5两个点中至少选一个；

在南区，由A6,A7两个点中至少选一个。

如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？

解题时先引入0?1变量xi(i=1,2,L,7) 令

?1,当Ai点被选中，xi=? i=1,2,L,7.

?0，当Ai点没被选中.

于是问题可列写成： Max

z=∑cixi

i=1

7

?7

?∑bixi≤Bi=1??

?x1+x2+x3≤2

?x+x≥1

5

?4?xi=0或1?x6+x7≥1,

3.1.2 相互排斥的约束条件

有两个相互排斥的约束条件

5x1+4x2≤24 或 7x1+3x2≤45。

为了统一在一个问题中，引入0?1变量y，则上述约束条件可改写为：

?5x1+4x2≤24+yM?

?7x1+3x2≤45+(1?y)M

?y=0或1?

其中M是充分大的数。

约束条件

x1=0 或 500≤x1≤800 可改写为

?500y≤x1≤800y

?

=01y或?

-19-

如果有m个互相排斥的约束条件：

i=1,2,L,m

为了保证这m个约束条件只有一个起作用，我们引入m个0?1变量yi(i=1,2,L,m)和一个充分大的常数M，而下面这一组m+1个约束条件

ai1x1+L+ainxn≤bi+yiMi=1,2,L,m （1）

y1+L+ym=m?1 （2）

就合于上述的要求。这是因为，由于（2），m个yi中只有一个能取0值，设yi*=0，

代入（1），就只有i=i的约束条件起作用，而别的式子都是多余的。

3.1.3 关于固定费用的问题（Fixed Cost Problem）

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。

例5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令

xj表示采用第j种方式时的产量；

*

ai1x1+L+ainxn≤bi

cj表示采用第j种方式时每件产品的变动成本； kj表示采用第j种方式时的固定成本。

为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为

??kj+cjxj,当xj>0

Pj=? j=1,2,3.

??0, 当xj=0 在构成目标函数时，为了统一在一个问题中讨论，现引入0?1变量yj，令

??1,当采用第j种生产方式，即xj>0时，

（3） yj=?

0,当不采用第j种生产方式，即xj=0时.??

于是目标函数

minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)

（3）式这个规定可表为下述3个线性约束条件：

yjε≤xj≤yjM,j=1,2,3 （4） 其中ε是一个充分小的正常数，M是个充分大的正常数。（4）式说明，当xj>0时yj必须为1；当xj=0时只有yj为0时才有意义，所以（4）式完全可以代替（3）式。 3.2 0?1型整数规划解法之一（过滤隐枚举法）

解0?1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2个组合。对于变量个数n较大（例如n>100），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对

-20-

n

有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

下面举例说明一种解0?1型整数规划的隐枚举法。 例6 Maxz=3x1?2x2+5x3

?x1+2x2?x3≤2?x+4x+x≤4123??

?x1+x2≤3

?4x+x≤6

3

?2??x1,x2,x3=0或1

求解思路及改进措施：

（i） 先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且z=3。

（ii） 因为是求极大值问题，故求最优解时，凡是目标值z<3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：

（iii） 改进过滤条件。 （iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z大的组合，这样可提前抬高过滤门槛，以减少计算量。

§4 蒙特卡洛法（随机取样法）

前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。

然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。

例7 已知非线性整数规划为：

2222

Max z=x12+x2+3x3+4x4+2x5?8x1?2x2?3x3?x4?2x5

?0≤xi≤99(i=1,L,5)?x+x+x+x+x≤40012345??

?x1+2x2+2x3+x4+6x5≤800 ?2x+x+6x≤200

23

?1??x3+x4+5x5≤200

如果用显枚举法试探，共需计算(100)=10个点，其计算量非常之大。然而应用蒙特卡洛去随机计算10个点，便可找到满意解，那么这种方法的可信度究竟怎样

呢？

下面就分析随机取样采集10个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。

假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算10个点后，有任一个点能落在高值区的概率分别为

-21-

6

6

6

5

10

1?0.991000000≈0.99L99(100多位）， 1?0.999991000000≈0.999954602。

解 （i）首先编写M文件mente.m定义目标函数f 和约束向量函数g，程序如下： function [f,g]=mengte(x);

f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-... x(4)-2*x(5); g=[sum(x)-400

x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800 2*x(1)+x(2)+6*x(3)-200 x(3)+x(4)+5*x(5)-200];

（ii）编写M文件mainint.m如下求问题的解： rand('state',sum(clock)); p0=0; tic

for i=1:10^6

x=99*rand(5,1);

x1=floor(x);x2=ceil(x); [f,g]=mengte(x1); if sum(g<=0)==4 if p0<=f

x0=x1;p0=f; end end

[f,g]=mengte(x2); if sum(g<=0)==4 if p0<=f

x0=x2;p0=f; end end end x0,p0 toc

本题可以使用LINGO软件求得精确的全局最有解，程序如下： model: sets:

row/1..4/:b;

col/1..5/:c1,c2,x; link(row,col):a; endsets data:

c1=1,1,3,4,2;

c2=-8,-2,-3,-1,-2; a=1 1 1 1 1 1 2 2 1 6 2 1 6 0 0 0 0 1 1 5;

b=400,800,200,200;

-22-

enddata

max=@sum(col:c1*x^2+c2*x);

@for(row(i):@sum(col(j):a(i,j)*x(j))

@for(col:@bnd(0,x,99)); end

§5 指派问题的计算机求解

整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等0?1整数规划问题，可以直接利用Matlab的函数bintprog进行求解。

例8 求解下列指派问题，已知指派矩阵为

?382103??

?

87297?

??

64

275?

??84235?

??9106910???

解：编写Matlab程序如下：

c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5 8 4 2 3 5;9 10 6 9 10]; c=c(:);

a=zeros(10,25); for i=1:5

a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1; end

b=ones(10,1);

[x,y]=bintprog(c,[],[],a,b); x=reshape(x,[5,5]),y

求得最优指派方案为x15=x23=x32=x44=x51=1，最优值为21。求解的LINGO程序如下： model: sets:

var/1..5/;

link(var,var):c,x; endsets data:

c=3 8 2 10 3 8 7 2 9 7 6 4 2 7 5 8 4 2 3 5 9 10 6 9 10; enddata

min=@sum(link:c*x);

@for(var(i):@sum(var(j):x(i,j))=1); @for(var(j):@sum(var(i):x(i,j))=1); @for(link:@bin(x)); end

-23-

§6 生产与销售计划问题

6.1 问题实例

例9 某公司用两种原油（A和B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油的最低比例分别为50％和60％，每吨售价分别为4800元和5600元。该公司现有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨单不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工。

6.2 建立模型 （1）问题分析 安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差。这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。

（2）模型建立

设原油A的购买量为x（单位：吨）。根据题目所给数据，采购的支出c(x)可表示为如下的分段线性函数（以下价格以千元/吨为单位）：

0≤x≤500?10x,

?

c(x)=?1000+8x,500≤x≤1000 （5）

?3000+6x,1000≤x≤1500?

设原油A用于生产甲、乙两种汽油的数量分别为x11和x12，原油B用于生产甲、乙两种汽油的数量分别为x21和x22，则总的收入为4.8(x11+x21)+5.6(x12+x22)（千

元）。于是本例的目标函数（利润）为

z=4.8(x11+x21)+5.6(x12+x22)?c(x) （6）

约束条件包括加工两种汽油用的原油A、原油B库存量的限制，原油A购买量的限制，以及两种汽油含原油A的比例限制，它们表示为

x11+x12≤500+x （7） x21+x22≤1000 （8） x≤1500 （9） x11

≥0.5 （10）

x11+x21

x12

≥0.6 （11）

x12+x22

x11,x12,x21,x22,x≥0 （12） 由于（5）式中的c(x)不是线性函数，（5）~（12）给出的是一个非线性规划，而且，对于这样用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解。能

不能想办法将该模型化简，从而用现成的软件求解呢？

6.3 求解模型 下面介绍3种解法 （1）解法一

-24-

max

一个自然的想法是将原油A的采购量x分解为三个量，即用x1,x2,x3分别表示以价格10千元/吨、8千元/吨、6千元/吨采购的原油A的吨数，总支出为c(x)=10x1+8x2+6x3，且

x=x1+x2+x3 （13）

这时目标函数（6）变为线性函数：

maxz=4.8(x11+x21)+5.6(x12+x22)?(10x1+8x2+6x3) （14） 应该注意到，只有当以10千元/吨的价格购买x1=500（吨）时，才能以8千元/吨的价格购买x2(>0)，这个条件可以表示为

(x1?500)x2=0 （15） 同理，只有当以8千元/吨的价格购买x2=500（吨）时，才能以6千元/吨的价格购买x3(>0)，于是

(x2?500)x3=0 （16） 此外，x1,x2,x3的取值范围是

0≤x1,x2,x3≤500 （17）

由于有非线性约束（15）、（16），因而（7）～（17）构成非线性规划模型。将该模型输入LINGO软件如下： model: sets:

var1/1..4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22; var2/1..3/:x,c; endsets

max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var2:c*x); y(1)+y(3)<@sum(var2:x)+500; y(2)+y(4)<1000; 0.5*(y(1)-y(2))>0; 0.4*y(3)-0.6*y(4)>0; (x(1)-500)*x(2)=0; (x(2)-500)*x(3)=0;

@for(var2:@bnd(0,x,500)); data:

c=10 8 6; enddata end

可以用菜单命令“LINGO|Options”在“Global Solver”选项卡上启动全局优化选型，并运行上述程序求得全局最有解：购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，共生产2500吨汽油乙，利润为5000（千元）。

（2）解法二

引入0－1变量将（15）和（16）转化为线性约束。

令z1=1，z2=1，z3=1分别表示以10千元/吨、8千元/吨、6千元/吨的价格采购原油A，则约束（15）和（16）可以替换为

500z2≤x1≤500z1， （18）

500z3≤x2≤500z2， （19）

-25-

x3≤500z3， （20） z1,z2,z3=0或1 （21）

式（7）～（14），式（17）～（21）构成混合整数线性规划模型，将它输入LINGO软件如下： model: sets:

var1/1..4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22; var2/1..3/:x,z,c; endsets

max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var2:c*x); y(1)+y(3)<@sum(var2:x)+500; y(2)+y(4)<1000; 0.5*(y(1)-y(2))>0; 0.4*y(3)-0.6*y(4)>0;

@for(var1(i)|i #lt# 3:500*z(i+1)

@for(var2:@bin(z));

@for(var2:@bnd(0,x,500)); data:

c=10 8 6; enddata end

（3）解法三

直接处理分段线性函数c(x)。式（5）表示的函数c(x)如图1所示。

记x轴上的分点为b1=0，b2=500，b3=1000。当x属于第1个小区间[b1,b2]时，记x=w1b1+w2b2，w1+w2=1，w1,w2≥0，因为c(x)在[b1,b2]上是线性的，

图1 分段线性函数c(x)图形

所以c(x)=w1c(b1)+w2c(b2)。同样，当x属于第2个小区间[b2,b3]时，

x=w2b2+w3b3，w2+w3=1，w2,w3≥0，c(x)=w2c(b2)+w3c(b3)。当x属于第3个小区间[b3,b4]时，x=w3b3+w4b4，w3+w4=1，w3,w4≥0，c(x)=w3c(b3)+w4c(b4)。为了表示x在哪个小区间，引入0-1变量zk(k=1,2,3)，当x在第k个小区间时，zk=1，否则，zk=0。这样，w1,w2,w3,w4,z1,z2,z3应满

足

w1≤z1，w2≤z1+z2，w3≤z2+z3，w4≤z3 （22）

-26-

w1+w2+w3+w4=1，wk≥0（k=1,2,3,4） （23） z1+z2+z3=1，z1,z2,z3=0或1 （24） 此时x和c(x)可以统一地表示为

x=w1b1+w2b2+w3b3+w4b4=500w2+1000w3+1500w4 （25） c(x)=w1c(b1)+w2c(b2)+w3c(b3)+w4c(b4)

=5000w2+9000w3+12000w4 （26）

式（6）～（13），式（22）～（26）也构成一个混合整数线性规划模型，可以用

LINGO求解。输入的LINGO模型如下： model: sets:

var/1..4/:b,c,y,z,w;

!这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22 端点数为4，即分段数为3; endsets data:

b=0,500,1000,1500; c=0,5000,9000,12000;

z=,,,0; !增加的虚拟变量z(4)=0; enddata

max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var:c*w); y(1)+y(3)<@sum(var:b*w)+500; y(2)+y(4)<1000; 0.5*(y(1)-y(2))>0; 0.4*y(3)-0.6*y(4)>0; w(1)

@for(var(i)|i #ne# 1:w(i)

@for(var:@bin(z)); End

注：这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第2和第3种解法，第3种解法更具一般性，其做法如下。

设一个n段线性函数f(x)的分点为b1≤L≤bn≤bn+1，引入wk将x和f(x)表示为

x

=∑wkbk

k=1

n+1k=1

n+1

f(xk)=∑wkf(bk)

wk和0-1变量zk满足

w1≤z1，w2≤z1+z2，…，wn≤zn?1+zn，wn+1≤zn （27） z1+z2+L+zn=1，zk=0或1 （28） w1+w2+L+wn+1=1，wk≥0（k=1,2,L,n+1） （29）

-27-

习 题 二

1. 用分枝定界法解：

Max z=x1+x2

951?xx+≤?114214?

1?

2xx?+≤?12

3?

?x1,x2≥0,x1,x2整数??

2. 试将下述非线性的0?1规划问题转换成线性的0?1规划问题 maxz=x1+x1x2?x3

?

??2x1+3x2+x3≤3

?xj=0或1，(j=1,2,3)

3. 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2,L,s10，相应的钻探费用为c1,c2,L,c10，并且井位选择上要满足下列限制条件：

（1） 或选择s1和s7，或选择钻探s9；

（2） 选择了s3或s4就不能选s5，或反过来也一样；

（3） 在s5,s6,s7,s8中最多只能选两个；试建立这个问题的整数规划模型。 4．有一条河流由于河床泥沙淤结，每当上游发生洪水时，就会破堤淹没两岸，造成人员和财产的损失，为减少总的损失，人们采取破堤泄洪的方法，图2是该河流一岸区域的信息示意图，在该区域边界上有很高的山，使该区域成为封闭区域。区域内又分成十五个小区，每个小区内标有三个数字，分别表示该区域的海拔高度h(m)、面积

S(km2)和被完全淹没时土地、房屋和财产等损失总数k（百万元），我们假设

（a）各小区间有相对高度为1.2m的小堤相互隔离，例如第一区和第二区之间事实上有海拔5.2m小堤。

（b）当洪水淹没一个小区且洪水高于该小区高度pm时，该小区的损失f(k,p)为该小区的k和p的函数：

?kp,0≤p≤1

f(k,p)=?

k,p≥1?

（c）假设决堤口，可选在大堤或小堤的任何地方，决堤口的数量不受限制，但已

经决口，就不能再补合，从河流经大堤决口流入小区的洪水量按决口数成比例分配，如在小区之间小堤开一决口，则假设该两小区之间的这段小堤不复存在，若水位高过小堤，则将自动向邻近最低的小区泄洪，若这样的小区有多块时，则平均泄洪。

求

（1）整个区域全部受损失的最小洪水量Q。 （2）当洪水量为Q/6，Q/3时，分别制定泄洪方案，使总损失最小（在一种方案中，决堤同时进行），并计算出该方案的损失数。

-28-

河 流 高 山 H3.6 S6.1 K1.4 1 111H4.0 S8.4 K7.0 2 2H4.7 S7.0 K5.8 33 H4.4 S9.3 K3.3 4 1H3.8 S4.8 K2.0 5 551大堤H3.3 H3.2 H2.5 H5.0 S3.6 S0.9 S8.5 S1.8 K9.4 6 K0.9 7 K6.0 8 K7.2 9 H4.4 S0.1 K1.6 10 H3.0 H2.5 S4.6 S1.5 K3.0 11 K4.1 12 H2.4 H3.8 H3.8 S2.3 S8.8 S1.3 K4.1 13 K5.3 14 K4.4 15 高 山 图2 河流一岸区域示意图

表1 校址选择数据

备选校址 覆盖的居民小区

B1 B2 B3 A1,A3,A5

B4 B5 A3,A6

B6 A4,A6A8

A1,A5A7

A1,A2A5,A8

A2,A4A8

5．某市为方便小学生上学，拟在新建的8个居民小区A1,A2,L,A8增设若干所小学，经过论证知备选校址有:B1,B2,L,B6,它们能够覆盖的居民小区如表1。 试建立一个数学模型，确定出最小个数的建校地址，使其能覆盖所有的居民小区。 6．某公司新购置了某种设备6台，欲分配给下属的4个企业，已知各企业获得这种设备后年创利润如表2所示，单位为千万元。问应如何分配这些设备能使年创总利润

-29-

最大，最大利润是多少？

表2 各企业获得设备的年创利润数 企业 设备 甲 乙 丙 丁 1 4 2 3 4 2 6 4 5 5 3 7 6 7 6 4 7 8 8 6 5 7 9 8 6 6 7 10 8 6 7．有一场由四个项目(高低杠、平衡木、跳马、自由体操) 组成的女子体操团体赛，赛程规定：每个队至多允许10名运动员参赛，每一个项目可以有6名选手参加。每个选手参赛的成绩评分从高到低依次为：10；9.9；9.8；…；0.1；0。每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者。此外，还规定每个运动员只能参加全能比赛(四项全参加) 与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三个单项。每个队应有4人参加全能比赛，其余运动员参加单项比赛。 表3 运动员各项目得分及概率分布表 运动员 项目 1 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 9.1~0.1 9.3~0.1 9.5~0.6 9.8~0.2 8.7~0.1 8.9~0.2 9.1~0.6 9.9~0.1 2 9.3~0.1 9.5~0.1 9.6~0.6 9.8~0.2 8.4~0.15 9.0~0.5 9.2~0.25 9.4~0.1 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.9~0.1 9.1~0.1 9.3~0.6 9.6~0.2 3 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.1~0.1 9.1~0.5 9.3~0.3 9.5~0.1 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 9.5~0.1 9.7~0.1 9.8~0.6 10~0.2 4 8.1~0.1 9.1~0.5 9.3~0.3 9.5~0.1 8.7~0.1 8.9~0.2 9.1~0.6 9.9~0.1 9.0~0.1 9.4~0.1 9.5~0.5 9.7~0.3 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 5 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 9.0~0.1 9.2~0.1 9.4~0.6 9.7~0.2 8.3~0.1 8.7~0.1 8.9~0.6 9.3~0.2 9.4~0.1 9.6~0.1 9.7~0.6 9.9~0.2 高低杠 平衡木 跳马 自由体操 续表3 运动员各项目得分及概率分布表 运动员 项目 6 9.4~0.1 9.6~0.1 9.7~0.6 9.9~0.2 8.7~0.1 7 9.5~0.1 9.7~0.1 9.8~0.6 10~0.2 8.4~0.1 8 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.8~0.05 9 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 8.4~0.1 10 9.0~0.1 9.2~0.1 9.4~0.6 9.7~0.2 8.1~0.1 高低杠 平衡木 -30-

跳马

自由体操

8.9~0.2 9.1~0.6 9.9~0.1 8.5~0.1 8.7~0.1 8.9~0.5 9.1~0.3 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.3~0.1 8.7~0.1 8.9~0.6 9.3~0.2 8.4~0.1 8.8~0.1 9.2~0.6 9.8~0.2 9.2~`0.05 9.8~0.5 10~0.4 8.7~0.1 8.9~0.2 9.1~0.6 9.9~0.1 8.2~0.1 9.3~0.5 9.5~0.3 9.8~0.1 8.8~0.1 9.2~0.6 9.8~0.2 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 9.3~0.1 9.5~0.1 9.7~0.5 9.9~0.3 9.1~0.5 9.3~0.3 9.5~0.1 8.2~0.1 9.2~0.5 9.4~0.3 9.6~0.1 9.1~0.1 9.3~0.1 9.5~0.6 9.8~0.2

现某代表队的教练已经对其所带领的10名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩稳定在4个得分上(见表3) ，她们得到这些成绩的相应概率也由统计得出(见表中第二个数据。例如：8.4～0.15表示取得8.4分的概率为0.15)。试解答以下问题：

（1）每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高；每个选手的各单项得分按均值估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高。

（2）若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计为不少于236.2分，该队为了夺冠应排出怎样的阵容？以该阵容出战，其夺冠的前景如何？得分前景（即期望值）又如何？它有90％的把握战胜怎样水平的对手？

-31-