【天津大學】《運籌學》（精品課） P3 - 3. 模型與圖解法 教學錄像（2）

我們前面介紹了線性規劃的問題和模型建立。 模型建立以後,我們將進一步介紹模型的求解。 先來介紹線性規劃問題的圖解法。 圖解法是用畫圖的方式求解線性規劃的一種方法。 它雖然只能用於解二維的問題,也就是隻有兩個決策變量的問題, 但是它的主要作用並不在於求解, 而是在於能夠直觀的說明線性規劃解的一些重要性質。 先來介紹圖解法的步驟。 圖解法第一步是做約束的圖形。 我們知道線性規劃模型的約束,包括資源約束和非負約束兩部分。 對於二維問題,非負約束,也就是兩個決策變量都大於等於零, 畫在平面直角座標系中就是一個第一象限。 我們以利1.1爲例, 它的約束就包括有資源約束部分和非負約束部分。 大於等於零,它就表示二維平面直角座標系的第一象限, 也就是說第一象限就是二維問題的非負約束的圖形。 接下來我們再來做資源約束的圖形。 資源約束以利1.1爲例, 我們看到是一組不等式,一組線性不等式。 那麼不等式的圖形又是怎樣的呢? 我們先來考慮一下不等式的幾何意義。 不等式該怎樣做圖? 我們還是以剛纔煤電油的例子裏邊的第一個約束,煤的約束爲例。 煤的約束9X1加4X2小於等於360。 這個不等式當它取等號的時候, 它表示一條直線,也就是9X1加4X2等於360。 這是一條直線,這條直線是可以做出來的。 我們知道用兩點可以定義直線, 那麼在這個直線表達式當中, 我們只要分別令X1等於0, 再令X2等於0, 則可以相應得到另一個變量的值。 那麼我們就可以得到過這個直線過的兩個點, 比如說煤的約束, 它的直線,它取等式時的這條直線, 就是過0,90和40,這兩個點。 過這兩個點,就可以把煤的約束的取等式情況的這條直線做出來。 那麼這個不等式,它又是一個什麼幾何意義呢? 我們有初等數學的知識,已經知道, 它表示的是以這條直線爲取等式的這條直線, 爲邊界的一個半平面, 那麼這條直線就是它的這個半平面的邊界, 不是這半側就是那半側, 那究竟是哪半側怎樣確定呢? 我們可以用一個點代入的方法, 也就是說,我們把這個直線, 邊界直線,它的某一側的一個具體點, 比如圓點,代入, 代入這個不等式,看是否成立, 比如我們把圓點00,代入這個不等式, 的左邊等於0,滿足小於360, 也就是說,這個圓點00, 是滿足這個不等式的, 這就說明,這個圓點所在的那半平面, 就是該不等式所表示的區域。 好,我們經過上述的分析, 便可知道如何做一個線性不等式的圖形, 它的方法很簡單,就是首先, 做該不等式取等號時的那條邊界直線, 然後再把這條邊界直線, 某一側的一個點,代入不等式, 看是否滿足,滿足的點所在的那半側區域, 就是這個不等式的圖形。 分析了不等式的做圖, 我們就可以接下來做出資源約束的圖形了。 仍以1.1爲例, 它的約束是沒電郵的資源約束和非賦約束組成, 非賦約束已經做出是第一象限, 那麼接下來我們把資源約束, 這些不等式的圖形也可以做出來, 仍以第1個約束沒的約束爲例, 剛纔已經分析過, 這個約束的取等號時的那條邊界直線, 是過0,90和40兩點, 我們可以先把這條邊界直線做出來, 然後把這邊界直線的某一側, 它下半側的一個點,比如00, 帶入不等式,發現滿足, 所以原點所在的那半平面, 就是這個不等式的圖形, 也就是說這個邊界直線下半側的區域, 同理我們可以做出電和郵, 兩個資源約束的圖形, 其中電的這條邊界直線很容易看出, 當取x1和x2分別爲0時, 它們相應的另一個點都可以得到, 很容易看出這條直線, 是過0,40和50兩個點, 我們就可以先把它的邊界直線做出來, 然後再把00帶入這個不等式, 發現也是滿足的, 於是這個不等式所表示的區域, 也是這條直線的原點所在的那下半側區域, 同理可以做出第三個約束, 郵的資源約束的圖形, 我們現在所有的約束的圖形都已經做完了, 那麼我們的最終的可行域, 也就是整個約束的圖形, 是哪一部分呢? 我們知道根據約束的含義, 決策變量應該滿足所有的約束, 也就是說應該是, 這些所有約束範圍的公共區域, 就是決策變量的取之範圍, 因此我們這所有約束的圖形做完之後, 他們的公共部分, 他們的交集就是模型的約束的圖形, 如圖所示,圖中陰影線部分, 就是這個模型的可行域, 可行域就是約束的圖形, 它也是可行解的集合, 可行域中每一個點表示一個可行的方案, 因爲它是滿足所有約束的, 所以它是一個可行的生產方案, 我們現在已經把約束的圖形做出來了, 也就是所有可行解的集合已經界定了, 接下來我們還要在這所有可行解當中, 可行的點當中, 尋找一個最優的點,最優的解, 也就是最優的生產方案, 那麼如何在這個區域的這麼多點中, 這麼多的方案中來搜尋最優方案呢? 拿什麼作爲搜尋最優方案的標準, 衡量的準繩呢? 我們說所有可行方案都是爲了 能夠獲取我們的目的和效益, 每個方案對應一個相應的收益, 我們就要從當中選擇 收益最優的那個方案, 因此我們評價的標準就是誰能使我們目標 函數達最大, 誰就是我們的最優方案, 因此接下來我們要用目標來搜尋最優方案, 圖解法的第二步就是做目標的圖形, 目標是一個什麼樣的圖形呢? 我們已經知道目標函數 它的一般式是z等於c1x1 加上一直到cnxn, 這是一個線性表達式, 只要z給一個具體值, 這便是一個具體的直線, 在二維問題它就是一個直線, 那麼我們由於z取不同的值表示不同的直線, 而我們是要求是z最大的那個相應的解, 因此我們在做圖的過程中 給z一個值做出的一條直線, 我們用虛線來表示, 因爲我們是要做不止一條相應的不同z值的直線, 那麼爲什麼要做不止一條呢? 究竟做幾條呢? 我們已經給出具體方法是 認給這兩個不同的值做出相應的兩條直線, 用虛線來表示, 那麼爲什麼要做兩條呢? 我們下面仍以立1.1爲例, 立1.1剛纔已經做出了它的可行域, 也就是約束的圖形, 接下來來看它的目標, 立1.1它的目標是z等於7x1加12x2, 按照剛纔的方法, 我們分別令z取兩個不同的值, 比如取z分別等於84和168, 那麼這樣便可做出相應的兩條不同的直線, 如圖所示, 我們看到這兩條直線分別是 相應於z等於84 和z等於168 的兩條目標的直線, 我們爲什麼做兩條的原因就是 可以看出當z由84變爲168時, 這個直線的位置是向哪個方向移動, 這道題已經看到當z增大的時候, 由84變爲168增大的時候, 直線是向右上方移動的, 這就是我們做兩條的目的, 因爲如果只做一條, 並不能看出z增大時向哪邊移, 如果做多於兩條是沒有必要的, 兩條就可以看出, 我們這一個步驟做目標的圖形, 就是做兩條不同z值的目標的直線, 大家已經看到這兩條直線是平行的, 因爲它們的斜率是相同的, 只是節矩不同, 我們主要是看出當z增大時, 它向哪個方向移, 就是要搜尋最優解, 我們就是要用這個方法, 找到在可行域中使z最大的那個解, 既然已經看出直線往哪個方向移的時候, 那麼我們就儘量使其向增大的方向移, 向使z優化的方向移, 在可行域的範圍內, 直到移到不能再移的時候爲止, 也就是最大限度的優化, 也就是在這個可行域中最大限度的z能達到多大, 我們直觀的已經看到, 當這條直線移到邊界處的時候, 這個時候就是在可行域的範圍內, 使z最大的水平了, 這是第二步做目標的圖形, 它的做完之後其實就已經看出最優點的位置了, 大概的位置了, 接下來第三步求出最優解, 剛纔已經看到, 只要將目標直線向使目標最優化的方向移, 直至可行域的邊界不能再移的時候爲止, 這個時候與可行域可能只有一個交點, 也可以形象的說是一個切點, 這個點就是在可行域的範圍內, 使z最大的點, 那麼我把它記作x, 它就是最優解了, 那麼以沒電油的例子, 它的最優目標直線如圖所示, 這時最優目標直線與可行域有一個交點, 這個交點就是在可行域的範圍內, 使z最大的點, 記作x,它就是最優解, 那麼這個解雖然位置找到了, 但是它的座標究竟是多少呢? 也就是具體解的得數到底是幾呢? 我們還需要計算一下, 不過這個計算也是很簡單的, 因爲如圖所示, 這個x星是兩個約束直線的交點, 在這道題當中是 後兩個資源約束直線的交點, 我們只需要把這兩條約束 邊界直線把它的式子寫出來, 然後也就形成一個 二元一次的連立方程組, 這樣求解這個兩條約束直線的 二元一次連立方程組就可解得 這個交點的值了,經過計算, 這個沒電由這道題的x星, 也就是它的最優解,等於20和24, 那麼這個20和24分別表示什麼意思呢? 在圖形上表示這個點的橫座標和縱座標, 也就是x1和x2的取值, 在實際意義上就表示 假產品和已產品的計劃產量的最優取值, 那麼這個方案就是一個最優的生產方案。 好,我們到這裏, 已經以例1.1爲例, 把圖解法的步驟已經介紹完了, 我們稍加回顧一下,圖解法的步驟有三步, 首先做約束的圖形, 約束的圖形中先做非復約束, 再做資源約束,所有的約束的公共部分, 如陰影線所示,就是約束的圖形稱作可行域, 第二步, 做目標的圖形,給目標z任意兩個不同的值, 分別做出相應的兩條直線, 用虛線表示,只要能看出 當z增大的時候,或者說當z優化的時候, 是往哪邊移就可以了。 第三步,求出最優解,就是將目標直線 儘量向增大的方向移, 在可行域的範圍內移到最大限度的, 也就是使這個z最大限度優化的 可行域的點,那麼在這道題就是 邊界上的一個腳點,這個點就是最優解,記住x 星,然後求解交出這個點的 兩個約束直線的連立方程,便可解出 這個最優解的具體數值了。 那麼步驟介紹完的過程也是 沒電由這道例題求解的過程, 我們到這裏已經把這個例1.1呢, 已經具體求解了出來,我們把例1.1的 結果把它給出來,剛纔用圖解法, 解得x星等於20,24, 這個是最優解,我們把它代入目標函數, 目標函數是z等於7x1 加12x2,我們用7乘以 24,就得到這個最優解相應的 最優值,也就是z星,z星等於 428,z星稱作最優值, x星稱作最優解,最優解和 最優值的實際意義就是 當假產品安排20個單位, 以產品的產量安排24個單位時, 可獲得最大收入428, 好,我們這個沒電由的例子已經介紹 完了,下面我們用圖解法學過的 方法可以做一個練習,練習 就是用圖解法求解一個線性 規劃,大家看一下這道題,這道題我們首先 看一下它是不是兩個變量的問題,只有兩個變量 的問題,纔可以用圖解法求解, 那麼這個題是一個兩個變量的問題, 它是一個目標爲極小型, 約數爲大於等於約數和非負約數,那麼由圖解 法該怎樣求解呢,我們大家自己先考慮一下, 我們梳理一下求解的過程和步驟,步驟 首先要想清楚,第一步做什麼,第二步 什麼,第三步什麼,根據剛纔的學習方法 第一步是做約數的圖形,具體 來講,是要做非負約數的圖形, 然後再做資源約數的圖形,非負 約數的圖形很簡單,就是第一項線, 然後我們再分別做出兩個資源 約數的圖形,每個約數首先 做出它取等號時的邊界直線, 用兩點定直線的方法,分別令xc和 s2爲0,求得另一個座標點, 這樣就可以得到這個邊界直線過的兩個點, 那麼兩點連線就可以做出它們的圖形了, 這是第一個約數的圖形,這是第二個約數的圖形, 那麼這個圖形只是邊界直線, 我們還要判斷它們代表這個直線的 邊界直線的哪半側,我們只需把 原點00代入,分別把00代入 這兩個不等式發現都是不滿足的, 那麼說明原點00所在的那半平面 不是這兩個不等式的 表示的區域,也就是說這兩個不等式 它的區域是它的邊界直線 是和原點相反的另一個區域, 也就是上半側,所有的約數做完 做完之後,我們來求出它們的公共 部分交集,這道題的所有 約數的交集也就是可行域,是表示 由第一個約數的邊界和兩個 座標軸構成的右上部分 右上半區域是一個 無界的區域,可行域做出之後,接下來 我們再來做目標的圖形,做出 目標的圖形,也就是給出 不同的值,看出它向哪邊移 這道題是優化的方向,這道題因爲是 極小星,它優化的方向是它減小的方向 那麼很明顯看到這道題的最優目標 直線的位置,及其它所交出的最優解 X星的位置,找到X星的位置之後 最後求解,交出它的約數直線 或者像這樣簡單的這道題 直接就可以看出,它的座標是0.50 我們求出最優解以後,把最優解 0.50帶入目標Z的表達式 可以求出它相應的 最優值是3,Z星等於3 我們最後把結果,就是最優解和 最優值寫在一起,這就是這道題 結果的完整表示 好,我們通過又做了一道圖解法的 習題之後,我們對圖解法的方法 已經清楚了,而且我們也確實看到 由圖解法能夠總結一些線性規劃的 一些特性,那麼線性規劃的 解也好,它的約數域 可行域,以及它的解的位置等等 都有哪些特性呢?首先我們看到 這兩道題的可行域的形狀 有一個共同的特點,它們都是由 一些直線段組成的一個多邊形 直線段組成,大家想直線段組成 爲什麼是直線段?因爲我們現在是 線性規劃,它的每個約數表達式都是 線性的表達式,所以它的約數是由 一些直線段組成的多邊形 第二個例子儘管是個無界的區域,它也是一個 有界的部分也是一個直線段圍成的一個 多邊形的形狀,還有什麼特點呢? 還有就是最優解的位置有什麼特點? 無論是上一個例子還是這道練習題,最優解 X星的位置都是在可行域的邊界 角點處獲得,這是爲什麼呢?也很容易 進行分析,因爲只有 到邊界的位置才能使目標 最大限度的優化,於是我們對這些 直觀的一些現象可以進行一些 總結,比如剛纔我們已經 分析過的兩個特點,我們可以先 總結一下線性規劃的可行域是一個什麼 形狀?剛纔已經說過了在二維的情況 因爲我們圖解法只能解二維的問題 它是一個由直線段圍成的一個多邊形 最優解在什麼位置獲得?剛纔已經看到了,是在可行域 也就是這個多邊形的邊界處 剛纔兩道題都是在邊界的一個角點處獲得 我們回到第一個問題,多邊形 是它的可行域的形狀,不僅如此 而且還是一個凸形的多邊形,什麼叫凸形的 多邊形呢?直觀上來看就是處處向外 凸出的向外鼓的這種形狀的多邊形 我們直觀的想象,假若一個圖形是由直線段 圍成的一個多邊形,它也有可能是凹進去一塊的 那這個就不是凸形的多邊形,我們線性規劃的可行域 由前面的例子我們看到都是一個凸形的多邊形 最有解的位置就是在邊界,而且可以在某個 頂點獲得,接下來我們就 把剛纔分析的由圖解法得到的線性規劃 解的一些特性,把它再總結一下 第一個得到的結論是線性規劃的可行域 或者稱爲約束集,是一個凸多面體 剛纔是二維的情況,說是凸多邊形 那麼對於一般的情況,我們 把它叫做凸多面體 它的每個面是由平面,是一個平面 這個多面體是由平面圍成的,而且是凸形的 一個集合,關於凸 集的概念和凸多面體的概念,這裏可以稍微的 說一下,凸多面體是凸集的一種 那麼什麼叫凸集呢?直觀上來解釋一下就是 這個集合中任兩點的連線仍屬此集 那麼比如說,我們用幾個圖形來 看一下,下面四個圖形中,我們看一下 哪些是凸集,哪些圖形不是 凸集呢?由剛纔的直觀描述 凸集必須滿足,集中任兩點的連線 仍屬此集,我們看到這四個圖形中 前兩個圖形是顯然是滿足的 也就是圓和多邊形 是凸集,但是後兩個圖形 它並不能做到所有任意兩點的連線 都仍屬此集,都全部仍屬此集 因此後兩個圖形不是凸集,那麼也可以說 凸集是直觀的描述 是處處向外凸的,向外鼓的,而且是連通的區域 像第四個圖形中間挖了一個窟窿,這樣的不是凸集 因爲它不能做到任兩點的連線 仍屬此集,在凸集的概念中 有一個相關概念,叫做集點 集點又稱頂點或角點 什麼叫凸集的集點呢? 就是它屬於此集,但不能表示成集中某二點連線的內點 這樣的點 我們用前兩個圖形爲例來說明 在第一個圓這個集合 圓盤這個集合 這個圖形中的哪些點是它的集點呢? 那麼在第二個圖形多邊形,這個圖形中 又有哪些點是它的集點呢? 我們根據它的定義的描述可知 這個集點必須是不能表示成集中某二點連線的內點 那麼由這個定義判斷 在這個多邊形這個圖形中 只有它的這幾個角點也稱頂點滿足 所以這個凸集的集點對於多邊形來講 它的邊界上的所有點都是它的集點 我們由圖解法得到 線性規劃解的第二個性質是最優解的位置 線性規劃的最優解若存在的話 一定能在可行域的頂點處獲得 剛纔已經分析過了 因爲由圖解法可知,只有當目標直線平移到邊界時 才能使目標Z達到最大限度的優化 這個最優解的位置的性質 有什麼重要的意義呢 我們知道既然尋優的工作 是在整個可行域中進行 那麼整個可行域的無窮多個點 都是尋優搜尋的對象 這樣工作量很大無窮多個點 但是現在我們有了這個結論 最優解它必能在可行域的腳點獲得 內部點是不可能成爲最優解的 因此我們只需在腳點中尋優就可以了 也就是說尋優的工作 可以由無限變爲有限 這個重要的性質使得我們爲線性規劃設計一般的算法成爲可能 事實上 這也是線性規劃的一般算法 也就是從腳點中尋優 接下來我們再來總結一下 由圖解法得到線性規劃解的幾種情形 第一種情形是唯一最優解 這種情形是最常見的 比如前面兩個例子都是這種情況 它的特點是可行域是有界的 並且最優目標直線在 一個腳點的位置達到 那麼這時這個腳點和最優目標直線相切的 這個腳點就是唯一的最優解 第二種情況稱作多重最優解 這種情況是目標直線的斜率和 某條邊界直線的斜率相同 那麼它又是向這個方向移 這時移到邊界處的時候是和 整條邊界線段重合 這條邊界線段的兩個頂點之間的所有點都是最優解 它們具有同樣的目標直 第三種情況稱作無可行解 我們知道約束級是 所有約束的交集公共部分 那麼假若一部分約束的圖形和另一部分約束的圖形 沒有交集交集爲空 那麼這時就是無可行解的情況 第四種情況稱作無有限最優解 也稱爲無界解 這種情況的特徵是可行於無界 並且目標直線向無界的方向移 那麼它將趨於無窮大永遠打不住頭 我們在實際的問題建模求解過程中 假如出現後兩種情況 也就是無可行解和無有限最優解的情況 需要檢查模型建立 是否有問題 也就是說 約束爲什麼不相容是否需要調整 是否需要檢查是否有不符合實際的情況 那麼對於無界的情況也要檢查 是否少寫了約束 因此我們在我們後面的討論中 主要遇到的情況是前兩種情況 以上我們就是對基於圖解法 對線性規劃解的解的一些特性 進行了討論 最優解的位置和解的幾種情形 最後我們把本節內容 進行回顧與思考 我們歸納爲了幾個問題 第一 線性規劃解決的對象是一類什麼樣的問題 第二 線性規劃的模型構成的三要素爲何 第三 線性規劃模型的一般式 包括分量式和矩陣式是什麼 圖解法的一般步驟是什麼 由圖解法得到線性規劃 哪些性質 關於這一節 線性規劃模型與圖解法就介紹到這裏