《《管理系统优化》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。单击“添加”，得到“添加约束”对话窗口，如下图所示。
