數學規(guī)劃模型

1、第四章 數學規(guī)劃模型,一、數學規(guī)劃模型,1.模型的建立,問題1 某廠利用甲,乙,丙,丁四種設備生產A,B,C三種產品, 相關數據如表所示. 已知這三種產品的單件利潤分別是4.5, 5, 7（百元）,試問該廠應如何安排生產可獲得最大利潤?,甲,乙,丙,丁,注意到變量 代表的是產品的產量, 故有抽去所給問題的具體意義, 我們得到原問題的數學關系為,分析,該問題的關鍵所在是確定每

2、種產品的產量, 為此以 表示三種產品的產量, 則目標為,在一個生產周期中, 每種設備所提供的工時為有限的,故對四種設備而言還應該滿足下列條件:,非負性,用Lingo軟件可以得到相應問題的解. 啟動Lingo, 在窗口下中輸入下列程序:,保存完之后執(zhí)行Lingo菜單下的Solve命令,得到相應的解.,Variable Value Reduced Cost

3、 X1 85.71429 0.000000 X2 71.42857 0.000000 X3 121.4286 0.000000 Row

4、Slack or Surplus Dual Price 1 1592.857 1.000000 2 0.000000 1.357143 3 57.14286

5、 0.000000 4 0.000000 0.2142857 5 0.000000 0.4642857,問題2 某車間要制造100套鋼筋架, 每套需要長為2.9 2.1 1.5 的鋼筋各一根. 已知原料鋼筋長

6、度為7.4 問如何切割鋼筋, 使得鋼筋的利用率為最高?,分析 該問題的要點是如何切割鋼筋, 使得每次切割之后, 剩下的余料為最少?,假設在切割過程中, 我們不考慮鋼筋的損耗, 并考慮各種切割方案:,非負性,從分析中可以看出, 此問題的關鍵是確定每種方案下的余料數.,設 表示第 種方案中使用的原料鋼筋數, 則余料數為,而相應的限制條件為,故原問題

7、的數學關系式為,非負性,在Lingo下得到該問題的解為,運行后得到該問題的解為,X2 25.00000 0.000000 X3 0.000000 0.3666667 X4 25.00000 0.000000

8、 X5 0.000000 1.283333 X1 25.00000 0.000000,線性規(guī)劃的模型一般可表示為,非負性,注 線性規(guī)劃的目標函數還可以用min來表示, 表示追求目標函數的最小值. 而 表示約束條件:（Subject to）.,

9、問題3 要從甲地調出物質2000噸, 從乙地調出物質1100噸, 分別供給 地1700噸, 地11噸, 地200噸和 100噸, 已知每噸運費如表所示, 試建立一個使運費達到最小的調撥計劃.,單位路程運費表,分析 設從第 個產地到第 個銷地的運輸量為 運輸成本為 則問題的目標函數為,由于從第一個產地調出的物質的總和為第一個產地的產量, 即有,同理,

10、有,對稱地, 對銷地而言, 有關系,由此得到該問題的數學模型,注 該問題又稱為運輸問題. 運輸問題的一般形式可寫成,其中 是第 個產地的產量, 是第 個銷地的需求量.,在上面的關系中, 有,相應的運輸問題稱為產銷平衡的運輸問題. 若產銷不平衡, 應該如何處理? 為什么總是假定產銷是平衡的.,問題4 隨機規(guī)劃模型,決策者要建造一座水庫, 使水庫的容量 在滿足給定的限制條件下達到最小,

11、 以使其造價最小.,分析 1.在一年中的第 個季節(jié)水庫應留出一定的容量 以保證洪水的注入. 由于洪水量是一個變數, 故假定以較大的概率 使得,其中 為第 個季節(jié)的儲水量.,2.為保證灌溉, 發(fā)電, 航運等用水供應, 水庫在每個季節(jié)應能保證一定的放水量 考慮到這仍然是一隨機因數, 要求滿足滿足這一條件的概率不小于 即,其中 為第 個季節(jié)的可放水量.,3.

12、為保證水庫的安全和水生放養(yǎng), 水庫還應有一定的儲水量 即,由此得到相應問題的數學模型為:,問題5 某公司準備派 個工人 去完成項工作 已知第 個工人完成第 工作的效率為 求如此的一個指派方案, 使工人完成這些工作的效率為最大.,該問題可用一個網絡圖 來表示:

13、其中 表示頂點集, 是邊集, 是權集. 該問題即是從 的每一個頂點,找出唯一的一條到 的某一個 的邊, 使得權之和為最大.,模型建立,若以 表示在頂點 存在邊, 否則則目標函數可表示為,而從 的每一個頂點 只能作一條邊等價于,同樣, 連 惟一的一條邊等價于,由此得到相應的數學模型為,這樣的規(guī)劃又稱為0-1規(guī)劃.,注1

14、很多實際問題都可以轉化成這樣的模型. 例如游泳接力隊員的選拔.,注2 當人數和工作數不相同時, 這樣的問題應該如何求解, 又當 時, 并且容許一個人能完成兩件工作, 又該如何解決?,二、模型的求解,例1 一奶制品加工廠用牛奶生產 兩種奶制品,1桶牛奶可以在設備甲上用12小時加工生產3公斤 或則在設備乙上用8小時加工成4公斤 根

15、據市場需要, 生產的 全部能售出, 且每公斤 獲利24元, 每公斤 可獲利16元. 現在加工廠每天能得到50桶牛奶的供應, 每天工人總的勞動時間為480小時, 并且設備甲每天至多能加工100公斤 設備乙的加工能力沒有限制. 試為該廠制定一個生產計劃, 使每天獲利最大, 并進一步討論以下3個附加問題:,⑴若用35元可以買到1桶牛奶, 應否作這項投資? 若投資,

16、 每天最多購買多少桶牛奶?,⑵若可以聘用臨時工人以增加勞動時間, 付給臨時工人的工資最多是每小時幾元?,⑶由于市場需求變化, 每公斤 的利潤增加到30元,應否改變生產計劃?,解 設 表示這兩種產品每天所消耗牛奶的數量（單位：桶）. 則用于生產 的牛奶可獲利用于生產 的牛奶可獲利 則目標函數為,限制條件分別為:,⑴對原料的限制:,⑵勞動力的限

17、制,⑶設備甲的開工限制,由此得到相應的規(guī)劃模型,對每一約束條件,在第一象限中確定坐標點的范圍, 最終確定解的范圍——可行域（多邊形區(qū)域）;,模型求解,解法1 （圖解法）,,確定等值線（圖中用虛線），則最優(yōu)解為可行域與等值線的最后交點（即圖中點的 坐標）即為所求問題的最優(yōu)解.,,,,,,,,為此求解方程,容易得到該方程的解為,解法2 （單純形方法）,原規(guī)劃的標準型為,解法3 （利用計算機軟件）,在軟件Lin

18、go8下進行求解:,輸入命令,Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000,Row Slack or Surplus Dua

19、l Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.000

20、00 0.000000,得到的解為,結果分析,⑴三個約束條件的右端視為“資源”: 原料, 勞動時間,設備甲的加工能力. 對當前解而言, 前兩種“消耗殆盡”，而設備甲尚余40公斤的加工能力.,⑵目標函數可以看作為是“效益”. 成為緊約束的資源一旦增加,則“效益”必然增加. 解中列出的“對偶”價格表示緊約束“資源”每增加一個單位后相應“效益”的增加值.,原料每增加一個單位, 利潤可增加48個

21、單位; 而勞動時間每增加一個單位, 利潤可增加2個單位. 而非緊約束資源的增加, 不會帶來相應的收益. 這種“資源”潛在價值被稱為 “影子”價格.,用“影子”價格即可回答附加問題.,⑴用35元購買一桶牛奶, 低于牛奶的影子價格, 故可以做這項投資; ⑵臨時工人每小時的工資不超過2元. 而設 備甲尚有富裕能力, 故增加工時不會產生效益.,⑶目標函數的系數發(fā)生變化對最優(yōu)解和最優(yōu)值的影響. 在圖解法中可以看到

22、，價值系數 對最優(yōu)解會產生一定的影響. 因為 確定了等值線的斜率, 原問題等值線的斜率為 , 當斜率上升到 則最優(yōu)解將會改變, 此時最優(yōu)解將在 點取得.,靈敏度分析還給出了各個系數的范圍: 的上界為24,下界為8, 即當

23、 時, 最優(yōu)解不變; 同樣當 時,最優(yōu)解不變.,從圖中還可以看出, 原料（牛奶）的增加, 對應的是直線 的向右的平移, 此時最優(yōu)解仍為點 但當 與 重合時, 最優(yōu)解將不再改變,,此時, 而由“影子”價格知: 原料每增加一個單位利潤將增加48個單位. 此時總利

24、潤為,同樣, 當勞動力資源增加時, 即直線 向右移動時, 最優(yōu)解也將改變, 但當 兩點重合時, 最優(yōu)解將不再改變. 由“影子”,價格, 勞動力每增加一個工時, 效益增加2個單位.但勞動力最多增加53個單位.,因設備甲仍有富余工時, 因而設備的加工能力無需再增加, 其“影子”價格為零.,根據上面的分析,可以回答原問題中提出的相關問題.,⑴可以批準用每桶35元的價格再購買部分牛奶,

25、但最多再購買10桶;,⑵可以以用低于每小時2元的工資聘用臨時工人以增,勞動時間, 但最多不得超過53小時.,例2 奶制品的銷售計劃,例1給出的 兩種奶制品的生產條件, 利潤及工廠的資源限制不變, 為增加工廠的獲利, 開發(fā)了奶制品的深加工技術: 用2小時和3元加工費, 可將1公斤 加工成0.8高級奶制品 也可將一公斤 加工成0.75公斤高級奶制品 每公斤

26、 能獲利44元, 每公斤 能獲利32元,試為該廠制定一個生產銷售計劃, 使獲得的利潤最大,并討論以下問題:,⑴若投資32元可以增加供應一桶牛奶, 投資3元可以增加一小時勞動時間, 應否作這樣的投資, 若每天投資150元, 可賺回多少?,⑵每公斤高級奶制品 的獲利經常有10%的波動,對指定計劃有無影響, 若每公斤 的獲利下降10%, 計劃應該改變嗎?,問題分析,要求指定生產計

27、劃, 關鍵是確定各產品的產量, 而目標函數為銷售這些產品之后可獲得的利潤.,建立模型,設每天銷售 公斤 公斤 公斤 公斤 用 公斤 加工 公斤 加工,目標函數,約束條件,原料供應 每天生產 公斤, 用牛奶 桶,

28、 每天生產 公斤,用牛奶 桶, 兩者之和不超過50桶;,勞動時間 每天生產 的時間分別為 加工 的時間分別為 兩者之和不超過480小時;,設備能力 的產量 不得超過設備甲

29、每天的,加工能力100公斤;,非負約束,附加約束 1公斤 加工成 公斤 即同樣,由此得到模型,,模型求解,用Lingo軟件, 進行求解, 得,Variable Value Reduced Cost X1 0.000000 1.680000

30、 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5

31、 24.00000 0.000000 X6 0.000000 1.520000,Row Slack or Surplus Dual Price 1 3460.800 1.000000

32、 2 0.000000 3.160000 3 0.000000 3.260000 4 76.00000 0.000000

33、 5 0.000000 44.00000 6 0.000000 32.00000Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable

34、 Variable Coefficient Increase Decrease X1 24.00000 1.680000 INFINITY,X2 16.00000 8.150000 2.100000

35、X3 44.00000 19.75000 3.166667 X4 32.00000 2.026667 INFINITY X5 -3.000000 15.80000 2.533333 X6

36、 -3.000000 1.520000 INFINITY,結果分析,由輸出的結果知, 約束2和3的“影子”價格分別是 和 即每增加一桶牛奶可使凈利潤增加,元,增加1小時勞動時間, 可是利潤增加 元, 所以應該投資 元增加一桶牛奶或投資3元增加一小時勞動時間. 若每天投資 元, 增加供應5桶牛奶, 可獲利,元,但約

37、束2的增加值最多不超過120, 意味牛奶的桶數最多不超過10桶.,在靈敏度分析的報告中, 目標函數系數的變化范圍分別為,由此可見, 當 的價格向下波動 或 的價格向上波動 都會影響到最優(yōu)解.,問題的提出 鋼鐵、煤、水電等生產、生活物資從若干供應點運送到一些需求點，怎樣安排運輸，使運費為最小、或者利潤為最大. 某種類型的貨物由于需要裝箱, 故要考慮如何搭配

38、使利用率達到最高, 諸如此類的問題都牽涉到一些具體的數學模型, 這目討論兩個問題,并利用相應的數學規(guī)劃模型加以解決.,三、應用舉例,題1 自來水的輸送問題,某市有甲、乙、丙、丁四個居民區(qū), 自來水由三個水庫供應, 四個區(qū)每天必須得到保證的基本用水量分別為 千噸, 但由于水源緊張, 三個水庫每天最多只能分別供應 噸自來水, 并由于地

39、區(qū)位置的差別, 自來水公司從各水庫向各區(qū)送水所需付出的引水管理費不同（見表）, 其它管理費用都是 千噸, 根據公司規(guī)定, 各區(qū)用戶按統(tǒng)一標準 千噸收費, 此外, 四個區(qū)都向公司申請了額外用水量, 分,分別為每天 千噸, 該公司應如何分配供水量, 才能獲利最多?,為了增加供水量, 自來水公司正在考慮進行水庫改造,隨三個水庫的供水量都提

40、高一倍, 問此時供水方案應如何改變?公司利潤可增加多少?,分析,問題的關鍵是如何安排從各個水庫向四個居民區(qū)供水,使得引水管理費用達到最小, 注意到其它費用與供水安排無關.,模型建立,設決策變量為 三個水庫 向甲、乙、丙、丁 四個區(qū)的供水量, 設水庫 向 區(qū)的日供水量為 并注意到

41、 由條件得,由于需求量大于供水量, 需求限制可表示為,在Lingo下得到問題的解.,Variable Value Reduced Cost X11 0.000000 30.00000 X12 50.00000

42、 0.000000 X13 0.000000 50.00000 X14 0.000000 20.00000 X21 0.000000 10.00000

43、 X22 50.00000 0.000000 X23 0.000000 20.00000 X24 10.00000 0.000000

44、 X31 40.00000 0.000000 X32 0.000000 10.00000 X33 10.00000 0.000000,即:該問題的解為,此時引水管理費為 元, 利潤為,元

45、.,討論,如果 三個水庫的每天最大供水量都增加一倍,則公司總供水能力為 千噸, 水庫供水量超過總需求量, 故此時需要計算三個水庫向甲、乙、丙、丁四個區(qū)供應每千噸水的凈利潤， 即有表2,從水庫向各區(qū)送水的凈利潤,由此得到目標函數為,約束條件為：,在Lingo下得到問題的解：,Variable Value Reduced Cost

46、 X11 0.000000 25.00000 X12 100.0000 0.000000 X13 0.000000 30.00000 X14

47、 0.000000 20.00000 X21 0.000000 5.000000 X22 40.00000 0.000000 X23 30.00000

48、 0.000000 X24 50.00000 0.000000 X31 80.00000 0.000000 X32 20.00000 0.00000

49、0 X33 0.000000 0.000000,Row Slack or Surplus Dual Price 1 93400.00 1.000000 2 0.0

50、00000 305.0000 3 0.000000 305.0000 4 0.000000 250.0000 5 0.000000

51、 10.00000 6 0.000000 15.00000 7 0.000000 -45.00000 8 0.000000 -5.000000,題2

52、貨機裝運問題,問題 某種貨機有三個貨艙: 前艙、中艙、后艙. 三個貨艙所能裝載的貨物的最大重量和體積都有限制, 如表所示, 并且為了保持飛機的平衡,三個貨艙中實際裝載貨物的重量必須與其最大容許重量成正比.,現有四種貨物供該貨機本次飛行裝運, 有關信息如表,最后一列表示裝運后獲得的利潤.,假設,1.每種貨物可以進行任意的分割;,2.每種貨物可以在一個或多個貨艙中任意分布;,3.每種貨物可以混裝, 并保證不留空隙.,

53、應如何安排裝運, 使該貨機本次裝運的利潤最大?,模型建立,決策變量 表示第 種物資裝入第 個貨艙的重量, 貨艙 分別表示前、中、后艙.,目標函數表示一次運送后的總利潤, 即有,約束條件有如下的:,⑴總重量約束,⑵三個貨艙的重量限制,⑶三個貨艙的空間限制,⑷平衡限制,模型求解.,在Lingo下,可得到模型的解為:,Variable Value Reduced C

54、ost X11 0.000000 400.0000 X12 0.000000 57.89474 X13 0.000000 400.0000

55、 X21 7.000000 0.000000 X22 0.000000 239.4737 X23 8.000000 0.000000

56、X31 3.000000 0.000000,Variable Value Reduced Cost X32 12.94737 0.000000 X33 0.000000 0.000000

57、 X41 0.000000 650.0000 X42 3.052632 0.000000 X43 0.000000 650.0000,最大利潤為,題3 汽車生產問題,一

58、汽車廠生產小、中、大三種類型的汽車, 已知各類型每輛車對鋼材、勞動時間的需求, 利潤以及每月工廠,勞動時間的現有量入表所示, 試指定月生產計劃, 使工廠每月的利潤最大.,模型的建立,設每月生產小、中、大型汽車的數量分別為工廠的月利潤為 假定在生產周期中, 各項指標不變, 則有相應的線性規(guī)劃:,模型求解,該問題的整數解為,討論,若增加附加條件: 每種汽車如果生產的話,則至少生產80輛, 則生產計劃應該做如何

59、修改?,分析: 根據條件, 對決策變量的限制改為如下幾種:,⑴,⑵,⑶,⑷,⑸,⑹,⑺,對得到的每一個解進行討論, 最后確定最大值解.,最優(yōu)解為,注 在Lingo下, 求整數解的命令為 變量名,方法二 用 規(guī)劃,在問題中,引入待定常數 其中 為任意的的正數,（在具體問題中可以確定）,,Global optimal solution found at

60、iteration: 31 Objective value: 610.0000 Variable Value Reduced Cost X1 80.00000 -2.0000

61、00 X2 150.0000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000

62、 Y2 1.000000 0.000000 Y3 0.000000 0.000000,題4 原料采購與加工,問題 某公司用兩種原油（ 和 ）混合加工成兩種汽油（甲和乙）, 甲、乙兩種汽油含原油的最低比例分別為

63、 每噸售價分別為 元和 元,該公司還有原油 和 的庫存量分別為 噸和噸, 另外還可以從市場上買到不超過 噸的原油原油 的市場價為: 購買不超過 噸時的單價為 噸, 購買量超過 噸但不超過 噸時, 超過部分 噸, 超過

64、 噸的部分, 噸. 該公,司應如何安排原油的采購和加工?,問題分析,公司安排原油的采購和加工, 其目的是為了取得最大利潤, 但問題的困難之處在于原油 的采購價與采購量的關系比較復雜.,模型建立,設原油的購買量為 則由題意, 購買成本函數為,但這樣的函數過于復雜, 為了是問題盡可能簡單, 我們引入多個變量來刻畫:,分別以 表示以

65、噸, 噸, 噸采購得到的原油 的采購量, 則當以 噸的價格采購到原油時, 總有 故相應的條件可表示為,同樣, 當以價格 噸的價格購買到了 噸原油 時, 有,此外,變量 還應滿足,假設: 用于生產甲、乙兩種汽油的原油 的數量分別為 用于生產甲、乙兩種汽油的原油 的

66、數量分別為 則總收入為,而成本函數 可表達為,約束條件為,以及非負限制,總結上面的分析, 得到相應的模型為,模型求解,利用Lingo, 得到問題的解為,Variable Value Reduced Cost X11 500.0000 0.000000

67、 X21 500.0000 0.000000 X12 0.000000 0.2666667 X22 0.000000 0.000000

68、 X1 0.000000 0.4000000 X2 0.000000 0.000000 X3 0.000000 0.000000,解法二: 采用 規(guī)劃,令