线性规划(1).doc

第一章线性规划一、线性规划的一般模型 1 、线性规划问题的三个要素?决策变量?决策问题待定的量值称为决策变量。?决策变量的取值要求非负。?约束条件?任何问题都是限定在一定的条件下求解, 把各种限制条件表示为一组等式或不等式,称之为约束条件。?约束条件是决策方案可行的保障。? LP 的约束条件,都是决策变量的线性函数。?目标函数?衡量决策方案优劣的准则,如时间最省、利润最大、成本最低。?目标函数是决策变量的线性函数。?有的目标要实现极大,有的则要求极小。 2 、线性规划模型的构建?例 1. 生产计划问题某厂生产甲乙两种产品,各自的零部件分别在 A、B 车间生产,最后都需在 C 车间装配,相关数据如表所示: 产品车间工时单耗甲乙生产能力 ABC 100234 8 12 36 单位产品获利 35 问如何安排甲、乙两产品的产量,使利润为最大。建立模型(1) 决策变量。要决策的问题是甲、乙两种产品的产量, 因此有两个决策变量:设 x1 为甲产品产量, x2 为乙产品产量。(2) 约束条件。生产这两种产品受到现有生产能力的制约,用量不能突破。?生产单位甲产品的零部件需耗用 A 车间的生产能力 1 工时, ?生产单位乙产品不需耗用 A 车间的生产能力, ? A 车间的能力总量为 8 工时,则 A 车间能力约束条件表述为 x 1≤8?同理, B和C 车间能力约束条件为 2x 2≤ 12 3x 1 +4x 2≤ 36 (3) 目标函数。目标是利润最大化,用 Z 表示利润,则 maxZ= 3x 1 +5x 2 (4) 非负约束。甲乙产品的产量不应是负数,否则没有实际意义,这个要求表述为 x 1≥0,x 2≥0?综上所述,该问题的数学模型表示为 maxZ= 3x 1 +5x 2x 1≤82x 2≤ 12 3x 1 +4x 2≤ 36 x 1≥ 0,x 2≥0 例 2. 运输问题某名牌饮料在国内有三个生产厂,分布在城市 A1 、 A2 、 A3, 其一级承销商有 4 个,分布在城市 B1 、 B2 、 B3 、 B4 , 已知各厂的产量、各承销商的销售量及从 Ai到Bj 的每吨饮料运费为C ij ,为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案。销地产地 B1 B2 B3 B4 产量 A1 A2 A3 6325 7584 3297 523 销量 2314 (1) 决策变量。设从 Ai到Bj 的运输量为 xij, (2) 目标函数。运费最小的目标函数为 minZ =6 x 11 +3 x 12 +2 x 13 +5 x 14 +7 x 21 +5 x 22 +8 x 23 +4 x 24+3x 31 +2 x 32 +9 x 33 +7 x 34 (3) 约束条件。产量之和等于销量之和, 故要满足: 供应平衡条件 x 11+x 12+x 13+x 14 =5 x 21+x 22+x 23+x 24 =2 x 31+x 32+x 33+x 34 =3 销售平衡条件 x 11+x 21+x 31 =2 x 12+x 22+x 32 =3 x 13+x 23+x 33 =1 x 14+x 24+x 34 =4 非负性约束: x ij≥0(i =1,2,3 ;j =1,2,3,4) 3 、线性规划的一般模型?用一组非负决策变量表示一个决策问题, ?存在一定的等式或不等式的线性约束条件, ?有一个希望达到的目标,可表示成决策变量的线性函数。可能是最大化,也可能是最小化。?线性规划一般模型的代数式为: max(min)Z=c 1x 1 +c 2x 2+…+c nx na 11x 1 +a 12x 2+…+a 1nx n≤(≥,=)b 1 a 21x 1 +a 22x 2+…+a 2nx n≤(≥,=)b 2 …………… a m1x 1 +a m2x 2+…+a mnx n≤(≥,=)b m x 1 ,x 2,…,x n≥(≤)0 二、两变量线性规划的图解法 1 、图解法的基本步骤?图解法即是用图示的方法来求解线性规划问题。?一个二维的线性规划问题,可以在平面图上求解,三维的线性规划则要在立体图上求解,这就比较麻烦,而维数再高以后就不能图示了。(1 )可行域的确定满足所有约束条件的解的集合,称之为可行域。即所有约束条件共同围城的区域。?例1 的数学模型为 maxZ= 3x1 +5 x2x 1≤82x 2≤ 12 3x 1 +4x 2≤ 36 x 1≥ 0,x 2≥0 五边形 OABCD 内( 含边界) 的任意一点(x 1,x 2) 都是满足所有约束条件的一个解, 称之可行解。x 1 =8 2x 2 =12x 1 x 248 12 3 6 90 0 A A B B C(4,6 C(4,6 D D (2 )最优解的确定目标函数 Z= 3x1 +5 x2 代