第1章 线性规划及单纯形法复习及举例.ppt

第1章 线性规划及单纯形法 知识点及应用举例 主要知识点 线性规划的数学模型 Max(Min)Z=c1x1+c2x2+…..+cnxn s.t. a11x1+a12x2+….+a1nxn ?(=, ?)b1 a21x1+a22x2+….+a2nxn ?(=, ?)b2 …………………. am1x1+am2x2+….+amnxn ?(=, ?)bm x1,x2….xn ? 0 主要知识点 线性规划模型的特点 数学建模方法的基本步骤 标准形的特征及一般形化为标准形的方法 用图解法求解2个变量线性规划问题的步骤 单纯形原理 单纯形方法及单纯形表 大M法和两阶段法 复习思考题 1 试述线性规划数学模型的结构及各要素的特征。 2 求解线性规划问题时可能出现哪几种结果，哪些结果反映建模时有错误。 3什么是线性规划问题的标准型式，如何将一个非标准型的线性规划问题转化为标准型式。 4试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。 5 试述单纯形法的计算步骤，如何在单纯形表上去判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 6 如果线性规划的标准型式变换为求目标函数的极小化min Z，则用单纯形法计算时如何判别问题已得到最优解。 复习思考题 7 在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中人工变量前的系数为(一M)的经济意义是什么。 8 什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。 9 判断下列说法是否正确: (a)图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的； (b)线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大； (c)线性规划问题的每一个基解对应可行域的一个顶点； (d)如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点； (e)对取值无约束的变量xj,通常令xj＝xjˊ-xj，其中xjˊ≥0，xj≥0，在用单纯形法求得的最优解中有可能同时出现xjˊ0，xj0。 复习思考题 (f)用单纯形法求解标准型式的线性规划问题时，与检验数大于0对应的变量都可以被选作换入变量； (g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负； (h) 单纯形法计算中，选取最大正检验数对应的变量为换入变量，将使目标函数值得到最快的增长； (i)一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果； (j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示； (k)若Xˊ、X分别是某一线性规划问题的最优解，则它们的线性组合也是该线性规划问题的最优解。 应用举例 例1 用图解法求解下列线性规划问题 min z ＝6x1＋4x2 st. 2x1＋ x2≥1 3x1＋ 4x2≥1.5 x1, x2≥0 解： 第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，交集为（1/2, 0）。 第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4），过原点O作一条矢量指向点（6，4），矢量的长度不限，矢量的斜率保持4比6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函数图形的位置任意，如果通过原点则目标函数值Z=0。 第三，求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向，在求最小值时将目标函数图形沿梯度方向的反方向平行移动，（在求最大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移动，其交点对应的坐标就是最优解，最优解x=（1/2, 0）,目标函数的最小值Z=3。 应用举例 最优性理论问题 例2 线性规划问题max z＝CX，AX＝b，X≥0，如X*是该问题的最优解，又λ＞0为某一常数，分别讨论下列情况时最优解的变化： （1）目标函数变为max z＝λCX； （2）目标函数变为max z＝（C＋λ）X； （3）目标函数变为max z＝（C/λ）X，约束条件变为AX＝λb。 解： （1）X*仍为最优解，max z＝λCX； （2）除C为常数向量外，一般X*不再是该问题的最优解； （3）最优解变为λX*，目标函数值不变。 应用举例 建模问题 例3某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种