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

同學們大家好,我們在續論中介紹了運籌學是一門以定量、方法和技術爲管理決策提供科學依據的學科 它具有多個分支的屬性,核心思想是自由化 那麼在運籌學的多個分支中,有一些具有更加基礎和代表性 我們接下來將介紹的第一章線性規劃就是這樣的一個分支 在第一章線性規劃中,我們將給大家介紹五部分內容 它們分別是 第一節線性規劃的模型與圖解法 第二節單純行法 第三節隊友問題與靈敏度分析 第四節線性整數規劃 第五節運輸問題 第一節介紹線性規劃的模型與圖解法 在這一節中,我們主要介紹兩部分內容 一個是線性規劃的問題及其數學模型 另一部分是模型的圖解法 我們先來說一下線性規劃的問題是一類實際中的怎樣一類問題 大家知道,在生產管理和經營活動中 經常需要解決如何合理的利用有限的資源 以得到最大效益的問題 下面舉一個簡單的例子 例1.1 某工廠可生產甲乙兩種產品 需消耗煤電油三種資源 現將有關數據列表如下 由這張表可以看到 爲了生產甲乙產品 需要用到的煤電油三種資源都是有限的 煤的資源360個單位 電的資源200個單位 油的資源300個單位 甲乙產品對這三種資源的單號 也就是生產一件甲乙產品 需要消耗的三種資源的數量 分別是943和450 甲乙產品生產出來以後 在市場上可銷售的單位價格 分別是7和12 這個問題它要求什麼呢 它要求的是 市擬定使總收入最大的生產計劃方案 那麼什麼是生產計劃方案呢 因爲這個問題很簡單 大家不難理解 它主要就是求甲乙兩種產品 各生產多少 可以使總收入最大 這個問題是一個很簡單的問題 也是線性規劃 即便是這樣簡單的問題 直接口答 直觀上來看 也很難說出準確的答案 因此需要有一種一般的方法 我們介紹的就是線性規劃的方法 來解決這個問題 方法的第一步 首先是要建立問題的數學模型 我們稱作線性規劃模型 那麼怎樣把這樣的一個問題 轉換成一個線性規劃的模型呢 也就是說模型怎樣建立呢 我們首先要了解模型的結構 線性規劃的模型 由三要素構成 第一要素 稱作決策變量 是指需決策的量 也就是通俗所說的帶球的未知數 第二要素 稱作目標函數 是指需優化的量 即預達的目標 它可以用決策變量的表達式來表示 我們這裏所說的優化 在實際中通俗的理解就是 極大化或者極小化 第三個要素 是勻數條件 它是指爲了實現優化目標 需要受到的限制 也是用決策變量的表達式來表示 通常用等式或者不等式來表示 下面我們將用剛纔的例1.1 來看一下它的模型的三要素各是什麼 我們先來分析一下 因爲這個題目很簡單 大家很容易可以分析出來 它要求的是什麼呢 這個問題要求生產計劃方案 剛纔我們已經分析了 這個生產計劃方案 就是指甲乙兩種產品的計劃產量 那麼這個就是決策變量 需決策的量 我們就用未知數來表示 假設計爲X1和X2 表示甲乙產量 這道題的第二要素 就是目標函數是什麼呢 由這個問題的最後一句話的要求可知 它要求使總收入最大的生產計劃方案 那麼它的目標就是使總收入集大化 因此這道題的目標就是總收入 目標函數就是總收入的表達式 我們假如把X1和X2來表示了甲乙產量 那麼總收入的表達式 就可以根據表格的數據得到 因爲在表格裏給出了單位產品的價格7和12 那麼單價乘以數量應該就是收入 所以這個表達式 這道題的總收入的表達式應該是7X1加上12X2 當然它還要表示它是追求集大化 這道題的第三要素 也就是約束條件是什麼呢 很明顯約束主要來自資源限量的約束 煤電油三種資源都是有限量的 那麼怎樣表示這個限量的約束呢 我們以煤爲例 因爲甲乙產品生產煤的單號數據是已知的 甲產品和乙產品生產煤所需的資源單號 分別是9和4 那麼生產這兩種產品的總的對煤的消耗量就是9X1加4X2 這個總的消耗量要小於等於煤的資源限量360 同理可以分析電和油的約束表達式 那麼除了資源限量的約束之外 決策變量X1和X2也就是甲乙的產量 它的取值範圍應該是非負的範圍 經過上述的分析 我們就可以把這道題的模型三要素把它列出來 根據剛纔的分析 決策變量就是甲乙產品的計劃產量 表示爲X1和X2 目標函數是總收入 我們用字母Z來表示目標函數 在這道題就是總收入 那麼這道題的Z就等於7X1加12X2 爲了體現它是極大化 在Z的前面冠一個極大號MAX 那麼假如問題是極小化的問題呢 我們就要在目標Z的前面冠以極小號MIN 這道題的第三要素約束條件 來自資源煤電油限量的約束 和產量取值爲非負的約束 我們剛纔已經分析了可以用一組不等式來表示 這組不等式的第一個約束 這組不等式的第一個不等式是煤的約束 剛纔已經分析過了 第二個不等式是電的約束 第三個不等式是煤的資源約束 最後是非負約束 把這些約束在它的左側用一個大括號 有的時候用一個大括號把它括一下 這個呢可以更加清楚一些 表示這些約束是一個整體 在大括號的左側有一個符號記號 S.T. 它表示約束的意思 那麼我們把這道題模型的三要素已經分析完畢 下面就可以把模型表示出來了 模型的表示仍然是按三要素的順序 首先要說明變量設置和目標的 包括這個決策變量和目標的字母 用什麼字母表示 然後接下來呢是模型的目標和約束的表達式的構成 我們看到由目標和約束表達式組成的 這就是一個線性規劃的模型 這是煤電油的問題 線性規劃的模型的結構 它的構成的三要素 我們已經介紹完了 大家看到以這道題爲例 在模型的表達式中 無論是目標還是約束 它的所有表達式都是決策變量的線性表達式 所以我們把這樣的優化問題稱作線性規劃 如果我們實際問題的模型中出現有 如這樣所示的非線性表達式的話 那麼則這個規劃問題就不屬於線性規劃 我們本章介紹的對象就是線性規劃 接下來我們再來看一個問題 例1.2 某市今年要興建大量住宅 已知有三種住宅體系可以大量興建 例1.3 各體系資源用量及今年供應量如下表所示 在這個數據表中給出了 今年某市需要興建住宅可供選擇的住宅體系的類型 包括三種 第一是磚混住宅 第二碧板住宅 第三種大磨住宅 這張表中還給出了資源的種類和資源的限量 資源分爲造價 鋼材水泥磚人工 假如我們只列了這幾種資源主要的資源 那麼在這個表格的中間部分 給出了三種住宅對這五種資源的單號數據 比如說磚混住宅 它對五種資源的單號數據 就是建造一單位磚混住宅需要消耗的五種資源的數量 如表中第一行所示 同理表中第二三兩行分別表示碧板和大磨住宅對五種資源的單號 最後一行給出了是五種資源的限量 在這個數據前提條件下 我們的問題是什麼呢 是要求在充分利用各種資源前提條件下 追求使建造住宅的總面積最大化 爲了這個面積最大化的目標求一個建造方案 這個問題我們對它進行一下分析 發現這個問題它和剛纔煤電油的問題 雖然內容不盡相同 但是它們的共同點都是在有限的資源條件下 如何合理的計劃來追求效益極大化的問題 煤電油那道題是追求甲乙產品的總收入極大化 而這道題是追求總的建築面積極大化 他們要求的是一個決策方案 要決策的是什麼呢 要優化的是什麼呢 又受到什麼限制呢 那麼這些都在題目中可以分析出來 這個問題既然也是一個在有限的資源條件下 如何合理計劃而獲取資源 而獲取效益極大化的問題 因此它也是一個我們線性規劃的可以解決的問題 下面我們來分析問題的三要素 模型的三要素 第一要素是決策變量 也就是這個問題它要決策什麼 求什麼呢 剛纔已經說過是求建造方案 那什麼是建造方案呢 我們有提議可知 就是在這三種住宅類型中 要決策各建造多少面積 能夠使總面積極大化 因爲每一種建造類型 它都要涉及到資源的約束 怎麼在資源約束的條件下 合理的計劃能使得面積極大化呢 那麼我們要求的就是三種住宅的面積 各建造多少 這是決策變量 我們假設分別計爲X1,X2和X3 也就是這三種住宅的面積 我們表示爲X1,X2,X3 我們爲了建模的第二要素 是目標函數 剛纔已經分析過 我們這個問題的目標是使總面積極大化 那麼總面積怎麼表示出來呢 由決策變量的設置 可知三種住宅的面積之和 也就是X1,X2,X3 就是總面積 這是優化目標 那麼第三要素是約束條件 這道題的約束也是很清楚的 就是受到五種資源的約束 這五種資源都是有限量的 那麼我們根據表中的數據 比如以造價爲例 造價這種資源 它的資源單號數據已知 那麼它的限量也已知 我們爲了建造三種住宅 需要消耗的造價的實際總消耗量 就是105X1 加上135X2 加上120X3 這個是它的實際造價的實際造價數量 那麼這個實際消耗的數量不能超過 也就是小於等於資源的限量 這裏要注意的一個問題點是 資源的限量是用千元做單位 而我們的單號數據是以元做單位 以造價爲例 那麼在列表達式的時候 要把量綱統一 好 經過分析 我們這個問題的建模的三要素已經清楚了 下面我們就把它的模型表示出來 第一步是決策變量和目標變量的說明和設置 設今年計劃修建磚混地板大模住宅 各爲X1,X2,X3 這表示總面積 則本問題的數學模型爲 目標函數是極大化Z等於X1加X2加X3 這個就是總面積表達式極大化 約束條件 前五個表達式是五種資源 五種資源的限量約束 我們看到由於量綱 它的這個爲了不等是兩端量綱的統一 因此呢 它把這個不等是左邊的單號數據也統一成以千元做單位了 以第一個約束爲例 最後一個一部分表達式呢 是非負約束 好 我們看到這個模型 它的 如果求解之後 可以解得什麼東西呢 它如果求解之後解出的解 使目標最大的這個解 它應該是一種建造方案 它求出的是磚混壁板大模各建造多少面積 這些面積之和就是在這些資源 約束條件下 所能夠達到的最大的建造面積 這個模型曾經在前蘇聯的尼古拉也夫斯克城 住宅興建計劃中實際採用了 當然實際中變量的個數和約束的個數會比這個更多一些 好 我們以上舉了兩道例題 都是關於線性規劃的問題和建立模型的 那麼在這個基礎之上 大家可以自己做一些練習題 能夠熟練的把建模的方法掌握 下面有一個同學自己的練習題 我們一起來看一下 某畜牧場每日要爲所飼養的牲畜購買飼料 以使其獲取ABCD四種養分 市場上可選擇的飼料有M和N兩種 有關數據如下表 我們看到在這個數據表格當中給出了的數據是 市場上可供選擇的M和N兩種飼料 它的售價 以及呢 我們每天爲所飼養的美頭 牲畜所需要的四種養分的名稱 記作ABCD 那麼這個數據表的中間部分 給出了兩種飼料 含有每種養分的百分比 比如說第一行給出了M飼料含有ABCD四種養分的比例 成分比例 第二行給出了N飼料 當中含有四種養分的比例 最後一行給出的是每天美頭牲畜需要四種養分的最低數量 我們現在的問題是要決定購買M和N兩種飼料各多少公斤 可使總支出的費用爲最少 好 這個問題呢 我們已經把它看了一遍 我們稍加分析一下 大家一起自己來思考一下 這個問題 它是不是一個線性規劃類型的問題 如果是 那麼它應該是一種在有限的資源條件下 如何合理的安排計劃 而使得總效益 某種總效益極大化的問題 經過分析 我們不難看到 這個問題 它的目標是使購買飼料的總花費極小化 因此 它也是一種優化問題 和前兩道題相比 前兩道題是極大化問題 而這道題呢 是個極小化問題 我們前面說過優化問題 它在實際中的體現 主要的基本類型就是極大化或極小化 因此 這個問題極小化 它也是一個優化問題 它是不是在有限的資源條件下 來合理安排計劃的問題呢 那麼它又要安排什麼計劃呢 需決策什麼呢 這個在問題已經說得很清楚了 要決定購買M與N飼料各多少 這個就是它的決策 要決策的變量 各買多少數量 那麼它受到的約束是什麼呢 受到的約束 我們經過分析也可知道 就是每頭牲畜 它所需要的 這個四種養分的數量 那麼你購買的飼料 每天購買的飼料 要保證它所需的養分 要達到最低的要求 好 大家經過分析了之後呢 大家自己可以想一下 這個問題的模型 該怎樣建立呢 建模就是三要素 你要寫出模型 就是把三要素分別寫出 第一你要考慮 決策變量設爲什麼 第二要考慮 目標函數怎樣表示 第三要考慮 約束條件又有哪些 怎樣表示 好 我相信大家呢 已經能夠把這個問題呢 這個正確的回答出來 那麼我們呢 把這個答案 大家一起來對照一下 剛纔已經說過 這道題的決策變量 是購買MN飼料的數量 各計爲X1和X2 這道題的目標 是使總購買費用極小化 因爲MN飼料的單價是一致的 單價乘以數量就是花費 兩種飼料的花費之和 就是總花費 總花費極小化 這就是目標 那麼約束條件是什麼呢 是你購買的這個數量 它的養分必須要符合 飼養的對養分的需求 最低要求的數量 那麼我們看到這個 約束條件這道題 是一個大於等於的類型 第一個不等式 因爲後面那種資料 它不含有A養分 所以它的含量是零 這個表示的是購買飼料中 A養分的數量 要不低於 不低於就是大於等於 0.4 同理下面就是BCD養分 的需求的約束 最後呢 因爲這個決策變量是購買數量 所以呢 是XCS要大於等於零 好這道題的模型呢 我們就建立完畢了 那麼我們看到 在剛纔接觸的幾個例子中 既有極大型 也有極小型 它的約束呢 既有大於等於 也有小於等於 不管是什麼形式 它的模型 都是由三要素構成 我們爲了進一步的研究 的需要 接下來 把剛纔實例當中的模型 進行一般化 也就是給出線性規劃模型的一般形式 以極大型小於等於約束爲例 它的決策變量 目標函數和約束條件 這三要素 用一般式來表示 可以表示成這樣 首先決策變量 我們假設一共有N個變量 分別計爲X1到XN 目標函數 現在因爲是以極大化爲例 所以它一般是計作 MAXZ等於 C1X1 加上一直到CNXN 這個C 這個X就是決策變量 這個C呢 就是決策變量 在目標中的係數 那麼在剛纔的例子中 它往往表示比如單價等等 第三部分約束條件 我們假設一共有M個約束 那麼第一個約束 計作A11X1 加上一直到A1NXN 小於等於B1 第M個約束計作 A11X1 加上一直到A1NXN 小於等於B1 這裏的Aij 表示資源單號係數 比如說第一列 相應於X1的這一列 就表示X1相應的 這個決策變量相應的 比如說那種產品 它的資源單號 那麼在這個 約束的不等式的右端 B1到BM 表示這M種 M個約束資源約束的資源限量 比如煤電油那道題裏邊的 煤電油的限量 在約束的最下面一行 X1到XN大於等於零 是非負約束 這個就是我們線性規劃 模型的一般式 這個一般式的表達式 大家看一下 無論是目標還是約束 都是用變量的線性表達式 來表示的 它的約束部分 Aij每個係數是雙下標Aij 前一個下標i 表示這個Aij的所在的行 後一個下標j 表示這個Aij所在的列 這種表示的形式 是和線性代數中 表示線性方程組和矩陣的 習慣的表達形式是一致的 那麼這個模型的一般式 我們在研究的過程中 有的時候希望它表示的更加簡潔 於是我們有的時候 也可以把它表示爲 向量和矩陣的形式 這個表達式是一個分量的形式 那麼如果我們把若干個分量 把它記爲一個向量 這樣的話就可以使得 表達的總的這個形式更加簡潔 比如說我們決策變量 X1到Xn 可以把它記作一個X 也就是以這些決策變量爲分量 組成一個決策向量 目標函數的係數 這些C我們也可以把它 記爲一個向量 記作C加入和那個決策向量 X相乘 而約束條件 約束條件的左邊的這些Aij m行和n列 這些Aij也可以構成一個 m乘n的一個矩陣 那麼這個不等式的左邊的 這些m個式子 也可以看作是係數矩陣 假設記爲A和決策 變量的向量 X的乘積 而約束的右端向 這個B呢 B1到Bm這些分量 也可以記爲 一個向量記號B 於是呢 我們就可以 在這種 表示下 我們就可以把 剛纔的模型的分量式 表示成矩陣式 大家請看 矩陣式的目標是 集大化Z等於CX 約束式AX小於等於B 和X大於等於0 這裏的0也是向量0 這個大寫的X就表示 剛纔那n個決策變量 做分量組成的向量 那麼這個向量 括號外面那個t次方 表示轉之的意思 這個X是個列向量 那麼這個模型的 目標的係數C 表示的就是 剛纔的目標中的係數 C1到Cn組成的向量 A就是一個m乘n的矩陣 約束中的係數所組成 而B呢 表示約束的右端向 資源限制係數組成的向量 它一般表示資源的限量 好 我們以後在研究的時候 往往需要用到 模型的一般式 有的時候呢 需要用到矩陣的形式 因爲它更加簡潔 回顧剛纔的第一個例子 沒電油的例子 在這個例子當中 它的這些個 模型一般式中相應的 記號都是什麼呢 我們來回顧一下 決策變量的向量 X表示由X1和X2組成的向量 分別是甲乙的產量 C表示產品的價格 在目標中的係數 7和12分別是甲乙的價格 一般式中的B 在沒電油的例子中 就是三種資源的限制向量 係數矩陣A表示資源單號數據 甲乙的資源單號分別是 我們根據這些係數 在實際中通常表示的含義 有的時候我們有一些 比較通俗的稱呼 剛纔已經說了 X稱爲決策變量的向量 模型中的C表示價格係數向量 因爲它在剛纔的例子中 大家看到一般 它是表示一種單位效應 比如價格 係數矩陣A稱爲技術係數矩陣 而B呢 右端向B稱爲資源限制向量 那麼這裏的A 爲什麼稱作技術係數矩陣呢 因爲A中的列表示的是資源單號 而資源單號在不同的企業中 它的消耗的水平和數量是可以不同的 反映了技術的水平 所以我們俗稱它是技術係數矩陣 好 到這裏 我們已經把線性規劃的模型 以及它的一般式進行了介紹 在模型建立之後 我們就可以繼續研究模型的求解了