关于猫的详细资料大全 0-1规划详细资料大全

0-1规划详细资料大全  

0-1规划是决策变数仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时，若决策变数采用 0-1变数即逻辑变数，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。

基本介绍

中文名：0-1规划外文名：zero-one programming实质：仅取值0或1的一类特殊的整数规划套用范围：求解互斥的计画问题等又称：二进制变数 简介,套用,互斥计画问题,约束条件问题,固定费用问题,分派问题,求解方法,零一整数规划,

简介

0-1 规划是一种特殊形式的整数规划 。这种规划的决策变数仅取值 0或1 ，故称为 0-1 变数或二进制变数 ，因为一个非负整数都可以用二进制记数法用若干个 0-1 变数表示 。 0-1 变数可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变数间的逻辑关系、顺序关系以及互斥的约束条件，因此 0-1 规划非常适合描述和解决如线路设计 、工厂选址 、生产计画安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。 实际上，凡是有界变数的整数规划都可以转化为 0-1 规划来处理 。由于 0-1 规划具有深刻的背景和广泛的套用，几十年来一直受到人们的重视 。0-1 规划主要用于求解互斥的计画问题、约束条件互斥问题、固定费用问题和分派问题等方面。

套用

互斥计画问题

如确定投资项目，选定投资场所，决定投产产品等。设有几种产品，各产品投产后获得的利润为c j，投资限额为 B，规定决策变数 xj的取值为 图1则此0-1规划的数学模型为图2图3 式中max表示求极大值；s.t.表示“受约束于”； z是目标函式； aj 是各种产品的投资额。

约束条件问题

设有 m个互相排斥的约束条件（≤型） ai1x1+ ai2x2+…+ ainxn≤ bi( i=1，2，…， m)，为了保证这 m个约束条件中只有一个起作用，引入 m个 0-1 变数 yi 和一个足够大的常数 M，构造 m+1 个约束条件 ai1x1+ ai2x2+…+ ainxn≤ bi+ yiMy1+ y2+…+ ym= m-1 因为 m个 yi中只有一个能取 0 值，所以只有一个约束条件能起作用。如运送两种货物，其数量分别为 x1 和 x2，车运时货物体积不得超过 b1 ，船运时货物重量不得超过 b2 ，即 a11x1+ a12x2≤ b1 （车运）， a21x1+ a22x2≤ b2（船运）。 若只能采用一种运送方式，这两个约束条件是互相排斥的。为了统一在一个问题中，引用 0-1 变数 yi，设 图4图5 把上述约束条件改造成为下面一组约束条件： a11x1+ a12x2≤ b1+ y1Ma21x1+ a22x2≤ 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) 图6 在构成目标函式时，为了统一在一个问题中讨论，引入 0-1 变数 yi，即则此0-1规划的数学模型为 图7图8 式中min表示求极小值， M是充分大的常数。

分派问题

由几个人去完成几项任务，但由于任务性质和各人专长不同，应分派哪个人去完成哪项任务，以使总效率最高或耗费的总时间最小，这类问题称为分派问题，又称指派问题。 分派问题必须给出系数矩阵（又称效率矩阵），矩阵的元素 c ij(>0)( i，j=1，2，…， n) 表示派第 i人去完成第 j项任务时的效率（或时间、成本等）。引用 0-1 变数 xij，设 图9分派问题的数学模型为图10图11 第 1 个约束条件说明第 j项任务只能由 1人去完成，第 2 个约束条件说明第 i人只能完成 1 项任务。分派问题的解可写成矩阵形式( xij)，其各行各列的元素之和都是1。

求解方法

求解 0-1 规划的方法主要是隐枚举法（如分枝定界法）。对一些特殊问题还有一些更加有效的方法，例如对指派问题，用D.柯尼希发明的匈牙利法求解更显方便有效。 0-1 规划问题一般有三种解法，即变换法、穷举法和隐枚举法。变换法用于解特殊的 0-1 规划问题。穷举法就是检查变数取值为 0 或 1 的每一种组合，比较目标函式值来求最优解，这就需要检查变数取值的 2 n个组合。对于 n>10 的情况，这几乎是办不到的。因此常设计一些方法，只检查变数取值组合的一部分，就能得到问题的最优解。这样的方法称为隐枚举法。 采用隐枚举法解 0-1 规划问题时要根据目标函式的性质增加一个相应的不等式作为附加约束条件，称为过滤条件，以减少运算次数。一般还要按目标函式中 x i 的系数递增的顺序，重新排列目标函式和约束条件中 x i 的次序，以简化计算。

零一整数规划

[zero-one integer programming] 0-1 整数规划是一类最简单的整数规划，即变数仅取 0 或 1， x 为（1,0）向量 背包问题是一个典型的零一整数规划。 零一整数规划可用分枝定界方法来解，方法可简单叙述如下。设 为 n 个 0-1 整数变数，记原问题为 ，它的松弛线性规划为 记其最优解值为 。第一步，解两个子问题 的松弛线性规划 ，若其最优解值为 ，且两个解均为整数解，则其中小的一个即为最优解；若其中有一个是整数解且对应最优值小于或等于另一子问题的最优值，则该整数解就是原问题的最优解。以上情形均不满足时，对最优值较小或小于已有整数解值、且解为非整数的子规划进行对第二个变数的分解。以下步骤的原理是相同的，具体的算法常采用不同的技巧。