简单回顾(1.0).ppt

简单回顾(One) 前五章 线性规划 1 建模 2 化标准形式 3 图解法 4 单纯形法 5 大M法及两阶段法 1 建模 1.融会贯通地理解要解决的问题，要搞清在什么条件下，要追求什么目标。 2.定义决策变量，每一个问题都用一组决策变量表示某一方案;这组决策变量的值就代表一个具休方案，一般这些变量取值是非负的。 根据题意确定变量(主要是根据目标的表达方式，兼顾题目中的其他条件); 3.用决策变量的线性函数形式写出所要追求的目标，称之为目标函数，按问题的不同，要求目标函数实现最大化或最小化。 4.用一组决策变量的等式或不等式来表示在解决问题过程上所必须遵循的约束条件。 5.确定变量的取值约束 例题 某工厂生产甲、乙两种产品，表中给出了生产每一单位产品对三种设备A、B、C台时数的需求量以及创造的利润，同时给出三种设备可用台时数的限量，问如何在现有的条件限制下确定两种产品的产量，使总利润最大？ 解答 解：设生产甲乙产品的产量分别为件，则由题意得： 2 化标准形式 目标函数－求极大值； 约束条件全为等式； 约束条件右端常熟项bi全为非负； 变量取值全为非负。 (1)目标函数为求极小值的情形： (2)约束条件为不等式的情形： (3)约束条件右端项小于0时的情形： (4)取值无约束的变量的情形： (5)当x0时的情形： 例题 化为标准形式 求解 3 图解法 只能解决两个变量的问题 首先建立坐标系 画出约束方程 画出关于目标函数的直线（族） 平移目标函数直线找到最有解 例题 用图解法求解下列线性规划问题。 求解 解：①根据题意，可以找到可行域如图所示： 求解 ②图示目标函数，求最优解。如图虚线所示，目标函数是一组平行的等值线： 4 单纯形法（大M法or两阶段法） 1 首先将线性规划化为标准行使 2 根据需要添加人工变量 3 列出单纯形表（初始） 4 计算检验数 如果某检验数大于0且其对应的列向量分量全部小于等于0，则停止计算，问题为无界解； 如果检验数全部小于等于0而且人工变量全部等于0，则已求得最有解；且如果某非基变量的检验数等于，且其对应的列向量分量有大于0的，则该问题有无穷多最有解； 如果检验数全部小于等于0而人工变量存在不等于0的情况，则问题为无解； 如果检验数大于0，则继续迭代； 5 进行初等行变换，计算下一基可行解，并返回4。 例题 用单纯形法求解线性规划问题。 求解 解：原问题的标准形式为: 求解 对应的单纯形表如下 求解 因为所有的检验数都小于等于0，所以已求得最优解 且 所以此线性规划问题有无穷多个最优解。其中一组为： 此时目标函数值最大，为6 对偶理论 原问题找对偶问题 影子价格的经济含义 对偶单纯形法（灵敏度分析） 灵敏度分析 1 原问题找对偶问题 例题 写出下面线性规划的对偶问题。 2 影子价格的经济含义 表示某种资源在当前的使用（生产）情况下，此种资源作出的贡献。 1 资源的影子价格会因企业生产任务、产品结构等情况的改变而改变。 2 影子价格是一种边际价格。 3 影子价格又是一种机会成本。 4 如果在生产过程中某种资源bi没有得到充分利用，则该种资源的影子价格为零；若某种资源的影子价格不为零，表明该种资源在生长过程种全部被利用。 5 当某种资源的影子价格高于市场价格时，企业应该买进该种资源用于扩大生产；相反，当市场价格高于企业的影子价格时，企业应该把该资源卖掉。 3 对偶单纯形法 参考单纯形法； 使用条件苛刻，一般不单独使用； 首先确定出基变量，然后确定入基变量。 例题 用对偶单纯形法求解下面的线性规划问题。 求解 解：(1)将线性规划化为标准形式。 (2)在约束方程组两边同时乘以－1得： 求解 列出单纯形表，并计算检验数，所有的检验数都小于等于零，所以可以利用对偶单纯形法求解。 4 灵敏度分析 1 将参数的改变通过计算反映到最终单纯形表中； 2 检查原问题是否仍为可行解； 3 检查对偶问题是否仍为可行解； 4 按照下面可能出现的各种情况分别进行处理。 例题 求解 解：首先将这种变化反映到单纯形表中（如果是B或者A的变化，写出步骤）； 运输问题 1 初始调运方案的确定 最小元素法；西北角法；沃格尔法 2 检验数的计算 闭回路法；位势法 3 调运方案的调整 闭回路法 4 产销不平衡问题的求解 虚拟一个产地（产求）或销地（产求） 5 有转运问题的求解（简单了解） 1 初始调运方案的确定 （1）首先确定第一条符合条件的路线（根据不同的方法）； （2）在这条路线上填入最大可能的调运量； （3）划去产量已经全部运出或销量全部运人的产地或销地（行or列），如果同时划去行和列，则在此行和列中随便选择一个在此步以前没有划去的空格填入0； （4）在剩余的路线中选择一条符合条件的路线，并进入步骤（2）。