(4.1.1)--线性规划的对偶模型（NO7）.pdf

1 运运 筹筹 学学 第七讲第七讲 线性规划的对偶模型线性规划的对偶模型 2 对偶理论是线性规划发展中最重要的成果之一，对偶理论是线性规划发展中最重要的成果之一，该理论认为每一个线性规划问题该理论认为每一个线性规划问题(称为原始问题称为原始问题)都有一个与它对应的对偶线性规划问题（称为对都有一个与它对应的对偶线性规划问题（称为对偶问题）。如果原问题是在给定的资源下，如何偶问题）。如果原问题是在给定的资源下，如何安排生产，才能获得最大收益；则对偶问题是从安排生产，才能获得最大收益；则对偶问题是从出让资源的角度来考虑问题，即如果不生产而将出让资源的角度来考虑问题，即如果不生产而将给定的资源出让，则出让资源如何定价，才能使给定的资源出让，则出让资源如何定价，才能使接受资源的决策者的付出最小（此时其实也是生接受资源的决策者的付出最小（此时其实也是生产者获得最大的收益）。产者获得最大的收益）。线性规划的对偶模型线性规划的对偶模型 3 例例(生产计划问题）生产计划问题）:某个工厂生产甲、乙两种产品。每件某个工厂生产甲、乙两种产品。每件产品的利润、所消耗的材料、工时及每天的材料限额，如产品的利润、所消耗的材料、工时及每天的材料限额，如下表所示下表所示.试问如何安排生产试问如何安排生产,使每天所得的利润为最大使每天所得的利润为最大?甲甲 乙乙 限额限额 材料材料 2 3 24 工时工时 3 2 26 利润利润(元元/件件)4 3 线性规划的对偶模型线性规划的对偶模型 1.问题的提出问题的提出 0,)(2623)(2432.t.s34Zmaxxxxxxxxx21212121工时约束材料约束从企业最优生产的角度从企业最优生产的角度建立的线性规划模型为：建立的线性规划模型为：4 例例(生产计划问题）生产计划问题）:某个工厂生产甲、乙两种产品。每件某个工厂生产甲、乙两种产品。每件产品的利润、所消耗的材料、工时及每天的材料限额，如产品的利润、所消耗的材料、工时及每天的材料限额，如下表所示下表所示.试问如何安排生产试问如何安排生产,使每天所得的利润为最大使每天所得的利润为最大?甲甲 乙乙 限额限额 材料材料 2 3 24 工时工时 3 2 26 利润利润(元元/件件)4 3 线性规划的对偶模型线性规划的对偶模型 1.问题的提出问题的提出 现从另一角度考虑此问题。假设有客现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时，由客户支付工时费和材料费，此时工厂应考虑如何为每种资源定价，同工厂应考虑如何为每种资源定价，同样使其获得的利润最大？样使其获得的利润最大？0,323432.t.s2624Wminyyyyyyyy212121215 解解:1)决策变量：决策变量：设设y1,y2分别表示出售单位原材料的价格（分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金含附加值）和出租设备单位工时的租金 3)约束条件约束条件:工厂决策者考虑：工厂决策者考虑：（1）出售原材料和出租设备应不少于自己生产产品的出售原材料和出租设备应不少于自己生产产品的获利获利，否则不如自己生产为好否则不如自己生产为好。因此有因此有 2）目标函数：）目标函数：此时工厂的总收入为此时工厂的总收入为W=24y1+26y2,这也是这也是租赁方需要付出的成本租赁方需要付出的成本.而在这个问题中而在这个问题中,是企业不生产是企业不生产,将将自己的资源出售或出租自己的资源出售或出租,因此因此,此时此时,起决定作用的是租赁方起决定作用的是租赁方,所以此时的目标函数为所以此时的目标函数为 Min W=24y1+26y2 323432yyyy21216（2）价格应尽量低价格应尽量低，否则没有竞争力否则没有竞争力（此价格可成为与客此价格可成为与客户谈判的底价户谈判的底价）租赁者考虑：希望价格越低越好，否则另找他人。租赁者考虑：希望价格越低越好，否则另找他人。于是，能够使双方共同接受的是于是，能够使双方共同接受的是：0,323432.t.s2624Wminyyyyyyyy212121217 0262324323421212121xxxxxxxxtsZ,.max0,323432.t.s2624Wminyyyyyyyy21212121 上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。LP DP 8 例例2：设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：产品数据表产品数据表 设备 产品 A B C D 产品利润（元件）甲 2 1 4 0 2 乙 2 2 0 4 3 设备可利用机时数（时）12 8 16 12 问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？获得最大利润？我们再来看一个实际问题我们再来看一个实际问题 9 解：解：设甲、乙型产品各生产x1及x2件，则数学模型为：0,124164821222.32max2121212121xxxxxxxxtsxxz反过来问：若厂长决定不生产甲和乙型产品，决定出租机器反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？价才是最佳决策？10 在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。设设A、B、C、D设备的机时价分别为设备的机时价分别为y1、y2、y3、y4，则新的线性，则新的线性规划数学模型为：规划数学模型为：0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy11 一般地对于任何一个线性规划问题都有一个与之相对应的一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：对偶问题。原问题与对偶问题的一般形式为：0.t.sZmaxxbxaxaxabxaxaxabxaxaxaxcxcxcjmnmn22m11m2nn22221211nn1212111nn22110.t.sWminycyayayacyayayacyayayaybybybinmmn2n21n12m2m2221121m1m221111mm2211 原问题（原问题（LP）相应的矩阵形式为：0XbAX.t.sCXZmax0YCYA.t.sYbWmin对偶问题（对偶问题（DP）12 对称形式的对偶问题为：对称形式的对偶问题为：0XbAX.t.sCXZmax（LP）0YCYA.t.sYbWmin（DP）二、二、原问题与对偶问题的关系原问题与对偶问题的关系 由以上两式可知由以上两式可知,原问题与对偶问题之间具有如下关系原问题与对偶问题之间具有如下关系(1)一个问题中的约束条件个数等于它的对偶问题中的变量一个问题中的约束条件个数等于它的对偶问题中的变量数数;(2)一个问题中目标函数的系数是其对偶问题中约束条件的一个问题中目标函数的系数是其对偶问题中约束条件的右端项右端项;(3)约束条件在一个问题中为“约束条件在一个问题中为“”,则在其对偶问题中为“则在其对偶问题中为“”;(4)目标函数在一个问题中为求最大值目标函数在一个问题中为求最大值,在其对偶问题中则为在其对偶问题中则为求最小值求最小值 13 非对称形式的对偶问题为：非对称形式的对偶问题为：（LP）0XbAX.t.sCXZmax（DP）无约束YCYA.t.sYbWmin推导过程如下：推导过程如下：原模型变化为原模型变化为 0.0.maxmaxXbAXbAXtsXbAXbAXtsCXZCXZ根据对称对偶关系，根据对称对偶关系，写出其相应的对偶问写出其相应的对偶问题题 无约束YCYAtsYYCAYYtsYYCAYAYtsYbWbYYWbYbYW.0,)(.0,.min)(minmin令令 YYY 14 原问题Max（对偶问题）对偶问题Min（原问题）约束条件数=m 变量个数=m 第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个变量0 第i个变量0 第i个变量无限制 变量个数=n 约束条件个数=n 第i个变量0 第i个变量0 第i个变量无限制 第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个约束条件的右端项 目标函第i个变量的系数 目标函数第i个变量的系数 第i个约束条件的右端顶 归纳对称形式与非对称形式的对偶归纳对称形式与非对称形式的对偶,原问题与对偶问题之间原问题与对偶问题之间的关系如下表所示的关系如下表所示 15 例例3 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 1231323123min4121833.2250 W，yyyyystyyyyy1231323123max4121833.2250 W，yyyyystyyyyy转化为一般形式 12121212min354212.32180Zxxxxs txxxx ，写出对偶问题 12121212max354212.32180Zxxxxs txxxx ，整理为原问题的对偶问题 LP DP 16 例例4 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 解：其对偶模型为：12312312323123min7424262436415.53100,0Zxxxxxxxxxstxxxxx 无无约约束束，12312123123123maxW2415104372654.64320,0,yyyyyyyystyyyyyy 无约束17 练习：练习：写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 0,5637325.52max3213132132132132xxxxxxxxxxxxxxtsZ解：其对偶模型为：056751323253232132121321321yyyyyyyyyyytsyyyW,.min18 无约束xxxxxxxxxxxxxxxxxx432143243143214321,0,06822103.t.s423Zmin练习：练习：写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 解：其对偶模型为：无约束32132132131213210014232326810yyyyyyyyyyyyytsyyyW,.max19 敬请指教！谢谢！