第三章线性规划的对偶理论李超
第三章 线性规划的对偶理论 李超
第三章线性规划的对偶理论第一节对偶规划问题第二节对偶理论第三节对偶单纯形法第四节灵敏度分析第五节应用实例
第三章 线性规划的对偶理论 第一节 对偶规划问题 第二节 对偶理论 第三节 对偶单纯形法 第四节 灵敏度分析 第五节 应用实例
第一节对偶规划问题一、对偶问题的提出[例11在第二章例1中我们建立了求A、B两种药物的产量实现最大利润的线性规划模型。现在从另外一个角度来讨论这个问题。若第二章例1中制药厂的设备都用于外协加工，即该厂的决策者不是考虑自己生产甲、乙两种产品，而是利用厂里的现有资源用于接受外来加工任务，将甲、乙两台设备出租给某公司使用，制药厂只收取租赁费或加工费。试问：设备甲、乙每工时各应如何收费才最有竞争力？
第一节 对偶规划问题 一、对偶问题的提出 [例1]在第二章例1中我们建立了求A、B两种药物 的产量实现最大利润的线性规划模型。现在从另 外一个角度来讨论这个问题。若第二章例1中制 药厂的设备都用于外协加工，即该厂的决策者不 是考虑自己生产甲、乙两种产品，而是利用厂里 的现有资源用于接受外来加工任务，将甲、乙两 台设备出租给某公司使用，制药厂只收取租赁费 或加工费。试问：设备甲、乙每工时各应如何收 费才最有竞争力？
·分析问题：1、每种资源收回的费用不能低于自已生产时的可获利润;2、定价又不能太高，要使对方能够接受，设y1，y2分别为出租资源设备甲、乙每工时收取的费用。（租金额最小）Min w = 40yi+ 30y2（药物A的租金不少于药物A的利润S.t. 2yi+3y2 >304yi+2y2 >25（药物B的租金不少于药物B的利润Yi, y2,> 0
• 分析问题： • 1、每种资源收回的费用不能低于自己生产时的可获 利润； • 2、定价又不能太高，要使对方能够接受。 • 设 y1 ，y2 分别为出租资源设备甲、乙每工时收取的 费用。 Min w = 40y1+ 30y2 (租金额最小） s.t.2y1+3y2 ≥30 （药物A的租金不少于药物A的利润） 4y1+2y2 ≥25 （药物B的租金不少于药物B的利润） y1, y2 ,≥ 0
30x1+25x2Maxz= :40s. t.2xi + 4x2<原问题3x1 + 2x2< 300X1 ,X2 >Min w =40yi+ 30y2s. t. 2yi+3y2 >30对偶问题4yi+2y2>250yi,y2，>每一个线性规划（LP）必然有与之相伴而生的另一个线性规划问题，其中的一个问题叫“原问题”，记为“LP”，另一个称为“对偶问题”，记为“DP
• Max z = 30x1 + 25x2 s.t. 2x1 + 4x2 ≤ 40 3x1 + 2x2 ≤ 30 原问题 x1 ,x2 ≥ 0 Min w = 40y1+ 30y2 s.t. 2y1+3y2 ≥30 4y1+2y2 ≥25 对偶问题 y1, y2 , ≥ 0 • 每一个线性规划（ LP ）必然有与之相伴而生 的另一个线性规划问题，其中的一个问题叫 “原问题”，记为“LP”，另一个称为“对偶问 题”，记为“DP