运筹学基础论文

《运筹学基础论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、运筹学基础论文单纯形乘子定理摘要：对偶理论是线性规划在早期发展中的重要成果之一，是线性规划的重要组成部分。对偶理论深刻揭示了原问题与对偶问题之间深刻的内在联系。对偶理论充分显示了线性规划理论逻辑的严谨和结构的对称美；对偶问题的对偶解是进行经济分析的重要工具。正确理解单纯形乘子定理；最优基B是什么，在单纯形表中如何找到；Y*=CB-*在单纯形表中的位置；原问题、对偶问题的最优值，在单纯形表中的确定；理解“对于原问题LP,其对偶问题DP的最优解就是LP最优单纯形表中松弛变量检验数的相反数。”；CB-'和CB-*b的计算及体现。关键字：运筹学线性规划单纯

2、形法对偶问题单纯性乘子定理最优值单纯形表1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，宜到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cxlAx=b,x20},则其对偶问题为max{yblyAWc}。当原始问题的一个基解满足最优性条件时，其检验数cBB・lA・cWO。艮知y=cBB-l（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满

3、足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。线性规划的对偶问题一、对偶问题的提出生产计划问题：某家具厂生产桌子和椅子，桌子售价50元/个，椅子售价30元/个。需要木工和油漆工，生产一个桌子需要木工4小时，油漆工2小时，生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时120小时,油漆工工时50小时。问：如何组织生产，使得每月销售收入最大？线性规划模型为（桌、椅数量为变量）:maxz=50兀］+30x24兀］+3兀25120s.tA2x}+x2<50现考虑一个成本最小化的问题：另一厂商，接到上述生产订

4、单后组织生产,其中的劳动力欲向家具厂雇佣，如何才能使得生产成本（工资）最小？分析：确定决策变量二木工的工资，儿二油漆工的工资得对偶问题规划minz=120^+50儿冃标函数一使工资支出最小4y,+2匕>50约束方程一向外转让的收入至少模型：s.t.3y}+y2>3（）要大于自己生产的收入y[.y2>0工资的非负约束二、对称形式的对偶问题的矩阵表述:maxz=CX原问题：既定的资源（成本）b约束下产量x最大化AX0minw=hfY对偶问题：既定的产量c约束下资源（成本）b最小化:s.t.A!Y>CY>0三、对偶原理在经济学厂

5、商理论屮的应用：从实物形态研究生产——生产理论；从货币形态研究成本结构——成本理论在完全竞争市场上，一定成本下产量最大化的投入组合问题]r互为对偶问题一定产量卜•成本最小化的投入组合问题丿1、•定成本下产量最大化的投入组合问题:maxQ=f(L.K)s.t.C—wL+rK2、令Z=厶K）+2（/—w厶—厂K）空=型-〃=0得dKdK伍即:min一定产量下成本最小化的投入组合问题：s.t.Bi。MP.=PMPkC=wL+rK◎=/（厶K）用拉格朗日乘数法求解:^Zf=wL+rK-才（Q-/（L,K））,dZf~dKdK'四、如何将原冋题转化为对偶问题

6、（-）约束条件为标准形式（见前例）忖标函数的最大值max――忖标函数的最小值min目标函数的价值系数C—约束方程右端的资源量C约束系数矩阵A--约束系数矩阵A'原问题的n个变量（20）--对偶问题的n个约朿方程约束条件“AXWB”一-对偶问题的约束条件“A!YMC”（二）约束条件为非标准形式将下列线性规划问题转化为对偶问题minz=7%!+4x2一3x3—4%

7、+2%2—6兀3—24—3%

8、一6%2一4兀3二15s.t.<5x2+3x3=30X}<0,£取值无约朿，®、01、先化为标准形式，再根据标准形式进行转化:令兀：-并将等式约朿5兀2+3兀3

9、=30化为两个不等式约朿5x2+3x3<30和5x2+3x3>30；对于min问题，统一约束不等式为“2”,得:minz=一7兀;+4兀；-4兀;一3x3—4x；—2x；+2%2+6兀3——243兀；-6兀;+6兀;-4兀3—1/.<5兀;一5兀;+3x3>30-5兀；+5%2-3兀3—-30X：,兀;，兀；,无3»0maxw=-24Yj+15y2+30儿一30儿-4)i+3y2<-7一2”_6旳+5儿_5儿54sl・<2y}+6y2-5y3+5y4<-46)?i-4y2+3y3-3y4<-3”，儿，丫3，儿>°2、将多余的量还原：第一个约朿方程的

10、右边还项原为正数，令卄二-X，必=儿一九，并将第三、第四约朿方程合并为等式约朿，得:maxw=24y；+15儿+30%-4