PPT《运筹学》

运筹学 线性规划与单纯形法 运筹学教师:赵玮

电话: 引言 数学要求课程的地位与作用运筹学概要 十 网络图论 十六 预测 十五 决策分析 十一 &

2 统筹法 八 线性整数规划 一,二,三,四,五,六 线性规划 教材章节 分支 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 例

1、例2,基本概念模型的基本化 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 基本原理图解法步骤最优解的几种类型 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法(单纯形法)与求解退化与循环 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法(单纯形法)与求解退化与循环 三种元素算法的比较单纯形法求解思路最优解的搜索迭代过程与检验数迭代与基变换单纯形表计算单纯形表基变换的进一步认识 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 图解法的灵敏度分析计算机解法的灵敏度分析 线性规划(LP) 问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析 对偶规划及其经济含义对偶规划基本理论对偶单纯形法算法比较影子价格 2.

线性整数规划 基本概念 定义 研究概况分支定界法的理论与算法基本思想算法与判别准则 线性规划 人力资源分配的问题例1. 某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下: x6

30 2:00-6:00

6 x5

30 22:00-2:00

5 x4

50 18:00-22:00

4 x3

60 14:00-18:00

3 x2

70 10:00-14:00

2 x1

60 6:00-10:00

1 xi 至少所需人数 时间 班次i xi: 实际安排司乘人员数 设司机和乘务人员分别在各时间段一开始时上班,并连续工作八小时,问该公交线路怎样安排司机和乘务人员,既能满足工作需要,又配备最少司机和乘务员? 解:设xi表示第i班次时开始上班的司机和乘务人员数,这样可以知道在第i班工作的人数应包括第i-1班次时开始上班的人员数和第班次时开始上班的人员数,例如有x1 +x2≥70.又要求这六个班次时开始上班的所有人员最少,既要求x1 +x2 +x3+x4 +x5 +x6最小,这样建立如下的数学模型: 目标函数:min z = (x1 +x2 +x3+x4 +x5 +x6)约束条件: 生产计划决策 例2. 某工厂在计划内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A,B两种原材料的消耗,以及资源的限制,如下表所示.

100 50 单位产品利润(元) 250千克

1 0 原材料B(千克) 400千克

1 2 原材料A(千克) 300台时

1 1 设备(台时) 资源限制 产品Ⅱ 产品Ⅰ 产品资源 可以用x1和x2的线性函数形式来表示工厂所要求的最大利润的目标:max z=50x1+100x2其中max为最大化的符号(最小化符号为min);

50和100分别为单位产品Ⅰ、Ⅱ的利润.上式称为目标函数.同样也可以用x1和x2的线性不等式来表示问题的一些约束条件.对于台时数方面的限制可以表示为: x1+x2≤300.同样,原材料的限量可以表示为 2x1+2x2≤400 x2≤250 暂不考虑市场需求.该工厂每生产一单位产品Ⅰ可获利50元,每生产一单位产品Ⅱ可获利100元,问工厂应分别生产多少个Ⅰ产品和Ⅱ产品才能使工厂获利最多? 这个问题可以用以下的数学模型来加以描述.工厂目前要决策的问题是生产多少个Ⅰ产品和Ⅱ产品,把这个要决策的问题用变量x

1、x2来表示,则称x1和x2为决策变量,即决策变量x1=生产Ⅰ产品的数量,决策变量x2 =生产Ⅱ产品的数量. 除了上述约束外,显然还应该有x1≥0, x2≥0,因为Ⅰ产品、Ⅱ产品的产量是不能取负值的.综上所述,就得到了例1的数学模型如下: 目标函数:max z=50x1+100x2 满足约束条件: 问题与建模 模型:对真实系统的结构与行为用图、解析式或方程来描述的合称为模型. 预测模型 评价模型 优化模型 仿真模型 例1. 生产计划决策 max z=50x1+100x2 xj生产产品j的数量 例2. 人力资源分配问题决策 min z = (x1 +x2 +x3+x4 +x5 +x6)xj:第j个班次司乘人员数 LP四要素s.t :subject约束条件z称为目标函数xj称为决策变量max或min成为优化准则LP def1: 若目标函数z为决策变量xj的线性函数,约束条件亦为决策变量xj的线性不等式(或等式),则该数学表达式(模型)称为线性规划.若目标与约束中至少有一为非线性时,则该模型称为非线性模型(NLP). 模型的标准化 标准化LP模型的特点目标函数仅限与极大化(或极小化)所有约束条件均由等式表示所有决策变量限于取非负值每一约束不等式(或等式)之右端均为非负值 n:决策变量个数m:约束方程个数 模型的标准化 约束方程的标准化(增加变量个数换取求解难度) s3≥0 s2≥0 s1≥0 s3≥0 s2≥0 s1≥0 s3≥0 s2≥0 s1≥0 x5+x6-s6=30 x5+x6≥30 x4+x5-s5=20 x4+x5≥20 x3+x4-s4=50 x3+x4≥50 x2+x3-s3=60 x2+x3≥60 x1+x2-s2=70 x1+x2≥70 x6+x1-s1=60 剩余变量 x6+x1≥60 例2 x2+s3=250 x2≤250 2x1+x2+s2=400 2x1+x2≤400 x1+x2+s1=300 松弛变量 x1+x2≤300 例1 标准形约束 引入变量类型 非标准约束 例 模型的标准化 def2:满足所有约束条件的解x称为LP的可行解,使目标函数z取得最大(小)的可行解x*称为LP的最优解,此时对应的目标函数值z (x *)称为LP的最优值.例1的解 z=50x1+100x2=27500元 最优值 (50,250) 最优解 (0,0),(50,250),(100,100),(200,0)….. 可行解 例1 (标准化模型) 模型的标准化 模型的标准化 例2 (标准化模型) 二维LP图解法 (利用解析式与平面区域对应关系求解)基本原理图解法步骤最优解的几种类型 一族平行直线(等值线族) z=ax1+bx2

5 L3左半平面G2

0 x1 ax1+bx2≤c L3右半平面G1 G2 ax1+bx2≥c 直线L3 L3 x2 G1 ax1+bx2=c

4 L2左半平面G2

0 x1 x2≤b L2右半平面G1 b G2 L2 x2≥b 直线L1 x2 G1 x2=b

3 L1左半平面G2

0 a x1 x1≤a L1右半平面G1 G2 G1 x1≥a 直线L1 x2 L1 x1=a

2 点P x=(x1, x2)

1 平面x1ox2上对应图形 解析式 基本原理 def3:满足LP中所有约束条件(不等式或等式约束)的点必在这些约束条件所对应区域所围成的公共区域D内,则称此公共区域D为LP的可行域.例1

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C(100,200) D 当目标函数z取z1,z2,z3……时,直线 有相同的斜率和不同的截距,这一族平行直线称为等值线族;

目标函数按优化准则递增(或递减)的方向称为等值线族的法线方向.z=x1+x2=300称为等值线,因直线上的点(0,300),(300,0),(150,150),(100,200)等均具有相等的目标函数值300. 图解法步骤 在平面x1ox2上求出LP的可行域利用目标函数作等值线族求出等值线的法线方向等值线沿法线方向(max准则递增方向,min准则递减方向)移动,并使目标函数z到(max, min)时,其与可行域D相交之点即为最优解 最优解的几种类型 唯一解无穷多解无界解无最优解 例1. 唯一解 max z=50x1+100x2

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C(100,200) D 例2. 无穷多解

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C(100,200) D max z=50x1+50x2 例3.无界解 max z=x1+x2

0 1

2 3 x2 -3x1+2x2=6 D

3 2

1 x1-x2=1 z3=3=x1+x2 x1 z1=1=x1+x2 z2=2=x1+x2 例4. 无最优解 max z=50x1+50x2

0 100

200 300

200 100

300 400 x1+x2=300 2x1+x2=400 x2=250 B(50,250) C(100,200) D1 D2

350 计算机算法(图解法只对n≤3有效) 图解法的启示与计算机求解思路需待解决的理论问题基本概念与理论算法与求解退化与循环 图解法的启示与计算机求解思路 最优解 在可行域D内(或边界)最优解 在D的顶点或边界达到求解思路设想:首先搜索D的顶点,然后通过顶点对应的目标值的比较来求解最优解 计算机求解 寻找Ax=b,非基变量=0之解(基本解) 寻找max z=Cx ,Ax=b ,x≥0之解(最优解) 寻找Ax=b,非基变量=0, x≥0之解(基本可行解) 图解法(n≤3) 可行点(D内点) 顶点 目标函数值比较 ? def4:在之LP中,若rank (A) = m0,经二次迭代后,已有 ,按照一般原理下有下述的x(2)=(30,6,0,0,4)T应为最优解,并迭代终止. . 虽然有z(x0)........