2012——2013学年第 一 学期
合肥学院数理系
实验报告
课程名称： 运 筹 学
实验项目： 应用LINDO软件求解整数规划
实验类别：综合性□ 设计性 □√ 验证性□
专业班级： 10级数学与应用数学（1）班
姓 名： 汪 勤 学 号： 1007021004
实验地点： 35-612
实验时间： 2012-11-29
指导教师： 管梅老师 成 绩：
1
一.实验目的
1、熟悉LINDO软件的求解整数规划功能。
2、学习应用LINGO软件求解整数规划问题。
3、熟练掌握LINGO软件的操作。
二.实验内容
1、某班有男同学30人,女同学20人,星期天准备去植树。根据经验,一天中,男同学平均每人挖坑20个,或栽树30棵,或给25棵树浇水,女同学平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多。建立该问题的数学模型，并求其解。
2、求解线性规划：121212212max2251228..010,zxxxxxxstxxx为整数
3、在高校篮球联赛中,我校男子篮球队要从８名队员中选择平均身高最高的出场阵容,队员的号码、身高及擅长的位置如下表：
队员 身高（m） 位置
1 1.92 中锋
2 1.90 中锋
3 1.88 前锋
4 1.86 前锋
5 1.85 前锋
6 1.83 后卫
7 1.80 后卫
8 1.78 后卫
同时，要求出场阵容满足以下条件： 2 ⑴ 中锋最多只能上场一个。
第4章 整数规划
判断:
用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；
指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；
效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响；
匈牙利法只能用于平衡分配问题；
对于极大化问题，匈牙利法不能直接求解。
整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。
用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。
用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。
分配问题的每个元素都加上同一个常数k，并不会影响最优分配方案。
分配问题的每个元素都乘上同一个常数k，并不会影响最优分配方案。
分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。
隐枚举法也可以用来求解分配问题
简答
试述分枝定界法求解问题的主要思想。
试述隐枚举法的步骤。
试讲述割平面方法的基本原理.
试例举三种应该剪枝的情况。
计算题
分枝定界法
用分枝定界法求解下列整数规划问题
12maxZxx
1212129511414123,xxxxxx0且为整数
用分枝定界法求解下列整数规划问题
12max32Zxx
121212231429,xxxxxx0且为整数
用分枝定界法求解下列整数规划问题
12max2010Zxx
1232312312324434323,,xxxxxxxxxxx－--0且为整数
用分枝定界法求解下列整数规划问题
12max79Zxx
百度文库 - 好好学习，天天向上
-1 P120第1（1）题
求整数规划问题
原问题A
松弛问题B
a=[
3 4 1 1 0 10
4 2 3 0 1 8
0 -4 -3 0 0 0]
zuiyoujie =
0
0
value =
最优解不是整数解，对问题B关于x1进行分支
B1
a=[
4 1 1 0 0 10
2 3 0 1 0 8
1 0 0 0 1 2
-4 -3 0 0 0 0]
zuiyoujie =
2
4/3
2/3
0
0
0 百度文库 - 好好学习，天天向上
-2 0
0
value =12
B2
a=[
4 1 1 0 0 10
2 3 0 1 0 8
1 0 0 0 -1 3
-4 -3 0 0 0 0]
无可行解
对问题B1关于x2进行分支
B11
a=[
4 1 1 0 0 0 10
2 3 0 1 0 0 8
1 0 0 0 1 0 2
0 1 0 0 0 1 1
-4 -3 0 0 0 0 0]
zuiyoujie =
2
1
1
1
0
0
value = 百度文库 - 好好学习，天天向上
-3 11
B12
a=[
4 1 1 0 0 0 10
2 3 0 1 0 0 8
1 0 0 0 1 0 2
0 1 0 0 0 -1 2
-4 -3 0 0 0 0 0]
zuiyoujie =
0
0
value =10
P120第1（3）题
求整数规划问题
原问题A
松弛问题B
a=[
3 5 4 1 0 24
4 2 5 0 1 13
整数规划求解题技巧
整数规划（Integer Programming，IP）是线性规划（Linear Programming，LP）的扩展，它要求所有变量的取值必须是整数。整数规划常用于求解实际问题中的最优决策，具有广泛的应用领域，如运输、生产、资源分配等。下面我将介绍一些整数规划求解题的技巧。
1. 转化为纯整数规划：将实际问题转化为纯整数规划问题可以简化模型。纯整数规划要求所有变量的取值都必须是整数，没有连续变量的限制。通过建立合适的约束条件和目标函数，可以将问题转化为纯整数规划问题进行求解。
2. 松弛约束：对于某些约束条件，如果将其从等式形式变为不等式形式且松弛一些限制，可以增加问题的可行解空间。这样可以使得模型具有更多的可行解，从而提高求解效率。
3. 分枝定界法：分枝定界法是一种常用的求解整数规划问题的方法。它将整数规划问题划分为多个子问题，通过不断划分和求解这些子问题，逐步逼近最优解。分枝定界法通常包括两个步骤：分枝和定界。分枝是指将问题分解为多个子问题，每个子问题都是原问题的一个可能解。定界是指通过对子问题的求解，确定上界和下界，从而缩小搜索范围。 4. 启发式算法：启发式算法是一种常用的求解整数规划问题的方法，它通过启发式规则和策略来指导搜索过程。启发式算法不保证找到最优解，但可以在较短时间内找到近似最优解。常见的启发式算法包括贪心算法、模拟退火算法、遗传算法等。
5. 接近最优策略：在实际问题中，有时求解整数规划问题的时间复杂度非常高，甚至是NP-hard难题。面对这种情况，可以采取接近最优的策略。即对于一个相对较大的整数规划问题，先求解一个近似最优解，然后逐步优化，以此来降低问题的复杂度。
6. 问题分解：对于大规模的整数规划问题，可以将问题分解成多个较小的子问题。通过对这些子问题的求解，可以逐步逼近整体问题的最优解。问题分解可以提高求解效率，同时可以充分利用问题的结构特点。
