方式（1 ）的工时约束为
0.3X1 + 0.5X2 ≤ 15
0
方式（2 ）的工时约束为
0.2X1 + 0.4X2 ≤ 12
0
引入 0-问1题变是量完成工序 B 只能从两种方式中任选一种，如
何将这两个互斥0 的约若束工条序件B统采一用在方一式个（线1 ）性完规成划模型中呢？
y1 = 1
若工序 B 不采用方式（1 ）完成
)中加入新的约束
x j xi (i j)
6）如果对第r种资源与第t种资源的投资的是相互排斥的，即只能对
资源br与bt中的一种进行投资，则可将(2)的第r个和第t个约束条件改写
为
n
arj x j br yM
j1
n
atj x j bt (1 y)M
j1
其中y为新引入的0—1变量，M为充分大的正数。 7）若在m个约束中只有k个起作用，则（2）改为
k
xj 1
j1
2）如果可供选择的k(k≤n)个项目相互排斥的，则在(2)中加入新的
约束条件
k
xj 1
j1
3）如果可供选择的k(k≤n)个项目中，至少应选择一项投资，则在(
2)中加入新的约束条件 k
xj 1
j1
4）如果项目j的投资必须以项目i的投资为前提，则可在(2)中加入新
的约束
x j xi
5）如果项目i与项目j要么同时被选中，要么同时不被选中，则在(2
x j My j
(6)
所以线性规划模型为
min z
n
(c j x j
j1
Kjyj)
s.t.
0 x j My j y j 0或1
(7)
由(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个
x6 x7 2 y1M x6 1 y2M 4 x7 5 y3M x6 x7 3 y4M y1 y2 y3 y4 2 yi 0或1(i 1, 2,3, 4)
例2 将以下问题表示为混合整数规划模型 问题 min z f1 x1 f2 x2 , 满足约束 1 x1 10,或x2 10.
2020/12/19
n
aij x j
j1
y1 y2
bi Myi ym m k
其中yi为0—1变量，M为充分大的正数。
8）约束条件的右端项可能是r个值（b1,b2, …br）中的某一个，即
n
aij xj b1或b2 , ,或br
j1
定义yi
1, 假定约束右端项为bi 0,否则
则，（2）表示为：
n
aij x j
i1
y1 y2
X6 X7 2
X6 1
X7 5
X 2020/12/19 6
X7
3
解：
x1 x2 2 1 y M
(1) 2x1 3x2 8 yM
y 0或1，M为充分大的正数
2020/12/19
(2)x3 0 y1 5 y2 9 y3 12 y4 y1 y2 y3 y4 1 yi 0或1 i 1, 2,3, 4
x2 4 yM x5 yM 3 x2 4 (1 y)M x5 3 (1 y)M y 0或1
0 y2 = 1
若工序 B 采用方式（2 ）完成 若工序 B 不采用方式（2 ）完成
于是前面两个互斥的约束条件可以统一为如下三个约束条件：
0.3X1 + 0.5X2 ≤ 150 + M1y1 0.2X1 + 0.4X2 ≤ 120 + M2y2
y1 + y2 = 1
其中 M1 ，M2 都是足够大的正数。
0 x1 y1M; x2 y2M
2020/12/19
1 x1 10 y3M x2 10 1 y3 M
2x1 x2 15 y4M 2 x1 x2 15 y5M
x1 2x2 15 y6M y4 y5 y6 2
xi 0, y j
0或1
例3 应用 0-1 变量解决含互斥约束条件问题
设：工序 B 有两种方式完成
Cj (xj )
K j c j x j (x j 0)
0
(xj 0)
(4)
其中Kj是同产量无关的生产准备费用。问题的目标是使所有产品 的总生产费用为最小.即
n
min z
Cj (xj )
(5)
j1
同样,定义yj为0—1变量，当xj=0时,yj=0;当xj>0,yj=1. 因此,引进一个特殊的约束条件:
第5讲:生产与服务管理中的 优化问题(一)
➢ 0-1规划问题补充 ➢生产与销售计划问题 ➢有瓶颈设备的多级生产计划问题 ➢ 疏散问题
2020/12/19
一 0-1整数规划问题补充
0-1变量作为逻辑变量（Logical variable），常常被用来处 理“选择问题”。
如：假定现有的m种资源对可供选择的n个项目进行投资,每 个项目可获取的利润为cj元，则求利润最大的数学模型为求一组决 策变量x1,x2, …,xn,使
r
bi yi
i1
yr 1
9）两组条件中满足其中一组
若x1≤4，则x2≥1；否则（即x1>4时）,x2≤3. 定义yi为0—1变量，M为充分大的正数,则问题可表述为
x1 4 yΒιβλιοθήκη Mx2 1 y1Mx1 4 y2M
x2 3 y2M
y1 y2 1
10）可以用以表示含固定费用的函数
如若用xj代表产品j的生产数量,其生产费用函数通常可表为:
2 下列各不等式至少有一个成立： 2x1 x2 15 x1 x2 15 x1 2x2 15
3 x1 0, x2 0 其中
2020/12/19
f1 x1 f2 x2
20 5x1 x1 0
0
x1 0
12 6x2 x2 0
0
x2 0
解 目标函数为：
min z 20 y1 5x1 12 y2 6x2
约束条件：
二 生产与销售计划问题
例4 某公司用两种原油（A和B）混合加工成两种汽 油（甲和乙）。甲、乙两种汽油含原油A的最低比 例分别为50%和60%，每吨售价分别为4800元和560 0元。该公司现有原油A和B的库存量分别为500吨 和1000吨，还可以从市场上买到不超过1500吨的 原油A。原油A的市场价为：购买量不超过500吨时 的单价为10000元/吨；购买量超过500吨但不超过 1000吨时，超过500吨的部分8000元/吨；购买量 超过1000吨时，超过1000吨的部分6000元/吨。该
n
max Z
cjxj
(1)
j1
n
s.t.
aij x j bi (i 1, 2, , m) (2)
j1
x j 0或1
(j=1,2, ,n) (3)
其中，cj表示投资第j项目获得的期望收益（价值系数），aij表示
第i种资源投于第j项目的数量，bi表示第i种资源的限量。
1）如果在可供选择的k(k≤n)个项目中，必须且只需选择一项，则在 (2)中加入新的约束条件