运筹学-本科

null 管理运筹学 管理运筹学 主讲：谢先达 2010.09null联系方式 办公室：QL643 87313663 手机： 13600512360 邮箱： xxdhz@163.com 绪 论绪 论绪论绪论什么是运筹学？ 运筹学发展历史 运筹学主要内容 运筹学的基本特征与基本 绪论绪论什么是运筹学？ 定义：为决策机构在对其控制下业务活动进行决策 时，提供以数量化为基础的科学方法。 西蒙：管理就是决策 决策 定性管理者的判断和经验定量运筹学绪论绪论运筹学发展历史 古代运筹思想：田忌赛马、丁渭修皇宫 二战期间的Operational Research 研究成果被应用到生产、经济领域，且研究不断深 化，逐步形成“运筹学”绪论绪论绪论绪论运筹学的主要内容有哪些？线性 运输问题 整数规划 目标规划 动态规划 图与网络分析 网络计划 存储论 排队论 对策论 决策分析 预测 绪论绪论运筹学研究的基本特征 系统的整体观念 多学科的综合 模型方法的应用绪论绪论运筹学研究的基本方法 分析和表述问题 建立模型 求解模型和优化 测试模型及对模型进行必要的修正 建立对解的有效控制 方案的实施第一章：线性规划及单纯形法第一章：线性规划及单纯形法第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型 线性规划图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论 第一章：线性规划及单纯形法第一章：线性规划及单纯形法例题：某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需的设备台时及A、Ｂ两种原材料的消耗以及资源的限制如表所示 工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少单位产品Ⅰ 和产品Ⅱ才能获利最多？ 第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题的数学模型 目标函数： maxz=50x1+100x2 x1+x2≤300 2x1+x2≤400 x2≤250 x1≥0 ，x2 ≥ 0 概念：可行解、最优解、最优值 约束条件：非负约束：第一章：线性规划及单纯形法第一章：线性规划及单纯形法500万m3练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3支流，第一化工厂每天排放含有某种有害物质的工业污水2万m3 ，第二化工厂每天排放这种工业污水1.4万m3 。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自净化。根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本是1000元/万m3 。第二化工厂处理污水的的成本是800元/万m3 。现问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。200万m3工厂1工厂2第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题的数学模型 目标函数：minz=1000x1+800x2 约束条件： (2-x1)/500≤0.2% 〔0.8(2-x1) +(1.4-x2)〕/700≤ 0.2% x1 ≤2 x2≤1.4 非负约束： x1≥0 ，x2 ≥ 0第一章：线性规划及单纯形法线性规划的一般模式 目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn 约束条件：a11x1+a12x2+a13x3+…+a1nxn ≤(= ≥)b1 a21x1+a22x2+a23x3+…+a2nxn ≤(= ≥)b2 … … … … am1x1+am2x2+am3x3+…+amnxn ≤(= ≥)bn 非负性约束：x1 ≥0,x2 ≥0,…,xn ≥0第一章：线性规划及单纯形法第一章：线性规划及单纯形法解得： 最大利润：27500 X1=50 X2=250 代入得： 设备台时：300 原料A：350 原料B：250 概念：松弛变量 剩余变量第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划的标准型 maxZ=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn=b1 a21x1+a22x2+…+a2nxn=b2 … … … am1x1+am2x2+…+amnxn=bm xj ≥0 j=1,2,…,n第一章：线性规划及单纯形法标准型的四个标准：求最大值、约束条件为等式、bj ≥0. xj ≥0 第一章：线性规划及单纯形法化非标准形线性规划为标准形式 minz=x1+2x2+3x3 -2x1+x2+x3 ≤ 9 -3x1+x2+2x3 ≥ 400 4x1-2x2-3x3=-6 x1 ≤ 0,x2 ≥ 0, x3取值无约束 第一章：线性规划及单纯形法第一章：线性规划及单纯形法练习：将下面线性规划问题化为标准形式 minz=2x1-2x2+3x3 -x1+x2+x3 = 4 -2x1+x2-x3 ≤ 6 x1 ≤ 0,x2 ≥ 0, x3取值无约束 第一章：线性规划及单纯形法第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型 线性规划图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论 第一章：线性规划及单纯形法目标函数： maxz=50x1+100x2 约束条件： x1+x2≤300 2x1+x2≤400 x2≤250 非负约束： x1≥0 ，x2≥04002001001002003004003000x1x2第一章：线性规划及单纯形法2x1+x2=400x2=250x1+x2=300第一章：线性规划及单纯形法4002001001002003004003000x1x22x1+x2=400x2=250x1+x2=300第一章：线性规划及单纯形法可行域第一章：线性规划及单纯形法4002001001002003004003000x1x22x1+x2=400x2=250x1+x2=300Z=0=50x1+100x2Z=10000=50x1+100x2Z=20000=50x1+100x2Z=27500=50x1+100x2第一章：线性规划及单纯形法等值线第一章：线性规划及单纯形法线性规划问题解的几种情况 线性规划存在唯一最优解 线性规划存在有无穷多个最优解的情况 线性规划可能存在无界解 线性规划存在无可行解的情况第一章：线性规划及单纯形法第一章：线性规划及单纯形法练习： P43：1.1（1） （2）第一章：线性规划及单纯形法第一章：线性规划及单纯形法第一章：线性规划及单纯形法线性规划问题及其数学模型 线性规划图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论 基本概念：基本概念：可行解 最优解 基 基解 基可行解 可行基 第一章：线性规划及单纯形法解的几何意义解的几何意义例: 线性规划问题基本可行解的意义：第一章：线性规划及单纯形法解的几何意义解的几何意义第一章：线性规划及单纯形法解的几何意义解的几何意义 第一章：线性规划及单纯形法解的几何意义解的几何意义 第一章：线性规划及单纯形法解的几何意义解的几何意义 第一章：线性规划及单纯形法解的几何意义解的几何意义第一章：线性规划及单纯形法解的几何意义解的几何意义第一章：线性规划及单纯形法算法思路算法思路  求一个初始基本可行解   是 判断基本可行解是否最优 结 束   不是   求使目标得到改善的基本可行解   是否存在？ 如何得到？是否唯一？如何判断？如何改善？ 如何判断没有有限最优解？第一章：线性规划及单纯形法基 本 定 理基 本 定 理定理1 若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。 定理2 线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点 定理3 若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解，如果在几个顶点上都出现最优解，则这些顶点的每个凸组合上也达到最优。第一章：线性规划及单纯形法凸 集 的 概 念凸 集 的 概 念1、基本概念： 凸集——设K是n维欧氏空间的一个点 集，若任意两点X（1）∈K，X（2）∈K的 连线上的一切点： αX（1）+（1-α）X（2） ∈ K （0<α<1），则称K为凸集。第一章：线性规划及单纯形法凸 集 的 概 念凸 集 的 概 念凸组合——设X（1） ，X（2） ，…，X（k） 是n维欧氏空间中的K个点，若存在k个数μ1， μ2 ，…， μk ,满足0≤μi≤1, i=1,2, …,k； 则称X=μ1X（1）+μ2X（2）+…+μkX(k)为X（1）, ，X（2） ，…，X（k）的凸组合。 顶点——设K是凸集，XK；若K中不存在两个不同的点X（1）  K，X（2）  K 使 X=αX（1）+（1-α）X（2） （0<α<1） 则称X为K的一个顶点（也称为极点或角点）。 第一章：线性规划及单纯形法凸 集 的 概 念凸 集 的 概 念凸集凸集不是凸集第一章：线性规划及单纯形法表格单纯形法表格单纯形法基变量检验数基变量系数 右端常数 最小比值列 第一章：线性规划及单纯形法表格单纯形法表格单纯形法基变量检验数基变量系数 右端常数 最小比值列 第一章：线性规划及单纯形法表格单纯形法表格单纯形法第一章：线性规划及单纯形法表格单纯形法表格单纯形法第一章：线性规划及单纯形法表格单纯形法表格单纯形法第一章：线性规划及单纯形法1、人工变量法（大Ｍ法） 2、两阶段法1、人工变量法（大Ｍ法） 2、两阶段法第一章：线性规划及单纯形法单纯形法的进一步讨论：第一章：线性规划及单纯形法第一章：线性规划及单纯形法人工变量法 目标函数： maxz=-3x1+ x3 x1+x2+ x3 ≤4 -2x1+x2- x3 ≥1 3x2+ x3 =9 x1，x2，x3 ≥ 0 约束条件：第一章：线性规划及单纯形法第一章：线性规划及单纯形法化成标准形式： 目标函数： maxz=-3x1+ x3+0x4+0x5 x1+x2+ x3 +x4 =4 -2x1+x2- x3 -x5 =1 3x2+ x3 =9 x1，x2，x3 ,x4,x5≥ 0 约束条件：第一章：线性规划及单纯形法第一章：线性规划及单纯形法添加人工变量： 目标函数：maxz=-3x1+ x3+0x4+0x5-Mx6-Mx7 x1+x2+ x3 +x4 =4 -2x1+x2- x3 -x5 +x6 =1 3x2+ x3 + x7 =9 x1，x2，x3 ,x4,x5,x6,x7≥ 0 约束条件：nullnull第一章：线性规划及单纯形法第一章：线性规划及单纯形法两阶段法： 目标函数：minw=x6+x7 x1+x2+ x3 +x4 =4 -2x1+x2- x3 -x5 +x6 =1 3x2+ x3 + x7 =9 x1，x2，x3 ,x4,x5,x6,x7≥ 0 约束条件：null第一章：线性规划及单纯形法第一章：线性规划及单纯形法练习： 目标函数： minz=2x1+3x2 x1+x2 ≥ 350 x1≥125 2x1+ x2 ≤ 600 x1，x2≥ 0 约束条件：第一章：线性规划及单纯形法第一章：线性规划及单纯形法几种特殊情况的判别 1、无可行解 2、无界解 3、无穷多最优解 4、退化问题 第三章 运输问题第三章 运输问题例1：某公司从两个产地A1，A2将物品运往三个销地B1， B2，B3，各产地的产量、各销地的销量和各产地运往各销地 的每件物品的运费如表所示第三章 运输问题第三章 运输问题运输问题线性规划模型求解 例1：某公司从两个产地A1，A2将物品运往三个销地B1，B2， B3，各产地的产量、各销地的销量和各产地运往各销地的每 物品的运费如表所示 第三章 运输问题第三章 运输问题 minf=6x11+4x12+6x12+6x21+5x22+5x23 x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij≥(i=1,2;j=1,2,3)解：产销平衡问题： 总产量 = 总销量 设xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表。 第三章 运输问题第三章 运输问题一般运输模型：产销平衡 A1、 A2、…、 Am 表示某物资的m个产地； B1、B2、…、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： m n Min f =   cij xij i = 1 j = 1 n  xij = si i = 1,2,…,m j = 1 m  xij = dj j = 1,2,…,n i = 1 xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n) 第三章 运输问题第三章 运输问题运输问题计算机软件求解第三章 运输问题运输问题求解的表上作业法 按某种找出一个初始基可行解； 对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一步骤； 在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。第三章 运输问题第三章 运输问题图：运输问题求解思路图第三章 运输问题第三章 运输问题初始基本可行解的确定 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各 城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运 输费用最少的调运方案。 第三章 运输问题 有关信息表 有关信息表 450 200 150 100日销量（需求量） 250 75 65 80 乙 200 100 70 90 甲日产量（供应量） C B A 运距 城市 煤矿第三章 运输问题null西北角法 不是优先考虑具有最小单位运价的供销业务，而是优先 满足运输表中西北角（左上角）上空格的供销要求 null用西北角法确定初始调运方案 100100100 50 50200200null 得到初始调运方案为： x11=100，x12=100，x22=50，x23=200 最小元素法： 从运价最小的格开始，在格内的标上允许取得的最大 数。然后按运价从小到大顺序填数。若某行（列）的产 量（销量）已满足，则把该行（列）的其他格划去。如 此进行下去，直至得到一个基本可行解。null用最小元素法确定初始调运方案 150100100100100100100null 得到初始调运方案为： x11=100，x13=100，x22=150，x23=100 最优性检验 根据最小元素法或西北角法求得运输问题的初始基可行 解之后，按照表上作业法的第二步，下面需对这个解进 行最优性判别，看它是否为本运输问题的最优解. null以xij空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号； 那麽，该非基变量xij的检验数：现在，在用最小元素法确定例2初始调运方案的基础上，计算非基变量X12的检验数 ：闭回路法null初始调运方案中以X12(X21)为起点的闭回路null非基变量X12的检验数：非基变量X21的检验数：经济含义：在保持产销平衡的条件下，该非 基变量增加一个单位运量而成为基变量时目 标函数值的变化量。位势法位势法检验数公式： 分别表示前m个约束等式对应的对偶变量； 分别表示后n个约束等式对应的对偶变量。 初始调运方案对偶变量对应表 初始调运方案对偶变量对应表 null2、位势法 null在式中，令u1=0，则可解得v1=90，v3=100，u2=-25， v2=90，于是 σ12=c12-（u1+v2）=70-（0+90）=-20 σ21=c21-（u2+v1）=80-（-25+90）=15 与前面用闭回路法求得的结果相同。 null 在式中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是 σ12=c12-（u1+v2）=70-（0+90）=-20 σ21=c21-（u2+v1）=80-（-25+90）=15 与前面用闭回路法求得的结果相同。 null位势法计算非基变量xij检验数的公式 σij=cij-（ui+vj） 复习比较检验数计算的两种方法思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）null解的改进 如检验出初始解不是最优解，即某非基变量检验数为 负，说明将这个非基变量变为基变量时运费会下降。根 据表上作业法的第三步，需对初始方案进行改进。 null解的改进步骤为： 1．（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变量）为换入变量，找出它在运输表中的闭回路； 2．以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号； 3．在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量； 4．将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都减去这一数值，最终得出一个新的运输方案。 对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止null继续上例，因σ12=-20 ，画出以x12为起始变量的闭回路 null 计算调整量：ε=Min（100，150）=100。 按照下面的方法调整调运量： 闭回路上，奇数次顶点的调运量加上ε，偶数次顶点的调运量减去ε；闭回路之外的变量调运量不变。得到新的调运方案： null重复上面的步骤，直至求出最优调运方案：nullnull 结 果 最优调运方案是： x11=50，x12=150，x21=50，x23=200 相应的最小总运输费用为： Zmin=90×50+70×150+80×50+75×200 =34000 第三章 运输问题第三章 运输问题运输问题的进一步讨论：产销不平衡问题 产销不平衡时，可加入假想的产地（销大于产时）或销地 （产大于销时）。第三章 运输问题第三章 运输问题例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个 虚设的销地 运输费用为0 第三章 运输问题第三章 运输问题例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个 虚设的产地 运输费用为0 第三章 运输问题第三章 运输问题产销不平衡问题 石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活 用煤和取暖用煤3000 T，1000T，2000T，由河北临城、山西盂县两处煤矿负 责供应，这两处煤矿的价格相同，煤的质量也基本相同，两处煤矿能供应北 方研究院的煤的数量，山西盂县为4000T，河北临城为1500T，由煤矿至北方 研究院的单位运价（百元/T）如表所示。 由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满 足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。 第三章 运输问题第三章 运输问题解： 根据题意，作出产销平衡与运价表： 这里 M 代表一个很大的正数，其作用是强 迫相应的 x31、 x33、 x34取值为0。第三章 运输问题第三章 运输问题例设有三个化肥厂供应四个地区的农用化肥,假定等量的化 肥在这些地区使用效果相同,各化肥厂年产量、各地区年需求 及各化肥厂到各地区运送单位化肥的运价如表所示，试求出总 的运费最节省的的化肥调拨方案。第三章 运输问题第三章 运输问题解： 根据题意，作出产销平衡与运价表：最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与 最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对 应 4”的销量50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。 第三章 运输问题第三章 运输问题 求解结果如下：第三章 运输问题第三章 运输问题生产与储存问题 例:某厂按合同规定须于当年每个季度末分别提供10、15、25、 20台同一规格的柴油机。已知该厂各季度的生产能力及生产每 台柴油机的成本如下表。如果生产出来的柴油机当季不交货， 每台每积压一个季度需储存、维护等费用0.15万元。试求在完 成合同的情况下，使该厂全年生产总费用为最小的决策方案。 第三章 运输问题第三章 运输问题课堂练习：课堂练习：null几点说明 若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代中。通常取 中最小者对应的变量为换入变量； 当迭代到运输问题的最优解时，如果有某非基变量的检验数等于0，则说明该运输问题有多重最优解； 当运输问题某部分产地的产量和，与某部分销地的销量和相等时，在迭代过程中间有可能有某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个格中填入0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-1)个。第四章 目标规划第四章 目标规划目标规划问题举例目标规划问题举例例1．企业生产:不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。 例2．商务活动:企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。null例3．投资:企业投资时不仅仅要考虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确的期望值时，才能得到满意的决策。 例4．裁员:同样的，企业裁员时要考虑很多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。 例5．营销:营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。 目标规划的图解法目标规划的图解法 例6．一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1： 从上表可知，A股票的收益率为（3／20）×100％＝15％，股票B的 收益率为4／50×100％＝8％，A的收益率比B大，但同时A的风险也 比B大。这也符合高风险高收益的规律。试求一种投资方案，使得一 年的总投资风险不高于700，且投资收益不低于10000元。目标规划的图解法目标规划的图解法显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一 是确保收益。在求解之前，应首先考虑两个目标的优先权。假设第一个目 标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解 过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目 标。 建立模型： 设x1、x2分别表示投资商所购买的A股票和B股票的数量。 首先考虑资金总额的约束：总投资额不能高于90000元。即 20x1＋50x2≤90000。 目标规划的图解法目标规划的图解法约束条件 再来考虑风险约束：总风险不能超过700。投资的总风险为 0.5x1＋0.2x2。引入两个变量d1+和d1-,建立等式如下： 0.5x1 +0.2x2=700+d1+-d1- 其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的 部分，d1+≥0。 目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作 用是允许约束条件不被精确满足。null 把等式转换，可得到 0.5x1 +0.2x2-d1++d1-=700。 再来考虑年收入: 年收入=3x1+4x2 引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。 于是，第2个目标可以表示为 3x1+4x2-d2++d2-=10000。 null有优先权的目标函数 本问题中第一个目标的优先权比第二个目标大。即最重要的目标 是满足风险不超过700。分配给第一个目标较高的优先权P1,分配给第 二个目标较低的优先权P2。 针对每一个优先权，应当建立一个单一目标的线性规划模型。首 先建立具有最高优先权的目标的线性规划模型，求解；然后再按照优 先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原 来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值 作为一个新的约束条件加入到当前模型中，并求解。 null图解法 针对优先权最高的目标建立线性规划 建立线性规划模型如下： Min d1+ s.t. 20x1＋50x2≤90000 0.5x1 +0.2x2-d1++d1-=700 3x1+4x2-d2++d2-=10000 x1,x2,d1+,d1-≥0nullnull针对优先权次高的目标建立线性规划 优先权次高（P2）的目标是总收益超过10000。 建立线性规划如下： Min d2- s.t. 20x1＋50x2≤90000 0.5x1 +0.2x2-d1++d1-=700 3x1+4x2-d2++d2-=10000 d1+＝0 x1,x2,d1+,d1-,d2+,d2-≥0 nullnull目标规划的这种求解方法可以表述如下： 1．确定解的可行区域。 2．对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。 3．对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。 4. 重复第3步，直至所有优先权的目标求解完。 null目标规划模型的标准化 例6中对两个不同优先权的目标单独建立线性规划进行求解。为简 便，把它们用一个模型来表达，如下： Min P1（d1+）+P2（d2-） s.t. 20x1＋50x2≤90000 0.5x1 +0.2x2-d1++d1-=700 3x1+4x2-d2++d2-=10000 x1,x2,d1+,d1-,d2+,d2-≥0 复杂情况下的目标规划复杂情况下的目标规划例7．一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的2倍。 试求如何安排生产？ null 解：本问题中有3个不同优先权的目标，不妨用P1、P2、P3表 示从高至低的优先权。 对应P1有两个目标：每周总耗费人力资源不能低于600工 时,也不能超过680工时； 对应P2有一个目标：每周的利润超过70000元； 对应P3有两个目标：每周产品A和B的产量分别不低于200和120件。null采用简化模式，最终得到目标线性规划如下： Min P1(d1+)+ P1(d2－)+P2(d3-)+ P3(d4-)+ P3(2d5-) s.t. 2x1+3x2-d1++d1-=680 对应第1个目标 2x1+3x2-d2++d2-=600 对应第2个目标 250x1+125x2+d3--d3+＝70000 对应第3个目标 x1-d4++d4-=200 对应第4个目标 x2-d5++d5-=120 对应第5个目标 x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0null 使用运筹学软件求解可得： x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0； d4+=50；d4-=0；d5+=0；d5-=60，目标函数d4-+2d5- =120。 可见，目标1、目标3和目标4达到了，但目标2、目标5都有一些偏差。 加权目标规划加权目标规划加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过 量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总 的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加 权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的 要求，那么，整个问题都可以描述为一个线性规划的问题。 如果在例7中我们对每周总耗费的人力资源超过680工时或低于600工时 的每工时罚数权重定为7；每周利润低于70000元时，每元的罚数权重为 5；每周产品A产量低于200件时每件罚数权重为2，而每周产品B产量低 于120件时每件罚数权重为4。null则其目标函数化为： min7d1++7d2-+5d3-+2d4-+4d5- 这就变成了一个普通的单一目标的线性规划问题 min7d1++7d2-+5d3-+2d4-+4d5- s.t. 2x1+3x2-d1++d1-=680 2x1+3x2-d2-+d2+=680 250x1+125x2-d3-+d3+=70000 x1-d4++d4-=200 x2-d5++d5-=120 x1,x2,d1+,d1-,d2-,d2+, d3+,d3-,d4+,d4-,d5+,d5-≥0 。第五章 整数规划第五章 整数规划第五章 整数规划第五章 整数规划 在整数规划中，如果所有的变量都为非负整数，则称为 纯整数规划问题；如果有一部分变量为非负整数，则称之 为混合整数规划问题。在整数规划中，如果变量的取值 只限于0和1，这样的变量我们称之为0-1变量。在纯整数 规划和混合整数规划问题中，如果所有的变量都为0-1变 量，则称之为0-1规划。null整数规划的图解法 例:某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2 ≥ 0 为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法，整数规划的图解法整数规划的图解法得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。由图表可 看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。性质1：任何求最 大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相 应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混 合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数 值。null例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x1,x2,x3 ≥ 0 为整数例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x3 ≤1 x1,x2,x3 ≥ 0 x1，x3 为整数 x3为0-1变量用《管理运筹学》软件求解得： x1 = 5 x2 = 2 x3 = 2 用《管理运筹学》软件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.25 整数规划的计算机求解整数规划的应用整数规划的应用投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?null解：设：0--1变量xi = 1(Ai 点被选用）或0(Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xi ≥ 0 且xi 为0--1变量，i = 1,2,3,……,10null固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金 属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所 示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万 元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/ 月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小 号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计 划，使获得的利润为最大。 null解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的 这种性质，设 yi = 1(当生产第 i种容器, 即 xi ＞ 0 时) 或0（当不生 产第 i种容器即 xi = 0 时）。引入约束 xi ≤ M yi ，i =1，2，3， M充分大，以保证当 yi = 0时，xi= 0 。 这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3null指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人 特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人 去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任 务的总的效率最高，这就是指派问题。 例6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项 工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时 间为最少。 null解：引入0—1变量 xij，并令xij = 1(当指派第 i人去完成第j项工作 时)或0（当不指派第 i人去完成第j项工作时)．这可以表示为一个 0--1整数规划问题： Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0--1变量，i,j = 1,2,3,4 * * * 求解可用《管理运筹学》软件中整数规划方法。 null分布系统 例7．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了 扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、 500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量 以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂? null解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时) 或0（当Ak 没被选中时),k =2,3,4,5．这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+ 3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 其中前4项为固定投资额，后面的项为运输费用。 s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制) x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制) x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制) x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij ≥0，i = 1,2,3,4,5； j = 1,2,3， yk 为0--1变量，k =2,3,4,5。 * * * 求解可用《管理运筹学》软件中整数规划方法。 null投资问题 例8．某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资 金额为3万元，最高金额为5万元； 项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额 或为2万元或为4万元或为6万元或为8万元。 项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资 金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额， 使到第五年末拥有的资金本利总额为最大?null解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项 目A，B，C，D的投资额；设yiA， yiB，是0—1变量，并规定取 1 时分别表 示第 i 年给A、B投资，否则取 0（ i = 1, 2, 3, 4, 5）。 设yiC 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4； 第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年 投资C项目2万元时，取值1；第2年不投资C项目时，取值0； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第