§、对偶线性规划2、对偶理论3、对偶单纯形法对偶理论是线性规划最重要的内容之一;每一个线性规划问题必然有与之相伴的另一个线性规划问题,一个称为“原始”的,记为(P),另一个称为“对偶”的,记为(D);这两个问题有非常密切的关系;研究问题:一、给定LP问题(P)后,如何写出(P)的对偶问题(D)?二、问题(P)与问题(D)有什么关系?三、对偶单纯形法例1某企业计划生产甲、乙两种产品,这两种产品均需在A、B、C三种不同设备上加工。每单位产品所耗用的设备工时、单位产品利润及各设备在某计划期内的工时限额如下表。试问应如何安排生产计划,才能使企业获得最大利润?、乙产品,而将设备A,B,C租赁出去,该企业如何确定单位设备工时的租赁费?设该企业租赁设备A,B,C的单位工时租赁费分别为w1,w2,w3①原拟用于生产甲产品的A,B,C的工时分别为1,1,0个单位,创造利润3,所以租赁各设备上述数量的工时所得到的租赁费起码不少于3②与①类似原拟用于生产乙产品的A,B,C的工时分别为1,2,2个单位,创造利润4,所以租赁各设备上述数量的工时所得到的租赁费起码不少于4③将原拟用于生产甲、乙产品的三种设备的全部工时租赁后可获全部租赁收入显然y越大越好,但不能要求目标函数为maxy这将导致y趋于无穷,无法把设备租出因此所求的是与自己生产甲、乙产品的最优情况效果相比的租价,≤原始问题(LP)minz=. Ax≥b x≥0对偶问题(DP)maxy=≤c w≥0≥minbAcTcATbT≤maxnm对称形式的对偶(规范形)nx≥0mw0≥课本P46
对偶性及对偶单纯形法课件 来自淘豆网m.daumloan.com转载请标明出处.
