1、第六章第六章 线性规划线性规划一一.线性规划的基本概念线性规划的基本概念二二.求解线性规划的单纯形法求解线性规划的单纯形法三三.初始基本可行解初始基本可行解2022-11-141 某厂生产甲、乙两种产品，已知：两种产某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天品分别由两条生产线生产。第一条生产甲，每天最多生产最多生产9 9件，第二条生产乙，每天最多生产件，第二条生产乙，每天最多生产7 7件；件；该厂仅有工人该厂仅有工人2424名，生产甲每件用名，生产甲每件用2 2工日，生工日，生产乙每件用产乙每件用3 3工日；产品甲、乙的单件利润分工日；产品甲、乙的单件利润分
2、别为别为4040元和元和8080元。问工厂如何组织生产才能获得元。问工厂如何组织生产才能获得最大利润？最大利润？一）应用实例一）应用实例6-1 6-1 线性规划的基本概念线性规划的基本概念2022-11-142日利润最大日利润最大生产能力限制生产能力限制劳动力限制劳动力限制变量非负变量非负.,21xx解解:设甲、乙两种产品的日产件数分别为设甲、乙两种产品的日产件数分别为0,2432798040)(max212121221xxxxxxRDXxxXFs.t.2022-11-143二二)线性规划的一般形式线性规划的一般形式0,.,.)(min21221122222121112121112211nmn
3、mnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcXFs.t.s.t.特点特点:1)1)为极小化问题为极小化问题;2);2)约束取等号约束取等号;3)3)限定系数非负限定系数非负;4);4)变量非负变量非负.式中，式中，价值系数；价值系数；结构系数结构系数 限定系数限定系数jcijaib2022-11-144 将数学模型化为标准型的方法将数学模型化为标准型的方法1 1）将极大化问题化为极小化问题）将极大化问题化为极小化问题iibXg)()1(若iibXg)()2(若kx 松弛变量松弛变量/jjjxxx（开关变量）（开关变量）（两边乘（两边乘-1-1）4 4）将负的
4、限定系数化为正值）将负的限定系数化为正值3 3）将任意变量化为非负变量）将任意变量化为非负变量2 2）将不等式约束变为等式约束：）将不等式约束变为等式约束：目标函数变号；目标函数变号；ikibxXg)(ikibxXg)(2022-11-1450,.,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.化为标准型化为标准型:2022-11-146三）线性规划的基本概念三）线性规划的基本概念0,2432798040)(max212121221xxxxxxRDXxxXFs.t.1.1.线性规划的图解线性规划的图解x2x10F=0F*=620(1.5,7)
5、2022-11-1472.2.线性规划的基本概念线性规划的基本概念1 1）可行解）可行解满足约束条件及非负条件的解。满足约束条件及非负条件的解。（D D内及其边界上的解）内及其边界上的解）2 2）基本解）基本解使使n-mn-m个变量等于个变量等于0 0，解约束方程，解约束方程组组(共有共有m m个约束方程个约束方程)所得的解。所得的解。基本解对应于约束边界的交点基本解对应于约束边界的交点.3 3）基本可行解）基本可行解可行域中的基本解（即可行域中的基本解（即D D的顶点）。的顶点）。4 4）基本变量与非基本变量）基本变量与非基本变量 预先取为零值的预先取为零值的n-mn-m个变量为非个变量为非
6、基本变量，其余基本变量，其余m m个为基本变量。个为基本变量。03xx2x10F=0F*=-620(1.5,7)04x05x01x02x0,.,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.2022-11-148四）线性规划的基本性质四）线性规划的基本性质 1 1）可行域）可行域D D为凸集，每个基本可行解对应于为凸集，每个基本可行解对应于D D上的上的一个顶点；一个顶点；2 2）只要可行域存在且封闭，则起码有一个基本可）只要可行域存在且封闭，则起码有一个基本可行解为最优点；行解为最优点；*）若最优点所在的边界线与等值线平行，则该）若最优点所
7、在的边界线与等值线平行，则该边界线上的点均为最优点；边界线上的点均为最优点；）若可行域不封闭，则可能有无界解。）若可行域不封闭，则可能有无界解。3)3)最优点可在最优点可在D D的顶点中寻找。的顶点中寻找。2022-11-1496-2 6-2 求解线性规划的单纯形法求解线性规划的单纯形法一一.基本思路基本思路 先取先取D D的一个顶点作为初始点的一个顶点作为初始点,由此出发朝由此出发朝可使目标函数降低最快的方向依次经过一系可使目标函数降低最快的方向依次经过一系列的基本可行解列的基本可行解,直至达到最优解直至达到最优解.*1)1)需获得一个初始基本可行解需获得一个初始基本可行解;2)2)每次只更
8、换一个非基本变量每次只更换一个非基本变量;3)3)保证下降性和可行性保证下降性和可行性.2022-11-1410二二.计算实例计算实例6,.,2,1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.s.t.1.1.初始基本可行解初始基本可行解取取x x5 5,x,x6 6 为基本变量为基本变量,则有则有:)0(X0 0 0 0 4 5T375543)0(F2022-11-14112.2.第一次变换顶点第一次变换顶点(1)(1)选取进基变量选取进基变量原则原则:考虑下降性考虑下降性,且下降得最快且下降得最快判别数判别数:假定假
9、定x x2 2进基进基,则有则有5246252xxxx0206252xxxx取取12x,15x26x相应的目标函数变化量相应的目标函数变化量:1110325326522xxx12a22a即即)(22612522acacc6,.,2,1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj2022-11-1412写成一般形式写成一般形式:miijBijjjjacczc11515432203523111251324151344321最小最小,x,x3 3 应为进基变量应为进基变量3推论推论:若线性规划的一个基本可行解的所有进基判别数均若线性
10、规划的一个基本可行解的所有进基判别数均为非负为非负,则该解为最优解则该解为最优解.6,.,2,1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj2022-11-1413(2)(2)确定离基变量确定离基变量原则原则:考虑可行性考虑可行性(该变量离基后该变量离基后,能使余下的基本变量为非负能使余下的基本变量为非负)判别数判别数:)35(335)2(224336335xxxxxx由于由于)若取若取 (离基离基),),则有则有 05x0263xx0323553xx)/()/(323223313113xabaxabaijiiab,.,2,1
11、mi 进基变量下标j应取应取 为正且其值为最小者对应的基本变量离基为正且其值为最小者对应的基本变量离基.i6,.,2,1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj(可行可行)(不可行不可行)06x)若取若取 (离基离基),),则有则有 2022-11-1414)推论推论:若线性规划的的所有离基若线性规划的的所有离基判别数均为负数时判别数均为负数时,则问题有无界解则问题有无界解.最小最小,x,x6 6 应为离基变量应为离基变量2)1(X0 0 5/3 0 2/3 0T31132335)1(F*)因为因为 ,故故 也必须大于也必
12、须大于0,0,否则不满足否则不满足可行性要求可行性要求;0,21bb2313,aa6,.,2,1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj)35(335)2(224336335xxxxxx2022-11-1415进基进基4x3.3.第二次变换顶点第二次变换顶点去掉了去掉了6x5,.,2,1,.05324423224)(min43215432154321jxxxxxxxxxxxxxxxXFj(1)(2)1)1)确定进基变量确定进基变量03183103311231231332123223133114421:3)2(3)(4)35
13、3132314321xxxx:)1()2()3(3231031315421xxxxmiijBijjacc12022-11-14162)2)确定离基变量确定离基变量2.0310/32531/3521 离基离基5x(1)(1)(2)(2)4321224)(minxxxxXF323103131353132314214321xxxxxxx)2(X0 0 8/5 1/5 0 0T251258)2(F:310/)2(3)(3)(4)(4)51101101421xxx:)1()31()3(58107103321xxx353132314321xxxx3231031315421xxxx2022-11-14174
14、.4.第三次变换顶点第三次变换顶点1)1)确定进基变量确定进基变量05.110121071205.310121031421 故故 为最优点为最优点,为最优值为最优值:)2(X)2(F)2(*XX0 0 8/5 1/5 0 0T251258)2(*FF51101101421xxx58107103321xxx4321224)(minxxxxXF2022-11-1418三三.用单纯形表求解线性规划用单纯形表求解线性规划例例.用初等变换法求解用初等变换法求解解解:增广矩阵增广矩阵:1125452121xxxx1112545,51030111123011112390135321xx2022-11-141
15、96,.,2,1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.离基判别数离基判别数进基判别数进基判别数 单纯形法实际上是解一系列的线性方程组单纯形法实际上是解一系列的线性方程组,也可用初等也可用初等变换方法列表求解变换方法列表求解.但需加入判别数的计算但需加入判别数的计算.421235基变量基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij例例1 12022-11-142042123基变量基变量x1x2x3x4x5x63x51/3
16、-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3jcBicibij421235基变量基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij2022-11-142142123基变量基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3jcBicibij4212基变量基变量x1x2x3x4x5x62x41/10-1/100
17、10.21x33/107/10101.6X2001.60.200F223.51.5jcBicibij已获得最优解已获得最优解2022-11-1422-2-300基变量基变量x1x2x3x40 x3-1110330 x41-4014-1X00034F00-2-3jcBicibij-2-30基变量基变量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5jcBicibij4,.,2,1,.044332)(min42132121jxxxxxxxxxXFjs.t.例例2 2问题有无界解问题有无界解2022-11-14236-3 6-3 初始基本可行初始基本可行
18、解解(1)(1)大大M M法法 引入一组人工变量引入一组人工变量,它们在目标函数中的它们在目标函数中的系数均是非常大的正数系数均是非常大的正数M;M;(2)(2)两相法两相法 引入一组人工变量引入一组人工变量,在人工变量未完全离在人工变量未完全离基前目标函数为各人工变量之和基前目标函数为各人工变量之和,当人工变当人工变量完全离基后恢复原目标函数。量完全离基后恢复原目标函数。当当A A内不包含单位矩阵时内不包含单位矩阵时,需引入由人工变量组需引入由人工变量组成的单位矩阵成的单位矩阵,以方便获得初始可行解以方便获得初始可行解.2022-11-1424一一.采用大采用大M M法获得初始基本可行解法获
19、得初始基本可行解543214)(minMxMxxxxXF33342253214321xxxxxxxx,0jx5,.,2,1js.t.采用大采用大M M法法：3214)(minxxxXF333422321321xxxxxx,0jx3,2,1js.t.原问题原问题：因因M M是比其他价值系数大得多的正数是比其他价值系数大得多的正数,且人工变量非负且人工变量非负,迭代迭代的结果会使人工变量趋于零的结果会使人工变量趋于零,而获得原问题的基本可行解而获得原问题的基本可行解.2022-11-1425543214)(minMxMxxxxXF33342253214321xxxxxxxx,0jx5,.,2,1j
20、s.t.411MM基变量基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij表一表一2022-11-1426411MM基变量基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij411M基变量基变量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3jcBicibij表一表一表二表二2022-11-1427411基变量基变量x1x2x3x4x51x30-3/411.5-24
21、x115/400.50.4X20.501.5F23.50-13/40jcBicibij表三表三初始基本初始基本可行解可行解411M基变量基变量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3jcBicibij表二表二2022-11-1428411基变量基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40jcBicibij411基变量基变量x1x2x3x4x51x3011.81x2100.4X300.41.8F32.2jcBicibij表三表三表四表四
22、初始基本初始基本可行解可行解最优解最优解2022-11-1429二二.采用两相法获得初始基本可行解采用两相法获得初始基本可行解大大M M法的法的M M是一个充分大的正数是一个充分大的正数,有时在计算机上不便处理有时在计算机上不便处理.3214)(minxxxXF333422321321xxxxxx,0jx3,2,1js.t.原问题：原问题：54minxxF33342253214321xxxxxxxx,0jx3,2,1js.t.相相1 1问题：问题：2022-11-143000011基变量基变量x1x2x3x4x51x421210421x53310131X0 00043F07-5-4-3jcBi
23、cibij0001基变量基变量x1x2x3x4x51x40-14/3121.50 x1111/3013X1 10020F121-4/3jcBicibij表一表一表二表二2022-11-1431000基变量基变量x1x2x3x4x50 x30-3/411.5-20 x115/400.50.4X2 0.501.5F2 00jcBicibij表三表三初始基本初始基本可行解可行解411基变量基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X00.501.5F03.5-13/4jcBicibij表四表四初始基本初始基本可行解可行解换换 相相2022-11-1432411基变量基变量x1x2x3x4x51x3011.81x2100.4X100.41.8F12.213/5jcBicibij表五表五最优解最优解2022-11-1433
