线性规划--第一讲-一般线性规划问题的数学模型(2).ppt

《线性规划--第一讲-一般线性规划问题的数学模型(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.1一般线性规划问题的数学模型-标准化线性规划标准型线性规划标准化途径线性规划的常见模型线性规划模型的一般形式线性规划问题的标准形式标准形式为:目标函数最大约束条件等式右端项非负决策变量非负简写为用向量表示用矩阵表示C—价值向量b—资源向量X—决策变量向量二、一般线性规划模型标准化1、目标函数为求极小值，即为：。因为求minz等价于求max(-z)，令z’=-z，即化为：2、约束条件为不等式，xn+1≥0松弛变量，其价值系数为0如何处理？xn+1≥0剩余变量，其价值系数为0３、右端项bi<0时，只需将等式两端同乘（-1）则右端项必大于零4、决策变量

2、无非负约束设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0(例1)试将LP问题minz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0化为标准形式。解：令x3=x4-x5其中x4、x5≥0；对第一个约束条件加上松弛变量x6；对第二个约束条件减去剩余变量x7；对第三个约束条件两边乘以“-1”；令z’=-z把求minz改为求maxz’maxz’=x1-2x2+3x4-3x5s.t.x

3、1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0例2将下列线性规划化为标准形【解】（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以令(2)第一个约束条件是≤号，在≤左端加入松驰变量(slackvariable)x4，x4≥0,化为等式；(4)第三个约束条件是≤号且常数项为负数，因此在≤左边加入松驰变量x6，x6≥0，同时两边乘以－1。（5）目标函数是最小值，为了化为求最大值，令Z′=－Z,得到maxZ′=－Z，即当Z达到最小值时Z′达到最大

4、值，反之亦然。(3)第二个约束条件是≥号，在≥左端减去剩余变量(Surplusvariable)x5，x5≥0。也称松驰变量综合起来得到下列标准型例3：将下列线性规划标准化目标函数maxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20Max例4：将如下线性规划标准化解：标准形为