線性規劃理論、建模與實作-職治系三年級 萬 柔
課程名稱►線性規劃理論、建模與實作 授課教師►數學系 許瑞麟老師
心得分享者►職治系三年級 萬 柔
「線性規劃理論、建模與實作」這門課帶大家認識線性規劃的理論與應用、搭配簡單的AMPL程式語言來幫忙求解。這堂課是英文授課，授課老師是數學系，許瑞麟教授。五天的課程環環相扣，讓修完微積分後就沒碰過數學的我從零開始認識線性規劃、學習線上程式neos的運用。這堂課比起上數學課，更像是在練習邏輯思考。每天的作業都能利用所學搭配新學到的內容，經過縝密的思考、假設，求得最佳解。
對我來說貫穿這堂課的核心元素是極值（最大值或最小值）、矩陣，以及neos的使用。第一堂課的最開始介紹名詞：feasible domain, constraint set, 我們想求極值的object function，再利用數學符號來表示出我們要求的極值。再來介紹線性規劃的內容，以及線性函數的數學特徵：additivity和constant returns to scale。再講述線性的constraint set：多面體結構，並以matrix來簡化方程式的表達。以上建構了我們接下來的課程核心列式：
maximize( minimize) cTx
subject to Ax≤(≥)b
以及最常提到的 x≥0
Data( A,b,c) 可以決定一個線性規劃的問題。
第一天介紹基本的矩陣計算。在上這堂課之前，我的數學最高修課經歷就是工學院大一微積分，所以上課簡報每個字我都要好好研究其意義。上課例題不難理解，但到了要使用neos來自己動手寫程式、做作業，尤其上課的例題講的是將食物營養成分以矩陣列式，回家作業突然變成以SVM( support vector machine) 求分割兩群數據的一條線，對一個數學沒有太多基礎、大學又沒修過程式相關課程的人來說實在是驚悚萬分。五天的作業令人印象非常深刻。每一張簡報、作業內容都是我下課、放學回家、甚至是晚上在Discord向助教和一起修課的同學討教才弄懂，成功自己寫出來的。
第一天的作業最重要的就是讓我認識neos這個求解線性規劃的套件。neos的運算需要三個檔案，第一個檔案的set表示已知的集合（物品）、param是不變的參數、var是變數、{}定義了內容、subject表示變數受限於題目的條件限制式、bounds表示變數的範圍。至於作業本身，一開始被support vector machine嚇到，畢竟那幾張簡報大概是整堂課出現最多新符號、新名詞的部分。但仔細研究後發現其實SVM只是尋找分割兩組座標群的界線，利用線性規劃來求界線到群體中的最大的範圍，也就是margin，而作業就是算點到線的y方向距離求極值。列完式準備代入neos時我也卡了很久，問了同學才比較懂程式裡各名詞（如：set, param…）的意思，並反覆琢磨簡報關於矩陣寫成程式的那幾頁，釐清各代數的意思，才成功設定好矩陣的行跟列，最後順利用neos將程式跑出來，實在得來不易。第一天的課程對於沒接觸過線性代數又不會寫程式的我真的是兩頭燒，但完成這份作業對於我之後上課的理解幫助很大，尤其是每份有關neos的作業，都是參考第一份作業的經驗寫出來的。從第一天寫了五個小時、東問西問才生出來，到自己寫完請同學陪我找問題，最後可以完全靠自己完成，很明顯地感受到自己的進步！
第二天的前半段講述了關於存貨庫存的問題，將目標函數列式出來是要考慮絕對值與連加。而絕對值並不是線性函數，因為不符合兩條規則中的additivity。然而將絕對值轉換成更高維度的線性函數使用了讓人印象深刻的技巧：重新定義出兩個新的未知數，藉此擺脫絕對值。這樣的技巧是利用值域互通，然後一步步做問題轉換，從起始帶有絕對值的原始問題(INV0)，(INV1)，列一個等價的線性規劃問題(INV2)。後半段介紹max flow in the network，是一種尋找最佳網路流量路徑的題目。這題令我印象最深刻的是 max-flow-min-cut theorem，當尋找最大流量時，將節點分割出邊界飽和的兩群，就可以根據nodes和edges訂好範圍，然而推導過程很長。第二天的課程還算愉快！至少作業像是複習第一天的內容，很快就可以完成。但在動筆前，我還在糾結前面所說「重新設定出兩個未知數，藉此擺脫絕對值以方便使用一般線性的連加」，因為作業中不像例題是單純未知數的轉換，還包含了常數。那麼絕對值中的常數要怎麼考慮呢？這時就要回歸這個技巧的重點：利用等號兩側值相同。就像電位一樣是要求相對的值，我們新設的未知數已經包含常數造成的平移了！思考題目的過程中我常常蹦出奇怪的問題打擾助教，助教好像也沒有想過這種一般人不會考慮的問題。還有很多有趣的問答但就不一一舉例了，第二天也算是有突破自己的一天！
第三天開始介紹set-covering problem，用到的技巧有點像是前兩天的總集合，要考慮矩陣列式還有連加，還再多加一個有或無( 0v1) 的條件。然而上課例題是求裁切紙捲的最節省方式，但作業卻出了一題飛機航班的排班問題，真是令人意想不到。飛機的排班問題題目敘述很長，讓人搞不太懂哪些是自己要選取的元素、哪些要設成邊？那些要設成點？多虧助教願意晚上花時間線上帶我釐清觀念！雖然我覺得這題要討論的東西還很多，而不像現在聽到的最佳解法只考慮每條航線站數增減，而是要考慮更多的排列組合（比如ABCBDA好像就沒有被考慮到），但這天因為有兩份作業搞太晚就不了了之，有點遺憾，也希望之後有機會的話可以公布各題目的最佳解法。另一題是在討論simplex method中basic solution in {Ax=b,x≥0}，用了很多矩陣、運算、在平面畫圖求解，將變量區分成xB、xN，最後將目標式轉換成xN變量求極值。這題寫出來很~長，題目是要求用x2、x3作為起始basic variables，整個算完後聽助教說如果要求極值的話用x2、x3不是最好的選擇。所以我用x1、x3重新算了一次，出來卻是-5（那題答案是175）。隔天再問助教才知道原來課堂介紹的式子只有考慮代x的數字求的極值，沒有考慮常數項。我用x2、x3計算的式子剛好有180的常數，配合重新計算的-5，答案才是175！煩惱一個晚上找不到自己錯在哪，這樣的發現真的是太令人感動了。這樣額外的收穫也是一種願意多花心思的回報吧。
第四天介紹duality。雖然第一次學但我覺得蠻有趣的，寫作業的時候也有step by step列出轉換的過程，也有好好搞懂求最大最小、放≥≤=對式子造成的影響。課程後面介紹linear program(P)和其對偶問題dual(D)我聽得很茫然，是靠同學畫出了兩條二次曲線最大最小的圖才比較懂infeasible, unbounded, normal的定義，雖然還是一知半解。聽到Farkas Lemma的部分大概是我五天課程最驚悚的時候了，這個觀念也是我問修過類似課程的同學才聽得懂：c是一個由幾個向量a圍出的圓錐，而b是一個向量，當b在c範圍內時可表示成Ax=b, x≥0有解，但若b不在c裡面則無解，且b與c有一超平面h(x)可以切割。這天的作業完成得很快！相較於前三天有漸入佳境的感覺。Duality的變換寫得很順、作業涉及Farkas Lemma的部分也是只有運用前面說到的觀念以矩陣列式，而做三條線求出存在的解並以neos得到答案的那題我完成得很快！雖然是相對簡單的，卻有種靈活運用的感覺！
最後一天的game theory是我聽得很快樂的主題，唯一一堂沒有什麼問題、寫作業還是前幾個寫完的！非常快樂！兩人零和賽局x, y一開始是列出矩陣，要注意的是課堂例題與練習都列的是以玩家x的角度去思考，釐清這樣的觀念對理解後面提到列誰的max誰的min非常重要！再後面就是同時考慮兩個玩家x, y的列式，就是希望在最悲觀的狀況下做出最好的選擇，算出來的結果其實是決策的期望值，當x最悲觀與y最悲觀的情況下各自算出來最佳期望值相等時則達成納許均衡，而納許均衡最後卻還成囚徒困境，很有趣！這天上課的內容主要就是賽局論的應用，我都可以理解上課例題的內容，而且兩題回家作業都很快地列出各條件並做完，寫完的時候看到其他同學都還在寫真的是非常有成就感。不光是內容有趣、賽局論應用對我來說也特別的貼近生活，是所有課堂主題中我最喜歡的！
這堂課的修課心得真的是五味雜陳。上課五天有四天我都在偷偷掉眼淚。我除了大一在資源系讀了一年後大二就轉到職治系，從此再也沒有碰過數學。聽雙主修工資管的朋友說前四天內容他們上課都有教過、只是沒講的那麼數學；或是看大家好像都聽得懂，每次下課跟下午的助教課都只有我在問問題就特別挫折。而且我是比較喜歡中文授課的人，這堂課不只英文授課、上數學課還涉及寫程式，完全集結了我過去最害怕的課程內容，所以我絕對不能退選而且絕對不能混過去！五天課程結束除了真的有學到知識外也是另類的突破自己、感受到自己的進步，可說是收穫滿滿！
現在回頭看發現課程安排其實很棒，就像前面說的，我每天的作業都有用到前面教到的技巧，這堂課的元素也很明確：線性規劃、矩陣、neos，至少我覺得這幾項都是一直重複，所以有好好跟上的話就可以很顯著感受到自己有在進入狀況（從第一天功課寫幾個小時到最後可以是班上前幾個寫完，連一起修課的同學都很驚訝）。每天要完成作業的當下真的是怕到不行，我寫得特別慢、特別久又愛鑽牛角尖，可是現在很謝謝願意把每句話弄懂的自己，至少重新回頭看我都可以再完成一次作業，而且知道每句話的意思，甚至有些說不定是老師課堂沒有特別提、但因為有和助教討論所以發現的細節。最後看著自己這五天的筆記與作業的紀錄真的是很感動，這禮拜是我暑假最有價值的日子！
謝謝許瑞麟老師準備那麼扎實的課堂內容（真的是非常非常充實，每天都上超久。我自己都累了何況是在台上一直講課的老師），每一個小主題都有很細膩的推導過程，雖然作業沒有全部出現，但課堂上聽老師一點一點抽絲剝繭、搭配一點熟悉的高中數學，也是印象深刻、收穫頗豐。最剛開始還會因為英文授課而想打退堂鼓，但因為內容扎實的簡報、課堂間偶爾的中文小提醒、以及課後助教們耐心解惑，總能解答我的十萬個為什麼。當然還有陪我一起修課還願意花時間回答我問題的好朋友，如果每天課後沒有他幫忙解惑，助教可能會被我煩死、我自己也會被自己給急死吧。我真的很喜歡這堂課！明年暑假要去實習應該沒有機會再修模組化課程了，幸好這學期有勇敢嘗試而且沒有半途而廢，真的是太好了哇！
瀏覽數:
分享