线性规划问题的对偶问题

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

1、2、线性规划问题的对偶问题例2．1胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？2.1对偶问题数学模型maxg=50x1+30x2s.t.4x1+3x2120(2.1)2x1+x250x1,x20假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工

2、和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：mins=120y1+50y2目标函数中的系数120，50分别表示可供出租的木工和油漆工工时数。该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：4y1+2y2503y1+y230y1,y2

3、0得到另外一个数学模型：mins=120y1+50y2s.t.4y1+2y250(2.2)3y1+y230y1,y20模型(2.1)和模型(2.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。如果模型(2.1)称为原问题，则模型(2.2)称为对偶问题。任何线性规划问题都有对偶问题，而且都有相应的意义。例2.2：常山机器厂生产Ⅰ、Ⅱ两种产品，

4、按工艺资料获得如下资料：ⅠⅡ设备能力设备A2h2h12h设备B4h0h16h设备C0h5h15h单位利润（元）23问该企业因安排生产两种产品各多少件，使总的利润收入为最大？数学模型maxZ=2x1+3x2s.t.2x1+2x2124x1165x215x1,x20现某机械厂为扩大生产租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备？设常山厂将设备A、B、C每h的出租价格为y1,y2,y3;它的对偶问题为minw=12y1+16y2+15y32y1+4y2≥22y1+5y3≥3y1

5、,y2,y3≥0把例2.2用矩阵表示：对偶问题原问题:Maxz=(2,3)线性规划的对偶关系：（I）Maxz=Cxs.t.Axb（2.3）x0(II)Minw=b’ys.t.A’yC’（2.4）y0（2.3)(2.4)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。例2-3：写出下列线性规划问题的对偶问题minw=12x1+8x2+16x3+12x4s.t.2x1+x2+4x322x1+2x2+4x43x1，x2，x3，x40解：该问题的对偶问题：maxz=2y1+3y2s.t.2y1+2y

6、212y1+2y284y1164y212y1，y20例2-4：写出下列线性规划问题的对偶问题maxS=10x1+x2+2x3s.t.X1+x2+2x310y14x1+2x2-x320y2x1，x2，x30解：该问题的对偶问题：ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y20例2-5：写出下列线性规划问题的对偶问题minS=x1+2x2+3x3s.t.2x1+3x2+5x323x1+x2+7x33x1，x2，x30解：用（-1）乘以第二个约束方程两

7、边minS=x1+2x2+3x3s.t.2x1+3x2+5x32y1-3x1-x2-7x3-3y2x1，x2，x30该问题的对偶问题：maxz=2y1-3y2s.t.2y1-3y213y1-y225y1-7y23y1，y20例2-6：写出下列线性规划问题的对偶问题minS=2x1+3x2-5x3s.t.x1+x2-x352x1+x3=4x1，x2，x30解：将原问题的约束方程写成不等式约束形式：minS=2x1+3x2-5x3x1+x2-x35y12x1+x34y2’-2x1-x3-4y2”x1

8、，x2，x30引入变量y1,y2’，y2”写出对偶问题maxg=5y1+4y2’-4y2”s.t.y1+2y2’-2y2”2y13-y1+y2’-y2”-5y1，y2’，y2”0令y2=y2’-y2”得到maxg=5y1+4y2s.t.y1+2y22y13-y1+y2-5y10，y2无非负约束此类问题称为非对称型