运筹学（O.R.） Operations Research

Presentation on theme: "运筹学（O.R.） Operations Research"— Presentation transcript:

1 运筹学（O.R.） Operations Research 运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

2 中国古代运筹学思想： 齐王赛马 丁渭修皇宫 沈括运粮 运筹学的产生： 防空系统 商船护航

3 运筹学发展三阶段： 创建时期（45年至50年代初） 成长时期（50年代初至50年代末） 迅速发展时期（60年代以来）
1948年 英国成立“运筹学”俱乐部 1948年 麻省理工学院 介绍运筹学 1950年 伯明翰大学开设运筹学课程 1952年 卡斯大学 设立运筹学硕士和博士学位 1947年 丹捷格 提出单纯形法 50年代初 计算机求解线性规划获得成功 成长时期（50年代初至50年代末） 多个国家成立运筹学会，多种运筹学刊物问世 1957年 在牛津大学召开第一次国际运筹学会议 1959年 成立国际运筹学联合会 迅速发展时期（60年代以来） 运筹学进一步分为各个分支，更多运筹学出版物 运筹学课程纳入教学计划

4 我国运筹学发展历程： 1956年 运筹学小组 1958年 运筹学研究室 1960年 应用运筹学经验交流会议 1962年 全国运筹学专业学术会议 1978年 全国运筹学专业学术会议 1980年 成立中国运筹学学会

5 国际著名运筹学刊物： Management Science Operations Research Interfaces Journal of Operational Research Society European Journal of Operations Research

6 运筹学的分支: 线性规划（linear programming） 非线性规划（nonlinear programming）
动态规划（dynamic programming） 图论与网络分析（graph theory and network analysis） 存贮论（inventory theory） 排队论（queueing theory） 对策论（game theory） 决策论（decision theory）

7 运筹学在工商管理中的应用: 生产计划：生产作业的计划、日程表的编排、合理下料、 配料问题、物料管理等，追求利润最大化和成 本最小化
库存管理：多种物资库存量的管理，库存方式、库存量等 运输问题：确定最小成本的运输线路、物资的调拨、运输 工具的调度以及建厂地址的选择等 人事管理：对人员的需求和使用的预测，确定人员编制、 人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与销售 计划制定等 财务会计：预测、贷款、成本分析、定价、证券管理、 现金管理等

8

9 学习管理运筹学: 必须使用相应的计算机软件 必须注重于学以致用的原则 要把注意力放在: 结合实际问题建立运筹学模型 解决问题的方案或模型的解 中间的计算过程尽可能让计算机软件完成

10 运筹学的工作步骤： 1．提出和形成问题 2．收集资料，确定参数 3．建立模型 4．模型求解和检验 5．解的控制

11 例1.1 某厂生产P、Q两种产品，主要消耗A、B、C三种原料，已知单位产品的原料消耗数量等资料如表所示。确定P、Q的产量，使产值最大。
第一章 线性规划 第一节 线性规划的基本概念 例1.1 某厂生产P、Q两种产品，主要消耗A、B、C三种原料，已知单位产品的原料消耗数量等资料如表所示。确定P、Q的产量，使产值最大。 P Q 原料总量 A B C 1 5 2 4 8吨 20吨 12吨 产品单价 2万元 5万元

12 数学模型： 设P、Q的产量分别为x1，x2

13 例1.2 某公司打算利用甲、乙、丙三种原料配置一种新型保健饮料，已知每千克原料中两种主要保健成分A，B含量及原料单价如表所示。质量标准规定每千克饮料中，营养成分A，B的含量不低于10个与8个单位。如何制定饮料配方，既满足质量标准又使成本最低？ 甲 乙 丙 A B 20 10 40 单价（元/千克） 2 3

14 数学模型： 设每千克饮料中原料甲、乙、丙的投入量分别为x1，x2，x3千克

15 例1.3 A1 A2是两个粮库，每月分别可调出粮食30 吨与40吨，三个粮店B1，B2，B3每月需求量分别为20吨，25吨与18吨。粮库与粮店之间每吨粮食的运费如下表所示。要求安排粮食调运方案，在满足需求的前提下使总运费最低。 B1 B2 B3 A1 A2 2 4 3 6 5 30 40 20 25 18

16 数学模型： 设从Ai到Bj调运量为xij

17 共同特点： （1）每个行动方案可用一组变量（x1,…,xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它是变量的线性函数。

18 (1.1) (1.2) (1.3)

19 二、图解法 例1.4 求下列问题的最优解。 x2 x1 x1+2x2=8 5x1+2x2=20 4x2=12 4 3 2 1 5 6 Q1
5 6 Q1 Q2 Q3 Q4 (3,2.5) (2,3) z的等值线：

20 例1.5 在例1.4中，约束条件不变，而目标函数改为max z=2x1+4x2
3 2 1 5 6 Q1 Q2 Q3 Q4 (3,2.5) (2,3) 全部最优解： αX1+（1－α）X2 （0≤α≤1）

21 D A 2 4 x2 x1 B C x1－x2=2 －2x1+x2=4 O 例1.6 例1.7在例1.6中，约束条件改为

22 第二节 线性规划的标准形式和解的性质 一、 LP的标准形式 (1.4) (1.5) (1.6)

23 方法： （1）目标函数求极小：令z1=－z， （2）某右端常数bi<0，以－1乘该约束两端。 （3）约束为“≤”型，左端加非负变量（松弛变量） 约束为“≥”型，左端减去非负变量（剩余变量） （4）若xj≤0；令xj′=－xj，则xj′≥0； 若xj无符号限制,令xj=xj′-xj″,其中xj′≥0，xj″≥0。

24 例1.8

25 例1.9

26 二、LP的基可行解的概念 决策变量向量：X=(x1，x2，…，xn)T 价值向量： C=(c1，c2，…，cn)
资源向量： b=(b1，b2，…，bm)T 系数矩阵A=（aij）m×n =

27 设系数矩阵A的秩是m，即A的m个行向量是线性无关的。若B是A的m阶满秩子阵，称B为问题的一个基。
B=( P1，P2 ，… ，Pm) 对应的变量 ( x1，x2 ，… ，xm)称为基变量 其它的变量称为非基变量； 令非基变量等于0，从方程组可以唯一解出基变量的值，从而得到方程组的一个解，称为基本解；如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。

28 三、LP解的性质 凸集和极点 设D为n维空间的点集，若对任意X1∈D，X2∈D，和实数α（0≤α≤1），都有αX1+（1－α）X2∈D，则称D为凸集。 凸集D中如果不存在两个不同的点X1∈D，X2∈D，使X=αX1+（1－α）X2（0<α<1）成立，那么点X称为极点。

29 2.线性规划解的性质 定理1 线性规划的可行域R是凸集。 证 对于LP max z=CX AX =b X ≥0 设X1∈R，X2∈R，则有Xi≥0，AXi=b 对于任意α∈[0，1]，X=αX1+（1－α）X2≥0 AX=A[αX1+（1－α）X2] = αAX1+（1－α）AX2 =αb+（1－α）b=b 故X∈R，R是凸集。

30 引理 设X是线性规划的可行解，则X是基可行解的充分必要条件是X的正分量对应的系数列向量是线性无关的。
证 （1）必要性。由基可行解的定义显然成立。 （2）充分性。不妨设X的前k个分量为正，若向量P1,P2,…,Pk线性无关，则必有k≤m。当k=m时，它们恰好构成一个基，从而X是基可行解。当k<m时，由于A的秩为m，从A中一定可以再找出m-k个列向量与P1,P2,…,Pk线性无关，共同构成一个基，其对应的解就是X，所以X是基可行解。

31 定理2 X是线性规划基可行解的充分必要条件是X是可行域的极点。
不失一般性，假设X的前m个分量为正，则有 （1） 由引理知P1,P2,…,Pm线性相关，即存在不全为零的数 使得 令 则 （2）

32 （1）+（2）得： （1）-（2）得： 设 则 又 即X不是可行域的顶点。

33 （2） X不是可行域的极点， 则X不是基可行解。
不失一般性，设 不是可行域的极点 存在两个不同的点 有 X=αY+(1－α)Z 即 因 故 时 因 故 （1） （2） （1）-（2）得： 因 故P1,P2,…,Pr线性相关

34 定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。
定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。 证 （1）不失一般性，假设可行解X的前m个分量为正。 如果P1,P2,…,Pm线性无关，则X是基可行解。 如果线性相关即存在不全为零的数 使得 令 则 设 则 若 则X2比X少一个正分量，若X2的m-1个列向量 线性无关，则X2是基可行解，否则，重复以上过程，直到找到基可行解为止。

35 （2）设X0是最优解，如果它不是基可行解，则有
故X1，X2也是最优解，如前所述， X1，X2中一定有一个点比X0少一个正分量。同理，如果X1（ X2）还不是基可行解，则能找到第三个最优解，其正分量比X1（ X2）少一个，如此继续下去，一定可以求得一个最优解，它的正分量是线性无关的，即这个最优解为基可行解。

36 第三节单纯形法 一、 单纯形法的解题思路 二、单纯形表 cj c1 c2 … cm cm+1 … ck … cn CB XB b
x1 x2 … xm xm … xk … xn c1 c2 cm x1 x2 xm b1 b2 bm … a1m … a1k … a1n … a2m … a2k … a2n … amm … amk … amn σj … 0

37 3. 单纯形法的基本法则 法则1 最优性判定法则 若对基可行解X1，所有检验数σj≤0，则X1为最优解。 法则2 换入变量确定法则 设 ，则xk为换入变量。 法则3 换出变量确定法则

38 例12 求下列LP问题 Cj -1 3 -2 CB XB b x1 x2 x3 x4 x5 x6 7 1 2 12 [4] 10 -4 8
-1 3 -2 CB XB b x1 x2 x3 x4 x5 x6 7 1 2 12 [4] 10 -4 8 σj [5/2] 1/4 -1/2 -5/2 -3/4 1/2 4 2/5 1/10 4/5 5 1/5 3/10 11 -1/5 -4/5 -12/5 例12 求下列LP问题

39 三、 关于单纯形法的补充说明  1. 无穷多最优解与唯一最优解的判别法则 若对某可行解X1， （1）所有检验数σj≤0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解； （2）所有非基变量的检验数σj<0，则问题有唯一最优解。

40 例13 讨论线性规划 cj 1 2 -1 CB XB b x1 x2 x3 x4 [1] σj

41 2. 无最优解（无界解）的判定 若对基可行解X1，存在非基变量xk的检验数σk>0，但aik≤0，i=1，2，…，m即xk的系数列向量无正分量，则问题无最优解。

42 3. 求min z 的情况 直接计算最优性检验条件改为：所有σj≥0； 换入变量确定法则改为：如果 则xk为换入变量。 例14 求例2中的LP

43 X*=(0.5,0,0.15,0,0)T，z=2×1/2+3×3/20=1.45 cj 2 3 CB XB b x1 x2 x3 x4 x5
CB XB b x1 x2 x3 x4 x5 1/4 2/5 [1/2] 1/2 1 -1/40 -1/20 σj -1/2 1/20 3/20 -1 1/40

44 第四节 初始可行基的求法——人工变量法 一、 大M法  例15 求下列LP问题的最优解

45

46 二、 两阶段法 例17

47 cj 1 CB XB b x1 x2 x3 x4 x5 x6 x7 11 3 -4 -2 2 [1] -1 σj 6 -3 10 12 -5

48 X*=(4，1，9，0，0)T，z*=2 cj 3 -1 CB XB b x1 x2 x3 x4 x5 12 1 -2 σj 4 9 1/3
CB XB b x1 x2 x3 x4 x5 12 1 -2 σj 4 9 1/3 2/3 -2/3 -4/3 -1/3 X*=(4，1，9，0，0)T，z*=2

49 三、 关于退化解的说明 cj -1 -4 1 CB XB b x1 x2 x3 x4 [1] σj -2 [2] 2 1/2 -1/2
[1] σj -2 [2] 2 1/2 -1/2 3/2

50 第五节线性规划应用举例 建立LP模型步骤： （1）深入分析问题特点，适当选择决策变量； （2）确定优化对象——目标函数，它必须表达为决策变量的线性函数； （3）分析制约变量的各种因素，用线性等式或不等式把这些条件反映出来。 例18 利用长度为7.4米的角钢，要做成三边长为2.9米，2.1米，1.5米的三角架100套。如何下料，才能使消耗的原料最少？

51 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 合计长 余料长 7.3 0.1 7.1 0.3 6.5 0.9 7.4 6.3 1.1 7.2 0.2 6.6 0.8 1.4 变量编号 x2 x4 x6 x1 x7 x3 x5 x8

52 例19 某食品厂要用C，P，H三种原料混合加工成三种不同档次的产品A，B，C，已知三种产品中原料含量限制，原料成本和每月限制用量，三种产品的加工费和单价等资料如表所示。该厂应当每月生产三种产品多少公斤，才能使利润最大？试建立问题的线性规划模型。

53 解 设AC，AP，AH分别表示产品A中三种原料的含量，其它符号BC，BP，BH和DC，DP，DH的含义相仿。
BC+BP+BH=B DC+DP+DH=D 含 量 限 制

54 AC+BC+DC≤3000 AP+BP+DP≤3000 AH+BH+DH≤2400 原料数量限制： 产品销售收入为： 60（AC+AP+AH）+45（BC+BP+BH）+40（DC+DP+DH） 加工费为： 6（AC+AP+AH）+5（BC+BP+BH）+4（DC+DP+DH） 原料成本为： 65（AC+BC+DC）+25（AP+BP+DP）+35（AH+BH+DH） 利润： z=60（x1+x2+x3）+45（x4+x5+x6）+40（x7+x8+x9） －6（x1+x2+x3）－5（x4+x5+x6）－4（x7+x8+x9） －65（x1+x4+x7）－25（x2+x5+x8）－35（x3+x6+x9） =－11x1+29x2+19x3－25x4+15x5+5x6－29x7+11x8+x9

55