《运筹学》课程教学资源（PPT课件讲稿）第一章 线性规划 1.1 线性规划的概念

(1)LP数学模型 (2)LP各种解的概念: 可行解(重点) 基本概念{基本解(难点) 基本可行解(重点) 最优解 线性规划内容框架 基本最优解 解的基本性质:四个主要定理 图解法 实际问题_条件LP模型→基本方法单纯形法(原始单纯形法、人工变量法大A法 两阶段法 对偶单纯形法 (求解) 前提?步骤? 修正单纯形法 进一步讨论对偶理论 灵敏度分析→参数规划 算法复杂性问题→哈奇扬算法、 karmarkar算法 经济管理方面的典型问题 整数LP 运输问题 特殊LP多目标LP ZZJyLP

   → →    ⎯⎯⎯→ → FuzzyLP LP LP LP karmarkarM LP LP LP 多目标 运输问题 整数 特殊 经济管理方面的典型问 题 算法复杂性问题 哈奇扬算法、 算法 灵敏度分析 参数规划 对偶理论 修正单纯形法 进一步讨论 前提？步骤？ （求解） 对偶单纯形法 ） 两阶段法 大 法 单纯形法（原始单纯形法、人工变量法 图解法 基本方法 解的基本性质：四个主要定理 基本最优解 最优解 基本可行解（重点） 基本解（难点） 可行解（重点） （ ） 各种解的概念： （） 数学模型 基本概念 实际问题 ？条件 模型 21 线性规划内容框架

第一章、线划 11线性规划的概念 、线性规划问题的导出 1.(引例)配比问题 用浓度为45%和92%的硫酸配置 100t浓度为80%的硫酸

第一章、 线性规划 1.1 线性规划的概念 一、线性规划问题的导出 1．(引例) 配比问题—— 用浓度为45%和92%的硫酸配置 100t浓度为80%的硫酸

取45%和92%的硫酸分别为x1和x2t, 则有: x1+x2=100 0.45x1+0.92x=0.8×100 求解一元二次方程组得解

取45%和92%的硫酸分别为x1和x2 t, 则有： 求解一元二次方程组得解。    + =  + = 0.45 0.92 0.8 100 100 1 2 1 2 x x x x

目的相同,但有5种不同浓度的硫 酸可选(30%,45%,73%,85%, 92%)会出现什麽情况? 取这5种硫酸分别为x1、x2、x3 x4、x5t,则有: x,+xn+x,+x1+x。=100 0.3x1+045x2+0.73x2+0.85X+092x。=0.8×100

目的相同，但有5种不同浓度的硫 酸可选（30%，45%，73%，85%， 92%）会出现什麽情况？ 取这5种硫酸分别为 x1、x2、x3、 x4、x5 t, 则有：    + + + + =  + + + + = 0.3 0.45 0.73 0.85 0.92 0.8 100 100 1 2 3 4 5 1 2 3 4 5 x x x x x x x x x x

有多少种配比方案?为什麽? 何为最好? 5种硫酸价格分别为:400,700,1400, 1900,2500元/t,则有: Miz=400x1+700x2+1400x2+1900x+2500x x1+x2+x2+x1+x=100 st0.3x1+0.45x,+0.73x2+0.85x1+0.92x 0.8×100 x1≥0,j=1,2,…,5

· 有多少种配比方案？为什麽？       = + + + + =  + + + + = = + + + + 0, 1,2, ,5 0.3 0.45 0.73 0.85 0.92 0.8 100 100 . . 400 700 1400 1900 2500 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 x j  x x x x x x x x x x st MinZ x x x x x j ·何为最好？ 5种硫酸价格分别为：400，700，1400， 1900，2500元/t，则有：

2.生产计划问题: 生产单位产品 产品所需资源 ABC每天可利用 资源量 资源 工时(单位)111 3 材料(t) 147 产品利润 (元/t 200030001000

2. 生产计划问题： 生产单位 产品 产品所需资源 资 源 A B C 每天可利用 资源量 工时（单位） 1 1 1 3 材料（t） 1 4 7 9 产品利润 （元/t） 2000 3000 1000

如何制定生产计划,使三种产品总 利润最大? 问题讨论 ①何为生产计划? ②总利润如何描述? ③还要考虑什麽因素? 有什麽需要注意的地方(技巧)? ⑤最终得到的数学模型是什麽?

如何制定生产计划，使三种产品总 利润最大？ 问题讨论 何为生产计划？ 总利润如何描述？ 还要考虑什麽因素？ 有什麽需要注意的地方（技巧）？ 最终得到的数学模型是什麽？

Minz=2x,3x + x x1+X,+x2≤3 st.x1+4x2+7x2≤9 x;≥O,j=1,2,3 线性规划的定义和数学描述(模型) 1.定义:对于求取一组变量x(=1,2,…,n) 使之既满足线性约束条件,又使具有线性表达 式的目标函数取得极大值或极小值的一类最优 化问题称为线性规划问题,简称线性规划

      = + +  + +  = + + 0, 1,2,3 4 7 9 3 . . 2 3 1 2 3 1 2 3 1 2 3 x j x x x x x x st MinZ x x x j 二、线性规划的定义和数学描述（模型） 1．定义：对于求取一组变量xj (j =1,2,......,n)， 使之既满足线性约束条件，又使具有线性表达 式的目标函数取得极大值或极小值的一类最优 化问题称为线性规划问题，简称线性规划

2配比问题和生产计划问题的线性规 划模型的特点: 用一组未知变量表示要求的方案,这组 未知变量称为决策变量; 存在一定的限制条件,且为线性表达式; 有一个目标要求(最大化,当然也可以 是最小化),目标表示为未知变量的线 性表达式,称之为目标函数; 对决策变量有非负要求

2.配比问题和生产计划问题的线性规 划模型的特点：  用一组未知变量表示要求的方案，这组 未知变量称为决策变量；  存在一定的限制条件，且为线性表达式；  有一个目标要求（最大化，当然也可以 是最小化），目标表示为未知变量的线 性表达式，称之为目标函数；  对决策变量有非负要求

3.LP的数学描述(数学模型) (1)一般形式 Max(或Mm)Z=cx1+c2x2+…+Cnxn C1x1+a1x2+……+a nn a21x1+a2x2+…a2nxn≤(=,)b2 st am1x1+an2x2+…+amxn≤(=,≥)bn 152 x.≥0

3．LP的数学描述(数学模型)： （1）一般形式           + + +  =  + +  =  + + +  =  = + + + , , , 0 ( , ) ( , ) ( , ) . . ( ) 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 n m m m n n m n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b st Max Min Z c x c x c x        或 