线性规划及其对偶问题

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

1、线性规划及其对偶问题1线性规划问题及其数学模型2线性规划问题的图解法3单纯形法4对偶问题5EXCEL求解线性规划6灵敏度分析1线性规划问题及其数学模型(1)线性规划问题例、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024解:设产品A,B产量分别为变量x1，x2可以建立如下的数学模型：MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目标函数约束条件可用资源煤劳动力仓库AB123202单位利润4050306024例某建筑设计院设计每万ｍ２办公建筑

2、和工业厂房需要的建筑师、结构工程师、设备工程师和电气工程师的平均人数列在表。问该院应如何安排设计任务，才能使设计费收入最大?专业建筑物建筑结构设备电器设计费收入（万元/万ｍ２）办公建筑532136工业厂房121220全院现有专业人数28261210解　设办公建筑和工业厂房各承揽ｘ１、ｘ２万ｍ２。根据题意maxZ＝36x1＋20x25x1＋x2≤28s.t3x1＋2x2≤282x1＋x2≤12x1＋2x2≤10x1、x2≥02.9m钢筋架子100个，每个需用2.1m各1，原料长7.4m1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；计

3、算出每个方案可得到的不同长度钢筋的数量及残余料头长度；确定决策变量；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。例、合理下料问题设按第i种方案下料的原材料为xi根组合方案123456782.9m211100002.1m021032101.5m10130234合计7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料长7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料头0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m例、运输问题工厂123库存仓121350222430库334210需求40153

4、5运输单价求：运输费用最小的运输方案。解：设xij为i仓库运到j工厂的产品数量其中：i＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13=50x21+x22+x23=30x31+x32+x33=10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij0s.t(2)线性规划问题的特点决策变量：(x1…xn)T代表某一方案，决策者要考虑和控制的因素非负；目标函数：Z=ƒ(x1…xn)为线性函数，求Z极大或极小;约束条件：可用线性

5、等式或不等式表示.具备以上三个要素的问题就称为线性规划问题。目标函数约束条件(3)线性规划模型一般形式隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值2线性规划问题的图解法定义1：满足约束(2)的X=(X1…Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。例1MaxZ=40X1+50X2X1+2X2303X1+2X2602X224X1,X

6、20s.t解：(1)、确定可行域X1+2X2303X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域(2)、求最优解最优解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C点：X1+2X2=303X1+2X2=600203010102030X1X2DABC最优解Z=975可行解Z=0等值线例2、MaxZ=40X1+80X2X1+2X2303X1+2X2602X224X1,X20s

7、.t解：(1)、确定可行域与上例完全相同。(2)、求最优解0203010102030DABC最优解Z=1200最优解：BC线段最优解：BC线段B点：X(1)=(6,12)C点：X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)MaxZ=1200X1615X2127.5X==+(1-)X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)例3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X

8、28X10X20可行域无界无有限最优解无有限最优解可行域无上