[自然科学]1-线性规划基本概念.pptVIP

练习 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？ 线性规划模型的建立 建立相应的线性规划模型 ：其中的 称为决策变量。 线性规划模型的标准形式 x2 50 40 30 20 10 10 20 30 40 x1 2x1+x2 ? 50 4x1+3x2 ? 120 可行域 同时满足： 2x1+x2 ? 50 4x1+3x2 ? 120 x1 ? 0 x2 ? 0 的区域——可行域 x2 50 40 30 20 10 10 20 30 40 x1 可行域 O（0，0） Q1（25，0） Q2（15，20） Q3（0，40） 可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。 该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以z作为参数的一组平行线 x2 = z/30-（5/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当z值不断增加时，该直线 x2 = z/30-（5/3）x1 沿着其法线方向向右上方移动。 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时，z（目标函数）值达到最大： Max z=50?15+30 ? 20=1350 此时最优解=（15，20） Q2（15，20） 二个重要结论： 最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。 解的讨论： 最优解是唯一解； 无穷多组最优解： 例1.1的目标函数由 max z=50x1+30x2 变成： max z=40x1+30x2 s.t. 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是同约束条件：4x1+3x2 ? 120平行的直线 x2 = z/30-（4/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当z的值增加时，目标函数同约束条件：4x1+3x2 ? 120 重合，Q1与Q2之间都是最优解。 Q1（25，0） Q2（15，20） 解的讨论： 无界解： 例：max z=x1+x2 s.t. -2x1+x2 ? 40 x1-x2 ? 20 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。 解的讨论： 无可行解： 例：max z=2x1+3x2 s.t. x1+2x2 ? 8 x1 ? 4 x2 ? 3 -2x1+x2 ? 4 x1,x2 ? 0 该问题可行域为空集，即无可行解，也不存在最优解。 解的情况： 有可行解 有唯一最优解 有无穷最优解 无最优解 无可行解 线性规划问题解的概念 线性规划标准型的矩阵形式： Max z = CX （1）