基于Lingo的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 ,故称为 0-1 变量或二进制变量 ,因为一个非负整数都可以用二进制计数法用若干个 0-1 变量表示 。 0-1 变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件,因此 0-1 规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。
目录
应用:
1、互斥计划问题
如确定投资项目,选定投资场所,决定投产产品等。设有几种产品,各产品投产后获得的利润为cj,投资限额为B,规定决策变量xj的取值为:
则此0-1规划的数学模型为:
式中max表示求极大值;s.t.表示“受约束于”;z是目标函数;aj 是各种产品的投资额。
2、约束条件问题
设有 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 式即得到船运约束条件。因此上述互相排斥的约束条件被一组联立约束条件所代替。
3、固定费用问题(成本)
采用一般线性规划不能解决固定费用问题,需要用 0-1 规划。设有n种生产方式可供选择,xi为采用第i种方式时的产量, ci为采用第i种方式时每件产品的变动成本,ki为采用第 i种方式时的固定成本,采用各种生产方式的总成本分别为(i=1,2,…,n)
在构成目标函数时,为了统一在一个问题中讨论,引入 0-1 变量yi,令:
这里假设的是三种资源生产三种产品,于是目标函数为:
式(1)可由以下三个线性约束条件表示:
................(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,设
成本(目标函数): ;其中
为特长系数(所需时间,逆权重)
约束条件:
每人只做一件工作:
每件工作只能由一人担任:
参考文献
[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](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)