第一章 线性规划及单纯型法1

上页下页返回第一章线性规划及单纯型法•1.1线性规划问题及其模型•1.2.1线性规划图解法•1.2.2线性规划解的性质•1.3单纯形法原理•1.4单纯形法计算步骤•1.5.1单纯形法的进一步讨论•1.5.2单纯形法的矩阵描述及改进单纯形法•1.6.1线性规划应用举例•1.6.2线性规划模型（电子表格）•1.7习题课线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回1.1线性规划问题及其数学模型上页下页返回•问题的提出•例:生产计划问题III资源限量设备原材料A原材料B1402048台时16kg12kg利润23上页下页返回产品I产品2如何安排生产使利润最大？上页下页返回决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)•基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值上页下页返回x1x2是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。•第1步-确定决策变量x1x2z•设——I的产量——II的产量——利润上页下页返回第2步--定义目标函数MaxZ=x1+x2上页下页返回MaxZ=2x1+3x2第2步--定义目标函数上页下页返回对我们有何限制?上页下页返回第3步--表示约束条件x1+2x284x1164x212x1、x20III资源限量设备原材料A原材料B1402048台时16kg12kg利润23上页下页返回该计划的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2上页下页返回线性规划问题的共同特征•一组决策变量X表示一个方案,一般X大于等于零。•约束条件是线性等式或不等式。•目标函数是线性的。求目标函数最大化或最小化上页下页返回线性规划模型的一般形式0,...,,),(......................................................),(...),(......)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax上页下页返回线性规划问题的标准形式•标准形式为:0,...,0,...,,......................................................2121221122222121112121112211mnmnmnmmnnnnnnbbbxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMax目标函数最大约束条件等式决策变量非负上页下页返回–简写为njxmibxaxcZjinjjijnijj,...,2,10,...2,1max11上页下页返回–用向量表示),...cc,(cC,...2,10max212121n211b...bbba...aaPx...xxXnjxbxPCXZmmjjjjnjnijj其中：上页下页返回–用矩阵表示nnmnmnxPPPaaaaAXbAXCXZ...xxX),...,,(.........................0max21211111决策变量向量-X价值向量-C资源向量0...000),...,,(.........................0max3211111bPPPaaaaAXbAXCXZmnmnC—价值向量b—资源向量X—决策变量向量上页下页返回•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化例：目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20上页下页返回•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz例：上页下页返回•“”约束：减去非负剩余变量；无约束321321321321321,0,7232732minxxxxxxxxxxxxxxxzMaxx6x7例：543xxxkx•可正可负（即无约束）；0,''kkkkkxxxxx令上页下页返回解：标准形为0,,,,,7)(232)(7)(00)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz线性规划问题的数学模型例将下列线性规划问题化为标准形式,0,523247532min321321321321321无约束xxxxxxxxxxxxxxxZ用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以33xx3x0,33xx线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;线性规划问题的数学模型0,,,,,5)(252)(7)(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：上页下页返回图解法线性规划问题求解的几种可能结果由图解法得到的启示1.2.1线性规划的图解法继续返回上页下页返回例1的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2上页下页返回9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+2x28(0,4)(8,0)目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x204x1164x216图解法上页下页返回9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216可行域图解法上页下页返回9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1+2x284x1164x216可行域BCDEA图解法上页下页返回9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216BCDEA2x1+3x2=6图解法上页下页返回9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216BCDEAx1+2x2=84x1=16最优解(4,2)图解法例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：图解法(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400图解法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1图解法（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE上页下页返回图解法求解步骤•由全部约束条件作图求出可行域；•作目标函数等值线，确定使目标函数最优的移动方向；•平移目标函数的等值线，找出最优点，算出最优值。上页下页返回线性规划问题求解的几种可能结果(a)唯一最优解x26—5—4—3—2—1—0|||||||||123456789x1上页下页返回(b)无穷多最优解6—5—4—3—2—1—0x2|||||||||123456789x1线性规划问题求解的几种可能结果上页下页返回(c)无界解MaxZ=x1+x2-2x1+x24x1-x22x1、x20x2x1线性规划问题求解的几种可能结果上页下页返回(d)无可行解MaxZ=2x1+3x2x1+2x284x1164x212-2x1+x24x1、x20可行域为空集线性规划问题求解的几种可能结果上页下页返回图解法的几点结论:（由图解法得到的启示）–可行域是有界或无界的凸多边形。–若线性规划问题存在最优解，它一定可以在可行域的顶点得到。–若两个顶点同时得到最优解，则其连线上的所有点都是最优解。–解题思路：找出凸集的顶点，计算其目标函数值，比较即得。上页下页返回练习：用图解法求解LP问题MaxZ=34x1+40x24x1+6x2482x1+2x2182x1+x216x1、x20上页下页返回图解法—（练习）18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x1x24x1+6x2482x1+2x2182x1+x216上页下页返回图解法—（练习）18—16—14—12—10—8—6—4—2—0|||||||||24681012141618