1) 0-1 programming
0-1规划
1.
Parallel 0-1 programming algorithm based on improved PSRS;
基于改进PSRS的并行0-1规划算法
2.
The 0-1 Programming Model of Two Graph Theory Problems;
两个图论问题的0-1规划模型
3.
Optimization of ammunition-type decision and firing time sequence based on 0-1 programming
基于0-1规划的弹种决策与发射时序优化
2) zero-one programming
0-1规划
1.
The practical application of the two-dimension zero-one programming is extensive,but it subjects to the constraints such as traditional algorithm or the improvement on the basis of other methods.
具有特殊约束的二维0-1规划的实际应用广泛,在解法中多是应用传统算法,或是在它基础上进行改进,但是此类解法计算繁琐不易推广。
2.
A new implicit enumerate method for polynomial zero-one programming is proposed in this paper.
本文提出了一个求解多项式0-1规划问题的隐枚举算法。
3) 0-1 program
0-1规划
1.
At first,make use of"Causy distribute function" to carry the DVD fancy in the report on quantity,then establish 0-1 program,and finally solve it with Lingo.
将每个会员填报定单中DVD的喜爱度利用“柯西隶属分布函数”来进行量化后,建立0-1规划模型,利用Lingo求解。
2.
Then the localization problem is transformed into a problem of 0-1 program,and lagrangian relaxation and subgradient method are adopted to solve this 0-1 program problem.
该方法通过在现有二分图故障传播模型中加入虚假故障因素,提出改进的二分图故障传播模型,在该模型基础上,将故障定位问题转化为一个0-1规划的最小化问题,然后利用拉格朗日松弛和次梯度方法对问题进行求解。
4) 0-1 Planning
0-1规划
1.
This paper does researches on the issue how to rationally arrange classes in physical fitting test,and constructs a model of dynamic optimization,using the methods of black box thinking,dynamic planning and 0-1 planning.
运用"黑箱思想"、"动态规划"和"0-1规划"的方法建立了一个动态优化模型。
5) Binary (0/1) programming
0/1规划
6) Zero and one programming
0~1规划
补充资料:0-1规划
决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时,若决策变量采用 0-1变量即逻辑变量,可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。
应用范围 0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。
互斥计划问题 如确定投资项目,选定投资场所,决定投产产品等。设有几种产品,各产品投产后获得的利润为cj,投资限额为B,规定决策变量xj的取值为
则此0-1规划的数学模型为
式中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+yiM
y1+y2+...+ym=m-1因为m个yi中只有一个能取0值,所以只有一个约束条件能起作用。
如运送两种货物,其数量分别为 x1和x2,车运时货物体积不得超过b1,船运时货物重量不得超过b2,即
a11x1+a12x2≤b1 (车运),
a21x1+a22x2≤b2 (船运)。若只能采用一种运送方式,这两个约束条件是互相排斥的。为了统一在一个问题中,引用0-1变量yi,设
把上述约束条件改造成为下面一组约束条件:
a11x1+a12x2≤b1+y1M
a21x1+a22x2≤b2+y2M
y1+y2=2-1式中M是足够大的数,采用车运时y1=0,由第1式即得到车运约束条件,采用船运时y2=0,由第2式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。
固定费用问题 采用一般线性规划不能解决固定费用问题,需要用0-1规划。设有n种生产方式可供选择,xi为采用第i种方式时的产量,ci为采用第i种方式时每件产品的变动成本,ki为采用第 i种方式时的固定成本,采用各种生产方式的总成本分别为
(i=1,2,...,n)在构成目标函数时,为了统一在一个问题中讨论,引入0-1变量yi,即
则此0-1规划的数学模型为
式中min表示求极小值,M是充分大的常数。
分派问题 由几个人去完成几项任务,但由于任务性质和各人专长不同,应分派哪个人去完成哪项任务,以使总效率最高或耗费的总时间最小,这类问题称为分派问题,又称指派问题。
分派问题必须给出系数矩阵(又称效率矩阵),矩阵的元素 cij(>0)(i,j=1,2,...,n)表示派第i人去完成第j项任务时的效率(或时间、成本等)。引用0-1变量xij,设
分派问题的数学模型为
第1个约束条件说明第j项任务只能由1人去完成,第2个约束条件说明第i人只能完成1项任务。分派问题的解可写成矩阵形式(xij),其各行各列的元素之和都是1。
隐枚举法 0-1规划问题一般有三种解法,即变换法、穷举法和隐枚举法。上述方法即为变换法,用于解特殊的0-1规划问题。穷举法就是检查变量取值为0或 1的每一种组合,比较目标函数值来求最优解,这就需要检查变量取值的2n个组合。对于n>10的情况,这几乎是办不到的。因此常设计一些方法,只检查变量取值组合的一部分,就能得到问题的最优解。这样的方法称为隐枚举法。
采用隐枚举法解 0-1规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件,称为过滤条件,以减少运算次数。一般还要按目标函数中xi的系数递增的顺序,重新排列目标函数和约束条件中xi的次序,以简化计算。
参考书目
S.P.勃雷达兰等著,翟立林等译:《应用数学规划》,机械工业出版社,北京,1983。(Stephen P.Bradley,Arnoldo C.Hax,Thomas L.Magnanti, Applied Mathematical Programming, Addison-Wesley Publ.Co.,1977.)
应用范围 0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。
互斥计划问题 如确定投资项目,选定投资场所,决定投产产品等。设有几种产品,各产品投产后获得的利润为cj,投资限额为B,规定决策变量xj的取值为
则此0-1规划的数学模型为
式中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+yiM
y1+y2+...+ym=m-1因为m个yi中只有一个能取0值,所以只有一个约束条件能起作用。
如运送两种货物,其数量分别为 x1和x2,车运时货物体积不得超过b1,船运时货物重量不得超过b2,即
a11x1+a12x2≤b1 (车运),
a21x1+a22x2≤b2 (船运)。若只能采用一种运送方式,这两个约束条件是互相排斥的。为了统一在一个问题中,引用0-1变量yi,设
把上述约束条件改造成为下面一组约束条件:
a11x1+a12x2≤b1+y1M
a21x1+a22x2≤b2+y2M
y1+y2=2-1式中M是足够大的数,采用车运时y1=0,由第1式即得到车运约束条件,采用船运时y2=0,由第2式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。
固定费用问题 采用一般线性规划不能解决固定费用问题,需要用0-1规划。设有n种生产方式可供选择,xi为采用第i种方式时的产量,ci为采用第i种方式时每件产品的变动成本,ki为采用第 i种方式时的固定成本,采用各种生产方式的总成本分别为
(i=1,2,...,n)在构成目标函数时,为了统一在一个问题中讨论,引入0-1变量yi,即
则此0-1规划的数学模型为
式中min表示求极小值,M是充分大的常数。
分派问题 由几个人去完成几项任务,但由于任务性质和各人专长不同,应分派哪个人去完成哪项任务,以使总效率最高或耗费的总时间最小,这类问题称为分派问题,又称指派问题。
分派问题必须给出系数矩阵(又称效率矩阵),矩阵的元素 cij(>0)(i,j=1,2,...,n)表示派第i人去完成第j项任务时的效率(或时间、成本等)。引用0-1变量xij,设
分派问题的数学模型为
第1个约束条件说明第j项任务只能由1人去完成,第2个约束条件说明第i人只能完成1项任务。分派问题的解可写成矩阵形式(xij),其各行各列的元素之和都是1。
隐枚举法 0-1规划问题一般有三种解法,即变换法、穷举法和隐枚举法。上述方法即为变换法,用于解特殊的0-1规划问题。穷举法就是检查变量取值为0或 1的每一种组合,比较目标函数值来求最优解,这就需要检查变量取值的2n个组合。对于n>10的情况,这几乎是办不到的。因此常设计一些方法,只检查变量取值组合的一部分,就能得到问题的最优解。这样的方法称为隐枚举法。
采用隐枚举法解 0-1规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件,称为过滤条件,以减少运算次数。一般还要按目标函数中xi的系数递增的顺序,重新排列目标函数和约束条件中xi的次序,以简化计算。
参考书目
S.P.勃雷达兰等著,翟立林等译:《应用数学规划》,机械工业出版社,北京,1983。(Stephen P.Bradley,Arnoldo C.Hax,Thomas L.Magnanti, Applied Mathematical Programming, Addison-Wesley Publ.Co.,1977.)
说明:补充资料仅用于学习参考,请勿用于其它任何用途。
参考词条