1、運 籌 學( Operations Research )一、古代樸素的運籌學思想一、古代樸素的運籌學思想例如：田忌賽馬例如：田忌賽馬二、運籌學的起源二、運籌學的起源國外國外英文原名英文原名 Operations Research 簡稱簡稱“O.R.”直譯為：運用研究或作業研究直譯為：運用研究或作業研究正式出現于正式出現于19381938年年7 7月英國一份關于防空作戰月英國一份關于防空作戰系統運行的研究報告中系統運行的研究報告中緒緒 論論 國內國內19561956年成立第一個運籌學小組年成立第一個運籌學小組19571957年從年從“夫運籌策帷幄之中，決勝于千里之外夫運籌策帷幄之中，決勝于千里之

2、外”中中摘取摘取“運籌運籌”二字，將二字，將O.R.正式翻譯為正式翻譯為“運籌學運籌學”三、運籌學的定義三、運籌學的定義研究工具：數學，計算機科學及其他相關科學研究工具：數學，計算機科學及其他相關科學研究目的：對有限資源進行合理規劃、使用，并提供研究目的：對有限資源進行合理規劃、使用，并提供 優化決策方案。優化決策方案。研究對象：復雜系統的組織和管理研究對象：復雜系統的組織和管理參考參考大英百科全書大英百科全書、辭海辭海、中國企業管理百科全書中國企業管理百科全書等。等。四、運籌學研究的基本特點四、運籌學研究的基本特點 系統的整體優化系統的整體優化 多學科的配合多學科的配合 模型方法的應用模型方

3、法的應用五、運籌學研究的基本步驟五、運籌學研究的基本步驟 分析與表述問題分析與表述問題 建立數學模型建立數學模型 對問題求解對問題求解 對模型和模型導出的解進行檢驗對模型和模型導出的解進行檢驗 建立對解的有效控制建立對解的有效控制 方案的實施方案的實施第一章第一章 線性規劃及單純形法線性規劃及單純形法Linear Programming and Simplex Methodxa此為無約束的極值問題此為無約束的極值問題1.1 一般線性規劃問題的數學模型一般線性規劃問題的數學模型1-1 1-1 問題的提出問題的提出例例1 1 用一塊邊長為用一塊邊長為a的正方形鐵皮做一個無蓋長方體容的正方形鐵皮做一

4、個無蓋長方體容器，應如何裁剪可使做成的容器的容積最大？器，應如何裁剪可使做成的容器的容積最大？ 例例2 2 常山機器廠生產常山機器廠生產 I I、IIII 兩型產品。這兩型兩型產品。這兩型產品都分別要在產品都分別要在A A、B B、C C三種不同設備上加工。按三種不同設備上加工。按工藝規定，生產每件產品工藝規定，生產每件產品I I需占用各設備分別為需占用各設備分別為2h2h、4h4h、0h0h，生產每件產品，生產每件產品IIII需占用各設備分別為需占用各設備分別為2h2h、0h0h、5h5h。己知各設備計劃期內用于生產這兩種產。己知各設備計劃期內用于生產這兩種產品的能力分別為品的能力分別為12

5、h12h、16h16h、15h15h，又知每生產一件，又知每生產一件產品產品I I企業能獲利企業能獲利2 2元利潤，每生產一件產品元利潤，每生產一件產品IIII企企業能獲利業能獲利3 3元利潤，問該企業應安排生產兩種產品元利潤，問該企業應安排生產兩種產品各多少件，使總的利潤收入為最大。各多少件，使總的利潤收入為最大。1-2 1-2 線性規劃問題的數學模型線性規劃問題的數學模型原型原型模型模型數學模型數學模型提煉提煉數學工具數學工具1 1、原型原型：現實世界中人們關心、研究的實際對象。：現實世界中人們關心、研究的實際對象。 模型模型：將某一部分信息簡縮、提煉而構造的原型替代物。：將某一部分信息簡

6、縮、提煉而構造的原型替代物。 數學模型數學模型：對現實世界的一個特定對象，為達到一定目的，：對現實世界的一個特定對象，為達到一定目的，根據內在規律做出必要的簡化假設根據內在規律做出必要的簡化假設, ,并運用適當數學工具得到并運用適當數學工具得到的一個數學結構。的一個數學結構。3 3、規劃問題數學模型的三要素、規劃問題數學模型的三要素（2 2）目標函數目標函數：問題要達到的目標要求，表示為決策變量的：問題要達到的目標要求，表示為決策變量的函數。用函數。用 z= =f( (x1 1，x2 2，xn n) )表示。表示。（1 1）決策變量決策變量：決策者為實現規劃目標采取的方案、措施，：決策者為實現

7、規劃目標采取的方案、措施，是問題中要確定的未知量。用是問題中要確定的未知量。用x1 1，x2 2，xn n表示。表示。（3 3）約束條件約束條件：決策變量取值時受到的各種可用資源的限制，：決策變量取值時受到的各種可用資源的限制，表示為含決策變量的等式或不等式。表示為含決策變量的等式或不等式。2 2、規劃問題、規劃問題即求目標函數在若干約束條件下的最值。即求目標函數在若干約束條件下的最值。4 4、線性規劃問題（、線性規劃問題（Linear Programming）的數學模型）的數學模型（2 2）一般形式一般形式：（1 1）條件條件：決策變量為可控的連續變量，目標函數和約束條：決策變量為可控的連續

8、變量，目標函數和約束條件都是線性的。簡記為件都是線性的。簡記為“L.P.” max (或或 min) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn （=，）b1 a21x1+a22x2+a2nxn （=，） b2 am1x1+am2x2+amnxn（=，） bm x1 , x2, , xn0（3 3）其他形式其他形式：連加形式連加形式11max (min) z=( , ) (1,2,). . 0 (1,2, )njjjnijjijjc xa xbimstxjn 1-3 1-3 線性規劃問題的標準形式線性規劃問題的標準形式1 1、標準形式、標準形式11max z

9、= (1,2,). . 0 (1,2, ) 0(1,2,)njjjnijjijjic xa xbims txjnbimmax z= . . 0 0CXAXbstXb或或2 2、條件、條件目標函數求極大值目標函數求極大值約束條件全是等式（線性方程組）約束條件全是等式（線性方程組）決策變量全非負決策變量全非負右端常數全非負右端常數全非負3 3、標準化方法、標準化方法1min z=njjjc x（1）若目標函數求極小值，即）若目標函數求極小值，即則令則令 zz 轉化為轉化為11max z = -z = -()nnjjjjjjc xcx（2 2）若約束條件為不等式，）若約束條件為不等式，則依次引入松弛

10、變量或剩余變量（統稱為松弛變量），則依次引入松弛變量或剩余變量（統稱為松弛變量），轉化為等式約束條件。轉化為等式約束條件。注意注意：松弛變量在目標函數中系數全為：松弛變量在目標函數中系數全為0。約束為約束為不等式，減去松弛變量，化為等式約束條件；不等式，減去松弛變量，化為等式約束條件；約束為約束為不等式，加上松弛變量，化為等式約束條件。不等式，加上松弛變量，化為等式約束條件。多退少補多退少補例：例：max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0， x2 0 s.t.12345123142512345max 2300022 124 16 s.t. 5

11、 15, , , , 0zxxxxxxxxxxxxxxxxx標準化標準化 0jjjxxx 且jjjxxx（3 3）若決策變量）若決策變量xj0，則令，則令（4 4）若決策變量）若決策變量xj取值無限制，則令取值無限制，則令（5 5）若約束等式的右端常數）若約束等式的右端常數bi 0 0，則，則0jjxx，其中其中（“一分為二一分為二”）等式兩邊同時乘以等式兩邊同時乘以“-1”。例例3：將下列線性規劃模型化為標準形式。將下列線性規劃模型化為標準形式。123123123123123min2329324. .32360, 0, zxxxxxxxxxstxxxxxx 取值無限制例例4：在下述線性規劃問

12、題中，列出全部基、基解、：在下述線性規劃問題中，列出全部基、基解、基可行解，并指出最優解?；尚薪?，并指出最優解。12345123142512345max 2300022 124 16 s.t. 5 15, , , , 0zxxxxxxxxxxxxxxxxx解：系數矩陣為解：系數矩陣為12345 221 0 0400 1 005 0 0 1 P PP P PA若取基為若取基為 B=(P1, P2, P3),則基變量為則基變量為x1, x2, x3, 非基變量為非基變量為x4, x5令令x4=x5=0，代入約束方程組，代入約束方程組解得解得x1=4, x2=3, x3=-21231222124

13、16 5 15xxxxx從而得到一個基解從而得到一個基解 X=(4,3,-2,0,0) T這個基解不是基可行解！這個基解不是基可行解！該該 L.P. 共有共有8個基解。個基解。若取基為若取基為 B=(P3, P4, P5)=I3,則基變量為則基變量為x3, x4, x5, 非基變量為非基變量為x1, x2令令x1=x2=0，代入約束方程組，代入約束方程組3451216 15xxx從而得到一個基解從而得到一個基解 X=(0,0,12,16,15) T這個基解是基可行解！這個基解是基可行解！（注意：選擇單位矩陣為基可以較方便的求出一個基可行解。）（注意：選擇單位矩陣為基可以較方便的求出一個基可行解

14、。）同理可得其他基解同理可得其他基解. .基基B基解基解是基是基可行可行解？解？目標目標函數函數值值x1x2x3x4x5P1P2P34 43 3-2-20 00 0否否1717P1P2P43 33 30 04 40 0是是1515P1P2P54 42 20 00 05 5是是1414P1P3P54 40 04 40 01515是是8 8P1P4P56 60 00 0-8-81515否否1212P2P3P40 03 36 616160 0是是9 9P2P4P50 06 60 01616-15-15否否1818P3P4P50 00 0121216161515是是0 0（最優基）（最優基）（最優解）

15、（最優解）（最優目標函數值）（最優目標函數值）4 4、線性規劃問題各種解之間的關系、線性規劃問題各種解之間的關系約束方程的約束方程的解空間解空間基解基解可行解可行解非可行解非可行解基可基可行解行解最優解最優解1.2 1.2 圖解法圖解法1 1、適用范圍：僅含兩個決策變量的、適用范圍：僅含兩個決策變量的 L.P.2、步驟：、步驟：（1 1）作平面直角坐標系，標上刻度；）作平面直角坐標系，標上刻度；（2 2）作出約束方程所在直線，確定可行域；）作出約束方程所在直線，確定可行域；（3 3）作出一組目標函數的等值線，判定優化方向；）作出一組目標函數的等值線，判定優化方向；（4 4）沿優化方向移動，確定

16、與可行域相切的點，確定）沿優化方向移動，確定與可行域相切的點，確定最優解，并計算最優目標函數值。最優解，并計算最優目標函數值。例：例： 用圖解法求解下列線性規劃問題。用圖解法求解下列線性規劃問題。（1） max z=2x1+3x2 s.t. 2x1+2x2 12 - 4x1 16 - 5x2 15 - x1 0, x2 0 x1x222468460 2x1+2x2=12 5x2 =15 4x1 =16 Z=6Z=0A(3,3)Zmax有有唯一最優解唯一最優解，當當 x1=x2=3 時，時，Zmax = 15= 15C(4,0)D(0,3)(0,0)B(4,2)頂點頂點基可行解基可行解A（3,3

17、）（3,3,0,4,0）B（4,2）（4,2,0,0,5）C（4,0）（4,0,4,0,15）D（0,3）（0,3,6,16,0）O（0,0）（0,0,12,16,15）一一對應一一對應 （2 2）（3 3）0,04 12231843 s.t.43max212212121xxxxxxxxxZ無窮多最優解無窮多最優解 0,142 s.t.max21212121xxxxxxxxZ無界解無界解x1x1x2 x2 0,12322 s.t.23max21212121xxxxxxxxZx1x2 無可行解無可行解（4 4）3 3、線性規劃問題解的類型、線性規劃問題解的類型（1）唯一最優解：只有一個解為最優解

18、）唯一最優解：只有一個解為最優解（2）無窮多最優解：有無窮多個解為最優解）無窮多最優解：有無窮多個解為最優解（3）無界解：目標函數的取值無界）無界解：目標函數的取值無界（4）無可行解：可行域為空集，即存在互相矛盾的約束條）無可行解：可行域為空集，即存在互相矛盾的約束條件。件。4 4、可行域的特征、可行域的特征（1 1）若）若L.P.的可行域不是空集，則可行域為凸集。的可行域不是空集，則可行域為凸集。（2 2）若）若L.P.有最優解，則一定可以在可行域的頂點上找到最有最優解，則一定可以在可行域的頂點上找到最優解。優解。（3 3）L.P.L.P. 的頂點與基可行解一一對應。的頂點與基可行解一一對應

19、。 3-1 3-1 預備知識：凸集與頂點預備知識：凸集與頂點1.3 1.3 單純形法單純形法（Simplex Method）原理原理（1 1）凸集：對于集合）凸集：對于集合C C中任意兩點連線段上的點，若全在中任意兩點連線段上的點，若全在C C內，內，則稱集合則稱集合C C為凸集。為凸集。直觀特征：圖形從內部向外部凸出。直觀特征：圖形從內部向外部凸出。凸集凸集非凸集非凸集（2 2）頂點：凸集中不在任意兩點的連線段內部的點。）頂點：凸集中不在任意兩點的連線段內部的點。X1X4X3X5X2單純形法的計算步驟：單純形法的計算步驟： 初始基可行解初始基可行解使目標函數值增大使目標函數值增大的新的基可行

20、解的新的基可行解是否最優解？是否最優解？結束結束是是否否1.4 1.4 單純形法的計算步驟單純形法的計算步驟1 1、前提：標準化的線性規劃問題的系數矩陣含有單位子矩陣。、前提：標準化的線性規劃問題的系數矩陣含有單位子矩陣。m n max z= s.t. 0 0CXAXbXb已知不妨假設不妨假設A中前中前m列對應的子矩陣是單位列對應的子矩陣是單位矩陣，取其為基矩陣，取其為基B，得到初始基可行解，得到初始基可行解12(0)00mbbXbm+3行行n+4列列第第1行：價值行行：價值行 cj第第2行：變量行行：變量行 xj最后一最后一行：檢驗數行行：檢驗數行 j第第1列：基價值列列：基價值列 CB第第

21、2列列：基變量列：基變量列 XB第第3列列：基解列：基解列 b最后一最后一列：列：比值比值列列 主體：系數矩陣主體：系數矩陣Amn2 2、單純形表的結構、單純形表的結構例例5：用單純形法求解下列線性規劃問題：用單純形法求解下列線性規劃問題.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x1 0， x2 0 s.t.12345123142512345max 2300022 124 16 s.t. 5 15, , , , 0zxxxxxxxxxxxxxxxxx解：先標準化解：先標準化Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X

22、3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 j 再列初始單純形表：再列初始單純形表：6-32 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 1615 2 2 1 0 0 6 4 0 0 1 0 - 0 5 0 0 1 3 2 3 0 0 0 j 以以55為主元進為主元進行初等行變換行初等行變換Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 6 16 3 2 0 1 0 -2/5 3 4 0 0 1 0 4 0

23、 1 0 0 1/5 - 2 0 0 0 -3/5x1 1為換入變量為換入變量 下面開始單純形法迭代：下面開始單純形法迭代：x5 5為換出變量為換出變量x2 2為換入變量為換入變量以以22為主元進為主元進行初等行變換行初等行變換x3 3為換出變量為換出變量主元化為主元化為1，主元列，主元列的其他元素化為的其他元素化為0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5j 此時得到唯一最優解此時得到唯一最優解X*=(3,3)T, , Z

24、max=15=15。6、單純形法中存在的問題、單純形法中存在的問題（1 1） 存在兩個以上的最大正檢驗數。存在兩個以上的最大正檢驗數。任取一個最大正檢驗數對應的變量作為換入變量。任取一個最大正檢驗數對應的變量作為換入變量。（2 2） 出現兩個以上相同的最小值。出現兩個以上相同的最小值。任取一個最小任取一個最小對應的變量作為換出變量。對應的變量作為換出變量。此時此時L.P.問題出現退化現象。問題出現退化現象。(1) (1) 當所有當所有 j 0 0 ，表示有，表示有唯一最優解唯一最優解；(2) (2) 當所有當所有 j 0，且，且存在某個非基變量的檢驗數存在某個非基變量的檢驗數 k=0，則該線，

25、則該線性規劃模型具有性規劃模型具有無窮多最優解無窮多最優解；(3) (3) 若存在某個若存在某個 j 0 0，但對應的第，但對應的第j列系數全非正，即列系數全非正，即aij 0 0，則，則線性規劃模型具有線性規劃模型具有無界解無界解。3-5 3-5 解的判別解的判別練習練習 用單純形法求解下列線性規劃問題用單純形法求解下列線性規劃問題 0,24261553 s.t.2max21212121xxxxxxxxz 0,24 2615 53 s.t.2 max432142132121xxxxxxxxxxxxz解：先標準化解：先標準化 2 1 0 0 54 x3x400 x1 x2 x3 x4bxBcB

26、 2 1 0 0cj 2415351 06201j 0 0 x3x102 x1 x2 x3 x4bxBcB 2 1 0 0cj430141 0j1/3-1/21/61/3-1/33/412 0 0 -1/12 -7/24 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810 -1/125/24j唯一最優解12max15333, , 444xxz5-1 5-1 人工變量法（大人工變量法（大M法）法）1.5 單純形法的進一步討論12121212min23 3s.t. 24,0zxxxxxxx x例例6：用單純形法求解下列線性規劃問題。：用單純形法求

27、解下列線性規劃問題。說明：說明： 若表中所有若表中所有 j 0 0 ，但存在非，但存在非0 0的人工變量的人工變量 ，則該模，則該模型型無可行解無可行解。 采用大采用大M法求解線性規劃模型時，如果模型中法求解線性規劃模型時，如果模型中各個系數與各個系數與M的值非常接近或相差很大，若用手工計算的值非常接近或相差很大，若用手工計算不會出現問題。但是若利用計算機求解，則容易引起混不會出現問題。但是若利用計算機求解，則容易引起混淆，使得機器判斷出錯，從而使大淆，使得機器判斷出錯，從而使大M法失效。法失效。 在這種情況下，可采用下面的兩階段法進行計算。在這種情況下，可采用下面的兩階段法進行計算。5-2

28、5-2 兩階段法兩階段法( (將將L.P.問題分成兩個階段來考慮問題分成兩個階段來考慮) ) 第一階段第一階段: : 判斷原判斷原L.P.L.P.問題是否存在可行解。問題是否存在可行解。 給原給原L.P.L.P.問題加入人工變量，并構造僅含人工變量的目標問題加入人工變量，并構造僅含人工變量的目標函數函數w（人工變量在人工變量在w中的系數一般取為中的系數一般取為1 1）并求）并求w的最小值；的最小值；然后用單純形法求解。若求得然后用單純形法求解。若求得wmin=0=0，則該問題有可行解，進，則該問題有可行解，進入第二階段，否則該問題無可行解，結束。入第二階段，否則該問題無可行解，結束。 第二階段

29、：將第第二階段：將第一一階段得到的最終表去掉人工變量，并階段得到的最終表去掉人工變量，并將目標函數還原為原將目標函數還原為原L.P.問題的目標函數（即修改最終表中問題的目標函數（即修改最終表中的第一行和第一列），以此作為第二階段的初始表，繼續的第一行和第一列），以此作為第二階段的初始表，繼續用單純形法求解。用單純形法求解。例：用兩階段法求解下列線性規劃問題。例：用兩階段法求解下列線性規劃問題。12121212min23 3s.t. 24,0zxxxxxxx x12312312123max230 3s.t. 2 4 ,0 xxxxxxxxx x x 標準化引入人工變量123451234125ma

30、x230 3s.t. 2 4 0 (1,2,5)jzxxxMxMxxxxxxxxxj z451234125min 3s.t. 2 40 (1,2,5)jwxxxxxxxxxxj(1) (1) 第一階段，構造判斷是否存在可行解的模型：第一階段，構造判斷是否存在可行解的模型：451234125max 3s.t. 2 40 (1,2,5)jwxxxxxxxxxxj 用單純形法求解這個問題，先標準化為；用單純形法求解這個問題，先標準化為；Cj x1x2x3x4XBbCB1 1 -1 1 0 1 2 0 0 1 0 0 0 -1 -134x4 x5-1 -1cj - zj 2 3-103/1=34/2=

31、 21/2 0 -1 1 -1/2 1/2 1 0 0 1/2x4 x212cj - zj 1/2 0 -1 0 -3/2-1 0241 0 -2 2 -1 0 1 1 -1 1x1 x221cj - zj 0 0 0 -1 -10 0 x50最優解12maxmin2, 1, 00 xxww，即本問題有可行解，進入第二階段 (2) (2) 第二階段第二階段 先在第一階段的最終單純形表去掉人工變量，再還原原先在第一階段的最終單純形表去掉人工變量，再還原原目標函數，即目標函數，即 max z=-2=-2x1 1-3-3x2 2+0+0 x3 3，繼續迭代：繼續迭代：Cj x1x2x3XBbCB1

32、0 -2 0 1 1 -2 -3 0 21x1 x2-2 -3cj - zj 0 0-1唯一最優解12max2, 1, 7xxz 故 zmin=7注意：兩階段法中不再出現大M，但需要解兩個線性規劃問題，要注意目標函數系數的變化。5-3 關于解的判別用最終單純形表判斷線性規劃問題解的類型：用最終單純形表判斷線性規劃問題解的類型：解的類型解的類型最終表的特征最終表的特征無可行解無可行解有非有非0 0的人工變量的人工變量有有可可行行解解唯一最優解唯一最優解無無非非0 0的人的人工變量，非基變量的檢驗工變量，非基變量的檢驗數全為負數數全為負數無窮多最優解無窮多最優解無非無非0 0的人工的人工變量，非基

33、變量的檢驗變量，非基變量的檢驗數全非正，且有某個非基變量的檢驗數全非正，且有某個非基變量的檢驗數為數為0 0無界解無界解無非無非0 0的的人工變量，有某個非基變量人工變量，有某個非基變量的檢驗數為正數，但該變量對應的系的檢驗數為正數，但該變量對應的系數全為非正數數全為非正數例：用單純形法求解下列線性規劃問題.max z=2 x1+3 x2 2 x1+2 x2 124x1 16 5 x2 15x10， x2 0 s.t.12345123142512345max 2300022 124 16 s.t. 5 15, , , , 0zxxxxxxxxxxxxxxxxx解：先標準化5-4 單純形法計算的

34、向量、矩陣描述Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 12 16 15 2 2 1 0 0 4 0 0 1 0 0 5 0 0 1 j 得到初始單純形表：6-3 2 3 0 0 0Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 3 4 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5 0 0 -1 0 -1/5j 最終單純形表：X4010X4010202410005B11102542151005B 可以驗證：11221sBbB bPB PC B 三三要要

35、素素決策變量決策變量約束條件約束條件目標函數目標函數兩兩個個三個三個以上以上xj0 xj無無約束約束xj 0 bi 0bi 0=maxZminZxs xa標標準準化化圖圖解解法、法、單單純純形形法法單單純純形形法法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束約束條件條件兩端兩端同乘同乘以以-1加加松松弛弛變變量量xs加加人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- Z 0-M根據上表可以列出初始單純形表根據上表可以列出初始單純形表5-5 5-5 單純形法小結單純形法小結個數取值限制右端常數約束方向要求系數結束j求檢驗數

36、0 j所所有有k找出最大正檢驗數？所有0 ika計算最小的lkxx替替換換基基變變量量用用非非基基變變量量單純形表列出下一張ax變量 的人工0非是否有 0 j非非基基變變量量的的有有某某個個最最優優解解一一唯唯 無可行解最優解最優解無窮多無窮多是是否否環環循循否否否否否否是是是是是是無無界界解解列初始表列初始表1.7 應用舉例 一般而言，一個經濟、管理問題要滿足以下條一般而言，一個經濟、管理問題要滿足以下條件，才能建立線性規劃模型：件，才能建立線性規劃模型： . .需要求解問題的目標能用數值指標來反映，需要求解問題的目標能用數值指標來反映，且能用線性函數來描述目標的要求；且能用線性函數來描述目

37、標的要求； . .為達到這個目標存在多種方案；為達到這個目標存在多種方案； . .要求達到的目標是在一定條件下實現的，這要求達到的目標是在一定條件下實現的，這些條件可用線性等式或不等式來描述。些條件可用線性等式或不等式來描述。（一）、混合配料問題例：某糖果廠用原料例：某糖果廠用原料A A、B B、C C加工成三種不同牌號的糖果甲、加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中各種原料的含量，原料成本，乙、丙。已知各種牌號糖果中各種原料的含量，原料成本，各種原料的每月限制用量，三種牌號糖果的單位加工費用及各種原料的每月限制用量，三種牌號糖果的單位加工費用及售價如下表所示。問該廠每月生產這

38、三種牌號糖果各多少千售價如下表所示。問該廠每月生產這三種牌號糖果各多少千克，能使該廠獲利最大。請建立這個問題的線性規劃模型?？?，能使該廠獲利最大。請建立這個問題的線性規劃模型。甲甲乙乙丙丙原料成本（元原料成本（元/kg/kg）每月限制每月限制用量（用量（kgkg）A AB BC C6060202030305050 60602.002.001.501.501.001.00200020002500250012001200加工費（元加工費（元/kg/kg）0.500.500.400.400.300.30售價（元售價（元/kg/kg）3.403.402.852.852.252.25解：用i=1,2,3表示原料A、B、C；用j=1,2,3表示糖果甲、乙、丙；設xij為生產第j種糖果使用的第i種原料的質量，則該問題的數學模型為：112131122232132333111