Dual Problem

對偶問題

Dual Conversion Step by Step

對偶轉換操作步驟與技巧

回原處

回目錄

Statistics Ch01 Introduction

統計入門導論

有『不相信』的問題，再去收集資料，找出答案－就是統計

上一篇

回目錄

下一篇

期中作業的第1題說明

(最後更新日: 2011.11.18)
1.
Roddy Mikks公司是一家生產室內，外油漆的公司。這兩種漆的原料為M1及M2，資料如下：
該公司室內漆的每日需求量最多不超過2噸。此外，室內漆每日需求量不會超過室外漆1噸，該公司應如何生產室內，外漆才能使得每天利潤總和為最大？

以下為主要解題模型:

[L1] max=5*x1+4*x2; [L2] 6*x1+4*x2<=24; [L3] x1+2*x2<=6; [L4] -x1+x2<=1; [L5] x2<=2; [L6] x1>=0; [L7] x2>=0;

以下為解題模型 Solutioin Report:

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(a) 請說明x1與x2所得之Value: 3, 1.5意義
(b) 請驗證slack中，row 3為0, row 4為2.5. 並說明其意義。
(c) 請驗證dual price中，row 2為0.75, row 3為0.5. 並說明其意義。
(d) 請驗證reduced cost中，x1為0, x2為0, 並說明其意義。
(e) 請說明何種情況下存在多重解，如何求解多重解。

解答都在《Solution Report 的說明》和《Range Report 的說明》

回到目錄

管理科學作業一的第6題解答

(最後更新日: 2011.11.11)
6.
四種產品的生產皆需經兩機器加工，下表為各產品在這兩部機器加工的時間及機器每小時之運轉成本：

以下為主要解題模型:

!- - - - 目標式(各產品的最大利潤加總金額)  - - - -; [GOAL]  max=(65-(2*10+3*5))*prod1+(70-(3*10+2*5))*prod2+(55-(4*10+1*5))*prod3+(45-(2*10+2*5))*prod4; !- - - - 限制式M (各生產線投入生產的產能限制) - - - -; [LINE1] 2*prod1+3*prod2+4*prod3+2*prod4<=500; [LINE2] 3*prod1+2*prod2+1*prod3+2*prod4<=380;

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(a) 請建構該問題的模型使利潤最大。

最大值(利潤)是 5280
其中 產品1生產28個；產品2生產148個；其它沒生產。

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(b) 若超出機器1,2產能的部分只能透過加班，請問公司每小時最高成本為何?


看 Line1和Line2 的 Dual Price 均為6，代表產能每加1產能則利潤加6。所以每小時加班最高成本是6 元。

(PS. 問老師中....是否應加上原機器成本，才會是最後的加班成本上限)

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(c) 產品3的每位機器成本應降為多少才有利潤?

看Prod3的Reduced Cost 的值為20，故將產品3的成本減20。就達生產的效益。產品3變成生產74個。

!- - - - 目標式(各產品的最大利潤加總金額)  - - - -; [GOAL]  max=(65-(2*10+3*5))*prod1+(70-(3*10+2*5))*prod2+(55-((4*10+1*5)-20))*prod3+(45-(2*10+2*5))*prod4;

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(d) 在原模型中，若假設產品1,3,4的售價分別改變成80元,65元及60元，請問產品2的售價訂為多少仍可維持目前的解。

就是將利潤設定為5280進行運算。可以看到會變成生產產品4共176個，其中產品2為0個，且Reduced Cost 也為0。故改變產品2的售價並沒法維持目前設定的利潤。

!- - - - 目標式(各產品的最大利潤加總金額)  - - - -; [GOAL]  max=(80-(2*10+3*5))*prod1+(70-(3*10+2*5))*prod2+(65-(4*10+1*5))*prod3+(60-(2*10+2*5))*prod4; !- - - - 限制式V (限制最大利潤) - - - -; [FIXVALUE] (80-(2*10+3*5))*prod1+(70-(3*10+2*5))*prod2+(65-(4*10+1*5))*prod3+(60-(2*10+2*5))*prod4=5280;

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(e) 若機器1的產能增加為550個，請問機器2的產能在哪個區間內變動時，不會改變原始解。


可以看到最多為增加445，最少為減少13.3

!- - - - 限制式M (各生產線投入生產的產能限制) - - - -; [LINE1] 2*prod1+3*prod2+4*prod3+2*prod4<=550;

回到目錄

管理科學作業一的第4題解答

(最後更新日: 2011.11.11)
4.
Fox公司正規劃未來四內年的六項計劃，Fox公司被授權可部分承攬或完全承攬這些計劃，期望報酬，每一項計劃的現金支出如下表。若採部分承攬計劃，將依適當的比例來分配其報酬及現金支出。

以下為主要解題模型:

!- - - - 目標式(各專案的最大報酬加總金額)  - - - -; [Goal] max=32.4*prj1+35.8*prj2+17.75*prj3+14.8*prj4+18.2*prj5+12.35*prj6; !- - - - 限制式P (各專案各年度投入金額) - - - -; [Prj1Cost] 10.5*prj1+14.4*prj1+2.2*prj1+2.4*prj1<=29.5; [Prj2Cost] 8.3*prj2+12.6*prj2+9.5*prj2+3.1*prj2<=33.5; [Prj3Cost] 10.2*prj3+14.2*prj3+5.6*prj3+4.2*prj3<=34.2; [Prj4Cost] 7.2*prj4+10.5*prj4+7.5*prj4+5*prj4<=30.2; [Prj5Cost] 12.3*prj5+10.1*prj5+8.3*prj5+6.3*prj5<=37; [Prj6Cost] 9.2*prj6+7.8*prj6+6.9*prj6+5.1*prj6<=29; !- - - - 限制式Y (每年可分配給各專案的基金)  - - - -; [Year1] 10.5*prj1+8.3*prj2+10.2*prj3+7.2*prj4+12.3*prj5+9.2*prj6<=60; [Year2] 14.4*prj1+12.6*prj2+14.2*prj3+10.5*prj4+10.1*prj5+7.8*prj6<=70; [Year3] 2.2*prj1+9.5*prj2+5.6*prj3+7.5*prj4+8.3*prj5+6.9*prj6<=35; [Year4] 2.4*prj1+3.1*prj2+4.2*prj3+5*prj4+6.3*prj5+5.1*prj6<=20;

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(a) 建構一模型決定如何安排這些計劃使其總報酬為最大。

最大值(報酬)是 116.0611
其中 Prj5 為部份承攬；Prj6為沒執行

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(b) 假設除非計劃6被部份承攬，否則計劃2不可部份承攬。請修正模型並求解。

這題中文題意會讓人誤會。
正確題意為：除非專案6沒全做(!=1)，不然專案2就得全做(=1)。
Ps. 雖然解題的限制式直覺有缺陷，但從邏輯角度看是對的。

!- - - - 限制式Q[b] (第二小題所加限制式)  - - - -; [Q2_L1] prj6>=prj2;

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(c) 第4年要借錢，值得嗎?

請看Row欄的[Year4] 該行就指出了，每增加1單位會增加 2.888889的利潤；
自然多借幾元來花投入是值得的。


※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(d) 假設在任何一年基金有剩下，將馬上被下個年度所使用，請求新的最佳解並分別求出從前一年借多少錢?

我們令balance1為第1年剩下的結餘款，則原第1年投入應為

{第1年實際投入}+{第1年結餘款}=60
→ {第1年實際投入} = 60 – balance1；

接著令balance2為第2年結餘款，則第2年投入應為

{第2年實際投入}+{第2年結餘款}=70+{第1年結餘款}
→ {第2年實際投入} = 70 + balance1 - balance2；

以下類推

!- - - - 限制式Q(d) Y (每年可分配給各專案的基金, 但加上前期結餘)  - - - -; [Q4_Year1] 10.5*prj1+8.3*prj2+10.2*prj3+7.2*prj4+12.3*prj5+9.2*prj6=60-balance1; [Q4_Year2] 14.4*prj1+12.6*prj2+14.2*prj3+10.5*prj4+10.1*prj5+7.8*prj6=70+balance1-balance2; [Q4_Year3] 2.2*prj1+9.5*prj2+5.6*prj3+7.5*prj4+8.3*prj5+6.9*prj6=35+balance2-balance3; [Q4_Year4] 2.4*prj1+3.1*prj2+4.2*prj3+5*prj4+6.3*prj5+5.1*prj6=20+balance3-balance4;

年度	結餘款	向前期的借款 (前期結餘-本期結餘)	說明
1	4.96	0	因為第一年沒人借它
2	7.62	0	因為第二年結餘款還超過前期的，表示剩很多錢沒用，根本不必動前期結餘
3	4.62	3	結餘變少了，表示有動用
4	0	4.62	沒結餘了，表示把前面的都用光了

故只有第3年、第4年有借用前期結餘


※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
(e) 假設前三年的可用基金超出表中規定的金額，因此，若有此需要則可向公司內部其他財務活動挪借。請重新建構模型並求解，請問新的最佳解需每年都借錢嗎?

依題意在每年後面加上一筆借款loan。
Ps. 這部份有個重點，就是每年都要加，不能只借前三年。根據實驗，這樣Lingo才會跑。
Ps. 從模型推測，當第四年需要借款，但沒借的話，變成第三年也不需借就可達到最高報酬。

!- - - - 限制式Q(e) Y (每年可分配給各專案的基金, 但加上每期對外的借款)  - - - -; [Q5_Year1] 10.5*prj1+8.3*prj2+10.2*prj3+7.2*prj4+12.3*prj5+9.2*prj6<=60+loan1; [Q5_Year2] 14.4*prj1+12.6*prj2+14.2*prj3+10.5*prj4+10.1*prj5+7.8*prj6<=70+loan2; [Q5_Year3] 2.2*prj1+9.5*prj2+5.6*prj3+7.5*prj4+8.3*prj5+6.9*prj6<=35+loan3; [Q5_Year4] 2.4*prj1+3.1*prj2+4.2*prj3+5*prj4+6.3*prj5+5.1*prj6<=20+loan4;

故發現只有第 3年和第 4年貸款不為0。

回到目錄

管理科學作業一的第10題解答

(最後更新日: 2011.11.19 00:09)
10.
Roddy Mikks公司是一家生產室內，外油漆的公司。這兩種漆的原料為M1及M2，資料如下表。
該公司室內漆的每日需求量最多不超過2噸。此外，室內漆每日需求量不會超過室外漆1噸。
公司考慮生產一較便宜品牌的室外漆，其每產量需要的投入為原料M1和M2各0.75噸。新的室外漆每噸的利潤為$3500。
該公司應如何生產室內，外漆才能使得每天利潤總和為最大？

以下為主要解題模型:

!- - - - 目標式(各油漆的最大生產利潤加總金額)  - - - -; [GOAL] max=5*painto + 4*painti + 3.5*paintn; !-利潤單位千元; !- - - - 限制式 (各原料投入生產油漆的限制) - - - -; [M1] 6*painto + 4*painti + 0.75*paintn <=24; !-原料M1的分配; [M2] painto + 2*painti + 0.75*paintn <=6; !-原料M2的分配; [Limit_i] painti <=2; !-室內漆需求上限為2; [Limit_o] painti - (painto + paintn) <=1; !-室外漆需求比室內漆少1以內; [v1] painto >=0; [v2] painti >=0; [v3] paintn >=0;

(註: Limit_o 的限制式和老師的解不同, 故請自行決定那種, 後果自付.   哈~)


※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
解答說明


在僅生產原室外漆3.6噸加上新的室外漆3.2噸時，
可獲得最高利潤 29200 元

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
對偶解轉換過程

※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※ ※
對偶解


簡單的說，就是改找出最小的成本組合

以下為主要對偶題模型:

!- - - - 目標式  - - - -; [GOAL] min=24*y1+6*y2+2*y3+y4; !- - - - 限制式  - - - -; [L2] 6*y1+y2-y4>=5; [L3] 4*y1+2*y2+y3+y4>=4; [L4] 0.75*y1+0.75*y2-y4>=3.5;

以下是倆個 Solution 的對應

回到目錄

Management Science Catalog

管理科學

Objective of The Course

課前準備與其他	Lingo 的 Solution Report 的說明 Lingo 的 Range Report 的說明 MS Excel規畫求解 (Solver)
Linear programming: application problems	解聯立方程式 矩陣 線性規畫
Dual problem analysis	對偶問題 〔對偶化轉換技巧說明〕
回家作業一 題解	第 4題 ∥ 第 6題 ∥ 第 10題
期中作業 說明	第 1 題
Duality and sensitivity analysis	----
Goal programming	----
Integer linear programming: application problems	----
Solution algorithm for integer programming	----
Decision analysis	----
Game theory with application problems	----

Textbook:
Hamdy A. Taha, Operations Research- an introduction, 2007, Prentice Hall.

References:
Optimization Modeling with Lingo, 1999, LINDO System INC.

我的參考書:
(1) 管理數學－現代管理數學及其應用, Lial 等著, 朱蘊鑛譯, 2008, 台灣培生
(2) 管理科學概論, Hillier等著, 陳明德譯, 2009, 麥格羅希爾
(3) 作業研究, 陳坤茂著, 2005, 華泰

Statistics

統計學 [NTUT]

課程目的
本課程之目的在訓練學生，使學生熟悉經常使用之統計方法與理論，能利用已知之資料整理、分析未知之現象，建立修習其他相關學科之基礎。課程內容包括：機率理論、推定、假設檢定等。

第一章 第二章 第三章	統計入門	----
第四章	常見的統計圖表	----
第五章	統計測量數	----
第六章	機率	----
第七章	---	----
第八章	---	----
第九章	---	----
第十章	---	----
第十一章	---	----
第十二章	---	----

教科書
應用統計學，第四版，林惠玲、陳正倉，雙葉書廊有限公司。