10.1 线性规划优化数学模型10.2 线性规划问题的基本概念10.3 用规划求解工具求解线性规划问题10.4 线性规划问题求解结果的分析第第10章章 管理系统优化管理系统优化在实际管理问题中，决策者经常面临以下类型的问题：n管理问题有一个数量化的，尽可能最大化或最小化的指标，称为目标函数。例如总成本最小化或者总利润最大化。n有许多因素和这个目标有关，而这些因素在一定范围内决策者是可以控制的，例如投资的规模，产品的产量等等。这些因素称为决策变量。n决策变量往往受到一些条件的制约，例如原材料供应量，市场销售量、生产设备能力、流动资金等。这些限制条件称为约束条件。线性规划模型就是将决策变量、目标函数、约束条件用线性函数的形式表示出来而形成的数学模型。10.1 线性规划优化数学模型一个工厂有车床、刨床、钻床和铣床四种设备。生产A、B、C、D、E五种产品。每种设备每天生产时间为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现在我们要确定这五种产品的生产数量，使得占用的设备工时不超过各种设备的能力，同时使总利润最大。设四种产品的产量分别为x1、x2、x3、x4、x5，总利润为z，则线性规划数学模型为：max z=123x1+94x2+105x3+132x4+118x512345 240001345 22000235 16000124 12000 x1，x2，x3，x4，x50利润最大化目标函数车床能力约束刨床能力约束钻床能力约束铣床能力约束变量非负约束其中，max表示最大化，s.t.表示subject to（约束）。这个问题的最优解为：x1=0（件），x2=0（件），x3（件），x4（件），x5（件），最大利润为元。由于上述数学模型中没有指明决策变量必须是整数，因此最优解中产品产量是连续变量，而不是整数。如果在约束条件中增加决策变量必须是整数的要求，则表达式变为：max z=123x1+94x2+105x3+132x4+118x512345 240001345 22000235 16000124 12000 x1，x2，x3，x4，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）的最低百分含量（）如下表所示。百分含量（%)ABCDM氮N301501515磷P100251515钾K020151510单价（元/吨）2200180024002700要求配1000吨复合肥料，并假定在配制过程中物料没有损耗。求使得总成本最低的配料方案。设四种原料分别选取x1，x2，x3，x4吨，总成本为z，线性规划数学模型为：min z=2200x1+1800x2+2400x3+2700x4总成本最小化124150 氮含量的下限约束 14150 磷含量的下限约束 234100 钾含量的下限约束 x1+x2+x3+x4=1000 物料平衡约束 x1, x2, x3, x40 变量非负约束这一类问题称为配料问题。这个问题的最优解为：x1=375（吨） x2=125（吨） x3=375（吨）x4=125（吨）最低成本为z=2287500（元）。背包问题一艘货船最大装载重量为5000千克，现有A、B、C、D、E、F六种货物待装运，每种货物单件的价值和重量如下表所示。物货ABCDEF价值（万元/件）2.753.224.554.735.015.50重量（千克/件）320420530550590640每种货物各装多少件，使得货船中货物的总价值最大？设A、B、C、D、E、F六种货物各装x1、x2、x3、x4、x5、x6件，线性规划数学模型为：123456 总价值最大化s.t. 320x1+420x2+530x3+550x4+590x5+640x65000 货船装载量约束 x1，x2，x3，x4，x5，x60 变量非负约束 x1，x2，x3，x4，x5，x6为整数 整数变量约束而这一类整数规划问题称为背包问题。这个货船装载问题的最优解为：x1=2（件）x2=0（件）x3=2（件）x4=6（件）x5=0（件）x6=0（件），最大价值为（万元）。物流配送问题某种产品从两个生产地A1、A2运往三个需求地B1、B2、B3。各生产地的生产量、各需求地的需求量、每个生产地到每个需求地每吨产品的运输价格如下表：运价（元/吨）B1B2B3生产量（吨）A1121321520A214178480需求量（吨）2004004001000求总运费最低的配送方案。这个问题称为供求平衡的物流配送问题。它的线性规划数学模型如下：min z=12x11+13x12+21x13+14x21+17x22+8x23总运费最低s.t.x11+x12+x13=520生产地A1约束 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设从两个生产地到三个需求地的运量（吨）如下表：这一类问题称为运输问题。运输问题有一个特点，只要供应量和需求量都是整数，那么最优解中的决策变量一定是整数，不必将决策定义成整数变量。这个问题的最优解如下表所示。运量（吨）B1B2B3生产量（吨）A11204000520A2800400480需求量（吨）2004004001500最小总运费为：z=10960元。公司选择问题一家控股公司要在下属的五家子公司中选择三家准备上市。这5家子公司的资产、负债和税后利润如下表所示。要求所选的三家子公司的总资产不低于10亿元，负债不超过5亿元，并使得新组建的公司税后利润最大。子公司ABCDE资产（亿元）3.485.627.336.272.14负债（亿元）1.282.531.023.550.53税后利润（万元）5400230046003300980设5个01变量x1，x2，x3，x4，x5我们将变量的取值全为0或1的线性规划问题称为0-1规划问题。这个0-1线性规划数学模型如下：max z=5400x1+2300x2+4600x3+3300x4+980x5利润最大化目标函数1234510资产约束 123455负债约束 x1+x2+x3+x4+x5=3 所选公司数量约束 x1,x2,x3,x4,x50变量非负约束 x1，x2，x3，x4，x5为0-1变量0-1变量约束这个01规划问题的最优解为：x1=1，x2=1，x3=1，x4=0，x5=0，max z=12300（万元）。即选择子公司A、B、C组建新公司，总资产可达亿元，总负债为亿元，符合指标要求。新组建公司的税后总利润可以达到亿元。有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：指派问题（Assignment Problem）市政府有四项市政建设工程招标。经过初选，四家建设公司最后参与这四项工程竞标。每家公司对每个工程的报价如下表所示：报价（万元）工程A工程B工程C工程D甲公司920480650340乙公司870510700350丙公司880500720400丁公司930490680410市政府规定，每项工程只能有一家公司中标，每家公司只能承担一项工程。求总价最低的决标方案。设：max =920x11+480x12+650x13+340x14+870x21+510x22+700x23+350x24+ 880x31+500x32+720x33+400x34+930x41+490x42+680x43+410x44s.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,10-1变量约束决策变量工程A工程B工程C工程D甲公司x11x12x13x14乙公司x21x22x23x24丙公司x31x32x33x34丁公司x41x42x43x44最优解为：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丙公司880500720400丁公司930490680410可以看出，每项工程并不是都由报价最低的公司中标。min(max) z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：10.2 线性规划问题的基本概念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 0x1x2z=6z=3z=9z=12问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？线性规划的图解凸集凸集不是凸集n线性规划的可行域是凸集n线性规划如果有最优解，最优解至少在可行域的一个极点上可行域的性质1、可行域封闭 唯一最优解2、可行域封闭 多个最优解3、可行域开放 唯一最优解4、可行域开放 多个最优解5、可行域开放 目标函数无界6、无可行解线性规划可行域和最优解的几种情况10.3 用规划求解工具求解线性规划问题nExcel规划求解工具nExcel规划求解报告n线性规划Excel规划求解模型Excel中提供了一个求解线性和非线性规划的工具。打开菜单：工具/规划求解就可以启动这个工具。Excel规划求解工具如果菜单中没有“规划求解”，打开菜单：工具/加载宏，选定“规划求解”。然后就会在菜单：“工具”栏中出现“规划求解”。在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。单击“添加”，得到“添加约束”对话窗口，如下图所示。添加车床“占用能力”=“设备能力”约束。左边框选择车床“占用能力”G2，中间下拉框选择“添加约束”中直接引用。例如，本例中“车床能力”约束条件的左边车床“占用能力”的表达式：“B2*$B$9+C2*$C$9+D2*$D$9+E2*$E$9+F2*$F$9”必须事先写入单元格G2中，以便在添加约束时直接引用它。车床能力约束添加完毕后，单击“添加”，出现新的“添加约束”对话窗口，如下图所示。添加刨床“占用能力”=“设备能力”约束。单击“添加”，又出现新的“添加约束”对话窗口，如下图所示。添加钻床“占用能力”=“设备能力”约束。单击“添加”，写入最后一个约束，如下图所示。添加铣床“占用能力”=“设备能力”约束，添加约束完成。单击“确定”，返回“规划求解”参数对话窗口，如下图所示。单击“选项”，进入“规划求解选项”对话窗口，如下图所示。选定“采用线性模型”和“假定非负”两项，其他选项保持默认值。单击“确定”结束“规划求解选项”对话窗口，返回“规划求解参数”对话窗口，如下图所示。单击“求解”，开始求解线性规划问题。求解完毕以后，出现“规划求解结果”对话窗口，如下图所示。如果线性规划问题没有可行解（即可行域为空集）或者目标函数无界，在窗口中会出现相应的提示。如果求出了最优解，在Excel表中变量相应的单元格和目标函数相应的单元格就会出现最优解的值，并出现如下的窗口。如下图所示。选定“保存规划求解结果”，变量相应的单元格和目标函数相应的单元格的值就会保存下来。如果选择“恢复为原值”，变量相应的单元格和目标函数相应的单元格的值就会恢复为0。根据需要，选定“报告”中的若干项。单击“确定”，就完成了线性规划求解的所有步骤。图是生产计划问题的最优解。Excel除了线性规划模型的工作表“Sheet1”以外，还出现了“运算结果报告”、“敏感性报告”和“极限值报告”三个新的工作表。这三个工作表的内容将在下一节介绍。由上图还可以看到，五种产品产量的数值并不是整数，这是由于在模型中没有定义变量为整数的约束。如果变量必须是整数，需要添加约束如下图所示。在左边框“单元格引用位置”中选定B9：F9变量单元格的位置，中间下拉框中选定“int”（整数integer的缩写），右边框的“约束值”就会自动出现“整数”。单击“确定”，返回“规划求解参数”对话窗口，如下图所示。可以看到，在“约束”框中增加了“$B$9：$F$9整数”这一约束。单击“确定”，重新开始求解。求解完毕，出现 “规划求解结果”对话窗口，如下图所示。选定“保存规划求解结果”以及三个报告，单击“确定”，出现以下Microsoft Excel消息窗口，如下图所示。单击“确定”，得到以下的整数规划最优解，如下图所示。配料问题优化的Excel模型= SUMPRODUCT(B4:E4,B8:E8)= SUMPRODUCT(B3:E3,B8:E8)=SUMPRODUCT(B2:E2,B8:E8)= SUMPRODUCT(B6:E6,B8:E8)=SUM(B8:E8)设置配料问题的规划求解参数，如下图所示。配料问题的最优解背包问题优化的Excel模型=SUMPRODUCT(B2:G2,B5:G5)=SUMPRODUCT(B3:G3,B5:G5)设置背包问题的规划求解参数，如下图所示。背包问题的最优解运输问题优化的Excel模型=SUM(B7:D7)=SUM(B8:D8)=SUM(B7:B8)=SUM(C7:C8)=SUM(D7:D8)=SUMPRODUCT(B2:D3,B7:D8)设置物流配送问题的规划求解参数，如下图所示。运输问题的最优解公司选择问题的Excel模型=SUMPRODUCT(B3:F3,B6:F6)=SUMPRODUCT(B2:F2,B6:F6)=SUMPRODUCT(B4:F4,B6:F6)=SUM(B6:F6)设置公司选择问题的规划求解参数，如下图所示。公司选择问题的最优解指派问题的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)设置指派问题的规划求解参数，如下图所示。指派问题的最优解产生分析报告。选定“保存规划求解结果”，单击“报告”文本框中“运算结果报告”、“敏感性报告”和“极限值报告”，单击“确定”，生成三张相应的Excel工作表。如下图所示。10.4 线性规划问题求解结果的分析其中，“运算结果报告”如下图：极限值报告如下图敏感性报告如下图x1x2z=5x1+2x2目标函数系数的灵敏度分析x1x2z=5x1+2x2z=4x1+2x2z=3x1+2x2z=2x1+2x2目标函数系数的灵敏度分析规划求解分析报告（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利润3231553270max z=32x1+31x2+55x3+32x4+70x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+3x2+5x3 +3x52400 x1，x2，x3，x4，x50规划求解分析报告（2）Excel模型规划求解分析报告（3）运算结果报告规划求解分析报告（4）敏感性报告规划求解分析报告（5）极限值报告规划求解分析报告中有关的术语（1）资源的影子价格n资源的影子价格：资源每增加一个单位，利润的增量。n资源的影子价格就是资源的边际利润。n凡是最优解时影子价格大于0的资源，最优解时没有剩余。n凡是最优解时影子价格大于0的资源，最优解时资源是紧缺的，影子价格越大，资源越紧缺。产品的机会成本n资源的影子价格和产品对资源消耗量的乘积之和，称为产品的机会成本。n产品的机会成本和利润的差，称为产品的差额成本（Reduced Cost）n机会成本大于利润（即差额成本大于0）的产品，在最优解中不会安排生产。n在最优解中安排生产的产品，机会成本等于利润（即差额成本等于0）。规划求解分析报告中有关的术语（2）设资源b1、b2、bm的影子价格为w1、w2、wmMax z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 w1 a21x1+a22x2+a2nxn b2 w2 am1x1+am2x2+amnxn bm wm x1, x2, , xn 0 产品xj的机会成本为：a1jw1+a2jw2+amjwmmax z=32x1+31x2+55x3+32x4+70x5s.t. x1+2x2+ 3x4+2x54000 2x1+2x2+3x3+ x4+4x52000 x1 +2x3+2x4+2x51800 4x1+3x2+5x3 +3x52400 x1，x2，x3，x4，x50产品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利润3231553270规划求解分析的例子规划求解分析报告数据的整理和应用产品产品编号12345资源利润（元/件）3231553270产量（件）055009000机会成本(元/件)限量（吨）占用（吨）剩余（吨）影子价格（元/吨）差额成本(元/件)设备设备A1.02.03.02.040000设备B2.02.03.01.04.0200015.5设备C1.02.02.02.018008.25设备D4.03.05.03.024000200007503800200018001650003132产品的机会成本产品对设备的消耗设备的影子价格资源的占用 产品产量产品对设备的消耗资源的剩余资源限量资源占用产品的差额成本产品的机会成本产品利润