资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,第四章 数学规划模型,第1页,一、数学规划模型,1.,模型建立,问题1 某厂利用甲,乙,丙,丁四种设备生产A,B,C三种,产品,相关数据如表所表示.已知这三种产品单件利润,分别是4.5,5,7（百元）,试问该厂应怎样安排生产可获,得最大利润?,第2页,A,B,C,总工时,甲,2,2,4,800,乙,1,2,3,650,丙,4,2,3,850,丁,2,4,2,700,第3页,甲,乙,丙,丁,注意到变量 代表是产品产量,故有,抽去所给问题详细意义,我们得到原问题数学关系,为,第4页,分析,该问题关键所在是确定每种产品产量,为此以,表示三种产品产量,则目标为,在一个生产周期中,每种设备所提供工时为有限,故对四种设备而言还应该满足以下条件:,第5页,非负性,第6页,用Lingo软件能够得到对应问题解.开启Lingo,在窗,口下中输入以下程序:,保留完之后执行Lingo菜单下Solve命令,得到对应解.,第7页,Variable Value Reduced Cost,X1 85.71429 0.000000,X2 71.42857 0.000000,X3 121.4286 0.000000,Row Slack or Surplus Dual Price,1 1592.857 1.000000,2 0.000000 1.357143,3 57.14286 0.000000,4 0.000000 0.2142857,5 0.000000 0.4642857,第8页,问题2 某车间要制造100套钢筋架,每套需要长为2.9,2.1 1.5 钢筋各一根.已知原料钢筋长度为7.4,问怎样切割钢筋,使得钢筋利用率为最高?,分析 该问题关键点是怎样切割钢筋,使得每次切割之,后,剩下余料为最少?,假设在切割过程中,我们不考虑钢筋损耗,并考虑各,种切割方案:,第9页,方案,2.9,2.1,1.5,余料,1,1,0,3,0,2,2,0,1,0.1,3,0,2,2,0.2,4,1,2,0,0.3,5,0,1,3,0.8,第10页,非负性,第11页,从分析中能够看出,此问题关键是确定每种方案下,余料数.,设 表示第 种方案中使用原料钢,筋数,则余料数为,而对应限制条件为,第12页,故原问题数学关系式为,非负性,第13页,在Lingo下得到该问题解为,第14页,运行后得到该问题解为,X2 25.00000 0.000000,X3 0.000000 0.3666667,X4 25.00000 0.000000,X5 0.000000 1.283333,X1 25.00000 0.000000,第15页,线性规划模型普通可表示为,非负性,第16页,注 线性规划目标函数还能够用min来表示,表示,追求目标函数最小值.而 表示约束条件:,（Subject to）.,第17页,问题3 要从甲地调出物质吨,从乙地调出物质,1100吨,分别供给 地1700吨,地11吨,地200吨和,100吨,已知每吨运费如表所表示,试建立一个使运费到达,最小调拨计划.,单位旅程运费表,销地,15,37,51,51,乙,15,7,25,21,甲,D,C,B,A,产地,第18页,分析 设从第 个产地到第 个销地运输量为 运,输成本为 则问题目标函数为,因为从第一个产地调出物质总和为第一个产地产,量,即有,同理,有,第19页,对称地,对销地而言,相关系,由此得到该问题数学模型,第20页,第21页,注 该问题又称为运输问题.运输问题普通形式可写,成,其中 是第 个产地产量,是第 个销地需求量.,第22页,在上面关系中,有,对应运输问题称为产销平衡运输问题.若产销不平,衡,应该怎样处理?为何总是假定产销是平衡.,第23页,问题5 某企业准备派 个工人 去完成,项工作 已知第 个工人完成第 工作效,率为 求如此一个指派方案,使工人完成这些工作,效率为最大.,该问题可用一个网络图 来表示:其中 表,示顶点集,是边集,是权集.,该问题即是从 每一个顶点,找出唯一一条到 某一个,边,使得权之和为最大.,第24页,模型建立,若以 表示在顶点 存在边,不然,则目标函数可表示为,而从 每一个顶点 只能作一条边等价于,一样,连 惟一一条边等价于,第25页,由此得到对应数学模型为,第26页,这么规划又称为0-1规划.,注1 很多实际问题都能够转化成这么模型.比如游泳,接力队员选拔.,注2 当人数和工作数不相同时,这么问题应该怎样求,解,又当 时,而且允许一个人能完成两件工作,又该怎样处理?,第27页,二、模型求解,第28页,例1 一奶制品加工厂用牛奶生产 两种奶制品,1桶牛奶能够在设备甲上用12小时加工生产3千克 或,则在设备乙上用8小时加工成4千克 依据市场需要,生产 全部能售出,且每千克 赢利24元,每公,斤 可赢利16元.现在加工厂天天能得到50桶牛奶供,应,天天工人总劳动时间为480小时,而且设备甲天天,至多能加工100千克 设备乙加工能力没有限制.试,为该厂制订一个生产计划,使天天赢利最大,并深入,讨论以下3个附加问题:,第29页,若用35元能够买到1桶牛奶,应否作这项投资?若投,资,天天最多购置多少桶牛奶?,若能够聘用暂时工人以增加劳动时间,付给暂时工,人工资最多是每小时几元?,因为市场需求改变,每千克 利润增加到30元,应否改变生产计划?,第30页,解 设 表示这两种产品天天所消耗牛奶数量,（单位：桶）.则用于生产 牛奶可赢利,用于生产 牛奶可赢利 则目标函数为,限制条件分别为:,对原料限制:,劳动力限制,设备甲开工限制,第31页,由此得到对应规划模型,第32页,对每一约束条件,在第一象限中确定坐标点范围,最,终确定解范围可行域（多边形区域）;,模型求解,解法1 （图解法）,确定等值线（图中用虚线），则最优解为可行域与,等值线最终交点（即图中点 坐标）即为所求问,题最优解.,第33页,第34页,为此求解方程,轻易得到该方程解为,第35页,解法2 （单纯形方法）,原规划标准型为,第36页,第37页,第38页,解法3 （利用计算机软件）,在软件Lingo8下进行求解:,输入命令,第39页,Variable Value Reduced Cost,X1 20.00000 0.000000,X2 30.00000 0.000000,Row Slack or Surplus Dual Price,1 3360.000 1.000000,2 0.000000 48.00000,3 0.000000 2.000000,4 40.00000 0.000000,得到解为,第40页,Ranges in which the basis is unchanged:,Objective Coefficient Ranges,Current Allowable Allowable,Variable Coefficient Increase Decrease,X1 72.00000 24.00000 8.000000,X2 64.00000 8.000000 16.00000,Righthand Side Ranges,Row Current Allowable Allowable,RHS Increase Decrease,2 50.00000 10.00000 6.666667,3 480.0000 53.33333 80.00000,4 100.0000 INFINITY 40.00000,第41页,结果分析,三个约束条件右端视为“资源”:原料,劳动时间,设备甲加工能力.对当前解而言,前两种“消耗殆尽”，,而设备甲尚余40千克加工能力.,目标函数能够看作为是“效益”.成为紧约束资源,一旦增加,则“效益”必定增加.解中列出“对偶”价格表,示紧约束“资源”每增加一个单位后对应“效益”增加值.,第42页,原料每增加一个单位,利润可增加48个单位;而劳动时间,每增加一个单位,利润可增加2个单位.而非紧约束资源,增加,不会带来对应收益.这种“资源”潜在价值被,称为“影子”价格.,用“影子”价格即可回答附加问题.,用35元购置一桶牛奶,低于牛奶影子价格,故能够,做这项投资;暂时工人每小时工资不超出2元.而设,备甲还有富裕能力,故增加工时不会产生效益.,第43页,目标函数系数发生改变对最优解和最优值影响.,在图解法中能够看到，价值系数 对最优解会产,生一定影响.因为 确定了等值线斜率,原问题,等值线斜率为 ,当斜率上升到 则,最优解将会改变,此时最优解将在,点取得.,第44页,灵敏度分析还给出了各个系数范围:上界为24,下界为8,即当 时,最优,解不变;一样当 时,最优解不变.,从图中还能够看出,原,料（牛奶）增加,对应,是直线 向右,平移,此时最优解仍,为点 但当 与 重合,时,最优解将不再改变,第45页,此时,而由“影子”价格知:原料每增加一个,单位利润将增加48个单位.此时总利润为,一样,当劳动力资源,增加时,即直线 向,右移动时,最优解也,将改变,但当 两,点重合时,最优解将,不再改变.由“影子”,第46页,价格,劳动力每增加一个工时,效益增加2个单位.但劳,动力最多增加53个单位.,因设备甲仍有充裕工时,因而设备加工能力无需再,增加,其“影子”价格为零.,依据上面分析,能够回答原问题中提出相关问题.,能够同意用每桶35元价格再购置部分牛奶,但最,多再购置10桶;,能够以用低于每小时2元工资聘用暂时工人以增,第47页,劳动时间,但最多不得超出53小时.,第48页,例2 奶制品销售计划,例1给出 两种奶制品生产条件,利润及工厂,资源限制不变,为增加工厂赢利,开发了奶制品深,加工技术:用2小时和3元加工费,可将1千克 加工成,0.8高级奶制品 也可将一千克 加工成0.75千克高级,奶制品 每千克 能赢利44元,每千克 能赢利32元,试为该厂制订一个生产销售计划,使取得利润最大,并讨论以下问题:,第49页,若投资32元能够增加供给一桶牛奶,投资3元能够增,加一小时劳动时间,应否作这么投资,若天天投资150,元,可赚回多少?,每千克高级奶制品 赢利经常有10%波动,对指定计划有没有影响,若每千克 赢利下降10%,计,划应该改变吗?,第50页,问题分析,要求指定生产计划,关键是确定各产品产量,而目,标函数为销售这些产品之后可取得利润.,第51页,建立模型,设天天销售 千克 千克 千克 千克,用 千克 加工 千克 加工,目标函数,第52页,约束条件,原料供给 天天生产 千克,用牛奶,桶,天天生产 千克,用牛奶,桶,二者之和不超出50桶;,劳动时间 天天生产 时间分别为,加工 时间分别为 两,者之和不超出480小时;,设备能力 产量 不得超出设备甲天天,第53页,加工能力100千克;,非负约束,附加约束 1千克 加工成 千克 即,一样,由此得到模型,第54页,第55页,模型求解,用Lingo软件,进行求解,得,Variable Value Reduced Cost,X1 0.000000 1.680000,X2 168.0000 0.000000,X3 19.0 0.000000,X4 0.000000 0.000000,X5 24.00000 0.000000,X6 0.000000 1.50,第56页,Row Slack or Surplus Dual Price,1 3460.800 1.000000,2 0.000000 3.160000,3 0.000000 3.260000,4 76.00000 0.000000,5 0.000000 44.00000,6 0.000000 32.00000,Ranges in which the basis is unchanged:,Objective Coefficient Ranges Current Allowable,Variable Coefficient Increase Decrease,X1 24.00000 1.680000 INFINITY,第57页,X2 16.00000 8.150000 2.100000,X3 44.00000 19.75000 3.166667,X4 32.00000 2.026667 INFINITY,X5 -3.000000 15.80000 2.533333,X6 -3.000000 1.50 INFINITY,第58页,结果分析,由输出结果知,约束2和3“影子”价格分别是,和 即每增加一桶牛奶可使净利润增加,元,增加1小时劳动时间,可是利润增加 元,所以应该,投资 元增加一桶牛奶或投资3元增加一小时劳动时,间.若天天投资 元,增加供给5桶牛奶,可赢利,元,第59页,但约束2增加值最多不超出120,意味牛奶桶数最多,不超出10桶.,在灵敏度分析汇报中,目标函数系数改变范围分,别为,第60页,由此可见,当 价格向下波动 或 价格向,上波动 都会影响到最优解.,第61页,问题提出 钢铁、煤、水电等生产、生活物资从,若干供给点运输到一些需求点，怎样安排运输，使运费,为最小、或者利润为最大.某种类型货物因为需要装,箱,故要考虑怎样搭配使利用率到达最高,诸如这类,问题都牵涉到一些详细数学模型,这目讨论两个问题,并利用对应数学规划模型加以处理.,三、应用举例,第62页,题1 自来水输送问题,某市有甲、乙、丙、丁四个居民区,自来水由,三个水库供给,四个区天天必须得到确保基本用水量,分别为 千吨,但因为水源担心,三个水库,天天最多只能分别供给 吨自来水,并因为地,区位置差异,自来水企业从各水库向各区送水所需付,出引水管理费不一样（见表）,其它管理费用都是,千吨,依据企业要求,各区用户按统一标准 千吨,收费,另外,四个区都向企业申请了额外用水量,分,第63页,分别为天天 千吨,该企业应怎样分配供,水量,才能赢利最多?,管理费,甲,乙,丙,丁,A,160,130,220,170,B,140,130,190,150,C,190,200,230,/,第64页,为了增加供水量,自来水企业正在考虑进行水库改造,随三个水库供水量都提升一倍,问此时供水方案应如,何改变?企业利润可增加多少?,第65页,分析,问题关键是怎样安排从各个水库向四个居民区供水,使得引水管理费用到达最小,注意到其它费用与供水安,排无关.,第66页,模型建立,设决议变量为 三个水库 向甲、乙、,丙、丁 四个区供水量,设水库 向 区,日供水量为 并注意到 由条件得,因为需求量大于供水量,需求限制可表示为,第67页,第68页,在Lingo下得到问题解.,Variable Value Reduced Cost,X11 0.000000 30.00000,X12 50.00000 0.000000,X13 0.000000 50.00000,X14 0.000000 20.00000,X21 0.000000 10.00000,X22 50.00000 0.000000,X23 0.000000 20.00000,X24 10.00000 0.000000,X31 40.00000 0.000000,X32 0.000000 10.00000,X33 10.00000 0.000000,第69页,即:该问题解为,此时引水管理费为 元,利润为,元.,第70页,讨论,假如 三个水库天天最大供水量都增加一倍,则企业总供水能力为 千吨,水库供水量超出总需求,量,故此时需要计算三个水库向甲、乙、丙、丁四个区,供给每千吨水净利润，即有表2,第71页,净利润,甲,乙,丙,丁,A,290,320,230,280,B,310,320,260,300,C,260,250,220,/,从水库向各区送水净利润,第72页,由此得到目标函数为,约束条件为：,第73页,第74页,在Lingo下得到问题解：,Variable Value Reduced Cost,X11 0.000000 25.00000,X12 100.0000 0.000000,X13 0.000000 30.00000,X14 0.000000 20.00000,X21 0.000000 5.000000,X22 40.00000 0.000000,X23 30.00000 0.000000,X24 50.00000 0.000000,X31 80.00000 0.000000,X32 20.00000 0.000000,X33 0.000000 0.000000,第75页,Row Slack or Surplus Dual Price,1 93400.00 1.000000,2 0.000000 305.0000,3 0.000000 305.0000,4 0.000000 250.0000,5 0.000000 10.00000,6 0.000000 15.00000,7 0.000000 -45.00000,8 0.000000 -5.000000,第76页,题2 货机装运问题,问题 某种货机有三个货舱:前舱、中舱、后舱.三,个货舱所能装载货物最大重量和体积都有限制,如,表所表示,而且为了保持飞机平衡,三个货舱中实际装载,货物重量必须与其最大允许重量成正比.,前舱,中舱,后舱,重量限制,10,16,8,体积,6800,8700,5300,第77页,现有四种货物供该货机此次飞行装运,相关信息如表,最终一列表示装运后取得利润.,重量,体积,利润,货物1,18,480,3100,货物2,15,650,3800,货物3,23,580,3500,货物,12,390,2850,第78页,假设,1.每种货物能够进行任意分割;,2.每种货物能够在一个或多个货舱中任意分布;,3.每种货物能够混装,并确保不留空隙.,第79页,应怎样安排装运,使该货机此次装运利润最大?,第80页,模型建立,决议变量 表示第 种物资装入第 个货舱重量,货,舱 分别表示前、中、后舱.,目标函数表示一次运输后总利润,即有,约束条件有以下:,第81页,总重量约束,三个货舱重量限制,第82页,三个货舱空间限制,平衡限制,第83页,模型求解.,在Lingo下,可得到模型解为:,Variable Value Reduced Cost,X11 0.000000 400.0000,X12 0.000000 57.89474,X13 0.000000 400.0000,X21 7.000000 0.000000,X22 0.000000 239.4737,X23 8.000000 0.000000,X31 3.000000 0.000000,第84页,Variable Value Reduced Cost,X32 12.94737 0.000000,X33 0.000000 0.000000,X41 0.000000 650.0000,X42 3.052632 0.000000,X43 0.000000 650.0000,最大利润为,第85页,题3 汽车生产问题,一汽车厂生产小、中、大三种类型汽车,已知各类,型每辆车对钢材、劳动时间需求,利润以及每个月工厂,劳动时间现有量入表所表示,试指定月生产计划,使工,厂每个月利润最大.,小型,中型,大型,现有量,钢材,1.5,3,5,600,劳动时间,280,250,400,60000,利润,2,3,4,第86页,模型建立,设每个月生产小、中、大型汽车数量分别为,工厂月利润为 假定在生产周期中,各项指标不变,则有对应线性规划:,第87页,模型求解,该问题整数解为,第88页,讨论,若增加附加条件:每种汽车假如生产话,则最少生产,80辆,则生产计划应该做怎样修改?,分析:依据条件,对决议变量限制改为以下几个:,第89页,对得到每一个解进行讨论,最终确定最大值解.,最优解为,第90页,注 在Lingo下,求整数解命令为 变量名,方法二 用 规划,在问题中,引入待定常数 其中 为任意正数,（在详细问题中能够确定）,第91页,Global optimal solution found at iteration:31,Objective value:610.0000,Variable Value Reduced Cost,X1 80.00000 -2.000000,X2 150.0000 -3.000000,X3 0.000000 -4.000000,Y1 1.000000 0.000000,Y2 1.000000 0.000000,Y3 0.000000 0.000000,第92页,题4 原料采购与加工,问题 某企业用两种原油（和 ）混合加工成两种,汽油（甲和乙）,甲、乙两种汽油含原油A最低百分比分,别为 每吨售价分别为 元和 元,该企业还有原油 和 库存量分别为 吨和,吨,另外还能够从市场上买到不超出 吨原油,原油 市场价为:购置不超出 吨时单价为,吨,购置量超出 吨但不超出 吨时,超,过部分 吨,超出 吨部分,吨.该公,第93页,司应怎样安排原油采购和加工?,第94页,问题分析,企业安排原油采购和加工,其目标是为了取得最大,利润,但问题困难之处于于原油 采购价与采购量,关系比较复杂.,第95页,模型建立,设原油购置量为 则由题意,购置成本函数为,但这么函数过于复杂,为了是问题尽可能简单,我,们引入多个变量来刻画:,第96页,分别以 表示以 吨,吨,吨采购得到,原油 采购量,则当以 吨价格采购到原油,时,总有 故对应条件可表示为,一样,当以价格 吨价格购置到了 吨原油 时,有,另外,变量 还应满足,第97页,假设:用于生产甲、乙两种汽油原油 数量分别,为 用于生产甲、乙两种汽油原油 数量分,别为 则总收入为,而成本函数 可表示为,约束条件为,第98页,以及非负限制,总结上面分析,得到对应模型为,第99页,第100页,模型求解,利用Lingo,得到问题解为,Variable Value Reduced Cost,X11 500.0000 0.000000,X21 500.0000 0.000000,X12 0.000000 0.2666667,X22 0.000000 0.000000,X1 0.000000 0.4000000,X2 0.000000 0.000000,X3 0.000000 0.000000,第101页,解法二:采取 规划,令 分别表示以 吨、吨、,吨,则约束条件可转化为,第102页,用Lingo软件得到问题解为,Variable Value Reduced Cost,X11 0.000000 0.000000,X21 0.000000 1.400000,X12 1500.000 0.000000,X22 1000.000 0.000000,X1 500.0000 0.000000,X2 500.0000 0.000000,X3 0.000000 0.000000,Y1 1.000000 0.000000,Y2 1.000000 .000,Y3 1.000000 1000.000,第103页,即问题解为,第104页,题5 接力队选拔,问题提出:在实际工作中,经常会碰到下面问题:,有若干项工作要分配给一些人去完成.在分配过程,中,要尽可能发挥每个人优点,以取得最大效益.这,样问题就称为指派问题.经过下面例子我们来说,明怎样求解这么指派问题.,第105页,问题,某班准备从5名游泳队员中选拔4人组成一个接力队,参加学校 混合泳接力赛.5名队员4种泳姿,成绩如表所表示,问应该怎样选拔?,第106页,甲,乙,丙,丁,戊,蝶泳,仰泳,蛙泳,自由泳,5名队员4种泳姿百米最好成绩,第107页,问题分析,处理该问题关键,是从5名队员中选出4名队员,组,成接力队,每名队员完成一个泳姿,且4人泳姿各不相,同,但使总成绩为最好.一个方法是穷举法,但这种方,法当 较大时是不可接收.我们用 规划来解,决这个问题.,第108页,以 表示5名队员,表示4种,泳姿,以 表示第 名队员游第 种泳姿最好成,绩,则有,第109页,66.8,57.2,78,70,67.4,75.6,66,67.8,74.2,71,87,66.4,84.6,69.6,83.8,58.6,53,59.4,57.2,62.4,第110页,引入 变量 若选择队员 去参加泳姿 比赛,则记 其它情况,记 且应该满足以下约,束条件:,1.每人最多只能入选4种泳姿之一，即,2.每种泳姿必须有一人也只能有一人入选，即,第111页,当队员 选泳姿 时，对应 表示他成绩,不然 所以,即为所求求目标函数.从而该问题规划模型为,第112页,第113页,用Lingo软件求解该问题.,该问题解为,第114页,第115页,题6 选课策略,某学校要求，运筹学专业学生毕业时最少学习过两,门数学课，三门运筹学课和两门计算机课，这些课程,编号、名称、学分、所属类别和先修课要求如表所表示，,那么毕业时学生最少能够学习这些课程中哪些课程？,假如某个学生既希望选修课程数量少，又希望所获,得学分多，他能够选修哪些课程？,第116页,编号,名称,学分,类别,先修课程号,1,微积分,5,数学,2,线性代数,4,数学,3,最优化方法,4,数学,运筹学,1,2,4,数据结构,3,数学,计算机,7,5,应用统计,4,数学,运筹学,1,2,6,计算机模拟,3,计算机,运筹学,7,7,计算机编程,2,计算机,第117页,编号,名称,学分,类别,先修课程号,8,预测理论,2,运筹学,5,9,数学试验,3,运筹学,计算机,1,2,第118页,模型建立,设 表示选修课表中按编号次序9门课程（,表示不选这门课程,）则问题目标为选修,课程为最少,即,约束条件有,1.最少选修两门数学课,三门运筹学课和两门计算机课,即,第119页,另外,一些课程有先选要求,比如对最优化方法,而言,必须先选微积分和线性代数线性代数.即,应该满足 从而得到约束条件关系,一样,对其它选修课程先选关系也可得到对应约束,条件,整理后得到,第120页,由此得到对应规划为,第121页,第122页,在Lingo下面对问题进行求解,得到解为,若在考虑选修课时到达最小同时,还希望所得到,学分到达最大,则增加目标函数,第123页,为此引入目标函数向量 最终得到目标函,数,不过得到问题解发觉选修课程门数多于6门而达,到7门,假如所考虑问题是优先门数话,则再增加限,制条件,第124页,则得到问题解为,而此时对应学分为,第125页,题7 销售代理开发与中止,问题 某企业正在考虑在某城市开发一些销售代理业,务.经过预测,该企业已经确定了该城市未来5年业务,量,分别为 该企业已经初步,物色了4家销售企业作为其代理候选企业,下表给出了该,企业与每个候选企业代理关系一次性费用,以及每个,应该与哪些候选企业建立代理关系?,第126页,代理1,代理2,代理3,代理4,最大业务量,350,250,300,200,一次性费用,100,80,90,70,年运行费用,7.5,4.0,6.5,3.0,第127页,假如该企业当前已经和上述4个代理建立了代理关系,而且都处于运行状态,但每年初能够决定暂时中止或重,新恢复代理关系,每次暂时中止或恢复代理关系费用,以下表所表示,该企业应怎样对这些代理进行业务调整?,代理1,代理2,代理3,代理4,中止费用,5,3,4,2,恢复费用,5,4,1,9,第128页,模型建立,首先考虑问题前半部分:以 表示企业在第,年与企业 首次建立代理关系（则表示不建立代理关,系）.,目标函数为这5年中总费用,则总费用为建立代理,关系一次性费用及每年运行费用,其中建立代理关,系一次性费用为,第129页,因为第一问中没有说明是否能够暂时中止代理关系,故,假定代理关系一旦建立,该关系将维持下去,所以对候选,代理1而言,5年总运行费用为,于是对全部候选代理人而言,5年总运行费用为,约束条件,第130页,由此得到问题目标函数为,第131页,约束条件为:企业业务量必须由足够代理负担,即,有,（第一年业务量）,类似，对第二年业务量，有,由此得到问题数学模型为,第132页,第133页,第134页,第135页,得到问题解为 其余变量为零,此,意味 企业在第一年初与代理1,2建立代理关系,并在以后,保持代理关系,第四年与代理4建立代理关系.最小费用,为 元.,第136页,深入地,若建立关系之后能够中止关系,中止关系,之后也可恢复关系,试在其它假设不变情况下,求出,问题最优解.,第137页,模型建立,依然以 表示在第 年企业与候选代理人 在年,初建立代理关系,但注意到在年初公式能够暂时决定公,司能够决定解除或恢复代理关系,故以 表示企业,在第 年初企业与代理人 中止代理业务,而 则表,示在第 年年初企业与代理人 恢复代理人业务,则,对应目标函数为,第138页,第139页,中止与恢复代理关系约束表现为,注意到期初时,企业与全部代理人都有代理关系,即,又恢复关系能够表现为 即,有,第140页,第141页,题8 饮料厂生产与检修计划,问题 某饮料厂生产一个饮料以满足市场需要.该厂,销售科依据市场预测,已经确定了未来四面该饮料厂,需求量,计划科依据本厂实际情况给出了未来四面生,产能力和生产成本,对应数据由下表所表示,每七天当饮料,满足需求后有剩下时,要支出存放费,为每七天每千箱饮,料 千元,问应怎样安排生产,在满足市场需要前,提下,使四面总费用为最小.,第142页,周次,需求量,生产能力,成本,1,15,30,5,2,25,40,5.1,3,35,45,5.4,4,25,20,5.5,累计,100,135,第143页,分析,从表中数据中能够看出,除了第四面外,其余各周,生产能力都大于每七天需求量,即能够满足市场需,要.假如第一周,第二周按需生产,第三周多生产5千箱,以填补第四面不足部分,能够使总存放费用为最小,但注意到,生产成本逐月上升,因而从总成本最小角度,出发考虑问题,前几周多生产一些,可能是更加好方案.,第144页,模型假设,设饮料厂在第一周开始时没有库存,而且假设在第四,周周末也没有库存,周末有库存时需支付一周存放,费.,第145页,模型建立,以 表示四面产量,表示,周末库存量,则成本为,对第一周而言,产量减去库存,即为当月需求量,即,平行有其它约束条件,由此得规划为,第146页,第147页,在Lingo下对该问题进行求解,轻易得到该问题解,为:,最优解值为,第148页,讨论,假如工厂要安排一次设备检修,检修将占用当周15千,箱生产能力,但会使检修以后每七天生产能力提升5,千箱,试确定检修时间安排.,第149页,分析,问题关键是确定检修时间安排.为此引入 变,量 若 则表示检修,放在第 周进行,注意到此时该周生产能力将降低15,千箱,而以后各周生产能力将增加5箱,因而要增加相,应约束条件:,第150页,又检修只能进行一次,故还应该满足,第151页,联合起来,得到原问题数学规划为,第152页,第153页,在Lingo下,能够得到问题解为,即检修安排在第一周,最优解值为,第154页,题9 饮料生产批量问题,问题 某饮料厂使用同一条生产线轮番生产各种饮料,以满足市场需要.假如某周开工生产其中一个原料,就,要清洗设备和更换部分部件,于是需支出生产准备费.,现在只考虑一个饮料生产,假设其未来四面需求量,生产能力,生产成本与存放费与上题相同,问怎样安排,这种饮料生产,使该种饮料总费用为最小?,第155页,周次,需求量,生产能力,成本,1,15,30,5,2,25,40,5.1,3,35,45,5.4,4,25,20,5.5,累计,100,135,第156页,分析,与上例相比,处理该问题关键是要考虑与产品数量,无关生产准备费用.条件是:只要生产,就有该费用产,生.,第157页,模型建立,首先我们对问题做普通讨论:,将问题分为若干个阶段,用 来表示.对时段 以,表示需求量,生产能力为 假如在时段 开工,则需支,付准备费用 时段 末库存为 单件存放费为,产量为 为成本,引入 变量,表示该产品在该时段投入生产,不然不投入生产,则目,标函数为,第158页,对应关系为,第159页,带回原来问题值,得到问题模型为,第160页,第161页,在Lingo下,得到问题最优解为,第162页,题10 钢管下料问题,问题 某钢管零售商从钢管厂进货,将钢管按客户,要求进行切割后售出,从钢管厂进货时长度都是19,现有一客户需要50根4 29根6 和15根8 钢筋,应怎样下料?,零售商假如采取不一样切割模式太多,将会造成生产,过程复杂化,从而增加生产和管理成本,所以该零售商,要求采取不一样切割模式不能超出3种,另外,该客户除,第163页,需要上面三种钢管外,还需要10根5 长钢筋,应如,何下料?,第164页,分析 首先确定哪些方案是可行,为此讨论以下方,案,方案,4m,6m,8m,余料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,第165页,方案,4m,6m,8m,余料,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,所谓一个适当切割方案,应该满足两点:第一方案,可行,第二切割后剩下余料应该小于最小用料单位4,所以适当切割方案只有这上述7种.,第166页,模型建立,由前面分析,不难得到对应模型为,第167页,在Lingo下,得到问题解为,其余,此时用料27根,余料27,假如余料无用,我们能够考虑另外一个模式,即要求用,料最少,此时模型为,第168页,第169页,此时最优解为,其余,此时余料为35,第170页,现在来看第二个问题,在增加一个品种条件下,要,求切割方案总数不超出3种,今用整数非线性规划方法加,以求解.,设 为第 种方案下使用原料数,第 种方案下产生,4 5 6 8 钢管数分别为,则问题模型为,第171页,第172页,第173页,得到问题最优解为,第174页,第175页,题11,某储蓄所天天营业时间为早晨9点到下午5点.依据,经验,天天不一样时间所需要服务员数量为:,时间段,910,1011,1112,121,数量,4,3,4,6,时间段,12,23,34,45,数量,5,6,8,8,第176页,储蓄所能够雇佣全时和半时两类服务员.全时服务员每,天酬劳100元,从早晨9点到下午5点工作,但中午12点到,下午2点之间必须安排1小时午餐时间.储蓄所天天可,以不超出3名半时服务员,每个半时服务员必须连续,工作4小时,酬劳40元,问该储蓄所该怎样雇佣全时和半,时服务员?假如不能雇佣半时服务员,天天最少增加多,少费用,假如雇佣半时服务员数量没有限制,天天能够,降低多少费用?,第177页,分析,处理此问题关键是确定聘用全时服务员及半时服务,员人数,但还要考虑全时服务员有吃午餐时间,故把,全时服务员分为两类:午餐时间为12时至下午1时及下,午1时至下午2时;而半时服务员按上班时间进行划分.,第178页,模型建立,设 为午餐时间为下午12时全时服务员人数,为午餐时间为下午1时全时服务员人数,而 分别,表示从9点,10点,11点,1点开始上班半时服务员,人数,则目标函数为,约束条件按各个小时需要服务员人数确定,则有,第179页,第180页,另外,对半时服务员人数限制,对决议变量限制为,为整数.,由上述分析,得到对应数学模型为,第181页,第182页,为整数.,第183页,模型求解,在Lingo下得到问题解:,若不能雇佣半时服务员,则最优解为,因而多支出 元.,若对半时服务员人数没有限制,则最优解为,第184页,节约开支 元.,第185页,四、几个惯用线性规划介绍,问题1 生产组织与计划问题,工厂用 种设备 生产 种产品,在一个生产周期内,已知第 台设备 只能工作 个,机时.工厂必须完成产品 最少 件.设备 生产 所,需要机时和成本分别为 试建立对应数学模型,使设备能在计划周期内完成计划但又使成本到达最低.,第186页,模型为,第187页,问题2 工厂选址问题,设有 个需求点（城市,仓库,商店等）,有 个可供,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
