《[经济学]1运筹学》由会员分享，可在线阅读，更多相关《[经济学]1运筹学（74页珍藏版）》请在金锄头文库上搜索。
1、,江 兵 合肥工业大学管理学院,2,三、课堂教学内容,3,运筹学的工作步骤,明确问题,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,Yes,No,No,明确问题 建立模型 设计算法 整理数据 求解模型 评价结果,结束,Yes,满意？,4,数学规划是管理科学中求最优或最有效使用有限资源的方 式以达到既定目标的一个领域，又称为最优化。 有限的资源：从地下抽出的原油、倾倒垃圾和有害废物的 场地、企业招聘的人员、餐馆放座位的空间、一个人每天工 作活动的时间，做某件事情需要花的钱,1、确定产品组合：多数企业可以生产多种产品，但不同产品所需的原材料和工时不同，类似地，它们产生的利润也不同，管理
2、者必须决定每种产品产量以使利润最大或以最小成本满足需求。 2、选路与物流：许多零售公司在各地都有提供商店货物的仓库，仓库可供的货物数量和各商店所需的货物数量是不同的，需要确定从仓库运送到商店的货物所需成本最低的方法。,5,线性规划 (Linear Programming LP)是数学规划的一个分支，是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。一般可以表达成以下两个问题中的一个： 当资源给定时，要求完成的任务最多； 当任务给定时，要求为完成任务所消耗的资源最少。,数学规划中的模型都是线性函数时，称线性规划。,6,第一章 线性规划及单纯形法 第一节 线性规划问题及数学模型（P8）
3、,7,设X1X2为工厂12的日处理量 Min Z=1000X1+800X2 X1 1 (1) 0.8X1+X2 1.6 (2) X1 2 (3) X2 1.4 (4) X1X20,8,LP问题的共同特征： 每一个问题变量都用一组决策变量 （x1,x2,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化或最小化。,目标：objective, goal, target,9,10,4x1=16,4x2=12,x1+2x2=8,x1,x
4、2,4,8,4,3,0,Q(4,2),Z=2x1+3x2,最优生产计划为：生产I产品4件，生产II产品2件。,三、两变量线性规划问题的图解法,作出LP问题的可行域 作出目标函数的等值线 移动等值线到可行域边界得到最优点,图解法步骤（图解法意义不大，但可直观揭示有关概念）,11,若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。,12,0 4 8 12 x1,9 6 3,x2,可行域,Z=36,4, 6,多重解举例 Max Z=3X1+4X2 X1 8 2X2 12 3X1+4X236 X1X20,此线段上的点 均为最优点,13,-1 0 1 2 3 x1,2 1,x2,可行域,无界解举
5、例 Max Z=3X1+2X2 -2X1+X22 X1-3X23 X1X20,14,0 2 4 6 8 x1,x2,无可行解举例 ： Max Z=2X1+3X2 X1+2X28 4X1 16 4X2 12 -2X1+X2 4 X1X20,6 4 2 0,无公共区域(可行域),15,四、 线性规划问题的标准型,16,线性规划标准形矩阵描述(A,C,b,X均为矩阵)：,X决策变量列向量。 b约束条件右端常数（资源）列向量。 C目标函数价值系数行向量。 Amxn约束条件左端系数矩阵。,17,非标准形LP问题化为标准形： 1）若目标函数为MinZ，令Z=-Z， 则MinZ等价于MaxZ 2） 若为不等
6、式约束： 若为，在方程左边加一非负新变量，称松弛 （Slack）变量 若为，在方程左边减一非负新变量，称剩余 （Surpius）变量或松弛变量,四个特点：极大化目标等式约束约束右端常数bi0决策变量Xj0。,18,非标准形LP问题化为标准形： 3） 若bi0, 方程两边同乘（-1） 4） 若变量不满足非负： 若xK0，令xK =-xK, xK0，用此式替换模型中xk 若xK无约束，令xK=xK-xK, xKxK0，用此式替换模型中xk,19,例1,可化为,20,1.4 LP问题解的概念 （可行解基基可行解可行基）,Max Z=2X1+3X2+4X3+7X4 2X1+3X2 -X3-4X4 =8
7、 X1-2X2+6X3-7X4 =-3 X1X2 X3X40,21,X1=(1,14/7,0,0); X2 =(45/13,0,-14/13,0) X3 =(34/5, 0,0,7/5); X4 =(0,45/16,7/16,0) X5 =(0,68/29,0,-7/29) ; X6 =(0,0,-68/31,-45/31) 基可行解X1X3X4, 最优解X3，Z=117/5,思考： X=(-9/7,27/7,1,0)、 X=(7,1,1,2)是何解？,22,例1 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,可行解、基解和基可行解举例
8、,4x1=16,4x2=12,x1+2x2=8,x1,x2,0,Z=2x1+3x2,A,B,C,D,E,F,G,H,标准型,23,线性规划标准型问题解的关系,约束方程的 解空间,基解,可行解,非可行解,基可 行解,24,Max Z=3X1+5X2+0X3+0X4+0X5 系数矩阵: X1 +X3=8 1 0 1 0 0 2X2 +X4 =12 0 2 0 1 0 3X1+4X2 +X5 =36 3 4 0 0 1 X1,X2, X3, X4 , X50 C =（3 5 0 0 0）,令x1,x2=0，得： X=(0 0 8 12 36) z=0 1,令x2,x3=0，得： X=(8 0 0 1
9、2 12) z=24 2,保留的变量称基变量，由解方程求得。移到右边并令为零的变量称非基变量。相应于基变量的系数列称基。,25,令x4,x5=0，得： X=(4 6 4 0 0) z=42 5,令x2,x5=0，得： X=(12 0 -4 12 0) z=36 6,令x1,x4=0，得： X=(0 6 8 0 12) z=30 3,令x3,x5=0，得： X=(8 3 0 6 0) z=39 4,26,令x1,x5=0，得： X=(0 9 8 -6 0) z=45 7,令x3,x4=0，得： X=(8 6 0 0 -12) z=54 8, 0 0 0 2 1 0 =0 4 0 1 无解 9,
10、1 1 0 0 0 0 =0 3 0 1 无解 10,27,小 结 本例3阶系数行列式共有10个，其中有8个行列式0，它们称为基，其中的每一列Pj (j=1,2,m)称基向量，另2个行列式=0，无意义。 与基向量Pj对应的变量xj称为基变量，记为XB ，其余变量称为非基变量，记为XN 根据基求出的解称基解，本例有8个基解，其中有5个解的所有变量都0(即可行)，这5个解称基可行解，给出这5个可行解的基称为可行基。 在5个可行解中，第5个解的目标函数值最大，故又称这个解的可行基为最优基。,28,线性规划解的概念与定理 可行解：满足约束方程组和非负条件的解。 基(B)：约束方程系数矩阵Am*n (m
11、为方程个数，n为变量个数)中满足行列式0的m阶方阵。对应于基系数列的变量称基变量 XB ，非基系数列对应变量称非基变量XN 。 基解：根据某个基，令非基变量=0而求出的解。,29,线性规划解的概念与定理 基可行解：满足非负条件的基解。 可行基：对应于可行解的基。 最优基：给出最优目标函数值的可行基。 定理：若线性规划问题存在最优解，则必定能在其基可行解中得到。从图形上看，也就是说最优解一定能在其可行域的顶点处得到。,30,第2节 LP理论基础：(凸集、凸组合、顶点）,凸集：设K为En的一点集，若对于任意X(1)X(2) K，都有X(1)+（1-）X(2) K ，（01）；则称K为凸集。,凸组合
12、：设X(1)X(2) X(k)为En的 K个点，若存在1、2 k，且0i1，i=1，2k; 使X=1 X(1)+2 X(2) +k X(k) 则称X为X(1)，X(2) X(k)的凸组合。,顶点：设K为凸集，X K，若X不能用不同的两点X(1)X(2) K的线性组合表示为X(1)+（1-）X(2) （01）；则称X为K的一个顶点。,31,第2节 LP理论基础：(定理1、2*、3）,证明： 设X(1)X(2)为LP可行域D内任意两点，X(1)X(2) ， 则AX(1)=b，AX(2)=b，X(1)0，X(2)0 令X为X(1)X(2) 连线上任意一点， 即X=X(1)+（1-）X(2) ，（01
13、） 代入约束AX=AX(1)+（1-）AX(2) =b+（1-）b=b， 又0，（1-）0，X0，即X(1)X(2) 连线上任意一点也在D内，由凸集定义，D为凸集。,定理1：若LP问题存在可行域，则其可行域 D= X| 是凸集。,32,证明： 设X(1).X(k)为可行域顶点，相应目标值Z(1).Z(k) ，其中第m个顶点X(m)处目标值最大，记为Z(m) ，若X(0) 不是顶点但其目标值最优，则：,X(0) = i X(i) ，i0， i =1 CX(0)= i CX(i)= iZ(i) iZ(m)= Z(m) 据假使CX(0) 为最优值，X(m)处也能达到最优。,定理3：若可行域有界，LP
14、问题的目标函数一定可以在其可行域的顶点上达到最优。,33,第3节 单纯形法(George Dantgig于1947年提出),由线性代数知，对标准形LP问题，理论上可以求出所有基解（枚举法），再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法.,34,为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。,第3节 单纯形法(George Dantgig于1947年提出),35,Z=2X1+3X2,C1=20, C2=30, 此解非最优 , 选X2进基.,X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12,用表表示：,36,当 X2=min(8/2,-,12/4)=3时, X5=0, X5出基。,X1+2X2 +X3 =8 4X1
