0-1规划

137368108

0-1规划
1 r: |0 _1 u* c* z+ [8 |0-1规划是决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时，若决策变量采用 0-1变量即逻辑变量，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。
　　0-1规划
0-1 Programming
一种特殊形式的整数规划 。这种规划的决策变量仅取值0或1，故称为0-1变量或二进制变量 ，因为一个非负整数都可以用二进制记数法用若干个0-1变量表示 。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件 ，因此0-1规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。实际上，凡是有界变量的整数规划都可以转化为0-1规划来处理 。由于0-1规划具有深刻的背景和广泛的应用，几十年来一直受到人们的重视。
求解0-1规划的方法主要是隐枚举法（如分枝定界法）。对一些特殊问题还有一些更加有效的方法，例如对指派问题，用D.柯尼希发明的匈牙利法求解更显方便有效。
应用范围
/ g4 p/ ^5 B: ~% D0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。
" L( p/ T, w9 ]4 l6 U互斥计划问题
如确定投资项目，选定投资场所，决定投产产品等。设有几种产品，各产品投产后获得的利润为 ，投资限额为 ，规定决策变量 的取值为
$ E" K' L) J9 k8 I; @
) V, X: e: h% E7 D: F" y. t则此0-1规划的数学模型为

( K, H9 V1 T9 e( S. J. m/ w& _- f式中 表示求极大值； 表示“受约束于”； 是目标函数； 是各种产品的投资额。
约束条件互斥问题
& w% G, {% x% R' Z5 D设有 个互相排斥的约束条件（≤型） 　(i＝1，2，…，m)为了保证这m个约束条件中只有一个起作用,引入m个0-1变量yi和一个足够大的常数M，构造m＋1个约束条件
2 Z+ \- k6 E! @; lai1x1＋ai2x2＋…＋ainxn≤bi＋yiM
" \- @; s3 w) y+ @. Ky1＋y2＋…＋ym＝m－1
. {3 a6 K; G7 y- a+ F. k因为m个yi中只有一个能取0值，所以只有一个约束条件能起作用。
如运送两种货物，其数量分别为 x1和x2，车运时货物体积不得超过b1，船运时货物重量不得超过b2，即
7 v/ E' }5 o3 n5 g3 l: \+ Qa11x1＋a12x2≤b1 （车运），
a21x1＋a22x2≤b2 （船运）。
若只能采用一种运送方式，这两个约束条件是互相排斥的。为了统一在一个问题中，引用0-1变量yi，设
  w9 v# j; ]& x1 Z6 K   
( p: E- u% I- f, n7 F   
把上述约束条件改造成为下面一组约束条件：
1 C( M* X5 c, C0 Ca11x1＋a12x2≤b1＋y1M
1 i6 y- X  X3 x8 `9 Z" `0 p# ba21x1＋a22x2≤b2＋y2M
3 b  A  A) X. Qy1＋y2＝2-1
& _. E- m$ A1 g, b% D式中M是足够大的数，采用车运时y1＝0，由第1式即得到车运约束条件，采用船运时y2＝0，由第2式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。
( v! C" u$ Y: N9 t9 J固定费用问题
采用一般线性规划不能解决固定费用问题，需要用0-1规划。设有n种生产方式可供选择，xi为采用第i种方式时的产量,ci为采用第i种方式时每件产品的变动成本，ki为采用第 i种方式时的固定成本，采用各种生产方式的总成本分别为
   
(i＝1,2,…,n)
3 {$ j7 ?. g% V, t( z在构成目标函数时，为了统一在一个问题中讨论，引入0-1变量yi，即
6 \" g! c2 c* A则此0-1规划的数学模型为
   
) {  T0 I% u2 ?* Q% @/ o- o: ^   
式中min表示求极小值，M是充分大的常数。
分派问题
由几个人去完成几项任务，但由于任务性质和各人专长不同，应分派哪个人去完成哪项任务，以使总效率最高或耗费的总时间最小，这类问题称为分派问题，又称指派问题。
! v0 I6 [" b. W: a- {* S分派问题必须给出系数矩阵（又称效率矩阵），矩阵的元素 cij(>0)(i，j＝1，2，…，n)表示派第i人去完成第j项任务时的效率（或时间、成本等）。引用0-1变量xij，设
   
分派问题的数学模型为
/ L2 ?! {: T$ ~  k( S- e  W4 y   
9 s. \5 v. |$ N. }2 F   
5 Q, }, }% Y  C( V: t: t; S, @第1个约束条件说明第j项任务只能由1人去完成，第2个约束条件说明第i人只能完成1项任务。分派问题的解可写成矩阵形式(xij)，其各行各列的元素之和都是1。
4 i- A5 T/ R4 F6 Y5 w" o0 M9 b隐枚举法
$ U+ Q2 `+ j  t* X6 N: w; ]- G* j0-1规划问题一般有三种解法,即变换法、穷举法和隐枚举法。上述方法即为变换法，用于解特殊的0-1规划问题。穷举法就是检查变量取值为0或 1的每一种组合，比较目标函数值来求最优解，这就需要检查变量取值的2n个组合。对于n>10的情况，这几乎是办不到的。因此常设计一些方法，只检查变量取值组合的一部分，就能得到问题的最优解。这样的方法称为隐枚举法。
采用隐枚举法解 0-1规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件，称为过滤条件，以减少运算次数。一般还要按目标函数中xi的系数递增的顺序，重新排列目标函数和约束条件中xi的次序，以简化计算。
4 W/ C" A; l0 I5 c4 E& H* y# c# H

china19901015

hehe~~