第一章线性规划(教案)[] 修改--模板修改.pptVIP

第一章：线性规划（3） 单纯形法的进一步讨论大M法及两阶段法解的类型 基本要求 1．熟练掌握人工变量法（大M法及两阶段法）。 2．能准确地根据单纯形表中的检验数判别所解问题的解的类型。 知识要点 1．人工变量法 大M法： 用单纯形法求解线性规划问题时，先要将问题化为标准形式，若这时约束方程组的系数矩阵中还没有包括一个单位矩阵（阶数要等于约束方程的个数），则可在一些约束方程上添加非负的人工变量，使系数矩阵中凑出个单位矩阵来。人工变量在目标函数中的系数为“-M”，M是充分大的正数。通过用单纯形法解这个新的线性规划（不妨称为大M问题）来求解原来的线性规划，这种方法叫大M法。 两阶段法 这种方法用与大M法相同。解决约束方程组系数矩阵中必须出现单位矩阵的问题，但以后将分成两个阶段计算：第一阶段目标函数是改为所有人工变量的和，求极小值，约束条件是原来问题的约束条件添加了松弛变量（剩余变量）以及人工变量后的约束条件。第二个阶段则是利用第一个阶段的结果单纯形表，或者说明原来题目无可行解，如果有解则去掉第一个阶段的结果单纯形表中人工变量对应的列，第二阶段目标函数为原题目 的目标函数，继续根据单纯形方法计算 第一章：线性规划（3） 2．检验准则（适用于有人工变量的问题，仅就大M法叙述，两阶段法有同样结论） （1）如果所有检验数均小于或等于零而且单纯形表的基变量没有取值非零的人工变量，那么已得到原来问题的最优解。 （2）如果所有检验数均小于或等于零，但基变量中还有不为零的人工变量，那么原 来问题无可行解。 （3）如果所解的大M问题有无界解（即有可行解但无最优解），则当人工变量全为零时，那么原来问题也有无界解，而当人工变量不全为零时，那么原来问题无可行解。 3．关于线性规划问题最优解是唯一，有如下定理 非退化的基可行解X0是唯一最优解的充分必要条件是，这个基可行解X0所有非基变量的检验数均小于零。 这也就是说，非退化的基可行解X0不是唯一最优解（从而问题有无穷多最优解）的充分必要条件是这个基可行解X0的某个非基变量的检验数等于零。 1。线性规划的引例与模型 矩阵A, 向量C,b,AX, a1,a1x,的经济含意 标准型式（max, 等式约束，非负限制） 松弛变量，剩余变量经济含意 可行解 2 线性规划的几何意义 图解法 可行域, 可行解 图示线性规划的解的各种情况 (1)???? 唯一最优解 (2)?? ? 无穷最优解 (3)??? ? 无界最优解 从图解法猜想 1 LP最优解是可行域的顶点之一 2 如可行域有界, 则LP最优解就是可行域的一个顶点 3 基可行解对应可行域的顶点 线性规划（4） 第一章：线性规划（4） 应用四例? Chapter 1: linear programming(4) ? Four applicational cases about LP ? Case 1:Production Process ? Case 2:Blending Problems ? Case 3: Producing Scheduling ? Case 4:Capital Investment Problems 例1：下料问题（p37） ? 例2：配料问题 (p38) ? 例3：生产计划问题 (p41) ? 例4：投资问题 (p42) 线性规划模型特点 1 一个目标函数：线性 2 几个约束条件：线性 3 多个决策变量：非负 世界500强企业中广泛的应用是因为现实中的确存在各种约束： 关键设备生产能力约束 各类能源约束（电力，煤） 工艺流程约束 产品类结构关系约束（例如产品的合金比，钢坯的连铸比） 物流过程上，中，下游产品供需约束 某些产品下限约束（例如必要库存，稳定的用户需求） 第一章：线性规划（4） 应用四例? 下料问题 案例 国际会议上本人听到日本教授的下料的论文。 本人家装修跃层木地板，废料多。 本人裁剪衣服，先用纸剪好。 第一章：线性规划（4） 应用四例? 企业 下料问题： 按需下料 废料最少 原材料7.4米 产品2.9米 产品2.1米 产品1.5米 第一章：线性规划（4） 应用四例? 第一章：线性规划（4） 应用四例? 例1 下料问题 用长度为７.４m的圆钢截断成制造某种机床所许的三个轴坯，长度分别为2.9m,2.1m,1.5m。现需要１００台机床。建立线性规划模型以寻求最佳的截断方案所需圆钢最少。 我们设Ｘj为第