1、第五章第五章 线线 性性 规规 划划 约束函数和目标函数都为线性函数的优化约束函数和目标函数都为线性函数的优化问题称作线性规划问题。问题称作线性规划问题。它的解法在理论上和方法上都很成熟，实它的解法在理论上和方法上都很成熟，实际应用也很广泛。际应用也很广泛。虽然大多数工程设计是非线性的，但是也虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。有采用线性逼近方法求解非线性问题的。此外，线性规划方法还被用作解决非线性此外，线性规划方法还被用作解决非线性问题的子问题的工具，如在可行方向法中可行问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。方向的寻求就是
2、采用线性规划方法。第一节第一节 线性规划的标准形式与基本性质线性规划的标准形式与基本性质一、线性规划实例一、线性规划实例例例5-1解解：设每天生产甲、乙两种产品分别为：设每天生产甲、乙两种产品分别为x1、x2件，则数学模型如下：件，则数学模型如下：0020054)(30010336049max12060),(212121212121xxxxxxxxxxxxf电电力力约约束束工工时时约约束束材材料料约约束束将其化成标准形式为：将其化成标准形式为：Txx21x求求)5,4,3,2,1(02005430010336049521421321ixxxxxxxxxxi使使2112060)(minxxfx且
3、满足：且满足：二、线性规划的标准形式二、线性规划的标准形式 线性规划数学模型的一般形式为：线性规划数学模型的一般形式为：Tnxxx21x求求),i(xbxaxaxabxaxaxabxaxaxaimnmnmmnnnn521022112222212111212111使使min)(2211nnxcxcxcfx且满足：且满足：Tnixxxx21x求求)n,i(x)m,j(bxaijniiji210211使目标函数使目标函数min)(1niiixcf x要求满足约束条件：要求满足约束条件：也可以写成如下的简化形式：也可以写成如下的简化形式：0,0222121xxxx例如例如 约束条件为约束条件为引入松弛
4、变量引入松弛变量 将第一个不等式约束条件将第一个不等式约束条件化成等式约束形式化成等式约束形式 约束条件包括两部分：一是等式约束条件，约束条件包括两部分：一是等式约束条件，二是变量的非负要求。它是标准形式中出现的二是变量的非负要求。它是标准形式中出现的唯一不等式形式。唯一不等式形式。如果线性规划问题除变量的非负要求外，如果线性规划问题除变量的非负要求外，还有其它不等式约束条件，可通过引入松弛变还有其它不等式约束条件，可通过引入松弛变量将不等式约束化成上述等式约束形式。量将不等式约束化成上述等式约束形式。03x0,0,022321321xxxxxx这样，可行域就这样，可行域就由二维空间变成由二维
5、空间变成三维空间。三维空间。如果在原来的问题中有一些变量并不要求非负如果在原来的问题中有一些变量并不要求非负的，那么可以把它们写成两个非负变量的差。的，那么可以把它们写成两个非负变量的差。0,0 kkkkkxxxxx 当松弛变量以及新的非负变量引入后，再当松弛变量以及新的非负变量引入后，再将所有的变量重新编序，原来的线性规划问题将所有的变量重新编序，原来的线性规划问题就变成了标准形式。就变成了标准形式。注意：注意：引入的松弛变量在目标函数中并不出现，引入的松弛变量在目标函数中并不出现，而新的非负变量一般将出现在目标函数中。而新的非负变量一般将出现在目标函数中。线性规划问题的标准形式又可写成如下
6、的矩阵线性规划问题的标准形式又可写成如下的矩阵形式：形式：iTjnmijTc,b,a.t.smin)(fcbA0 xbAxxcxx其中使求 在所有具有实际意义的线性规化问题中，在所有具有实际意义的线性规化问题中，总有总有mn，Ax=b变成矛盾方程组，不存变成矛盾方程组，不存在严格满足方程组的解。在严格满足方程组的解。只有当只有当mn，Ax=b才是不定的有无穷多才是不定的有无穷多个解个解。三、线性规划的基本性质三、线性规划的基本性质 用图解法和代数解法对上述实例进行分用图解法和代数解法对上述实例进行分析，说明线性规划的基本概念和基本性质。析，说明线性规划的基本概念和基本性质。令令 x3=x4=x
7、5=0)5,4,3,2,1(02005430010336049521421321ixxxxxxxxxxi 用代数法求解约束方程时，由于变量数用代数法求解约束方程时，由于变量数n=5，方程数，方程数m=3，mm）进行一次）进行一次附加的转轴运算，这时得到的新方程组仍然是附加的转轴运算，这时得到的新方程组仍然是正则形式，不过正则形式，不过xt进入基中，而进入基中，而xs就不再属于就不再属于基中了。基中了。sta 因此对正则形式的方程组进行一次附加的因此对正则形式的方程组进行一次附加的转轴计算，可以从一个基本解转换到另一个基转轴计算，可以从一个基本解转换到另一个基本解，从而把基本变量与非基本变量进行
8、交换。本解，从而把基本变量与非基本变量进行交换。一般地说，这种情况下所有基本变量的数一般地说，这种情况下所有基本变量的数值都要改变。值都要改变。其中有一个非零的基本变量变成零值的非其中有一个非零的基本变量变成零值的非基本变量，只有一个零值的非基本变量进入基基本变量，只有一个零值的非基本变量进入基中变成非零的基本变量。中变成非零的基本变量。例例5-28520213455432154321xxxxxxxxxx试进行基本解的转换计算试进行基本解的转换计算顺次用顺次用a11和和a22为转轴元素时，得：为转轴元素时，得：解：解：204312012327054325431xxxxxxxx 从而得一组基本解
9、：从而得一组基本解：不是可行解。不是可行解。0201254321xxxxx再用再用a25=-4为转轴元素：为转轴元素：得：得：5433410304124354324321xxxxxxxx05343251xxxxx是一组可行的基本解。是一组可行的基本解。与前一组基本解相比，与前一组基本解相比，x2由基本变量变成由基本变量变成非基本变量非基本变量出基。出基。x5由非基本变量变为基本变量由非基本变量变为基本变量进基。进基。从而实现从一个基本解到另一个基本解的从而实现从一个基本解到另一个基本解的变换。变换。二、从一个基本可行解转到另一个基本可行解二、从一个基本可行解转到另一个基本可行解 要使变换后所得
10、的基本解变成可行解，还要使变换后所得的基本解变成可行解，还需要研究这样的方法，即如何使某个选定的变需要研究这样的方法，即如何使某个选定的变量量xk(k=m+1,n)进入基本变量，来替换另一个进入基本变量，来替换另一个现在还在基本变量中的现在还在基本变量中的xs(s=1,2,m)，形成新的，形成新的基本可行解。基本可行解。当已经得到了一组可行解，即现在所有的当已经得到了一组可行解，即现在所有的bl都是非负的时，若要求把都是非负的时，若要求把xk选进基本变量的选进基本变量的下一组基本解是可行解的话，则在第下一组基本解是可行解的话，则在第k列所有列所有系数中不能取任何负值的系数中不能取任何负值的al
11、k作为轴元素，否则作为轴元素，否则将使将使bl为负，结果对应的为负，结果对应的xk必将是负的，它就必将是负的，它就不是可行解的一个元素。不是可行解的一个元素。第一个要求，若第一个要求，若 都是非负的，则必须都是非负的，则必须 才可选作轴元素进行转轴运算，以便用才可选作轴元素进行转轴运算，以便用 去代去代替替 。lb0lkakxsx这个过程是：反复进行转轴运算，直到这个过程是：反复进行转轴运算，直到 从从某个正值变成某个正值变成0，而，而 则从则从0变成某个正值变成某个正值 为止。为止。sxkxmlnkmmlmnmkmmlnlklmnkmnkmbbbbxxxxxxxaaaaaaaaaaaa211
12、211122121111010001000010000111122222k1kk1kkkklllkkllkmmmkkmmkxxba xbaxba xbaxba xbaxbaxba所以所以0minlkllabklkllxabmin0minlklkllkabxa 因此要满足两个条件：因此要满足两个条件：例如例如1234234531203441303544xxxxxxxx规则规则11100100kskkskskmkaaaaa p第第s行元素为行元素为1经转轴运算得：经转轴运算得：12341245131302882373102882xxxxxxxx先后得到四组基本解：先后得到四组基本解：1234515
13、23435124132451220013022103215033xxxxxxxxxxxxxxxxxxxx 12312352100,1,2,3ixxxxxxxi三、初始基本可行解的求法三、初始基本可行解的求法 单用添加松弛变量的方法把不等式约束转单用添加松弛变量的方法把不等式约束转换成等式约束时，这些松弛变量就可以作为初换成等式约束时，这些松弛变量就可以作为初始基本可行解中的一部分基本变量。始基本可行解中的一部分基本变量。引入松弛变量后引入松弛变量后123412350520100,1,2,3,4,5ixxxxxxxxxi 但是，如果不等式约束条件右端项是负的，但是，如果不等式约束条件右端项是负的
14、，它所对应的松弛变量就不能作为基本可行解的它所对应的松弛变量就不能作为基本可行解的基本变量。基本变量。所以上述方法并不是总能成功。所以上述方法并不是总能成功。这时需引入人工变量，经过变换再将它从这时需引入人工变量，经过变换再将它从基本变量中替换出去。基本变量中替换出去。前面阐述了应用前面阐述了应用规则所规定的条件，可规则所规定的条件，可以做到从一组基本可行解转换到另一组可行解。以做到从一组基本可行解转换到另一组可行解。但那一组可行解是最优呢？但那一组可行解是最优呢？当然可以用各组可行解分别代入目标函数当然可以用各组可行解分别代入目标函数f(x)，取使其最小或最大者为最优解。，取使其最小或最大者
15、为最优解。但是，能否找出确定最优解的规则呢？但是，能否找出确定最优解的规则呢？对于可行解（若有前对于可行解（若有前m个变量组成可行解个变量组成可行解的基本变量时），目标函数可以写成：的基本变量时），目标函数可以写成：1 122100mllmmlfcbcbc bc bx如果还有另一组可行解，它的基本变量中包含如果还有另一组可行解，它的基本变量中包含有有 ，即：，即：kxkm11122200000000kklllkkbaxbaxxbaxx其中其中ssskxbasm它所对应的目标函数它所对应的目标函数值是：值是：11122211000kkmmmkmmkllllkkllfc bacbacbaccbc
16、acx令令1mkllklfc aa则则 kkffcffrxxax相对价值系数相对价值系数kkrcfa 显然，对极小化问题，应要求显然，对极小化问题，应要求 ，即即 应是负值。应是负值。由于由于 是正值，则就应要求是正值，则就应要求 为负值。为负值。ffxxrkkrcfa 只要它仍是负值，则目标函数只要它仍是负值，则目标函数 还没达还没达到极小值，还有下降趋势，就还可以进行转轴到极小值，还有下降趋势，就还可以进行转轴运算，选取另一组可行解。运算，选取另一组可行解。fx 因此，一旦因此，一旦 为正，即可停为正，即可停止转轴运算。对应的可行解就是最优解。止转轴运算。对应的可行解就是最优解。kkrcf
17、a也可能有几组也可能有几组 都为负值。都为负值。kkrcfa对于极小化问题应取：对于极小化问题应取：minjjkkjcfcfaa其中其中1mjlljlfc aa最速变化规则最速变化规则 上面的方法是利用约束条件方程组解出可上面的方法是利用约束条件方程组解出可行解，再利用目标函数检验最优解的方法。行解，再利用目标函数检验最优解的方法。计算时，也可以直接把目标函数和约束条计算时，也可以直接把目标函数和约束条件同时列为转轴运算方程组。采用边计算可行件同时列为转轴运算方程组。采用边计算可行解，便校验目标函数值的变化情况的办法来求解，便校验目标函数值的变化情况的办法来求最优解。最优解。这时，对于极小化问
18、题，只要这时，对于极小化问题，只要 1 122nnfc xc xc xx中的系数有一个或几个是负值，就说明函数值中的系数有一个或几个是负值，就说明函数值还可以减小，就应把对应的还可以减小，就应把对应的 的变的变量量 选进可行解的基本变量中去。选进可行解的基本变量中去。minkjjcckx一个一个 规则规则min0lkllklkbxaa 一个最速变化规则一个最速变化规则minjjkkjcfcfaa构成单纯形方法的基础。构成单纯形方法的基础。当目标函数表示成只是非基变量的函数当目标函数表示成只是非基变量的函数时，对应于基本变量的系数时，对应于基本变量的系数 则则 ，最速变化规则又可表，最速变化规则
19、又可表示为：示为：01,2,lclm10mjlljlfc aaminjkjcc 极大值时取极大值时取max综上，单纯形法的运算过程主要是围绕两个综上，单纯形法的运算过程主要是围绕两个规则进行：规则进行：一个一个 规则：规则：用来说明如何进行基本变量中的变量交用来说明如何进行基本变量中的变量交换，是一个可行解通过转轴运算换成另一个换，是一个可行解通过转轴运算换成另一个新的基本可行解。新的基本可行解。一个最速变化规则一个最速变化规则 用来评价哪一组可行解是最优的。用来评价哪一组可行解是最优的。这两个规则的运算可以用矩阵的运算来表这两个规则的运算可以用矩阵的运算来表述，而且转轴的运算可以直接调用标准
20、程序。述，而且转轴的运算可以直接调用标准程序。有关矩阵运算的表述：有关矩阵运算的表述：求求x使使 fmin xcx或或 minf xcx.st 0Axbx1212Tnnxxx xxxx=12nc ccc=1112112122221212nnnmmmmnaaaaaaaaa AAA=p ppA12jjjjnaaaA=1212iTijiimimiaaa aaap=1212Tmmbbb bbbb=1,2,;1,2,injm nm 线性规划的基本性质说明，当约束方程组线性规划的基本性质说明，当约束方程组中等式的数目小于变量的个数时，将有无穷组中等式的数目小于变量的个数时，将有无穷组解，但只有满足约束条件
21、解，但只有满足约束条件x大于等于大于等于0的有限个的有限个解是基本可行解。解是基本可行解。在基本可行解中，变量可区分为基本变量在基本可行解中，变量可区分为基本变量和非基本变量两部分，即和非基本变量两部分，即TEFx=xx记矩阵记矩阵A中和基本变量中和基本变量xE相对应的那部分（假相对应的那部分（假定定 A中的前中的前m个列向量为个列向量为 ，且它们是，且它们是线性无关的）分块矩阵线性无关的）分块矩阵E是是m行行 m列的方阵，和列的方阵，和非基变量对应的分块矩阵非基变量对应的分块矩阵F是是m行（行（n-m）列矩）列矩阵。阵。E称为含有称为含有m个基向量的基方阵，它可写个基向量的基方阵，它可写成：
22、成：12mp pp12mE=p pp这样，约束方程这样，约束方程 可写成可写成AxbEEFFxAxE FExFxbx两端同乘两端同乘1E11EFx+E FxE b对于基本可行解，非基本变量对于基本可行解，非基本变量 ，则得，则得0Fx1ExE b记记 121EFmmnc cc cccc c 1111EEFEEFFFEFFFEEFFfxxcx=c cc xc xxcE b-E Fxc xc E b-c E F-cx得得或或 11EFEfFxc E F-cxc E b这是用这是用 表示目标函数的式子。表示目标函数的式子。Fx 对于用对于用 的基本可行解，则此时的基本可行解，则此时 的的 可以调用标
23、准程序进行转轴计可以调用标准程序进行转轴计算，达到从一组基本解转换到另一组基本解。算，达到从一组基本解转换到另一组基本解。0Fx 1Efxc E b 所谓从一组基本解转换到另一组基本解的所谓从一组基本解转换到另一组基本解的转轴运算，实际上就是把转轴运算，实际上就是把 中的中的列向量列向量 用另一个列向量用另一个列向量 代替，即把原代替，即把原基方阵基方阵 转换成新的基方阵转换成新的基方阵 sp12mE=p ppkp12smE=p ppp12kmE=p ppp 这种转轴的结果，是把原基本解的基本这种转轴的结果，是把原基本解的基本变量变量 中的中的 用用 来替代，使来替代，使新一组基本变量的基本变
24、量变成新一组基本变量的基本变量变成12,smxxxxsxkx12,kmxxxx 利用利用 规则就可以确定规则就可以确定 的选取。从而的选取。从而做到从一组基本解转换到另一组基本解。做到从一组基本解转换到另一组基本解。kx 自约束条件自约束条件 可以写出，符合可以写出，符合 的解是基本可行解。的解是基本可行解。10,0EFbxEx0 x 对于基方阵对于基方阵 来说，这时基来说，这时基本可行解的基本变量是本可行解的基本变量是 ；非基本；非基本变量是变量是 。12mE=p pp12,mxxx1,mnxx 再利用最速变化规则，就可以确定使目标再利用最速变化规则，就可以确定使目标函数达极值的最优解。函数
25、达极值的最优解。第四节第四节 单单 纯纯 形形 法法 应应 用用例例5-35-3目标函数目标函数()123f2x3x4xx预算约束预算约束12320 x25x30 x9000总数约束总数约束123xxx350每类单元每类单元数约束数约束.().().()152535x0 2 350 xx0 6 350 xx0 4 350 x求求 、的值，使目标函数的值，使目标函数 为极大，且满足约束条件为极大，且满足约束条件 1x2x3x()123f2x 3x 4xx12320 x25x30 x9000123xxx350.().().()152535x0 2 350 xx0 6 350 xx0 4 350 x
26、引入松弛变量引入松弛变量 、4x5x6x7x8x()123f2x3x4xxmaxmax123420 x25x30 xx90001235xxxx350.156257358x0 2xx70 x0 6xx210 x0 4xx140s.t.s.t.引入人工非负变量引入人工非负变量.12341235915625735820 x25x30 xx9000 xxxxx350 x02xx70 x06xx210 x04xx140max()1239f2x3x4x1000 xxs.t.s.t.12341235915625735820 x25x30 xx9000 xxxxx350 x02xx70 x06xx210 x0
27、4xx140单纯形表的矩阵形式可以通过矩阵运算给出：单纯形表的矩阵形式可以通过矩阵运算给出：对对 的两边左乘的两边左乘 ，有，有Axb1E11EAxE b两边再左乘两边再左乘 ，得，得Ec11EEc EAxc E b左右两边分别加到左右两边分别加到 的左右两边，得的左右两边，得()fxcx()11EEfxc EAxcxc E b或或()()11EEfxc EAc xc E b11EAxE b()()11EEfxc EAc xc E b写成矩阵形式写成矩阵形式-()1111EEfx0E AE bxIc E A-cc E b矩阵矩阵-()1111EEE bE AT Ec E bc E A-c就是对
28、应于基矩阵的单纯形表。就是对应于基矩阵的单纯形表。-()1111EEE bE AT Ec E bc E A-cbf(aj)和和b交交点处的值点处的值x1,xn和和p1,pn的子矩阵的子矩阵价值系数价值系数rj第五节第五节 修修 正正 单单 纯纯 形形 法法()()049678149673EpppppEppppp01100001000300100001001001000010000010000100000100001EE1110003001001001000001000001E111000309000900042004800010013503501402100010070707000010210
29、21021000001140140140Eb()()149673229673EpppppEppppp121000302500000100111000001000010000010100100000100001EE21E()()229673329173EpppppEppppp13E,=111112nEEE b EA Epppcc EA1E()()12sm12kmEppppEpppp设设()1k2k112kmskmk1 0a001a00 0a00 0a1E Epppp1k1k2k2k11kskskmkmkaaaaaaaaEpE()1k2k112kmskmk1 0a001a00 0a00 0a1E
30、Epppp1ksk2 ksk11skmkska100aa010a1000aa001aEE111EEEE1ksk2 ksk11skmkska100aa010a1000aa001aE例例5-45-4max.(,)12123124125iZ5x4 xx3xx902xxx80s txxx45x0 i1 25解：解：12345131002101011001ppp ppATT54000908045cb0345100010001Eppp10100010001E0031E4051E0 x1009090 x0108080 x0014545100000010000001xE bc E00111E01122E021
31、rc50002513rc4000141 c Epc Ep101100110102200111 Epmins9080458040121203451315EpppEppp1E050c1110111102100E21012E E101E1E11029050100804024551012xEx11E11102150500000221012c E1122E12353rc4001221 c Ep1144E14055rc0001220 c Epmax,2423r rr2112151022311001221110122 Epmin,k50405510 s35111222213152312EpppEppp2E0
32、54c1112105011002E E-11112121110210512510110001120020121012EE EE211E2E10550250114035002510 xEx21E2125054011013012c E2144E240rc00131100 c Ep255E250rc00130301 c E p,()2212345EEx35 x10 x25 xx025zf0543521510 xc x第六节第六节 工程设计应用工程设计应用一、等截面长条类材料下料方案的最优确定在工程中，最大限度的节约材料，提高材料利用率是实际生产中追求的目标。在等截面长条类材料如各种型材的下料过程中，
33、往往都是从一种规格的材料中下出各种不同长度尺寸的坯料。一般工程中往往采用凭直觉判断下料的方案，几乎不可能实现最节省原材料的最优方案。评价下料方案的优劣，可通过比较原材料利用率大小来确定。例 今有一批4m长的圆钢，需要下长0.7m的坯料4000件，长0.52m的坯料3600件，问如何下料可以使材料的利用率最高（忽略切口损失长度）？解：解：如果采用单一的下料方案，所需圆钢数目12nnn0.7m长4000件坯料所需型材的条数 0.52m长3600件坯料所需型材的条数=4000/INT(4/0.7)+3600/INT(4/0.52）12nnn=4000/5+3600/7=1315材料利用率=(0.74
34、000+0.523600)/(13154)=88.8213%采用优化设计，建立数学模型：目标函数 minnii 1fxx约束条件 40003600n1i1i 1n2i1i 1a xa x故该问题的优化设计数学模型为 min123456fxxxxxxx约束条件 543240002356736001234523456xxxxxxxxxx二、分配运输任务的最有确定 例 有一车队有八辆车，这八辆车存放在不同的地点，队长要派出五辆车去不同的地点拉货，各辆车从存放处去拉货至返回原处所需费用见下表，问选派哪五辆车分别到何处去拉货，可使运输所需的总费用最少？解：解：优化设计数学模型为目标函数约束条件 11,2,811,2,8018ijj 18iji 1ijijxixjxx或
