12.1線性規劃的基本概念
12.1.1可行解，可行域
定義12.1.1：稱滿足全部約束條件的向量為可行解或可行點。
例如： slp
如果滿足這些約束，即且，則就是slp的可行解。
定義12.1.2：稱所有可行解（點）構成的集合為可行集或可行域。也稱為可行解集。
例如：上面 slp 的可行域為
定義12.1.3：若乙個線性規劃問題的可行集為空集時，則稱這一線性規劃無可行解。這時線性規劃的約束條件不相容。
由上一章的分析可以看到：乙個線性規劃的可行解集可以是空集，有界非空集和無界非空集。
12.1.2最優解，無界解
定義12.1.4：稱使目標函式值達到最優值的可行解為線性規劃問題的最優解
定義12.1.5：對於極大化目標函式的標準線性規劃問題，定義其無界解如下：對於任何給定的正數m，存在可行解 x 滿足，使。那麼稱該線性規劃問題有無界解。
由定義可知，無界解的意思是：若是極大化目標函式，則在可行域上目標函式值無上界；若是極小化目標函式，則在可行域上目標函式值無下界。那麼，有無界解的線性規劃問題一定沒有最優解。
例12.1.1 考慮線性規劃問題：
圖12.1.1
解：問題的可行域是上圖所示的無界凸多邊形區域，在此無界可行域上，目標函式值無上界，所以這個線性規劃問題有無界解。
例12.1.2
解：此問題的可行域如上圖，是乙個無界的多邊形。但極大化目標函式卻以1為上界。
因此這個線性規劃問題沒有無界解，而且事實上，此問題目標函式最優值max f=1在可行域射線上均可達到。
12.1.3. 基本可行解
定義12.1.6：對於約束條件ax=b，設a是秩m的mｘn矩陣，用(, j=1 ~n) 表示a的第j列向量。即a=()。由a的m個列向量構成的m階方陣 b=()
若b是非奇異的，即detb0，則稱b為乙個基或稱為乙個基矩陣。
因為slp問題中含有約束條件ax=b，因此也通常稱b為線性規劃slp的乙個基。
由上面定義可知，b中m個列向量是線性無關的，並且它是a的列向量組的乙個最大無關組。
按定義，a中m個列向量，只要是線性無關的就可以構成乙個基。
定義12.1.7：若變數對應a中列向量包含在基b中，則稱為b 的基變數；若變數對應a中的列向量不包含在基b中， 則稱為b中的非基變數。
例12.1.3 求滿足使
解：則的列是線性無關的，即是線性無關，因此是一組基。而，不在這個基中，所以為非基變數。
定義12.1.8 ：
設ax=b, x≥0乙個基，其對應的基變數構成的m維列向量記為這時若全非基變數等0，則 ax=b ,得唯一解.記為於是得到方程組ax=b的乙個解非基變數稱之為對應於基b的基本解。這個定義也告訴我們怎樣找乙個基本解）
如：上面例12.1.
2中，非基變數。則可得。所以是對應於基b的乙個基本解，但由於=-2<0.
不能滿足約束條件，所以這個基本解不是原問題的可行解。（為什麼？）
這是因為，按照定義，基本解中的 n-m個非基變數必須取0值只有m個基變數取值才可能不等於0。但可以取負值。因此基本解不一定滿足slp的非負要求。
定義12.1.9：對應於基b的基本解，若基變數取非負值，即，b>0，則稱它為滿足約束 ax=b, x>o的基本可行解。
對應地稱b為可行基，因slp中具有此約束條件。也通常稱為slp的基本可行解。
定義12.1.10：使目標函式達到最優值的基本可行解，稱為基本最優值。
例12.1.4：（slp)如例12.1.3，試找乙個基本可行解。
解：是其乙個基矩陣.是乙個基。則為基變數。為非基變數。令.得. 故是原問題的乙個基本可行解，為基可行基。
上面我們講到基本解中有n-m個分量必須取零值，而只有m個基變數取非零值。而基本可行解，它一方面是基本解，另一方面又是可行解，因為它是基本解，所以n-m個非基變數取0值；它是可行解，則m個基變數取非負值，從而基本可行解正分量是個數不超過m.
那麼滿足ax=b,x0的正分量個數不超過m的可行解。是否一定是基本可行解呢？
我們舉例說明這個問題。
例12.1.5.已知約束條件為：
它有正分量個數等於m(m=2)的可行解。但它不是基本可行解。
證明：（反證法）假設可行解x=(3,1,0,0)t面約束的基本可行解。因為基本可行解中非基變數取0值，基變數取非負值。
在這個可行解中非零正值，因此不可能是非基變數，只能是基變數。
按定義，基變數對應的係數矩陣中的列向量應構成乙個基矩陣b.但這裡是線性相關的（), 這與b是基矩陣矛盾。故知x=(2,1,0,0)t是基可行解。
由此例可見，雖然可行解（3，1，0，0）t 正分量個數不超過m，但它的正分量對應的列向量線性無關，不能與一基矩陣相聯絡，所以它不是乙個基本可行解。
現在我們把例12.1.4中鬆弛變數去掉，約束變為
圖12.1.2
其可行域如圖12.1.2，可行解（3，1，0，0）t用表示為圖上點（3，1）。
由圖可見這不是可行域的頂點。而我們今天將證明基本可行解是可行域的頂點。而在例中線性無關，所以b=()是乙個基矩陣，對應的基本解為（4，0，0，0）t用座標表示則為平面上的點（4，0），是上圖可行域的頂點。
對於這個基b=()的基本可行解（4，0，0，0）t 。除了非基變數外，還有基變數,這樣的基本可行解稱為退化的基本可行解。
定義12.1.11：有基變數取0值的基本可行解，稱為退化的基本可行解，它對應的基b稱為退化的可行基。
m個基變數均取正值的基本可行解，稱為非退化的基本可行解，對應基b稱為非退化的可行基。如果乙個線性規劃問題的所有基本可行解都是非退化的，則稱這個線性規劃問題是非退化的。
由以上定義可知，如果約束問題有m 個基變數，則在退化的基本可行解中，正分量個數一定小於m.
在基本可行解中去正值的變數一定是基變數。這樣基本可行解中正分量個數也不會超過m. 但是上面的例4已經說明，正分量個數不超過 m 可行解不一定是基本可行解，還要看可行解中正分量對應的列向量是否線性無關而定。
然而基本可行解中正分量對應的係數矩陣的列向量一定線性無關。
定理12.1.1 設 a是m×n矩陣，秩為 m, 對於ax=b, x ≥0有：
（1）可行解是基本可行解的充要條件是的分量，對應a中的列向量線性無關。
（2）如果x=(0,0….0)t 即x=0是可行解，則它一定是基本可行解。
證明：（1）必要性.假定是基本可行解，由基本可行解定義可知，中的正分量一定是基變數，基變數對應係數矩陣a中的列向量一定在基b中，則線性無關。
充分性.假定正分量對應a中的列向量線性無關，只要證明是基本可行解。
因為矩陣a的秩m，則k≤m（ k是的正分量個數）
當k=m時，只要m個線性無關的向量構成乙個基，而對應中的分量
，取正值的列向量線性無關。因此也構成乙個基，所以就是對應於該基的乙個非退化的基本可行解。
當k 因為有取0值的基變數，所以是對應於基（）的乙個退化基本可行基解。
（2）因為a的秩為m , 所以在a中一定存在m個線性無關的列向量，將其構成乙個b,對應於可行解x=(0,0 ,…0)t中的基變數取０值，所以可行解x=0是對應於基 b的退化的基本可行解。
根據這個定理，基本可行解也可以定義如下：
定義12.1.12：設a是m×n矩陣，秩為 m，對於 ax=b, x≥0 的可行解x，如果滿足：
（１）x 的正分量個數小於或等於 m
（２）x 的正分量對應 a 中的列向量線性無關。
則稱 x 是乙個基本可行解。
若 x=0 是可行解，則定義它是乙個基本可行解。
注：定義12.1.9與定義12.1.12的等價性可由定義12.1.7推出。
12.1.4 凸集
我們先考察二維平面上直線段上任意一點的表示形式。
取x.y為平面上兩點，用以原點為起點的向量來表示x 和 y並設z是線段xy上任意一點，得向量 z-y.它與向量x-y平行且方向相同於是有當時，z=y；時， z=x
當由0連續變動到1時，點z由y沿此直線連續的變動到x，且因z-y平行x-y，則有：於是有：
這說明當時，表示以x，y為端點的直線段上的所有點，因而它代表以 x，y為端點的直線段。
一般地，如果x，y是n維歐氏空間中的兩點，則有如下定義：
定義12.1.13：如果 x=(x1…x2)t,y=(y1…y2)t是中任意兩點，定義
的點所構成的集合為以x，y為端點的線段，對應的點 x, y叫做這線段的端點，而對應的點叫做這線段的內點。
定義12.1.14：設r是rn中的乙個點集，（即），對於任意兩點以及滿足的實數,恒有則稱r為凸集。
根據以上定義12.1.12及12.1.13可以看到，凸集的幾何意義是：連線凸集中任意兩點的直線段仍在此集合內。
例如實心的圓，實心的矩形，實心的球體，實心的長方體等等均是凸集，圓周不是凸集。直觀地看，凸集是沒有凹入的部分，其內部沒有孔洞。
圖12.1.3
上圖中(a)(b)是凸集，而(c)(d)不是凸集。
例12.1.5：集合是r3中的乙個凸集。（可按定義證明）
例12.1.6：是r2中的乙個凸集。
例12.1.7：（lp）問題： 的可行域
證明：設由定義知，只要證明 x1, x2 的任意凸組合即可。
因,有可見故知r是凸集。
注：可以用歸納法證明：如果r是凸集，則r中任意有限個點的凸組合均在r中。
定理12.1.2：(slp)問題的可行集是rn中的乙個凸集。（證明與例12.1.7相似）
定義12.1.16：設a是矩陣，b是m維列向量，集合如果r不是凸集，則稱r為多面凸集。
第十二章計畫的實施
一 教學要點 1 計畫實施的任務。2 目標管理的基本思想。3 目標的基本性質。4 目標管理的過程。5 滾動計畫法的基本思想。6 滾動計畫法的優缺點。7 網路計畫技術的基本步驟。8 網路圖的基本構成及繪製方法。9 網路計畫技術的優缺點。10 關鍵名詞 戰略性計畫 目標管理 滾動計畫法 網路計畫技術 網...
第十二章計畫的實施
歡迎光臨 貳囧鋪子 一 填充題 1 目標管理是美國管理學家 於1954年提出的。2 實踐中計畫組織實施行之有效的方法主要有和 3 滾動計畫法是一種 4 滾動計畫法的具體做法是 5 目標管理是一種程式，使乙個組織中的上下各級管理人員會同一起來制訂共同的目標，確定彼此的成果責任，並以此項責任來作為 6 ...
第十二章計畫的實施習題
一 教學要點 1 計畫實施的任務。2 目標管理的基本思想。3 目標的基本性質。4 目標管理的過程。5 滾動計畫法的基本思想。6 滾動計畫法的優缺點。7 網路計畫技術的基本步驟。8 網路圖的基本構成及繪製方法。9 網路計畫技術的優缺點。10 關鍵名詞 戰略性計畫 目標管理 滾動計畫法 網路計畫技術 網...