0-1规划是决策变量仅取值0或1的一类特殊的整数规划。这种规划的决策变量仅取值 0或1 ,故称为 0-1 变量或二进制变量 ,因为一个非负整数都可以用二进制计数法用若干个 0-1 变量表示 。 0-1 变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件,因此 0-1 规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。

目录

应用:

1、互斥计划问题

2、约束条件问题

3、固定费用问题(成本)

4、分派问题

参考文献


应用:

1、互斥计划问题

如确定投资项目,选定投资场所,决定投产产品等。设有几种产品,各产品投产后获得的利润为cj,投资限额为B,规定决策变量xj的取值为:

                                                                 

则此0-1规划的数学模型为:
                                                                         图2
                                                                          图3

式中max表示求极大值;s.t.表示“受约束于”;z是目标函数;aj 是各种产品的投资额。

2、约束条件问题

设有 m个互相排斥的约束条件(≤型)ai1x1+ai2x2+…+ainxnbi(i=1,2,…,m),为了保证这m个约束条件中只有一个起作用,引入m个 0-1 变量yi 和一个足够大的常数M,构造m+1 个约束条件

ai1x1+ai2x2+…+ainxnbi+yiM

y1+y2+…+ym=m-1

因为myi中只有一个能取 0 值,所以只有一个约束条件能起作用。如运送两种货物,其数量分别为 x1 和x2,车运时货物体积不得超过b1 ,船运时货物重量不得超过b2 ,即

a11x1+a12x2≤b1 (车运),

a21x1+a22x2≤b2(船运)。

若只能采用一种运送方式,这两个约束条件是互相排斥的。为了统一在一个问题中,引用 0-1 变量yi,设

图4                              图5

把上述约束条件改造成为下面一组约束条件:

a11x1+a12x2≤b1+y1M

a21x1+a22x2≤b2+y2M

y1+y2=2-1

式中M是足够大的数,采用车运时y1=0 ,由第 1 式即得到车运约束条件,采用船运时y2=0 ,由第 2 式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。

3、固定费用问题(成本)

采用一般线性规划不能解决固定费用问题,需要用 0-1 规划。设有n种生产方式可供选择,xi为采用第i种方式时的产量, ci为采用第i种方式时每件产品的变动成本,ki为采用第 i种方式时的固定成本,采用各种生产方式的总成本分别为(i=1,2,…,n)
                                                         

在构成目标函数时,为了统一在一个问题中讨论,引入 0-1 变量yi,令:
                                                          

这里假设的是三种资源生产三种产品,于是目标函数为:
                                                                 min\: z=(k_{1}y_{1}+c_{1}x_{1})+(k_{2}y_{2}+c_{2}x_{2})+(k_{3}y_{3}+c_{3}x_{3})

式(1)可由以下三个线性约束条件表示:
                                                                  x_{i}\leq y_{i}M\:\:\:j=1,2,3    ................(2)

式(2)中,M为一个充分大的常数,式(2)也说明了,当xi>0时,yi必须为1;当xi=0时,只有yi=0才有意义,所以式(2)可以替代(1)

西南交通大学的运筹学A类科技对于“固定费用问题”假设三种资源三种产品所构建的规划模型数据:

4、分派问题

由几个人去完成几项任务,但由于任务性质和各人专长不同,应分派哪个人去完成哪项任务,以使总效率最高或耗费的总时间最小,这类问题称为分派问题,又称指派问题。

分派问题必须给出系数矩阵(又称效率矩阵),矩阵的元素 cij(>0)(i,j=1,2,…,n) 表示派第i去完成第j项任务时的效率(或时间、成本等)。引用 0-1 变量xij,设

成本(目标函数):MinT=\sum a_{ij}x_{ij}     ;其中a_{ij}为特长系数(所需时间,逆权重)

约束条件:

每人只做一件工作:\sum_{j=1}^{n}x_{ij}=1\;\;\;i\in (1,2,3,\cdots ,n)

每件工作只能由一人担任:\sum_{i=1}^{n}x_{ij}=1\;\;\;j\in (1,2,3,\cdots ,n)

参考文献

[1]陈修素, 陈睿. 关于固定费用的问题(FixedcostProblem)的整数规划模型的注记[J]. 重庆工商大学学报(自然科学版), 2017(06):59-61.

[2]摘自百度百科0-1规划:https://baike.baidu.com/item/0-1%E8%A7%84%E5%88%92/5790449?fr=aladdin

 

 

 

 

 

 

 

 

 

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐