整数0-1规划

例析0-1整数规划及隐枚举法的应用

自主招生近年来成为各大高校又一招纳人才的举措,面试在自主招生中扮演着越来越重要的角色,考生面试的成绩不容忽视。因此如何确定面试专家的分配方案,使录取工作真正公平合理的进行,是各大高校积极考虑的问题。本文通过采用0-1整数规划及隐枚举法建立相关模型,较好地解决了这一问题。

1 预备知识简介

1.1 线性规划[1]

在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—— 数学规划,而线性规划则是数学规划的一个重要分支。若在线性规划模型中,变量限制为整数,则为整数线性规划。0-1整数规划是整数规划中的特殊情形,它的变量仅取0或1。合理地引用0-1规划能够容易且高效率地求解相关问题。

1.2 隐枚举法[2]

隐枚举法是Balas E在1965年提出的,是求解0-1规划问题的一种有效方法。它只检查一部分变量组合,在这过程中根据已有信息自动舍弃许多不可能成为最优解的组合,求得最优解,从而大大减少了工作量。隐枚举法只需比较目标函数在小部分组合点上的取值大小,就能求得最优解和最优值。

2 问题描述与建模

2.1 问题描述

某高校采用通过专家面试的方式进行自主招生,经过初选合格进入面试的考生有N人,拟聘请老师M人进行面试。每位学生要分别接收“面试组”每位老师的单独面试,每个面试组由4名老师组成。已知要求面试不同考生的“面试组”成员不能完全相同。试求在考生数N已知的条件下,聘请老师数M至少应为多大,才能做到任两位学生的“面试组”都没有两位面试老师相同。

2.2 数学建模

该问题是一个单目标规划问题,解决的是满足一定约束条件要求,计算在给出一定的学生人数下,所需要教师的最少人数。 根据实际情况分析,一般面试学生的个数要远大于教师的个数。因为教师人数较少,容易进行分组(即按照约束条件将教师每4人分成一组),满足约束条件的情况下,所能组合的最大组数目即可面试学生的最大人数[3～4]。因此,我们改变优化变量,当教师数目M一定的情况下最多可面试的学生个数,即求max N。

第２８卷第３期　

２０１　０年５月　西安航空技术高等专科学校学报　

Ｊｏｕｒｎａｌ　ｏｆ　Ｘｉ’ａｎ　Ａｅｍｔ￣ｈｎｉｃａｌ　Ｃｏｌｌｅｇｅ　Ｖ＿ｏ１．２８Ｎｏ．３　

Ｍａｙ　２　０　１　０　

会议筹备的０—１整数规划＊　

李　华，王　振，王　凯，段智强　

（西安航空技术高等专科学校基础部，陕西西安７１００７７）　

摘要：在举行大型会议时，组委会需对宾馆预定、会议室安排，客车租用这三方面问题做出合理的安排，既要满足　

与会代表的要求，又要使租用会议室及租车费用尽可能少。针对此问题，建立了多目标规划模型，利用分层序列法，　

把目标按其重要性的序列：宾馆预定，会议室安排，客车租用依次求解，在前一目标最优解集内求下一个目标最优　

解，并利用ＬＩＮＧＯ软件求解。　

关键词：多目标规划；０—１整数规划；ＬＩＮＧＯ软件；行车路径　

中图分类号：０１４４．５文献标识码：Ａ文章编号：１００８—９２３３（２０１０）０３—００６１—０３　

１问题的提出　

某会议服务公司准备举行一次全国性会议，主　

要负责为与会代表预定宾馆客房、租借会议室、租借　

客车接送代表。由于会议规模庞大，而适于接待这　

次会议的几家宾馆的客房和会议室数量有限，所以　

只能安排代表分散地住在若干家宾馆中。为方便管　

理，尽可能地满足代表在价位等方面的要求，还要使　

所选择的宾馆数尽可能的少及距离上比较靠近。　

经过筹备组的实地观察，选出了１０家宾馆作为　

备选，宾馆名称用①至⑩表示。　

从以往几届会议来看，有一些代表事先发来回　

执但没有来开会，同时还有一些代表事先没有发来　

回执却来开会，客房费是由与会代表自己支付，如果　

预定客房数量大于实际用房数量，筹备组将要支付　

一天的空房费，如若预定客房数量不足，则与会代表　

将产生不满情绪，造成非常被动的局面。　

若会务组上、下午各要安排６个分组会议，筹备　

组需要在代表下榻的几个宾馆里租借会议室。但事　

先不知道哪些代表将参加哪个分组会，所以筹备组　

需要租借汽车来接送代表。现有４５座、３６座和３３　座的三种类型的汽车，租金分别是半天８００元、７００　

0-1型整数线性规划模型理论

(1) 0-1型整数线性规划

0-1型整数线性规划是一类特殊的整数规划,它的变量仅取值0或1.其模型如下:

Tmin..01(1,2,,)jfstxjncxAx=b取或

其中T12,,,,nccccT12,,,,nxxxx,ijmnaAT12,,,.mbbbb

称此时的决策变量为0-1变量,或称二进制变量.在实际问题中,如果引进0-1变量,就可以把各种需要分别讨论的线性(或非线性)规划问题统一在一个问题中讨论了.

(2) 求解0-1型整数线性规划的分支界定法Matlab指令

x = bintprog(f,A,b): 求解0-1型整数线性规划,用法类似于linprog.

x = bintprog(f,A,b,Aeq,beq): 求解下述线性规划问题:

Tmin,zfxAxb,Axb,Aeqxbeq,x分量取0或1.

x = bintprog(f,A,b,Aeq,beq,x0): 指迭代初值x0,如果没有不等式约束,可用[]代替A,b表示默认,如果没有等式约束,可用[]代替Aeq和beq表示默认;用[x,fval]代替上述各命令行中左边的x,则可得到最优解处的函数值fval.

例如：求解0-1型整数线性规划模型:

1minniiZx

12345356894679123471256758129232200..20002001(1,2,,9)jxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxj或

用Matlab软件编程可解得1236791xxxxxx,其他变量为0,共六门课,满足所给条件, Matlab程序代码如下：

c = ones(1,9);

a =

[-1,-1,-1,-1,-1,0,0,0,0;0,0,-1,0,-1,-1,0,-1,-1;0,0,0,-1,0,-1,-1,0,-1;-1,-1,2,0,0,0,0,0,0;0,0,0,1,0,0,-1,0,0;

0-1规划

0-1规划（Zero-One Programming）是一种最优化问题求解方法。它是一类离散规划问题的特例，通过将问题转化为一个整数规划问题，通过寻找满足一系列约束条件的0-1变量取值，来求解最优解。

0-1规划是一种非常重要的数学模型，可以用来解决许多实际问题。它通常应用于资源分配、项目选择、生产排程等领域。其目标是在满足约束条件的情况下，使得某个目标函数取得最大值或最小值。

在0-1规划中，变量只能取0或1两个值，这种限制使得问题变得更有挑战性。为了将问题转化为0-1规划问题，需要将问题中的决策变量转化为二进制变量，并构建一个合适的目标函数和约束条件。

0-1规划的解决方法主要包括贪婪算法、动态规划和分支定界法等。其中，贪婪算法是最简单、最直观的方法，但不一定能得到最优解；动态规划是一种递推求解的方法，可以解决一些特殊问题；而分支定界法是一种逐步逼近最优解的方法，具有较高的求解精度。

0-1规划的一个经典例子是背包问题。假设有一个背包，容量为W，现在有n个不同重量和价值的物品，需要选择哪些物品放入背包，使得背包中的物品总重量不超过W，同时使得物品的总价值最大化。

对于这个问题，可以将每个物品的选择状态表示为一个0-1变量。如果选择放入背包，变量取值为1；如果不选择放入背包，变量取值为0。然后可以设置目标函数为物品的总价值，约束条件为物品的总重量不超过背包容量。

这个问题可以通过分支定界法求解。首先，将问题分解为一个个子问题，然后通过计算上界和下界，逐步减小解空间。最终可以找到一个近似最优解。

总之，0-1规划是一种重要的最优化问题求解方法。虽然在实际应用中，由于问题的复杂性，往往需要使用更加复杂的算法来求解，但0-1规划的基本思想和方法依然具有广泛的应用。通过合理地构建目标函数和约束条件，可以帮助我们在资源有限的情况下，做出最优的决策。