数学建模0—1规划

公交站点的数学建模的例子0-1规划记录一个关于0-1规划问题（指派问题、分配问题）模型的建立、实现、求解的过程，并在基础模型通过添加惩罚或激励机制考虑多种情况。

记录目的在于学习交流以及日后自己对该类模型能进行较快的进行描述实现。

问题描述（基础）考虑这么一个分配问题有9个数，让他们其中分成2组每组不超过6人，每组又分成A、B两队，每队不超过3人。

目标使得每组A、B两队和之差最小。

用数学题的语言进行描述该问题，现有9人，分成2组，每组最多6人，每组内又分AB两队，如何安排才能使得每组两队分数较为平衡。

思考解的形式我们将解分成2*2个（两组每组两队）部分，每个部分需要重9个数中进行选择，用0-1来表示在该部分中是否被选中，那么它的解的个分别数为9*2*2，用矩阵形式为：将其用向量的形式进行表示：思考约束条件以及目标解的形式确定之后，思考如何针对该解的形式，然后对问题进行描述，从问题中和解的形式，我们可以总结出以下的2个约束：•每组中的A部分和B部分分别小于等于3人•每个数只能出现1次，即每一列的和为1 用公式进行表达为：∑j=113x1ja<=3∑i=13xi1a<=1∑j=113x1jb<=3∑i=13xi 1b<=1......思考目标两队分数之和比较接近，可以理解每一组中为：max(∑(xa)∗y)st.∑(xa)∗y<=1/2∗∑(x)∗y其中x表示9个数的位置（0-1表示），y表示对应位置的数的值,即使得每组A队的分数尽可能大并且接近该组之和的1/2。

将其组合起来可以该总目标表示为：max(∑(xija)∗y）st.∑j=19x1ja<=∑j=19x1jb∑j=19x2ja<=∑j=19x2jb最后将问题进行重新进行整理•目标为：A队之和最大•约束1: 每队小于等于3人•约束2: 每组A队小于B队•约束3: 每个数只能出现1次，即每一列和为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]。

实用文案2012高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员 (打印并签名) ：1. 孔甜程2. 王成3. 刘子恒指导教师或指导教师组负责人 (打印并签名)：日期： 2012 年 8月 15 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：基于0-1整数规划的就业选择模型摘要：当今社会，大学生就业问题已引起了广大的关注，针对这一现象，假设有25个用人单位和25位应聘者，每个人及每个单位的基本条件和要求条件各不相同，某高等院校学生就业指导中心就如何根据用人单位和大学生的基本条件和要求条件进行牵线搭桥，使用人单位和大学生签订就业协议。

本文利用0-1型整数规划建立了大学生就业问题的数学模型，并结合实际提出了通用可行的算法。

首先将用人单位的五个要求条件和应聘者的五个要求条件等级A、B、C、D、E分别做量化处理为5、4、3、2、1，得到用人单位和应聘者的基本条件量化矩阵和要求条件量化矩阵，得出满意度分量。

然后确定最优方案模型，被选人员对用人单位的满意度最大时的人员选取即为所求，从而建立了应聘人员最优选取的0-1整数规划模型关键词：0-1整数规划条件量化满意度1问题重述目前，随着我国高等教育的持续发展，大学生毕业人数逐年增多，大学生就业难问题已经引起了社会各方的广泛关注。

数模练习一某手机运营商准备在一个目前尚未覆盖的区域开展业务，计划投资5000万元来建设中继站。

该区域由15个社区组成，有7个位置可以建设中继站，每个中继站只能覆盖有限个社区。

图1.1.1是该区域的示意图，每个社区简化为一个多边形，每个可以建设中继站的位置已用黑点标出。

由于地理位置等各种条件的不同，每个位置建设中继站的费用也不同，且覆盖范围也不同。

表1.1.2中列出了每个位置建设中继站的费用以及能够覆盖的社区，表1.1.3列出了每个社区的人口数。

表1.1.2每个位置建设中继站的费用及所能覆盖的社区位置 1 2 3 4 5 6 7费用（百万元）9 6.5 20 14.5 19 13 10.5覆盖社区1,2,4 2,3,54,7,8,10 5,6,8,9 8,9,127,10,11,12,1512,13,14,15表1.1.3 每个社区的人口数量社区 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 人口（千人） 2 4 13 6 9 4 8 12 10 11 6 14 9 3 6问题一：在不超过5000万建设费用的情况下，在何处建设中继站，能够覆盖尽可能多的人口；问题二：考虑到中继站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取，针对于5000万元的预算，应该如何建设中继站，才能够使得资费的收入达到最大。

问题分析：问题一，决策变量：为整数）（处建设中继站，位置处不建设中继站，位置i i i i X i ,7110≤≤⎩⎨⎧= 目标函数：},max{··},,max{·},max{·},max{},max{·.},max{··},max{},max{761571471376512611631054954867464253423212311X X y X y X y X X X y X y X X y X X y X X y X y X y X X y X y X y X X y X X y MAX +++++++⋅++++++⋅+⋅=约束条件：5071≤⋅∑=i i i f X用LINGO 软件编程求解，程序如下：sets :position/1..7/:x,f; society/1..15/:r; endsets data :r=2 4 13 6 9 4 8 12 10 11 6 14 9 3 6; f=9 6.5 20 14.5 19 13 10.5; enddatamax =r(1)*@smax (x(1),x(3))+r(2)*@smax (x(1),x(2))+r(3)*x(2)+r(4)*x(3)+r(5)*@smax (x(2),x(4))+r(6)*x(4)+r(7)*x(6)+r(8)*@smax (x(4),x(5))+r(9)*@smax (x(4),x(5))+r (10)*@smax (x(3),x(6))+r(11)*x(6)+r(12)*@smax (x(5),x(6),x(7))+ r(13)*x(7)+r(14)*x(7)+r(15)*@smax (x(6),x(7)); @for (position(i):@bin (x));@sum (position(i):x(i)*f(i))<=50;!@max 和@smax 是不同的。

题目（一）2、观察鱼在水中的运动，发现它不是进行水平运动，而是突发性、锯齿形地向上运动，然后向下滑行。

可以认为这是在长期进化过程中鱼类选择的消耗能量最小的运动方式。

（1）设鱼总是以常速v运动，鱼在水中净重w ，向下滑行的阻力是w在运动方向的分力；向上游动时所需的力是w在运动方向与运动所受阻力之和，而游动的阻力是滑行阻力的k倍。

水平方向游动时的阻力也是滑行阻力的k倍。

写出这些力的表达式。

（2）证明当鱼要从A点到达处于同一水平线上的B点时（见右图），沿折线ACB运动消耗的能量与沿水平线AB运动消耗的能量之比（向下滑行不消耗能量）为 (k*sinα+sinβ)/[k*sin(α+β)]。

（3）据实际观察，tanα≈0.2。

试对不同的值（1.5, 2, 3），根据消耗能量最小的准则估计最佳的β值。

一、模型假设1．鱼在水中运动不受水速影响，且为常速运动；2．不考虑鱼年龄因素对鱼运动消耗能量的影响；二、符号说明v：鱼运动常速w：鱼在水中的净重f：向下滑行时的阻力1f：向上流行的力2f：水平流动阻力3三、问题分析与模型的建立和求解 鱼的受力情况鱼的受力情况如右所示： 由力的分解与合成可知：向下滑行时的阻力1sin f w α=向上流行的力2sin sin f w kw βα=+水平流动阻力3sin f kw α=鱼运动消耗能量鱼运动的能量公式 E fl = 所以 2ACB E f AC =3AB E f AB =又由几何关系可知 sin sin AC BC βα=cos cos AC BC AB βα+=所以sin sin()AC AB ααβ=+也就是sin sin sin()ACB AB E k Q E k αβαβ+==+鱼消耗能量最小的求解要求鱼沿ACB 消耗能量最小，只需求Q 的最小值。

此时有：0,0Q Qαβ∂∂==∂∂此时应满足：1cos()k αβ+=tan 0.2,11.3αα=∴≈︒对于不同的k ，分别求出β，如下表所示：k1.52 3β37︒49︒59︒题目（二）1、某银行经理计划用一笔资金进行证券投资业务，可供购进的证券及其相应信息如下表所示，且有如下规定和限制：（1）市政证券的收益可以免税，其它证券的收益需要按50%的税率纳税；（2）政府及代办机构的证券总共至少购进400万元；（3）所购证券的平均信用等级不超过1.4（信用等级越小，信用程度越高）；（4）所购证券的平均到期年限不超过5年；证券名称证券种类信用等级到期年限到期税前收益率(%)A 市政 2 9 4.3B 代办机构 2 15 5.4C 政府 1 4 5.0D 政府 1 3 4.4E 市政 5 2 4.5请回答下列问题：（1）若该经理有1000万资金，应如何投资？（2）在（1）的条件下，如果能够以2.75%的利率借到不超过100万元，该经理应该如何操作？（3）在1000万元资金情况下，若证券A的税前收益增加为4.5%，投资应否改变？若证券C的税前收益减少为4.8%，投资应否改变？注：为简化问题起见，题中的税前收益率和利率都与年限无关，即都为固定值。

基于01规划的数学模型设计01规划是一种常见的数学规划方法，广泛应用于各种优化问题中。

它是一种整数规划方法，主要解决的是在给定条件下，如何最优地分配资源，或者是最大化或最小化一个目标函数。

本文将介绍基于01规划的数学模型设计。

01规划的数学模型通常可以表示为以下形式：max z = f(x1, x2,..., xn)s.t. ci(x1, x2,..., xn) ≤ 0, i = 1, 2,..., mx1, x2,..., xn ∈ {0,1}其中，z为目标函数，x1, x2,..., xn为决策变量，ci(x1, x2,..., xn)为约束条件，且ci(x1, x2,..., xn) ≤ 0表示该约束条件是一个不等式约束。

x1, x2,..., xn ∈ {0,1}表示决策变量只能是0或1。

求解01规划的方法有很多种，其中比较常用的有：穷举法：对于小规模的问题，可以通过穷举所有可能的解，然后选择最优的解。

分支定界法：对于大规模的问题，可以通过分支定界法来求解。

该方法的基本思想是将问题分解为若干个子问题，然后逐个求解。

在求解的过程中，可以不断剪枝，从而缩小问题的搜索空间。

智能算法：对于一些复杂的问题，可以通过智能算法来求解。

例如遗传算法、蚁群算法等。

这些算法可以模拟生物进化、社会行为等自然现象，从而寻找到最优解。

01规划的应用非常广泛，例如在生产计划、资源分配、物流运输等领域都有广泛的应用。

例如，在生产计划中，可以通过01规划来优化生产线的配置，从而提高生产效率。

在资源分配中，可以通过01规划来优化资源的分配方式，从而提高资源的利用效率。

在物流运输中，可以通过01规划来确定最佳的运输路径和运输方式，从而提高物流效率。

基于01规划的数学模型设计是一种非常有用的数学工具，它可以解决各种优化问题。

在实际应用中，需要根据具体问题来选择合适的求解方法，从而得到最优的解决方案。

随着城市的发展，高层建筑物越来越普遍，而随之而来的是疏散路径的优化问题。

数学建模作业生产计划问题班级数学与应用数学一班高尚学号生产计划问题摘 要本文通过对每个季度各种产品产量、需求量和存储量之间关系的分析，建立了基于Lingo 的生产决策模型，解决了生产计划问题，并提出合理的生产方案得到了总赔偿和存储费用的最优解。

针对该问题，采用线性规划的方法，首先确定ij x 为第j 季度产品i 的产量，ij d 为第j 季度产品i 的需求量，ij s 为第j 季度末产品i 的库存量，用0-1规划来限制上述变量，然后确定这些变量所具有的约束条件，最后列出目标函数与约束条件，利用Lingo 软件（见附录）求解出总的赔偿和库存费用的最小值为5900.70元。

模型思路清晰，考虑周全，可以针对同类问题进行建模，具有一定的应用性和推广性。

关键词： Lingo 、0-1规划、生产决策、线性规划一、问题重述对某厂I、II、III三种产品下一年各季度的合同预订数如表1所示。

该三种产品1季度初无库存，要求在4季度末各库存150件。

已知该厂每季度生产工时为15000.8小时，生产I、II、III产品每件分别需要2.1、4.3、2.7小时。

因更换工艺装备，产品I在2季度无法生产。

规定当产品不能按期交货时，产品I、II每件每迟交一个季度赔偿20.5元，产品III赔10.8元；又生产出来产品不在本季度交货的，每件每季度的库存费用为5.1元。

问该厂应如何安排生产，使总的赔偿加库存的费用为最小。

二、问题分析该问题的目标是使一年总的赔偿加库存费用最小，需要重新建立生产计划，每种产品在每个季度的产量、贮存量、需求量都对最终决策起到了限制,因此需要对变量进行0-1规划，建立目标函数与约束条件，在此基础上实现总的赔偿加库存的费用最小的目的。

三、模型假设1.产量、贮存量、需求量不受外界因素影响；2.产品的生产时间互不影响；3.变量间没有相互影响。

四、变量说明变量含义z总赔偿和库存费用=jix,=4,3,2,1,3,2,1第j季度产品i的产量ij=jd,=i,3,2,1,34,2,1第j季度产品i的需求量ijis=j4,3,2,1,=,3,2,1第j季度末产品i的库存量ij五、模型的建立与求解根据题中所给条件分析可得：决策目标:总的赔偿费用为每个季度各产品费用的总和，总的库存费用为每个季度各产品的总库存量与费用之积，总的赔偿加库存的费用最小为目标，即：()∑∑∑===+++=3131313211.58.105.205.20min j i j ijj j j s d d d z约束条件一：每个季度总工时是有限的，第j 季度生产所有产品所耗总工时不能超过每季度生产工时，即：8.150007.33.41.2321≤++j j j x x x约束条件二：产品I 在第二季度无法生产，产量为0，即：012=x约束条件三：每种产品在第四季度给库存150件，四个季度的总产量与第四季度库存量总和为该种产品一年的总需求量，即：1504141+=∑∑==j j ij ijd x约束条件四：第i 季度的库存量就是本季度生产量与上个季度库存量之和在除去需求量，即：11j jik ij ij ik k k xd s d ==+-=∑∑ 约束条件五：每个季度每种产品的产品量不可能为负数，并且也只能为整数，即：4,3,2,1,3,2,1,0==≥j i x ij 且为整数，线性规划的目标函数与约束条件方程为：33312311112312441111min (20.520.510.8) 5.12.1 4.3 3.715000.80.15001,2,3,1,2,3,4j j j ijj i j j j j ij ij j j jj ik ij ij ik k k ijz d d d s x x x x s t x d x d s d x i j ========+++⎧⎪++≤⎪⎪=⎪⎪=+⎨⎪⎪⎪+-=⎪⎪≥==⎩∑∑∑∑∑∑∑且为整数，利用Lingo得出总的赔偿加库存的费用最小为5900.70元。

0-1规划问题课程设计一、课程目标知识目标：1. 学生能理解0-1规划问题的基本概念和原理，掌握其数学表达形式；2. 学生能够运用0-1规划问题解决实际生活中的优化问题，如资源分配、选择决策等；3. 学生掌握0-1规划问题求解的基本方法，如线性规划、分支定界法等。

技能目标：1. 学生能够运用数学软件或编程语言实现0-1规划问题的建模与求解；2. 学生具备分析实际问题，抽象出0-1规划模型的能力；3. 学生能够通过小组合作，共同解决复杂的0-1规划问题，并展示解题过程。

情感态度价值观目标：1. 学生通过解决0-1规划问题，培养严谨的科学态度和问题解决能力；2. 学生在小组合作中，学会沟通、协作与分享，培养团队合作精神；3. 学生能够认识到数学在实际生活中的广泛应用，激发对数学学科的兴趣和热爱。

课程性质：本课程为数学学科选修课程，旨在提高学生的数学应用能力和问题解决能力。

学生特点：学生具备一定的数学基础，具有较强的逻辑思维能力和学习兴趣。

教学要求：教师需引导学生掌握0-1规划问题的基本理论和求解方法，注重培养学生的实际应用能力和团队合作精神。

通过课程学习，使学生能够将数学知识应用于实际生活，提高问题解决能力。

在教学过程中，关注学生的个体差异，激发学生的学习兴趣和潜能。

二、教学内容1. 0-1规划问题基本概念：介绍0-1规划的定义、特点和应用场景，如指派问题、背包问题等；教材章节：第五章第一节。

2. 0-1规划问题的数学表达：讲解0-1规划问题的标准形式、约束条件和目标函数；教材章节：第五章第二节。

3. 0-1规划问题求解方法：a. 线性规划方法：介绍如何将0-1规划问题转化为线性规划问题进行求解；b. 分支定界法：讲解分支定界法的基本原理及其在0-1规划问题中的应用；c. 动态规划方法：介绍动态规划方法在0-1规划问题中的应用，如背包问题。

教材章节：第五章第三节、第四节。

4. 数学软件与编程语言应用：介绍数学软件（如MATLAB、Lingo）和编程语言（如Python、C++）在0-1规划问题求解中的应用；教材章节：第五章第五节。

0-1规划课程设计一、课程目标知识目标：1. 学生能理解0-1规划的基本概念，掌握其数学模型及其应用场景。

2. 学生能够运用0-1变量表示问题的状态，并建立相应的线性规划模型。

3. 学生能通过分析实际案例，识别问题中的约束条件和目标函数。

技能目标：1. 学生能够独立设计并解决含有0-1变量的线性规划问题。

2. 学生通过小组讨论，学会运用逻辑推理和数学方法解决实际问题。

3. 学生能运用计算机软件辅助求解0-1规划问题，并进行结果分析。

情感态度价值观目标：1. 学生通过解决实际问题，培养科学严谨的态度和问题解决的自信心。

2. 学生在学习过程中，增强团队合作意识，学会尊重他人意见。

3. 学生能够认识到数学在现实生活中的广泛应用，提高学习数学的兴趣。

课程性质分析：本课程为数学学科领域的内容，以实际问题引入0-1规划，注重理论与实践相结合。

课程旨在培养学生运用数学知识解决实际问题的能力。

学生特点分析：考虑到学生所在年级，已具备一定的数学基础和逻辑思维能力。

学生对新知识充满好奇，但需引导其将理论知识与实际应用相结合。

教学要求：1. 教学过程中注重启发式教学，引导学生主动探索和解决问题。

2. 教师应关注学生的个别差异，提供个性化的学习指导。

3. 教学评估以学生的实际操作能力和解决问题的能力为主要依据。

二、教学内容1. 引入0-1规划概念：通过案例分析，让学生了解0-1规划在实际生活中的应用，如人员安排、物流配送等。

相关教材章节：第五章第二节《线性规划的特殊形式》。

2. 0-1变量的数学表示：介绍0-1变量的含义，如何用它来表示问题的状态，并建立相应的数学模型。

相关教材章节：第五章第二节《线性规划的特殊形式》。

3. 约束条件和目标函数的确定：分析实际案例，引导学生识别问题中的约束条件和目标函数。

相关教材章节：第五章第一节《线性规划的基本概念》。

4. 建立和求解0-1规划模型：教授如何将实际问题转化为0-1规划模型，并运用求解方法进行解答。

实验一：数学规划模型AMPL求解专业年级：2014级信息与计算科学1班姓名：黄志锐学号：201430120110一、实验目的1. 熟悉启动AMPL的方法。

2. 熟悉SCITE编辑软件的运行。

3. 熟悉AMPL基本编程。

4. 熟悉AMPL求解数学规划模型的过程。

二、实验内容1. 用AMPL求解下列问题并作灵敏度分析:一奶制品加工厂用牛奶生产A1和A2两种奶制品，1桶牛奶可以在甲类设备上用12小时加工成3公斤A1或者在乙类设备上用8小时加工成4公斤A2，且都能全部售出，且每公斤A1获利24元，每公斤A2获利16元。

先加工厂每天能得到50桶牛奶的供应，每天工人总的劳动时间为480小时，并且甲类设备每天至多加工100公斤A1，乙类设备的加工能力没有限制，试为该厂制定一个计划，使每天的获利最大。

基本模型：根据题意，设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2，每天获利为z元，则可建立线性规划模型如下：max z=72x1+64x2s.t.x1+x2≤5012x1+8x2≤4803x1≤100x1≥0,x2≥0模型求解：使用AMPL编程求解上述线性规划模型（并作敏感性分析）代码如下：结果分析：使用AMPL编程求解上述线性规划模型（并作敏感性分析）结果如下：通过分析上述结果可知，该线性规划模型的全局最优解为x1=20,x2=30，则最优值为3360（即最大利润为3360元）。

求解过程中迭代次数为2次。

对上述线性规划模型进行敏感度分析有：1.目标函数系数变化范围：x.rc x.down x.up :=x1 0 64 96x2 0 48 72;即x.rc为最优解下“资源”增加1单位时“效益”的增量; x.down,x.up为最优解不变时目标函数系数允许变化范围。

2.影子价格raw = 48 原料增加1单位, 利润增长48;time = 2 时间增加1单位, 利润增长2;capacity = 0 加工能力增长不影响利润即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，甲类设备的影子价格为0元。