运筹学基础及应用第4章-整数规划与分配问题
56页1、,目,录,CONTENTS,在很多场合,我们建立最优化模型时,实际问题要求决策变量只能取整数值而非连续取值。此时,这类最优化模型就称为整数规划(离散最优化)模型。,整数规划的求解往往比线性规划求解困难得多,而且,一般来说不能简单地将相应的线性规划的解取整来获得。,整数规划的特点及应用,整数规划的特点及应用,整数规划(简称:IP) 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划,则称该整数规划为整数线性规划。,整数线性规划数学模型的一般形式:,整数规划的特点及应用,整数线性规划问题的种类:,纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划。 混合整数线性规划:决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划:决策变量只能取值0或1的整数线性规划。,整数规划的特点及应用,整数规划的典型例子,例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求,故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地
2、有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij,见下表:,工厂A3或A4开工后,每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用最少。,整数规划的特点及应用,解:这是一个物资运输问题,特点是事先不能确定应该建A3还是A4中哪一个,因而不知道新厂投产后的实际生产物资。为此,引入0-1变量:,再设xij为由Ai运往Bj的物资数量,单位为千吨;z表示总费用,单位万元。 则该规划问题的数学模型可以表示为:,整数规划的特点及应用,混合整数规划问题,整数规划的特点及应用,例4.2 现有资金总额为B。可供选择的投资项目有n个,项目j所需投资额和预期收益分别为aj和cj(j1,2,n),此外由于种种原因,有三个附加条件: 若选择项目1,就必须同时选择项目2。反之不一定; 项目3和4中至少选择一个; 项目5,6,7中恰好选择2个。 应该怎样选择投资项目,才能使总预期收益最大。,整数规划的特点及应用,解:对每个投资项目都有被选择和不被选择两种可能,因此分别用0和1表示,令xj表示第j个项目的决策选择
3、,记为:,投资问题可以表示为:,整数规划的特点及应用,整数规划问题解的特征:,整数规划问题的可行解集合是它松弛问题可行解集合的一个子集,任意两个可行解的凸组合不一定满足整数约束条件,因而不一定仍为可行解。 整数规划问题的可行解一定是它的松弛问题的可行解(反之不一定),但其最优解的目标函数值不会优于后者最优解的目标函数值。,整数规划的特点及应用,例4.3 设整数规划问题如下,首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。,整数规划的特点及应用,用图解法求出最优解为:x13/2, x2 = 10/3,且有Z = 29/6,现求整数解(最优解):如用舍入取整法可得到4个点即(1,3),(2,3),(1,4),(2,4)。显然,它们都不可能是整数规划的最优解。,x1,x2,3,3,(3/2,10/3),按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如右图所示。其中(2,2),(3,1)点的目标函数值最大,即为Z=4。,整数规划的特点及应用,整数规划问题的求解方法:,匈牙利法(指派问题) 分支定界法和割平面法,指派问题,一、
4、指派问题的数学模型的标准形式:,设n 个人被分配去做n 件工作,规定每个人只做一件工作,每件工作只有一个人去做。已知第i个人去做第j 件工作的效率( 时间或费用)为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率( 时间或费用)最高?,设决策变量,指派问题的数学模型为:,指派问题,克尼格定理 : 如果从分配问题效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui,从每一列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵bij,则以bij为效率矩阵的分配问题与以aij为效率矩阵的分配问题具有相同的最优解。,指派问题,二、匈牙利法,指派问题的匈牙利法求解步骤:,1) 变换指派问题的系数矩阵(cij)为(bij),使在(bij)的各行各列中都出现0元素,即 从(cij)的每行元素都减去该行的最小元素; 再从所得新系数矩阵的每列元素中减去该列的最小元素。,2) 进行试指派,以寻求最优解。 在(bij)中找尽可能多的独立0元素,若能找出n个独立0元素,就以这n个独立0元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。,指派问题,找独立0元素
《运筹学基础及应用第4章-整数规划与分配问题》由会员龙***分享,可在线阅读,更多相关《运筹学基础及应用第4章-整数规划与分配问题》请在金锄头文库上搜索。
一号教学楼一层地面修缮工程竞争性磋商文件
新能源高端设备制造示范项目(一期)施工图设计服务招标文件正文
新丰镇农村公路大中修-新北线(一期南段)招标文件正文
长信科技:长信科技拟发行股份及支付现金购买资产涉及的芜湖长信新型显示器件有限公司股东全部权益价值项目资产评估报告
山东科技大学城市轨道交通调度系统考核装置采购项目竞争性磋商
山东墨龙:寿光宝隆石油器材有限公司评估报告
浙商中拓:三维企业评估报告
大丰区乡村振兴(农村公路大中修工程)——三裕线招标文件招标文件正文
恒辉安防:最近三年的财务报告及其审计报告以及最近一期的财务报告
浙商中拓:三维企业审计报告
唯万密封:上海唯万密封科技股份有限公司拟现金购买上海嘉诺密封技术有限公司股权所涉及的上海嘉诺密封技术有限公司股东全部权益价值资产评估报告
顺控发展:佛山市顺合环保有限公司模拟审计报告
唯万密封:上海嘉诺密封技术有限公司审计报告
琏升科技:眉山琏升光伏科技有限公司2023年1-7月审计报告
天娱数科:山西聚为科技有限公司审计报告
顺威股份:江苏骏伟精密部件科技股份有限公司模拟审计报告
山东墨龙:威海市宝隆石油专材有限公司评估报告
顺威股份:广州顺威新能源汽车有限公司拟股权收购涉及江苏骏伟精密部件科技股份有限公司模拟股东全部权益价值资产评估报告
盈峰环境:佛山市顺合环保有限公司模拟审计报告
领益智造:最近三年的财务报告及其审计报告以及最近一期的财务报告
2023-11-15 30页
2023-11-16 31页
2023-11-16 38页
2023-11-15 33页
2023-11-15 36页
2023-04-17 12页
2023-04-17 13页
2023-04-17 13页
2023-04-17 19页
2023-04-17 14页