清华数学实验整数规划作业

3．用LINGO 软件求解：

1maxz?cTx?xTQx

2s..t ?1?x1x2?xx3?41 ?3?x1?x2?x3?x?42 x1,x2,x3,x 1}?{1,4?其中c=(6,8,4,-2)T,Q 是三对角线矩阵，主对角线上元素全为-1，两条次对角线上元素全为2。 解：

【1】设计程序。

由于Q是三对角矩阵。设计lingo程序如1ingo1003。 【2】得出答案并绘制表格 X( 1) X( 2) X( 3) 1.000000 1.000000 0.000000 【结论】 得出maxz=15.

【附录】

model: sets:

set1/1..4/:x,c; ! set1表示由1~4组成的集合，c(i)为c矩阵的第i个值 b/1,2/:value; ! m(set1,b):d; link(set1,set1):Q; endsets data: c=6 8 4 -2; Q=-1 2 0 0 2 -1 2 0 0 2 -1 2 0 0 2 -1; value=1,-1; enddata

max=-1/2

1、一个公司考虑到北京、上海、广州和武汉四个城市设立库房，这些库房负责向华北、华中、华南三个地区供货，每个库房每月可处理货物1000件。在北京设库房每月成本为4.5万元，上海为5万元，广州为7万元，武汉为4万元。每个地区的月平均需求量为：华北每月500件，华中每月800件，华南每月700件。发运货物的费用（单位：元/件）如下表所示： 北京 上海 广州 武汉 华北 200 300 600 350 华中 400 250 350 150 华南 500 400 300 350 公司希望在满足地区需求的条件下使平均月成本为最小，且还要满足以下条件：

a) 如果在上海设库房，则必须也在武汉设库房； b) 最多设两个库房；

c) 武汉和广州不能同时设库房；

请写出一个满足上述要求的整数规划模型，并求出最优解。

2、华南投资公司决定投资兴办产业，以增强发展后劲，投资总额为800万元，其中第一年（即1998年）350万元，第二年300万元，第三年150万元。投资方案有： A1：建立彩色印刷厂。第一、二年年初分别投入220万元220万元，第二年年底可获利60万元，第三年起每年获利130万元。

A2：投资离子镀膜基地。第一年投资70万元，第二年起每年获利18万

数学建模与实验课程 实验报告

实验名称 三、线性规划与整数规划 实验地点 日期 2014-10-28 姓名 班级 学号 成绩

【实验目的及意义】

[1] 学习最优化技术和基本原理，了解最优化问题的分类； [2] 掌握规划的建模技巧和求解方法； [3] 学习灵敏度分析问题的思维方法；

[4] 熟悉MATLAB软件求解规划模型的基本命令；

[5] 通过范例学习，熟悉建立规划模型的基本要素和求解方法。

通过该实验的学习，使学生掌握最优化技术，认识面对什么样的实际问题，提出假设和建立优化模型，并且使学生学会使用MATLAB、Lingo软件进行规划模型求解的基本命令，并进行灵敏度分析。解决现实生活中的最优化问题是本科生学习阶段中一门重要的课程，因此，本实验对学生的学习尤为重要。 【实验要求与任务】

根据实验内容和步骤，完成以下实验，要求写出实验报告（符号说明—模型的建立—模型的求解（程序）—结论）

A组

高校资金投资问题

高校现有一笔资金10

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件： (1)在s1，s2，S4中至多只能选择两个； （2）在S5，s6中至少选择一个；（3）在s3，s6，S7，S8中至少选择两个。 试建立这个问题的整数规划模型

解：设xj（j=1,…,10）为钻井队在第i个井位探油 minZ=?cjxj

j?110

背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为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变量xi, xi=1表示应携带物品i，,xi=0表示不应携带物品I

naxz?20x1?15x2?18x3?14x4?8x5?4x6?10x7?5x1?5x2?2x3?6x4?12x5

第五章 整数规划习题

5.1 考虑下列数学模型 min且满足约束条件

z?f1(x1)?f2(x2)

（1）或x1?10，或x2?10；

（2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

（3）

x1?x2?0或5或10

?0（4）x1其中

?0，x2

?20?5x1,如x1?0?,如x1?0f1(x1)?0=

将此问题归结为混合整数规划的模型。 解：min

z?10y1?5x1?12y2?6x2?12?6x2,如x2?0?,如x2?0f2(x2)??0

5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题

maxz?x1?x2x3?x323（?0）x1?y1?M；x2?y2?M?（1）x1?10?y3?M??x2?10?(1?y3)?M?（?2）x1?x2?15?y4M?x1?x2?15?y5M??x1?2x2?15?y6M??y4?y5?y6?2?（?3）x1?x2?0y7?5y8?5y9?10y10?11y11?y7?y8?y9?y10?y11?1??1i＝1，.???，11）?(4)x1?0，x2?

第五章 整数规划习题

5.1 考虑下列数学模型 min且满足约束条件

z?f1(x1)?f2(x2)

（1）或x1?10，或x2?10；

（2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

（3）

x1?x2?0或5或10

?0（4）x1其中

?0，x2

?20?5x1,如x1?0?,如x1?0f1(x1)?0=

将此问题归结为混合整数规划的模型。 解：min

z?10y1?5x1?12y2?6x2?12?6x2,如x2?0?,如x2?0f2(x2)??0

5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题

maxz?x1?x2x3?x323（?0）x1?y1?M；x2?y2?M?（1）x1?10?y3?M??x2?10?(1?y3)?M?（?2）x1?x2?15?y4M?x1?x2?15?y5M??x1?2x2?15?y6M??y4?y5?y6?2?（?3）x1?x2?0y7?5y8?5y9?10y10?11y11?y7?y8?y9?y10?y11?1??1i＝1，.???，11）?(4)x1?0，x2?

运筹学实验二——整数规划

一、实验目的

熟悉WinQSB软件LP-ILP子系统界面内容，掌握操作命令。用WinQSB软件求解整数规划问题（分支定界法）。

二、实验平台和环境

WindowsXP平台下，WinQSB V2.0版本已经安装在D:\\WinQSB中。

三、实验内容和要求

建立整数规划新问题，使用WinQSB软件输入模型，求解模型，并对问题的结果进行简单分析。

四、实验操作步骤

求解整数规划。启动程序，点击开始?程序?WinQSB?Linear and Integer Programming。

点击菜单栏Solve and Analyze?Solve and Display Steps或点击工具栏中的图标支定界法求解，观察一下软件用分支定界法求解IP的迭代步骤。 五、分析讨论题

1、求以下整数规划问题的最优解 （1）

用分

MaxZ?40x1?90x2?9x1?7x2?56?s.t.?7x1?20x2?70?x,x?0且取整数?12

（2）

MaxZ?x1?x2?2x1?x2?6?4x?5x?20 ?2s.t.?1?x1,x2?0??x1,x2为整数2、求以下0，1规划问题的最优解

MaxZ?3x1?2x2?5x3?x1?2x2?x3?

整数规划+指派问题

解：设 xij

1, 如果第i项由第j个人完成 0, 如果第i项未由第j个人完成

,用

f (x )

表示所花费的总时间，由题意

现有 A、B、C、D、E 共 5 个人，挑选其中

可得如下模型

的时间如表所示。规定每项工作只能由

m i n f ( x ) 1 0 x1 1 2 x1 2 3 x1 3 1 5 x1 4 9 x1 5 5 x 21 1 0 x 22 1 5 x 23 2 x 24 4 x 25 1 5 x31 5 x32 1 4 x33 7 x34 1 5 x35 2 0 x 41 1 5 x 42 1 3 x 43 6 x 44 8 x 45 x1 1 x1 2 x 21 x 22 x31 x32 x 41 x 42 x x 21 11 x1 2 x 2 2 x x 23 13 x1 4 x 2 4 x1 5 x 2 5 x 44 0 x ij 0 x1 3 x1 4 x1 5 1 x 23 x

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

1

专业推广者推

广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广 工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a ?b批兼职推广员，其余的b批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若

不行，考虑争取4 人。

§5.4 0—1型整数规划模型

1、 0—1型整数规划模型概述

整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主

整数规划和对策论模型实验作业

一、 基本实验

1.工程安排问题

三年内有五项工程可以考虑施工。每项工程的期望收入和年度费用如表4.1.所示。假定每一项已经选定的工程要在整个三年内完成。目标是要选出使总收入达到最大的那些工程。

表4.1 每项工程期望收入和年度费用表（单位：千元）

费用 工程 第一年 1 2 3 4 5 可用基金 5 4 3 7 8 25 第二年 1 7 9 4 6 25 第三年 8 10 2 1 10 25 20 40 20 15 30 收入 解：设0-1变量xi,i=1,2,3,4,5为工程i,i=1,2,3,4,5的投资情况。Xi=0,说明i项目不投资，xi=1,说明对i项目进行投资。

目标项为：

Max z=20*x1+40*x2+20*x3+15*x4+30*x5, 约束条件为：

5x1+ 4x2+3x3+7x4+ 8x5≤25， X1+ 7x2+9x3+4x4+ 6x5≤25， 8x1+10x2+2x3+ x4+10x5≤25， @bin(xi),i=1,2,3,4,5. 写成Lingo程序：

Max =20*x1+40*x2+20*x3+15*x4+30*x5; 5*x1+ 4*x2+3*x3+7*x4+ 8*x