下载文档原格式
0-1规划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.柯尼希发明的匈牙利法求解更显方便有效。
应用范围0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。
互斥计划问题如确定投资项目，选定投资场所，决定投产产品等。
设有几种产品，各产品投产后获得的利润为c j，投资限额为B，规定决策变量xj的取值为1则此0-1规划的数学模型为23式中max表示求极大值；s.t.表示“受约束于”；z是目标函数；aj是各种产品的投资额。
约束条件互斥问题设有m个互相排斥的约束条件（≤型）ai1x1＋ai2x2＋…＋ainxn≤bi(i＝1，2，…，m)为了保证这m个约束条件中只有一个起作用,引入m个0-1变量y i和一个足够大的常数M，构造m＋1个约束条件ai1x1＋ai2x2＋…＋ainxn≤bi＋yiMy1＋y2＋…＋ym＝m－1因为m个yi中只有一个能取0值，所以只有一个约束条件能起作用。
0 前言化问题，可知最优解的目标函数一定不小于 5。
为此，在求最优解之前先增加一个约束条件，即过滤0- 1 型整数规划是整数规划的特例，其数学模型的目 条件：3x - 2x +5x !5##⊙ 标函数、约束条件与线性规划相同，不同的是其变量只能1 2 3 过滤条件的作用是：在检验一个解是否为可行解之取 0 和 1，分别表示两种截然相反的结果。
0- 1 型整数规前，先看目标函数是否不小于 5，若小于 5，则肯定不是最 划应用很广，如土木工程系统的最优工程配置问题，城建优解，其可行性无须再检验而直接被淘汰，可以大大减少规划中的居民点、给水点、加油站和商业网点的最优布局计算工作量。
问题，均可应用 0- 1 型整数规划求得最优解。
有了过滤条件，就可以列表计算。
对解集中的解逐个检0- 1 型整数规划的数学模型如下：验，先检验过滤条件，若不符合则直接淘汰该解;若符合条 目标函数：件⊙，再按①~④顺序检验每一个约束条件，当某一个约 束条件不满足时即行淘汰，其右边的约束条件再无检验 约束条件：的必要。
这样，计算工作量可大为减少。
本例中有 3 个变量，共有 23=8 个解需要检验，通过计 算求得的最优解为: .本例以 为初始可行解，通过建立过滤条1 求解 0- 1 型整数规划三种通用的方法 件，只计算了 18 次就找到了最优解，而用穷举法需要计算1.1 穷举法40 次，技术工作量大大减少了。
如在求解过程发现更好的 由于 0- 1 型整数规划的变量个数有限且取值非 0 即可行解及时更换过滤条件 ，计算工作量还可进一步减少。
1，所以不难将解的集合找出来，再检验每个解的可行性， 1.2.2 对隐枚法法 I 的评价 凡符合全部约束条件者均为可行解，通过比较目标函数 对隐枚举法 I 来说其数学模型无须转化为标准型,减的值便可找到最优解，这个解法称为穷举法。
当变量和约 少了人工处理的工作量，但它需要检验的方案较多,而且 束条件很多时，其工作量是非常大的。
0—1型整数规划模型1. 0—1型整数规划模型概述整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。
在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。
0—1型整数规划的的数学模型为：目标函数 n n x c x c x c z Min Max +++= 2211)(约束条件为：⎪⎪⎩⎪⎪⎨⎧==≥≤++=≥≤++=≥≤++1| 0 ) ,() ,() ,(22112222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21这里，0 | 1表示0或1。
2. 0—1型整数规划模型的解法0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量nx x x , , ,21 的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。
这种方法一般适用于决策变量个数n 较小的情况，当n 较大时，由于n 个0、1的可能组合数为n2，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。
隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。
此时，就只能用穷举法了。
3. 应用实例例1 工程上马的决策问题1）问题的提出某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。
2）模型分析与变量的假设这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用0—1型整数规划模型建立其相应的模型。
0-1型整数线性规划模型理论
(1) 0-1型整数线性规划
0-1型整数线性规划是一类特殊的整数规划,它的变量仅取值0或1.其模型如下:
T min ..01(1,2,
,)j f s t x j n =⎧⎨=⎩c x
Ax =b 取或 其中()T 12,,,,n c c c =c ()T 12,,,,n x x x =x (),ij m n
a ⨯=A ()T 12,,,.m
b b b =b 称此时的决策变量为0-1变量,或称二进制变量.在实际问题中,如果引进0-1变量,就可以把各种需要分别讨论的线性(或非线性)规划问题统一在一个问题中讨论了.
(2) 求解0-1型整数线性规划的分支界定法Matlab 指令
x = bintprog(f,A,b): 求解0-1型整数线性规划,用法类似于linprog.
x = bintprog(f,A,b,Aeq,beq): 求解下述线性规划问题:
T min ,z =f x ≤Ax b ,≤Ax b ,⋅≤Aeq x beq ,x 分量取0或1.
x = bintprog(f,A,b,Aeq,beq,x0): 指迭代初值x0,如果没有不等式约束,可用[]代替A,b 表示默认,如果没有等式约束,可用[]代替Aeq 和beq 表示默认;用[x,fval]代替上述各命令行中左边的x,则可得到最优解处的函数值fval.
例如：求解0-1型整数线性规划模型:
1min n
i i Z x ==∑
()()()
123453568946791234712567
5812923
2200..20
0020
01(1,2,,9)j x x x x x x x x x x x x x x x x x x x s t x x x x x x x x x x x j ⎧-++++≤-⎪-++++≤-⎪⎪-+++≤-⎪⎪--+≤⎪-≤⎪⎨--+≤⎪⎪-≤⎪-+≤⎪⎪--+≤⎪⎪==⎩
或
用Matlab 软件编程可解得1236791x x x x x x ======,其他变量为0,共六门课,满足
所给条件, Matlab程序代码如下：
c = ones(1,9);
a =
[-1,-1,-1,-1,-1,0,0,0,0;0,0,-1,0,-1,-1,0,-1,-1;0,0,0,-1,0,-1,-1,0,-1;-1,-1,2,0,0,0,0,0,0;0,0,0,1,0,0,-1,0, 0;
-1,-1,0,0,2,0,0,0,0;0,0,0,0,0,1,-1,0,0;0,0,0,0,-1,0,0,1,0;-1,-1,0,0,0,0,0,0,2];
b = [-2;-3;-2;0;0;0;0;0;0];
A = [5 4 4 3 4 3 2 2 3];
x = bintprog(c,a,b)
f = A*x
运行结果：
Optimization terminated.
x =
1
1
1
1
1
1
f =
20。
