运筹学讲解1

第1节 线性规划问题及其数学模型 1．1 问题的提出 1.1.1 引例

例1．可取为教学参考书P8例1，或随堂构造一个相当的例子。

通过例1，得出线性规划模型的构成，并引出线性规划模型的一般形式。1.1.2 数学模型一般形式

optzcjxjj1n(1)i1,2,,mj1,2,,n(2)(3)naijxj(,)bis..tj1x0j

其中：⑴为目标函数；⑵和⑶为约束条件；opt=max或min。 1.1.3 数学模型特征

线性规划数学模型特征为：

⑴ 解向量x(x1,x2,...,xn)T描述方案； ⑵ 所有式子均为线性式子； ⑶ 目标函数追求极大化或极小化。 1．2 图解法 线性规划的图解法(解的几何表示)一般只用于求解只有两个变量的线性规划问题，实用意义不大。但可以在二维直角坐标平面上作图表示线性规划问题的有关概念和解的情况等，帮助初学者了解线性规划问题的求解过程。 1.2.1 相关概念 1.2.1.1 函数梯度

函数梯度方向是函数值增长最快的方向，这里以行向量描述梯度。 目标函数的梯度记为C=(c1,c2,,„，cn)。 1.2.1.2 线性式子的几何意义

线性等式代表一个超平面（二维时为一条直线）； 线性不等式代表一个半空间（二维时为一个半平面）。

1

1.2.1.3 一些解的概念

以数学模型一般形式为基准，介绍一些相关概念。 解：x的一个值称为一个解。 可行解：满足约束条件的解。 可行域：可行解的集合。 最优解：满足⑴的可行解。

最优值：与最优解对应的目标函数值。 1.2.2 图解法的步骤 1.2.2.1 确定可行域

可行域为各约束式子对应的区域的交。

如果可行域为空集，问题无可行解，否则，问题有可行解。 1.2.2.2 确定最优方向P

Coptmax PCoptmin1.2.2.3 确定最优解

据P和可行域的情况，可以确定解的情况：

如果目标函数值可以趋向无穷大，则问题无有限最优解，否则可以在可行域边界上取得最优解。 1.2.3 解的情况

讨论可行域和解（求解结果）的可能组合。 1.2.3.1 可行域为空集

此时无可行解。

2

① x2 ③ 例2A ② 10 maxzx1x1x210 s..tx1x25x,x012B 可行域为空集 无可行解 5 ④ x1 D O P 5 10 E 1.2.3.2可行域非空有界

⑴ 唯一最优解

x2 ② ③ 例3A 10 maxzx1x1x210 s..tx1x25x,x012B 5 ④ xx(10,0) *z10O P Z=0

3

*ETx1 D 5 Z=5 10 Z=10 ① E ⑵ 无穷多最优解

x2 ② ④ 例4A 10 maxzx1x2x1x210 s..tx1x25x,x012B x*xA(1xE,0,1z10*5 ③ D O P 5 Z=0 10 Z=5 E ① Z=10 x1 1.2.3.3可行域非空无界

⑴ 唯一最优解

x2 ③ ① 例510 minzx1x2x15 s..tx25x,x012② A 5 xx*Bz*5 B O P 5 Z=0 Z=5 10 ④ x1 4

⑵ 无穷多最优解

x2 ③ ① 例610 minzx1x15 s..tx25x,x012② x1 10 Z=5 x*xA(1xB,0,1z*5A 5 ④ B O P Z=0 5 ⑶ 无有限最优解

x2 ③ ① 例710 maxzx1x2x15 s..tx25x,x012② ④ A 5 maxz P O B 5 Z=0

5

x1 10 Z=5 Z=10 1.3 标准型 1.3.1 标准型

标准型为:

maxzcjxjj1n(1)(2)(3)naijxjbi0i1,2,,ms..tj1x0j1,2,,nj标准型也可写为向量形式：

maxzcxnPjxjb0s..tj1x0j1,2,,nj(1)(2) (3) 式中：c(c1,c2,...,cn)；b(b1,b2,...,bm)T；Pj(a1j,a2j,...,amj)T。

标准型也可写为矩阵形式：

maxzcxAxb0s..tx0(1)(2) (3)式中：A(P1,P2,...,Pn)。 1.3.2 化标准型

将不符合标准型要求的数学模型化为标准型。 设已得：

optzcjxjj1kk)iaijxj(,b j1jJ1s..txj0x0jJ2jjJ3xj无约束i=1,2,

,m ⑴ 变换1

① minzcxjj1kjmax(z)cjxj

j1k 6

②

axijj1kj(,)bi0aijxj(,)bij1k

③ xj无约束——>以xjxj取代xj，xj，xj0。 ④ xj≤0——>以xj取代xj，xj 0。

经变换1，得如下形式的数学模型：

maxzcjxjj1kkaijxj(,)bi0s..tj1x0j=1,2,,kj⑵ 变换2

①

i=1,2,,m

aj1kkijxjbi0 aijxjxsibi，松弛变量xsi0，csi0。

j1k②

aj1ijxjbi0 aijxjxsibi，剩余变量xsi0，csi0。

j1k经变换2，得标准型。 ⑶ 变换3

必要时，变更变量的文字符号。 1.4 解的概念

以标准型为基础，讨论解的概念。 设rAm。

基：A的m阶非奇异子矩阵，记为B。 基向量:构成B的系数列向量。

非基向量：A中除基向量外的系数列向量。 基变量：与基向量对应的变量。 非基变量：与非基向量对应的变量。

基本解：令非基变量为零，由（2）得到的解。 基本可行解：满足（3）的基本解。 可行基：与基本可行解对应的基。

7

最优基：与满足（1）的基本可行解对应的基。 例4．随堂构造一个例子或取为(P)0的一个特例。

通过例4引出一些相关的概念。

第2节 线性规划问题的几何意义 2.1 基本概念

（1）凸集

设D为Rn上的点集，若对x1,x2D,[0,1],有x1(1)x2D，则称D为凸集。

（2）凸组合

设x,x,...,xRn，1,2,...,K[0,1]，j1，则称xjxj为

12Kj1j1KKx1,x2,...,xK的凸组合。

（3）顶点

设D为凸集,xD，x1,x2D且x1x2，若x不能用xx1(1)x2，

(0,1)表示，则称x为D的顶点。 2．2 基本定理

定理1.若线性规划问题有可行域，则其可行域是凸集。 定理2.线性规划问题的基本可行解对应于可行域的顶点。

定理3.若线性规划问题有可行域，则必有基本可行解。 定理4.若线性规划问题有最优解，则可以在可行域顶点上达到 最优。

定理5.最优解的凸组合仍然是最优解。

8

x2 ② ③ A 10 maxzx1x2x1x210 s..tx1x25x,x012B x*xA(1xE,0,1z10*5 ④ D O P 5 Z=0 10 Z=5 E ① Z=10 x1 1110A1,P2,P3,P4 P1101

t 0 1 2 3 4 Pt1,Pt2 xt1,xt2 xt3,xt4 基本解xT= 基本解是 (x1,x2,x3,x4)T 否可行 (5,0,5,0)T (10,0,0,5)T (0,5,5,0)T (0,10,0,5) Tzt 5 10* 5 10* - 对应的可 行域顶点 D E B A - P1,P3 P1,P4 P2,P3 P2,P4 P3,P4 x1,x3 x2,x4 x2,x3 x1,x4 x1,x3 是 是 是 是 否 x1,x4 x2,x3 x2,x4 x3,x4 x1,x2 (0,0,10,5)T 2．3 枚举法

如果问题有最优解，则找出所有的可行基，比较对应的 目标函数值，得最优基本可行解，作它们的凸组合得最优解 得表达式。

如果可行域非空有界，一定可以用枚举法取得最优解。

9

如果可行域非空无界，不一定可以用枚举法取得最优解。 第3节 单纯形法

单纯形法是求解线性规划问题的一种基本方法。 3．1 求解原理

原理（有最优解）：确定一个可行域顶点，如果尚未求得所有的 最优顶点，则在目标函数值不劣化的前提下，寻找新顶点，直至 求得所有的最优顶点为止。

最优顶点的凸组合代表了更多的最优解。

由于解的情况不只是有最优解一种，这样我们求解时必须 解决下述几个问题：

假设原来的问题为P0,求解时的问题为P（符合标准型的要求），则 ⑴ P一定有可行解； ⑵ 确定初始顶点的方法；

⑶ 对顶点进行解的检验，要求可以判别出： ① P0无可行解的情形； ② P0无有限最优解的情形；

③ 如果有最优解，则当前顶点是否最优顶点以及是否取得了 所有的最优顶点的判别方法。

单纯形法中，对每个顶点进行解的检验，如果出现无有限最优解的特征，退出运算；当前顶点为最优顶点时，需判别P0是否无可行解，如果没有P0无可行解的特征，应判别是否取得了所有的最优顶点。

为便于对顶点的判别，应制定对应的模型格式。

⑷ 顶点变换（从当前顶点出发，在目标函数值不劣化的前提下，确定新顶点）；

⑸ 最优顶点的凸组合。 这里只需解决问题⑴－⑷。 3．2 规范型和规范标准型

规范型和规范标准型是便于解的判别的模型格式。

10

设(P)为:

maxzcx (1)

s.t. Axb0 (2) x0 (3) 又设rAm,Bt(Pt1,Pt2,...,Ptm)(t=0,1,„)为第t+1个基,则(P)关于Bt的规范型(P)t为:

tt+∑maxzcBtBt1b(ccBtBt1A)xz0(ccBtAt)x=z0t

x (1)t

s.t. Bt1AxAtxBt1bbt (2)t x0 (3)t

ttttt式中cBt(ct1,ct2,...,ctm),AtBt1A(P1,P2,,Pm,P(m1),,Pn)， tttttttAtBt1A(Pt1,Pt2,,Ptm,Pt(m1),,Ptn)(Bt,Nt)

为方便，A也可记为A(Pt1,Pt2,,Ptm,Pt(m1),,Ptn)(Bt,Nt)，c和x也可采取类似记法。

C(ct1,ct2,,ctm,ct(m1),,ctn)(CBt,CNt),

xBtx(xt1,xt2,,xtm,xt(m1),,xtn)xNtT。 Bt下的基本解xt为：

xBt(xt1,xt2,...,xtm)T=bt, xNt(xt(m1),xt(m2),...,xtn)T=0,

tzt=z0 。

tttt称∑t＝(1t,2,...,n)或∑＝(tt1,tt2,...,tn)为Bt下的检验数向量，

称tjcjcBtBt1PjcjcBtPjt称为xj的检验数，

tt或称tjctjcBtBt1PccPtjtjBttj为xtj的检验数。

易知基变量的检验数为零。

11

若Bt为可行基,则称(P)t为(P)关于Bt的规范标准型。 3．3 确定初始顶点x0 3．3．1 确定(P)

设已得P0：

maxzcjxjj1kkiI1aijxjbi0j1k iI2aijxjbi0s..tj1kaijxjbi0iI3j1x0j1,2,,kj式中：I1I2I31,2,...,m。

P0可以在建模后，经由化标准型的一些步骤取得。 P0做下述变换：

（1）对iI1，aijxjbi0 aijxjxsibi，松弛变量xsi0，

j1j1kkcsi0。

（2）对iI2，aijxjbi0 aijxjxGibi0，人工变量

j1j1kkxGi0，cGiM。

（3）对iI3，aijxjbi0 aijxjxsixGibi，剩余变量

j1j1kkxsi0，csi0，人工变量xGi0，cGiM。

可得P（符合标准型的要求）： 12

maxzcx (1)

(P) s.t. Axb0 (2)

x0 (3)

3．3．2 确定(P)0

依次（依i的次序）取(P)中的Psi和PGi为基向量：“≤”型约束中xsi的系数列向量Psi，“≥”型约束和“＝”型约束中xGi的系数列向量PGi。这些向量排成一个单位矩阵,取这个矩阵为初始单位基B0。

(P)0：

1100+∑maxzcB0B0b(ccB0B0A)xz0(ccB0A0)x=z00

x (1)0

11 s.t. B0AxA0xB0bb0 (2)0

x0 (3)0 如果没有引入人工变量,则cB0=0, (P)0与(P)相同。

令B0下的非基变量为零,得初始基本可行解x0,x0对应于初始顶点。 3．4 解的检验

tttt称∑t＝(1t,2,...,n)或∑＝(tt1,tt2,...,tn)为(P)t下的检验数，其中

tjcjcBBt1PjcjcBPjt。

tt易知，基变量的检验数为零。

定理6.对(P)t,若∑t ≤ 0,则xt为最优解。

证明：设对(P)t,有∑t ≤ 0,若xt不是最优解，则设最优解为x，

t对应的zztjxj≤z0=zt，矛盾。

t0j1nt定理7.若k>0且Pkt0，则(P)无有限最优解。

证明：对(P)t，有

13

Ptitbitbt （1）

i1t和 aik（2） PtitPkt

i1mm取>0，乘以（2）式两边并移项得：

t Paik（3） Ptit0

tki1m将（3）加入（1）左端并整理得：

t (bitaik（4） )PtitPktbt

i1m由（4）可知x为：

t bitaik i=1,2,„,m xti  ti=k 0 i=m+1,m+2,…,n且tik

tt易知x为可行解，zz0。 k当，z，故(P)无有限最优解。

t定理8.设xt为最优解，若存在非基变量xk，有k＝0且lt0，则

bitblt(P)有无穷多最优解。（注：这里mint） ttaik0aalkiktlbitblt证明：设x为最优解，若存在非基变量xk，有＝0且min t0，ttaik0aaiklkttktl仿照定理7构造xt1：

t bitaik i=1,2,„,m t1 xti  ti=k 0 i=m+1,m+2,…,n且tik

t为使xt1可行，取0，并且只需考虑对i=1,2,„,m,有bitaik0。这

14

时有下述情形：

tt（1）aik0，则bitaik0；

ttt（2）aik>0，若取bitaik，则bitaik0。

bitblt取＝mint， ttaik0aalkiktlttttt则xt1为基本可行解，zt1z0，从而xt1也是最优解，kz0lkkz0进而x*xt(1xt1{0,1}也是最优解，定理得证。

定理9.设xt中有人工变量，若xt为最优解且其中人工变量不全为零，则P0无可行解。

证明：设xt中有人工变量、xt为最优解且其中人工变量不全为零。 设P0有可行解x'，x为(P)中与之对应的可行解，，由于x中人工变量一定取零值，因此x优于xt，矛盾。

据定理6－定理9，可以对(P)t进行解的检验。 3．5 基变换

未求得所有最优基本可行解且未出现无有限最优解特征时，应进行基变换。 基变换规则为一入一出，即先从当前非基向量中挑选一个向量作为新的基向量（入基向量），再从当前基向量中挑选一个向量作为新的非基向量（出基向量）。

与入基向量对应的变量称为入基变量，与出基向量对应的变量称为出基变量。

3．5．1 入基向量的确定

入基向量Pk（或Pkt）由下式确定：

t kmaxtj│tj0,xj为非基变量3．5．2 出基向量的确定

仿照3．4中定理8的证明，构造xt1，

15

t出基向量Ptl（或Ptl）由下式确定：

bitbltmint ttaik0aalkiktltt由于lt＝bltalk，所以bltalk即xt1可行解，非零分量个数不超过m。 0，tttt注意zt1z0，因而xt1不劣于xt，从xt到xt1的变换是可取klztz0的。

3．5．3 新基Bt1

与xt1对应的可行基Bt1为：

Bt1(Pt1,Pt2,...,Pt(l1),Pk,Pt(l1),...,Ptm)(P(t1)1,P(t1)2,...,P(t1)(l1),P(t1)l,P(t1)(l1),...,P(t1)m)显然，xt1为基本可行解。 3．6 单纯形表

单纯形表包含(P)t、对xt解的检验和基变换的信息，其格式如表1。 表1中：-z、cj、cB、xB、b、θ为文字符号；x为文字符号x1,x2,„,xn；cB为具

t体值的对

cB cj xB b c x 转置；其余为具体值；其中θt＝（θit）m×1,θ tt>0，itbitaik，否则it－。 aikcBt xBt bt

3．7 旋转变换

At θt 表1

-z t Σt z0旋转变换即从(P)t出发求(P)t1。

t以alk为主元素进行旋转变换，旋转变换后各元素值为：

16

①t/④t 主元行元素

①t+1＝ ①t-②t×③t/④t 与主元素不同行不同列元素

0 非主元行的主元列元素

式中：①为待求新值的元素；④为主元素；②和③为由①和④决定的矩形的

t

t

t

t

t

t

另外两个顶点。

第4节 单纯形法的计算步骤

举例说明上述定理和单纯形法的求解过程。 例：P8例1。

maxz2x13x28x12x24x16 1s..t4x212j1,2xj0

cj cB xB b x3 8 2 3 0 0 0 x1 x2 x3 x4 x5 1 2 1 0 0 θ 8/2 - 12/4 0 0 ○0 x4 16 4 0 0 1 0 0 x5 12 0 4 0 0 1 ○-z cj cB xB b 2 2 3 0 0 0 x1 x2 x3 x4 x5 0 2 3 0 0 0 θ 2/1 16/4 - ① 0 x3 1 0 1 0 -1/2 ○4 0 0 1 0 0 1 0 0 1/4 0 x4 16 3 x2 3 -z

-9 2 0 0 0 -3/4 17

cj cB xB b 2 8 3 -13 2 3 0 0 0 x1 x2 x3 x4 x5 1 0 1 0 -1/2 0 0 -4 1 ○2 0 1 0 0 1/4 θ - 8/2 3/（1/4） ② 2 x1 0 x4 3 x2 -z

cj cB xB 0 0 -2 0 1/4 2 3 0 0 0 b 4 4 2 -14 x1 x2 x3 x4 x5 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0 θ ③ 2 x1 0 x5 3 x2 -z

最优解最优值x*x3(4,2,0,0,4)Tzz14*3

第5节 单纯形法的进一步讨论 5．1 人工变量法 5．1．1 大M法

视－M为充分小的负数，按单纯形法求解。 例：P32例8。

minz3x1x2x311x12x2x34xx2x3 123s..t12x1x3j1,2,3xj0

18

0 ○cB 0 -M-M z ① cB 0 -M-1 z ② cB 0 -1 -1 z ③ cB 3 -1 -1 cj xB x1 x2 x3 b 4 1 9 3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6 x7 1 0 0 1/3 -2/3 2/3 -5/3 0 1 0 0 -1 1 -2 0 0 1 2/3 -4/3 4/3 -7/3 θ cj xB x4 x2 x3 b 12 1 1 2 3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6 x7 3 0 0 1 -2 2 -5 ○0 1 0 0 -1 1 -2 -2 0 1 0 0 0 1 1 0 0 0 -1 1-M -1-M θ 12/3 - - cj xB x4 x6 x3 b 10 1 1 1+M 3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6 x7 3 -2 0 1 0 0 -1 0 ○1 0 0 -1 1 -2 -2 0 1 0 0 0 1 1 -1+M 0 0 -M 0 1-3M θ - 1/1 - cj xB x4 x6 x7 b 11 3 1 3 -1 -1 0 0 -M -M x1 x2 x3 x4 x5 x6 x7 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 ○1 0 0 0 1 θ 11/1 3/2 1/1 4M 3-6M -1+M -1+3M 0 -M 0 0 19

z -2 0 0 0 -1/3 -1/3 1/3-M 2/3-M

最优解最优值x*x3(4,1,9,0,0,0)Tzz2*35．1．2 两阶段法

由于M是个不确定的数，可能引起求解的失误，故引入两阶段法。 第一阶段，求解(P)的辅助问题(P)。

minwiI2I3xGi

(P) s.t. Axb

x0

若w*=0,转第二阶段，否则无可行解。

第二阶段，对第一阶段的最优表，删去人工变量所在的列，恢复(P)的 价值系数，重新计算检验数行的数值，按单纯形法求解。 举例说明二阶段法的求解过程。 例：P32例8。 第一阶段求解：

(P)：

max(w)x6x7x411x12x2x34xx2xxx3 12356s..tx712x1x3xj0j1,2,,7 0 ○cB 0 -1 -1 w cj xB x4 x6 x7 b 11 3 1 4 0 0 0 0 0 -1 -1 x1 x2 x3 x4 x5 x6 x7 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 ○1 0 0 0 1 -6 1 3 0 -1 0 0 θ 11/1 3/2 1/1 20

① cB 0 -1 0 w ② cB 0 0 0 w cj xB x4 x6 x3 b 10 1 1 1 0 0 0 0 0 -1 -1 x1 x2 x3 x4 x5 x6 x7 3 -2 0 1 0 0 -1 0 ○1 0 0 -1 1 -2 -2 0 1 0 0 0 1 0 1 0 0 -1 0 -3 θ - 1/1 - cj xB x4 x2 x3 b 12 1 1 0 0 0 0 0 0 -1 -1 x1 x2 x3 x4 x5 x6 x7 3 0 0 1 -2 2 -5 0 ○1 0 0 -1 1 -2 -2 0 1 0 0 0 1 0 0 0 0 0 -1 -1 θ - 1/1 - w*=0,转第二阶段：

0 ○cB 0 -1 -1 z ① cB 3 -1 -1 z cj xB x4 x2 x3 b 12 1 1 2 3 -1 -1 0 0 x1 x2 x3 x4 x5 3 0 0 1 -2 ○0 1 0 0 -1 -2 0 1 0 0 1 0 0 0 -1 θ 12/3 - - cj xB x1 x2 x3 b 4 1 9 -2 3 -1 -1 0 0 x1 x2 x3 x4 x5 1 0 0 1/3 -2/3 0 ○1 0 0 -1 0 0 1 2/3 -4/3 0 0 0 -1/3 -1/3 θ - 1/1 - 21

最优解最优值5．2 退化

x*x1(4,1,9,0,0)Tzz2*1

5．3 检验数的几种表达方式 5．4 单纯形法小结 第6节 应用举例 例：P38例10。题略。

长度 （m） 2.9 2.1 1.5 合计 料头 方案锯截根数 数模如下：

下料根数 方案Ⅰ 方案Ⅱ 方案Ⅲ 方案Ⅳ 方案Ⅴ 1 0 3 7.4 0 x1 2 0 1 7.3 0.1 x2 0 2 2 7.2 0.2 x3 1 2 0 7.1 0.3 x4 0 1 3 6.6 0.8 x5 minw0.1x20.2x30.3x40.8x5x4100x12x22x32x4x5100 s..t3x1x22x33x5100xj0j1,2,,5例：P38例11。题略。

C B 产品名称 A 规格要求 原材料C不少于50％ 原材料P不超过25％ 原材料C不少于25％ 原材料P不超过50％ 不限 单价（元/kg） 50 35 25 22

目函

C 投入原材料：P H 产品单价（元/kg） 产出产品： A B C x1 x4 x7 x2 x5 x8 x3 x6 x9 50 35 25 单价 （元/kg） 65 25 35 每天最多供应量 （kg） 100 100 60 标数：

maxz产品销售收入－原材料成本＝50(x1x2x3）＋35（x4x5x6）＋25（x7x8x9）

65(x1x4x7）+25(x2x5x8）+35(x3x6x9）15x125x215x330x410x540x710x9约束条件：

⑴ 产品A规格要求：

x1(x1x2x3)0.5x2(x1x2x3)0.25

⑵ 产品B规格要求：

x4(x4x5x6)0.25x5(x4x5x6)0.5

⑶ 原材料可用量约束：

x1x4x7100x2x5x8100 x3x6x960⑷ 无负产量约束：

xj0

j1,2,,9

例：P41例12。题略。

23

产 售价 单件 工时 库存费 期末库存量 单件成本 (元/件) 加班 品 (元/件) (h/件) (元/件.月) （件） 正常 1 2 3 4 5 产 品 1 2 3 4 5

产 分月份正常生产量（件） 分月份库存量（件） 0 1 2 3 4 5 6 w10＝0 w11 w12 w13 w14 w15 w16＝k1 w20＝0 w21 w22 w23 w24 w25 w26＝k2 w30＝0 w31 w32 w33 w34 w35 w36＝k3 w40＝0 w41 w42 w43 w44 w45 w46＝k4 w50＝0 w51 w52 w53 w w55 w56＝k5 正常生产可用工时(h) 加班生产可用工时(h) s1 s2 s3 s4 s5 a1 a2 a3 a4 a5 H1 H2 H3 H4 H5 k1 k2 k3 k4 k5 c1 c2 c3 c4 c5 c1' ' c2' c3' c4' c5分月份最大需求量（件） 1 2 3 4 5 6 d11 d12 d13 d14 d15 d16 d21 d22 d23 d24 d25 d26 d31 d32 d33 d34 d35 d36 d41 d42 d43 d44 d45 d46 d51 d52 d53 d d55 d56 r1 r2 r3 r4 r5 r6 r1' r2' r3' r4' r5' r6' 分月份加班生产量（件） 1 2 3 4 5 6 '''''' x12 x13 x14 x15 x16 x11品 1 2 3 4 5 6 1 x11 x12 x13 x14 x15 x16 2 x21 x22 x23 x24 x25 x26 3 x31 x32 x33 x34 x35 x36 4 x41 x42 x43 x44 x45 x46 '''''' x22 x23 x24 x25 x26 x21'''''' x32 x33 x34 x35 x36 x31'''''' x42 x43 x44 x45 x46 x41''''''5 x51 x52 x53 x x55 x56 x51 x52 x53 x x55 x56 24

目标函数：

产 分月份销售量（件） 品 1 2 3 4 5 6 1 y11 y12 y13 y14 y15 y16 2 y21 y22 y23 y24 y25 y26 3 y31 y32 y33 y34 y35 y36 4 y41 y42 y43 y44 y45 y46 5 y51 y52 y53 y y55 y56 maxz=（产品销售收入－正班成本－加班成本）－库存费＝Siyij-cixij-cx-Hiwij'i'iji=1j=1i=1j=15655

约束条件： ⒈ 生产能力约束

axi155iijrjj1,2,,6

axi1'iijrj'j1,2,,6

⒉ 销售量不超过最大需要量约束

yijdiji1,2,,5j1,2,,6

3． 库存量约束

'wijwi,j1xijxijyiji1,2,,5j1,2,,6

⒋ 非负约束

'xij0,xij0,yij0i1,2,,5j1,2,,5

j1,2,,6

wij0i1,2,,5 25

例：P42例13。题略。

设xij为第i年初投资于项目j的资金额（万元），

j=A: i=1,2,3,4（次年末回收，本利和为投资额的115％）

j=B: i=3(第五年末回收，本利和为投资额的125％，投资限额4万元) j=C: i=2(第五年末回收，本利和为投资额的140％，投资限额3万元) j=D: i=1，2，3，4，5(年末回收，本利和为投资额的106％

期初资金10万元。

1.15x4A+1.25x3B+1.40x2C+1.06x5D 10 1.06x1D 1.15x1A+1.06x2D 1.15x3A+1.06x4D 1.15x2A+1.06x3D 0 1 2 3 4 5 x1A+x1D x2A+ x2C+x2D x+ x3B+x3D x3A3A+ x3B+x3D x4A+x4D x5D

目标函数：

maxz1.15x4A+1.25x3B+1.40x2C+1.06x5D 约束条件：

x1Ax1D10x2Ax2Cx2D1.06x1Dx3Ax3Bx3D1.15x1A1.06x2Dx4Ax4D1.15x2A1.06x3Dx5D1.15x3A1.06x4Dx3B4x2C3xij0jA,i1,2,3,4;jB,i3;jC,i2;jD,i1,2,3,4,5

26