第三章 规划和优化模型.ppt

分别设 、 表示在计划期内产品I、II的产量，建立该问题的数学模型为： 第三章 线性规划 数据、模型与决策 (第二版) 将其转换为标准型为： （4） （5） 第三章 线性规划 数据、模型与决策 (第二版) 确定初始可行基和基可行解 由式（5）可得 ， 和 对应的系数列向量线性无关，因此，取可行基： 则 ， 和 为基变量， ， 为非基变量。 将基变量和目标函数用非基变量表示为： （6） （7） 当非基变量 ， 时，得到基可行解 ，此时， ，即Keku公司未生产任何产品，其利润为0。 第三章 线性规划 数据、模型与决策 (第二版) 确定换入变量 在目标函数式（6）中，非基变量 ， 的系数都是正数，因此，不管以谁作为换入变量都能使目标函数值增大，其经济意义为安排生产任一种产品都可以增加Keku公司的利润。我们选择系数较大的 作为换入变量。 确定换出变量 选择 作为换入变量后，必须从 ， 和 中确定一个换出变量。 解 （令 ），得到 解 （令 ），得到 为保证所有变量的非负性，故 ，此时， 为换出变量。这种确定换出变量的规则称为 规则。 第三章 线性规划 数据、模型与决策 (第二版) 重复上述过程，可得最优解 结论： Keku公司应生产4件产品I和2件产品II，共可获得利润14元。 第三章 线性规划 数据、模型与决策 (第二版) 第三章 线性规划 3.1 线性规划问题概述 3.2 线性规划问题的图解法 3.3 单纯形法 3.4 对偶问题 3.5 敏感性分析 第三章 线性规划 数据、模型与决策 (第二版) 3.4 对偶问题 3.4.1 原问题与对偶问题的关系 3.4.2 举例说明 第三章 线性规划 数据、模型与决策 (第二版) 3.4.1 原问题与对偶问题的关系 求原问题的对偶问题的步骤： （1）如约束条件中有“ ”的情况，将其转换成“ ”，使得所有约束条件全部变成“ ”或“=”的形式。 （2）如果原问题的目标函数是“ ”的形式，则 ①对偶问题的目标函数是“ ”的形式。 ②原问题的 n个变量对应于对偶问题中 n个约束条件。具体地， 若变量 的取值“ 0”，则对偶问题中第 i个约束条件为“ ”的不等式； 若变量 的取值“ 0”，则对偶问题中第 个约束条件为“ ”的不等式； 若变量 无约束，则对偶问题中第i 个约束条件为等式。 ③原问题的 m个约束条件对应于对偶问题中 m个变量。具体来讲， 若第i 个约束条件是“ ”的不等式，则变量 的取值“ 0”； 若第i 个约束条件为等式，则变量 无约束。 第三章 线性规划 数据、模型与决策 (第二版) （3）如果原问题的目标函数是“ ”的形式，则 ①对偶问题的目标函数是“ ”的形式。 ②原问题的 n个变量对应于对偶问题中n 个约束条件。具体地， 若变量 的取值“ 0”，则对偶问题中第 i个约束条件为“ ”的不等式； 若变量 的取值“ 0”，则对偶问题中第i 个约束条件为“ ”的不等式； 若变量 无约束，则对偶问题中第 i个约束条件为等式。 ③原问题的m 个约束条件对应于对偶问题中m 个变量。具体来讲， 若第 i个约束条件是“ ”的不等式，则变量 的取值“ 0”； 若第 i个约束条件为等式，则变量 为无约束。 （4）在原问题和对偶问题中，将 的位置进行对换；对偶问题的约束系数矩阵是原问题中 的转置，即 。 第三章 线性规划 数据、模型与决策 (第二版) 3.4.2 举例说明 写出下面线性规划的对偶规划模型 第三章 线性规划 数据、模型与决策 (第二版) 首先对原规划的约束条件进行变形，可转化为： 第三章 线性规划