0-1规划
0-1 Programming
0-1规划
百科内容来自于：
简介
应用范围
0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。
互斥计划问题
如确定投资项目，选定投资场所，决定投产产品等。设有几种产品，各产品投产后获得的利润为c
j，投资限额为
B，规定决策变量xj的取值为
则此0-1规划的数学模型为
式中max表示求极大值；s.t.表示“受约束于”；
z是目标函数；
aj 是各种产品的投资额。
约束条件互斥问题
设有
m个互相排斥的约束条件（≤型）
ai1
x1+
ai2
x2+…+
ainxn≤
bi (
i=1，2，…，
m)为了保证这
m个约束条件中只有一个起作用,引入
m个0-1变量yi和一个足够大的常数
M，构造
m+1个约束条件
ai1
x1+
ai2
x2+…+
ainxn≤
bi+
yiM
y1+
y2+…+
ym=
m－1
因为
m个
yi中只有一个能取0值，所以只有一个约束条件能起作用。
如运送两种货物，其数量分别为
x1和
x2，车运时货物体积不得超过
b1，船运时货物重量不得超过
b2，即
a11
x1+
a12
x2≤
b1 （车运），
a21
x1+
a22
x2≤
b2 （船运）。
若只能采用一种运送方式，这两个约束条件是互相排斥的。为了统一在一个问题中，引用0-1变量yi，设
把上述约束条件改造成为下面一组约束条件：
a11
x1+
a12
x2≤
b1+
y1
M
a21
x1+
a22
x2≤
b2+
y2M
y1+
y2=2-1
式中
M是足够大的数，采用车运时
y1=0，由第1式即得到车运约束条件，采用船运时
y2=0，由第2式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。
固定费用问题
采用一般线性规划不能解决固定费用问题，需要用0-1规划。设有
n种生产方式可供选择，
xi为采用第
i种方式时的产量,c
i为采用第
i种方式时每件产品的变动成本，
ki为采用第
i种方式时的固定成本，采用各种生产方式的总成本分别为
(
i=1,2,…,
n)
在构成目标函数时，为了统一在一个问题中讨论，引入0-1变量yi，即
则此0-1规划的数学模型为
式中min表示求极小值，
M是充分大的常数。
分派问题
由几个人去完成几项任务，但由于任务性质和各人专长不同，应分派哪个人去完成哪项任务，以使总效率最高或耗费的总时间最小，这类问题称为分派问题，又称指派问题。
分派问题必须给出系数矩阵（又称效率矩阵），矩阵的元素 c
ij(>0)(
i，j=1，2，…，
n)表示派第
i人去完成第
j项任务时的效率（或时间、成本等）。引用0-1变量xij，设
分派问题的数学模型为
第1个约束条件说明第
j项任务只能由1人去完成，第2个约束条件说明第
i人只能完成1项任务。分派问题的解可写成矩阵形式(
xij)，其各行各列的元素之和都是1。
隐枚举法
$firstVoiceSent
- 来自原声例句