《线性规划问题的数学模型.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的数学模型.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、现在学习的是第1页，共53页 线性规划是运筹学的重要分支之一，也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自1947年线性规划被成功的运用于工业、交通、农业和军事等各个领域后，现在它已成为管理科学的重要基础和手段之一。随着计算机的普及，它的适应领域越来越广泛。线性规划研究的问题主要有两类：一是一项任务确定后，如何统筹安排，尽量作到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用他们，使得完成任务最多。其实这两类问题是一个问题的两个方面，就是所谓寻求整个问题的某个整体指标最优的问题。1.1.运输问题运输问题 2.2.生产的组织与计划问题生产的组织与计划
2、问题 3.3.合理下料问题合理下料问题 4.4.配料问题配料问题 5.5.布局问题布局问题 6.6.分配问题分配问题现在学习的是第2页，共53页1.运输问题运输问题 设有两个砖厂设有两个砖厂A A1 1、A A2 2。其产量分别为。其产量分别为2323万块与万块与2727万块。它们生产的供应万块。它们生产的供应B B1 1、B B2 2、B B 3 3三个工地。其需要量分别为三个工地。其需要量分别为1717万块、万块、1818万块和万块和1515万块。自各万块。自各产地到各工地的运价格如下表：问应如何调运，才使总运费最省。产地到各工地的运价格如下表：问应如何调运，才使总运费最省。运价 工地 砖
3、厂B1B2B 3A1506070A260110160现在学习的是第3页，共53页运量 工地砖厂B1B2B 3发量A1x11x12x1323A2x21x22x2327收量17181550现在学习的是第4页，共53页111213212223min50607060110160Sxxxxxx11121321222311211222133123271718150(1,2;1,2,3)ijxxxxxxxxxxxxxij现在学习的是第5页，共53页单位产品 产品耗用资源 资源A（公斤）B（公斤）现有资源铜（吨）94360电力（千瓦）45200劳动日（个）310300单位利润（万元/公斤）712 现在学习的是
4、第6页，共53页约束条件约束条件12max712Sxx121212943 6 0452 0 031 03 0 00(1,2)ixxxxxxxi 目标函数现在学习的是第7页，共53页 上述例子虽然有不同的实际内容，但是都可归结为一类优化问题。从数学上说它们具有以下共同特征：每一个问题都是求一组变量（称为决策变量）的值。这组变量的一组定值就代表一个具体方案。通常要求这组变量的取值是非负的。存在一定的限制条件，称为约束条件。这些约束条件都可以用一组线性等式或不等式来表示。都有一个期望达到的目标，并且这个目标可以表示为决策变量的线性函数（称为目标函数）。按所研究问题的不同，要求目标函数值最大化或最小化
5、。我们将具有上述三个特点的最优化问题归结为线性规划问题，其数学模型称为线性规划问题的数学模型，简称线性规划数学模型。现在学习的是第8页，共53页1122m ax(m in)(1)nnfc xc xc x或11112211211222221122(,)(,)(,)(2)01,2,(3)nnnnmmmnnmja xaxaxbaxaxaxbaxaxaxbxjn （1）式称为目标函数（2）式中等式或不等式称为约束条件（3）式是非负约束条件 x1,x2,xn称为决策变量，简称变量。现在学习的是第9页，共53页满足约束条件的一组变量的值0001122,nnxxxxxx称为线性规划问题的一个可行解，使目标函
6、数取得最大（或最小）的可行解称为最优解。此时，目标函数的值称为最优值。首先，确定决策变量。线性规划的数学模型建得是否容易，求解是否方便，取决于决策变量的选取是否得当。其次，确定约束条件，并根据实际问题添加非负条件。明确问题中所有的限制条件，并用决策变量的线性等式或不等式表示。一般可用表格形式列出所有的限制数据，然后根据所列出的数据写出相应的约束条件，以避免遗漏或重复所规定的限制要求。最后，确定目标函数，并确定是求极大还是求极小。用决策变量的线性函数来表示实际问题所要达到的目标，得到目标函数。现在学习的是第10页，共53页12121243280,0 xxxxxx 求x1、x2的值，使它们满足并且
7、使目标函数f=2 x1+5x2的值最大。图解法是利用直观的几何图形求解线性规划的一种几何解法 现在学习的是第11页，共53页x12x1+5x2=192x1+5x2=152x1+5x2=82x1+5x2=4x2=3x1=4x1+2x2=80 x2最优解为 x1=2，x2=3 相应的目标函数的最大值为 S=2*2+5*3=19现在学习的是第12页，共53页x1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0 x2=3x1=4x1+2x2=80 x2 若把例1的目标函数 ，最优解有，它们对应的目标函数值都是。（见下图）现在学习的是第13页，共53页例3 求x1、x2的值，使它们满足1
8、212121200,0 xxxxxx并且使目标函数s=2 x1+2x2的值最小。现在学习的是第14页，共53页x1x202X1+2x2=22X1+2x2=62X1+2x2=102X1+2x2=16 若把例3使的目标函数的值最大，从图可看出目标函数无上界，因此无最优解现在学习的是第15页，共53页 求x1、x2的值，使它们满足121212120,0 xxxxxx 并且使目标函数s=2 x1+2x2的值最小。现在学习的是第16页，共53页x1x2-x1+x2=1x1+x2=-2没有可行解，当然没有最优解。现在学习的是第17页，共53页 线性规划问题的数学模型有各种不同的形式。为了便于讨论，需要将线
9、性规划数学模型写成统一格式。线性规划问题的是：1122m a x(1)nnfc xcxcx约束条件（2）式又称等式约束（3）式称非负约束。标准型的特点为1111221121122222112212(2)0,0,0(3)nnnnmmm nnmnaxaxaxbaxaxaxbaxaxaxbxxx现在学习的是第18页，共53页 把一般的线性规划问题化成标准型的过程称为线性规划问题的标准化。线性规划问题的标准化的方法如下：令F=-f，则可将求f的最小值问题转化成求F的最大值问题，即 引入一个非负变量 xn+i，转化为线性等式，称 xn+i 为松弛变量。可在该约束条件两边同乘-1，化为1122m innn
10、fc xc xc x1122m a xnnFc xcxcx 11220iiinniaxaxaxbn+i若引 入 x有1122iiinnniiaxaxaxxb1122iiinnnkiaxaxaxxb1122iiinniaxaxaxb 可引进非负变量xj/,xj/，令xj=xj/-xj/代入约束条件和目标函数中。11220iiinniaxaxaxbn+k若引 入 x有现在学习的是第19页，共53页12312312312312m i n23723250,0fxxxxxxxxxxxxxx 引进松弛变量 x40,x5 0，将式中不等式约束条件变换成等式约束条件：1234123572xxxxxxxx将3x
11、1-x2-2x3=-5两边同乘-1，变为-3x1+x2+2x3=5变量x3无非负约束，引进非负变量x6,x7，令x3=x7-x6，代入约束条件 和目标函数。得12761276412765127623()()7()232()5fxxxxxxxxxxxxxxxxxx 最后，令F=-f，则可将求f的最小值问题转化成求F的最大值问题。标准型为：现在学习的是第20页，共53页12456712467125671267124567max200337232250,0,0,0,0,0Fxxxxxxxxxxxxxxxxxxxxxxxxxx 在线性规划的标准型中，如果有变量只在某一个约束方程 中系数为1，在其余约束
12、方程中系数全为0，则称为该约束 的一个；如果每个等式约束都有一个基变量，则称 等式约束条件是这些基变量的。如果线性规划的约束条件是典型方程组，不失一般性，设n个变量的线性规划问题的典型方程组为：现在学习的是第21页，共53页1 12211,111122,1122,11max01,2,nnmmnnmmnnmm mmmnnmjfc xc xc xxaxa xbxaxa xbxaxaxbxjn1单纯形法的基本思想单纯形法的基本思路是：根据标准型，从可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函数值逐步变优，当目标函数值达到最大值时，就得到问题的最优解。现在学习的是第22页，共53页
13、123123123123ma x23111133314733330,0,0fxxxxxxxxxxxx 先将问题化成标准型123451234123512345m ax23001111333114733330,0,0,0,0fxxxxxxxxxxxxxxxxxx（）现在学习的是第23页，共53页 显然 x4,x5为基变量，x1,x2,x3为非基变量，约束条件是典型方程组。由（1）可得：412351231111333(2)1473333xxxxxxxx将（2）代入目标函数可得 f=2x1+3 x2+x3+0 ,令非基变量 x1=x2=x3 =0则有 ,同时得到一个 由f=2x1+3 x2+x3+0可
14、知，非基变量的系数都是正数，若将其中任意一个非基变量变成基变量（取值从0变成正数）,都可以使目标函数值增加,所以只要在目标函数的表达式中还存在有正系数的非基变量，就表示目标函数值还有增加的可能，从而不是最优解，就需要将非基变量与基变量进行对换。我们把非基变量转换为基变量称为。一般选择正系数最大的那个非基变量（本例为x2）为进基变量，以求得目标函数值较快的增加。将x2换入到基变量中。同时，还要确定基变量中有一个要换出来成为非基变量。变量由基变量转化成非基变量称为。现在学习的是第24页，共53页4252113433xxxx随着x2的值增加，x4,x5的值会逐渐变小，由于 1433314252214
15、910,30min,433xxxxx 只有 才能保证x40,x50（即解的可行性）。当x2=9/4时，x5=0。即用 x2替换x5（x5出基），于是得到新的,。这种确定出基变量的方法称为。现在学习的是第25页，共53页21354113533173433119173113344443xxxxxxxxxx 整理得 213541359173444411114444xxxxxxxx 代入目标函数得 令非基变量x1=x3=x5 =0 得一新的代入代入目标函数 得相应的目标函数值 非基变量x1的系数是正数，说明目标函数值还可能增加，于是再用上述方法，确定进基、出基变量，又得到 用非基变量表示目标函数 现在
16、学习的是第26页，共53页由标准形等式约束条件得1(1,2,)niiijjjmxba xim代入目标函数进行简单的运算后，用非基变量表示目标函数为01122mmmmnnffxxx12,mmn12,mmnxxx称为非基变量的。将用检验数来判定线性规划问题是否有最优解，有最优解定理。现在学习的是第27页，共53页0(1,2,)jj mmn 则基本可行解就是(2)如果关于非基变量的所有检验数0(1,2,)jj mmn 且其中有一个非基变量xm+k的检验数为零 则该线性规划问题有(3)如果存在非基变量xm+k 的检验数0 且xm+k对应的均小于等于零 则该线性规划问题 现在学习的是第28页，共53页
17、用表格的形式来表示上面求解线性规划问题的单纯形法的计算过程可以 使计算和检验更加简便。具体方法如下：将目标函数式改写为-f+c1 x1+c2 x2 +cnxn=0 且作为等式约束方程组的第m+1个方程，得11,111122,1122,111 122(3 1)0mmnnmmnnmm mmmnnmnnxaxa xbxaxa xbxaxaxbfc xc xc x对方程组(3-1)的增广矩阵施行初等行变换，化为如下的阶梯形矩阵1111212211001000010(32)000110000mnmnmmmnmmnaabaabaabf现在学习的是第29页，共53页xBb100010 001-f000-f0
18、 x1x2xmxm+1xnx1x2xmb1b2bma1m+1a2m+1amm+1a1na2namn1mn下面通过具体的例子说明用单纯形法求解线性规划问题。现在学习的是第30页，共53页121212112m a x23221 22841 60,0fxxxxxxxxx 将该线性规划问题化为标准型1212312415max232212284160(1,2,3,4,5)jfxxxxxxxxxxxj现在学习的是第31页，共53页 xB b 2 2 1 0 0 12 1 2 0 1 0 8 4 0 0 0 16 -f 2 3 0 0 0 01x3x5x1x3x4x5初始基本可行解为 x1=x2=0,x3=
19、12,x4=8,x5=16。由于检验系数有正数，所以这个基本可行解不是最优解。从x1，x2中选一个检验数最大的。根据最小比值原则(mim12/2,8/2=4)确定。进基变量x2所在列与出基变量x4所在行的交叉处元素称为，加上方括号，再施行行初等变换，将主元所在列的主元化为，其余元素化为，得下表 现在学习的是第32页，共53页 xB b 1 0 1 -1 0 4 1/2 1 0 1/2 0 4 4 0 0 0 16 -f 1/2 0 0 -3/2 0 -12x3x2x2x3x5x41 xB b 0 0 1 -1-1/4 0 0 1 0 1/2-1/8 2 1 0 0 0 4 -f 0 0 0 -
20、3/2 -1/8 -14x1x2x3x4x5x3注：比值相等时可任选其一 x2x1 1/4最优解为目标函数值为 非基变量的检验数小于0现在学习的是第33页，共53页12123124m a x322340(1,2,3,4)jfxxxxxxxxxj x3 ,x4为基变量，x1 ,x2为非基变量。可得初始单纯形表 XBb1-1102-31014-f32000X3X4X2X4现在学习的是第34页，共53页XBb1-11020-23110-f05-30-6X1X2X3X4X1X4有检验数0均0 用单纯形法求解线性规划问题121212212m in3362830,0fxxxxxxxxx 现在学习的是第35
21、页，共53页1212312425m ax3362830(1,2,5)jFxxxxxxxxxxxjF=-f 进行换基迭代，计算过程如表现在学习的是第36页，共53页 xB b 1 1 0 0 6 1 2 0 1 0 8 0 1 0 0 3 -F 3 3 0 0 0 0 1 1 1 0 0 6 0 1 -1 1 0 2 0 1 0 0 3 -F 0 0 -3 0 0 -18 x4 x5 x2 x3 x4 x5 x1 x4 x5 1 1非基变量有检验数0，有检验数=0 其中一个最优解是 x1=6,x2=0 最优值为 f=-F=-18 现在学习的是第37页，共53页 求解线性规划问题的单纯形法必须满足
22、每个等式约束都有一个基变量即线性规划的约束条件是典型方程组，但经常出现的情况是线性规划的标准型的约束条件不是典型方程组，从而不具有初始单纯形表，这时，需要在线性规划问题中加入人工变量，把问题变为约束条件是典型方程组的情形，再按上述方法换基迭代求出最优解。人工变量是后加入原约束方程组中的虚拟变量，我们必须把它们从基变量中逐渐替换掉。若经过基的变换，基变量中不再含有人工变量，这表示原问题有解；若经过基的变换，最后在基中还有一个或几个人工变量，这意味着原问题无可行解。两阶段法是处理人工变量的方法之一，它是将加入人工变量后的线性规划问题分成两阶段求解。现在学习的是第38页，共53页1211112211
23、12112222221122max0,0(1,2,1,2,)mnnnnmmmnnmmjiZyyya xa xaxybaxaxaxybaxaxaxybxyjn im 对辅助线性规划问题应用单纯形法，求出辅助问题的最优解。若最优值Z=0，说明所有人工变量都变换为非基变量，表明原问题已得到一个基本可行解，则进入第二阶段；否则原问题无可行解，计算结束。现在学习的是第39页，共53页 用两阶段法求解下面的线性规划问题123412341234max532458102432100(1,2,3,4)jfxxxxxxxxxxxxxj第一阶段：第一、第二约束中暂缺基变量，分别引入人工变量 y1、y2,引入辅助线性
24、规划问题现在学习的是第40页，共53页12123411234212m ax58102432100(1,2,3,4),0,0jZyyxxxxyxxxxyxjyy Z用非基变量表示：121234123420 754107541020ZyyxxxxZxxxx 用单纯形表进行换基迭代如下 XB x1 x2 x3 y1 y2b5111010 y224320110 -Z754100020现在学习的是第41页，共53页 XB x1 x3 x4 y1 y2bx45/81/81/811/805/43/411/40-1/4115/2 -Z3/415/411/40-5/4015/2x43/501/3012/15-1
25、/301 x21/5111/150-1/154/152 -Z0000-1-10由于得到辅助问题的最优值Z=0，且人工变量均已出基，于是进入第二阶段。现在学习的是第42页，共53页4134132132131234113313133131115305301111112251551553241113153(2)24(1)51553012103xxxxxxxxxxxxfxxxxfxxxxxxfxx 代入中得用单纯形法进行计算，如下表所示 现在学习的是第43页，共53页XBx2x3x4 b3/501/3011x21/5111/1502-f20-1/30-10 x1101/185/35/3x20113/1
26、8-1/35/3-f00-4/9-10/3-40/3原线性规划问题为 为 现在学习的是第44页，共53页12312123123m i n951 432232340(1,2,3)jfxxxxxxxxxxxxj 化成标准型12312123123m a x951 432232340(1,2,3)jFxxxxxxxxxxxxj 现在学习的是第45页，共53页12312112321233max951432232340(1,2,3)0(1,2,3)jiZyyyxxyxxxyxxxyxjyi，Z用非基变量表示：1231231231362013620ZyyyxxxZxxx 用单纯形表进行换基迭代如下：现在学习
27、的是第46页，共53页xBx2x3y1y2y3 by195010014y213-20102-230014-Z1361000200-910-32y2011/3-301-1/32/3x11-2/31001/34/3-Z044/3-1200-13/38/3x201-9/111/110-3/112/11y2000-1/312/30 x1105/112/3305/3316/11-Z000-4/30-1/30现在学习的是第47页，共53页2131233yyy这表明原问题的约束方程组中的第二个方程可由第一个方程减去二倍的第三个方程得出。因此，第二个方程是多余的，故最后一个迭代的基变量y2所在的第二行可以划去
28、，再划去人工变量列，且将-Z行换成-F行，先将F用非基变量表示，由上表最后一次换基迭代知 13132323123333335665111111 119229111111 116529()()11 1111 1118 15151811 111111xxxxxxxxFxxxxxxxFx得原问题的初始单纯形表 现在学习的是第48页，共53页XBx1x2x3bx201-9/112/11x1105/1116/11-F00-5/1118/11于是得原问题 现在学习的是第49页，共53页13123413123m a x4311222233132236400(1,2,34)jfxxxxxxxxxxxxj，引进
29、辅助线性规划问题 123123411321243max11222233132236400(1,2,3 4),0(1,2,3)jiZyyyxxxxyxxyxxxyxjyi，用非基变量表示Z：用单纯形表进行换基迭代如表 现在学习的是第50页，共53页XBx2x3x4y1y2y3by11/211/2-2/31002y23/20-1/200103-6040010-Z5-5010/3000501/2-4/310-1/62y203-1/2-201-1/231-204/3001/30-Z050-10/300-5/35011/4-2/31/20-1/121y2000-3/21-1/40 x1101/20101/62-Z00-5/40-5/20-5/40现在学习的是第51页，共53页XBx1x2x3x4y1y2y3bx2010-2/31/5-/5-1/151x300106/5-4/5-/50 x110002/52/5-/152-Z0000-1-1-10在表中划去人工变量列，并将-Z行换成-f 行(见后），得原问题的初始单纯形表 XBx1x2x3x4bx2010-2/31x300100 x110002-f00008现在学习的是第52页，共53页感谢大家观看现在学习的是第53页，共53页