线性规划的基本概念与基本定理.ppt

分量对应A中的列向量线性无关，则就是基本可行解（定理1（1）），取即得到基本最优解.若正分量对应A中的列向量线性相关，则存在不全为零的数使：。构造n维列向量y使其第1，2，……k分量分别为而其余分量为0，则有y≠0且取可见0且即和是两个可行解，分别记为及。它们的目标函数值分别为：第30页，共55页，星期日，2025年，2月5日因为是最优解，所以：,又因为故于是有;这表明及均为最优解。又由的取法知当时,这时中第l分量等于0，当时,这时中第l分量等于0。所以至少有一个的正分量个数比的正分量个数要少，记这个解为。那么也是最优解。可见，如果不是基本最优解，即的正分量对应A中的列向量线性相关，那么总可以令一个最优解，其正分量个数比正分量个数少。如果是基本最优解，即的正分量对应A中的列向量线性无关，则取,即证明3（2）。第31页，共55页，星期日，2025年，2月5日（ii）只有唯一的一个正分量，因A的列向量均为非零故的正分量对应A中的列向量线性无关。同（I）一样可知即为基本最优解。（iii）=0这时=0是可行解。由上面的证明已知=0就是基本最优解。到此，我们证明了定理的第（2）部分。（i）的正分量对应A中的列向量线性无关，因此是基本可行解。取即为基本最优解（3）假定目标函数在极点上达到最优值又设它们的任意凸组合为：如果的正分量对应A中的列向量线性相关，则可重复上述步骤，得到最优解经过有限步必达到下面的三种情形之一：第32页，共55页，星期日，2025年，2月5日上面，定理3，定理4是线性规划的两个很重要的定理。证明了线性规划的基本可行解等同于可行域的顶点。并且，如果线性规划有最优解，则必在可行域的顶点上达到最优。这样，一个有最优解的（SLP）问题，是一定可以从可行域的极点中（即基本可行解中）求得最优解的。而又故知的凸组合也是目标函数的最优值点。至此，我们全面证明了定理4。第33页，共55页，星期日，2025年，2月5日而基本可行解是对应A中的m个线性无关的列向量。A只有n个列向量。从n个列向量中取出m个线性无关向量相成的向量组。其数目上有限的。因此基本可行解的数量也是有限的。它不会超过：个。这样对一个有最优解的线性规划利用穷举法可以在有限步内找到基本最优解。但运算是很大的。我们后面要学习的单纯形方法就是根据这一基本定理在有限个基本可行解中寻