数据模型11章(新)

数据模型与决策西安理工大学经济与管理学院熊国强教授一、数据与统计第1章数据和数据分析第5章回归分析第6章统计预测二、管理系统优化与决策第11章管理系统优化数据模型与决策第11章管理系统优化11.1线性规划模型11.2线性规划的图解法11.3线性规划问题的计算机求解11.4线性规划在工商管理中的应用应用中涉及的软件—WinQSB11.1线性规划模型11.2线性规划的图解法11.3线性规划问题的计算机求解11.4线性规划在工商管理中的应用第11章管理系统优化11.1.线性规划模型线性规划(Linearprogramm，简记LP)是运筹学中发展较快,应用较广,比较成熟的一个分支。它实质上是解决稀缺资源在有竞争的应用领域中如何进行最优分配的问题。如经营管理中:(1)物流问题(2)生产组织与计划安排问题(3)合理下料问题(4)配料问题(5)布局问题等什么是线性规划例11.1某公司在生产过程中需要使用浓度为70%的硫酸150吨，而市场上只有浓度为30%、40%、65%、75%和90%的硫酸出售，每吨价格分别为350、600、950、1500和2100元。如果您是采购部经理，试问制定怎样的采购方案，才能既满足生产要求，又使得所花费用最少？分析：用两种不同浓度的硫酸配制（初等代数法）1.应付型●确定决策变量：设x1—浓度为30%的硫酸购买量x2—浓度为90%的硫酸购买量●列方程：x1+x2=1500.30x1+0.90x2=0.7×150x1=50,x2=100——用五种不同浓度的硫酸配制（线性代数法)•确定决策变量：•设x1—浓度为30%的硫酸购买量x2—浓度为40%的硫酸购买量x3—浓度为65%的硫酸购买量x4—浓度为75%的硫酸购买量x5—浓度为90%的硫酸购买量•列方程：x1+x2+x3+x4+x5=1500.30x1+0.40x2+0.65x3+0.75x4+0.90x5=0.7×1502.深思熟虑型——考虑使费用最少(优化方法）x1+x2+x3+x4+x5=150s.t.0.3x1+0.4x2+0.65x3+0.75x4+0.9x5=105x1,x2,x3,x4,x5≥0(s.t.=Subjectto)Z=350x1+600x2+950x3+1500x4+2100x5Min---Minimize这就是一个最小化的线性规划模型.目标函数约束条件3.完美型Min例11.2配料问题（书中P434）化肥厂用四种原料A、B、C、D混合成复合肥料M。这四种原料所含氮（N）、磷（P）、钾（K）的百分含量（％）和原料单价，以及复合肥料M所要求的氮（N）、磷（P）、钾（K）的最低含量，如下表所示。百分含量（%)ABCDM氮N3015015150磷P1002515150钾K0201515100单价（元/吨）2200180024002700要求配1000吨复合肥料，并假定在配制过程中物料没有损耗。求使得总成本最低的配料方案。分析：设四种原料分别选取x1，x2，x3，x4吨，总成本为z，线性规划数学模型为：minz=2200x1+1800x2+2400x3+2700x4总成本最小化0.30x1+0.15x2+0.15x4≥150氮含量约束0.10x1+0.25x3+0.15x4≥150磷含量约束s.t.0.20x2+0.15x3+0.15x4≥100钾含量约束x1+x2+x3+x4=1000物料平衡约束x1,x2,x3,x4≥0变量非负约束这一类问题称为配料问题。百分含量（%)ABCDM氮N3015015150磷P1002515150钾K0201515100单价（元/吨）2200180024002700例11.3某企业计划安排生产甲、乙两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗量，如下表。试问应如何安排计划可使该企业获得最大利润？产品资源产品甲产品乙资源限制设备原材料A原材料B1402048（台时）16（kg）12（kg）单位利润（元/件）232.线性规划模型：Z=2x1+3x2…….利润最大化x1+2x2≤8(1)……..设备约束4x1≤16（2）……原材料A约束4x2≤12（3）…….原材料B约束x1，x2≥0（4）…….非负要求这是一个最大化的线性规划模型.(max---maximize)1.确定决策变量：x1为产品甲生产量,x2为产品乙生产量Max一个工厂有车床、刨床、钻床和铣床四种设备。生产A、B、C、D、E五种产品。每种设备每天生产时间为8小时，每年工作日为250天。各种设备的台数、全年能力（可用工时），每种产品生产一件需要分别占用这四种设备的工时（单位：小时），五种产品可以获得的利润（单位：元/件）如下表所示。例11.4生产计划问题（书中P433）设备类型设备台数产品A产品B产品C产品D产品E设备能力（小时）车床120.230.440.170.080.3612×8×250＝24000刨床110.13－0.200.370.1911×8×250＝22000钻床8－0.250.34－0.188×8×250＝16000铣床60.550.72－0.61－6×8×250＝12000产品利润（元/件）12394105132118试确定这五种产品的年生产数量，使得占用的设备工时不超过各种设备的能力，同时使总利润最大。现在我们要确定这五种产品的年生产数量，使得占用的设备工时不超过各种设备的能力，同时使总利润最大。设四种产品的产量分别为x1、x2、x3、x4、x5，总利润为z，则线性规划数学模型为：maxz=123x1+94x2+105x3+132x4+118x50.23x1+0.44x2+0.17x3+0.08x4+0.36x5≤240000.13x1+0.20x3+0.37x4+0.19x5≤220000.25x2+0.34x3+0.18x5≤160000.55x1+0.72x2+0.61x4≤12000x1，x2，x3，x4，x5≥0利润最大化目标函数车床能力约束刨床能力约束钻床能力约束铣床能力约束变量非负约束其中，max表示最大化。分析：线性规划的一般形式为：s.t.….…..….min是minimize的缩写，含义为“最小化”max是maximize的缩写，含义为“最大化”max2211nnxcxcxcz11112211(nnaxaxaxb，）21122222(nnaxaxaxb，）1122(mmmnnmaxaxaxb，）0,,,21nxxx线性规划的一般形式例11.5下列模型中，哪些是LP模型，哪些不是LP模型。1.MaxZ=3x1+x222.S=-8x1+x2x1+4x2≤9-x1+5x2≤77x2≥5x1+7x2≥5x1，x2≥0x1，x2≥03.MaxS=x1+2x24.Minf=-8x1+x2x1+2x2≤6-x1+5x2≤73x1+7x2≥5x1+7x2≥5x1，x2≥0x1，x2≥0例11.5下列模型中，哪些是LP模型，哪些不是模型。11.2线性规划的图解法对于只有两个变量的线性规划问题，可应用图解法求解。步骤：1.先画直角坐标系；2.依次画出每条约束线,并描出它们的公共区域；3.任取一目标函数值画出目标函数线，然后根据目标函数类型将该线平移至可行域边界，这时目标函数与可行域的交点即最优可行解，代入目标函数即得最优值。例11.6用图解法解下列LP问题Maxz=2x1+3x2x1+2x2≤8(1)4x1≤16（2）4x2≤12（3）x1，x2≥0（4）（4，2）（4，0）（0，0）（2，3）唯一最优解①②③Z=1zmax1.画直角坐标系2.依次画出每条约束线,并描出它们的公共区域；3.任取一目标函数值画出目标函数线，然后根据目标函数类型将该线平移至可行域边界x1x2*1*242xx线性规划解的几个概念●而所有的这些半平面中的共同部分,就构成了这个线性规划问题的解域,即可行域.（4，2）（4，0）（0，0）（2，3）●可行域中的每一个点都称为可行解,●能够使目标函数取得极值的可行解就是最优解.（4，2）（4，0）（0，0）（2，3）Maxz=2x1+3x2s.t.x1+x2≤10-x1+x2≤4x1≤8x1≥0,x2≥0可行域目标函数等值线最优解108642246810-4-20x1x2z=10z=0z=2011.2线性规划的图解法例11.7书例P440用图解法解下列LP问题：x1=3x2=7LP解的类型:1.唯一最优解2.无穷多最优解3.无界解4.无可行解线性规划问题：•Maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1，x2≥0例11.8用图解法解下列LP问题Maxz=2x1+4x2x1+2x2≤8(1)4x1≤16（2）4x2≤12（3）x1，x2≥0（4）（4，2）（4，0）（0，0）（2，3）①②③Z=1zmax1.画直角坐标系2.依次画出每条约束线,并描出它们的公共区域；3.任取一目标函数值画出目标函数线，然后根据目标函数类型将该线平移至可行域边界⑼x1x2*1*242xx无穷多最优解其中：例11.9用图解法解下列LP问题Maxz=x1+x2-2x1+x2≤4（1）x1－x2≤2（2）x1,x2≥0（3）（2，0）（0，4）（0，0）无界解②①（无最优解）讨论：•可行域无界，LP问题一定无最优解？（2，0）（0，4）（0，0）例11.10用图解法解下列LP问题Maxz=2x1+x2x1+x2≤2(1)2x1+2x2≥6(2)x1,x2≥0(3)（0，3）（3，0）无可行解①（0，2）（2，0）（无最优解）AAB唯一最优解无穷多最优解无界解无可行解LP解的类型:重要结论:•若LP存在最优解，它一定在可行域的顶点（或边界）上得到。（4，2）（4，0）（0，0）（2，3）最优解11.3线性规划问题的计算机求解•解决线性规划问题的软件包主要有以下几类：1.大规模软件包：数千个决策变量和约束条件2.微机软件包：数百个决策变量和约束条件主要介绍WinQSB软件，该软件包含了管理优化问题的大部分计算。应用中涉及的软件—WinQSB开始WinQSBLinearandintegerprogramming例11.6用图解法解下列LP问题Maxz=2x1+3x2x1+2x2≤8(1)4x1≤16（2）4x2≤12（3）x1，x2≥0（4）唯一最优解*1*242xx（4，2）（4，0）（0，0）（2，3）①②③Z=1zmaxx1x2开始WinQSBLinearandintegerprogramming一个工厂有车床、刨床、钻床和铣床四种设备。生产A、B、C、D、E五种产品。每种设备每天生产时间为8小时，每年工作日为250天。各种设备的台数、全年能力（可用工时），每种产品生产一件需要分别占用这四种设备的工时（单位：小时），五种产品可以获得的利润（单位：元/件）如下表所示。例生产计划问题（书中P433）设备类型设备台数产品A产品B产品C产品D产品E设备能力（小时）车床120.230.440.170.080.3612×8×250＝24000刨床110.13－0.200.370.1911×8×250＝22000钻床8－0.250.34－0.188×8×250＝16000铣床60.550.72－0.61－6×8×250＝12000产品利润（元/件）12394105132118maxz=123x1+94x2+105x3+132x4+118x50.23x1+0.44x2+0.17x3+0.08x4+0.36x5≤240000.13x1+0.20x3+0.37x4+0.19x5≤220000.25x2+0.34x3+0.18x5≤160000.55x1+0.72x2+0.61x4≤12000x1，x2，x3，x4，x5≥0建立问题表：maxz=123x1+94x2+105x3+132x4+118x50.23x1+0.44x2+0.17x3+0.08x4+0.36x5≤240000.13x1+0.20x3+0.37x4+0.19x5≤2