1、Operations Research Prof. Wang School of Economics & Managementpage 1*第二讲第二讲 (1) 线性规划及其对偶对偶特性是线性规划的最重要特征，有人称对偶是线性规划的心脏，本书将把对偶问题贯彻于线性规划之始终。 1 对偶问题的现实来源2 原问题与对偶问题的对应关系3 线性规划的规范型4 对偶规划规范型及其转换5 线性规划的标准型及其转换Operations Research Prof. Wang School of Economics & Managementpage 2*第二讲1 对偶问题的现实来源（ 1）q 设某工厂生产两种
2、产品甲和乙，生产中需 4种设备按 A， B，C， D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于表。 表 1 产品数据表 设备产 品A B C D产 品利 润（元件） 甲 2 1 4 0 2乙 2 2 0 4 3设备 可利用机 时 数（ 时） 12 8 16 12Operations Research Prof. Wang School of Economics & Managementpage 3*第二讲1 对偶问题的现实来源（ 2）1、问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？试列出相应线性规划数学模型。设，甲及乙型产品各生产
3、 x1及 x2件，则数学模型为： 2x1 2x2 12x1+2x2 8 ( 机时限制 )4x1 164x2 12xj0 j=1,2 (变量限制，产品量必为正 ) 2x1 3x2 max （ 目标函数，使利润最大）Operations Research Prof. Wang School of Economics & Managementpage 4*第二讲1 对偶问题的现实来源（ 3）2、反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那未种机器的机时如何定价才是最佳决策？ 也许有人会马上回答，定价愈高，收益愈大，故必是最佳决策。然而这是错误的，因为定价太高，势
4、必失去顾客，从而也必减少收益，在市场竞争的时代，厂长的最佳决策显然应符合两条：（ 1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。Operations Research Prof. Wang School of Economics & Managementpage 5*第二讲1 对偶问题的现实来源（ 4）（ 2） 竞 争性原 则 ，即在上述不吃 亏 原 则 下，尽量降低机 时总 收 费 ，以便争取更多用 户 。 设 A、 B、 C、 D设备 的机 时 价分 别为 y1、 y2、 y3、 y4， 则 新的 线 性 规 划数学模型 为
5、： （不吃亏原则）yj 0， j=1,2,3,4 （ 定价必为正）(目标函数，使收费最低) Operations Research Prof. Wang School of Economics & Managementpage 6*第二讲1 对偶问题的现实来源（ 5）把同种问题的两种提法所获得的数学模型用表 2表示，将会发现一个有趣的现象。表 2 原问题与对偶问题对比表 A（ y1） B（ y2）C（ y3） D（ y4） 甲（ x1） 2 1 4 0 2乙（ x2） 2 2 0 4 312 8 16 12 minmax z 表 2，直接去看是原问题，将它转 900看便是对偶问题。当然，对偶是
6、相互的，若把表转 900看成是问题，则原表亦可看成是相应的对偶问题。Operations Research Prof. Wang School of Economics & Managementpage 7*第二讲2原问题与对偶问题的对应关系 （ 1）1、原问题表达式 (结合实例 )，不对称 例如，给定一线性规划为 (约束 )x10， x2 0， x3 0(目标函数 )写成矩阵形式为 Operations Research Prof. Wang School of Economics & Managementpage 8*第二讲2原问题与对偶问题的对应关系 （ 2）其中， Operations
7、 Research Prof. Wang School of Economics & Managementpage 9*第二讲2原问题与对偶问题的对应关系 （ 3）2、相应的对偶问题表达式为： （约束）y1， y2不限制（目标函数）写成矩阵形式 Operations Research Prof. Wang School of Economics & Managementpage 10*第二讲2原问题与对偶问题的对应关系 （ 4）其中， 由此例看出，线性规划 AX=b， X 0 ， 的对偶问题，即为 ， 。 3、原问题与对偶问题的转换，对称若把上例原问题的约束条件由等式变为不等式，则对偶问题的自变量取值由无限制变为有限制，即原问题变为（约束）（目标函数）
