上交大运筹学课件于长锐-第二讲

运筹学课程上海交通大学管理学院于长锐电话：28516057E-mail：相关概念可行解满足线性规划问题约束条件的解，都称为该线性规划问题的可行解，所有可行解集合称为可行解集（或可行域）。最优解是目标函数达到最优值（最大值或最小值）的可行解，称为最优解。凸多边形区域设x1,x2为多边形区域中的两点，若两点连线上的任意一点，即ax1+（1-a)x2,(0≤a≤1)仍属于该多边形区域，则该多边形区域为凸多边形区域。任何两个凸多边形区域的集合仍为凸多边形区域。顶点设x为凸多边形区域中的一点，若x不能用凸多边形区域种不同两点的线性组合来表示，则称x为凸多边形区域的一个顶点。线性规划问题的图解法（1）线性规划问题的图解法（2）问题实例求解步骤求满足约束条件的可行域建立直角坐标系，以x1为横轴，x2为纵轴；确定非负约束x1≥0，x2≥0的各点集合，即第一象限；确定满足约束条件2x1+3x2≤100的各点集合。在坐标系中画出直线2x1+3x2=100，该直线为边界的左下方的半平面即为满足约束条件2x1+3x2≤100的各点集合；同理，确定其他各约束条件的点集合；点集合的交叉区域即为该问题的可行域。从可行域中找出目标函数的最优解画目标函数的等值线；平移等值线，在可行解区域内找到目标函数的最优解。线性规划问题图解法的几种特殊情况有多重最优解将上例中目标函数由Z=6x1+4x2变为Z=4x1+6x2后，再用图解法进行求解可行解区域无界用图解法求解线性规划问题的图解法（3）无可行解区域用图解法求解图解法的几点讨论(1)若线性规划问题有可行解．则可行解区域是一个凸多边形，它可能是有界的；也可能是无界的。(2)若线性规划问题有最优解，则最优解可能是唯一的；也可能是无穷多个。如果是唯一的，这个最优解一定在该凸多边形的某个顶点上；如果是无穷多个，那末这些最优解一定是凸多边形的一条边界（包括此边界的两个端点）。总之，如果线性规划问题有最优解，则这个最优解一定可以在凸多边形的顶点达到。(3)若线性规划问题有可行解，但是没有有限最优解。这时凸多边形是无界的。(4)若线性规划问题没有可行解，即可行解集是空集，则此问题没有最优解。线性规划问题的图解法（4）线性规划模型的几种形式（1）一般形式标准形式（标准型）线性规划模型的几种形式（2）可见简写为：注意：目标函数一定是max；标准型中规定各约束条件的右端项bi≥0，否则等式两端乘以“-1”决策变量一定是非负。一般形式转化为标准型若原模型中的目标函数实现最小化，即minZ=CX，则令Z/=-Z，可得到maxZ/=-CX，这就同标准型的目标函数形式相一致；若原模型中的约束条件为不等式，两种情况原约束条件左端≥右端，则添加剩余变量，约束条件化为原约束条件左端-剩余变量=右端(剩余变量≥0)原约束条件左端≤右端，则添加松弛变量，约束条件化为原约束条件左端+松弛变量=右端(松弛变量≥0)在原模型中引入剩余变量(或松弛变量)后，使问题的变量维数增加，目标函数并不发生改变，即在目标函数中，附加变量的系数为0。若原模型中变量xk自由变量，即xk

∈(∞,-∞)，则令xk

=x/k–x//k，其中x/k，x//k

≥0，目标函数相应变化。线性规划模型的几种形式（3）实例线性规划模型的几种形式（4）线性规划模型的几种形式（5）标准型的几种表示形式向量形式矩阵形式线性规划模型的几种形式（6）线性规划问题解的性质（1）可行解与最优解从线性规划问题的标准型来看，满足线性规划问题约束条件的解称为线性规划问题的可行解；在可行解中，目标函数达到最大值的解，称为最优解。因此，线性规划问题可行解的求取可转化为求解有约束条件组成的非齐次线性方程组。基、基变量、非基变量设A是约束条件方程组的m*n为系数矩阵，其秩为m，B是矩阵A中m*m阶非奇异子矩阵（|B|≠0)，则称B为线性规划问题的一个基。与基对应的决策变量称为基变量，否则称为非基变量。线性规划问题解的性质（2）==目标函数约束条件行列式≠0基右边常数线性规划问题解的性质（3）基解、基可行解、可行基设XB=（x1,x2,…,xm)为基B所对应的基变量,令非基变量xm+1,xm+2,…,xn=0，可以求出一个解XB=（x1,x2,…,xm,0,0,…,0)，该解的称为基B的基解。满足非负条件的基解，成为基可行解。对应于基可行解的基，称为可行基。讨论：一个线性规划问题最多有多少个基可行解？实例线性规划问题的几何性质（1）定义凸集、顶点定理1.线性规划问题存在可行域，则其可行域是凸集。2.线性规划问题的基可行解对应于可行域的顶点。3.若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。结论线性规划问题的可行域是凸集，也可能是无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在可行域的某个顶点上得到。线性规划问题的求解思路可以是：找出问题的所有基可行解，代入目标函数后，求的目标函数的值，然后把目标函数值一一比较，最终找到最优解。线性规划问题的几何性质（2）几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基解可行域的顶点基可行解目标函数等值线：一组平行线目标函数值等于一个常数的解单纯形法的基本原理（1）基本原理根据问题的标准型，从可行域中某个基可行解（一个顶点）开始，判断此基可行解是否最优，否则转换到另一个基可行解（顶点），直到是目标函数达到最大值时，问题得到最优解。过程实例工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制，如下表所示。每生产一单位产品I可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应如何安排生产获利最多?单纯形法的基本原理（2）1.建立模型设决策变量xj（j=1,2)表示生产成品j的数量，则问题可归结为2.转化为标准型添加松弛变量x3,x4,x5,则标准型为单纯形法的基本原理（3）单纯形法的基本原理（4）3.确定初始基，并求出基解系数矩阵为则可令x3,x4,x5位初始基变量，则基解为(0,0,300,400,250)是基可行解4.最优解检验检验方法：将基变量用非基变量线性表示，然后带入目标函数，如果非基变量前面的某个系数大于零，说明仍没有达到最优解；否则，该解为问题最优解。因为非基变量x1,x2在目标函数中的系数均大于零，因此基可行解(0,0,300,400,250)不是最优解单纯形法的基本原理（5）5.确定出基变量、入基变量在非基变量表示的目标函数中，系数最大的非基变量为入基变量。因此，x2为入基变量把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项b的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。因此，x5为出基变量新的基变量为x2,x3,x4，非基变量为x1,x5单纯形法的基本原理（6）单纯形法的基本原理（7）进行矩阵变换，求基可行解基解为（0,250,150,50,0)，是基可行解单纯形法的基本原理（8）最优解检验因为非基变量x1在目标函数中的系数大于零，因此基可行解(0,0,300,400,250)不是最优解因此，x1为入基变量因此，x3为出基变量新的基变量为x1,x2,x4，非基变量为x3,x5单纯形法的基本原理（9）进行矩阵变换，求基可行解基解为（50,250,0,50,0)，是基可行解最优解检验带入目标函数非基变量的均小于等于0，因此该解为最优解单纯形法的基本原理（10）单纯形法的表格形式（1）检验数计算的一般形式设线性规划问题

系数矩阵为基可行解为(b1,b2,…,bm,0,0,…,0)求检验数，判断该解是否为最优解有非基变量线性表示基变量，得单纯形法的表格形式（2）带入目标函数有令则目标函数变为单纯形法的表格形式（3）判断是否达到最优解，是判断非基变量前的系数是否小于等于零因此，我们将称为检验数其中单纯形法的表格形式（4）单纯形表的格式单纯形法的表格形式（5）单纯形法的表格形式（6）计算步骤1.找出初始可行基，确定初始基可行解，建立初始单纯形表；2.检验各非基变量xj的检验数，若，则已得到最优解，可停止计算，否则转入下一步；3.若在