线性规划模型的建立与应用重点PPT学习教案

1、会计学1线性规划模型的建立与应用重点线性规划模型的建立与应用重点第一节 线性规划模型的基本原理 第1页/共73页第一节 线性规划模型的基本原理 第2页/共73页第一节 线性规划模型的基本原理 第3页/共73页第一节 线性规划模型的基本原理 第4页/共73页第一节 线性规划模型的基本原理 特点：1.可以使研究对象具体化、数量化。可以对所研究的技术经济问题做出明确的结论；2.线性3.允许出现生产要素的剩余量4.有一套完整的运算程序第5页/共73页第一节 线性规划模型的基本原理 局限性：1. 线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期计划为基

2、础。2.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。3.线性规划本身只是一组方程式，并不提供经济概念，它不能代替人们对现实经济问题的判断。 第6页/共73页第一节 线性规划模型的基本原理 第7页/共73页约束条件目标函数第一节 线性规划模型的基本原理 第8页/共73页 x1 ，x2 ，xn0第一节 线性规划模型的基本原理 极大值模型第9页/共73页njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0m

3、ax12211其简缩形式为其简缩形式为 第一节 线性规划模型的基本原理 极大值模型第10页/共73页第一节 线性规划模型的基本原理 极小值模型第11页/共73页njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0min12211其简缩形式为其简缩形式为 第一节 线性规划模型的基本原理 极小值模型第12页/共73页其简缩形式为其简缩形式为 第一节 线性规划模型的基本原理 极大值模型可用向量表示： 01jnjjjxbxPCXzMaxnxxxX21mjjjjaaaP21bmbbb21 C=(c1,c2,cn) 第13页/共73页第14页/共73页第15页/共73页第16页/共73页

4、第17页/共73页数量分别为x1、x2和x3公顷，根据问题建立线性规划问题模型如下：第18页/共73页第19页/共73页式种x2公顷，总收入为Z，则有：第20页/共73页第21页/共73页第22页/共73页第23页/共73页无穷多个可行点，缩小到可行域的有限几个极点上。第24页/共73页第25页/共73页O 20 40 x120ABCD280 x1+150 x2=42006x1+15x2=240 x1+x2=20 x2Z=1000 x1+1200 x2A(0,16)B(6.7,13.3)C(9.2,10.8)D(15,0)ZA=19200ZB=22660ZC=22160ZD=15000第26页

5、/共73页第27页/共73页1515105105OABCDx2x1x1+6x2=15可行域3x1+x2=15x1+x2=1010 x1+20 x20A(0,15)B(2.5,7.5)C(9,1)D (15,0)ZA=300ZB=175ZC=110ZD=150第28页/共73页 单纯形方法是一种较为完善的、步骤化的线性规划问题求解方法。它的原理涉及到较多的数学理论上的推导和证明，我们在此仅介绍这种方法的具体操作步骤及每一步的经济上的含义。为更好地说明问题，我们仍结合实例介绍这种方法 第29页/共73页一、线性规划的标准型二、线性规划问题的解三、单纯形法 四、单纯型表第30页/共73页第三节 单纯

6、形法一线性规划的标准型LP目标函数有的要求实现最大化，有的要求实现最小化，约束条件可以是“=”、“”，这种多样性给讨论问题带来不便。为了便于讨论，我们规定线性规划问题的标准形式为：Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn=b1 (1) a21x1+a22x2+a2nxn=b2 (2) am1x1+am2x2+amnxn=bm (m) x1 ，x2 ，xn0 第31页/共73页第三节 单纯形法其简缩形式为 一线性规划的标准型njxbxaxcxcxcZjinjjijnn, 3 , 2 , 1,0max12211用向量表示 01jnjjjxbxPnxxx

7、X21mjjjjaaaP21bmbbb21 其中 C=(c1,c2,cn) 向量Pj是其对应变量xj 的系数向量。 第32页/共73页第三节 单纯形法一线性规划的标准型用矩阵描述CXzMax0XbAX mnmnmmnbbbbbPPPaaaaaaA321212111211;第33页/共73页第三节 单纯形法二线性规划问题的解 可行解可行解最优解最优解 基基 设A为约束方程组的mn阶系数矩阵，其秩为m。B是矩阵A中mm阶非奇异子矩阵（ ）,则称B是线性规划问题的一个基。不失一般性可设 0BmmmmmmPPPaaaaaaB212111211称Pj为基向量，与基变量Pj相对应的变量为基变量。否则为非基

8、变量。 第34页/共73页二线性规划问题的解 第35页/共73页nmnnnmmmmmmmmmmmmmxaaaxaaabbbxaaaxaaaxaaa211112112121122212112111nmjjjmjjjxPbxP11或 021nmmxxxTmxxxX)0 , 0 ,(21设非基变量用高斯消去法，可求出一个解称X为基本解基本解基本可行解基本可行解 满足非负条件的基本解二线性规划问题的解 第36页/共73页如何安排生产计划，才能得到利润最多？三单纯形法第37页/共73页 设备产品ABCDx12140 x22204三单纯形法第38页/共73页三单纯形法第39页/共73页引入松弛变量x3 A

9、设备闲置台时数x4 B设备闲置台时数x5 C设备闲置台时数x6D设备闲置台时数将线性规划化为标准型.（8.1） 三单纯形法 求解过程第40页/共73页（8.2） 三单纯形法 求解过程第41页/共73页系数矩阵 100040010004001021000122654321PPPPPPA10000100001000016543PPPPB三单纯形法 求解过程第42页/共73页对应于B的变量x3, x4, x5, x6为基变量，从标准型我们可以得到： （8.3） 三单纯形法 求解过程第43页/共73页TxxxxxxX121681200121681200)0(6)0(5)0(4)0(3)0(2)0(1)

10、0(这个基本可行解表示：工厂没有安排生产产品；设备的有效台时数没有被利用，所以构成的利润为0。 从分析目标函数的表达式可以看到，非基变量x1 ,x2系数都是正数，若将非基变量换成基变量，目标函数就会增加。所以，只要在目标函数的表达式中还存在正系数的非基变量，这表示目标函数还有增加的可能，就需要将非基变量换成基变量。一般选择正系数最大的那个非基变量。可按以下方法来确定换出变量。三单纯形法 求解过程第44页/共73页Z=0+2x1+3 x2 （8.4）3412,28,212min2x时，才能使（8.5）式成立。因当x2=3时，基变量x6=0这就决定用x2去替换x6。三单纯形法 求解过程第45页/共

11、73页三单纯形法 求解过程第46页/共73页TTxxxxxxX)0 ,16, 2 , 6 , 3 , 0(),() 1 (6) 1 (5) 1 (4) 1 (3) 1 (2) 1 (1) 1 (三单纯形法 求解过程第47页/共73页TX)0 , 8 , 0 , 2 , 3 , 2()2(TX)4 , 0 , 0 , 0 , 2 , 4()3(三单纯形法 求解过程第48页/共73页三单纯形法 求解过程小结第49页/共73页jnjjxczMax101jnjjjxbxP10001000121MPPPB三单纯形法 求解过程小结第50页/共73页10001000121MPPPB三单纯形法 求解过程小结第

12、51页/共73页TmnmTmnmbbbxxxX)0, 0,()0, 0,(2121个个，三单纯形法 求解过程小结第52页/共73页nmjjijiixabx1三单纯形法 求解过程小结第53页/共73页nmjjijmiijimiiixaccbcz111)(ijmiijimiiaczbcz110,j=m+1,n nmjjjjxzczz10)(), 1(nmjzcjjjnmjjjxzz10三单纯形法 求解过程小结第54页/共73页TmbbbX)0, 0(, 2, 1)0(0j0kmTmbbbX)0, 0(, 2, 1)0(0,kmia为换入变量则对应的kkjx )0max(ckcikikabaabRi

13、0mincx三单纯形法 求解过程小结第55页/共73页三单纯形表例1第56页/共73页例1第57页/共73页例1第58页/共73页例1第59页/共73页例2第60页/共73页例2第61页/共73页例2第62页/共73页第63页/共73页x x1 1x x2 2x x3 3x x4 4x x5 5x x6 61 10 00 0 x x3 36 60 00 01 13 3/ /2 2- -0 0. .2 25 50 02 20 00 0+ +1 1x x1 16 61 11 10 0- -0 0. .5 51 1/ /4 40 00 0 x x6 63 36 60 0- -1 12 20 0- -

14、9 9- -4 4. .5 51 12 20 00 0+ +1 11 15 50 01 10 00 00 00 00 01 18 80 00 02 20 00 0+ +1 12 20 00 0+ +1 11 10 00 05 50 0- -0 0. .5 51 12 25 5+ +0 0. .2 25 51 10 01 18 80 00 00 0- -5 50 0- -1 10 0- -5 50 0+ +0 0. .5 51 1- -2 25 5- -0 0. .2 25 51 10 0实实际际活活动动松松弛弛活活动动目目标标系系数数行行c cj j机机会会成成本本行行Z Zj j第第三三单单

15、纯纯形形表表C CB BX XB Bb b检检验验数数行行j j-50 1 1001 -501 1001 100 -50-1 0 -50+0.51 0 -25-0.251 0第64页/共73页2 -50-502 0第65页/共73页-100/3 3 1003 -100/33 100 -50-1.53 0 -250.253 0第66页/共73页表8-3 目标系数的允许变动范围活动目标系数当前值可减上限 可增上限 可变范围玉米种植x120050100150300大豆种植x2150无穷大50-200地瓜种植x3100100/3100200/3200 当仅有一种目标系数在允许范围内变动时，最优方案不会

16、变动，但最优目标值会随之变化。 第67页/共73页0360481212/9904/12/104/12/301PBX当右边值发生变化时，如耕地变化，此时，影子价格不变的条件是 第68页/共73页0360481212/9904/12/104/12/3101PBX得到 6+3/210 6-1/210 -414 36-910因此耕地影子价格不变的耕地数量范围为：8，16第69页/共73页0360481212/9904/12/104/12/3201PBX得到 61/420 6+1/420 -2428 36-9/220因此劳动力影子价格不变的劳动力数量范围为：24，56第70页/共73页0360481212/9904/12/104/12/3301