第二十四章 线性规划初步

1、l第一节 线性规划问题的数学模型l第二节 线性规划问题的图解法l第三节 单纯方法初步*第二十四章 线性规划初步 线性规划是运筹学中研究较早如于20世纪30年代，发展较快，应用较广，在理论和方法上比较完善的重要分支.随着科学技术的发展，计算机的普及，线性规划已广泛应用到工业、农业、商业、交通运输、军事及经济管理和经济活动分析等诸多领域. 线性规划研究的问题主要有两大类.第一类是：一项任务确定后，如何统筹安排，使得所用人力、物力资源最少；第二类是：如何对一定数量的人力、物力、财力资源做最有效的分配使用，使得完成的任务最多，收到的效益最高，上述两大类问题，实质上是如何进行有效的经营管理和合理的经济分

2、析工作，以达到良好的经济效果的问题. 线性规划属于应用较广泛的应用数学学科，所以利用线性规划去解决实际问题，首先就要将实际问题进行抽象的概括，转化为数学形式，即建立数学模型.数学模型就是描述实际问题共性的抽象的形式.下面通过实例体会如何建立线性规划问题的数学模型.一、实例1.运输问题的数学模型1212312,.A AB BBA A 设粮库存每月可分别调出粮食28t,29t,粮店每月需粮分别为12t,15t,30t,均由粮库供应各粮库运住各粮店每吨粮食的运费见24-1,问如何安排运输计划,可使运费最少?例1粮库粮店t供应量/t需求量/1B2B3B1A2A表24-1 运费2829202430252

3、2151824121/t元( ),(1,2;1,2,3),ijijABx tij设从 粮库运到粮店的粮食为其中得到运量见表24-2.粮库粮店t供应量/t需求量/1B2B3B1A2A表24-2 运量2829t11x12x13x21x22x23x121530,(1,2;1,2,3)ijxij显然所设变量同时受到供应量与需求量的限制,即1112132122231121122213232829121530 xxxxxxxxxxxx0,(1,2;1,2,3).ijxij并且所有的,S设 表示总运费 则有111213212223182520212224Sxxxxxx:,(1,2;1,2,3)ijxij故所

4、求问题数学模型为 求一组变量的值,使其满足条件11121321222311211222132328291215300,(1,2;1,2,3)ijxxxxxxxxxxxxxij111213212223182520212224().Sxxxxxx并使函数取得最小值总运费最少 上述问题的数学模型属供需平衡的数学模型,而在实际问题中存在大量的供需不平衡问题,若供大于求,则反映在限制条件中是总需求量小于总供给量;若供不应求,则在限制条件中总需求量大于总供量.2.生产组织与计划问题 某工厂生产产品的型号,各车间设备每日的生产能力,各个产品的收以及生产各种产品所需要的设备台时数见表24-3例28181420

5、360022680240024403680项目甲车间/台时乙车间/台时收 入/元产品A产品B产品C产品D生产能力/台时问工厂决定生产哪些产品,生产多少时,能创造更多的收入?表24-3说明,甲车间生产能力为3600台时/d,乙车间生产能力为2400台时/d,生产一件产品A需甲车间设备工作8个台时,乙车间设备工作2个台时,产品B,C,D同理类推.解1234,x x x x设工厂计划生产产品A,B,C,D的产量分别为显然这些变量同时受到甲,乙两车间生产能力的限制,即1234123481814203600226802400 xxxxxxxx1234,.x x x x并且均为非负整数,S设 表示总收入

6、则123424403680Sxxxx于是该问题的数学模型为:1234,x x x x求一组变量的值 使其满足条件12341234818142036002268024000,(1,2,3,4)jjxxxxxxxxxxj并且 为整数123424403680.Sxxxx并使函数取得最大值3.合理下料问题 用长度为500cm的条材,截成长度分别为98cm和78cm的毛坯,要求98cm长的毛坯不得少于10000根,78cm的毛坯不得少于20000根,问怎样截取钢材,才能所用原料最少?例3(),244.首先找出用一根条材截成98cm和78cm的毛坯的所有可能最经济的方案 即使所剩料头最短 见表表24-4

7、不同下方式截取的毛坯根数321270503010653210012345项 目料头长/cm毛坯长/cm下料方式98781B2B3B4B5B6B(1,6),jjBxj 设采用种下料方式所需的条材数为 根显然所设变量受到两种毛坯需求的限制 即1234523456543210000235620000 xxxxxxxxxx(1,6),.jxj 并且为非负整数S设 表示所用原料总数,即123456Sxxxxxx:于是该问题的数学模型为(1,6),jxj 求一组变量的值 使其满足条件12345234565432100002356200000,(1,6)jjxxxxxxxxxxxxj并且 为整数123456

8、()Sxxxxxx并使函数取得最小值 所用原料最少 以上建立了几个生产经济领域中常见的数学模型，此外，还有配料、合理布局等问题，虽然这些问题的内容不同，但它们却有相似的数学形式：即首先设出问题中待定的未知量，称为决策变量；其次找出限制决策变量的条件，称之为约束条件，并且这些问题的约束条件和特点是关于决策量的线性等式或线性不等式.最后给出实际问题要达到的最优化指标函数，称为目标函数，在此，所找到的目标函数的特点是关于决策变量的线性函数， 由于约束条件和目标函数是线性的，所以，具有上述两个特点的数学模型问题称为线性规划问题.二、线性规划问题的数学模型1.线性规划问题的数学模型的一般形式,(1,2,

9、)jxjn求一组决策变量的值使其满足1111221111211222222211221(,)(,)(,)0,(1, )nnnnmmmnnmmja xa xa xbbba xa xa xbbba xa xa xbbbxjn或或或或约束条件或或1122().nnSc xc xc x并使目标函数的值最小 或最大 也可简记为1122min(max )nnSc xc xc xS或11112211112112222222112211(,)(,)(,)0,(1, )nnnnmmmnnmma xa xa xbbba xa xa xbbbS ta xa xa xbbbxjn或或或或或或,Subject to.S

10、 t 式中为英文表示 受约束于2.建立线性规划问题的数学模型的一般步骤(1)从所求问题入手,寻找待求的未知量,即设出决策变量;(2),;从已知条件中找出所有限制决策变量的条件 即寻找约束条件(3)找出目标函数,并给出线性规划问题的数学模型.(.)掌握建立线性规划问题数学模型的方法非常重要 某鸡场有10000只鸡,用动物饲料和谷物饲料混合喂养,每天每只鸡平均食混合饲料1斤,其中动物饲料所点比例不能少于20%,动物饲料每斤0.25元,谷物饲料每斤0.15元,饲料公司每周仅保证供应谷物饲料60000斤.问饲料怎么样混合,才能使成本最低(1斤=500g)?例4因所求的问题是成本最低,而谷物,动物饲料单

11、价已知,故待定变量为购买动物,谷物饲料的数量.解1212,xxSx x设每周购买动物,谷物饲料的量为 斤, 斤,总成本为显然受一星期所需混合饲料公司供应量以及动物饲料所占比例的约束.12,x x于是该问题的数学模型为:求一组变量的值 使其满足12121210000 770000 20%600000,0 xxxxxx约束条件120.250.15.Sxx并使目标函数取最小值 线性规划问题的数学模型是前面所述的两类实际问题的抽象数学形式，反映了客观事物数量的本质规律.在该问题中，满足所有约束条件的解称为线性规划问题的可行解.全部可行解的集合称为可行解集.在可行解中，使目标函数取得最大值或最小值的解，

12、称为最优解.在实际建模过程中，要根据实际问题，抓住最本质因素，剔除次要因素，建立一个既简单而又比较真实反映问题本质规律的模型. 在前一节中，介绍了线性规划问题的数学模型及建立的方法.以后将介绍线性规划问题的解法及解的性质.由二元不等式的知识得到启示，可以利用作图的方法即图解法去求解最简单的线性规划问题仅含两个决策变量的线性规划问题.一、图解法 求解下列线性规划问题例112maxSxx1212125457350,0 xxS txxxx1212,xxxOx以 为横坐标 以 为纵坐标建立直角坐标系在该坐标系中分别作出直线1122312:5,:4,:5735lxlxlxx,找出满足每个不等式的解所在半

13、平面 并在图中标出,如图24-1所示.解图24-1 例1示意图1x2xO0S 2S AB1lMN2l.OABMNDDD 图中凸多边形即区域 是满足所有约束条件的半平面的公共部分,因此 上的每个点坐标都是该规划问题的可靠的可行解,故称 为该规划问题的可行解域1212,0,2,0,2,DSSSxxxxSDBB为在可行解域 中找出使目标函数取得最大值的最优解 令目标函数 为一大一小的数.即不妨令作两条直线因在这样的直线上 任意点的坐标代入方程 函数值不变 故称之为等值线.由两条等值线的位置可知,当 值越大 等值线越远离点 因求目标函数最大值 故平移等值线 在区域 上找一点,使得过该点的等值线离原点最

14、远,图中 点即为所求的点 解方程组 求 点的坐标.先解方程组12157355xxx121210105,5,.7745,max.7BxxSxxS得于是该规划问题的最优解为代入得1257,45.7SxxBMBMS若在例1中的目标函数改为因离原点最远等值线与线段重合 所以线段上的每一点的坐标都是最优解.故该规划问题有无穷多解,并且其对应的最大值都是 求解下列线性规划问题例212maxSxx12121212360,0 xxS txxxx12,242.xOxD在直角坐标系中 作出满足所有约束条件的可行解域如图所示0,1,SS令作等值线 显然 在无界可行解域上找不到一点使得过该点的等值线离原点最远.故该规

15、划问题无解.解图24-2 例2示意图O0S 1S 12236xx1x2x121xxAD1212min,242,3 838,min5 55511.5SxxSDAxxS若将该问题的目标函数,改为则由图可知当 的值越小 等值线离原点越近 平移等值线,在可行解区域 上找一点 使得过该点的等值线距离原点最近,这个点就是 点 其坐标为因此 得到该问题最优解最优值为 求解下列线性问题例312min22Sxx121212120,0 xxS t xxxx 图24-3 例3示意图O1x2x112xx 111xx12,xOx在直角坐标系中作出满足各约束条件的解 如图24-3所示.显然,同时满足几个约束条件的可行解不

16、存在,故该规划问题无解.通过以上几个实例给出利用图解法求解线性规划问题的步骤.二、图解法求解步骤(1);D建立直角坐标系,并通过作图寻找可行解域(2)0,SSa作两条等值线 判断等值线的大小与其离原点远近关系,以此断定目标函数值的变化与等值线位置变化的关系;(3),D平移等值线至可行解域 上 找出最优解或判定无解;(4)求出最优解和最优值.三、重要结论(1)线性规划问题的任意两个可行解连线上的点都是可行解,即可行解域是凸集;(2),();线性规划问题如有可行解 可能有三种情形:惟一解,无穷多解或无 最优 解(3),可行解域的顶点称为基础解 线性规划问题的最优解可以在顶点上达到.因线性规划问题可

17、行解域的顶点有限,由结论(3)可知,最优解可以在有限个顶点中寻找,即通过代数迭代的方法,从一个顶点迭到另一个顶点,去寻找最优解,这种求解思想正是单纯形方法求解的根据.一、线性规划问题的标准形为了寻求含有多个决策变量的线性规划问题的解法以及讨论和计算的方便,在此给出线性规划问题的标准形.1.线性规划问题的标准形1122minnnSc xc xc x111122112112222211220,(1,2, )nnnnmmmnnmja xa xa xba xa xa xbS ta xa xa xbxjn1212,( ,)( ,).TnnCc ccXx xxS式中 令为决策变量在目标函数 中系数1112

18、12122212.nnmmmnaaaaaaAaaa为系数矩阵12,(1,2, ),jjjmjaaPjna12mbbbb分别为决策变量的系数列向量和常数列向量.这时线性规划问题的标准形可表示为minSCX0AXbS tX2.标准形的化法(1),.SSSS 若求目标函数 的最大值,则可令使之转化为求目标函数的最小值(2),若存在不等约束 则需引入松弛变量 通过加上或减去一松弛变量,使之满足等式约束.(3), 若某一决策变量无非负约束 则可引入两个非负变量,令其为所设变量的差即可. 将下列规划问题化为标准形例1123max34Sxxx1312312232400 xxS txxxxx 4533333,

19、0,0,0,0,SSxxxxxxx 令引入松弛变量及非负变量并令则原问题的标准形为1233min34(),Sxxxx133412335332()32()40,(1,2,4,5).0,0jxxxxS txxxxxxjxx解二、单纯形方法初步G.B.Duntzg1947,.单纯形方法是借助于线性方程组,矩阵及初等变换知识设计出来的一种代数迭代方法,它是美国数学家于年首先提出的 至今这一数学方法仍然是解线性规划问题行之有效的方法,为研究方便 不妨设线性规划问题为minmin,(),0SCXR Am b其中0AXbS tX1.几个概念(1),AmmB 由系数矩阵 中的任意 个线性无关的列向量构成的 阶

20、可逆阵 称为规划问题一个基 记为由单位向量构成的基最简单.基(2) ,.BNXX变和变基中系数列向量所对应的决策变量 称为基变量,记为其余变量为非基变量,记为基量非基量2.求解方法,0,;,BNBNNNBXXSXXSXBXS 首先找出一个基 及相应的基变量并用非基变量表示目标函数 和然后取非基变量即可得到一基础解和相应的目标函数值.若在 的表达式中的系数不小零 则该基础解是最优解,基 就是最优基 若的系数有负数 则说明 的值仍可减少,该解就不是最优解,此时需要换基.S 换基的方法是:为了保证换基后所换变量在目标函数中的系数不小于零.则在 的表达式中找绝对值最大的负数对应非基变量作为换入的新基变

21、量,为保证新基变量取值非负,则在所选非基变量 的系数列向量中,选正分量所对基变量为换出变量.若无正分量,则规划问题无解.若有多个正分量,则用正分量去除相应的常数项取最小的商所对正分量.得到新基后,重复上述步骤,只要规划问题有最优解,那么若干次换基后就可求出最优.这种求解方法就叫单纯.形方法:可以验证 单纯形方法的求解过程实际上是对一个矩阵进行初等变换的过程,以下举例说明. 求解线性规划问题例212min2Sxx 12312443260,(1,2,3,4)jxxxS txxxxj由已知解1110,3201A4,6b ( 1,2,0,0)C 3134410(,).,01BxBP PXx 取基相应的

22、基变量为根据已知条件列表24-6.1246()T B表 单纯形式01-20041110632011()T BS3x4x1x2x3x4x11(),BT B称为基 对应的单纯形式表由表中易得12120()2Sxxxx 312124()4xxxxx412126(32)632xxxxx12141231310,0,0(0,0,4,6),1()1),.,min4/1,6/3=6/3,(,),BxxST BSxxBP PxXx令代入得及基础解此与已知基求相应的目标函数值和基础解的结果一致.因目标函数中存在负数表中与之相应的是在 行存在正数所以需换基 由换基方法 知 因故将 换出 将 换入得新基与之相应的基变

23、量为表达式为24248181223333Sxxxx 324241111223333xxxxx124242121223333xxxxx22()247BT B由此可得基对应单纯形表见表2247()T B表 单纯形表2()T BS3x1x2083-1323013-13-132200101x2x3x4x247,(2,0,2,0),min2.SS 由表可知行无正数 故基础解为规划问题的最优解 最优值为从上述解题过程中,注意到以下几个问题.(1),单纯形表的特点是基变量所在列中只有与该基变量所在行交叉处为1,其余元素均为0.21122(2) ()(),()().T BT BT BBT B 是由经过若干次初等行变换得到的 方法是换基后,按单纯形表的特点将变换成基对应的单纯形表(3)( ),;T BSSSS利用单纯形表可直接求解,方法是在单纯表中 若 行有正数,则需换基,但在此是找 行最大的正数下方的正分量换基;若行无正数 则该基就是最优基 若 行有正数且正数下方无正分量,则无解. 求解下列规划问题例3123minSxxx 12312123231223340,(1,2,3)jxxxxxS txxxxj:将规划问题化为标准形123minSx