第二章 線性規(guī)劃基本概念

1、Data, Model and Decisions 數(shù)據(jù)、模型與決策數(shù)據(jù)、模型與決策 Session 2 Linear Programming: Basic Conception 線性規(guī)劃：基本概念線性規(guī)劃：基本概念 Session Topics Three Classic Applications of LP 典型的線性規(guī)劃問題典型的線性規(guī)劃問題 Basic Concepts of Linear Programming 線性規(guī)劃的基本概念線性規(guī)劃的基本概念 The Graphical Method for Solving LP 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 Using Excel Sol

2、ver to Solving 用微軟用微軟Excel Solver 求解求解 Key Categories of LP Problems 線性規(guī)劃問題的主要類型線性規(guī)劃問題的主要類型 2.2 案例研究：偉恩德玻璃制品公司產(chǎn)品組合問題案例研究：偉恩德玻璃制品公司產(chǎn)品組合問題 公司有三個工廠：公司有三個工廠： 工廠工廠1：生產(chǎn)鋁框和五金件：生產(chǎn)鋁框和五金件 工廠工廠2：生產(chǎn)木框：生產(chǎn)木框 工廠工廠3：生產(chǎn)玻璃和組裝窗與門：生產(chǎn)玻璃和組裝窗與門 公司打算生產(chǎn)的新產(chǎn)品公司打算生產(chǎn)的新產(chǎn)品 8英尺玻璃門英尺玻璃門 4英尺英尺 6英尺雙層窗英尺雙層窗 收集的所有數(shù)據(jù)信息如下表收集的所有數(shù)據(jù)信息如下表 工廠

3、工廠 單位產(chǎn)品生產(chǎn)時間單位產(chǎn)品生產(chǎn)時間 每周可利用時間每周可利用時間 門門窗窗 11小時小時04小時小時 202小時小時12小時小時 33小時小時2小時小時18小時小時 單位利潤單位利潤300500 理論模型理論模型 0, 1823 122 4 . . 500300max 21 21 2 1 21 xx xx x x ts xxz 2.3 在電子表格上建立偉恩德公司問題的模型在電子表格上建立偉恩德公司問題的模型 第一步：選擇決策變量單元格第一步：選擇決策變量單元格 決策變量的初始值一般賦決策變量的初始值一般賦0，并用較醒目的顏色表示。，并用較醒目的顏色表示。 Wyndor Glass Co.

4、Product-Mix Problem 門門窗窗 單位利潤單位利潤$300$500 可用工時可用工時 工廠工廠1104 工廠工廠20212 工廠工廠33218 門門窗窗 產(chǎn)品利潤產(chǎn)品利潤00 單位產(chǎn)品工時消耗單位產(chǎn)品工時消耗 第二步：目標單元格，用函數(shù)公式表示第二步：目標單元格，用函數(shù)公式表示 并用較醒目的顏色表示。并用較醒目的顏色表示。 門門窗窗 單位利潤單位利潤$300$500 可用工時可用工時 工廠工廠1104 工廠工廠20212 工廠工廠33218 門門窗窗Total Profit 生產(chǎn)量生產(chǎn)量11$800 單位產(chǎn)品工時消耗單位產(chǎn)品工時消耗 11 12 G Total Profit =

5、SUMPRODUCT(UnitProfit,UnitsProduced) 第三步：約束條件左邊項也用函數(shù)表示第三步：約束條件左邊項也用函數(shù)表示 門門窗窗 單位利潤單位利潤$300$500 已用工時已用工時可用工時可用工時 工廠工廠1101=4 工廠工廠2022=12 工廠工廠3325=18 門門窗窗總利潤總利潤 生產(chǎn)量生產(chǎn)量11$800 單位產(chǎn)品工時消耗單位產(chǎn)品工時消耗 5 6 7 8 9 E Hours Used =SUMPRODUCT(C7:D7,UnitsProduced) =SUMPRODUCT(C8:D8,UnitsProduced) =SUMPRODUCT(C9:D9,UnitsP

6、roduced) 門門窗窗 單位利潤單位利潤$300$500 已用工時已用工時可用工時可用工時 工廠工廠1104=4 工廠工廠2026=12 工廠工廠33218=18 門門窗窗總利潤總利潤 生產(chǎn)量生產(chǎn)量43$2,700 單位產(chǎn)品工時消耗單位產(chǎn)品工時消耗 The spreadsheet for the Wyndor problem with a trial solution (4 doors and 3 windows) entered into the changing cells. 第四步：試求最優(yōu)解第四步：試求最優(yōu)解 2.6 應用應用Excel 求解線性規(guī)劃問題求解線性規(guī)劃問題 (1)Ex

7、cel Solver 的安裝 Excel工具菜單中選擇加載宏 (2)確定可變單元格和目標單元格 3 4 5 6 7 8 9 10 11 12 BCDEFG DoorsWindows Unit Profit$300$500 HoursHours UsedAvailable Plant 1101=1 Plant 2022=12 Plant 3325=18 DoorsWindowsTotal Profit Units Produced11$800 Hours Used Per Unit Produced (3)增加約束條件增加約束條件 DoorsWindows Unit Profit$300$500

8、 HoursHours UsedAvailable Plant 1101=1 Plant 2022=12 Plant 3325=18 DoorsWindowsTotal Profit Units Produced11$800 Hours Used Per Unit Produced (4)完成求解對話框完成求解對話框 (5)求解方式的選擇求解方式的選擇 (6)求解結果對話框求解結果對話框 (7) 求解結果報告求解結果報告靈敏性報告靈敏性報告極限報告極限報告 偉恩德公司電子表格求解模型偉恩德公司電子表格求解模型 Wyndor Glass Co. Product-Mix Problem 門門窗窗

9、單位利潤單位利潤$300$500 已用工時已用工時可用工時可用工時 工廠工廠1102=4 工廠工廠20212=12 工廠工廠33218=50%50% 非聯(lián)合001010 01 11 1 卡車010111 10 00 0720720=720720 鐵路1 10 01 10 00 00 01 11 1505505=1919 決策變量 阿什利阿什利A 貝德福德貝德福德B康索康索C鄧比鄧比D厄勒姆厄勒姆E 弗洛倫斯弗洛倫斯F 加斯頓加斯頓G 霍普特霍普特H合計合計 購買數(shù)量(千噸)55556006000 020201001000 04504500 01225=12251225 = 生產(chǎn)容量（千噸）30

10、0300600600510510655655575575680680450450490490 目標函數(shù) 采購成本總計(美元) 73267.573267.5 電子表格電子表格 (1)為了使供應煉焦煤的成本最小化為了使供應煉焦煤的成本最小化,NBS應該與每個供應商簽訂多應該與每個供應商簽訂多 少煤炭的供應量少煤炭的供應量? 答案如上表所示。答案如上表所示。 (2)NBS的總供應成本是多少的總供應成本是多少? 答案：供應煉焦煤的總成本是：答案：供應煉焦煤的總成本是： 成本成本 =49.50A+50.00B+61.00C+63.50D+66.50E+71.00F+72.50G+80.00H =7326

11、7.50 (3)NBS的平均供應成本是多少的平均供應成本是多少? 答案答案:平均成本是平均成本是73267.50/1225=59.81(美元美元/噸噸) 我們現(xiàn)在可以回答斯蒂芬提出的三個問題：我們現(xiàn)在可以回答斯蒂芬提出的三個問題： （4）煉焦煤的邊際成本是多少，也就是說，煉焦煤額外增加一噸）煉焦煤的邊際成本是多少，也就是說，煉焦煤額外增加一噸 花費花費NBS多少費用？多少費用？ （5）NBS應該考慮擴大卡車的運輸能力嗎？如果回答是肯定的，應該考慮擴大卡車的運輸能力嗎？如果回答是肯定的， 那么它們應該愿意花費多少？那么它們應該愿意花費多少？ （6）NBS應該考慮擴大鐵路的運輸能力嗎？如果回答是肯

12、定的，應該考慮擴大鐵路的運輸能力嗎？如果回答是肯定的， 那么它們應該愿意花費多少？那么它們應該愿意花費多少？ （7）為了從貝德福德礦業(yè)公司或加斯頓礦業(yè)公司獲得更多的煤，）為了從貝德福德礦業(yè)公司或加斯頓礦業(yè)公司獲得更多的煤， 斯蒂芬愿意簽訂一個比較高的價格協(xié)議嗎？如果回答是肯定的，那斯蒂芬愿意簽訂一個比較高的價格協(xié)議嗎？如果回答是肯定的，那 么他應該愿意支付的價格是多少？么他應該愿意支付的價格是多少？ 更深入的問題：更深入的問題： 這需要從求解以后的敏感性報告中獲取有關信息來回答這些問題這需要從求解以后的敏感性報告中獲取有關信息來回答這些問題 敏感性報告敏感性報告 （4）煉焦煤的邊）煉焦煤的邊

13、際成本是多少，也際成本是多少，也 就是說，煉焦煤額就是說，煉焦煤額 外增加一噸花費外增加一噸花費 NBS多少費用？多少費用？ 答：煉焦煤額外增煉焦煤額外增 加一噸花費加一噸花費NBS 61.5美元的費用美元的費用 （5）NBS應該考應該考 慮擴大卡車的運輸慮擴大卡車的運輸 能力嗎？如果回答能力嗎？如果回答 是肯定的，那么它是肯定的，那么它 們應該愿意花費多們應該愿意花費多 少？少？ 答答:應該擴大卡車應該擴大卡車 的運輸能力的運輸能力,NBS 愿意花費愿意花費1千美元千美元/ 千元千元 （6）NBS應該考應該考 慮擴大鐵路的運輸慮擴大鐵路的運輸 能力嗎？如果回答能力嗎？如果回答 是肯定的，那么

14、它是肯定的，那么它 們應該愿意花費多們應該愿意花費多 少？少？ 答答:鐵路的運載能鐵路的運載能 力為力為650千噸千噸,而實而實 際只用了際只用了505千噸千噸, 因此不需要增加鐵因此不需要增加鐵 路的運輸能力路的運輸能力. （7）為了從貝德）為了從貝德 福德礦業(yè)公司或加福德礦業(yè)公司或加 斯頓礦業(yè)公司獲得斯頓礦業(yè)公司獲得 更多的煤，斯蒂芬更多的煤，斯蒂芬 愿意簽訂一個比較愿意簽訂一個比較 高的價格協(xié)議嗎？高的價格協(xié)議嗎？ 如果回答是肯定的如果回答是肯定的 ，那么他應該愿意，那么他應該愿意 支付的價格是多少支付的價格是多少 ？ 答答:可以增加貝德可以增加貝德 福德礦業(yè)公司或加福德礦業(yè)公司或加 斯

15、頓礦業(yè)公司的采斯頓礦業(yè)公司的采 購量購量,其價格分別其價格分別 為為51.5美元美元/噸和噸和 73.5美元美元/噸噸 案例案例 二：二： 最優(yōu)季度生產(chǎn)供貨方案最優(yōu)季度生產(chǎn)供貨方案 某柴油機廠接到的客戶訂貨合同規(guī)定必須在各季度交貨的柴油機生某柴油機廠接到的客戶訂貨合同規(guī)定必須在各季度交貨的柴油機生 產(chǎn)任務各不相同，與此同時，由于種種原因該廠的季度生產(chǎn)能力與產(chǎn)任務各不相同，與此同時，由于種種原因該廠的季度生產(chǎn)能力與 單臺柴油機的生產(chǎn)成本也隨季度而變化。各季度的合同交貨任務、單臺柴油機的生產(chǎn)成本也隨季度而變化。各季度的合同交貨任務、 生產(chǎn)能力與單臺柴油機生產(chǎn)成本數(shù)據(jù)如下表所示生產(chǎn)能力與單臺柴油機生

16、產(chǎn)成本數(shù)據(jù)如下表所示 季度交貨任務（臺）生產(chǎn)能力（臺）生產(chǎn)成本（萬元/臺） 1102510.8 2153511.1 3253011.0 4201011.3 每臺柴油機在倉庫中保存一個季度的儲存成本為每臺柴油機在倉庫中保存一個季度的儲存成本為0.15萬元萬元.由于交貨由于交貨 任務與生產(chǎn)成本隨季度而變任務與生產(chǎn)成本隨季度而變,工廠為了降低成本必須恰當?shù)匕才鸥鱾€工廠為了降低成本必須恰當?shù)匕才鸥鱾€ 季度的生產(chǎn)數(shù)量季度的生產(chǎn)數(shù)量(例如在成本較低的季度多生產(chǎn)一些以便用來滿足例如在成本較低的季度多生產(chǎn)一些以便用來滿足 成本較高的后續(xù)季度的合同需求成本較高的后續(xù)季度的合同需求)才能降低成本才能降低成本.試確

17、定在保證完成試確定在保證完成 合同交貨任務的前提下使工廠全年生產(chǎn)與儲存成本達到最低的各季合同交貨任務的前提下使工廠全年生產(chǎn)與儲存成本達到最低的各季 度柴油機的生產(chǎn)安排度柴油機的生產(chǎn)安排 分析：分析： 交貨季度交貨季度 生產(chǎn)季度生產(chǎn)季度 1234生產(chǎn)能力生產(chǎn)能力 1X11X12X13X1425 2-X22X23X2435 3-X33X3430 4-X4410 交貨任務交貨任務10152520 交貨季度交貨季度 生產(chǎn)季度生產(chǎn)季度 1234生產(chǎn)能力生產(chǎn)能力 110.810.8+0.1510.8+0.310.8+0.4525 2-11.111.1+0.1511.1+0.335 3-11.011.0+0

18、.1530 4-11.310 交貨任務交貨任務10152520 決決 策策 變變 量量 成成 本本 理論模型理論模型 11121314 222324 3334 44 11121314 222324 3334 44 11 1222 132333 14243444 min10.810.9511.111.25 11.111.2511.4 1111.15 11.3 25 35 30 10 10 15 25 20 Zxxxx xxx xx x xxxx xxx xx x x xx xxx xxxx 生產(chǎn)能力限制生產(chǎn)能力限制 交貨量限制交貨量限制 電子表格模型電子表格模型 單位成本交貨季度 生產(chǎn)季度季度1

19、季度2季度3季度4 季度110.810.9511.111.25 季度2-11.111.2511.4 季度3-1111.15 季度4-11.3 決策變量交貨季度 生產(chǎn)季度季度1季度2季度3季度4實際生產(chǎn)總量生產(chǎn)能力 季度110100525=25 季度205005=35 季度30025530=30 季度40001010=3% 液體洗滌劑3%2%18%=18% 洗衣粉-1%4%8%=4% 總成本 電視印刷媒體($millions) 廣告數(shù)量4310 單位廣告增加的市場占有率 電子表格模型電子表格模型: 案例研究之二：復雜的廣告組合問題案例研究之二：復雜的廣告組合問題 Pronuevo公司是一家小公司

20、，它最近將一種新產(chǎn)品投放到某公司是一家小公司，它最近將一種新產(chǎn)品投放到某 個地區(qū)的市場中個地區(qū)的市場中,并且希望通過各種媒體對此產(chǎn)品進行宣傳。因此該并且希望通過各種媒體對此產(chǎn)品進行宣傳。因此該 公司與當?shù)氐囊患覍ｉT從事這種地區(qū)宣傳的廣告代理商公司與當?shù)氐囊患覍ｉT從事這種地區(qū)宣傳的廣告代理商PRCo進行進行 了聯(lián)系，并將此任務完全托付給對方，預算金額總數(shù)為了聯(lián)系，并將此任務完全托付給對方，預算金額總數(shù)為250,000歐歐 元。此廣告代理商對當?shù)厥袌鲇谐浞值牧私?，即了解通過各種媒體，元。此廣告代理商對當?shù)厥袌鲇谐浞值牧私?，即了解通過各種媒體， 如雜志，廣播電臺，或電視臺等進行的宣傳能夠讓多少人了解

21、此產(chǎn)如雜志，廣播電臺，或電視臺等進行的宣傳能夠讓多少人了解此產(chǎn) 品。廣告公司建議在六種不同的媒體上進行兩個月的宣傳。對于每品。廣告公司建議在六種不同的媒體上進行兩個月的宣傳。對于每 種媒體，廣告公司都了解在其上進行廣告的成本以及此媒體能夠影種媒體，廣告公司都了解在其上進行廣告的成本以及此媒體能夠影 響到的人數(shù)。此外每種媒體的影響指數(shù)也已知。響到的人數(shù)。此外每種媒體的影響指數(shù)也已知。 廣告公司也了解每種媒體的最大使用量（如，電視臺廣告播放廣告公司也了解每種媒體的最大使用量（如，電視臺廣告播放 次數(shù)不能超過次數(shù)不能超過8次）。下面的表列出了這些信息。次）。下面的表列出了這些信息。Pronuevo公

22、司希公司希 望此廣告宣傳計劃至少能夠影響望此廣告宣傳計劃至少能夠影響100,000人。應如何選擇這些媒體人。應如何選擇這些媒體 的組合才能夠使廣告的總影響指數(shù)最高？的組合才能夠使廣告的總影響指數(shù)最高？ 編號編號 媒體類型媒體類型 影響人數(shù)影響人數(shù) 單位費用單位費用 最大使用量最大使用量 影響指數(shù)影響指數(shù) 1 周報周報 12,000 1,500 4個星期個星期 3 2 月刊月刊 1,500 8,000 2個月個月 7 3 周刊周刊 2,000 12,000 8個周期個周期 8 4 電臺廣播電臺廣播 6,000 9,000 60次播放次播放 2 5 4*3米的戶外廣告牌米的戶外廣告牌 3,000

23、24,000 4個廣告牌個廣告牌 6 6 電視臺電視臺 9,000 51,000 8次播放次播放 9 分析：決策變量：每種類型廣告使用量分析：決策變量：每種類型廣告使用量 目標：影響總指數(shù)最高目標：影響總指數(shù)最高 約束：影響人數(shù)限制，預算資金限制，最大使用量限制約束：影響人數(shù)限制，預算資金限制，最大使用量限制 編號編號 媒體類型媒體類型 影響人數(shù)影響人數(shù) 單位費用單位費用 最大使用量最大使用量 影響指數(shù)影響指數(shù) 1 周報周報 12,000 1,500 4個星期個星期 3 2 月刊月刊 1,500 8,000 2個月個月 7 3 周刊周刊 2,000 12,000 8個周期個周期 8 4 電臺廣

24、播電臺廣播 6,000 9,000 60次播放次播放 2 5 4*3米的戶外廣告牌米的戶外廣告牌 3,000 24,000 4個廣告牌個廣告牌 6 6 電視臺電視臺 9,000 51,000 8次播放次播放 9 理論模型理論模型 123456 123456 123456 123456 max378269 121.52639100 1.581292451250 4,2,8,60,4,8 Zxxxxxx xxxxxx xxxxxx xxxxxx 廣告宣傳問題廣告宣傳問題 媒體類型周報月刊周刊電臺廣播戶外廣告牌電視臺實際總數(shù)可用資源 影響人數(shù)12000150020006000300090001030

25、00=100000 單位費用150080001200090002400051000250000=250000 影響指數(shù)378269 媒體類型使用量 決策變量428440 = 最大使用量4286048 目標總指數(shù)122 編號編號 媒體類型媒體類型 影響人數(shù)影響人數(shù) 單位費用單位費用 最大使用量最大使用量 影響指數(shù)影響指數(shù) 1 周報周報 12,000 1,500 4個星期個星期 3 2 月刊月刊 1,500 8,000 2個月個月 7 3 周刊周刊 2,000 12,000 8個周期個周期 8 4 電臺廣播電臺廣播 6,000 9,000 60次播放次播放 2 5 4*3米的戶外廣告牌米的戶外廣告

26、牌 3,000 24,000 4個廣告牌個廣告牌 6 6 電視臺電視臺 9,000 51,000 8次播放次播放 9 最優(yōu)方案：最優(yōu)方案： Components of the Model LP模型的組成部分模型的組成部分 Decision variables 決策變量決策變量 Objective function 目標函數(shù)目標函數(shù) Constraints 約束約束 Mathematical Statement of LP Problem 線性規(guī)劃的數(shù)學描述線性規(guī)劃的數(shù)學描述 線性規(guī)劃要確定決策變量線性規(guī)劃要確定決策變量 x1, x2, , xn 使得使得 Maximize Z c1x1cnxn

27、 Objective Function subject to a11x1a1nxn b1 a21x1 a2nxn b2 M am1x1 amnxn bm Functional Constraints and x1 0,xn 0 Nonnegativity Constraints 已知參數(shù)已知參數(shù) c1, , cn ; a11, , amn ; b1, , bm. Assumptions of Linear Programming 線性規(guī)劃的假設線性規(guī)劃的假設 Linearity 線性線性 Divisibility 可分性可分性 Certainty 確定確定性性 Nonnegativity 非負性非負性 Why Use Linear Programming? 為什么要使用線性規(guī)劃為什么要使用線性規(guī)劃 線性規(guī)劃很容易而有效率地被求解線性規(guī)劃很容易而有效率地被求解 如果存在最優(yōu)解，則肯定能夠找