《《管理系统优化》PPT幻灯片》由会员分享,可在线阅读,更多相关《《管理系统优化》PPT幻灯片(76页珍藏版)》请在金锄头文库上搜索。
1、10.1线性规划优化数学模型 10.2线性规划问题的基本概念 10.3用规划求解工具求解线性规划问题 10.4线性规划问题求解结果的分析,第10章 管理系统优化,在实际管理问题中,决策者经常面临以下类型的问题: 管理问题有一个数量化的,尽可能最大化或最小化的指标,称为目标函数。例如总成本最小化或者总利润最大化。 有许多因素和这个目标有关,而这些因素在一定范围内决策者是可以控制的,例如投资的规模,产品的产量等等。这些因素称为决策变量。 决策变量往往受到一些条件的制约,例如原材料供应量,市场销售量、生产设备能力、流动资金等。这些限制条件称为约束条件。 线性规划模型就是将决策变量、目标函数、约束条件
2、用线性函数的形式表示出来而形成的数学模型。,10.1 线性规划优化数学模型,一个工厂有车床、刨床、钻床和铣床四种设备。生产A、B、C、D、E五种产品。每种设备每天生产时间为8小时,每年工作日为250天。各种设备的台数、全年能力(可用工时),每种产品生产一件需要分别占用这四种设备的工时(单位:小时),五种产品可以获得的利润(单位:元/件)如下表所示。,生产计划问题,现在我们要确定这五种产品的生产数量,使得占用的设备工时不超过各种设备的能力,同时使总利润最大。 设四种产品的产量分别为x1、x2、x3、x4、x5,总利润为z,则线性规划数学模型为:,max z=123x1+94x2+105x3+13
3、2x4+118x5 s.t. 0.23x1+0.44x2+0.17x3+0.08x4+0.36x5 24000 0.13x1 +0.20 x3+0.37x4+0.19x5 22000 0.25x2+0.34x3 +0.18x5 16000 0.55x1+0.72x2 +0.61x4 12000 x1,x2,x3,x4,x50,利润最大化目标函数 车床能力约束 刨床能力约束 钻床能力约束 铣床能力约束 变量非负约束,其中,max表示最大化,s.t.表示subject to(约束)。,这个问题的最优解为: x1=0(件),x2=0(件),x3=18772.099(件),x4=19672.130(件
4、),x5=53430.480(件), 最大利润为z=10872588.307元。,由于上述数学模型中没有指明决策变量必须是整数,因此最优解中产品产量是连续变量,而不是整数。如果在约束条件中增加决策变量必须是整数的要求,则表达式变为:,max z=123x1+94x2+105x3+132x4+118x5 s.t. 0.23x1+0.44x2+0.17x3+0.08x4+0.36x5 24000 0.13x1 +0.20 x3+0.37x4+0.19x5 22000 0.25x2+0.34x3 +0.18x5 16000 0.55x1+0.72x2 +0.61x4 12000 x1,x2,x3,x
5、4,x50, x1,x2,x3,x4,x5为整数,决策变量必须取整数的问题称为整数规划问题。这个整数规划问题的最优解为: x1=0(件),x2=0(件),x3=18771(件) x4=19672(件), x5=53431(件)。 最大利润为z= 10872517(元)。,配料问题,化肥厂用四种原料A、B、C、D混合成复合肥料M。这四种原料的单价以及复合肥料M所要求的氮(N)、磷(P)、钾(K)的最低百分含量()如下表所示。,要求配1000吨复合肥料,并假定在配制过程中物料没有损耗。求使得总成本最低的配料方案。 设四种原料分别选取x1,x2,x3,x4吨,总成本为z,线性规划数学模型为:,min
6、 z=2200 x1+1800 x2+2400 x3+2700 x4总成本最小化 s.t. 0.30 x1+0.15x2 +0.15x4150 氮含量的下限约束 0.10 x1 +0.25x3+0.15x4150 磷含量的下限约束 0.20 x2+0.15x3+0.15x4100 钾含量的下限约束 x1+x2+x3+x4=1000 物料平衡约束 x1, x2, x3, x40 变量非负约束 这一类问题称为配料问题。这个问题的最优解为: x1=375(吨) x2=125(吨) x3=375(吨)x4=125(吨) 最低成本为z=2287500(元)。,背包问题,一艘货船最大装载重量为5000千克
7、,现有A、B、C、D、E、F六种货物待装运,每种货物单件的价值和重量如下表所示。,每种货物各装多少件,使得货船中货物的总价值最大? 设A、B、C、D、E、F六种货物各装x1、x2、x3、x4、x5、x6件,线性规划数学模型为:,max z=2.75x1+3.22x2+4.55x3+4.73x4+5.01x5+5.50 x6 总价值最大化 s.t. 320 x1+420 x2+530 x3+550 x4+590 x5+640 x65000 货船装载量约束 x1,x2,x3,x4,x5,x60 变量非负约束 x1,x2,x3,x4,x5,x6为整数 整数变量约束 而这一类整数规划问题称为背包问题。
8、这个货船装载问题的最优解为: x1=2(件)x2=0(件)x3=2(件) x4=6(件)x5=0(件)x6=0(件), 最大价值为z=42.98(万元)。,物流配送问题,某种产品从两个生产地A1、A2运往三个需求地B1、B2、B3。各生产地的生产量、各需求地的需求量、每个生产地到每个需求地每吨产品的运输价格如下表:,求总运费最低的配送方案。,这个问题称为供求平衡的物流配送问题。它的线性规划数学模型如下: min z=12x11+13x12+21x13+14x21+17x22+8x23总运费最低 s.t.x11+x12+x13=520生产地A1约束 x21+x22+x23 =480生产地A2约束
9、 x11 +x21 =100需求地B1约束 x12 +x22 =400需求地B2约束 x13 +x23 =400需求地B3约束 x11,x12,x13,x21,x22,x230,设从两个生产地到三个需求地的运量(吨)如下表:,这一类问题称为运输问题。运输问题有一个特点,只要供应量和需求量都是整数,那么最优解中的决策变量一定是整数,不必将决策定义成整数变量。这个问题的最优解如下表所示。,最小总运费为:z=10960元。,公司选择问题,一家控股公司要在下属的五家子公司中选择三家准备上市。这5家子公司的资产、负债和税后利润如下表所示。要求所选的三家子公司的总资产不低于10亿元,负债不超过5亿元,并使
10、得新组建的公司税后利润最大。,设5个01变量x1,x2,x3,x4,x5,我们将变量的取值全为0或1的线性规划问题称为0-1规划问题。这个0-1线性规划数学模型如下: max z=5400 x1+2300 x2+4600 x3+3300 x4+980 x5利润最大化目标函数 s.t.3.48x1+5.62x2+7.33x3+6.27x4+2.14x510资产约束 1.28x1+2.53x2+1.02x3+3.55x4+0.53x55负债约束 x1+x2+x3+x4+x5=3 所选公司数量约束 x1,x2,x3,x4,x50变量非负约束 x1,x2,x3,x4,x5为0-1变量0-1变量约束 这
11、个01规划问题的最优解为: x1=1,x2=1,x3=1,x4=0,x5=0,max z=12300(万元)。 即选择子公司A、B、C组建新公司,总资产可达16.43亿元,总负债为4.83亿元,符合指标要求。新组建公司的税后总利润可以达到1.23亿元。,有n项任务由n个人完成,每项任务交给一个人,每人都有一项任务。由i个人完成j项任务的成本(或效益)为cij。求使总成本最小(或总效益最大)的分配方案。 设:,指派问题(Assignment Problem),市政府有四项市政建设工程招标。经过初选,四家建设公司最后参与这四项工程竞标。每家公司对每个工程的报价如下表所示:,市政府规定,每项工程只能
12、有一家公司中标,每家公司只能承担一项工程。求总价最低的决标方案。设:,max =920 x11+480 x12+650 x13+340 x14+870 x21+510 x22+700 x23+350 x24+ 880 x31+500 x32+720 x33+400 x34+930 x41+490 x42+680 x43+410 x44 s.t. x11+x12+x13+x14=1 甲公司只能中标一项工程 x21+x22+x23+x24=1乙公司只能中标一项工程 x31+x32+x33+x34=1 丙公司只能中标一项工程 x41+x42+x43+x44=1 丁公司只能中标一项工程 x11+x21
13、+x31+x41=1 工程A只能由一家公司承接 x12+x22+x32+x42=1 工程B只能由一家公司承接 x13+x23+x33+x43=1 工程C只能由一家公司承接 x14+x24+x34+x44=1 工程D只能由一家公司承接 xij=0,10-1变量约束,最优解为:x13=1,x24=1,x31=1,x42=1,max z=2370 甲公司中标工程C,乙公司中标工程D,丙公司中标工程A,丁公司中标工程B,四个标总价为2370万元。,可以看出,每项工程并不是都由报价最低的公司中标。,min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn (, )
14、b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free),线性规划模型的目标函数必须是变量的线性函数,约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题:,10.2 线性规划问题的基本概念,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题:1、线性规划的最优解是否可能位于可行域的内部? 2、线性规划的最优解是否可能位于可行域的边界上?,线性规划的图解,凸集,凸集,不是凸集,
15、线性规划的可行域是凸集 线性规划如果有最优解,最优解至少在可行域的一个极点上,可行域的性质,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,线性规划可行域和最优解的几种情况,10.3 用规划求解工具求解线性规划问题,Excel规划求解工具 Excel规划求解报告 线性规划Excel规划求解模型,Excel中提供了一个求解线性和非线性规划的工具。打开菜单:工具/规划求解就可以启动这个工具。,Excel规划求解工具,如果菜单中没有“规划求解”,打开菜单:工具/加载宏,选定“规划求解”。,然后
16、就会在菜单:“工具”栏中出现“规划求解”。,在Excel工作表中输入有关线性规划模型的数据。,=SUMPRODUCT(B5:F5, $B$9:$F$9),=SUMPRODUCT(B4:F4,$B$9:$F$9),=SUMPRODUCT(B3:F3,$B$9:$F$9),=SUMPRODUCT(B2:F2,$B$9:$F$9),=SUMPRODUCT(B7:F7,$B$9:$F$9),打开Excel菜单:“工具规划求解”,出现“规划求解参数”对话窗口,如下图所示。,选择“目标单元格”选项为$B$11,“等于”选项为“最大值”,“可变单元格”选项为$B$9:$F$9。单击“添加”,得到“添加约束”对话窗口,如下图所示。