一章线规划与单纯形法.pptVIP

第一章　线性规划与单纯形法 第一节　线性规划的基本概念 第二节　线性规划的标准形式和解的性质 第三节　单纯形法 第四节　人工变量法 第五节　线性规划应用举例 本章学习目的和要求 　　　通过本章的学习，要求学生掌握线性规划的图解法，深刻理解单纯形法的解题思路，熟练掌握其运算步骤，并能在实际问题中加以运用。 主要研究目的 1．已有一定数量的人力、物力、财力资源，研究如何充分合理地使用才能使完成的任务量最大。（如：利润、产值等最大。 maximum） 2．当一项任务量确定以后，研究如何统筹安排，才能使完成任务耗费的资源量为最小。（如：成本最小。minimum） 第一节　线性规划的基本概念 一、线性规划的数学模型 　　　【例1-1】 某厂生产P、Q两种产品，主要消耗A、B、C三种原料，已知单位产品的原料消耗数量等资料如表1-1所示。 　　解：设每千克饮料中原料甲，乙，丙的投入量分为x1，x2，x3千克，则问题的模型为： 　【例1-3】 A1，A2是两个粮库，每月分别可调出粮食30吨与40吨，三个粮店B1，B2，B3每月的需求量分别为20吨，25吨与18吨。粮库与粮店之间每吨粮食的运费如下表1-3所示（单位：元/吨）。 解：设从粮库Ai到粮店Bj的调运量为xij，i=1，2，j=1，2，3，则问题的模型为： 　　上述三个问题属于同一类型的决策优化问题，它们具有下列共同特点： （1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它也是变量的线性函数。 　　　具备以上三个特点的数学模型称为线性规划（Linear Programming，简记为LP）。 实际问题中线性的含义 　　　一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例。 　　　二是可叠加性，如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和。 　　线性规划的一般形式为： 　　采用求和符号Σ，线性规划的一般形式可以简写为： 用向量形式可表示为： 二、图解法 　　　当决策变量个数n=2时，LP问题可以通过在平面上作图的方法求解，称为图解法。 　　　图解法求解的目的： 1.判别线性规划问题的求解结局。 2.在存在最优解的条件下，把问题的最优解找出来。 【例1-4】 求下列问题的最优解。 （1）确定问题的可行域R。 （2）分析目标函数Z的等值线平行移动与Z值的关系，确定最优解的位置。 　　　当z取定值时，方程z=2x1+5x2或x2=－2/5x1+z/5表示一条斜率为－2/5的直线 l ， 称为z的等值线，它在x2轴上的截距为z/5。当l向右上方平行移动且保持与R有共同部分时，z值不断上升，由于l的斜率为－2/5，因此当l向右上方平移的过程中，与R最后的公共点是Q3，z在Q3达到最大值。 （3）计算最优解。 点Q3是直线l1与l3的交点，它的坐标由方程组 线性规划问题求解的几种可能结局： 1.唯一最优解：如上例。 2.无穷多最优解：如Z换成maxZ=2X1+4X2,，此时最优解在线段Q2Q3 上达到，有无穷多最优解。 已求得Q3的坐标为（2，3）；Q2坐标由方程组 3.无界解 　　　如约束条件只保留第3个，即4X2≤12，这时可行域无界，Z值可无限上升，无最优解，简称无界解，即有可行解，但目标函数值无解。 　　　产生原因：是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。 4.无解或无可行解 图解法得到的启示 1.求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解和无可行解。 2.若线性规划问题的可行域存在，则可行域是一凸集。 3.若线性规划问题的最优解存在，则最优解一定在某个顶点可达到。 4.解题思路是：先找出凸集的任一顶点，计算Z值，比较相邻顶点Z值，如大，转到相邻顶点，一直到找出使Z值最大的顶点为止。 第二节 线性规划的标准形式和解的性质 一、 LP的标准形式 例：把LP问题 　　　　　　　　　　　　　 化为标准形式 　　　在三个技术约束中，分别加入松弛变量x3，x4，x5，问题化为标准形式： 【例1-9】 把LP问题 化为标准形式 二、 LP的基可行解的概念 　　对于标准形式的线性规划，利用向量矩阵记号，令X=（x1，x2，…，xn）T，C=（c1，c2，…，cn），b=（b1，b2，…，bm）T，A=（aij）m×n。 　　X，C，b分别称为决策变量向量，价值向量，资源向量（右端常数向量），A称为系数矩阵。Pj=（a1j，a2j，…，amj）T是xj的系数列向量，它是A的第j列，A=（P1，P2，…，Pn）。 　　利用这些记号，标准形线性规