OR-01-线性规划及单纯型法_167408766

1、运筹学基础Introduction to Operations Research清华大学自动化系 王焕钢 Introduction to Operations Research线性规划2Tsinghua University2022-3-22 Introduction to Operations Research1. 一般模型和标准模型2. 低维问题的图解法3. 基本定理与基本算法4. 单纯形法5. 对偶性与对偶算法6. 灵敏度分析7. 补充内容32022-3-22Tsinghua University Introduction to Operations Research一般模型和标准模型4

2、2022-3-22Tsinghua University Introduction to Operations Research例：生产I、II两种产品，要占用A、B设备及调试时间，每件产品机时利润如表所示 15245产品I产品II每天可用时间1占用A机时占用B机时调试时间利润0612521如何生产使每天利润最大？52022-3-22Tsinghua University Introduction to Operations Research确定变量：12x x，生产两种产品的数量约束条件：1552xA机时约束242621 xxB机时约束0, 021xx非负约束521 xx调试时间约束每天利润

3、：212xx 62022-3-22Tsinghua University Introduction to Operations Research122121212max 2s.t. 515622450,0 xxxxxxxxx数学规划模型 72022-3-22Tsinghua University Introduction to Operations Research例：某种物品有 个产地，记为 ，各产地产量分别是 ；有 个销地mAAA,21m maaa,21n ，各销地销量分别是 ；12,nB BBnbbb,21假定从产地 向销地 运输单位物品运价jBiA是 ；问怎样调运这些物品能使总费用最小

4、？ijc82022-3-22Tsinghua University Introduction to Operations Research产地销地产量销量1AmA2AnB1B2B2ama1anb2b1b21c21x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx92022-3-22Tsinghua University Introduction to Operations Research数学规划模型 1111mins.t. ,1,10,1,1mnijijijnijijmijjiijc xxaimxbjnximjn 102022-3-22Tsin

5、ghua University Introduction to Operations Research数学规划模型的一般形式 tjxxxgmixxxhxxxfnjnin, 2 , 1, 0, 2 , 1, 0, s.t.,max2121210, 052426155 s.t.2max212121221xxxxxxxxx121211222121231212412151222,0,5,2, 515,6224,5,nmtf x xxxgx xxgx xxxgx xxxgx xxgx xx 112022-3-22Tsinghua University Introduction to Operations

6、 Research111mins.t. ,1,10,1,1njjjnijjijnijjijjjc xa xbipa xbpimxjqxqjn 线性规划模型的一般形式（min）122022-3-22Tsinghua University Introduction to Operations Research0, 052426155 s.t.2max212121221xxxxxxxxx231221152451ma5622450,1,2,x 2s.t., 5ixxxxxxxxxxix2155xxx2142624xxxA机时剩余量B机时剩余量调试时间剩余量235-15xx 13线性规划不等式约束转化为

7、等式约束2022-3-22Tsinghua University Introduction to Operations Research000s.t.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxc线性规划标准型目标函数等式约束非负约束142022-3-22Tsinghua University Introduction to Operations Research线性规划的标准模型 11min ( or max)s.t. ,10,1njjjnijjijjc xa xbimxjn min ( or

8、max)s.t. 0TC XAXbX1ncCc1mbbb1111nmmnaaAaa1nxXx152022-3-22Tsinghua University Introduction to Operations Research5 , 2 , 1, 052426155 s.t.2max5214213221ixxxxxxxxxxxi0s.t.maxXbAXXCT52415,100110102600150,00012bAC162022-3-22Tsinghua University Introduction to Operations Research对线性规划标准型的基本假定1. 系数矩阵A的行向量

9、 线性无关TmTTaaa,21如果该假定不满足，某个行向量，比如 ，可以表示为 的线性组合，即TmaTmTTaaa121,1 12211TTTTmmmaaaa则对任何满足前 个约束的 都成立1mX11111111mmTmmTTmbbXaXaXa当 时，第 个约束不起作用，故可以删除，若上述等式不满足原问题无可行解。1 111mmmbbbm172022-3-22Tsinghua University Introduction to Operations Research在基本假定的基础上可进一步假定2. 系数矩阵A的列数大于其行数，即nm如果 ，由于 是 个 维的向量，不可能线性无关，如果 ，

10、是行向量线性无关的方阵，因此有逆，满足 的只有一个向量 ，不需要优化Amn maa,1mnmn bAXbAX1182022-3-22Tsinghua University Introduction to Operations Research0s.t.maxXbAXXCT其中 ，并假定我们所考虑的线性规划标准型为：mnmnnRbRARXRC,mn 1. 2. 的行向量线性无关A192022-3-22Tsinghua University Introduction to Operations Research线性规划一般模型与标准模型的转换 1 1iinnia xa xb1 1110iinnni

11、na xa xxbx1 11iinnia xa xbx 111110,0iinniaxxa xbxx1maxnjjjc x1minnjjjc x202022-3-22Tsinghua University Introduction to Operations Research低维问题的图解法212022-3-22Tsinghua University Introduction to Operations Research生产一种家电产品，要占用A、B设备及调试时间，每件产品机时利润如表所示 15245产品每天可用时间1占用A机时占用B机时调试时间利润521如何生产使每天利润最大？222022-

12、3-22Tsinghua University Introduction to Operations Research数学规划模型： maxs.t. 51522450 xxxxx0 x x515x 224x 5x 黄实线是可行集，红点是最优解232022-3-22Tsinghua University Introduction to Operations Researchmaxs.t. 51522450 xxxxx0 x x515x 224x 5x 24s.t. 5min152245xxxxmaxs.t. 5155224xxxx 求解线性规划问题时，解的情况有：惟一最优解；无界解；无可行解；无

13、穷多最优解。 2022-3-22Tsinghua University Introduction to Operations Research生产I、II两种产品，要占用A、B设备及调试时间，每件产品机时利润如表所示 15245产品I产品II每天可用时间1占用A机时占用B机时调试时间利润0612521如何生产使每天利润最大？252022-3-22Tsinghua University Introduction to Operations Research数学规划模型 122121212max2s.t. 515622450,0zxxxxxxxxx262022-3-22Tsinghua Unive

14、rsity Introduction to Operations Research0, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx3z 8z 8.5z 0z 1x2x7z 122zxx12zxx梯度方向最优解最优目标值目标函数等值线27最优解?2022-3-22Tsinghua University Introduction to Operations Research15245III每天可用时间1占A机时占B机时调试时间利润4011521II产品I0612生产I、II、III三种产品，要占用A、B设备及调试时间，每件产品机时利

15、润如表所示如何生产使每天利润最大？282022-3-22Tsinghua University Introduction to Operations Research数学规划模型 1232312123max2s.t. 5415622450,1,2,3izxxxxxxxxxxxi292022-3-22Tsinghua University Introduction to Operations Research1x2x3x0, 3, 075. 3, 0, 075. 3, 0,25. 10, 0, 03, 0, 21, 0, 40, 0, 40, 5 . 1, 5 . 33z 7z 8.5z 126

16、224xx235415xx123x5xx8z 9z 1232zxxx3.75z 6.25z 0z 302022-3-22Tsinghua University Introduction to Operations Research一维、二维、三维共有规律1. 可行集中任意两点的连线都在可行集内：凸集2. 最优解都不在两个不同点的连线上：顶点3. 所有顶点的个数有限：有限集312022-3-22Tsinghua University Introduction to Operations Research基本定理与基本算法322022-3-22Tsinghua University Introdu

17、ction to Operations Research向高维推广要解决的基本问题1. 证明可行集总是凸集，总有顶点是最优解 所有顶点组成的集合总是有限集2. 如何计算顶点3. 如何在顶点集中找到最优解332022-3-22Tsinghua University Introduction to Operations Research凸集凸集非凸集如果某个集合中任意两点连起来的直线都属于该集合，则称其为凸集，否则为非凸集，如下图所示数学定义： 是凸集当且仅当对任意实数 和任意的 均成立1X2X1X2X211XX1021,XX342022-3-22Tsinghua University Intro

18、duction to Operations Research线性规划的可行集是否是凸集？标准线性规划问题（线性规划问题的标准型式）的可行集是否是凸集？首先考察更一般的情况。352022-3-22Tsinghua University Introduction to Operations Research线性规划的规范形式11mins.t. ,10,1njjjnijjijjc xa xbimxjn mins.t. 0TC XAXbX1ncCc1mbbb1111nmmnaaAaa1nxXx362022-3-22Tsinghua University Introduction to Operatio

19、ns Research对任意的 可以推得线性规划的可行集是凸集,0nX XRAXb X 规范形式可行集121212,0,0XXAXb AXb XX1212111AXXAXAXbbb101210XX121AXX满足凸集定义372022-3-22Tsinghua University线性规划问题标准型的可行集是凸集（证法相同） Introduction to Operations Research凸集的顶点如果凸集内的一点不在凸集内任何不同的两点连起来的直线上，则称该点为该凸集的顶点，如下所示（顶点）数学定义： 是凸集 的顶点当且仅当不存在实数 和 满足（不是顶点）211XXXX2121,XXXX

20、10382022-3-22Tsinghua University Introduction to Operations Research一二三维规范形式顶点的共有规律515x 0 x 0 x *5153xx392022-3-22Tsinghua University Introduction to Operations Research一二三维规范形式顶点的共有规律10 x 20 x 2515x 125xx126224xx*12125,62243.5,1.5TxxxxX120,00,0TxxX120,5150,3TxxX402022-3-22Tsinghua University Introd

21、uction to Operations Research一二三维规范形式顶点的共有规律235415xx126224xx123x5xx10 x 20 x 30 x 顶点是该点所有起作用约束(不等式成为等式的约束)构成的线性方程组的唯一解*1231225,6224,04,0,1TxxxxxxX412022-3-22Tsinghua University Introduction to Operations Research0, 0524261552121212xxxxxxx顶点是该点所有起作用约束(不等式成为等式的约束)构成的线性方程组的唯一解1203xx21212125156224500 xx

22、xxxxx215150 xx起作用约束该线性方程组的解唯一该点是顶点422022-3-22Tsinghua University Introduction to Operations Research0, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x432022-3-22Tsinghua University Introduction to Operations Research0, 0524261552121212xxxxxxx顶点是该点所有起作用约束(不等式成为等式的约束)构成的线性方程组的唯一解1202xx21212

23、125156224500 xxxxxxx10 x 起作用约束该线性方程组的解不唯一该点不是顶点442022-3-22Tsinghua University Introduction to Operations Research0, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x0, 2452022-3-22Tsinghua University Introduction to Operations Research那么当且仅当等式方程组的解唯一时 是 的顶点规范形式顶点的数学描述规范形式可行集1,10,1nijjijja x

24、bimxjn :X11,(1), ( ),0,(1),( ) ,0,(1), (1), ( ) ninijjijjjijjja xb ikk mxjk ma xbikk mkk nxjmk n对任意的 ，将所有的线性不等式进行如下划分X 462022-3-22Tsinghua University Introduction to Operations Research1203xXx 21212125156224500 xxxxxxx4722211215150622450 xxxxxxx2022-3-22Tsinghua University0, 0524261552121212xxxxxxx

25、Introduction to Operations Research1,10,1nijjijja xbimxjn :由于由等式方程约束条件产生的只能是等式，所以对任意的 可进行如下划分（注意 ）标准形式顶点的数学描述X 10,(1), ( ), 1,0,(1), ( )njijjijjxjkk ma xbimxjk mk n 当且仅当上面的等式方程组解唯一时 是 的顶点X482022-3-22Tsinghua Universitymn Introduction to Operations Research一维规范形式转换为标准形式的顶点规律3x 0 x 49xy3330,0 xyxy顶点13

26、0030 xyxxyy顶点233000 xyxyyx2022-3-22Tsinghua University Introduction to Operations Research0, 0524261552121212xxxxxxx51, 05242615552142132ixxxxxxxxxi线性方程组解唯一，该点是顶点23121251562245xxxxxx0, 0, 5 . 7, 5 . 1, 5 . 354321xxxxx502022-3-22Tsinghua University Introduction to Operations Research0, 43, 25 . 1, 5

27、. 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x512022-3-22Tsinghua University Introduction to Operations Research212412551562245xxxxxxx线性方程组解不唯一该点不是顶点123451,3,0,12,1xxxxx520, 43, 25 . 1, 5 . 33, 00, 010 x 20 x 2515x 125xx126224xx1x2x2022-3-22Tsinghua University Introduction to Operations Research0, 052

28、4261552121212xxxxxxx可行集原始表示可行集等价表示51, 05242615552142132ixxxxxxxxxi任意指定两个变量，如 ，解线性方程组 ktxx ,判断所得到的解是否可行，即是否都不小于05242615552142132xxxxxxxx00ktxx532022-3-22Tsinghua University Introduction to Operations Research52426155212132xxxxxx0054xx5242615552142132xxxxxxxx0, 0, 5 . 7, 5 . 1, 5 . 354321xxxxx例如得到一个顶点

29、求得542022-3-22Tsinghua University Introduction to Operations Research求得又例如有变量为负数，不是顶点524215524232xxxxx0051xx5242615552142132xxxxxxxx0,14,10, 5, 054321xxxxx552022-3-22Tsinghua University Introduction to Operations Research标准形式顶点的等价描述之一1njjjP xb1, 1TjjmjPaajn 1111, 1jnnijjijjjmjmaba xbimxab ( )( )( )10

30、,1,mk jk jk jjxjmPxb 10,(1), ( ), 1,0,(1), ( )jnijjijjxjkk ma xbim xjk mk n 当且仅当 的正分量对应的系数向量线性无关X 562022-3-22Tsinghua University Introduction to Operations Research5241510001000112516054321xxxxx5242615552142132xxxxxxxx5 , 2 , 1, 0ixi5 , 2 , 1, 0ixi123451,3,0,12,1xxxxx572022-3-22Tsinghua University I

31、ntroduction to Operations Research标准形式顶点的等价描述之二如果 是行满秩矩阵，那么 是可行集11,0, 1nTnjjjjXxxP xb xjn 的顶点充要条件是：存在可逆方阵 ，1,nPP(1)(),kk mPP可以把 的分量划分为 ，使满足XX(1)1(1)()( )(),0,0,1kkk mk jk mxPPbxmjnx ( ),1,k jxjn 主要理由：( )( )1mk jk jjPxb正分量对应的系数向量线性无关582022-3-22Tsinghua University Introduction to Operations Research称可

32、行的基本解为基本可行解线性规划标准形式的基阵、基本解和基本可行解(1)(),kk mPP称可逆矩阵 为基阵(1)1(1)()( )(),0,1kkk mk jk mxPPbxmjnx 称其分量由下式决定的 为基本解X标准线性规划的基本可行解就是可行集的顶点标准线性规划的可行集的顶点个数总是有限的称基阵对应变量为基变量，其余变量为非基变量592022-3-22Tsinghua University Introduction to Operations Research线性规划标准形式的基本定理【定理1】一个标准形式线性规划问题若有可行解，则至少存在一个基本可行解【定理2】一个标准形式线性规划问题

33、若有有限的最优目标值，则一定存在一个基本可行解是最优解【定理3】如果标准线性规划问题的某个基可行解的相邻的基可行解都不比它好，那么这个基可行解就是最优解602022-3-22Tsinghua University Introduction to Operations Research定理1的图形表示只要可行解不是顶点，就可以沿某个方向移动直至某个不起作用约束变成起作用约束，如此继续一定找到顶点10 x 20 x 23515xx1255xxx1x2x1246224xxx20 x 10 x 30 x 40 x 50 x 0X1X51, 05242615552142132ixxxxxxxxxi612

34、022-3-22Tsinghua University Introduction to Operations Research定理2的图形表示只要最优解不是顶点，就可沿等值线移动直至某个不起作用约束变成起作用约束，如此继续一定找到最优顶点假设：125zxxx10 x 20 x 23515xx1255xxx1x2x1246224xxx20 x 10 x 30 x 40 x 50 x 0X1X2X622022-3-22Tsinghua University Introduction to Operations Research例：2143,2242,1232,2241,1231,2221该问题至多

35、有下面 个可能的基阵624C12341234max12347s.t.221230, 14jzxxxxxxxxxj 利用基本定理求解线性规划问题632022-3-22Tsinghua University Introduction to Operations Research对每个基矩阵 ，计算 ，可得11372143,25 . 037224225 . 0371232,611313722412 . 24 . 0371231,5 . 54372221111111BbB1该线性规划只有3个基本可行解642022-3-22Tsinghua University Introduction to Oper

36、ations Research由 可确定对应的基本可行解24132221A1111221331370.40.4, 0, 2.2, 0,2.62132.22370.50, 0.5, 2, 0,2.5213234710, 0,1,1,21231TTTXzXzXz 如果该问题存在有限的最优解， 就是最优解1X1234zxxxx由 可算出对应的目标函数值652022-3-22Tsinghua University Introduction to Operations Research单纯形法662022-3-22Tsinghua University Introduction to Operation

37、s Research顶点搜索路径假设从顶点 出发到达顶点10 x 20 x 23515xx30 x 0X1X3X0X1X672022-3-22Tsinghua University Introduction to Operations ResearchT00 0 15 24 5X ， ， ，T10 3 0 18 2X ， ，23124125125156224500 xxxxxxxxxx23124125135156224500 xxxxxxxxxx起作用约束起作用约束1. 相邻顶点间只有一个起作用约束不同（非基变量）2. 若顶点不是最优解，其相邻顶点集中有更好的顶点682022-3-22Tsin

38、ghua University Introduction to Operations Research顶点搜索路径10 x 20 x 23515xx1255xxx1246224xxx30 x 40 x 50 x 0X2X1X3X692022-3-22Tsinghua University Introduction to Operations Research如何计算选定进基变量后的基本可行解如何判断已经找到最优的基本可行解如何选择进基变量使目标函数改进假定已知一个基本可行解702022-3-22Tsinghua University Introduction to Operations Res

39、earchT00 0 15 24 5X ， ， ，T10 3 0 18 2X ， ，23124125125156224500 xxxxxxxxxx23124125135156224500 xxxxxxxxxx起作用约束起作用约束712022-3-22Tsinghua University Introduction to Operations Research例15 , 2 , 1, 052415100010001125160s.t. 0002max5432154321jxxxxxxxxxxxj5241512516021543xxxxx由此可看出 是一个基本可行解TX5 ,24,15, 0 ,

40、0我们将基变量只出现在一个等式的等式约束称为对应的基本可行解的表示式（教材中称为典式），由表示式可看出基本可行解。其等式约束可写成722022-3-22Tsinghua University Introduction to Operations Research在 的各行除以 的系数假设我们想要让 变成基变量，即选择 为进基变量，根据基本可行解的表示式，必须让 只出现在一个等式约束中2x2x51231111305 . 02 . 021543xxxxx2x5241512516021543xxxxx可得2x732022-3-22Tsinghua University Introduction to

41、 Operations Research51231111305 . 02 . 021543xxxxx在 中选定一行，用其它行减去该行，即可达到只有一行有 的目的，例如：2x5721001215 . 02 . 02155453xxxxxxx整理后可得5721111215 . 02 . 051243xxxxx问题：第一个方程的右边出现负数742022-3-22Tsinghua University Introduction to Operations Research51231111305 . 02 . 021543xxxxx为了避免前面的问题，在方程中，只能用其它行减去第一行，即右边常数最小的一

42、行，由此可得2930011302 . 02 . 05 . 02 . 02135343xxxxxxx752022-3-22Tsinghua University Introduction to Operations Research整理后得到2932 . 02 . 02 . 01305 . 031542xxxxx再将第二行除以 得到基本可行解的表示式5 . 021832 . 04 . 02 . 016031542xxxxx该基本可行解是 , 变成非基变量，它是原来的基本可行解在保留 的行的基变量TX2 ,18, 0 , 3 , 03x2x762022-3-22Tsinghua Universit

43、y5241512516021543xxxxx Introduction to Operations Research51231111305 . 02 . 021543xxxxx5241512516021543xxxxx由于 的 等于152245155123其中 和 分别是 52415125中进基变量 的系数向量和右边常数向量，所以前面选择保留 的行的方法可以总结为选择达到2x15,224,515min2x的行，一旦选定这样的行，在该行的基变量将变成非基变量，从而确定了出基变量772022-3-22Tsinghua University Introduction to Operations Re

44、search如果我们又想让 进基，由于21832 . 04 . 02 . 016031542xxxxx现在已知基本可行解 的表示式为TX2 ,18, 0 , 3 , 03x采用前面总结的规则应该保留第二行的 ，但是若将第二行的 前的系数变成1 ，必须在第二行除以 ，此时右边系数将变成负数，所以，只能选择进基变量系数非负的行保留进基变量4 . 0182 . 02,4 . 018,2 . 03min3x4 . 03x782022-3-22Tsinghua University Introduction to Operations Research21832 . 04 . 02 . 01603154

45、2xxxxx由于 ，让 进基只能用第一行的 消去其它行的 ，对于 的系数不是正数的行，我们需要将第一行乘以一个合适的正数加到相应的行，这种操作不会使右边项的数变成为负数，因此在选择保留进基变量所在行的过程中不用考虑进基变量的系数不是正数的行3x3x3x3x792022-3-22Tsinghua University Introduction to Operations Research可以利用数据表完成换基运算的表示式由下面的数据表完全确定5241512516021543xxxxxTX5 ,24,15, 0 , 051001124010261500150RHSBV54354321xxxxxxx

46、x（基变量）（右边项）802022-3-22Tsinghua University Introduction to Operations Research让 进基是对数据表进行如下运算：2102 . 00118014 . 0063002 . 010RHSBV54254321xxxxxxxx2x51001124010261500150RHSBV54354321xxxxxxxx 5 (-2) + (-1) + 15,224,515min812022-3-22Tsinghua University Introduction to Operations Research总结前面的讨论，可得到下面的一般

47、规则：假设某基本可行解的表示式是BnjnjmjmjBXxPxPX)()() 1() 1(其中(1)1 ( )(1)11( )( )()( )(),jj tjBj tj tBj mm j tj mxpxXPB PtXB bxpx如果要选 （ ）进基，则应该仅保留第 行的 ，即 出基，其中 满足)(tjxl)(tjx)(ljxl)()(0)()(min)(tjiijptjlljpxpxtjintm1822022-3-22Tsinghua University Introduction to Operations Research为获得 进基、 出基后的基本可行解表示式，需要对原来的表示式Bnjnj

48、mjmjBXxPxPX)()() 1() 1(具体做法：先在第 行除以 ，再将第 行分别乘以 加到第 行l), 2 , 1(limii)(tjlpl)(tjx)(ljx进行行等价变换，使 前面的系数向量)(tjx变成)()()(1)(tjmtjltjtjpppP010)(tjip832022-3-22Tsinghua University Introduction to Operations Research1234512345max 2000 s.t.051001562010241100150,1,2,5jxxxxxxxxxxxj 13452010015560102421001510,1,2

49、,5jxxxxxxj 842022-3-22Tsinghua University Introduction to Operations Research(1)(1)( )( )( )( )( )( )( )Bj mj mj nj nBj tj tBXPxPxXPPX( )( )( )( ),( )( )0,1,BBj tj tj iXXPxxmin it 任取正数 ，定义 维向量 的分量如下：n( )X由 可知 ，满足不等式约束，此外( )0X0)(tjP满足等式约束，因此 是可行解，并且其分量 在可行集里可以趋于无穷大( )X 时对应的变量在可行集可趋于无穷大0)(tjP特殊情况：)()(

50、0)()(min)(tjiijptjlljpxpxtji无法计算( )( )j tx0)(tjP852022-3-22Tsinghua University Introduction to Operations Research小结假定已知基本可行解 的表示式为BnjnjmjmjBXxPxPX)()() 1() 1(X2. 只要 有一个分量大于 0 ，就可以通过行变换让 进基，形成一个新的基本可行解任取 ，则有以下结论：1. 如果 ，变量 在可行集可趋于无穷大ntm10)(tjP)(tjx)(tjP)(tjx862022-3-22Tsinghua University Introduction

51、 to Operations Research如何计算选定进基变量后的基本可行解如何判断已经找到最优的基本可行解如何选择进基变量使目标函数改进假定已知一个基本可行解872022-3-22Tsinghua University Introduction to Operations Research对于例我们已经得到两个基本可行解，即5 , 2 , 1, 052415100010001125160s.t. 0002max5432154321jxxxxxxxxxxxjTX2 ,18, 0 , 3 , 0TX5 ,24,15, 0 , 0记12345()2000f Xxxxxx则()0,()3f Xf

52、 X如何找到其目标函数值大于 的基本可行解？()f X882022-3-22Tsinghua University Introduction to Operations Research21832 . 04 . 02 . 016031542xxxxxTX2 ,18, 0 , 3 , 0已知 的表示式为将上式确定的基变量对非基变量的函数关系代入目标函数 ，可以得到由于每个变量都不能小于0，由上式可知，当且仅当 取正数（等价于让其进基）时，才能获得比 更大的目标函数值1313()320.2()20.2 f XfxXxxx1x()f X12534()2000 xxxfxxX892022-3-22Ts

53、inghua University Introduction to Operations Research2102 . 0016618 . 0003002 . 010RHSBV14254321xxxxxxxx如前所述，让 进基是对数据表进行如下运算： (-6) + 12,618,03min2102 . 00118014 . 0063002 . 010RHSBV54254321xxxxxxxx1x902022-3-22Tsinghua University Introduction to Operations Research2102 . 0016618 . 0003002 . 010RHSBV

54、14254321xxxxxxxx根据数据表马上可知新的基本可行解为()()47f Xf XTX0 , 6 , 0 , 3 , 2其中 是 对应的目标函数值将上表确定的基变量对非基变量的函数关系代入目标函数 又可得新目标函数式13()()20.2xff XxX3535()()40.22()0.22 f Xf Xf XxxxxX912022-3-22Tsinghua University Introduction to Operations Research用 表示线性规划标准型的目标函数，它和 之XzzxcxcxcbxPxPxPnnnn22112211可将其写成下面的扩充的等式约束形式zbxcP

55、xcPxcPnnn222111例如，对于例题，其扩充的等式约束为zxxxxx524150100001000011125216054321间的函数关系完全由以下线性方程组所确定922022-3-22Tsinghua University Introduction to Operations Research21832 . 04 . 02 . 016031542xxxxxTX2 ,18, 0 , 3 , 0相当于对扩充的等式约束的前三行进行变换获得对原来的等式约束进行行变换得到 的表示式zxxxxx21830100001002 . 04 . 02 . 01001216054321932022-3-

56、22Tsinghua University Introduction to Operations Research基变量的函数关系代入 以获得仅含非基变量的 ，相当于利用下面前三行等式将第四行的基变量的系数变成 021832 . 04 . 02 . 016031542xxxxx543210002xxxxxz将 所确定的基变量对非zxxxxx21830100001002 . 04 . 02 . 01001216054321312 . 023xxz942022-3-22Tsinghua University Introduction to Operations Researchzxxxxx2183

57、0100001002 . 04 . 02 . 01001216054321将第一行乘以-1加到第四行就可以得到32183010000102 . 02 . 04 . 02 . 00001216054321zxxxxxX对于扩充约束我们将其称为基本可行解 的扩充表示式952022-3-22Tsinghua University Introduction to Operations Research1. 是基本可行解32183010000102 . 02 . 04 . 02 . 00001216054321zxxxxx从扩充表示式TX2 ,18, 0 , 3 , 0可以获得下述信息：2. 的目标函数

58、值满足 ，即X30 z3z3. 目标函数可以写成 ，因此让 进基能够增加目标函数值1x312 . 023xxz962022-3-22Tsinghua University Introduction to Operations Research前面由 的表示式获得其扩充表示式的过程可利用下面扩充的数据表（单纯形表）完成TX2 ,18, 0 , 3 , 0zxxxxxxxx000122102 . 00118014 . 0063002 . 010RHSBV54254321其中前面三行数据由 的表示式确定，最后一行是目标函数和变量间的（任意一种）约束式X972022-3-22Tsinghua Univ

59、ersity Introduction to Operations Research该表能够完全确定基本可行解 的扩充表示式，我们将其称为 的单纯形表对前面的单纯形表通过行变换将最后一行的基变量前面的系数变成 0 就得到下面的单纯形表3002 . 0022102 . 00118014 . 0063002 . 010RHSBV54254321zxxxxxxxxXX982022-3-22Tsinghua University Introduction to Operations Research3002 . 0022102 . 00118014 . 0063002 . 010RHSBV542543

60、21zxxxxxxxx利用 的单纯形表，很容易获得让 进基后的基本可行解的单纯形表，即先由右边项和 前面的系数的比值确定出基变量为1x5x12,618,03min然后通过行变换将 所在列除了第三行以外的系数变成 0 即可得到新的基本可行解对应的单纯形表1xX1x992022-3-22Tsinghua University Introduction to Operations Research新的基本可行解对应的单纯形表为据此可知：2. 的目标函数值满足 ，即X70 z7z3. 让 进基能够增加目标函数值3x1. 是基本可行解TX0 , 6 , 0 , 3 , 27202 . 0002102 .