1、运筹帷幄之中决胜千里之外线性规划及单纯形法Linear Programming第一章Chapter1 线性规划 (Linear Programming)LP的数学模型图解法 单纯形法单纯形法的进一步讨论人工变量法LP模型的应用本章主要内容：本章主要内容：线性规划问题的数学模型1. 规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（ 1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（ 2）在一定的
2、资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大 .）线性规划问题的数学模型例 1.1 如图所示，如何截取 x使铁皮所围成的容积最大？ xa线性规划问题的数学模型例 1.2 某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润 问：应如何安排生产计划，才能使总利润最大？ 解：1.决策变量：设产品 I、 II的产量分别为 x1、 x22.目标函数：设总利润为 z， 则有：max z = 2 x1 + x23.约束条件：5x2 156x1+ 2x2 24x1+ x2 5x1， x20线性规划问题的数学模型例 1.3 已知资料如下表所示，问如何安排生产才能使利润最大
3、？或如何考虑利润大，产品好销。设 备产 品ABCD利 润 （元） 2 1 4 0 2 2 2 0 4 3有 效 台 时 12 8 16 12解：1.决策变量：设产品 I、 II的产量分别为 x1、 x22.目标函数：设总利润为 z， 则有： max z = 2 x1 + 3x23.约束条件： x1 0 , x2 02x1 + 2x2 12x1 + 2x2 84x1 164x2 12线性规划问题的数学模型例 1.4 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量 解：要求：生产 A种药物至少 160单位； B种药物恰好 200单位， C种药物不超过 180
4、单位，且使原料总成本最小。1.决策变量：设四种原料的使用量分别为： x1、 x2 、 x3 、 x42.目标函数：设总成本为 zmin z = 5 x1 + 6 x2 + 7 x3 + 8 x43.约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、 x2 、 x3 、 x4 0例 1.5 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：航 线 号 船 队类 型 编队 形式货 运成本（千元 队 ）货 运量（千吨）拖 轮 A型驳 船 B型驳 船1 1 1 2 36 252 1
5、 4 36 202 3 2 2 4 72 404 1 4 27 20船只种 类 船只数拖 轮 30A型 驳 船 34B型 驳 船 52航 线 号 合同 货 运量1 2002 400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型解：设： xj为第 j号类型船队的队数（ j = 1， 2， 3， 4），z 为总货运成本则： min z = 36x1 + 36x2 + 72x3 + 27x4x1 + x2 + 2x3 + x4 302x1 + 2x3 344x2 + 4x3 + 4x4 5225x1+20x2 20040x3+20x4 400xj 0 （ j = 1
6、,2,3,4）线性规划问题的数学模型线性规划问题的数学模型2. 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量 Decision variables 目标函数目标函数 Objective function约束条件约束条件 Constraints其特征是：其特征是：（ 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的 线性线性 函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；（ 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的 线性线性 不不等式或等式。等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？
