【文章內(nèi)容簡(jiǎn)介】 圖解法的實(shí)例 例 16 我們看到目標(biāo)函數(shù)的圖形恰好與約束條件（ 1）平行。當(dāng)目標(biāo)函數(shù)直線向右上方移動(dòng)時(shí)，他與凸多邊形相切時(shí)不是一個(gè)點(diǎn)，而是在整個(gè)線段 Q2Q3上相切。這時(shí)在 Q2點(diǎn)、 Q3點(diǎn)及 Q2Q3線段上的任意點(diǎn)都是目標(biāo)函數(shù)值 z達(dá)到最大，即該線性規(guī)劃問題有無窮多最優(yōu)解，也稱具有多重最優(yōu)解。 ??????????????）（）（）（）（40,3515216411222..33m a x21212121xxxxxxtsxxz圖解法的實(shí)例 例 17 用圖解法求下列線性規(guī)劃問題的最優(yōu)解 ??????????0,242..2m a x2112121xxxxxtsxxzx1 x2 如圖：此問題有可行域，但為無界解（無最優(yōu)解） 其原因是由于在建立實(shí)際問題的數(shù)學(xué)模型時(shí)遺漏了某些必要的資源約束。 圖解法的實(shí)例 例 18 用圖解法求下列線性規(guī)劃問題的最優(yōu)解 ????????????0,4126..32m a x21212121xxxxxxtsxxzx1 x2 用圖解法求解時(shí)找不到滿足所有約束條件的公共范圍，這時(shí)此問題無可行解。原因是模型本身有錯(cuò)誤，約束條件相互矛盾，應(yīng)檢查修正。 圖解法的解題思路和幾何上直觀得到的一些概念判斷，對(duì)求解一般線性規(guī)劃問題的單純形法有很大的啟示： （ 1）求解線性規(guī)劃問題時(shí)，解的情況有： 惟一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解 ； （ 2）若線性規(guī)劃問題的可行域存在，則可行域是一個(gè) 凸集 （凸多邊形，稍后介紹）； （ 3）若線性規(guī)劃問題的 最優(yōu)解存在 ，則最優(yōu)解或最優(yōu)解之一（如果有無窮多的話）一定能夠在可行域（凸集）的某個(gè) 頂點(diǎn) 找到； 三、求解線性規(guī)劃模型的圖解法 （ 4）解題思路是： 先找出 凸集的任一頂點(diǎn) ，計(jì)算在頂點(diǎn)處的 目標(biāo)函數(shù)值 。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值更優(yōu)，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更優(yōu)的另一個(gè)頂點(diǎn)，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點(diǎn)為止。 圖解法雖然直觀、簡(jiǎn)便，但是當(dāng)變量數(shù)大于兩個(gè)時(shí)，它就無能為力了。引入單純形法！ 四、單純形法 預(yù)備知識(shí)：凸集和頂點(diǎn) 線性規(guī)劃問題的解 幾個(gè)基本定理（不要求證明） 單純形法求解線性規(guī)劃 單純形法的計(jì)算步驟 四、單純形法 單純形法是求解一般線性規(guī)劃問題的基本方法，是1947年由丹齊格（ ）提出。 預(yù)備知識(shí)：凸集和頂點(diǎn) ① 凸集： 對(duì)一個(gè)給定的幾何圖形，通?？蓮闹庇^上判斷其凹凸性。但容易產(chǎn)生錯(cuò)誤。 凸集的嚴(yán)格定義： 如果集合 C中任意兩個(gè)點(diǎn) X X2，其連線上的所有的點(diǎn)也都是集合 C中的點(diǎn)，稱 C為凸集。 四、單純形法 預(yù)備知識(shí)：凸集和頂點(diǎn) ① 凸集： 因?yàn)?X X2的連線可表示為： aX1+（ 1a） X2（ 0a1） 所以凸集定義用數(shù)學(xué)語言表示為： 對(duì)任何 X1∈C ， X2 ∈C ，有 aX1+（ 1a） X2 ∈C （ 0a1），則稱 C為凸集。 預(yù)備知識(shí)：凸集和頂點(diǎn) ① 凸集 判斷下列幾何圖形是否是凸集？ （ a） （ b） （ c） （ d） 四、單純形法 預(yù)備知識(shí)：凸集和頂點(diǎn) ① 凸集： ② 頂點(diǎn) 凸集 C中滿足下述條件的點(diǎn) X稱為頂點(diǎn)： 如果 C中不存在任何兩個(gè)不同的點(diǎn) X X2，使 X成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn)。 對(duì)任何 X1∈C ， X2 ∈C ，不存在 X=aX1+（ 1a） X2 （ 0a1），則稱 X是凸集 C的頂點(diǎn)。 解釋：頂點(diǎn)是不會(huì)出現(xiàn)在集合 C中任意兩點(diǎn)之間的連線上。 四、單純形法 線性規(guī)劃問題的解 假設(shè)所要研究的線性規(guī)劃模型的形式為： 求解線性規(guī)劃問題，就是滿足約束條件（ b）、（ c）的方程組中找出一個(gè)解，使目標(biāo)函數(shù)（ a）達(dá)到最大值。 ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） 四、單純形法 （ 1）可行解 滿足上述約束條件（ b）、（ c）的解 X=（ x1， … ， xn） T 稱為線性規(guī)劃問題的 可行解 ，全部可行解的集合稱為 可行域 。 （ 2）最優(yōu)解 使目標(biāo)函數(shù)（ a）達(dá)到最大值的可行解稱為最優(yōu)解。 線性規(guī)劃問題的解 （ 3）基 設(shè) A為約束方程組（ b）的 m n階系數(shù)矩陣（設(shè) nm），其 秩為 m。 B是矩陣 A中的一個(gè) m m階的 滿秩子矩陣 ，稱 B是線性規(guī)劃問題的一個(gè) 基 。不失一般性，設(shè) ????????????mnmmnnaaaaaaaaa.....................212222111211）（ mmmmmPPaaaa,...,...............B 11111????????????B中的每一個(gè)列向量 Pj（ j=1,… ,m）稱為 基向量 ，與基向量 Pj對(duì)應(yīng)的變量 xj稱為 基變量 。線性規(guī)劃中除基變量以外的其他變量稱為 非基變量 。 ??? ????),......,2,1(..1mibxats injjij基 基向量 回顧：矩陣的秩的定義 定義 :如果數(shù)域 F 上的 m ? n 矩陣 ???????????????mnmmnnaaaaaaaaaA??????112222111211存在一個(gè) k 階子式不為零，并且所有的 k + 1 階子式全為零，則稱 A 秩為 k ，記作 r (A) = k . 顯然， r ( A ) ? min ( m , n ) 。 r ( AT ) = r ( A ) . 例 求矩陣 A 的秩，其中 .174532321????????????A 解 :在 A 中，容易看出２階子式 ,0132 21 ???而 A 的三階子式只有一個(gè) ｜ Ａ ｜ ,0|| ?A 因此 .2)( ?Ar（ 3）基 例 19 已知線性規(guī)劃 ?????????????????)5,...,2,1(02261035..24m a x53214321321jxxxxxxxxxtsxxxzj求所有基矩陣。 【 解 】 ：約束方程的系數(shù)矩陣為 2 5矩陣： ?????????10261001115A容易看出 r（ A） =2， 2階子矩陣有 C25=10個(gè)，其中第1列與第 3列構(gòu)成的 2階矩陣 不是一個(gè)基 ，因此基矩陣只有 9個(gè)，即： ?????????61015B1 ?????????01015B2?????????11005B3 ?????????2611B4?????????1201B8?????????0211B7?????????1601B6?????????0911B5?????????1001B9由線性代數(shù)知道，基矩陣 B必為非奇異矩陣，即 |B|≠0 。當(dāng)矩陣 B的行列式等于零是就不是基。 根據(jù)： B中的每一個(gè)列向量 Pj（ j=1,… ,m）稱為 基向量 ，與基向量 Pj對(duì)應(yīng)的變量 xj稱為 基變量 。線性規(guī)劃中除基變量以外的其他變量稱為 非基變量 。 請(qǐng)指出例 19中 B2的基向量、基變量和非基變量。 ?????????01015B2 ?????????10261001115AB2的基向量是 A中的第一列和第四列 B2的基變量是 x1和 x4 B2的非基變量是 x x3和 x5。 基變量和非基變量是針對(duì)某一確定的基而言的，不同的基對(duì)應(yīng)的基變量和非基變量是不相同的。 ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） 四、單純形法 （ 4）基本解 在約束方程組（ b）中，令所有 非基變量xm+1=xm+2=… =xn=0,又因?yàn)橛?|B|≠0 ，根據(jù) 克拉默規(guī)則 ，由 m個(gè)約束方程可解出 m個(gè)基變量的惟一解 XB=（ x1， … ，xm）。這個(gè)解加上非基變量取 0的值有 X=（ x1， x2， … ，xm， 0， … ， 0） T，稱為 線性規(guī)劃問題的基解 。顯然在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù) m，又基解的總數(shù)不超過 Cnm個(gè)。 線性規(guī)劃問題的解 對(duì)某一特定的基 B，令非基變量等于零， 利用（ b）求解出基變量， 則這組解成為基 B的基本解。 )1(22112222212111212111???????????????????nnnnnnnnnnbxaxaxabxaxaxabxaxaxa??????????????定理 (克拉默法則 ) 如果含有 n 個(gè)方程 的 n 元線性方程組 的系數(shù)行列式 0d e t212222111211??nnnnnnaaaaaaaaaA??????則方程組 (1)有唯一解，并且 njABx jj ,2,1,d e td e t ???其中 detBj 是將系數(shù)行列式 detA 的第 j 列元 a1j , a2j , … , anj , 換成常數(shù)項(xiàng) b1 , b2 , … , bn 后得到的行列式 . ??????????????),...,1(0),......,2,1(..m a x zj11njxmibxatsxcinjjijnjjj（ a） （ b） （ c） 四、單純形法 （ 5）基本可行解 滿足變量非負(fù)約束條件（ c）的基解稱為基可行解。 （ 6）可行基 對(duì)應(yīng)于基可行解的基稱為 可行基 （ 7）最優(yōu)基 基本最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基 線性規(guī)劃問題的解 例 19中 對(duì)于 B1來說， x x2是基變量， x x x5是非基變量，令 x3=x4=x5=0，則 因 |B|≠0 ，由克萊姆法則知， X x2有惟一解， 解得 x1=2/5， x2=1 則基本解為 X（ 1） = ?????????????????)5,...,2,1(02261035..24m a x53214321321jxxxxxxxxxtsxxxzj?????????61015B1????????2610352121xxxxT000152 ），，（例 19中 對(duì)于 B2來說， x x4是基變量， x x x5是非基變量，令 x2=x3=x5=0，則 因 |B|≠0 ，由克萊姆法則知， X x4有惟一解， 解得 x1=1/5， x4=4 則基本解為 X（ 2） = ?????????????????)5,...,2,1(02