您好,欢迎访问三七文档
线性规划(LinearProgramming)线性规划问题及其数学模型线性规划问题的求解方法线性规划的图解法线性规划的单纯形法单纯形法的进一步讨论线性规划模型的应用为了完成一项任务或达到一定的目的,怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的,这个过程就是规划。例一、有一正方形铁皮,如何截取x使容积为最大?xa22xxav此为无约束极值问题02222)()()(xaxxa6ax0dxdv一、线性规划问题及其数学模型(一)、问题的提出设备产品ABCD利润(元)Ⅰ21402Ⅱ22043有效台时1281612例二、已知资料如下表所示,问如何安排生产才能使利润最大?或如何考虑利润大,产品好销。模型maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题问题中总有未知的变量,需要我们去解决。要求:有目标函数及约束条件,一般有非负条件存在,由此组成规划数学模型。如果在规划问题的数学模型中,变量是连续的(数值取实数)其目标函数是有关线性函数(一次方),约束条件是有关变量的线性等式或不等式,这样,规划问题的数学模型是线性的。反之,就是非线性的规划问题(其中一个条件符合即可)。(二)、数学模型1、0012211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcZ)()((min)max目标函数:约束条件:①②③2、线性规划数学模型的一般形式也可以记为如下形式:)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj目标函数:约束条件:如将上例用表格表示如下:设变量)21(njxj产品j设备i有效台时利润mnmijnaaaaa1111n21m21mbbb21nccc21jcib向量形式:)(21ncccCnxxX1mjjjaap1mbbb10)((min)maxXbxpCXZjj矩阵形式:mnmnaaaaA11110)((min)maxXbAXCXZ规划确定型随机型静态规划动态规划线性规划非线性规划整数规划非整数规划整数规划非整数规划3、规划类型一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但需将一般形式变成标准形式二、线性规划问题的求解方法(一)、求解方法1、解的概念⑴可行解:满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。⑵最优解:使目标函数达到最大值的可行解。⑶基:B是矩阵A中m×n阶非奇异子矩阵(∣B∣≠0),则B是一个基。)(211111mmmmmpppaaaaB则称Pj(j=12……m)为基向量。∴Xj为基变量,否则为非基变量。(二)、线性规划问题的解⑷基本解:满足条件②,但不满足条件③的所有解,最多为个。Cmn⑸基本可行解:满足非负约束条件的基本解,简称基可行解。⑹可行基:对应于基可行解的基称为可行基。非可行解可行解基解基可行解Maxz=2x1+3x2st.x1+x2≤3x1+2x2≤4x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3x1+2x2+x4=4x1,x2,x3,x4≥0A=x1x2x3x411101201可行解:X=(0,0)T,X=(0,1)T,X=(1/2,1/3)T等。设B=1001,令,则|B|=1≠0,令x1=x2=0,则x3=3,x4=4,X=(0,0,3,4)T例:x3x4——基变量令B=1110x1x3,则令x2=x4=0,则x3=-1,x1=4,X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解标准化例2.2某地区有三个矿山A1,A2,A3,生产同一种矿物。另外有四个这种矿物消费地(铁厂)B1,B2,B3,B4。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表2-2。问应如何调运,才使总运费最省?(一)运输问题的数学模型表2-2铁厂运价(元/t)矿山B1B2B3B4产量(t)A1A2A31.571.220.80.30.31.42322.51008050需量(t)50708030•解:该题有两个限制条件:一个是产量,一个是需量。目标是总运费最省。设:xij表示从第i个矿山运往第j个铁厂的矿物运量。这样得到以下两组线性方程组:(1)各矿山矿物的生产量与运出量平衡方程:1112131421222324313233341008050xxxxxxxxxxxx(2)各铁厂矿物供应量与需要量平衡方程11213112223213233314243450708030xxxxxxxxxxxx(3)矿物的运输量应非负0(1,2,3,1,2,3,4)ijxij(4)目标函数111213142122min1.520.3370.8Zxxxxxx2324313233341.421.20.322.5xxxxxx(二)资源最优利用的数学模型例2.3某厂生产A、B产品1kg需用资源数见表2-3,已知生产A1kg价值7千元,B1kg12千元。应该生产A和B产品各多少才能使总价值最大。表2-3产品资源AB现有资源数煤/t电力/kw劳动力/个9434510360200300利润(千元)712•解:设A、B两产品的计划产量为x1、x2则数学模型为:121212129436045200310300,0xxxxxxxx12max712Zxx(三)机床负荷问题的数学模型•例2.4设某车间需加工甲、乙两种零件。这两种零件可以在三种不同机床——铣床、六角车床、自动机床上进行加工。机床数及生产效率如表2-4。表2-4机床生产效率(件/日)机床台数甲产品乙产品铣床六角车床3315202030(三)机床负荷问题的数学模型此表说明,在一台铣床上一个工作日可以加工15件甲零件或20件乙零件,余类同。该车间共有3台铣床,3台六角车床,1台自动机床。问如何合理安排机床的加工任务,使得在产品配套比例条件下(设甲、乙零件1:1配套),使成套产品的数量达到最大。•解:设xij表示第i种机床用来生产第j种产品的台数,则数学模型为:(1)加工甲、乙产品机床台数平衡方程:111221222132331xxxxxx(2)甲、乙零件配套比例平衡方程:112131122232152030203055xxxxxx(3)变量非负:0(1,2,31,2)ijxij112131max152030Zxxx(4)目标函数求成套产品数量最大:(四)人员分配的数学模型例2.5有四件工作,分配给四人,每人能力不同,工作效率也不同如表2-5,规定每项工作由一个人担任和每个工人只分配一项工作。问应分配哪个人去完成哪项工作可使总效率达到最大。表2-5工作工人ABCD甲乙丙丁67872410733751234解:设xij表示i个工人分配担任第j项工作的情况,并xij取1和0两个值,xij=1,表示第i个工人分配担任第j项工作;xij=0,表示i个工人不担任第j项工作。数学模型:(1)每个工人只担任一项工作111213142122232431323334414243441111xxxxxxxxxxxxxxxx(2)每项工作必由一个工人担任112131411222324213233343142434441111xxxxxxxxxxxxxxxx(3)变量取值:1(1,2,,,1,2,,)0ijximjn(4)目标函数求总效率最大:111213142122232431323334424344max623743281073754Zxxxxxxxxxxxxxxx(五)合理配料问题的数学模型例2.6某人每日需服A、B两种维生素,A最少服9个单位,B最少服19个单位,现有六种营养物每克含A、B维生素的单位数和每克价格如表2-6。问此人每天要服用这六种营养物各多少克,才既能获得每日最少所需维生素又使花费最省。表2-6一克营养物所含维生素单位数营养素维生素(一)(二)(三)(四)(五)(六)维生素最少需量AB102212013132919单位价格(元/g)3.53652.72.2(五)合理配料问题的数学模型设:六种营养物分别各服用x1g,x2g,x3g,x4g,x5g,x6g。则数学模型:12345612345616022290332190xxxxxxxxxxxxxx123456min3.53652.72.2Zxxxxxx(六)合理下料问题的数学模型例2.7某车间有一批长度为180cm的钢管,为着制造零件的需要,要将其截成三种不同长度的管料:70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问题是应如何下料能使消耗的钢管数量最少?解:设在180cm长的钢管上能够下出U个70cm的零件,V个52cm的零件和W个35cm的零件,则U、V、W个零件必须符合:70U+52V+35W≤180(六)合理下料问题的数学模型•经过试算,可得8种下料方式,见表:下料方式零件尺寸(一)(二)(三)(四)(五)(六)(七)(八)零件需要量702111000010052021032101503510130235100余料56235246235设:x1、x2、x3、x4、x5、x6、x7、x8分别表示这八种下料方式钢管消耗的总根数,则数学模型:12342356713467818210023215032351000xxxxxxxxxxxxxxxxx12345678min56235246235Zxxxxxxxx2、解的基本定理⑴线性规划问题的可行域是凸集(凸多边形)。凸集凸集不是凸集顶点⑵最优解一定是在凸集的某一顶点实现(顶点数目不超过个)Cmn⑶先找一个基本可行解,与周围顶点比较,如不是最大,继续比较,直到找出最大为止。3、解的情况唯一解无穷解无界解无可行解有最优解无最优解建立直角坐标,图中阴影部分及边界上的点均为其解,是由约束条件来反映的。例一、)0,(21xx0,012416482122232max2121212121xxxxxxxxxxZ⑴⑵⑶⑷三、图解法012345678123456⑴⑵⑶⑷作图∴最优解:x1=4x2=2有唯一最优解,Z=14x2x1(42)00124164821222322121212121xxxxxxxxxxZ,max⑴⑵⑶⑷例二、例三、0,021223622max212212121xxxxxxxxxZ⑴⑵⑶无穷多最优解0,122min21212121xxxxxxxxZ⑴⑵无界解x1x1x2x20,632123min2121211xxxxxxxxZ⑴⑵x1x2无可行解0,150510032170251810max2121212121xxxxxxxxxxZ0,4322232max212212121xxxxxxxxxZ例四、练习1效产品机床率AB机床台数Ⅰ304040Ⅱ553040Ⅲ2337202、某车间用三种不同型号的机床Ⅰ、Ⅱ
本文标题:建模培训_线性规划
链接地址:https://www.777doc.com/doc-976415 .html