文档库 最新最全的文档下载
当前位置:文档库 › 整数规划

整数规划

整数规划
整数规划

129

习题五

5.1 试将下述非线性的0-1规划问题转换为线性的0-1规划问题 max z =x 12+x 2x 3-x 33

st. -2x 1+3x 2+x 3 ≤3

x j =0或1(j =1,2,3)

5.2 某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用为最小。若10个井位的代号为s 1,s 2,…,s 10,相应的钻探费用为c 1,c 2,…,c 10,并且井位选择上要满足下列限制条件:

(1) 或选择s 1和s 7,或选择钻探s 8;

(2) 选择了s 3或s 4就不能选s 5,或反过来也一样;

(3) 在s 5,s 6,s 7,s 8中最多只能选两个。

试建立此问题的整数规划模型。

5.3 用分枝定界法求解下列整数规划问题

(1) max z =x 1+x 2

st. x 1+149x 2 ≤14

51 -2x 1 +x 2 ≤3

1 x 1,x 2≥0且为整数

(2) max z =2x 1+3x 2

st. 5x 1+7x 2≤35

4x 1+9x 2≤36

x 1,x 2≥0且为整数

5.4 用割平面法求解下列整数规划问题

(1) max z =7x 1+9x 2

st. -x 1+3 x 2 ≤6

7x 1 + x 2 ≤35

x 1,x 2≥0且为整数

(2) min z =4x 1+5x 2

st. 3x 1+2x 2≥7

x 1+4x 2≥5

3x 1+ x 2≥2

130

x 1, x 2≥0且为整数

5.5 用隐枚举法求解0-1整数规划问题

max z = 3x 1+2x 2-5x 3-2x 4+3x 5

st. x 1+ x 2 + x 3+2x 4+ x 5≤ 4

7x 1 +3x 3-4x 4+3x 5≤ 8

11x 1-6x 2 +3x 4-3x 5≥ 3

x j =0或1(j =1, (5)

5.6 请用解0-1整数规划的隐枚举法求解下面的两维0-1背包问题:

max f = 2x 1+2x 2+3x 3

s.t. x 1+2x 2+2x 3≤4

2x 1+x 2+3x 3≤5

x j =0或1,j=1,2,3

5.7

用匈牙利法求解如下效率矩阵的指派问题

7 9 10 12

13 12 16 17

15 16 14 15

11 12 15 16

5.8 分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数,故规定其中有一个人可兼完成两项任务,其余三人每人完成一项。试确定总花费时间为最少的指派方案。

人 任务 A B C D E

甲 25 29 31 42 37

乙 39 38 26 20 33

丙 34 27 28 40 32

丁 24 42 36 23 45

5.9 已知下列五人各种姿势的游泳成绩(各为50米),试问如何进行指派,

5.10. 运筹学中著名的旅行商贩(货郎担)问题可以叙述如下:某旅行商贩从某一城市出发,到其它几个城市去推销商品,规定每个城市均须到达而且只到达一次,然后回到原出发城市。已知城市i和j之间的距离为d ij,问该商贩应选择一条什么样的路线顺序旅行,使总的旅程为最短。试对此问题建立整数规划模型。

5.11. 有三个不同的产品要在三台机床上加工,每个产品必须首先在机床1上加工,然后依次在机床2,3上加工。在每台机床上加工三个产品的顺序应保持一样,假定用t ij表示在第j机床上加工第i个产品的时间,问应如何安排,使三个产品总的加工周期为最短。试建立此问题的整数规划模型。

复习思考题

5.12 对整数规划问题,是否能先解相应的线性规划问题,然后用凑整的办法求出最优整数解,为什么?

5.13 对可行域是有界的整数规划问题,其可行点的个数是有限的,是否可以用列举法寻找出最优整数解,为什么?

5.14 试用例子说明解指派问题的匈牙利解法比用单纯形法和运输问题的表上作业法都来得简单。

131

运筹学应用实例分析

运筹学课程设计 实践报告 学号: 01 班级: 管理科学与工程类4班

第一部分小型案例分析建模与求解 ................................................................... 错误!未定义书签。 案例1. 杂粮销售问题 ........................................................................................................ 错误!未定义书签。 案例2. 生产计划问题 ........................................................................................................ 错误!未定义书签。 案例3. 报刊征订、推广费用的节省问题 ...................................................................... 错误!未定义书签。 案例4. 供电部门职工交通安排问题 ................................................................................ 错误!未定义书签。 案例5. 篮球队员选拔问题 ................................................................................................ 错误!未定义书签。 案例6. 工程项目选择问题 .............................................................................................. 错误!未定义书签。 案例7. 高校教职工聘任问题(建摸) .......................................................................... 错误!未定义书签。 案例8. 电缆工程投资资金优化问题 ................................................................................ 错误!未定义书签。 案例9. 零件加工安排问题 ................................................................................................ 错误!未定义书签。 案例10. 房屋施工网络计划问题 ...................................................................................... 错误!未定义书签。第二部分:案例设计 ...................................................................................................... 错误!未定义书签。 问题背景: .......................................................................................................................... 错误!未定义书签。 关键词: .............................................................................................................................. 错误!未定义书签。 一、问题的提出 .................................................................................................................. 错误!未定义书签。 二、具体问题分析和建模求解 .......................................................................................... 错误!未定义书签。 三、模型的建立对于N个应聘人员M个用人单位的指派是可行的。......................... 错误!未定义书签。

整数规划实验报告例文

整数规划实验报告例文 篇一:实验报告整数规划 一、实验名称:整数规划问题和动态规划问题 二、实验目的: 熟练使用Spreadsheet建立整数规划、动态规划模型,利用excel建立数学模型,掌握求解过程,并能对实验结果进行分析及评价 三、实验设备 计算机、Excel 四、实验内容 (一)整数规划 1、0-1整数规划 其中,D11=F2;D12=F3;D13=F4;D14=F5; B11=SUMPRODUCT($B$9:$E$9,B2:E2); B12=SUMPRODUCT($B$9:$E$9,B3:E3); B13=SUMPRODUCT($B$9:$E$9,B4:E4); B14=SUMPRODUCT($B$9:$E$9,B5:E5); H8==SUMPRODUCT($B$9:$E$9,B6:E6); 用规划求解工具求解:目标单元格为$H$8,求最大值,可变单元格为$B$9:$E$9,约束条件为 $B$11:$B$14<=$D$11:$D$14;$B$9:$E$9=二进制。在【选项】

果,实现最大利润为140. 2、整数规划 其中,D11=D2;D12=D3; B11=SUMPRODUCT($B$8:$C$8,B2:C2);B12=SUMPRODUCT($B$8:$ C$8,B3:C3); F7=SUMPRODUCT($B$8:$C$8,B4:C4); 用规划求解工具求解:设置目标单元格为F7,求最大值,可变单元格为$B$8:$C$8,约束条件为 $B$11:$B$12<=$D$11:$D$12;$B$8:$C$8=整数。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果,实现最大利润为14. 3、指派问题 人数跟任务数相等: 其中, F11=SUM(B11:E11);F12=SUM(B12:E12);F13=SUM(B13:E13);F14=SU M(B14:E14); B15=SUM(B11:B14);C15=SUM(B11:B14);D15=SUM(B11:B14);E15=SU M(B11:B14); H11,H12,H13,H14,B17,C17,D17,E17单元格值均设为1. 用规划求解工具求解:设置目标单元格为$B$8,求最小值,可变单元格为$B$11:$E$14,约束条件为$B$11:$E$14=二进制; $B$15:$E$15=$B$17:$E$17;$F$11:$F$14=$H$11:$H$14. 在【选

MATLAB求解线性规划含整数规划和01规划问题.pdf

MATLAB 求解线性规划(含整数规划和0-1规划)问题 线性规划是数学规划中的一类最简单规划问题,常见的线性规划是一个有约束的,变量范围为有理数的线性规划。如: max 712z x y =+ 9430045200s.t 310300,0 x y x y x y x y +≤??+≤??+≤??≥? 对于这类线性规划问题,数学理论已经较为完善,可以有多种方法求解此类问题。但写这篇文章的目的并不是为了介绍数学理论,我们这里主要讲解如果利用工具求解这一类线性规划问题。 最著名,同时也是最强大的数学最优化软件是LINGO/LINDO 软件包,它能够求解多种的数学规划问题,同时还提供了多种的分析能力。但LINGO 软件并不容易上手,同时,应用LINGO 的场合一般是大规模的线性规划问题,小小的线性规划完全可以不使用它。一个更受科研人员欢迎的数学软件是MATLAB ,它以功能强大而称著,并有数学软件中的“航空母舰”之称。我们这里就是要学习使用MATLAB 软件求解线性规划(含整数规划和0-1规划)问题。 为了使得不熟悉MATLAB 的人员也能够使用MATLAB 进行线性规划问题求解,本文将对MATALB 中使用到的函数和过程以及结果进行详细的分析,最后会对每一个问题都给出一个可以完全“套用”的MATLAB 程序。 我们首先从上面的线性规划问题开始,为了便于表达,将上面的式子写成矩阵形式: max 712z x y =+ 9430045200s.t 310300,0x y x y ???????? ? ??≤? ? ? ???? ? ???????≥? 于是约束就表达为了一个Ax b ≤不等式。 求解MATLAB 线性规划时,最常用的函数是linprog 函数,下面来介绍一下这个函数的使用。 打开MATLAB 帮助文档(PS:帮助文档的内容是最全的,只要你的英文过了专业8级),可以看到linprog 函数求解的是具有如下标准形式的线性规划:

整数规划的两种数学模型解法

规划模型求解 指导老师: 组员: 组员分工 实际的内容: 1·简要介绍线性规划的历史 线性规划是运筹学中最基本、应用最广泛的分支。规划模型是一类有着广泛应用的确定性的系统优化模型,1939年,苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书. 1947年,美国数学家丹兹格提出了线性规划问题的单纯形求解方法. 1951年,美国经济学家库普曼斯(J.C.Koopmans,1910—1985)出版《生产与配置的活动分析》一书. 1950~1956年,线性规划的对偶理论出现. 1960年,丹兹格与沃尔夫(P.Wolfe)建立大规模线性规划问题的分解算法. 1975年,康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖. 1978年,苏联数学家哈奇扬(L.G.Khachian)提出求解线性规划问题的多项式时间算法(内点算法),具有重要理论意义. 1984年,在美国贝尔实验室工作的印度裔数学家卡玛卡(N.Karmarkar)提出可以有效求解实际线性规划问题的多项式时间算法——Karmarkar算法.

线性规划的基本点就是在满足一定约束条件下,使预定的目标达到最优. 现在线性规划已不仅仅是一种数学理论和方法,而且成了现代化管理的重要手段,是帮助管理者与经营者做出科学决策的一个有效的数学技术. 历史表明,重要数学概念对数学发展的作用是不可估量的,函数概念对数学发展的影响,可以说是贯穿古今、旷日持久、作用非凡,回顾函数概念的历史发展,看一看 函数概念不断被精炼、深化、丰富的历史过程,是一件十分有益的事情,它不仅有助于我们提高对函数概念来龙去脉认识的清晰度,而且更能帮助我们领悟数学概念 对数学发展,数学学习的巨大作用。 2·线性规划的原理:线性规划是合理利用、调配资源 的一种应用数学方法。它的基本思路就是在满足一定的约束条件下,使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定,如何合理筹划,精细安排,用最少的资源(人力、物力和财力)去实现这个任务;二是资源的数量已定,如何合理利用、调配,使任务完成的最多。前者是求极小,后者是求极大。线性规划是在满足企业内、外部的条件下,实现管理目标和极值(极小值和极大值)问题,就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此,线性规划是辅助企业“转轨”、“变型”的十分有利的工具,它在辅助企业经营决策、计划优化等方面具有重要的作用。其一般形式为: n n n n n n b x a x a x a b x a x a x a x c x c x c x f =+++=+++→+++= 2 2222121112121112211min )(

Lingo超经典案例大全

Lingo超经典案例大全 LINGO是Linear Interactive and General Optimizer的缩写,即“交互式的线性和通用优化求解器”。Lingo超强的优化计算能力在很多方面(线性规划、非线性规划、线性整数规划、非线性整数规划、非线性混合规划、二次规划等)比matlab、maple等强得多,Lingo编程简洁明了,数学模型不用做大的改动(或者不用改动)便可以直接采用Lingo语言编程,十分直观。 Lingo模型由4个段构成: (1)集合段(sets endsets);(2)数据段(data enddata); (3)初始段(init endinit);(4)目标与约束段。 Lingo的五大优点: 1. 对大规模数学规划,LINGO语言所建模型较简洁,语句不多; 2. 模型易于扩展,因为@FOR、@SUM等语句并没有指定循环或求和的上下限,如果在集合定义部分增加集合成员的个数,则循环或求和自然扩展,不需要改动目标函数和约束条件; 3. 数据初始化部分与其它部分语句分开,对同一模型用不同数据来计算时,只需改动数据部分即可,其它语句不变; 4. “集合”是LINGO有特色的概念,它把实际问题中的事物与数学变量及常量联系起来,是实际问题到数学量的抽象,它比C语言中的数组用途更为广泛。 5. 使用了集合以及@FOR、@SUM等集合操作函数以后可以用简洁的语句表达出常见的规划模型中的目标函数和约束条件,即使模型有大量决策变量和大量数据,组成模型的语句并不随之增加. 一、求解线性整数规划、非线性整数规划问题: 1.线性整数规划: model: max=x1+x2; x1+9/14*x2<=51/14; -2*x1+x2<=1/3; @gin(x1);@gin(x2); end

用matlab求解整数规划的例子

有四个人,要指派他们分别完成四项工作,每人做各项工作所消耗的时间如表所示: 有四个人,要指派他们分别完成四项工作,每人做各项工作所消耗的时间如表所示: c=[15,18,21,24,19,23,22,18,26,17,16,19,19,21,23,17]; a=[15,18,21,24,zeros(1,12); zeros(1,4),19,23,22,18,zeros(1,8); zeros(1,8),26,17,16,19,zeros(1,4); zeros(1,12),19,21,23,17; 15,zeros(1,3),19,zeros(1,3),26,zeros(1,3),19,zeros(1,3); zeros(1,1),18,zeros(1,3),23,zeros(1,3),17,zeros(1,3),21,zeros(1,2); zeros(1,2),21,zeros(1,3),22,zeros(1,3),16,zeros(1,3),23,0; zeros(1,3),24,zeros(1,3),18,zeros(1,3),19,zeros(1,3),17]; b=[24;23;26;23;26;23;23;24]; A=[ones(1,4),zeros(1,12); zeros(1,4),ones(1,4),zeros(1,8); zeros(1,8),ones(1,4),zeros(1,4); zeros(1,12),ones(1,4); 1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3); 0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,2); 0,0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,0; zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1]; B=ones(1,8);

01型整数规划模型

甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模 型的组合方案如下:其中X 为可能竞争到的专业推广者人数,即动态规划模型中第一天的

专业推广者推 广能力的份数,Y 为第二天需要的专业推广者推广能力的份数,即第三天安排从事推广 工作的专业推广者的人数;Z 为第三天需要的专业推广者推广能力的份数,即第三天安排从事推广工作的专业推广者的人数;a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数(每批20 人),其中,有多种组合方案;甲公司雇佣这些兼职推广者均工作一天,从事推广工作,第二天辞退a ?b 批兼职推广员,其余的b 批继续从事推广工作一天后辞退,即兼职宣传员总共最多雇佣2 天;cost 为花费的成本,即资金的使用数量;F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据,根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧,即不合作的情况下甲公司可以尽量争取到9 人,如若 不行,考虑争取4 人。 §5.4 0—1型整数规划模型 1、 0—1型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划,在实际问题的应用中,整数规划模型对应着大量的生产计划或活动安排等决策问题,整数规划的解法主要有分枝定界解法及割平面解法(这里不作介绍,感兴趣的读者可参考相关书籍)。在整数规划问题中,0—1型整数规划则是其中较为特殊的一类情况,它要求决策变量的取值仅为0或1,在实际问题的讨论中,0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论,我们将列举一些模型范例,以说明这个事实。 0—1型整数规划的的数学模型为: 目标函数 n n x c x c x c z M i n M a x +++= 2211)( 约束条件为: ???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(2211222221211 1212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21 这里,0 | 1表示0或1。 2、0—1型整数规划模型的解法

整数规划

整数规划

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S 1,S 2.…,S 10相应的钻探费用为C 1 ,C 2 ,… C 10,并且井位选择要满足下列限制条件: (1) 在s 1,s 2,S 4中至多只能选择两个; (2)在S 5,s 6中至少选择一个;(3)在s 3,s 6,S 7,S 8中至少选择两个。 试建立这个问题的整数规划模型 解:设x j (j=1,…,10)为钻井队在第i 个井位探油 minZ=j j j x c ∑=10 1 背包问题:一个登山队员,他需要携带的物品有:食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 解:引入0—1变量x i , x i =1表示应携带物品i ,,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区,每个区都可以建消防站,市政府希望设置的消防站最少,但必须满足在城市任何地区发生火警时,消防车要在15min 内赶到现场。据实地测定,各区之间消防车行驶的时间见表,请制定一个布点最少的计划。 地区1 地区2 地区3 地区4 地区5 地区6 地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0

整数规划

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S 1,S 2.…,S 10相应的钻探费用为C 1 ,C 2 ,… C 10,并且井位选择要满足下列限制条件: (1)在s 1,s 2,S 4中至多只能选择两个; (2)在S 5,s 6中至少选择一个;(3)在s 3,s 6,S 7,S 8中至少选择两个。 试建立这个问题的整数规划模型 解:设x j (j=1,…,10)为钻井队在第i 个井位探油 minZ=j j j x c ∑=10 1 背包问题:一个登山队员,他需要携带的物品有:食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。 解:引入0—1变量x i , x i =1表示应携带物品i ,,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,102542126255104814181520765432176 54321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区,每个区都可以建消防站,市政府希望设置的消防站最少,但必须满足在城市任何地区发生火警时,消防车要在15min 内赶到现场。据实地测定,各区之间消防车行驶的时间见表,请制定一个布点最少的计划。

解:引入0—1变量x i , x i =1表示在该区设消防站,,x i =0表示不设 ????? ??????=≥++≥++≥++≥+≥++≥++++++=0 1111111min 65 2 654 543 436 2 121654321或i x x x x x x x x x x x x x x x x x x x x x x x z 解得: X*=(0,1,0,1,0,0)’ Z*=2 某公司现有5个项目被列入投资计划,各项目的投资额和期望的投资收益如下表所示: 该公司只有600万元资金可用于投资,由于技术上的原因,投资受到以下条件的 约束:(1)在项目1、2和3中必须有一项被选中,(2)项目3和项目4只能选中一项,(3)项目5被选中的前提是项目1必须被选中。试就这一问题建立运筹学研究模型。 5.2某市为方便学生上学,拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表5–2所示,问为覆盖所有小区至少应建多少所小学,要求建模并求解。

第六章---运筹学-整数规划案例

第六章整数规划 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 . 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解: 2、 min f=10x1+9x2 . 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0

求解下列整数规划问题 1、 min f=4x1+3x2+2x3 . 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解:最优解(0,0,1),最优值:2 2、 min f=2x1+5x2+3x3+4x3 . -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解:此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 . 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解:最优解(0,3,4,3),最优值:47 4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5+3 x6+4 x7+3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5+ x6-10 x16≤0 x7+ x8+ x9-20 x17≤0 x10+ x11+ x12-30 x18≤0 x13+ x14+ x15-40 x19≤0 x1 + x4+ x7+x10+ x13=30 x2 + x5+ x8+x11+ x14=20 x3 + x6+ x9+x12+ x15=20 x i为非负数(i=1,2…..8) x i为非负整数(i=9,10…..15) x i为为0-1变量(i=16,17…..19) 解:最优解(30,0,0,0,0,0,0,0,0,0,0,0,0,20,20,0,0,0,1),最优值:860 一餐饮企业准备在全市范围内扩展业务,将从已拟定的14个点中确定8个点建立分店,由于地理位置、环境条件不同,建每个分店所用的费用将有所不同,现拟定的14个店的费用情况如下表:

第六章整数规划

第五章整数规划 一、填空题 1.用分枝定界法求极大化的整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的()。 2.在分枝定界法中,若选Xr=4/3进行分支,则构造的约束条件应为()。 3.已知整数规划问题P0,其相应的松驰问题记为P0’,若问题P0’无可行解,则问题P。()。 4.在0 - 1整数规划中变量的取值可能是()或()。 5.对于一个有n项任务需要有n个人去完成的分配问题,其解中取值为1的变量数为()个。 6.分枝定界法和割平面法的基础都是用()求解整数规划。 7.若在对某整数规划问题的松驰问题进行求解时,得到最优单纯形表中,由X。所在行得X1+1/7x3+2/7x5=13/7,则以X1行为源行的割平面方程为()。 8.在用割平面法求解整数规划问题时,要求全部变量必须都为()。 9.用()求解整数规划问题时,若某个约束条件中有不为整数的系数,则需在该约束两端扩大适当倍数,将全部系数化为整数。 10.求解纯整数规划的方法是割平面法。求解混合整数规划的方法是()。 11.求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是()。 12.在应用匈牙利法求解分配问题时,最终求得的分配元应是()。 13.分枝定界法一般每次分枝数量为()个. 二、单选题 1.整数规划问题中,变量的取值可能是()。 A.整数B.0或1C.大于零的非整数D.以上三种都可能 2.在下列整数规划问题中,分枝定界法和割平面法都可以采用的是A()。 A.纯整数规划B.混合整数规划C.0—1规划D.线性规划 3.下列方法中用于求解分配问题的是()。 A.单纯形表B.分枝定界法C.表上作业法D.匈牙利法 三、多项选择

01型整数规划模型

§5.4 0—1型整数规划模型 1、 0—1型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划,在实际问题的应用中,整数规划模型对应着大量的生产计划或活动安排等决策问题,整数规划的解法主要有分枝定界解法及割平面解法(这里不作介绍,感兴趣的读者可参考相关书籍)。在整数规划问题中,0—1型整数规划则是其中较为特殊的一类情况,它要求决策变量的取值仅为0或1,在实际问题的讨论中,0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论,我们将列举一些模型范例,以说明这个事实。 0—1型整数规划的的数学模型为: 目标函数 n n x c x c x c z Min Max +++=ΛΛ2211)( 约束条件为: ???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(2211222221211 1212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,2 1ΛΛΛΛΛΛΛΛΛΛΛΛ 这里,0 | 1表示0或1。 2、0—1型整数规划模型的解法 0—1型整数规划模型的解法一般为穷举法或隐枚举法,穷举法指的是对决策变量 n x x x , , ,21ΛΛ的每一个0或1值,均比较其目标函数值的大小,以从中 求出最优解。这种方法一般适用于决策变量个数n 较小的情况,当n 较大时,由于n 个0、1的可能组合数为n 2,故此时即便用计算机进行穷举来求最优解,也 几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法,该法虽能减少运算次数,但有的问题并不使用。此时,就只能用穷举法了。 3. 应用实例 例1 工程上马的决策问题

整数规划割平面法

割平面法 求解整数规划问题: Max Z=3x1+2x2 2x1+3x2?14 4x1+2x2?18 x1,x2?0,且为整数 解:首先,将原问题的数学模型标准化,这里标准化有两层含义:(1)将不等式转化为等式约束,(2)将整数规划中所有非整数系数全部转化为整数,以便于构造切割平面。从而有:Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x2?0,且为整数 利用单纯形法求解,得到最优单纯形表,见表1: 表1

最优解为:x1=13/4, x2=5/2, Z=59/4 根据上表,写出非整数规划的约束方程,如:x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式,即:(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左边,分数及带有分数系数的变量称到方程右边,得:x2 - x4-2 =1/2-(1/2x3+1/2x4) (2) 由于原数学模型已经“标准化”,因此,在整数最优解中,x2和x4也必须取整数值,所以(2)式左端必为整数或零,因而其右端也必须是整数。又因为x3,x4?0,所以必有: 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数,于是有: 1/2-(1/2x3+1/2x4)?0 (3) 或 x3+x4?1 (4) 这就是考虑整数约束的一个割平面约束方程,它是用非基变量表示的,如果用基变量来表示割平面约束方程,则有: 2x1+2x2?11 (5)

从图1中可以看出,(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部 分区域,使点E(3.5,2)成为可行域的一个极点。 图1 在(3)式中加入松弛变量x5,得: -1/2x3-1/2x4+x5=-1/2 (6) 将(6)式增添到问题的约束条件中,得到新的整数规划问题: Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 -1/2x3-1/2x4+x5=-1/2 x i?0,且为整数,i=1,2,…,5 该问题的求解可以在表1中加入(6)式,然后运用对偶单纯形法求出最优解。具体计算过程见表2: 表2

整数规划和多目标规划模型

1 整数规划的MATLAB 求解方法 (一) 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数,因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序,在此命名为intprog ,在原程序的基础上做了简单的修改,将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种,即:选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下: [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为: ????? ??????∈=≥≤≤=≤=) 取整数(M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ) ,,2,1(0 ..min 在上述标准问题中,假设x 为n 维设计变量,且问题具有不等式约束1m 个,等式约束2m 个,那么:c 、x 均为n 维列向量,b 为1m 维列向量,eq b 为2m 维列向量,A 为n m ?1维矩阵,eq A 为n m ?2维矩阵。 在该函数中,输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数,A 为不等式约束条件方程组构成的系数矩阵,b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵,b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号,例如问题中设计变量为621,,,x x x ,要求32,x x 和6x 为整数,则M=[2;3;6];若要求全为整数,则M=1:6,或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限,即若某数x 和最邻近整数相差小于该误差限,则认为x 即为该整数。

整数规划习题

第五章 整数规划习题 5.1 考虑下列数学模型 )()(m in 2211x f x f z += 且满足约束条件 (1)或101≥x ,或102≥x ; (2)下列各不等式至少有一个成立: ??? ??≥+≥+≥+15 215152212121x x x x x x (3)021=-x x 或5或10 (4)01≥x ,02≥x 其中 )(11x f =?? ?=>+0,0 0,520111x x x 如如 =)(2 2x f ?? ?=>+0,00,612222x x x 如如 将此问题归结为混合整数规划的模型。 解:2211612510m in x y x y z +++= ? ? ?????????????? ????=≥≥=+++++-+-=-≤++-≥+-≥+-≥+?--≥?-≥?≤?≤),,=(或,)()()(;)(11.110;00)4(1 11105503215215152)1(1010102111 1098711109872165462152142132312211i y x x y y y y y y y y y y x x y y y M y x x M y x x M y x x M y x M y x M y x M y x i 5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题 3 3 3221max x x x x z -+= ?? ?==≤++-) ,(或3,2,110332321j x x x x j

解:令=y ???==否则,当,01132x x 故有y x x =32,又21x ,3 1x 分别与1x ,3x 等价,因此题中模型可转换为 31m ax x y x z -+= ? ???? ?? ??-+≤+≤≤≤++-变量均为10,,,1 3 323213 23 2321y x x x y x x x y x y x x x 5.3 某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1 要求:(1)装入卫星的仪器装置总体积不超过V ,总质量不超过W ;(2)A 1与A 3中最多安装一件;(3)A 2与A 4中至少安装一件;(4)A 5同A 6或者都安上,或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。 解: j j j x c z ∑==6 1 max ??? ?? ?????????????==≥+≤+≤≤∑∑==否则 仪器安装,0,111 654231 6 1 6 1j j j j j j j j A x x x x x x x W x w V x v 5.4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用最小。若10个井位的代号为s 1 ,s 2,…s 10,相应的钻探费用为c 1 ,c 2,…,c 10,并且井位选择上要满足下列限制条件:

第二章 整数规划

第二章 整数规划 §1 概论 1.1 定义 规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类: 1o 变量全限制为整数时,称纯(完全)整数规划。 2o 变量部分限制为整数的,称混合整数规划。 1.2 整数规划特点 (i ) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况: ①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21m in x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为:4 5 min ,45,021===z x x 。 ③有可行解(当然就存在最优解),但最优解值变差。 例2 原线性规划为 21m in x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为:2 3 min ,23,021===z x x 。 若限制整数得:2m in ,1,121===z x x 。 (ii ) 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类: (i )分枝定界法—可求纯或混合整数线性规划。 (ii )割平面法—可求纯或混合整数线性规划。 (iii )隐枚举法—求解“0-1”整数规划: ①过滤隐枚举法; ②分枝隐枚举法。 (iv )匈牙利法—解决指派问题(“0-1”规划特殊情形)。 (v )蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系

整数规划实验案例

1、一个公司考虑到北京、上海、广州和武汉四个城市设立库房,这些库房负责向华北、华中、华南三个地区供货,每个库房每月可处理货物1000件。在北京设库房每月成本为4.5万元,上海为5万元,广州为7万元,武汉为4万元。每个地区的月平均需求量为:华北每月500件,华中每月800件,华南每月700件。发运货物的费用(单位:元/件)如下表所示: 公司希望在满足地区需求的条件下使平均月成本为最小,且还要满足以下条件: a)如果在上海设库房,则必须也在武汉设库房; b)最多设两个库房; c)武汉和广州不能同时设库房; 请写出一个满足上述要求的整数规划模型,并求出最优解。 2、华南投资公司决定投资兴办产业,以增强发展后劲,投资总额为800万元,其中第一年(即1998年)350万元,第二年300万元,第三年150万元。投资方案有: A1:建立彩色印刷厂。第一、二年年初分别投入220万元220万元,第二年年底可获利60万元,第三年起每年获利130万元。 A2:投资离子镀膜基地。第一年投资70万元,第二年起每年获利18万元。 A3:投资参股F企业,第二年投入180万元设备,第三年起每年可获利50万元。 A4:投资D企业,每年年底可获得投资额的25%的利润,但第一年最高投资额为80万元,以后每年递增不超过15万元。 A5:建立超细骨粉生产线,第三年投入320万元第四年起每年可获利90万元。 A6:投资所属中北机电设备公司,年底回收本利120%,但每年投资额不低于60万元。A7:投资所属澳得技术公司,年底回收本利115% 所求问题:投资期为五年,需从上述七个方案中选择最优投资组合,使得五年末时资金总额为最大。

整数规划的数学模型及解的特点

整数规划的数学模型及解的特点 整数规划IP (integer programming):在许多规划问题中,如果要求一部分或全部决策变量必须取整数。例如,所求的解是机器的台数、人数、车辆船只数等,这样的规划问题称为整数规划,简记IP 。 松弛问题(slack problem):不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。 若松弛问题是一个线性规化问题,则该整数规划为整数线性规划(integer linear programming)。 一、整数线性规划数学模型的一般形式 ∑==n j j j x c Z 1 min)max(或 中部分或全部取整数n j n j i j ij x x x m j n i x b x a t s ,...,,...2,1,...,2,10 ),(.211 ==≥=≥≤∑= 整数线性规划问题可以分为以下几种类型 1、纯整数线性规划(pure integer linear programming):指全部决策变量都必须取整数值的整数线性规划。有时,也称为全整数规划。

2、混合整数线性规划(mixed integer liner programming):指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。 3、0—1型整数线性规划(zero —one integer liner programming):指决策变量只能取值0或1的整数线性规划。 1 解整数规划问题 0—1型整数规划 0—1型整数规划是整数规划中的特殊情形,它的变量仅可取值0或1,这时的 ???? ? ????≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z

用LINGO求解整数规划的例子

附1:用LINGO求解整数规划的例子。 某钢管零售商从钢管厂进货,将钢管按照顾客要求的长度进行切割,称为下料。假定进货时得到的原料钢管长度都是19m。 1)现有一客户需要50根长4m、20根长6m和15根长8m的钢管。应如何下料最节省? 2)零售商如果采用的不同切割模式太多,将会导致生产过程的复杂化,从而增加生产和管理成本。所以该零售商规定采用的不同切割模式不能超过3种。此外。该客户除需要1)中的3种钢管外,还要10根长5m的钢管。应如何下料最节省? 问题分析:对于下料问题首先要确定采用哪些切割模式。所谓切割模式,是指按照顾客要求的长度在原料钢管上安排切割的一种组合。例如,我们可以将19m的钢管切割成3根长4m的钢管,余料为7m;或者将长19m的钢管切割成长4m、6m和8m的钢管各1根,余料为1m。显然,可行的切割模式是很多的。 其次,应当明确哪些切割模式是合理的。合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。例如,可以将长19m的钢管切割成3根4m的钢管是可行的,但余料为7m,可进一步将7m的余料切割成4m钢管(余料为3m),或者将7m的余料切割成6m钢管(余料为1m)。经过简单的计算可知,问题1)的合理切割模式一共有7种,如表1所示: 于是问题转化为在满足客户需要的条件下,按照哪几种合理的模式,每种模式切割多少根原料钢管最为节省。而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。 问题1)用x i表示按照表1第i种模式(i=1,2,…,7)切割的原料钢管的根数,若以切割后剩余的总余料量最小为目标,则按照表1最后一列可得 minZ1 = 3x1+x2+3x3+3x4+x5+x6+3x7 若以切割原料钢管的总根数最少为目标,则有 表1 钢管下料问题1)的合理切割模式

相关文档