线性规划问题的最优解

宿州学院 2011 届本科生毕业论文线性规划问题的最优解1 线性规划问题的最优解引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。1. 线性规划问题的最优解探讨1.1 线性规划问题的提出考虑下面的线性规划问题的标准型：目标函数：CXZmin (1) 约束条件：0XbAX (2) 其中，),,,(21ncccC,TnxxxX),,,(21,Tmbbbb),,,(21,nmijaA)(阶矩阵。设 B 是 A 中 m个线性无关的列向量构成的一个基，mmijaB)(阶矩阵，这样将矩阵 A 分成两个部分，即 A=),(NB,X=),(NB XX,C=NB CC ,,BX ,BC 为基 B对应的非基变量和系数，NX,NX为 N对应的非基变量和系数，这样将线性规划问题改写为： minZNB CC ,BBXX (3) 约束条件：宿州学院 2011 届本科生毕业论文线性规划问题的最优解2 0),(NBNBXXbXXNB (4) 经过矩阵变换，得出关于基B 的标准型如下：1minBCZB+(NC-1BC BN)NX (5) 约束条件：0,11NBNBXXbBNXBX (6) TmbbbbB),,,(''21'1mnmmmmnmmnmmaaaaaaaaaNB2122212121111将（ 5）（6）展开为：Zmin'1imii bc+nmj1('1ijmiijacc)jx (7) 约束条件：inmjjijibxax'1' ,mi,,2,1 (8) 0jx ,nj,,2,1 (9) 令'10imiibcZ , j'1ijmiijacc ,nmmj,,2,1 , 称j 为检验数。1.2 最优解判别准则准则一：若TmbbbX)0,,0,,,,('2'1')1(，为对应于基B 的基本可行解，且对于一切的nmmj,,2,1，j >0 ，则 X 为线性规划问题的最优解。宿州学院 2011 届本科生毕业论文线性规划问题的最优解3 证明：j >0 ，由（'7 ）式可知，对任意一组可行解TnxxxX),,,(21，njjj xcZ1 ,均有0ZZ，但)1(X能使等式成立，即0ZZ，故)1(X为线性规划问题的最优解。准 则 二 ： 当j0 ,nmmj,,2,1， 有 某 一 个0j， 设1mj ,mi,,2,1 ,01'ima，则该线性规划问题有第二个最优的基本可行解。证明：构造一个行解)2(X，('8 ) 得：11''mimiixabxmi,,2,11mx00jxnmj,,2根据原则0|min1'1''1imimimiaab1''LmLab1mx1''LmLab , 0Lx将)2(X带入原目标函数（ 4）得：',1imLiiibcZ+(1mc-1'1immii ac+...