运筹整数规划素材教学提纲.ppt

《运筹整数规划素材教学提纲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹整数规划素材2021/10/22纯整数规划：在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。§1整数规划的有关概念及特点§1.1概念整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）2021/10/23求整数解的线性规划问题，不是用四舍五入法

2、或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例：求解下列整数规划：§1.2整数规划的求解特点2021/10/24分析：若当作一般线性规划求解，图解法的结果如下。1、非整数规划最优解显然不是整数规划的可行解。2、四舍五入后的结果也不是整数规划的可行解。3、可行解是阴影区域交叉点，可比较这些点对应的函数值，找出最优。2021/10/25§2应用举例§2.1逻辑变量在数学模型中的应用1、m个约束条件中只有k个起作用设有m个约束条件定义0-1整型变量：第i个约

3、束起作用第i个约束不起作用2021/10/26设M是任意大正数，则原约束中只有k个真正起作用的情况可表示为：2021/10/272、约束条件右端项是r个可能值中的一个则通过定义约束条件右端项不是bi约束条件右端项是bi可将上述条件表示为2021/10/283、两组条件中满足其中一组例如表示条件：若，则；否则时则通过定义第i组条件起作用，i=1，2第i组条件不起作用可将上述条件表示为其中：M是任意大正数2021/10/29定义4、表示含有固定费用的函数例如：表示产品的生产数量，其生产费用函数为：目标函数：其中是与产量无

4、关的生产准备费用则原问题可表示为2021/10/210§2.2应用举例例1东方大学计算机实验室聘用4名大学生（代号1,2,3,4）和2名研究生（代号5,6）值班。已知各学生从周一至周五每天可安排的值班时间及每人每小时报酬见下表所示。学生代号酬金(元/h)每天可安排的值班时间(h)周一周二周三周四周五110.060607210.00606339.94830549.855640510.830460611.3062442021/10/211实验室每天开放时间为8:00AM—10:00PM,共14小时。开放时间内需要有一名学

5、生值班。规定大学生每周值班时间是8—15小时，研究生是7—12小时，每次值班不小于2小时。又每名学生每周值班次数不得多于三次，每天值班人员中至少有一名研究生，每天值班人数不超过3人。试为该实验室安排一张人员值班表，使得总酬金支出为最少。解：设表示学生i在周j的值班时间。学生i在周j不值班学生i在周j值班表示学生i在周j的最多可值班时间。则目标函数：2021/10/212研究生值班7-12小时每周不超过3次每天不超过3人每天有一研究生值班不超过每人可安排的时间每天开放14小时大学生值班8-15小时约束条件2021/10

6、/213例2红星日用化工厂为发运产品，下一年度需要6种不同容积的包装箱，每种包装箱的需求量及生产一个的可变费用如下表所示。包装箱代号123456容积（m3）0.080.100.120.150.200.25需求量（个）500550700900450400可变费用（元/个）5.08.010.012.116.318.2由于生产不同容积包装箱时需进行专门的准备、下料等，生产每一种包装箱的固定费用都是1200元。又若某容积的包装箱数量不够时，可用比它大的代替。试问该厂应订做哪几种代号的包装箱各多少个，可使得费用最省？2021/

7、10/214解：设表示代号为j的包装箱的订做数量。不订j包装箱订j包装箱目标函数约束条件2021/10/2152021/10/216例3（固定成本问题）高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定

8、一个生产计划，使获得的利润为最大。2021/10/217解：设分别为小号容器、中号容器和大号容器的生产数量。建立如下的数学模型：资源小号容器中号容器大号容器金属板（吨）248劳动力（人月）234机器设备（台月）123不生产j型号容器生产j型号容器2021/10/2182021/10/219§3指派问题及匈牙利解法§3.1指派问题与模型m项任务分