运筹学ABC-2.doc

第二部分 线性规划 Linear Programming 简记 LP 主要内容 ： ? 学习数学规划的建模，提高分析问题的能力 ? 掌握线性规划的标准型、图解法 ? 了解线性规划的单纯形法、对偶理论 ? 了解影子价格的意义 ? 了解灵敏度分析的目的 第一节 （LP）模型的建立及标准形式 一、由实际问题出发，建立（LP）模型 LP主要解决的问题： 稀缺资源在竞争的使用方向中如何进行最优分配 例如： ? 产品的最优组合 ? 生产排序 ? 最优投资方案 ? 人力资源分配 …… 模型的四个要点： ? 真实性 ? 简明性 ? 完整性 ? 规范性 规划论模型包含的三个方面： 1、设计方案： 利用变量 x1 , x2 ,···,x n 表示方案，称为设计变量或决策变量。 2、目标（方案好坏的评价标准）： 一般表示为决策变量的函数 f (x1 ,···,x n )，称为目标函数，用Max ( Min ) 表示最优。 3、限制条件（客观条件对方案的限制）： 一般表示为决策变量的不等式方程，称为约束方程。 规划论模型的数学表示： x1 , x2 ,···,x n ， Max ( Min ) Z = f (x1 ,···,x n ) g 1 (x1 ,···,x n ) ≥ (≤ , = ) b 1 …… g m (x1 ,···,x n ) ≥ (≤ , = ) b m LP只是规划论中的一种。 规划论中不同规划的区别：—— 函数 ?若目标函数与约束方程中的函数均为线性函数，—— 线性规划 ?若目标函数与约束方程中的函数有非线性函数，—— 非线性规划 ?若设计变量要求取整数，—— 整数规划 ?若设计变量要求只取 ( 0, 1 )，—— 0 -1规划 ?若函数中引入时间参数, —— 动态规划 另：若目标有多个, —— 多目标规划 线性与非线性的区别： ?线性函数：函数为多元一次。表达式： a1 x1 + a2 x2 + ······ + an xn ?不是线性的函数，均称为非线性函数。例如： 2 x12 + 3 x1x2 函数不是线性的规划问题 例：把半径为R的实心金属球熔化后，铸成一个实心圆柱体，问：圆柱体取什么尺寸，才能使它的表面积最小？ 解：设计变量：设圆柱体的底面半径为x1 ，高为x2 目标函数：M in (圆柱体表面积 ) = (两个底面积) + (侧面积) = 2πx12 + 2πx1x2 约束方程：V圆柱 = V 圆球 πx12 x2 = 4/3 πR3 x1，x2 ≥0 二、（LP）模型的种类 （1）(引论中的例1) Min Z = x1 + x2 + x3 + x4 + x5 4 x1 + 3x2 + 2x3 + x4　　　≥ 90 　　　2x2 + 4x3 +5x4 + 7x5 ≥ 70 x i ≥ 0 i =1······5 （2）(引论中的例2) Max Z = 20 x 1 + 30 x 2 1/40 x1 + 1/56 x2 ≤120 1/600 x1 + 1/380 x2 ≤10 x1 ≤4000 x2 ≤3000 x1 + x2 ≤5000 x1 ，x2 ≥ 0 例3 (运输最优调配问题) 某矿区有四座冶炼厂和三座选矿厂，三座选矿厂选出的精矿分别送到四座冶炼厂冶炼。冶炼厂年处理精矿能力、选矿厂年生产精矿能力以及精矿运费如表： 运费　 　冶炼厂 选矿厂　 (元/T) Ａ Ｂ Ｃ Ｄ 生产量 ( T ) 甲 1.5 2.0 0.3 3.0 1000 乙 7.4 0.8 1.4 2.0 800 丙 1.2 0.2 2.0 2.5 500 处理量 ( T ) 500 700 800 300 2300 2300 问：如何调配精矿，使运费最低？ 建模： 设第i 选矿厂向第 j 冶炼厂调配精矿xi j (T) 。i =1, 2, 3 (甲,乙,丙)， j = 1, 2, 3, 4 (A,B,C,D) Min Z = 1.5 x11 + 2.0x12 + 0.3x13 + 3.0x14 + …… + 1.2 x31 + 0.2x32 + 2.0x33 + 2.5x34 x11 + x12 + x13 + x14 = 1000 x21 + x22 + x23 + x24 = 800 产量约束 x31 + x32 + x33 + x34 = 500 x11 + x21 + x31 = 500 x12 + x22 + x32 = 700 处理量约束 x13 + x23 + x33 = 800 x14 + x24 + x34 = 300 xi j ≥0 i =