線性規(guī)劃基本性質(zhì)

1、關(guān)于線性規(guī)劃的基本性質(zhì)第一張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月第二張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/112第三張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/113第四張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/114第五張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/115第六張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/116第七張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月第八張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/118第九張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/119第十張，PPT共二十三頁(yè)

2、，創(chuàng)作于2022年6月2022/8/1110第十一張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月第十二張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/1112 是凸集(convex set)，如果對(duì)S中任意兩 點(diǎn) x , y 和(0,1)中的任一數(shù) 滿足四、線性規(guī)劃解的概念和性質(zhì)1. 線性規(guī)劃解的概念第十三張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/1113第十四張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/1114B是可逆的；B的行列式0第十五張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/1115x0第十六張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022

3、/8/1116基本解的個(gè)數(shù)？第十七張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/1117非基變量是自由變量. 基變量用非基變量表示。第十八張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/1118引理1. 線性規(guī)劃的可行解為基可行解的充要條件是其正分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān). 引理2. 可行解x是K的頂點(diǎn)的充要條件是x為線性規(guī)劃的基可行解。第十九張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/11當(dāng)這些列向量線性無(wú)關(guān)時(shí)，由引理1 ，知x為基礎(chǔ)可行解.當(dāng)向量 線性相關(guān)時(shí)，則存在一組不全 為零的數(shù)組 ,使得 成立。證明： 設(shè)x是可行解，且前k個(gè)正分量為 若它們?cè)诰仃嘇中對(duì)

4、應(yīng)的列向量為（1）則有由(2)式右端為零，因此總可假定存在非零的 ,(否則乘以-1于（2）的兩端)，總有 成立。（2）第二十張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/11在上式中乘以 并與（2）相加得： 因而，當(dāng)取時(shí)，上式中至少會(huì)有一個(gè)分量。也就是說(shuō)，若記上式中對(duì)應(yīng)的點(diǎn)為，則正分量 比x至少減少一個(gè). 若此時(shí)，正分量對(duì)應(yīng)的 線性無(wú)關(guān)，則已是基礎(chǔ)可行解。 否則重復(fù)上述過(guò)程，正分量的個(gè)數(shù)不斷減少，至多減至只剩一個(gè)時(shí)為止，例如對(duì)應(yīng)列向量為 但，它是只含一個(gè)向量的線性無(wú)關(guān)組，因此，如果約束集有可行解，則必定存在基本可行解。 第二十一張，PPT共二十三頁(yè)，創(chuàng)作于2022年6月2022/8/11定理2 （線性規(guī)劃基本定理） 設(shè)約束集K非空( )有解，且最大值可在一個(gè)頂點(diǎn)（基礎(chǔ)可行解）上達(dá)到。對(duì)任意的，LP的目標(biāo)函數(shù)值有上界，則線性規(guī)劃第二十二張，P