管理系统优化PPT课件

1、在实际管理问题中，决策者经常面临以下类型的问题：n 管理问题有一个数量化的，尽可能最大化或最小化的指标，称为目标函数。例如总成本最小化或者总利润最大化。n 有许多因素和这个目标有关，而这些因素在一定范围内决策者是可以控制的，例如投资的规模，产品的产量等等。这些因素称为决策变量。n 决策变量往往受到一些条件的制约，例如原材料供应量，市场销售量、生产设备能力、流动资金等。这些限制条件称为约束条件。线性规划模型就是将决策变量、目标函数、约束条件用线性函数的形式表示出来而形成的数学模型。10.1 线性规划优化数学模型第1页/共75页一个工厂有车床、刨床、钻床和铣床四种设备。生产A、B、C、D、E五种产

2、品。每种设备每天生产时间为8小时，每年工作日为250天。各种设备的台数、全年能力（可用工时），每种产品生产一件需要分别占用这四种设备的工时（单位：小时），五种产品可以获得的利润（单位：元/件）如下表所示。生产计划问题设备类型设备台数产品A产品B产品C产品D产品E设备能力（小时）车床120.230.440.170.080.3612825024000刨床110.130.200.370.1911825022000钻床80.250.340.188825016000铣床60.550.720.616825012000产品利润（元/件）12394105132118第2页/共75页现在我们要确定这五种产品的生

3、产数量，使得占用的设备工时不超过各种设备的能力，同时使总利润最大。设四种产品的产量分别为x1、x2、x3、x4、x5，总利润为z，则线性规划数学模型为：max z=123x1+94x2+105x3+132x4+118x5s.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利润最大化目标函数车床能力约束刨床能力约束钻床能力约束铣床能力约束变量非负

4、约束其中，max表示最大化，s.t.表示subject to（约束）。第3页/共75页这个问题的最优解为：x1=0（件），x2=0（件），x3=18772.099（件），x4=19672.130（件），x5=53430.480（件），最大利润为z=10872588.307元。第4页/共75页由于上述数学模型中没有指明决策变量必须是整数，因此最优解中产品产量是连续变量，而不是整数。如果在约束条件中增加决策变量必须是整数的要求，则表达式变为：max z=123x1+94x2+105x3+132x4+118x5s.t. 0.23x1+0.44x2+0.17x3+0.08x4+0.36x5 24000

5、 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， x1，x2，x3，x4，x5为整数第5页/共75页决策变量必须取整数的问题称为整数规划问题。这个整数规划问题的最优解为：x1=0（件），x2=0（件），x3=18771（件）x4=19672（件）， x5=53431（件）。最大利润为z= 10872517（元）。第6页/共75页配料问题化肥厂用四种原料A、B、C、D混合成复合肥料M。这四种原料的单价以及复合肥料M所要求的氮（N

6、）、磷（P）、钾（K）的最低百分含量（）如下表所示。百分含量（%)ABCDM氮N301501515磷P100251515钾K020151510单价（元/吨）2200180024002700要求配1000吨复合肥料，并假定在配制过程中物料没有损耗。求使得总成本最低的配料方案。设四种原料分别选取x1，x2，x3，x4吨，总成本为z，线性规划数学模型为：第7页/共75页min 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 磷含量的下限约束

7、 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（元）。第8页/共75页背包问题一艘货船最大装载重量为5000千克，现有A、B、C、D、E、F六种货物待装运，每种货物单件的价值和重量如下表所示。物货ABCDEF价值（万元/件）2.753.224.554.735.015.50重量（千克/件）320420530550590640每种货物各装

8、多少件，使得货船中货物的总价值最大？设A、B、C、D、E、F六种货物各装x1、x2、x3、x4、x5、x6件，线性规划数学模型为：第9页/共75页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为整数 整数变量约束而这一类整数规划问题称为背包问题。这个货船装载问题的最优解为：x1=2（件）x2=0（件）x3=2（件）x4=6（件）x

9、5=0（件）x6=0（件），最大价值为z=42.98（万元）。第10页/共75页物流配送问题某种产品从两个生产地A1、A2运往三个需求地B1、B2、B3。各生产地的生产量、各需求地的需求量、每个生产地到每个需求地每吨产品的运输价格如下表：运价（元/吨）B1B2B3生产量（吨）A1121321520A214178480需求量（吨）2004004001000求总运费最低的配送方案。第11页/共75页这个问题称为供求平衡的物流配送问题。它的线性规划数学模型如下：min z=12x11+13x12+21x13+14x21+17x22+8x23总运费最低s.t.x11+x12+x13=520生产地A1约

10、束 x21+x22+x23 =480生产地A2约束x11 +x21 =100需求地B1约束 x12 +x22 =400需求地B2约束 x13 +x23 =400需求地B3约束x11，x12，x13，x21，x22，x230运量（吨）B1B2B3生产量（吨）A1x11x12x13520A2x21x22x23480需求量（吨）2004004001000设从两个生产地到三个需求地的运量（吨）如下表：第12页/共75页这一类问题称为运输问题。运输问题有一个特点，只要供应量和需求量都是整数，那么最优解中的决策变量一定是整数，不必将决策定义成整数变量。这个问题的最优解如下表所示。运量（吨）B1B2B3生产

11、量（吨）A11204000520A2800400480需求量（吨）2004004001500最小总运费为：z=10960元。第13页/共75页公司选择问题一家控股公司要在下属的五家子公司中选择三家准备上市。这5家子公司的资产、负债和税后利润如下表所示。要求所选的三家子公司的总资产不低于10亿元，负债不超过5亿元，并使得新组建的公司税后利润最大。子公司ABCDE资产（亿元）3.485.627.336.272.14负债（亿元）1.282.531.023.550.53税后利润（万元）5400230046003300980设5个01变量x1，x2，x3，x4，x5）（选择子公司不选子公司5 , 4 ,

12、 3 , 2 , 110iiixi第14页/共75页我们将变量的取值全为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变量约束这个01规划问题的最优解为：x

13、1=1，x2=1，x3=1，x4=0，x5=0，max z=12300（万元）。即选择子公司A、B、C组建新公司，总资产可达16.43亿元，总负债为4.83亿元，符合指标要求。新组建公司的税后总利润可以达到1.23亿元。第15页/共75页有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：项任务个人被指派完成第第项任务个人不从事第第ji1ji0 xij1 , 0 xn,.,2 , 1i1xn,.,2 , 1j1x. t . sxczmax(min)ijn1jijn1iijn1in1jijij指

14、派问题（Assignment Problem）第16页/共75页市政府有四项市政建设工程招标。经过初选，四家建设公司最后参与这四项工程竞标。每家公司对每个工程的报价如下表所示：报价（万元）工程A工程B工程C工程D甲公司920480650340乙公司870510700350丙公司880500720400丁公司930490680410市政府规定，每项工程只能有一家公司中标，每家公司只能承担一项工程。求总价最低的决标方案。设：jijixij承接工程公司不承接工程公司10第17页/共75页max =920 x11+480 x12+650 x13+340 x14+870 x21+510 x22+700

15、x23+350 x24+ 880 x31+500 x32+720 x33+400 x34+930 x41+490 x42+680 x43+410 x44s.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

16、+x34+x44=1 工程D只能由一家公司承接 xij=0,10-1变量约束决策变量工程A工程B工程C工程D甲公司x11x12x13x14乙公司x21x22x23x24丙公司x31x32x33x34丁公司x41x42x43x44第18页/共75页最优解为：x13=1，x24=1，x31=1，x42=1，max z=2370甲公司中标工程C，乙公司中标工程D，丙公司中标工程A，丁公司中标工程B，四个标总价为2370万元。中标工程A工程B工程C工程D甲公司0010乙公司0001丙公司1000丁公司0100报价工程A工程B工程C工程D甲公司920480650340乙公司870510700350丙公司

17、880500720400丁公司930490680410可以看出，每项工程并不是都由报价最低的公司中标。第19页/共75页min(max) z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：0 x,x,x9x4+x+x8xx+x+x2. t . sxx2+x3=zmin3213211321212110

18、.2 线性规划问题的基本概念第20页/共75页max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3 -2 -1 0 x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？线性规划的图解第21页/共75页凸集凸集不是凸集n 线性规划的可行域是凸集n 线性规划如果有最优解，最优解至少在可行域的一个极点上可行域的性质第22页/共75页1、可行域封闭 唯一最优解2、可行域封闭 多个最优解3、可行域开

19、放 唯一最优解4、可行域开放 多个最优解5、可行域开放 目标函数无界6、无可行解线性规划可行域和最优解的几种情况第23页/共75页10.3 用规划求解工具求解线性规划问题nExcel规划求解工具nExcel规划求解报告n线性规划Excel规划求解模型第24页/共75页 Excel中提供了一个求解线性和非线性规划的工具。打开菜单：工具/规划求解就可以启动这个工具。Excel规划求解工具第25页/共75页如果菜单中没有“规划求解”，打开菜单：工具/加载宏，选定“规划求解”。第26页/共75页然后就会在菜单：“工具”栏中出现“规划求解”。第27页/共75页在Excel工作表中输入有关线性规划模型的数

20、据。=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菜单：“工具规划求解”，出现“规划求解参数”对话窗口，如下图所示。第28页/共75页选择“目标单元格”选项为$B$11，“等于”选项为“最大值”，“可变单元格”选项为$B$9:$F$9。单击“添加”，得到“添加约束”对话窗口，如下图所示。第29页/共75页添加车床“占用能力”=“设备能力”约束。左边

21、框选择车床“占用能力”G2，中间下拉框选择“添加约束”中直接引用。例如，本例中“车床能力”约束条件的左边车床“占用能力”的表达式：“B2*$B$9+C2*$C$9+D2*$D$9+E2*$E$9+F2*$F$9”必须事先写入单元格G2中，以便在添加约束时直接引用它。第31页/共75页车床能力约束添加完毕后，单击“添加”，出现新的“添加约束”对话窗口，如下图所示。添加刨床“占用能力”=“设备能力”约束。单击“添加”，又出现新的“添加约束”对话窗口，如下图所示。第32页/共75页添加钻床“占用能力”=“设备能力”约束。单击“添加”，写入最后一个约束，如下图所示。添加铣床“占用能力”=“设备能力”约

22、束，添加约束完成。单击“确定”，返回“规划求解”参数对话窗口，如下图所示。第33页/共75页单击“选项”，进入“规划求解选项”对话窗口，如下图所示。第34页/共75页选定“采用线性模型”和“假定非负”两项，其他选项保持默认值。单击“确定”结束“规划求解选项”对话窗口，返回“规划求解参数”对话窗口，如下图所示。第35页/共75页单击“求解”，开始求解线性规划问题。求解完毕以后，出现“规划求解结果”对话窗口，如下图所示。如果线性规划问题没有可行解（即可行域为空集）或者目标函数无界，在窗口中会出现相应的提示。如果求出了最优解，在Excel表中变量相应的单元格和目标函数相应的单元格就会出现最优解的值，

23、并出现如下的窗口。如下图所示。第36页/共75页选定“保存规划求解结果”，变量相应的单元格和目标函数相应的单元格的值就会保存下来。如果选择“恢复为原值”，变量相应的单元格和目标函数相应的单元格的值就会恢复为0。根据需要，选定“报告”中的若干项。单击“确定”，就完成了线性规划求解的所有步骤。图10.18是生产计划问题的最优解。第37页/共75页Excel除了线性规划模型的工作表“Sheet1”以外，还出现了“运算结果报告”、“敏感性报告”和“极限值报告”三个新的工作表。这三个工作表的内容将在下一节介绍。由上图还可以看到，五种产品产量的数值并不是整数，这是由于在模型中没有定义变量为整数的约束。如果

24、变量必须是整数，需要添加约束如下图所示。第38页/共75页在左边框“单元格引用位置”中选定B9：F9变量单元格的位置，中间下拉框中选定“int”（整数integer的缩写），右边框的“约束值”就会自动出现“整数”。单击“确定”，返回“规划求解参数”对话窗口，如下图所示。第39页/共75页可以看到，在“约束”框中增加了“$B$9：$F$9整数”这一约束。单击“确定”，重新开始求解。求解完毕，出现 “规划求解结果”对话窗口，如下图所示。第40页/共75页选定“保存规划求解结果”以及三个报告，单击“确定”，出现以下Microsoft Excel消息窗口，如下图所示。单击“确定”，得到以下的整数规划最

25、优解，如下图所示。第41页/共75页第42页/共75页配料问题优化的Excel模型= SUMPRODUCT(B4:E4,B8:E8)= SUMPRODUCT(B3:E3,B8:E8)=SUMPRODUCT(B2:E2,B8:E8)= SUMPRODUCT(B6:E6,B8:E8)=SUM(B8:E8)第43页/共75页设置配料问题的规划求解参数，如下图所示。第44页/共75页配料问题的最优解第45页/共75页背包问题优化的Excel模型=SUMPRODUCT(B2:G2,B5:G5)=SUMPRODUCT(B3:G3,B5:G5)第46页/共75页设置背包问题的规划求解参数，如下图所示。第47

26、页/共75页背包问题的最优解第48页/共75页运输问题优化的Excel模型=SUM(B7:D7)=SUM(B8:D8)=SUM(B7:B8)=SUM(C7:C8)=SUM(D7:D8)=SUMPRODUCT(B2:D3,B7:D8)第49页/共75页设置物流配送问题的规划求解参数，如下图所示。第50页/共75页运输问题的最优解第51页/共75页公司选择问题的Excel模型=SUMPRODUCT(B3:F3,B6:F6)=SUMPRODUCT(B2:F2,B6:F6)=SUMPRODUCT(B4:F4,B6:F6)=SUM(B6:F6)第52页/共75页设置公司选择问题的规划求解参数，如下图所示

27、。第53页/共75页公司选择问题的最优解第54页/共75页指派问题的Excel模型=SUM(B8:E8)=SUM(B9:E9)=SUM(B10:E10)=SUM(B11:E11)=SUM(B8:B11)=SUM(E8:E11)=SUMPRODUCT(B2:E5,B8:E11)=SUM(D8:D11)=SUM(C8:C11)第55页/共75页设置指派问题的规划求解参数，如下图所示。第56页/共75页指派问题的最优解第57页/共75页产生分析报告。选定“保存规划求解结果”，单击“报告”文本框中“运算结果报告”、“敏感性报告”和“极限值报告”，单击“确定”，生成三张相应的Excel工作表。如下图所示

28、。10.4 线性规划问题求解结果的分析第58页/共75页其中，“运算结果报告”如下图：第59页/共75页极限值报告如下图第60页/共75页敏感性报告如下图第61页/共75页x1x2z=5x1+2x2目标函数系数的灵敏度分析第62页/共75页x1x2z=5x1+2x2z=4x1+2x2z=3x1+2x2z=2x1+2x2目标函数系数的灵敏度分析第63页/共75页规划求解分析报告（1）生产计划问题产品1产品2产品3产品4产品5资源限量资源A1.02.03.02.04000资源B2.02.03.01.04.02000资源C1.02.02.02.01800资源D4.03.05.03.02400利润32

29、31553270max z=32x1+31x2+55x3+32x4+70 x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+3x2+5x3 +3x52400 x1，x2，x3，x4，x50第64页/共75页规划求解分析报告（2）Excel模型第65页/共75页规划求解分析报告（3）运算结果报告第66页/共75页规划求解分析报告（4）敏感性报告第67页/共75页规划求解分析报告（5）极限值报告第68页/共75页规划求解分析报告中有关的术语（1）资源的影子价格n 资源的影子价格：资源每增加一个单位，利润的增量。n 资源的影子价格就是资源的边际利润。n 凡是最优解时影子价格大于0的资源，最优解时没有剩余。n 凡是最优解时影子价格大于0的资源，最优解时资源是紧缺的，影子价格越大，资源越紧缺。第69