第二次图解概念原理excel求解

线性规划图解法及其几何意义线性规划求解法目前最常用的方法有：图解法：利用数模中方程式的几何图形来直接找到最优解。单纯形法:求解线性规划的一般方法2.1图解法只适合于两个变量，故其实用意义不大。解法的一个重要目的在于利用它的直观图形看问题，有助于了解和剖析线性规划的原理及过程。图解法的重点是说明线性规划的几何意义。对上述【例1--1】进行图解法的求解过程。MaxZ=3x1+4x2

x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0s.t.(1—1)在以x1,x2为坐标轴的直角坐标系中，非负条件是指第一象限。x1x20123456789654321每一个约束条件都代表一个半平面。如是代表以直线为边界的左下方的半平面。同时满足x1,x2≥0x1+x2≤6x1+2x2≤8x2≤3必落在由这三个半平面交成的第一象限区域内。x1+x2=62x1+2x2=8X2=3Q0Q2Q1Q5Q4Q3Q8Q7Q6x1x20123456789654321Q0Q2Q1Q4Q3可行解：满足约束条件的解。绿色区域中的每一个点（包括边界点）都是可行解。此区域是【例1--1】的线性规划问题的解的集合（可行解域）。目标函数Z=3x1+4x2在这个坐标平面上，它可以表示以Z为参数、-3/4为斜率的一族平行线：x2=-3x1/4+Z/4位于同一直线上的点，具有相同的目标函数，称为“等值线”。当Z值由小变大时，直线x2=-3x1/4+Z/4沿其法线方向（3，4）向右上方移动。当移动到Q2时，Z值在可行域的边界上实现最大化。最优解Q2（4，2），Z=20。该企业的最优生产方案甲产品生产4吨，乙产品生产2吨，可得最大利润2000元。图解法的计算步骤：（1）绘出每个约束方程的约束半平面设约束方程为①画出直线②若约束方程为，则半平面在其直线的-(a1,a2)方向。③若约束方程为，则半平面在其直线的(a1,a2)方向。④若约束方程为，则半平面即为该直线。试画（2）绘出可行解域各个约束半平面相交的区域。（3）设目标函数为

作与方向相垂直的目标函数等值线在可行解域中移动①若目标为求“max”，则目标函数等值线沿方向同方向移动②若目标为求“min”，则目标函数等值线沿相反方向移动移动中确定使目标函数达到最优的可行解，该解即为最优解。（4）求出最优解优化方向x1x20123456789654321Q0Q2Q1Q4Q3当移动到Q2Q3线段时，Z值在线段Q2Q3上实现最大化。线段Q2Q3上的任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。线性规划问题求解可能情况：A无穷多最优解（多重解）：B无界解考虑下述线性规划问题：

x1x20123456789654321该问题可行域无界，目标函数可以增大到无穷大可行域无界是否一定没有最优解？C无可行解考虑如下线性规划问题：x1x20123456789654321可行域为空集，无可行解，当然也无最优解。2.2线性规划的几何意义当线性规划问题的可行解域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。线性规划的这些性质并不因变量的个数增加而改变，可以从两个变量的图解法几何意义理解任意多个变量单纯形法原理。2.2.1基本概念设有两点与上两点之间的关系如下图。CBACBA两点,间线段上的点的表达式。即基本概念凸集：对于n维欧氏空间点集D中的任意不同两点则称D为凸集。(a)(b)(c)(d)

凸组合：设X（1），…，X(k)是n维欧式空间中的k个点，若存在，则称X为的凸组合。顶点：设D为凸集，若X不能用不同的两个顶点的线性组合表示为：则称X为凸集D一个顶点（或极点）。(a)(b)(c)(d)2.2.2线性规划的几何意义1）线性规划的可行解域为凸集；2）线性规划可行解域的顶点个数是有限的；3）若线性规划问题存在最优解，则最优解必在其可行解域的某一顶点上得到。3.单纯形法原理3.1线性规划的标准型约束条件满足以下两点的称为标准型：约束方程均为等式方程；所有变量均为非负变量。简写为向量表达式为其中：矩阵表达式为：3.2化线性规划问题为标准型3.2.1化不等式约束为等式约束①约束方程为“≤”号。在“≤”左端加入一个非负松弛变量，把原“≤”的不等式变为等式。②约束方程为“≥”号。在“≥”左端减去一个非负剩余变量（也可称为松弛变量），把原“≥”的不等式变为等式。3.2.2化无约束变量为非负变量若为无约束变量，令，即可。在各不等式中分别加上一个非负松弛变量,使不等式变为等式，得标准型：【例1—7】【例1—8】令第一个约束加入松弛变量；第二个约束减去松弛变量；第三个约束加入松弛变量。得标准型：3.3基本概念设有一标准型可行解：满足约束条件（1—3）、（1—4）的解称为线性规划问题的可行解。基：设B是从A中任取m个列所构成的方阵，且则称B是线性规划问题的一个基。基变量：若B为基，则B中列所对应的变量称为基变量，用XB表示，余下的其他变量成为非基变量，用XN表示。注意两点：B在A中是任意取的。故A中有很多基B。基变量是针对B而言的，不同B，其对应的基变量和非基变量是不同的。可取A中取定某一基B后，式（1—3）可表示为取则（1—3）式可写成基解：设B为某一个基，则有BXB+NXN=b

令XN=0，则得一个满足（1—3）式的解这个解称为基解。基可行解：若为一个基解，且则得到一个满足（1—3）、（1—4）的可行解，称为基可行解。3.4基本定理定理1：若线性规划问题存在可行解域，则其可行解域是凸集。引理1：线性规划问题的可行解

为基可行解的充要条件是，X的正分量所对应的系数列向量是线性独立的。定理2：线性规划问题的基可行解X对应于可行域D的顶点。引理2：若D是有界凸集，则任何一点X∈D可表示为

D的顶点的凸组合。定理3：若可行域有界，线性规划问题的目标函数一定可以在可行解域的顶点上达到最优。由上述线性规划的基本定理，得以下结论：线性规划问题的可行解域是凸集；基可行解是可行域的顶点，可行域的顶点即是基可行解，因此，每个基可行解对应可行域的一个顶点；3.可行解域的顶点个数是有限的，不超过个。4.若线性规划问题有最优解，则最优解必在某个顶点上得到。【例1—1】线性规划模型标准型如下（1—8）序号基变量基解X=(x1,x2,x3,x4,x5)T是否可行对应点Z值1x1,x2,x3X=(2,3,1,0,0)T可行Q3182x1,x2,x4X=(3,3,0,-1,0)T不可行Q7—3x1,x2,x5X=(4,2,0,0,1)T可行Q2204x1,x3,x5X=(8,0,-2,0,3)T不可行Q8—5x1,x4,x5X=(6,0,0,2,3)T可行Q1186x2,x3,x4X=(0,3,3,2,0)T可行Q4127x2,x3,x5X=(0,4,2,0,-1)T不可行Q5—8x2,x4,x5X=(0,6,0,-4,-3)T不可行Q6—9x3,x4,x5X=(0,0,6,8,3)T可行Q00X1、X3、X4不能构成B的一组基变量。x1x20123456789654321x1+x2=62x1+2x2=8X2=3Q0Q2Q1Q5Q4Q3Q8Q7Q6基可行解所对应的顶点为Q3，Q2，Q1，Q4，Q0Q2为最优解。枚举法找所有的基可行解，然后比较，找到最优解。当m,n较大时，此法行不通！单纯形法。4.单纯形法步骤及过程单纯形法的思路是：根据线性规划问题的规范型，从可行解域中某个基可行解（顶点）开始，判断该基可行解是否是最优解（定理3：最优解必在某一基可行解中得到），若不是最优解，则转换到另一个基可行解（另一顶点），使目标函数值得到改善，如此反复，直至找到最优解（某一基可行解）为止。4.1线性规划问题的规范型定义：AX=bX≥0b≥0,且A中含有一个单位矩阵I。标准型这里【例1--10】【例1--1】的标准型为（P1,P2,P3,,P4,P5）=I式（1—9）是规范型。【例1--11】两边同乘（-1），（1—10）式变为：由于这时（P1,P2,P3,,P4,P5）=I式（1—10）是规范型。【例1--12】有如下标准型：右边常数为正。但A中找不到三列向量构成的方阵为单位矩阵，故式（1--11）是标准型而不是规范型。对于规范型（如1—9式），取B=I=（P3，P4，P5），故B=I为一个基，该基的基变量为x3,x4,x5，非基变量为x1,x2，令非基变量为零（x1=0,x2=0），得一基可行解XB=b≥0,即(x1,x2

x3,x4,x5)T≥0.规范型的作用是可以从规范型中马上确定一个基可行解（顶点）。任何线性规划问题均可化为标准型，（见本章3.2一节），但并不一定可以化为规范型。【例1--13】有一线性规划问题约束如下：把上式化为标准型：由规范型定义知，式（1—12）不是规范型。4.2单纯形求解过程（步骤）以【例1--1】来讨论它的求解过程，【例1--1】的标准型为（1）确定一个初始基可行解（顶点）。式（1—13）还是一个规范型，取A中所含的单位矩阵作为一个基，即B=I，XB=(x3，x4，x5)T，XN=(x1,x2)T。则可得一初始基可行解X(0)=（0，0，6，8，3)T,其目标函数值Z0=0。最优解必在某一基可行解（顶点）上达到，那么是否是最优解？-------检验。考察目标函数Z=0+3x1+4x2(1—14)目标函数是以X（0）的非基变量表示的，不会有X（0）的基变量。由于x1=x2=0，所以Z（0）=0。系数都是正的若将非基变量变换成基变量，目标函数的值就可能增大，x1，x2不等于0，等于某个正数所