基于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
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
8
0- 0
已为社区贡献12条内容
所有评论(0)