《对偶问题的提出ppt课件.ppt》由会员分享，可在线阅读，更多相关《对偶问题的提出ppt课件.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对偶是什么对偶是什么：对同一事物（或问题），从不同的角度对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。（或立场）提出对立的两种不同的表述。例如：（例如：（1 1）周长一定，面积最大的矩形是正方形。）周长一定，面积最大的矩形是正方形。（2 2）面积一定，周长最短的矩形是正方形。）面积一定，周长最短的矩形是正方形。这是互为这是互为对偶关系对偶关系
2、的表述。的表述。这种表述有利于加深对事物的认识和理解。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。线性规划问题也有对偶关系。任何线性规划问题都有其对偶问题任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义对偶问题有其明显的经济含义 对偶性是线性规划问题的最重要的内容之一对偶性是线性规划问题的最重要的内容之一为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对偶问题概念：对偶问题概念：任何一个线性规划问题都有一个与之相对应任何一个线性规划问题都有一个与之相对应的另一个线性规划问题，的另一个线性规划问题，
3、如果前者称为如果前者称为原问题原问题，后者就称为，后者就称为“对偶对偶”问题问题。对偶问题是对原问题从另一角度进行的描述。对偶问题是对原问题从另一角度进行的描述。其最优解与原问题的最优解有着密切的联系其最优解与原问题的最优解有着密切的联系:在求得一个线性规划最优解的同时也就得到对偶线在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。理论，是线性规划理论的重要内容之一。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工
4、作人员聘用制度，保障用人单位和职工的合法权益 【例【例1 1】最优生产计划问题。】最优生产计划问题。某某工工厂厂在在计计划划期期内内要要安安排排生生产产、两两种种产产品品，已已知知生生产产单单位位产产品品所所需需的的设设备备台台时时及及A A、B B两两种种原材料的消耗，如表原材料的消耗，如表1-11-1所示。所示。该工厂每生产一件产品该工厂每生产一件产品可获利可获利2 2元，元，每生产一件产品每生产一件产品可获利可获利3 3元，元，问应如何安排计划使该工厂问应如何安排计划使该工厂获利最多获利最多?一一一一 对偶问题的提出对偶问题的提出对偶问题的提出对偶问题的提出为了规范事业单位聘用关系，建立
5、和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益数学模型数学模型 max z=2x max z=2x1 1+3x+3x2 2 s.t.x s.t.x1 1+2x+2x2 2 8 8 4x 4x1 1 16 16 4x 4x2 21212 x x1 1,x,x2 2 0 0设设 产量产量 产量产量如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家原问题原问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益设：设：出租设备出租设备 -y -y1 1元台时元台时 出让原材料出让原材料A-
6、yA-y2 2 元元/kg/kg 出让原材料出让原材料B-yB-y3 3元元kgkg 收购方收购方 付出的代价最小，付出的代价最小，且厂家能接受。且厂家能接受。厂家出让代价应不厂家出让代价应不低于用同等数量的资低于用同等数量的资源自己生产的利润。源自己生产的利润。假设该厂家决定假设该厂家决定不生产不生产产品产品、，而将其所有资源而将其所有资源出租或外售出租或外售。工厂的决策者就要考虑给每种资源如何定价的问题。工厂的决策者就要考虑给每种资源如何定价的问题。现从另一角度来讨论这个问题。现从另一角度来讨论这个问题。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度
7、，保障用人单位和职工的合法权益设设y y1 1,y y2 2和和y y3 3分别表示出租单位设备台时的分别表示出租单位设备台时的租金和出让单位原材料租金和出让单位原材料A,BA,B的附加额的附加额=8y1+16y2+12y3出售资源出售资源 对偶对偶 问题问题收购方的意愿：收购方的意愿：收购方的意愿：收购方的意愿：总的收购价越小越好总的收购价越小越好厂家能接受的条件厂家能接受的条件厂家能接受的条件厂家能接受的条件：出售资源后所得不应比出售资源后所得不应比 生产产品所得少生产产品所得少 目标函数目标函数 min单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低
8、于收入不低于3 3元元原问题原问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对对对对偶偶偶偶问问问问题题题题原原原原问问问问题题题题收收购购厂厂家家一对对偶问题一对对偶问题这表明：这表明：从不同角度考虑同一问题可得到相互联系的从不同角度考虑同一问题可得到相互联系的 线性规划模型，这就是线性规划的对偶问题线性规划模型，这就是线性规划的对偶问题 。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益两个模型两个模型 既有区别又有联系：既有区别又有联系：联系联系在
9、于它们都是在于它们都是LPLP模型并且使用相同的数据，模型并且使用相同的数据，区别区别在于模型反映的实质内容是不同的在于模型反映的实质内容是不同的模型模型(1)(1)是站在厂家经营者立场是站在厂家经营者立场,追求销售收入最大追求销售收入最大;模型模型(2)(2)则是站在厂家的对手收购者的立场则是站在厂家的对手收购者的立场,追求所付的租金最少追求所付的租金最少。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 特点：特点：1 1 2 2资源向量资源向量b b 价值向量价值向量C C 3 3一个约束一个约束 一个变量。一个变量。4
10、 4 的的LPLP约束约束“”“”的的 LP LP是是“”“”的约束。的约束。5 5变量都是非负限制。变量都是非负限制。6.A ATy1y2y3x1x2为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益加入松驰变量加入松驰变量化为标准形化为标准形将以上公式运用于初始单纯形表和迭代后以将以上公式运用于初始单纯形表和迭代后以B B为基为基的单纯形表中得到如下表格：的单纯形表中得到如下表格：设松弛变量对应的系数列向量占据设松弛变量对应的系数列向量占据A A 的后的后mm列，列，可行基可行基B B占据占据A A的前的前mm列，其余子块仍
11、用列，其余子块仍用NN来表示。来表示。二二二二 根据矩阵描述讨论对偶问题根据矩阵描述讨论对偶问题根据矩阵描述讨论对偶问题根据矩阵描述讨论对偶问题则有：则有：A=A=（A,I)=(B,N,I),C=(CA,I)=(B,N,I),C=(CB B,C,CN N,0),0)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益初始矩阵单纯形表初始矩阵单纯形表将将B B化为化为I I（I I为为mm阶单位矩阵）阶单位矩阵）,C CB B化为零化为零,求基可行解和检验数。求基可行解和检验数。用用B B1 1左乘表中第二行左乘表中第二行,得到迭代
12、后的表格：得到迭代后的表格：cjCBCN0系数系数基变量基变量解向量解向量XBXNXS0XSbBNICj-ZjCBCN0cjCBCN0系数系数基变量基变量解向量解向量XBXNXSCBXBB-1bIB-1NB-1Cj-Zj -CBB-1b0CN-CBB-1N-CBB-1为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益LPLP问题取得最优问题取得最优N N=C CN N-C-CB BB B-1-1N N 0非基变量中存在松弛变量时检验数：非基变量中存在松弛变量时检验数：s s=-C-CB BB B-1-1 0（1 1）令令Y=CY
13、=CB BB B-1-1为单纯形乘子为单纯形乘子（2-9）（2-10）由由(2-10)(2-10)可得：可得：-C-CB BB B-1-1=-Y=-Y0 0Y Y0 0（2 2）所有变量的检验数：所有变量的检验数：A A=C-C=C-CB BB B-1-1A A=C-YAC-YA00YAYA C对偶问题的对偶问题的约束条件约束条件非基变量的检验数：非基变量的检验数：(2-9)(2-9)式及式及(2-10)(2-10)式是作为得到最优解的判断条件。式是作为得到最优解的判断条件。对偶变量的对偶变量的非负条件非负条件cjCBCN0系数系数基变量基变量解向量解向量XBXNXSCBXBB-1bIB-1N
14、B-1Cj-Zj -CBB-1b0CN-CBB-1N-CBB-1为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益（4 4）得新的得新的LPLP问题问题（3 3）由由Y=CY=CB BB B-1-1，两边右乘两边右乘b b得得：YAYA CYb=CYb=CB BB B-1-1b b=Z=Z称为原有称为原有LPLP问题问题min=YbYbY Y0 0YbYb取值的上限不受限制，取值的上限不受限制，只有取极小值时，只有取极小值时，LPLP问题才有意义问题才有意义.的对偶问题的对偶问题.对偶问题对偶问题的的目标函数目标函数为了规范事业
15、单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例:它的对偶问题是它的对偶问题是：YAYA Cmin=YbYbY Y0 0Y Y=（y1，y2，y3）为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对偶的定义对偶的定义原始问题原始问题min f(x)=CTXs.t.AXbX 0对偶问题对偶问题max z(y)=bTYs.t.ATYCY0minbACTCATbTmaxmnmn为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一一般般规规律律