數(shù)學建模第三章線性模型

1、第二章 線性規(guī)劃模型 線性規(guī)劃是數(shù)學規(guī)劃中研究較早, 發(fā)展較快, 應用廣泛的的一個重要分支, 也是數(shù)學模型中的一項重要內容. 它在生產(chǎn)安排、物質運輸、投資決策、交通運輸?shù)痊F(xiàn)代工農業(yè)和經(jīng)濟安排、物質運輸、投資決策、交通運輸?shù)痊F(xiàn)代工農業(yè)和經(jīng)濟管理等方面都有著廣泛的應用. 我們知道, 在經(jīng)濟活動中提高經(jīng)濟效益一般可通過兩個途徑: 第一是加強技術方面的改造以降低生產(chǎn)過程中對資源的消耗從而降低制造成本; 第二是提高企業(yè)的管理, 即合理安排人力及物力，以降低企業(yè)的管理成本. 線性規(guī)劃最早由前蘇聯(lián)數(shù)學家康托羅維奇首先提出, 1947年美國數(shù)學家丹齊克提出了解決線性規(guī)劃的普遍算法單純形方法；1947年美國數(shù)學

2、家馮. 諾依曼提出了對偶理論并開創(chuàng)了線性規(guī)劃的許多新領域; 線性規(guī)劃的研究成果推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究.一 、線性規(guī)劃模型 一、模型的建立 我們從下面幾個例子引出線性規(guī)劃的模型. 問題一 某車間為其它部門生產(chǎn)200套鋼管三腳架, 每套由長度為2.9、2.1、1.5米的鋼管各一根組成. 已知原料鋼管的長度為7.4米, 如何確定鋼管的切割方案, 能使鋼管的利用率最高. 分析 首先對長度為7.4米的鋼管要確定合適的切割方案, 并使得每次切割后丟棄的原料盡可能少. 為此建立所有可能的切割方案:1.440080.831070.222061.10305030140

3、.911130.302120.11021余料1.52.12.9編號 以 表示在第 種方案下所使用的原料數(shù), 則一個合適的切割方案表現(xiàn)為而衡量方案好壞的評價指標為在該方案下所丟棄的余料數(shù), 即反映為余料函數(shù)由此得到該問題的數(shù)學表達式: 問題二 投資決策問題 某基金公司為擴展業(yè)務需要招聘部分基金經(jīng)理. 在業(yè)務考試中, 考官提出了這樣一個問題. 為公司制定一個五年期的投資計劃. 項目可供選擇：現(xiàn)已知有四個投資項目A: 于每年的年初可進行投資, 并于次年末完成, 投資收益為6%；項目B: 于第三年的年初進行投資, 并于第五年的年末完成投資, 投資收益為16.5%, 投資額不超過35萬；項目C: 于第二

4、年的年初進行投資, 并于第五年的年末完成成投資, 投資收益為21.5%, 投資額不超過40萬； 項目D: 于每年的年初可進行投資, 并于當年末完成, 投資收益為2.35%. 該公司現(xiàn)有資金120萬, 試為該公司制定投資計劃. 模型建立 以 代表年份, 分別表示4個項目, 表示在第 年對項目 的投資額. 顯然, 每年的資金必須全部用于某些項目的投資. 由條件所設知每年可行的投資計劃為第一年第二年第三年第四年第五年 投資收益函數(shù)為 由此得到該問題的數(shù)學模型 問題三 運輸問題產(chǎn)地的產(chǎn)量分別為對該類物資, 有 個需并設求點, 分別記為 需求量為又從產(chǎn)地 到需求點 的單位運輸成本為求相應的運輸方案. 設

5、有一種物資, 它有 個產(chǎn)地, 記為 模型建立 設 表示從產(chǎn)地 到需求點 的運輸量, 則合適的運輸方案表現(xiàn)為對產(chǎn)量的要求對需求量的要求 而相應的目標函數(shù)為 由此得到相應的數(shù)學模型為 思考 一般情況下, 產(chǎn)銷是不平衡的, 此時相應的模型將如何? 在上面例中, 目標函數(shù)及約束條件均為線性表達式, 故把這樣的模型稱為線性規(guī)劃模型. 定義 如下的一組數(shù)學關系式即稱為一個線性規(guī)劃或線性規(guī)劃模型 求解線性規(guī)劃的傳統(tǒng)解法是單純形法. 但單純形方法針 對的是線性規(guī)劃的標準型, 為此引入標準型（典式）的概念. 定義 具有如下形式的線性規(guī)劃為線性規(guī)劃的標準型: 對于非標準形式的線性規(guī)劃都可以經(jīng)過適當?shù)霓D換而化化為相

6、應的標準型.二、線性規(guī)劃的解法 1.解的概念 設線性規(guī)劃定義 設是 維實向量, 若 滿足,則稱 是線性規(guī)劃的一個解;若解 滿足, 則稱其為規(guī)劃的可行解; 可行解的全體稱為可行域;使規(guī)劃達到極值 的可行解稱為線性規(guī)劃的最優(yōu)解,相應的目標函數(shù)值稱為最優(yōu)解值. 2.圖解法 線性規(guī)劃的圖解法針對的是具有兩個決策變量的線性規(guī)劃問題. 設線性規(guī)劃 求解過程建立合適的坐標系統(tǒng);對約束條件 建立第 條直線 從而確定可行域;對等值線:由規(guī)劃的類型確定等值線移動方向, 則最優(yōu)解為等值線在移動過程中與可行域的最后交點. 例 求解規(guī)劃最后交點移動方向解 由圖中可以看到, 可行域為多邊形區(qū)域 最優(yōu)解為 最優(yōu)解值為 3.

7、單純形方法 設線性規(guī)劃并進一步假定約束條件系數(shù)矩陣中中有 階單位子矩陣. 單純形方法解題步驟:1.建立單純形表, 并保證在該表中基變量的價值系數(shù)為0.2.求出當前解, 并判定當前解是否為最優(yōu)解. （當前解3.若當前解不是最優(yōu)解, 則進行換基:則檢驗數(shù)行 為新價值系數(shù)的相反數(shù)行.的定義是基變量取右端的常數(shù)項, 非基變量取為零）.判定當前解是否為最優(yōu)解的條件是確定進基變量 其中 由關系確定.確定出基變量 其中而 為第 行對應的基變量.以 為主元進行迭代, 目標: 主元化為1, 該列的其余4.重新進行判定.元化為零. （只能用行變換）注 線性規(guī)劃的單純性表 設線性規(guī)劃為并且假設在約束條件系數(shù)矩陣中前

8、 個列向量為單位向量, 則相應的單純形表為表中的 行是檢驗數(shù)行, 中的數(shù)是將 消為0后, 取負值后所得到的.例2 用單純形方法求解線性規(guī)劃.解 由前面討論知原問題的單純形表為此時, 當前解為由于 故當前解非最優(yōu)解. 所以主元主元故最優(yōu)解為 最優(yōu)解值為檢驗數(shù)非負二、整數(shù)規(guī)劃 在前面所涉及到的許多線性規(guī)劃模型中, 很多情況下, 除了對變量有非負要求外, 有時甚至要求其取值為整數(shù)型的. 例如在問題一中, 變量 表示在第 種方案下所使用的原料鋼管數(shù), 則相應取值為非負整數(shù). 這樣的線性規(guī)劃稱為整數(shù)規(guī)劃. 若線性規(guī)劃中對變量的要求為部分整數(shù)型的, 這樣的規(guī)稱為混合型的. 在整數(shù)規(guī)劃中, 舍棄決策變量的整

9、數(shù)限制, 所得到的規(guī)劃稱為原規(guī)劃所對應的松弛問題. 求解整數(shù)規(guī)劃并不能通過求對應的松弛問題的最優(yōu)解再取其整數(shù)部分而求得. 求解整數(shù)規(guī)劃的方法主要有分枝定界法和割平面法. 這里我們僅介紹分枝定界法, 有興趣的讀者可以參閱相應的書籍. 1.整數(shù)規(guī)劃及分枝定界法 求解整數(shù)規(guī)劃的的分枝定界法 設線性規(guī)格為整數(shù).求出對應松弛問題的最優(yōu)解, 若該解為整數(shù)解, 則該解也是原規(guī)劃的最優(yōu)解, 若該解不是整數(shù)解, 則進行分枝;設 不是整數(shù)解, 則最優(yōu)整數(shù)解中的 必然滿足因此將原問題分解成兩個規(guī)劃 為整數(shù).及為整數(shù).分別求出這兩個規(guī)劃所對應的松弛問題的最優(yōu)解;若有一個分枝的解為整數(shù)解, 而另一個分枝的最優(yōu)解的函數(shù)值

10、小于該整數(shù)解的函數(shù)值, 則將該枝剪去（定界）并由此得到原問題的最優(yōu)解;若兩個分枝對應的松弛問題的最優(yōu)解都不是整數(shù)解, 則分別進行分枝, 繼續(xù)求解.例3 求解整數(shù)規(guī)劃且為整數(shù).解 由單純性方法得到松弛問題的最優(yōu)解:注意到該解不是整數(shù)解, 取 進行分枝, 形成2個規(guī)劃,規(guī)劃且為整數(shù).及規(guī)劃且為整數(shù).這兩個規(guī)劃所對應的松弛問題的最優(yōu)解分別為 由于規(guī)劃所對應的松弛問題的最優(yōu)解值低于規(guī)劃所對應的松弛問題的最優(yōu)解值, 且規(guī)劃所對應的松弛問題的解為整數(shù)解, 故規(guī)劃舍去（定界, 剪枝）, 從而得到原規(guī)劃的最優(yōu)解為 2.01規(guī)劃 整數(shù)規(guī)劃中的一個特殊模型是01規(guī)劃. 在引入01規(guī)劃之前先看一個例子. 問題三課程

11、選修方案確定 某學校規(guī)定: 運籌學專業(yè)的學生畢業(yè)時至少學習過兩門數(shù)學課, 三門運籌學課和兩門計算機課. 這些課程的編號、名稱、學分和所屬類別如下表所示, 則畢業(yè)時學生最少可以學習這些課程中的哪些課程？又如果某個學生既希望選修課程的數(shù)量少, 而又能獲得較多的學分, 那么他該如何確定他的選修課程計劃？1,2計算機,運籌學2數(shù)學實驗95運籌學2自動化控制8計算機4程序設計77計算機,運籌學3匯編語言61,2數(shù)學,運籌學3應用統(tǒng)計57數(shù)學,計算機3數(shù)據(jù)結構41,2數(shù)學, 運籌學3最優(yōu)化方法3數(shù)學3線性代數(shù)2數(shù)學5微積分1先修課類別學分課程名稱編號 建模 以 表示該學生選修課程號為 的課程, 而則表示未

12、選修該課程. 若希望課程數(shù)最少, 則目標函數(shù)為至少選修2門數(shù)學課的要求表現(xiàn)為關系平行可得其它約束條件, 由此得到關系再考慮對先修課的要求.例如要選最優(yōu)化方法, 則必須先修微積分與線性代數(shù), 從而有關系其它情況完全類似, 從而有約束條件組由此得到問題對應的數(shù)學模型:思考: 若該學生希望能得到較高的學分而課程數(shù)盡可能少,又該如何處理？ 在問題三中我們看到, 由于決策變量表示是否選修第門課程, 其取值只有0和1兩種情況, 因而相應的規(guī)劃稱為01規(guī)劃, 在實際問題中, 01規(guī)劃出現(xiàn)的情況很多. 問題四 背包問題 某人爬山, 可攜帶的物品有 其重量為 價值為 又攜帶的物品的總重量不得超過 則該登山人該如

13、何確定其攜帶方案, 使價值為最高？ 這樣的問題稱為背包問題. 分析以 表示該登山人攜帶第 種物品件數(shù), 則有問題的模型為該問題也可用動態(tài)規(guī)劃的方法求解.為正整數(shù).例 某倉庫有一臺載重為13t的卡車, 現(xiàn)要裝運3種貨物，問: 這三種貨物各裝多少,價值最大?這三種貨物的重量和價值分別為， 01規(guī)劃的常用解法稱為隱枚舉法. 3.指派問題與匈牙利方法 01規(guī)劃中的一個重要形式是指派問題. 指派問題 設有 項工作, 交給 個人去完成, 各人完成每項工作的代價（成本）為已知的, 設第人完成第項工作的代價為. 規(guī)定每人只能完成其中的一項工作, 求相應的指派方案, 使完成這些工作的總代價為最小.（這樣的問題就

14、稱為指派問題. ）一個比較典型的指派模型為混合接力隊員的選拔. 分析 引入變量 第 項工作由第 人去完成;第 項工作由他人完成.注意到每人只能完成其中的一項, 并且每項工作最多只有一人完成, 由此相應的約束條件為及而完成這些工作的總代價為由此得到指派問題的數(shù)學模型 指派問題對應的數(shù)學模型屬于01規(guī)劃的范疇, 可以用求解01規(guī)劃的方法進行求解. 但求解相當繁瑣, 匈牙利數(shù)學家考尼格（Konig）提出了解決該問題的新的算法, 因而該方法稱為匈牙利方法. 該矩陣稱為指派問題中的代價（成本）矩陣. 又引入矩陣該矩陣稱為指派問題中的指派矩陣.為此首先引入矩陣 由指派條件, 矩陣中每行的元素只能有一個是1

15、及每列的元素至多有一個1, 其余元均為0. 這樣的矩陣稱為指派矩陣,對應的是某個指派方案. 例4 設指派問題中的代價矩陣為則下面的兩個矩陣均可視為某個指派方案下的指派矩陣:相應的代價分別為 匈牙利方法 首先我們討論指派問題中的特殊形式, 即 的情況.行縮減每行減去該行的最小數(shù);列縮減每列減去該列的最小數(shù)； 判定是否有個獨立的零. 若有，則在指派矩陣中對應獨立的零的 取1, 其余的取0, 由此得到最小代價的指派方案;若沒有個獨立的零, 則進行下面的迭代過程在未被線劃去的數(shù)中找最小數(shù);未被線劃去的所有數(shù)都減去該數(shù), 除了兩線的交叉點以外, 被線劃去的數(shù)保持不變, 而交叉點的數(shù)再加上該數(shù);繼續(xù)判定.

16、例5 用匈牙利方法求解指派問題, 其中的代價矩陣為 解 首先進行行列縮減, 由此得到對上面的矩陣, 可以判定沒有四個獨立的零. 事實上, 用三條線可以將所有的零劃去. 此時相應的最小數(shù)為2, 繼續(xù)迭代有該矩陣中有4個獨立的零, 因而對應的指派矩陣可取 即對應的指派方案為 而相應的最小代價為注 對 的指派問題, 可以通過增加零行或零列來進行轉化.思考 若 且所有工作都必須完成, 同時至多只有一個人完成其中的兩項工作, 該如何確定相應的指派方案?四、用Lingo軟件求解線性規(guī)劃 在前面的討論中我們看到, 用手工算法求解一個線性規(guī)劃問題, 即使算法再好, 對一個大型的線性規(guī)劃問題, 也是相當困難的.

17、 這里我們介紹一個借助軟件來求解線性規(guī)劃的方法. 1.用Lingo軟件求解線性規(guī)劃問題 Lingo軟件是由美國Lindo公司研制開發(fā)的, 用于求解線性規(guī)劃和非線性規(guī)劃的應用軟件. 在Lingo官方網(wǎng)站上可以得到相應的下載軟件, 目前的11.0版本支持Vista平臺. 其特點是書寫簡便, 使用靈活.例6 求解線性規(guī)劃解 啟動Lingo,在主窗口中輸入主窗口即注意表達式 執(zhí)行Lingo菜單下的Solve命令, 得到問題的解 執(zhí)行Lingo菜單下的Solve命令, 得到問題的解即問題的最優(yōu)解為 最優(yōu)解值為結果分析: 對于解代入到約束條件中, 此時條件1與條件3正好取等式, 這樣的約束條件稱為緊約束條

18、件, 一般相應的影子價格不為0.而變量的意義是該產(chǎn)品的價值不高, 沒必要投入生產(chǎn).例7 求問題一的解 問題一的規(guī)劃為注意到問題中的變量應取整數(shù), 故在程序中增加相應命令.指定變量為整數(shù)型問題的解為最優(yōu)解值為 在上面的例子中可以發(fā)現(xiàn), 當變量較多時, 這樣的輸入比較繁瑣, 在Lingo中可以通過設置變量來簡化輸入過程, 我們以下面的簡單例子來加以說明其用法.例8 求解線性規(guī)劃相應的求解程序為運行后得到問題的最優(yōu)解:例 用Lingo程序求解規(guī)劃程序為 說明 Set的使用 Set命令是定義Lingo中的初始集, 基本格式為 Sets Setname/number_list :attributs_li

19、st; Endsets 例如下面命令定義了一個學生集：Sets: Students/1. .20/: Sex, Age;Endsets 模型中數(shù)據(jù)的定義 在Lingo中, 通過命令Data來定義模型中的數(shù)據(jù). 其基本格式是Data： Attribute=value_lists；Enddata 數(shù)值計算 在Lingo中常用的數(shù)值計算函數(shù)有: 求和, 最大值, 最小值, 求平均值等. 例如求和命令sum格式 sum(set(set_index_list)|condition_qualified:expr). 其中condition_qualified是個可選參數(shù). 循環(huán) Lingo中的基本循環(huán)命令

20、是for. 格式 for(set(set_index_list)|condition_qualified:expr).例9 求解01規(guī)劃 解 相應的Lingo程序如下運行后得問題的最優(yōu)解例10 運輸問題 有一連鎖超市系統(tǒng), 系統(tǒng)中4個存儲站和10個門市部, 倉儲站的庫存量為196, 187, 179, 176; 10個門市部當前的需求量分別為75, 69, 72, 83, 66, 65, 74, 62, 81, 56, 從倉儲站到門市部的運輸成本如下表:4475568765478985754663875347694528567896787110987654321求相應的運輸方案, 使總運輸成本

21、為最小. 分析以 表示第 個倉儲站的庫存量, 為第 個門市部的需求量, 注意到以 表示第 個倉儲站到第 個門市部的運輸量. 則模型為并且注意到 為整數(shù)變量. 該規(guī)劃共有40個變量, 可以看到用手工算法是相當困難的. 在Lingo下編制程序: 運行后得到問題的最優(yōu)解為 最小成本為 即相應的運輸方案為下表: 56000045000754000021216572003000734400069020816200018000110987654321例11 求解最小指派問題解 指派問題的數(shù)學模型為相應程序如下:求解后得到問題的最優(yōu)解 最小成本為 五、應 用 應用一 資源分配 某公司安排職員的工作日程安排:

22、 一周中每天都需要一定數(shù)量的員工工作, 數(shù)量有差異. 每個員工一周連續(xù)工作五天, 休息兩天. 公司對員工數(shù)量要求為下表:14周六19周五16周四15周三16周二18周一12周日所需員工數(shù)時間試確定該公司每天應聘用的職員數(shù). 分析以 表示在周 開始工作的人數(shù), 則問題的目標函數(shù)為約束條件為對每天員工數(shù)量的要求, 即對周一而言有由此得到問題的數(shù)學模型: 在Lingo中輸入命令 運行后得到問題的最優(yōu)解為下面這段程序給出了用循環(huán)的方式的求解命令. 應用二 貨運問題 問題的提出要將7種規(guī)格的包裝箱 裝到兩輛平8466978數(shù)量10002000400050010003000200064.052.048.7

23、72.061.352.048.7平板車上去, 包裝箱的寬度和高度都相同, 但厚度及重量 不同. 下表給出了相應的數(shù)據(jù) 每輛平板車有 長的地方可以用來裝箱（像面包那樣排列）, 載重為 由于當?shù)刎涍\的限制, 對 三類包裝箱的總數(shù)有相應的約束: 所占的空間不得超過試建立相應的數(shù)學模型, 將這些箱裝到平板車上, 并使浪費的空間為最小. 分析 所有貨物的重量之和為 而兩輛車的裝哉能力為 故貨物不能全部裝車, 所以應選擇一個合適的裝運方案, 使貨盡可能地多裝, 而且浪費的空間為最小. 問題的關鍵是確定各車的運輸方案. 模型建立 記 表示第 輛車裝運 種箱的個數(shù)以 表示 的厚度, 則目標函數(shù)為 約束條件有:

24、 對箱數(shù)的約束 對重量的約束:厚度約束: 對 的約束:得到問題的最優(yōu)解為所占空間為用Lingo軟件對該問題進行求解: 問題的求解程序為最優(yōu)解為注 該問題的解不唯一. 應用三 手術安排問題 某大醫(yī)院向社會提供各種不同的醫(yī)療服務, 為獲得最好的社會效益和經(jīng)濟效益, 醫(yī)院必須優(yōu)化其資源配置. 如果資源配置不是最好的, 則可能存在有的資源使用率低, 而有的資源使用過度的情況. 以下面提供的外科手術數(shù)據(jù)為例, 試建建立一個能夠幫助醫(yī)院改善其資源配置, 提高效益的的數(shù)學模型.手術類型分為三類: 簡稱為大手術（例如心臟搭橋手術）, 中手術（例如胃切除手術）和小手術（例如闌尾手術）. 每種手術所需的人數(shù)和費用

25、如下表:手術主刀醫(yī)師麻醉師配合醫(yī)師器械護士大3112中2111小1101手術巡回護士所需時間平均費用大21天3萬中2半天1.6萬小15個/天3千資源數(shù)據(jù)表 現(xiàn)在醫(yī)院的人員基本情況如下: 高級醫(yī)師21人, 普通醫(yī)師44人. 只有高級醫(yī)師才可以充當1.假定各種外科手術的病人足夠多, 如何安排每天的日常手2.若做手術的病人分布不均, 如大手術并不常見, 而小手術大, 中手術的主刀醫(yī)師. 護士100人, 其中只有60人可以充當器械護士, 麻醉師30人.手術使得其經(jīng)濟效益最高?則可能較多, 要求做小手術的病人在手術完成之前一直占據(jù)著醫(yī)院的床位, 如若床位有限, 小手術要求一周內完成, 3.充分考慮社會效

26、益和經(jīng)濟效益, 如何在原來的計劃上作否則病人要求轉院. 問如何制定一個醫(yī)院的每周手術安排計劃?盡可能小的調整, 滿足急癥病人的需要. 問題分析 在第一種情況下, 需要確定各種手術方案, 目標是使得 設 是每天進行的大手術的人數(shù), 是每天進行的中手手術的人數(shù), （為使問題簡單, 是實際進行中手術的人數(shù), ） 是進行小手術的人數(shù). 則目標函數(shù)為相應的收益達到最大, 而并不考慮實際情況. 因問題假設是有足夠多的病人可供選擇. 再考慮資源的要求:高級醫(yī)師: 假設小手術中由高級醫(yī)師主刀的有 個, 而有普通醫(yī)師主刀的有 個, 普通醫(yī)師: 麻醉師: 器械護士: 護士總需要:另外, 所有的 都必須取正整數(shù).

27、由此得到相應的數(shù)學模型為為非負整數(shù).由Lingo程序, 得到該問題的解總收益為 單位: 萬元.結果分析: 在這樣的安排下, 大手術沒有安排（想一下原因是什么?） 高級醫(yī)師進行的都是中手術. 中手術一共完成了20個. 小手術安排了100個, 均是由普通醫(yī)師主刀的. 此時醫(yī)師的使用情況是: 高級醫(yī)師20, 普通醫(yī)師30, 麻醉師30. 器械護士30, 巡回護士40. 2.在第1種情況下, 沒有安排大手術, 這顯然不合理. 由于大手術并不多見, 故可以考慮在周末安排一到兩個大手術. 如果盡安排一個大手術的情況下, 相應問題的解為:總收益為 單位: 萬元. 對小手術的安排, 不妨可以規(guī)定: 在需要進行

28、小手術的病人住院后, 5天內一定要安排手術. 對結果的分析, 可以發(fā)現(xiàn), 開刀醫(yī)生資源并沒有充分利用. 造成這一現(xiàn)象的關鍵原因是麻醉師不夠（當然還得考慮病區(qū)內有值班醫(yī)師和護士的存在）. 但如果從增加效益的角度來說, 提高社會效益和醫(yī)院效益的一個方法是增加法是增加麻醉師.例如當把麻醉師的數(shù)量從30增加到35人時, 相應問題的解為總收益為 單位: 萬元.不斷改變麻醉師的數(shù)量, 可以發(fā)現(xiàn)當麻醉師數(shù)量上升到45總收益為 單位: 萬元.人時, 解不再變化. 問題的解為應用四 易拉罐下料問題 問題 某公司采用一套沖壓設備生產(chǎn)一種罐裝飲料的易拉罐.這種易拉罐是用鍍錫板沖壓而成的. 易拉罐為圓柱形, 包括罐身

29、、上蓋和下底, 罐身高上蓋和下底的直徑均 為 該公司使用兩種不同規(guī)格的鍍錫板原料: 規(guī)格1的鍍錫板為正方形, 邊長為規(guī)格2的鍍錫板為長方 形, 長和寬分別為 和 由于生產(chǎn)設備和生產(chǎn)工藝的限制, 對于規(guī)格1的鍍錫板原料, 只可以按下圖中的模式1、模式2和模式3進行沖壓; 對于規(guī)格2的鍍錫板原料, 只能按模式4進行沖壓.使用模式 1、2、3、4進行沖壓時, 每次所需要的時間分別是 該工廠每周工作每周可供使用的規(guī)格1、規(guī)格2的原料分別為5萬張和2萬張.目前每只易拉罐的利潤為元, 原料余料損失為 問工廠應如何安排生產(chǎn)?上蓋罐身下底 問題分析 本問題的關鍵是確定每種模式下的余料損失！ 由已知條件得各種模

30、式下的余料損失如下: 模式1 10個蓋子的面積 一個罐身的面積 余料損失為 將4種模式下的數(shù)據(jù)整理如下罐身個數(shù)蓋的個數(shù)余料損失沖壓時間模式1110222.61.5模式224183.32模式3016261.81模式445169.53 模型建立 以 表示第 種模式下的沖壓次數(shù), 表示一周生產(chǎn)的 易拉罐個數(shù),表示不配套的罐身個數(shù),表示不配套的罐蓋個數(shù), 并視這些變量為連續(xù)變量.要點！ 目標函數(shù)浪費的余料數(shù)和面積相乘 約束條件 時間約束 原料約束 配套約束 由此得到規(guī)劃模型 由于約束條件1,2的常數(shù)過大, 所以簡化后得到: 在Lingo下求解該規(guī)劃.輸入下面語句:運行后的結果為 即問題的最優(yōu)解為六、用

31、MatLab求解線性規(guī)劃 設線性規(guī)劃為 基本格式例 求解規(guī)劃解 將問題轉化為相應的標準形式, 則有此時輸入語句結果為即原問題的最優(yōu)解為不能省略!也可以簡寫成例 求解規(guī)劃解 輸入下面語句運行結果為例 求解線性規(guī)劃解 輸入下面語句運行結果為七、非線性規(guī)劃 在上面諸節(jié)中討論了線性規(guī)劃和幾類特殊的線性規(guī)劃整數(shù)規(guī)劃及01規(guī)劃和相應的解法. 所謂線性規(guī)劃實際上是指數(shù)學規(guī)劃中的目標函數(shù)及約束條件表達式均為線性關系. 但實際問題中所對應的數(shù)學規(guī)劃其表達式很可能不是線性關系式. 在微積分課程中我們大量遇到該類問題. 首先我們看兩個簡單例子.例12 將邊長為的正三角形剪去三個全等的四邊形（如圖所示）, 然后將其折

32、起, 做成一個無蓋的正三棱柱, 當圖中的 取何值時, 該盒子的容積為最大 解 盒子的高為 底面面積為故相應的體積為求導后并令其為零, 得所以再注意到,即函數(shù)在該點取極大值, 又因駐點唯一, 故該點一定是最大值點. 該模型是個非線性規(guī)劃，一般稱為無約束的優(yōu)化問題.例13 某工廠要用鐵板做成一個體積為2的有蓋長方體水箱. 問當長, 寬, 高各取多少時, 所使用的原料最省？ 設長方體的三邊長分別為則水箱的表面積為此為問題的目標函數(shù). 而相應的約束條件為由此得到問題的數(shù)學模型為 這樣的問題稱為有約束的最優(yōu)化問題. 一個標準的無約束的優(yōu)化問題可以寫成而有約束的優(yōu)化問題可以寫成 問題 砂石運輸問題. 設有

33、 立方米的砂, 石要由甲地運到乙地, 運輸前需先裝入一個有底無蓋并在底部裝有滑行器的木箱中. 砂石運到乙地后, 從箱中倒出,在繼續(xù)用空箱裝運. 不論箱子大小, 每裝運一箱, 需0.1元, 箱底和兩端的材料費為20元/米2, 箱子兩側的材料費為5元/米2, 箱底的兩個滑行器與箱子同長, 材料費為2.5元/米. 問木箱的長寬高各為多少米,才能使運費與箱子的成本費的總和為最小. 建模 設木箱的長寬高分別為 運費與成本費的總和為 則目標函數(shù)為 若在上述問題中, 箱子的底與兩側使用廢料來做, 而廢廢料只有4平方米, 則問題為:在上面問題中, 目標函數(shù)與約束條件中的每一項可表達成 的形式（其中的 為整數(shù)）

34、 , 數(shù)學上將其稱為廣義多項式, 相應的規(guī)劃稱為幾何規(guī)劃.當系數(shù)為正數(shù)時, 規(guī)劃稱為正項幾何規(guī)劃. 非線性規(guī)劃解法例1 求解非線性規(guī)劃解1 圖解法最優(yōu)解為解2 用Lingo軟件求解最優(yōu)解為 無約束非線性規(guī)劃解法簡介 無約束非線性規(guī)劃一般可寫成其中 解法 1.求 的梯度 2.令梯度 解出 的駐點3.驗證 在該點的Hessian矩陣是否為正（負）定的, 若成立, 則該點為函數(shù)的極?。ù螅┲迭c.例 求函數(shù) 的極小點.解 的梯度為令 則駐點為 函數(shù)的Hessian陣為注意到該矩陣為正定陣, 因而該點為極小值點. 注意到此方法只有對一些特殊的函數(shù)才有效. 一般情況1.給出 的極小點 的一個初始估計值 稱為初始2.如果 已求得, 并且不是極小點, 設法選取一個方向（該方向稱為搜索方向）, 使目標函數(shù) 沿該方下, 要求出函數(shù)的駐點是比較困難的. 下面我們簡單介紹求解