高等代数在线性规划中的.docx
12页
高等代数性规划中的应用学号：姓名： 班级: 摘要：随着科技的发展，社会的进步，数学在实际生活中的应用越来越广泛数学的任务， 已不仅仅是为数学自身学科分支的完善，解决自身内部提出的问题，而是更好地应用，为经 济的发展，社会的进步做出应有的贡献马克思曾说过：“一门学科，只有成功应用了数学时, 才真正达到了完善的地步本学期，我们学习了高等代数，如多项式、行列式、线性方程组 等通过查阅各种资料，我们对高等代数在实际生活中的应用有了更多的了解在本篇论文 中，我将运用线性方程组、矩阵等知识，运用LINGO软件进行编程，解决线性规划中的一些 问题，求出最优解关键词：线性方程组、矩阵、线性规划、最优解1・线性规划问题的数学模型 2.线性规划问题的标准型 3.基本概念1.线性规划问题的数学模型引例 某工厂生产一种型号的机床，每台机床上需要2.9叭2. Im和1.5m长的三种轴各一 根这些轴需要同一种圆钢制作，圆钢的长度为7.4m,如果要生产100台机床，应如何下料, 才能使得用料最省？分析：对于每一根长为7. 4m的圆钢，截成2. 9m、2. Im和1. 5m长的毛坯，可以有若T•种 下料的方式把它截成我们需要的长度，有8种下料方式，如下表：下料方式及每种类型的数目B\B、B?需要量2. 9m211100001002. Im021032101001. 5m10130234100余料0. 10.30.901. 10.20.81.4100下料方式是按从大到小，从长到短的顺序考虑的：（1） 若考虑用鸟方式下料，需要用料100根；（2） 若采用木工师傅的下料方法：先下最长的，再下次长的，最后下短的，如下表所示。
动一下脑筋，就可以节约用料4根，但这仍然不是最好的下料方法木工师傅的下料情况下料方式下料根数2. 9m根数2. lin根数1. 5m根数B\50100050B,3309901200481022合计96100101100（3）如果要我们安排下料，暂不排除8种下料方式中的任何一种，可通过建立数学模型（线 性规划数学模型）进行求解，寻找最好的下料方案设用目，B2, b3, b4, b5, B6, B7, BJ方式下料的根数分别为兀］、兀2、兀3、兀4、兀5兀6,兀7,兀8,则可以建立线性规划数学模型：minS二兀| +兀2 +兀3 +兀4 +兀5 +兀6 +兀7 +兀82X] + x2 + x3 + x4 > 1002x2 + 兀3 + 3x5 + 2兀 + x7 > 100X] + 尢3 + 3x4 + 2x6 + 3x7 + 4x8 > 100用LINGO软件求解，程序如下:minst2xl+x2+x3+x4>=1002x2+x3+3x5+2x6+x7〉=100xl+x3+3x4+2x6+3x7+4x8>=100end根据输出结果，得Xj=10,兀2 =50,无3=，兀4 =30,兀5=0,兀二，x7=0, x8=0, min S=90;或X] =40, x2 =20,兀3二0, x4 =0, x5=0,兀6=30, x7 =0, x8=0, minS=90,这就是最优的下料方案。
下料问题是经济管理中经常要遇到的问题，引例是条材下料的问题，此外还有板材下料 的问题和更复杂的下料问题明确问题中有待确定的未知变量（称为决策量），用数学符号来表示； 明确巴题所有的限制条件（约束条件），用决策变量的一组表达式（线性 来表示；明确解决问题的冃的，并用决策变量的线性函数（称为冃标函数）表示,在生产管理和经验活动中，经常要考虑这样一类问题：如何合理地利用有限的人力、物 力和财力等资源，以得到最好的经济效果建立线性规划问题数学模型的基本要素：（1） 决策变量（2） 约束条件 等式或线性不等式）（3） 目标函数按问题的要求，求其最大值与最小值我们把决策变量、约束条件、目标函数称为线性规划数学模型的三个基木要素下面从 几个方面介绍典型的建立线性规划模型的方法例1 某工厂生产一种型号的机床，每台机床上需要2. 9m、2. Im和1. 5m的三种轴分 别为1根、2根、1根，这些轴需要用同一种圆钢制作，圆钢的长度为7. 4mo如果要生产100 台机床，应如何下料，才能使得用料最省？解 关于下料方式的分析如引例，下料方式见引例的表设用方式下料的根数分别为兀］，兀2,兀3，兀4,兀5，兀6，兀7,兀8 则可以建立问题的线性规划数学模型:minS 二 x( + x2 + + x4 + x5 + x6 + x7 + x82x, + 兀2 + 兀3 + 尤4 n 1 00s. t. <2x2 + x3 + 3兀5 + 2x6 + x7 > 100兀]+ 兀3 + 3 兀4 + 2 兀6 + 3 兀7 + 4兀8 - 1 0()兀]，兀2，兀3，兀4,兀5,兀6,兀7，兀8LTNDO 软 件X] = 0,兀2 — 80,兀3 = ，兀4 = 20,x5 = 0,x6 = 20,x7 = 0,x8 = 0, minS=120例2 某公司饲养实验用的动物以供出售。
已知这些动物的生长对饲料中的三种营养成 分(蛋片质，矿物质和维生素)非常敏感，每只动物每天至少需要蛋片质70g,矿物质3g, 维生素10mg.该公司能买到5种不同的饲料，每种饲料lkg所含各种营养成分和成本如下表所 示求既能满足动物生长需要，乂使总成本最低的饲料配方配料问题的数据A%4A4营养最低要求蛋白质(g)0.3210.61.870矿物质(g)0. 10. 050. 020.20. 053维生素(mg)0. 050. 10. 020.20. 0810成本0.20.70.40.30.5解：设需要5种饲料数量分别为x,,x2,x3,x4,x5kg,则可建立线性规划数学模型：minS=O. 2 兀]+0. 7 x2 +0. 4 x3 +0. 3 x4 +0. 5x50.3xj + 2x2 + 兀3 + 06兀4 + 1.8x5 > 700.1 Xj + 0.05x2 0.02x3 0.2x4 0.05x5 > 3 s. t. <0.05X| + 0.1x2 0.02x. 0.2x4 0.08x5 > 10通过LINGO求解，程序为：min 0. 2x1+0. 7x2+0. 4x3+0. 3x4+0. 5x5 0.3xl+2x2+x3+0. 6x4+1.8x5>=700.lxl+0.05x2+0. 02x3+0. 2x4+0. 05x5>=30.05x1+0.1x2+0. 02x3+0. 2x4+0. 08x5>=10end求解，得兀]=0,兀2 = 0,兀3 = 0,勺=39.74,兀5 = 25.64, minS=24. 74例3 设有n件工作d，B2 ,…，B”分派给n个人人，血，…，代去做，每人只能做一件工作，且每一件工作只能分派给一个人去做。
设如完成为的工时为(?.. (i, j=l, 2, --n),如下表所示，问：应如何分派，才能使完成全部工作所需的总工时最少?一般指派问题的效率数据• • •B“AC\2• • •C\nA^21^22• • •C2n• • •• • •• • •• • •• • •4C‘2”• • •%/ 、C】1 12 …C\n解：称由工作时间组成的矩阵C二％ 5…5〃为效率矩阵• •• ••• •••C"2 …Cnn ）设第个人&•完成工作Bj的情况为分派如完成工作Bj _[0不分派4浣成屛"2・・丿）则有:minS=ZXc；xv工>1|=1切=心=1,2,・丿）这就是求最小指派问题的数学模型Xjj =0或1(门=1,2,..*)2.线性规划问题的标准型第一章的实际问题对应的线性规划模型可以有多种不同的形式，不同形式给求解带來了 不便为了便于研究，我们规定其中的一种形式为标准型，线性规划问题的标准型为：］］兀］+ al2x2 + ... + ahJxfJ = b、d］2尢］+ a21x2 +・・・+ ^2打尢"=*內 +〜2 兀2 +•••+“九二—hx > 0,h2 > 0,.・•，船 > 0如果线性规划问题不满足标准型的要求，则可通过以下步骤化成标准型:（1） 目标函数的改写：化求最小值为求最大值；彳各 minS二C]X|+5兀2+・・・ + c“x” ” 改为 “maxS =-3=-€^} -c2x2 - 1（2） 化不等式约束为等式约束；若 ％兀]+%兀2 +・・・ + %届 ~^k 则化为“2】+ @2 兀 2 +•••% + S = hkI 兀士》若d/內+ al2x2 +・・・ + d]n兀“、b[,则化为14內+切2尢2 +…+仏心一兀硼=btI 兀比二增加的变量兀点，陥/等成为松弛变量（3） 对于没有非负限制的化为有非负限制。
若无无非负限制，则引进xk >0,x* >0,化为xk=xk-xk（4） 如果约束条件右端的常数项小于0,则用-1乘以该式两端即可例1 将线性规划问题minS二一兀| +2兀2 -3x3%)+ x2 + x3 < 7 尢］一尢2 +尢3 2一 2兀 1 + 兀2 + 2 兀3 = 5 兀］> O,x2 > 0,兀3无符号限制化为标准型解：标准型为X)+ 兀2 + X； —兀(+ 兀4 = 7 尢]—尢尢 _尤3 —兀5 =2 —2尤]+尢乍+ 2尤3 — 2兀3 = 5 x},x2,x^x4,x5 >0若记 C 二仏疋2,…,“），、… a\n/ \(J \，b\A 二a2\• • •• • •…a2n• • •,X=X.,b=h2• • •a泌…mt i /E丿则可将线性规划问题表示成矩阵形式：maxS=CXX>0或记A^11a2\… p，rn，分别为兀i，兀2,…,”的系数列向量，则该线性规划问题可表示成向量组合形式:niaxS 二 C]X] + c2x2 +... + C后s. t.Pg + P2x2 + ...Pnx = bx},x2,x3...xn > 03.基本概念设有线性规划问题(LP)： maxS=CX\AX=bs. t.
最优解：使目标函数取到最大值的可行解，称为（LP）的最优解若系数矩阵&宓“的秩为m,称A的任一 n?x加的非奇异子矩阵B = （Pj、PJ2 ... PJm）为线性规划问题（LP）的一个基，当B =（Pyi Pj2 ...仏）为线性规划问题（LP）的一个基时,Pj\,Pj”・・,Pm称为基向量，勺,。
