第三章_线性规划的对偶理论.pdf

第第第第 三三三三 章章章章 对对 偶偶 理理 论论 (Duality Theory) 线性规划线性规划对偶问题的提出对偶问题的提出 线性规划线性规划的矩阵表示的矩阵表示 对偶问题的性质对偶问题的性质 对偶单纯形法 灵 敏 度 分 析 应用实例 11 第一节第一节第一节第一节 对偶规划问题对偶规划问题对偶规划问题对偶规划问题 一、一、对偶问题的基本概念对偶问题的基本概念对偶问题的基本概念对偶问题的基本概念 1.1.对偶现象对偶现象对偶现象对偶现象：：事物的两面性事物的两面性事物的两面性事物的两面性。。 例如：例如： （（（（1111）））） ““在周长在周长在周长在周长一一定的四边形中定的四边形中定的四边形中定的四边形中，，以正方形的以正方形的以正方形的以正方形的 面积最大。”面积最大。” （（（（2222 ）））） ““在面积在面积在面积在面积一一定的四边形中定的四边形中定的四边形中定的四边形中，，以正方形的以正方形的以正方形的以正方形的 周长最小。”周长最小。” 这是这是这是这是一一个现象的两个提法个现象的两个提法个现象的两个提法个现象的两个提法，，我们称这两我们称这两我们称这两我们称这两 种情况互为对偶，其中一个问题为原问题，种情况互为对偶，其中一个问题为原问题， 另外另外另外另外一一个问题为原问题的对偶问题个问题为原问题的对偶问题个问题为原问题的对偶问题个问题为原问题的对偶问题。。。。 22 22..对偶问题：对偶问题： 例例例例11--1 1 某制药厂用甲某制药厂用甲某制药厂用甲某制药厂用甲、、、、乙两台机器生产乙两台机器生产乙两台机器生产乙两台机器生产AA、、、、BB两种药物两种药物两种药物两种药物。。。。每种药每种药每种药每种药 物要经过两道工序，在甲机器上搅拌，在乙机器上包装。已知物要经过两道工序，在甲机器上搅拌，在乙机器上包装。已知 在未来两周内，甲、乙两台机器的使用时间分别不得超过在未来两周内，甲、乙两台机器的使用时间分别不得超过4040小小 时和时和时和时和3030小时小时小时小时，，生产每公斤药物生产每公斤药物生产每公斤药物生产每公斤药物AA的利润是的利润是的利润是的利润是3030元，元，BB是是是是2525元。元。生产生产生产生产 每公斤药物所需的加工时间如表所示：每公斤药物所需的加工时间如表所示： 试问试问试问试问，，如何安排这两周的生产如何安排这两周的生产如何安排这两周的生产如何安排这两周的生产，，能使工厂利润最大能使工厂利润最大能使工厂利润最大能使工厂利润最大？？？？ 药物药物 甲加工时间甲加工时间 乙加工时间乙加工时间 利润利润 （（（（公斤公斤公斤公斤）））） （（（（小时小时小时小时）））） （（（（小时小时小时小时）））） （（（（元元元元）））） AA 22 33 3030 BBBB 4444 2222 限制时间限制时间 4040 3030