作目标函数等值线

课程网站：exp.vanpersie.cc/operations继续返回图解法线性规划问题求解的几种可能结果由图解法得到的启示回顾线性规划的图解法继续返回例1的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x29—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)图解法图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。线性规划问题求解的几种可能结果(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可行域为空集线性规划问题求解的几种可能结果图解法的几点结论:（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。2.2.2线性规划解的性质线性规划解的概念线性规划问题的几何意义（单纯形法原理）继续返回线性规划问题解的概念,...,x,xxbxa...xaxa...........................bxa...xaxabxa...xaxaxc...xcxcznmnmnmmnnnnnn0max21221122222121112121112211线性规划问题解的概念n11111...，资源向量,...,.........,...,约束条件矩阵bbbaaaaAmnmn11,nnxc,...,c...x价值向量c决策变量向量x引例（上一章例）0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz线性规划问题解的概念nnxcxcz...max110...01nxxmnmnnmmmmmmmmmbbxaaxaaxaaxaa.....................11111111111线性规划问题解的概念n1n11111......,...,.........,...,bbxxaaaabAxmnmnnnx...x,...,cczcxz11maxmax)0,...,0(),...,(0x1nxx线性规划问题解的概念标准型可行解:满足Ax=b,x≥0的解X称为线性规划问题的可行解。最优解：使z=CX达到最大值的可行解称为最优解。maxx0zcxAxb基：若B是矩阵A中m×m阶非奇异子矩阵（|B|≠0），则B是线性规划问题的一个基。不妨设：),...,(,...,.........,...,11111mmmmmPPaaaaBjPjxjx,j=1，2，…,m——基向量。，j=1，2，…,m——基变量。,j=m+1,…,n——非基变量。线性规划问题解的概念求解nmnnmmmmmmmmmmxaaxaabbxaaxaa.....................111111111110maxXbAXCXZ线性规划问题解的概念基解：称上面求出的x解为基解。基可行解：非负的基解x称为基可行解可行基：对应基可行解的基称为可行基线性规划问题解的概念TmBxxxX)...,(21'''12(,,...,0,0,...,0)mxbbbT基变量令可求出：0...21nmmxxx线性规划解的关系图非可行解可行解基可行解基解线性规划问题解的概念最优解？2.3单纯形法原理本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。引例（上一章例）0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz第1步确定初始基可行解100010001),,(令：543PPPB100400100400121),...,(51PPA根据显然，可构成初等可行基B。543,,PPP为基变量543,,xxx第2步求出基可行解基变量用非基变量表示，并令非基变量为0时对应的解是否是最优解？412416282514213xxxxxxx)1216800(,03200)0(2121,,,,XXxxxxZ)(得一基可行解令：函数标代入目第3步最优性检验分析目标函数zxx02312检验数=0时，最优解0时，无解换基，继续只要取x10或x20,z的值可能增大。考虑将或换入为基变量21xx第4步基变换换入基变量：换入变量2x均可换入。2211210320xxxxz212,1,,0xx（即选最大非负检验数对应的变量）一般选取对应的变量),max(21换出变量使换入的变量越大越好同时，新的解要可行。选非负的最小者对应的变量换出i为换出变量3)4/12,,2/8min(04120160285225423xxxxxxx2x为换入变量，应换出？变量。为换出变量变量：为换入变量，确定换出522542323)4/12,,2/8min(0412016028xxxxxxxx3)4/12,,2/8min(}0,,min{2323222121kaababab因此，基由变为)(243PPPB转第2步：基变量用非基变量表示。第3步：最优性判断检验数存在正，按第4步换基继续迭代均非正，停止（这时的解即是最优解）x2为换入变量，应换出x5变量。)(543PPPB转第2步)0,16,2,3,0(,0432941341621212441682)1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：函数标代入目继续迭代,可得到:43)3()2(125.05.114目标函数为：)4,0,0,2,4()0,8,0,3,2(xxZXX最优值Ｚ＝１４最优解结合图形法分析（单纯形法的几何意义）6—5—4—3—2—1—0x2|||||||||123456789x1)0,16,2,3,0(得一基可行解,0令：4329代入目标函数41341621812441682)1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx43)3()2(125.05.114目标函数为：)4,0,0,2,4()0,8,0,3,2(xxZXX43)3()2(125.05.114目标函数为：)4,0,0,2,4()0,8,0,3,2(xxZXXA(0,3)B(2,3)C(4,2)D(4,0)2.2.2线性规划解的性质返回作业1：用图解法求解LP问题MaxZ=34x1+40x24x1+6x2482x1+2x2182x1+x216x1、x20作业2：用课上讲的单纯型法解法求解LP问题MaxZ=34x1+40x24x1+6x2482x1+2x2182x1+x216x1、x20