北京理工大學--運籌學

1、1,運籌學,北京理工大學管理與經濟學院吳祈宗教授,2,1、緒 論 2、線 性 規(guī) 劃 3、運 輸 問 題 4、動 態(tài) 規(guī) 劃 5、圖與網絡分析 6、排 隊 論 7、教學日歷,運 籌 學 ——目錄,說 明 本教學課件是與教材緊密配合使用的，教材為：《運籌學》 楊民助編著西安交通大學出版社，2000年6月參考書：《運籌學》 清華大學出版社或其

2、他的《運籌學》方面本科教材的相關內容下面所標注的頁號，均為本課程教材的頁號。例如：p123 表示第123頁p31-34 表示從第31頁到第34頁,3,緒 論,運籌學（Operational Research) 直譯為“運作研究” 運籌學是運用科學的方法（如分析、試驗、量化等）來決定如何最佳地運營和設計各種系統(tǒng)的一門學科。運籌學對經濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據

3、的最優(yōu)方案，以實現最有效的管理。 運籌學有廣泛應用（可以自己找一些參考書看）運籌學的產生和發(fā)展（可以自己找一些參考書看）,4,運籌學解決問題的過程,1）提出問題：認清問題2）尋求可行方案：建模、求解3）確定評估目標及方案的標準或方法、途徑4）評估各個方案：解的檢驗、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實施：回到實踐中7）后評估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析

4、與定量分析。構成決策。,5,運籌學的分支,線性規(guī)劃非線性規(guī)劃整數規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃隨機規(guī)劃模糊規(guī)劃等,圖與網絡理論存儲論排隊論決策論對策論排序與統(tǒng)籌方法可靠性理論等,6,運籌學在工商管理中的應用,生產計劃：生產作業(yè)的計劃、日程表的編排、合理下 料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存

5、 量等運輸問題：確定最小成本的運輸線路、物資的調撥、 運輸工具的調度以及建廠地址的選擇等人事管理：對人員的需求和使用的預測，確定人員編 制、人員合理分配，建立人才評價體系等市場營銷：廣告預算、媒介選擇、定價、產品開發(fā)與 銷售計劃制定等財務和會計：預測、貸款、成本分析、定價、證券管

6、 理、現金管理等 *** 設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等,7,運籌學方法使用情況(美1983)（%）,8,運籌學方法在中國使用情況(隨機抽樣)（%）,9,運籌學的推廣應用前景,據美勞工局1992年統(tǒng)計預測: 運籌學應用分析人員需求從1990年到2005年的增長百分比預測為73%,增長速度排到各項職業(yè)的前三位.結論:運籌學在國內或國外的推廣前景是非常廣

7、闊的工商企業(yè)對運籌學應用和需求是很大的在工商企業(yè)推廣運籌學方面有大量的工作要做,10,學習運籌學要把重點放在分析、理解有關的概念、思路上。在自學過程中，應該多向自己提問，如一個方法的實質是什么，為什么這樣做，怎么做等。自學時要掌握三個重要環(huán)節(jié)： 1、認真閱讀教材和參考資料，以指定教材為主，同時參考其他有關書籍。一般每一本運籌學教材都有自己的特點，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學習深入

8、。但是，把時間過多放在參考資料上，會導致思路分散，不利于學好。 2、要在理解了基本概念和理論的基礎上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習的主要作用也是這樣，它同時還有讓你自己檢查自己學習的作用。因此，做題要有信心，要獨立完成，不要怕出錯。因為，整個課程是一個整體，各節(jié)內容有內在聯(lián)系，只要學到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。 3、要學會做學習小結。每一節(jié)或一章學完后，必須學會用精

9、煉的語言來該書所學內容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關知識和內容。這就稱作“把書讀薄”，若能夠結合自己參考大量文獻后的深入理解，把相關知識從更深入、廣泛的角度進行論述，則稱之為“把書讀厚”在建數學模型時要結合實際應用，要學會用計算機軟件解決問題。,如何學習運籌學課程,返回目錄,11,各章節(jié)的重點、難點及注意事項,12,1、 線 性 規(guī) 劃,線性規(guī)劃模型： 目標函數：Max z = 50 x

10、1 + 100 x2 約束條件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250

11、 x1 , x2 ≥ 0**看 p 7--9 例1-1，1-2,例1. 某工廠在計劃期內要安排甲、乙兩種產品的生產，已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗以及資源的限制，如下表：問題：工廠應分別生產多少單位甲、乙產品才能使工廠獲利最多？,,13,1、 線 性 規(guī) 劃 （續(xù)1.1）,1. 1 線性規(guī)劃的概念線性規(guī)劃的組成： 目標函

12、數 Max f 或 Min f 約束條件 s.t. (subject to) 滿足于 決策變量 用符號來表示可控制的因素,一般形式 ( p10-- p 11)目標函數： Max （Min）

13、z = c1 x1 + c2 x2 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …

14、… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0,標準形式 ( p11-- p 15 ，例1-3)目標函數： Max z = c1 x1 + c2 x2

15、 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… ……

16、 am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0**練習：p 68--70 習題1 1-1，1-2,14,1、 線 性 規(guī) 劃 （續(xù)1.2）,1. 2 線性規(guī)劃問題解的概念及性質熟悉下列一些解的概念（p15--16）

17、 可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最優(yōu)基。,圖解方法及各有關概念的意義（p16--20） 看：圖解法步驟，例1-4，1-5，1-6，1-7，1-8，1-9 下一頁是一個圖解法解題的一個例子，右圖中的陰影部分為可行域。,單純形法的理論基礎（p20--30） 1.2.3段要求看懂，了解如何直接通過對約束矩陣的分析求出基本可行解

18、 1.2.4, 1.2.5兩段應注重結論的了解，如單純形法思想和關于線性規(guī)劃解的四個定理，而對證明過程則可根據自己的數學基礎來掌握： 基礎很好，可要求掌握；否則，也可略去不看。**習題：p70 習題1 1-3，1-4,15,1、 線 性 規(guī) 劃 （續(xù)1.2）,例1.目標函數： Max z = 50 x1 + 100 x2 約束條件： s.t. x1

19、+ x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標值 z =

20、 27500,16,1、 線 性 規(guī) 劃 （續(xù)1.3）,1. 3 單純形法 利用單純形表的方法求解線性規(guī)劃——重點 (p30--45 1.3.1, 1.3.2, 1.3.3) 此項內容是本章的重點，學習中應注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內容以及大量練習來掌握。,17,1、 線 性 規(guī) 劃 （續(xù)1.3）,表格單純形法 ( p40-- p 45)

21、 考慮： bi > 0 i = 1 , … , m Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn

22、 ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ，x2 ，… ，xn ≥ 0加入松弛變量： Max z = c1 x1 + c2

23、 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… ……

24、 am1 x1 + am2 x2 + … + amn xn+ xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0,18,顯然，xj = 0 j = 1, … , n ; xn+i = bi i = 1 , … , m 是基本可行解 對應的基是單位矩陣。以下是初始單純形表：

25、 m m其中：f = -∑ cn+i bi ?j = cj -∑ cn+i aij 為檢驗數 cn+i = 0 i= 1,…,m i = 1

26、 i = 1 an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m,1、 線 性 規(guī) 劃 （續(xù)1.3）,19,1、 線 性 規(guī) 劃 （續(xù)1.3單純形法解題例）,例1。化標準形式： Max z = 50 x1 + 100 x2 s.t. x

27、1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250

28、 x1 , x2 , x3 , x4 , x5 ≥ 0最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標量，表示原料A有50個單位的剩余）,20,注意：單純形法中， 1、每一步運算只能用矩陣初等行變換； 2、表中第3列的數總應保持非負（≥ 0）； 3、當所有檢驗數均非

29、正（≤ 0）時，得到最優(yōu)單純形表。,1、 線 性 規(guī) 劃 （續(xù)1.3）,21,1、 線 性 規(guī) 劃 （續(xù)1.3）,一般情況的處理及注意事項的強調（p45--55） 1.3.4段主要是討論初始基本可行解不明顯時，常用的方法。要弄清它的原理，并通過例1-14 ~ 例1-17掌握這些方法，同時進一步熟悉用單純形法解題?？紤]一般問題： bi > 0 i = 1 , … , m Max

30、 z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… ……

31、 am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0,22,1、 線 性 規(guī) 劃 （續(xù)1.3）,大M法： 引入人工變量 xn+i ≥ 0 i = 1 , … , m ; 充分大正數 M 。 得到， Max z = c1 x1

32、+ c2 x2 + … + cn xn + M xn+1 + … + M xn+m s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… ……

33、 am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0顯然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解 對應的基是單位矩陣。結論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , …

34、 , m 則是原問題的最優(yōu)解；否則，原問題無可行解。,23,1、 線 性 規(guī) 劃 （續(xù)1.3）,兩階段法：引入人工變量 xn+i ≥ 0，i = 1 , … , m；構造， Max z = - xn+1 - xn+2 - … - xn+m s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22

35、 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0第一階段求解上述問題：顯然，xj = 0 j=1,

36、 … , n ; xn+i = bi i =1 , … , m 是基本可行解 對應的基是單位矩陣。結論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , … , m 則是原問題的基本可行解；否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。,24,1、 線 性 規(guī) 劃 （續(xù)1.3）例題,例：（LP） Max z = 5 x1 + 2 x2 + 3 x3 -

37、 x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x

38、2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0大M法問題（LP - M） Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x6 s.t.

39、 x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26

40、 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0兩階段法 ：第一階段問題（LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15

41、 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0,25,1、 線

42、性 規(guī) 劃 （續(xù)1.3）大M法例,大M法 （LP - M）,得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標值：112/3,26,1、 線 性 規(guī) 劃 （續(xù)1.3）兩階段法例,第一階段 （LP - 1）,得到原問題的基本可行解：(0，15/7，25/7，52/7)T,27,1、 線 性 規(guī) 劃 （續(xù)1.3）兩階段法例,第二階段 把基本可行解填入表中,得到原問題的最優(yōu)解：(25/3，10/3，0，11)T

43、 最優(yōu)目標值：112/3,28,1、 線 性 規(guī) 劃 （續(xù)1.3）,1.3.5 矩陣描述—— 此段為選讀，有困難者可不看。 1.3.6 段單純形迭代過程中的幾點注意事項是對有關內容的強調和補充，要認真學習、理解。**習題：p70--71 習題1 1-5，1-6,29,1. 4 線性規(guī)劃應用—— 建模（p55--68）本節(jié)介紹了些線性規(guī)劃應用的例子，這些例子從多個方面介紹建模對未來是很有用的，應認真對待

44、。 除了教材上的例子之外，還有許多其它應用：* 合理利用線材問題：如何下料使用材最少* 配料問題：在原料供應量的限制下如何獲取最大利潤* 投資問題：從投資項目中選取方案，使投資回報最大* 產品生產計劃：合理利用人力、物力、財力等，使獲利最大* 勞動力安排：用最少的勞動力來滿足工作的需要* 運輸問題：如何制定調運方案，使總運費最小 **下面是一些建模的例子，有興趣者，可作為練習。這些例子有一定的難度，做起來會有

45、一些困難。**習題：p72--73 習題1 1-7，1-8，1-9，1-10,1、 線 性 規(guī) 劃 （續(xù)1.4）,返回目錄,30,例．某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員?,例：人力資源分配的問題,31,解：設 xi 表示第i班次時開始

46、上班的司機和乘務人員數,這樣我們建立如下的數學模型。目標函數： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20

47、 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0,例：人力資源分配的問題（續(xù)）,32,例、 明興公司生產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、乙兩種產品的鑄件可以外包協(xié)作，亦可以自行生產，但產品丙必須本廠鑄造才能保證質量。數據如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產品各生產多少件？甲、乙兩種產品的鑄造中，由本公司鑄造和由外包協(xié)作各應多少

48、件？,例：生產計劃的問題,33,解：設 x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產品的件數， x4,x5 分別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產品的件數。 求 xi 的利潤：利潤 = 售價 - 各成本之和可得到 xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下的數學模型。目標函數： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x

49、5 約束條件： s.t. 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0,例：生產計劃的問題（續(xù)）,34,例、 永久機械廠

50、生產Ⅰ、Ⅱ、Ⅲ三種產品，均要經過A、B 兩道工序加工。假設有兩種規(guī)格的設備A1、A2能完成 A 工序；有三種規(guī)格的設備B1、B2、B3能完成 B 工序。Ⅰ可在A、B的任何規(guī)格的設備上加工；Ⅱ 可在任意規(guī)格的A設備上加工，但對B工序，只能在B1設備上加工；Ⅲ只能在A2與B2設備上加工；數據如下表。問：為使該廠獲得最大利潤，應如何制定產品加工方案？,例：生產計劃的問題（續(xù)）,35,解：設 xijk 表示第 i 種產品，在第 j 種工序上的第

51、 k 種設備上加工的數量。 利潤 = [（銷售單價 - 原料單價）* 產品件數]之和 - （每臺時的設備費用*設備實際使用的總臺時數）之和。 這樣我們建立如下的數學模型: Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t. 5x111 + 10x211

52、 ≤ 6000 （ 設備 A1 ） 7x112 + 9x212 + 12x312 ≤ 10000 （ 設備 A2 ） 6x121 + 8x221 ≤ 4000 （ 設備 B1 ） 4x122 + 11x322 ≤ 7000 （ 設備 B2 ） 7x123

53、 ≤ 4000 （ 設備 B3 ） x111+ x112- x121- x122- x123 = 0 （Ⅰ產品在A、B工序加工的數量相等） x211+ x212- x221 = 0 （Ⅱ產品在A、B工序加工的數量相等） x312 - x322 = 0 （Ⅲ產品在A、B工序加工的數量相等） xijk ≥ 0 , i = 1,2,3; j

54、= 1,2; k = 1,2,3,例：生產計劃的問題（續(xù)）,36,例、某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應如何下料，可使所用原料最??？解： 設計下列 5 種下料方案,假設 x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數。這樣我們建立如下的數學模型。目標函數： Min x1 + x2 + x3 + x4 + x5

55、約束條件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0,例：套裁下料問題,37,例6．某工廠要用三種

56、原料1、2、3混合調配出三種不同規(guī)格的產品甲、乙、丙，數據如下表。問：該廠應如何安排生產，使利潤收入為最大？,例：配料問題,38,例：配料問題（續(xù)）,解： 設 xij 表示第 i 種（甲、乙、丙）產品中原料 j 的含量。這樣我們建立數學模型時，要考慮： 對于甲： x11，x12，x13； 對于乙： x21，x22，x23； 對于丙： x31，x32，x33； 對于原料1： x11，x21，

57、x31； 對于原料2： x12，x22，x32； 對于原料3： x13，x23，x33； 目標函數： 利潤最大，利潤 = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個； 供應量限制 3 個。,39,Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 s.t. 0.5 x11-0.5 x12 -0.5 x1

58、3 ≥ 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超過25%） 0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超過50%） x11+ x21 + x31 ≤ 100 (供應量限制）

59、x12+ x22 + x32 ≤ 100 (供應量限制） x13+ x23 + x33 ≤ 60 (供應量限制） xij ≥ 0 , i = 1,2,3; j = 1,2,3,例：配料問題（續(xù)）,40,例8．某部門現有資金200萬元，今后五年內考慮給以下的項目投資。已知：項目A：從第一年到第五年每年年初都可投資，當年末能收回本利110%；項目B：從第一年

60、到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元； 據測定每萬元每次投資的風險指數如右表：問：a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應如何確定這些項目的每年

61、投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數為最?。?解： 1）確定決策變量：連續(xù)投資問題 設 xij ( i = 1 - 5，j = 1、2、3、4)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51

62、 B x12 x22 x32 x42 C x33 D x24,例：投資問題,41,2）約束條件：第一年：A當年末可收回投資，故第一年年初應把全部資金投出去，于是 x11+ x12 = 200；第二年：B次當年末才可收回投資故第二年年初的資金為 x11，于是 x2

63、1 + x22+ x24 = 1.1x11；第三年：年初的資金為 x21+x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；第四年：年初的資金為 x31+x22，于是 x41 + x42 = 1.1x31+ 1.25x22；第五年：年初的資金為 x41+x32，于是 x51 = 1.1x41+ 1.25x32； B、C、D的投資限制： xi2 ≤ 30 ( I =1、2、3、4 )，x33 ≤ 80

64、，x24 ≤ 100 3）目標函數及模型：a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x5

65、1 = 1.1x41+ 1.25x32； xi2 ≤ 30 ( I =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4） b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 20

66、0 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 ≤ 30 ( I =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 1.1x51 +

67、1.25x42+ 1.4x33+ 1.55x24 ≥ 330 xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,例：投資問題（續(xù)）,42,2、線性規(guī)劃問題的進一步研究（2.1）,2. 1 對偶原理1、對偶問題：考慮前文例 1 若設備和原料都用于外協(xié)加工，工廠收取加工費。試問：設備工時和原料A、B 各如何收費才最有競爭力？

68、 設 y1 ，y2 ，y3 分別為每設備工時、 原料 A、B每單位的收取費用Max z = 50 x1 + 100 x2 Min f = 300 y1 + 400 y2 + 250 y3 s.t. x

69、1 + x2 ≤ 300 s.t. y1 + 2 y2 + ≥ 50 2 x1 + x2 ≤ 400 （不少于甲產品的利潤） x2 ≤ 250 y1 + y2 + y3 ≥ 100