线形规划课件.ppt

《线形规划课件.ppt》由会员分享，可在线阅读，更多相关《线形规划课件.ppt（23页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、线形规划线性规划1.线性规划的例子2.规划问题的特点3.线性规划建模4.模型求解5.例子1.线性规划的例子例1.一个工厂可以生产种不同的产品A、B和C,而其中每种产品又有1型和2型之分。今有原料100单位用以生产这些产品,并且要求产品A的投料数量不得少于40单位,其余两种产品的投料量均不得超过35单位。每种产品的单位投料所获得利润由表给出。试问如何投料才能使所获总利润最大？产品利润分配表产 品ABC产品型别A1A2B1B2C1C2单位投料利润（万元）32.53.5454.51.线性规划的例子这个问题可用数学表达式表示如下:用x1和x2分别表示A1和A2所用的投料数量,用y1和y2表示B1和B2

2、所用的投料数量,用z1和z2分别表示C1和C2所用的投料数量。根据已知条件,它们满足以下关系式:1.线性规划的例子例2.有两个钢厂A1和A2,月产量分别为23万t和27万t。它们生产的钢供应B1、B2和B3三个机器厂,各工厂的月需要量分别为17万t,18万t和15万t。钢厂到各机器厂的单位运价如表所示。问应如何编制调运方案,才能使总运费最省？机器厂运价（元/万t）钢厂B1B2B3A1506070A2601101601.线性规划的例子这个问题可用数学表达式表示如下:用xij表示第i(i=1,2)个钢厂运用到第j(j=1,2,3)个机器厂的钢的数量。根据已知条件,它们满足以下关系式:2.线性规划问

3、题的特点1.目标函数为线性函数;2.约束条件为线性函数;3.变量非负。3.线性规划建模线性规划的标准形式的矩阵表示:其中C为1n的行向量,X为n1的非负列向量,A为mn的矩阵,b为m1的非负列向量。3.线性规划建模非标准形式转化为标准形式变量x为负值:用x取代x;b为负值:等式左右同乘一个负号;不是等式:1):在不等式左边减去一个非负变量;2):在不等式左边加上一个非负变量。4.1 凸集凸集:集合中任意两点的连线上所有的点都在集合中。线性规划的可行区域(约束集合)是一个凸集。4.2 两变量图解法 xyo362x+y-602x+y-6=04.2 两变量图解法 线性规划的可行域是一个凸集xyo3-

4、5x-y+5=0 x+y=0 x=34.2 两变量图解法 梯度方向是使目标函数值变大的方向。对于函数f(x,y),其梯度方向是(偏导):xyoax+by=Z(x1,y1)(x2,y2)(a,b)4.2 两变量图解法 55x=1x-4y+3=03x+5y-25=01ABCC:(1,4.4)A:(5,2)B:(1,1)Oxy1.1.设目标函数为设目标函数为 max Z=max Z=x+2y 2.2.设目标函数为设目标函数为 min Z=x+2y min Z=x+2y梯度方向梯度方向4.2 两变量图解法 两变量图解法步骤:1)画出线性约束条件所表示的可行域;2)在线性目标函数所表示的一组平行线中,利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线;3)通过解方程组求出最优解。4.3 线性规划的性质 1)可行域是数条直线围成的凸多边形;2)如果线性规划问题存在最优解,则至少有一个可行域中的顶点是最优解;Thanks