经济应用数学6.5线性规划初步ppt课件

1、上页下页铃结束返回首页经济应用数学经济应用数学 16.5 6.5 线性规划初步线性规划初步一、线性规划的数学模型一、线性规划的数学模型二、两个变量线性规划问题的图解法二、两个变量线性规划问题的图解法三、单纯形法三、单纯形法 上页下页铃结束返回首页经济应用数学经济应用数学 2一、线性规划的数学模型一、线性规划的数学模型1 1 线性规划问题实例线性规划问题实例例例5 51 1 （配料问题某工厂在计划期内要生产甲、乙两（配料问题某工厂在计划期内要生产甲、乙两种产品，已知生产单位产品所需要的设备台时，种产品，已知生产单位产品所需要的设备台时，A A、B B两种两种原材料的消耗以及每件产品可获得的利润见

2、下表问应如原材料的消耗以及每件产品可获得的利润见下表问应如何安排生产计划使得该工厂获得利润最多？何安排生产计划使得该工厂获得利润最多？产品消耗材料甲乙资源限量设备8（台时）原材料17 (千克)原材料12（千克）单位产品利润（万元）54上页下页铃结束返回首页经济应用数学经济应用数学 3 解解 设设 、 分别表示在计划期内产品甲、乙的产量，分别表示在计划期内产品甲、乙的产量，1x2x，z表示利润由于资源的限制有表示利润由于资源的限制有z12max54zxx利润利润的最大化的最大化，受条件受条件121212284174120,0 xxxxxx这就是该问题的线性规划问题的数学模型这就是该问题的线性规划

3、问题的数学模型的限制的限制2A 例例5 52 2 （运输问题在（运输问题在 A1A1、A2A2两个粮库里分别装有两个粮库里分别装有6 6吨玉米和吨玉米和102102吨玉米，要运到吨玉米，要运到 B1B1、B2B2、B3B3 三个市三个市 上页下页铃结束返回首页经济应用数学经济应用数学 4场去出售三个市场的需求量分别是场去出售三个市场的需求量分别是3434吨、吨、7575吨、吨、4949吨，吨， 各仓库到各市场的运价元各仓库到各市场的运价元/ /吨）吨） 见表见表6 63 3 如何调运，才能使总运费最省？如何调运，才能使总运费最省？ 表表6 63 3仓库到市场的运价表单位元仓库到市场的运价表单位

4、元/ /吨吨市市场场运运价价仓仓库库 B B1 1 B B2 2 B B3 3 A A1 1606070709090 A A2 2757580807070ijxiAjB解解 以以表示从仓库表示从仓库运到市场运到市场的玉米数量，的玉米数量， 显然显然0(1,2;1,2,3)ijxij 上页下页铃结束返回首页经济应用数学经济应用数学 511121356xxx212223102xxx1 12 13 4xx122275xx132349xx0(1,2;1,2,3)ijxij 根据分析，将其转化为数学问题：根据分析，将其转化为数学问题： 就是求一组变量就是求一组变量ijx的值，使它满足限制条件：的值，使它

5、满足限制条件： 并使运费最小，即并使运费最小，即 111213212223min607090758070zxxxxxx例例5 53 3某商业银行开展贷款业务，有两种方案可供某商业银行开展贷款业务，有两种方案可供 上页下页铃结束返回首页经济应用数学经济应用数学 6选择方案每一元贷款一年后可获利润选择方案每一元贷款一年后可获利润0 07 7元；元； 方案每一元贷款两年后可获利润元在方案方案每一元贷款两年后可获利润元在方案中，要求贷款的时间是两年的倍数，要想在第三年中，要求贷款的时间是两年的倍数，要想在第三年 年底所获本利最多，应该怎样贷款年底所获本利最多，应该怎样贷款1 000 0001 000

6、000元？元？ 按方案进行投资，投资按方案进行投资，投资1x元到第三年年底的本利和为元到第三年年底的本利和为3311(10.7)1.7xx（元），（元）， 按方案进行投资，投资按方案进行投资，投资 元到第二年年底的本利和为元到第二年年底的本利和为2x解解 设方案设方案A A的投资为的投资为 元，方案的投资元，方案的投资 元元1x2x22(1 2)3xx（元），（元），然后再把然后再把 元按方案进行投资到第三年年底的本利和为元按方案进行投资到第三年年底的本利和为23x上页下页铃结束返回首页经济应用数学经济应用数学 722230.7 (3)5.1xxx元，因而，到第三年年底商业银行可获得本利和为因

7、而，到第三年年底商业银行可获得本利和为3121.75.1zxx由此题的条件可知，由此题的条件可知，121 000 000 xx 根据以上分析将其转化为数学问题就是根据以上分析将其转化为数学问题就是求满足约束条件求满足约束条件 12121000 0000,0 xxxx 下，使下，使 312max1.75.1zxx的解的解 2 2 线性规划问题的标准形式线性规划问题的标准形式上页下页铃结束返回首页经济应用数学经济应用数学 8 目标函数为：目标函数为： 1 122maxnnzc xc xc x约束条件为：约束条件为： 11 11221121 1222221 122(0,1,2, ,)nnnnmmmn

8、nmia xa xa xba xa xa xba xaxaxbxin在约束条件中，在约束条件中，ix称为决策变量这种形式的线性规称为决策变量这种形式的线性规划问题称为线性规划问题的标准形式划问题称为线性规划问题的标准形式 其特征为：其特征为：（所有约束条件都由等式表示，且等式右端的（所有约束条件都由等式表示，且等式右端的常数非负；常数非负；上页下页铃结束返回首页经济应用数学经济应用数学 9（决策变量（决策变量ix非负；非负；（求目标函数的最大值（求目标函数的最大值用矩阵形式表示为：用矩阵形式表示为： 12mbbBb max zCX0AXBX12( ,)nCc cc111212122212nnm

9、mmnaaaaaaAaaa12nxxXx其中其中 例例5.4 5.4 将下列线性规划数学模型化成标准形式将下列线性规划数学模型化成标准形式设目标函数设目标函数 123max337zxxx上页下页铃结束返回首页经济应用数学经济应用数学 10约束条件约束条件 12312312123340975053200,0,xxxxxxxxxxx 无符号限制解解 因为因为3x没有非负限制，引入新变量没有非负限制，引入新变量 33,xx使使 333xxx；引入松弛变量；引入松弛变量45,x x 则化成标准型为则化成标准型为1233max337()zxxxx1233412335121233453()4097()50

10、5320,0 xxxxxxxxxxxxx x xxx x上页下页铃结束返回首页经济应用数学经济应用数学 11 二、两个变量线性规划问题的图解法二、两个变量线性规划问题的图解法12121212236323240,0 xxxxxxxx2134xxz例例5 55 5 求求的最大值，约束条件为的最大值，约束条件为1x2x 解解 以以为横坐标轴，为横坐标轴，为纵坐标轴，建立坐标系为纵坐标轴，建立坐标系 1x2x0 0C C1.51.5，1 1） 1, 5 . 121xx9max z即即，上页下页铃结束返回首页经济应用数学经济应用数学 12例例6 6 用图解法解线性规划问题用图解法解线性规划问题 解解 步

11、骤同前题，画出可行域步骤同前题，画出可行域 1x2x0 0阴影部分是无界区域阴影部分是无界区域 因为可行域无界，所以找不到因为可行域无界，所以找不到 z 的最大值，故无最优解的最大值，故无最优解12max22zxx1212121200,0 xxxxxx 上页下页铃结束返回首页经济应用数学经济应用数学 13三、单纯形法三、单纯形法1 1 线性规划问题的基与解线性规划问题的基与解max zCX0AXBX设线性规划问题的标准形式用矩阵表示为：设线性规划问题的标准形式用矩阵表示为： A()m m nA假设矩阵假设矩阵的秩为的秩为，则称，则称中任意一个中任意一个m m阶满秩矩阵为该线性规划问题的一个基阶

12、满秩矩阵为该线性规划问题的一个基 如果变量如果变量 所对应的列所对应的列 jx12jjjmjaaPa上页下页铃结束返回首页经济应用数学经济应用数学 14则称则称 为基变量。为基变量。jx其余的其余的nm个变量称为非基变量个变量称为非基变量 例例5.8 5.8 设有线性规划问题设有线性规划问题 12max23zxx123124152212284160(1,2,3,4,5)xxxxxxxxxj，写出它的一个基和该基对应的基变量和非基变量写出它的一个基和该基对应的基变量和非基变量解解 约束方程组的系数矩阵约束方程组的系数矩阵 221001201010001A显然矩阵显然矩阵 是该线性规划问题的一个基

13、是该线性规划问题的一个基1100010001A它所对应的基变量是它所对应的基变量是 345,x x x非基变量是非基变量是12,x x 上页下页铃结束返回首页经济应用数学经济应用数学 15 在标准形式的线性规划中，非基变量取零值的可行在标准形式的线性规划中，非基变量取零值的可行解叫做线性规划问题的基本可行解，相对应的基叫做基解叫做线性规划问题的基本可行解，相对应的基叫做基本可行基最优的基本可行解叫最优解，所对应的基叫本可行基最优的基本可行解叫最优解，所对应的基叫最优基最优基2 2 单纯形法单纯形法例例5.9 5.9 用单纯形法求下面线性规划问题的最优解用单纯形法求下面线性规划问题的最优解解解

14、本题的约束条件的线性规划问题已经是标准形，本题的约束条件的线性规划问题已经是标准形，约束方程组的系数矩阵为约束方程组的系数矩阵为 12max23zxx123124152212284160(1,2,3,4,5)xxxxxxxxxj，2 2 1 0 01 2 0 1 01 0 0 0 1A上页下页铃结束返回首页经济应用数学经济应用数学 16，选可行基1100010001A所对应的基变量就是345, ,x x x1. 作出对应的单纯形表6 2 2 1 0 0 1 （2） 0 1 0 4 0 0 0 1 181 2 3 0 0 0 0 bx1x2x3x4x5x b3x4x5xz表中最左边的列 是基变量

15、，bx第一行是所有变量， 中间是系数矩阵， 最右边的 列是常数列，b最下边 z行是目标函数各变量相对应的系数，叫做检验数， 上页下页铃结束返回首页经济应用数学经济应用数学 17该行也叫做检验行检验行与该行也叫做检验行检验行与b b列相交的数值为目标函数值的相列相交的数值为目标函数值的相反数，即非基变量取零时的基本可行解反数，即非基变量取零时的基本可行解 10012816X2 2 判定最优解判定最优解（1 1若所有检验数若所有检验数 均小于或等于零，均小于或等于零，(1,2,3,4,5)jj则已求得的基本可行解就是最优解；则已求得的基本可行解就是最优解； （2 2若检验数中有正数，正数所对应的列

16、中均为非正数则问若检验数中有正数，正数所对应的列中均为非正数则问 题无最优解；题无最优解；（3 3若检验数中有正数，且这些正数所在的列中的其他元素若检验数中有正数，且这些正数所在的列中的其他元素 有正数则需要继续改进来寻找更优的解有正数则需要继续改进来寻找更优的解上页下页铃结束返回首页经济应用数学经济应用数学 18 在本例题中在本例题中 , , 因而因而 不是最优解不是最优解122,31X3 3 改进基本可行解改进基本可行解 （1 1选主元选主元 当表中有正检验数时，为了使目标函数值尽可能的提当表中有正检验数时，为了使目标函数值尽可能的提高，一般选择检验数大的所在列对应的非基变量为进基高，一般

17、选择检验数大的所在列对应的非基变量为进基变量，用该列上各正数去除同一行中变量，用该列上各正数去除同一行中b b列上的元素，比列上的元素，比值最小者所对应的除数即为主元，用（值最小者所对应的除数即为主元，用（ ）标出主元所）标出主元所对应的变量即为出基变量对应的变量即为出基变量在本例题中，最大检验数在本例题中，最大检验数 ，最小比值为，最小比值为2312 8min,422上页下页铃结束返回首页经济应用数学经济应用数学 19所以为所以为 主元，主元， 进基，进基， 为出基变量为出基变量222a2x4x(2)(2)换基迭代换基迭代方法是：对单纯形表施行初等行变换使主元变为方法是：对单纯形表施行初等行

18、变换使主元变为1 1， 主元所在的列上的其余元素全都化为零主元所在的列上的其余元素全都化为零得单纯形表65 1 0 1 -1 0 1 0 0(4) 0 0 0 1 4 4 16 1/2 3 0 -3/2 0 -12 bx1x2x3x4x5xb3x2x5xz上页下页铃结束返回首页经济应用数学经济应用数学 20由表由表5 5可知，基变量为可知，基变量为 ，非基变量为，非基变量为 325,x x x基本可行解为基本可行解为14,x x2044016X检验数为检验数为112， 所以不是最优解，所以不是最优解， 选选1x进基，进基， 由最小比值法由最小比值法 4 4 16min,1142选选5x出基，出

19、基， 可得可得 表表6 66 6 0 0 1 -1 -1/40 0 1 -1 -1/40 1 0 -1/8 0 1 0 -1/8 1 0 0 0 1/4 1 0 0 0 1/4 0 02 24 4 0 0 0 -3/2 -1/8 0 0 0 -3/2 -1/8 bx1x2x3x4x5xb3x2x1xz1 4/上页下页铃结束返回首页经济应用数学经济应用数学 21由于检验数均小于等于，因此为最优解由于检验数均小于等于，因此为最优解 此时，最优解为此时，最优解为 342000X 此时目标函数的最优值为此时目标函数的最优值为14z 例例5 510 10 用单纯形法解线性规划问题用单纯形法解线性规划问题12max33zxx 12312412526231840(1,2,3,4,5)ixxxxxxxxxxi解解 345,x x x12,x x 为基变量，为基变量，为非基变量为非基变量 上页下页铃结束返回首页经济应用数学经济应用数学 22 列单纯形表，在做题时将单纯形表合并在一起，列单纯形表，在做题时将单纯形表合并在一起， 见下见下表表6 67 7bx1x2x3x4x5xb3x4x5xzbx1x2x3x4x5xb3x4x2xz 2 -