《整数线性规划-数学建模与数学实验》由会员分享，可在线阅读，更多相关《整数线性规划-数学建模与数学实验（73页珍藏版）》请在金锄头文库上搜索。
1、整数整数线性规划线性规划数学建模与数学实验数学建模与数学实验实验目的实验目的实验内容实验内容2. 掌握用数学软件求解整数线性规划问题掌握用数学软件求解整数线性规划问题.1. 了解整数线性规划的根本内容了解整数线性规划的根本内容.2. 用数学软件包用数学软件包MATLAB求解整数线性规划问题求解整数线性规划问题.4. 实验作业实验作业. .3. 用数学软件包用数学软件包LINGO求解整数线性规划问题求解整数线性规划问题.1.整数线性规划整数线性规划整整 数数 规规 划划整数规划问题与模整数规划问题与模型型整数规划算法整数规划算法计算软件计算软件应用案例应用案例整数规划问整数规划问题题实例实例特点
2、特点模型分类模型分类例3 某储蓄所每天的营业时间为上午9：00到下午的17：00，根据经验，每天不同时间段所需要的效劳员的数量为：时间段9101011111212131314141515161617数量43465688储蓄所可以雇用全时和半时两类效劳员，全时的报酬是100元每天，中午必须在12：00到14：00之间休息1个小时；每天雇用不超过3名的半时效劳员，必须连续工作4小时，报酬为40元问：1该储蓄所应该如何雇用全时和半时两类效劳员？2如果不雇用半时效劳员，每天费用增加多少？3如果雇用半时效劳员的数量没有限制，可减少多少费用？X1，X2分别为全时效劳员在12：0013：00和13：0014
3、：00安排休息的人数，Y1，Y2，Y3，Y4，Y5，分别为9：00，10：00，11：00，12：00，13：00，开始工作的半时效劳人员 如果生产某一类型汽车，那么至少要生产如果生产某一类型汽车，那么至少要生产8080辆，辆， 那么最优的生产方案应作何改变？那么最优的生产方案应作何改变？例例 汽车厂生产方案汽车厂生产方案 汽车厂生产三种类型的汽车，各类型每辆车对钢材、汽车厂生产三种类型的汽车，各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。劳动时间的需求，利润及工厂每月的现有量。 小型小型 中型中型 大型大型 现有量现有量钢材（吨）钢材（吨） 1.5 3 5 600劳动时间（小时
4、）劳动时间（小时） 280 250 400 60000利润（万元）利润（万元） 2 3 4 制订月生产方案，使工厂的利润最大。制订月生产方案，使工厂的利润最大。设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1, x2, x3汽车厂生产方案汽车厂生产方案 模型建立模型建立 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4 线性线性规划规划模型模型(LP)模型模型求解求解 3 模型中增加条件：模型中增加条件：x1, x2, x3 均为整数，重新求解。均为整数，重新求解。 OBJ
5、ECTIVE FUNCTION VALUEVARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES结果为小数，结果为小数，怎么办？怎么办？1舍去小数：取舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与与LP最优值相差不大。最优值相差不大。2试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数值数值z，通过比较可能得到更优的解。，通过比较可能得到更优的解。 但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？IP可用可用LINDO直接求
6、解直接求解整数规划整数规划( (Integer Programming, ,简记简记IP) )“gin 3“gin 3表示表示“前前3 3个变个变量为整数，等价于：量为整数，等价于：gin x1gin x1gin x2gin x2gin x3 gin x3 IP 的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280x1+250x2+400x360000endgin 3 OBJECTIVE FUNCTION VALUEVARIABLE VALUE REDUCED COST X3 0.000000 -
7、4.000000 模型求解模型求解 IP 结果输出结果输出n特征特征变变量整数性要求量整数性要求n来源来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量的需要n性质性质可可行域是离散集合行域是离散集合线性整数规划模型线性整数规划模型一般整数规划模型一般整数规划模型0-1整数规划模型整数规划模型混合整数规划模型混合整数规划模型一般整数规划模一般整数规划模型型0-1整数规划模型整数规划模型混合整数规划模混合整数规划模型型算算 法法与线性规划的关与线性规划的关系系分支定界算法分支定界算法割平面算法割平面算法近似算法近似算法与线性规划的关与线性规划的关系系整数规划整数规划放松的线性
8、规划放松的线性规划可行解是放松问题的可行解可行解是放松问题的可行解最优值大于等于放松问题的最优值最优值大于等于放松问题的最优值注注 释释最优解不一定在顶点上到达最优解不一定在顶点上到达最优解不一定是放松问题最优解的邻近整最优解不一定是放松问题最优解的邻近整数解数解整数可行解远多余于顶点，枚举法不可取整数可行解远多余于顶点，枚举法不可取算法思想算法思想算法步骤算法步骤算例算例割平面算法割平面算法算算 法法 思思 想想由放松问题的可行由放松问题的可行域向整数规划的可域向整数规划的可行域逼近行域逼近方法方法利用超平面利用超平面切除切除要求要求 整数解保存整数解保存 放松问题最优值放松问题最优值增加增
9、加割平面生成方割平面生成方法法条件条件-保存整数解删除最优保存整数解删除最优解解整数可行解整数可行解最优基可行解最优基可行解正则解正则解算算 法法 步步 骤骤求放松问题的求放松问题的最优基可行解最优基可行解判断是否判断是否为整数解为整数解是停止是停止得到最优解得到最优解否否在单纯性表中加入在单纯性表中加入一列利用对偶单纯一列利用对偶单纯性算法求最优解性算法求最优解算算 例例(1,1.5)分支定界算分支定界算法法算法思想算法思想算法步骤算法步骤算例算例注释注释算算 法法 思思 想想隐枚举法隐枚举法求解放松问题求解放松问题最优值比界坏最优值比界坏 最优解为整数最优解为整数最优值比界好最优值比界好
10、最优解为非整最优解为非整数最优值比界好数最优值比界好分分 支支边边 界界分分 支支舍舍 弃弃分支的方法分支的方法定定 界界当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值那么替代整数解且目标值小于原有最好解的值那么替代原有最好解原有最好解整数解且目标值大于原有最好解的值那么整数解且目标值大于原有最好解的值那么 删除删除该分支其中无最优解该分支其中无最优解非整数解且目标值小于原有最好解的值那么继非整数解且目标值小于原有最好解的值那么继续分支续分支非整数解且目标值大于等于原有最好解的值那
11、非整数解且目标值大于等于原有最好解的值那么删除该分支其中无最优解么删除该分支其中无最优解选一分支写出并求解选一分支写出并求解放松问题，同时从分放松问题，同时从分支集中删除该分支支集中删除该分支判判定是否定是否为整数为整数解解初始分支为可行解初始分支为可行解集，初始界为无穷大集，初始界为无穷大判判定是否定是否分支集分支集空空是停止是停止当前最好解当前最好解为最优解为最优解是是否否判定最判定最优值是否优值是否小于小于当前界当前界判定最判定最优值是否优值是否小于小于当前界当前界是是否否按非整数变量分按非整数变量分支并加入分支集支并加入分支集否否是是以最优解替代当前最以最优解替代当前最好解最优值替代当
12、前界好解最优值替代当前界算算 例例注注 释释求解混合整数规划问题，只对整数变量分支，求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。对非整数变量不分支。对对0-1整数规划分支时整数规划分支时计计 算算 软软 件件Matlab没有提供专门的解整数线性规划的函数，我们可以根据分支定界法结合函数linprog来解决整数线性规划问题。例：例：分而治之分而治之MinMin在第二个区域 中继续继续上述的过程，我们可以结合matlab和分支定界法得到所求问题的答案，只需要改动vlb和vub。相对较为繁琐矛盾Min转向另一个区域转向另一个区域矛盾Min21Min17MinMin17整数变量定义整数
13、变量定义 LinDo 一般整数变量一般整数变量:GIN 0-1整数变量整数变量: INT LinGo 一般整数变量一般整数变量: GIN( variable_name); 0-1整数变量：整数变量：BIN( variable_name);算例算例算算 例例 max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2 +5 x3=2000endgin x1gin x3应用案例分应用案例分析析人力资源分配问题人力资源分配问题应急设施选址问题应急设施选址问题人力资源分配问题人力资源分配问题某个中型百货商场对售货人员周工某个
14、中型百货商场对售货人员周工资资200元的需求经统计如下表元的需求经统计如下表 为了保证销售人员充分休息，销售人为了保证销售人员充分休息，销售人员每周工作员每周工作5天，休息天，休息2天。问应如何天。问应如何安排销售人员的工作时间，使得所配安排销售人员的工作时间，使得所配售货人员的总费用最小？售货人员的总费用最小？星期星期一一二二三三四四五五六六七七人数人数12151214161819模型假模型假设设每天工作每天工作8小时，不考虑夜班的情小时，不考虑夜班的情况；况；每个人的休息时间为连续的两天时每个人的休息时间为连续的两天时间；间；每天安排的人员数不得低于需求量，每天安排的人员数不得低于需求量，
15、但可以超过需求量但可以超过需求量问题分问题分析析因素因素 不可变因素不可变因素：需求量、休息时间、单位费用；：需求量、休息时间、单位费用； 可变因素可变因素：安排的人数、每人工作的时间、总费用；：安排的人数、每人工作的时间、总费用；方案方案 确定每天工作的人数，由于连续休息确定每天工作的人数，由于连续休息2天，当确定每天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。求出每天工作的人数。变量变量 每天开始休息的人数每天开始
16、休息的人数 约束条件约束条件 1.每人休息时间每人休息时间2天，自然满足。天，自然满足。 3.变量非负约束：变量非负约束：目标函数目标函数：总费用最小，总费用与使用的总总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于天开始休息，所以总人数等于模模 型型注注 解解该问题本质上是个整数规划问题，该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数放松的线性规划的最优解是个整数解，所以两规划等价。解，所以两规划等价。定义整数变量用函数定义整数变量用函数gin(x1) gin(x7); 0-1整数变量为整数变量为
17、bin(x1)应急选址问应急选址问题题 某城市要在市区设置某城市要在市区设置k个应急效劳中心个应急效劳中心,经过初步筛选确定了经过初步筛选确定了m个备选地，现个备选地，现共有共有n个居民小区，各小区到个备选地个居民小区，各小区到个备选地的距离为的距离为 为了使为了使得各小区能及时得到应急效劳，要求得各小区能及时得到应急效劳，要求各小区到最近的效劳中心的距离尽可各小区到最近的效劳中心的距离尽可能的短，试给出中心选址方案。能的短，试给出中心选址方案。问题分析问题分析 该问题与传统的选址问题的该问题与传统的选址问题的主要区别主要区别在于其目标不再是要求费用最小，而在于其目标不再是要求费用最小，而是要
18、求最长距离最短。也就是离服务是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中中心距离最远的小区离最近的服务中心距离最小。心距离最小。 变量变量：当中心的位置确定下来后，各：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设真正的变量也就是小区的位置。设 问题分问题分析析 为了便于说明问题引入间接变量，第为了便于说明问题引入间接变量，第i小区是否由第小区是否由第j个中心服务个中心服务 以及最远的距离以及最远的距离 约束条件约束条件 小区服务约束小区服务约束问问 题题 分分 析析最远距离约束最远距离约束中心个数约束中心个数约束目标函数目标函数：最远距离：最远距离 最小最小模模 型型
