线性规划对偶理论与方法

《线性规划对偶理论与方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学（operationsresearch,OR）第四讲线性规划对偶理论与方法商学院电子商务系7/25/20211第四讲线性规划对偶理论与方法一.对偶问题的提出二.写对偶问题三.对偶问题的性质四.对偶单纯形法7/25/20212一、对偶问题的提出第四讲线性规划对偶理论与方法什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。有诗为证：窗含西岭千秋雪，门泊东吴万里船。有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。7/25/20213第四讲线

2、性规划对偶理论与方法一、对偶问题的提出对例1从对偶的角度进行表述。假设该工厂的决策者决定不生产产品甲、乙，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出让单位原材料和出租生产设备A，B生产台时的租金的收益。在做决策时，做如下比较：若生产一件产品甲，可获利3元，那么生产每件产品甲的设备台时和原材料出租或出让的所有收入应不低于生产一件产品甲的利润，这就有y1+4y2≥3.7/25/20214第四讲线性规划对偶理论与方法一、对偶问题的提出对例1从对偶的角

3、度进行表述。同理将生产每件产品乙的设备台时和原材料出租或出让的所有收入应不低于生产一件产品乙的利润，这就有：2y1+4y3≥3把工厂所有设备台时和资源都出租或出让，其收入为：w=8y1+16y2+12y37/25/20215第四讲线性规划对偶理论与方法一、对偶问题的提出例1的对偶数学模型为：minw=8y1+16y2+12y3y1+4y2≥32y1+4y3≥4yi≥0，i=1,2,37/25/20216第四讲线性规划对偶理论与方法一、对偶问题的提出从数学逻辑上提出对偶问题由前可知检验数的表达式是：CN−CB

4、B-1N与−CBB-1即：包含所有变量在内的检验数为：C−CBB-1A将Y=CBB-1两边右乘b，得到:Yb=CBB-1b=z因Y的上界为无限大，所以只存在最小值。令：Y=CBB-1，称Y为单纯形乘子，由最优解的判定条件可得：Y≥0即：C−CBB-1A=C−YA≤0YA≥C7/25/20217第四讲线性规划对偶理论与方法一、对偶问题的提出从数学逻辑上提出对偶问题从这里可以得到另一个线性规划问题:minw=YbYA≥CY≥0称为原线性规划问题｛maxz=CX｜AX≤b，X≥0｝的对偶规划问题。7/25/202

5、18第四讲线性规划对偶理论与方法二、写对偶问题标准型对偶关系对偶7/25/20219第四讲线性规划对偶理论与方法二、写对偶问题规范形式原问题与对偶问题变换规则观察分析上述规范形式下线性规划的原问题及其对偶问题的模型形式，可发现，按如下规则，可从线性规划原问题得到其对偶问题：（3）对偶问题约束为≥型，有?行；（1）目标函数由max型变为min型；（2）对应原问题，每个约束行有一个对偶变量;（4）原问题的价值系数C变换为对偶问题的右端项；（5）原问题的右端项b变换为对偶问题的价值系数；（6）原问题的系数矩阵A转

6、置后成为对偶问题的系数矩阵。根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。7/25/202110第四讲线性规划对偶理论与方法二、写对偶问题标准型原问题与对偶问题的关系7/25/202111第四讲线性规划对偶理论与方法二、写对偶问题标准型原问题与对偶问题的关系例2根据下表写出原问题与对偶问题的表达式xyx1x2by112≤8y240≤16y304≤12c≥3≥47/25/202112第四讲线性规划对偶理论与方法二、写对偶问题标准型原问题与对偶问题的关系原问题（LP）对偶问题(DP)对偶7/25/

7、202113第四讲线性规划对偶理论与方法二、写对偶问题练习题练习1、写出下列线性规划问题的对偶问题7/25/202114第四讲线性规划对偶理论与方法二、写对偶问题非标准型对偶关系原问题的约束条件中含有等式约束条件时，按以下步骤处理：设等式约束条件的线性规划问题为：第一步：先将等式约束条件分解为两个不等式约束条件7/25/202115第四讲线性规划对偶理论与方法二、写对偶问题非标准型对偶关系第二步：按对称形式变换关系可写出它的对偶问题设yi′，yi″是对应上式的对偶变量，i=1,2,…，m7/25/20211

8、6第四讲线性规划对偶理论与方法二、写对偶问题非标准型对偶关系将上述规划问题的各式整理后得到：7/25/202117第四讲线性规划对偶理论与方法二、写对偶问题线性规划的原问题与对偶问题的关系可表示为：7/25/202118第四讲线性规划对偶理论与方法二、写对偶问题例题写出下列线性规划问题的对偶问题7/25/202119第四讲线性规划对偶理论与方法二、写对偶问题练习题17/25/202120第四讲线性规划对偶理论与方