线性规划概论ppt课件.ppt

《线性规划概论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章線性規劃概論IntroductiontoLinearProgramming作業研究（華泰）20192021/7/301章節大綱前言典型範例圖解法線性規劃模式的形式線性規劃模式的解線性規劃的假設線性規劃模式的範例22.1前言線性規劃（linearprogramming）簡稱LP線性（linear）：模式中所有函數均為線性函數規劃（planning）：指活動的規劃線性規劃屬數學規劃（mathematicalprogramming，MP）MP：將問題以目標函數及限制式表達的數學模式LP：MP的所有數學式均為線

2、性32.2典型範例某公司生產兩種產品P1及P2，需要使用兩部機器M1與M2，每箱利潤為$7000及$8000，詳細資料如下表，每週應分別生產多少箱的P1及P2，才能獲得最大的利潤？生產1單位所需產能機器P1P2可用產能M11210M23218單位利潤$7,000$8,0004建立LP模式四個步驟定義決策變數寫出此問題的目標函數，並決定是予以極大化或極小化寫出各功能限制式決定各變數是否具有非負限制式或不受正負限制5Sec.2.22.2典型範例LP模式：62.3圖解法（graphicalmethod）三個步驟：繪

3、製非負限制式（或不受正負限制）的範圍繪製各功能限制式的範圍，並決定可行區域繪製目標函數的線條，並決定最佳解7以圖解法求解典型範例08108642642(4,3)8Sec.2.32.4LP模式的形式標準形式9專有名詞目標函數（objectivefunction）目標函數值（objectivefunctionvalue）目標函數係數限制式係數右手邊常數（right-hand-sideconstant；RHS）限制式（constraint）功能限制式（functionalconstraint）非負限制式（non-n

4、egativityconstraint）10Sec.2.4其他形式目標可以是極小化限制式可以是「大於等於」或「等於」變數可以無非負限制式不受正負限制（unrestrictedinsign）或不受限（unrestricted）11Sec.2.42.5線性規劃模式的解解（solution）包含所有變數的任何特定值可行解（feasiblesolution）滿足所有限制式不可行解（infeasiblesolution）至少違反其中一個限制式的解最佳解（optimalsolution）在所有可行解中，具有最有利目標函數

5、值的解12LP問題四種可能解唯一最佳解（uniqueoptimalsolution）僅有一個最佳解多重最佳解（multipleoptimalsolutions）or擇一最佳解（alternativeoptimalsolutions）有無限多個目標函數值相同的最佳解無可行解（nofeasiblesolutions）簡稱無解沒有任何可行解無窮解（unboundedsolution）對於極大化問題，對於極小化問題，13Sec.2.5多重最佳解的情況064264214Sec.2.5無可行解的情況064264215Se

6、c.2.5無窮解的情況064264216Sec.2.52.6線性規劃的假設成比例性proportionality各個項目對於該函數的貢獻和變數之值成比例可加性additivity函數的各項目彼此獨立，因此可相互加減可分性divisibility所有變數都可以是任何實數值，而不必是整數確定性certainty所有係數均為已知的常數172.7線性規劃模式的範例混合問題人力安排問題飲食問題財務規劃問題18混合問題19Sec.2.7混合問題(1/2)定義決策變數：原油1用於生產產品A的桶數原油1用於生產產品B的桶數原

7、油2用於生產產品A的桶數原油2用於生產產品B的桶數成分的限制式產品A最低的辛烷含量是96，所以20Sec.2.7混合問題(2/2)LP模式：21Sec.2.7人力安排問題(1/2)問題考慮一家五星級飯店客房部的人力安排問題員工每週連續上班五天，然後休假兩天至少需雇用人，才能滿足人力需求？星期一二三四五六日人力需求1410111316201822Sec.2.7人力安排問題(2/2)定義：自星期開始上班的員工數LP模式：23Sec.2.7飲食問題(1/2)問題：狗主人每個月應如何以最低的狗糧費用餵食這三隻狗，並滿

8、足狗所需要的營養？24Sec.2.7飲食問題(2/2)定義：每月餵食每隻狗狗糧A的磅數每月餵食每隻狗狗糧B的磅數LP模式：最佳解：25Sec.2.7財務規劃問題(1/2)目前有4億的資金未來的第二、三、四年年初已確定各需支付1億四項計畫：計畫A：以一年為期，每期的預估報酬率為2.5%計畫B：以兩年為期，每期的預估報酬率為5.2%計畫C：以三年為期，每期的預估報酬率為8.5%計畫D：以四年為期，每期的