優(yōu)化軟件課件2

第一章用Excel求解規(guī)劃問題Excel具有內(nèi)置的規(guī)劃求解功能。MicrosoftExcel的“規(guī)劃求解”工具取自德克薩斯大學(xué)奧斯汀分校的LeonLasdon和克里夫蘭州立大學(xué)的AllanWaren共同開發(fā)的GeneralizedReducedGradient(廣義既約梯度法)非線性最優(yōu)化代碼。線性和整數(shù)規(guī)劃問題取自FrontlineSystems公司的JohnWatson和DanFylstra提供的有界變量單純形法和分支邊界法。簡介第一章用Excel求解規(guī)劃問題1、啟動Excel；2、Tools－》Add－Ins3、選中SolverAdd－in開啟“Solver”O(jiān)ffice07在excel選項-》加載項，點選“轉(zhuǎn)到”，選中“規(guī)劃求解”，然后在“數(shù)據(jù)”=》分析第一章用Excel求解規(guī)劃問題4、重新打開Tools菜單；5、選中Solver即可。開啟“Solver”第一章用Excel求解規(guī)劃問題例：某工廠要生產(chǎn)兩種產(chǎn)品：門和窗；每扇門需要在車間1加工1小時，車間3加工3小時；每扇窗需要在車間2加工2小時，車間3加工2小時；車間用于生產(chǎn)這兩種產(chǎn)品的時間：車間1為4小時，車間2為12小時，車間3為18小時；每扇門的利潤300元，窗的利潤500元；如何確定產(chǎn)品周生產(chǎn)計劃，使總利潤最大？入門：一個簡單的例子第一章用Excel求解規(guī)劃問題規(guī)劃模型：x1＝門生產(chǎn)量；x2=窗生產(chǎn)量入門：一個簡單的例子Maxz=300*x1+500*x2s.t.X1<=4;2*X2<=12;3*x1+2*x2<=18;x1,x2>=0;第一章用Excel求解規(guī)劃問題打開Excel，輸入模型參數(shù)的常量部分：上面是目標(biāo)系數(shù)，下面是約束（黃色的是常量）；入門：一個簡單的例子Examp01-01.xls第一章用Excel求解規(guī)劃問題然后輸入模型參數(shù)的變量相關(guān)部分：即決策變量、與決策變量相關(guān)的量，如總利潤和實際使用工時（藍(lán)色是變量部分）；入門：一個簡單的例子第一章用Excel求解規(guī)劃問題選“Solver”，輸入如下參數(shù)：入門：一個簡單的例子第一章用Excel求解規(guī)劃問題點擊Options，選擇“Assumelinearmodel”和“Assumenon－linear”。點擊【OK】，【solve】：入門：一個簡單的例子第一章用Excel求解規(guī)劃問題在彈出的“SolverResults”中，選擇“Reports”中的“Answer”,選擇【OK】。入門：一個簡單的例子第一章用Excel求解規(guī)劃問題結(jié)果如下：入門：一個簡單的例子第一章用Excel求解規(guī)劃問題同時，決策變量的最優(yōu)值以及和決策變量相關(guān)變量的值也自動被填充。入門：一個簡單的例子第一章用Excel求解規(guī)劃問題靈敏度分析能夠為決策提供有用的信息，能夠幫助管理者進(jìn)行正確的決策。例如，模型中的有些系數(shù)（例如上例中的可用工時）被認(rèn)為是確定的，優(yōu)化也在此基礎(chǔ)上進(jìn)行。但是，實際情況中，環(huán)境變化可能使系數(shù)發(fā)生變化，而這些變化可能又影響當(dāng)前的最優(yōu)解。因此，需要研究最優(yōu)解對系數(shù)變化的反應(yīng)程度，以適應(yīng)各種偶然變化。用Excel進(jìn)行靈敏度分析第一章用Excel求解規(guī)劃問題回顧上節(jié)的例子：用Excel進(jìn)行靈敏度分析某工廠要生產(chǎn)兩種產(chǎn)品：門和窗；每扇門需要在車間1加工1小時，車間3加工3小時；每扇窗需要在車間2加工2小時，車間3加工2小時；車間用于生產(chǎn)這兩種產(chǎn)品的時間：車間1為4小時，車間2為12小時，車間3為18小時；每扇門的利潤300元，窗的利潤500元；如何確定產(chǎn)品周生產(chǎn)計劃，使總利潤最大？最優(yōu)解：x1=2;x2=6,最大利潤3600。第一章用Excel求解規(guī)劃問題那么，考慮以下的問題：用Excel進(jìn)行靈敏度分析如果門的利潤由300提高到400，最優(yōu)解是否改變？對總利潤有怎樣的影響？如果車間1的可用工時增加2個小時，總利潤是否變化？如何變化，最優(yōu)解是否發(fā)生變化？如果車間2更新工藝，生產(chǎn)一扇窗由以前的2小時下降到1小時，最優(yōu)解如何變化？如果工廠新增加用電限制，是否會改變原來的最優(yōu)方案？。。。第一章用Excel求解規(guī)劃問題用Excel進(jìn)行靈敏度分析用Excel進(jìn)行靈敏度分析最簡單的方法，就是修改參數(shù)并重新進(jìn)行求解，但逐個嘗試工作量很大；Excel提供了敏感性報告的功能，可以利用其結(jié)果方便的進(jìn)行靈敏度分析。第一章用Excel求解規(guī)劃問題用Excel進(jìn)行靈敏度分析上例的靈敏度分析結(jié)果：第一章用Excel求解規(guī)劃問題用Excel進(jìn)行靈敏度分析上例的可變單元格的靈敏度分析結(jié)果：最優(yōu)解當(dāng)該非基變量增加一個單位時目標(biāo)函數(shù)減少的量(對max型問題)目標(biāo)系數(shù)（已知）目標(biāo)函數(shù)在允許的增量范圍內(nèi)變化時，最優(yōu)解不變目標(biāo)函數(shù)在允許的遞減范圍內(nèi)變化時，最優(yōu)解不變故c1的范圍（300－300，300＋450）；c2的范圍（500－300，500＋無窮）；第一章用Excel求解規(guī)劃問題用Excel進(jìn)行靈敏度分析上例的靈敏度分析結(jié)果：如果保證最優(yōu)解不變，那么故車間1工時的范圍（4－2，4＋無窮）；故車間1工時的范圍（12-6,12+6）;故車間3工時的范圍(18-6,18+6);終值－工時實際使用量約束限制值－不等式右邊的常量允許的增量(或漸量)：右端值在允許的增量和漸量范圍內(nèi)變化時，影子價格不變(但最優(yōu)解可能變化)。影子價格，表示約束右端值每增加和減少1時，目標(biāo)函數(shù)值的相應(yīng)增量或漸量第一章用Excel求解規(guī)劃問題用Excel進(jìn)行靈敏度分析影子價格第一個約束：增加車間1一個單位的可用工時，總利潤并不變（因為時間使用工時2小時小于可用工時4小時）；第二個約束：在允許的范圍內(nèi)(12-6,12+6)，增加車間2一個單位的可用工時，將增加利潤150（因為車間2的可用工時都用來生產(chǎn)了產(chǎn)品），這對管理者很有決策的意義。第三個約束：。。。第一章用Excel求解規(guī)劃問題用Excel進(jìn)行靈敏度分析影子價格的經(jīng)濟(jì)意義：影子價格實際上是一種機(jī)會成本。當(dāng)資源的價格低于影子價格時，可買進(jìn)該資源，反之可賣出。隨著資源變化，影子價格也隨之變化。當(dāng)影子價格與市場價格相同時，才處于平衡狀態(tài)；當(dāng)影子價格＝0，表示該資源未得到充分利用；否則表示資源在生產(chǎn)中已全部利用；在公司內(nèi)部，可借助資源的影子價格確定內(nèi)部結(jié)算價格，以控制有限資源的使用，使有限資源得到更大的經(jīng)濟(jì)效益。第一章用Excel求解規(guī)劃問題練習(xí)：文具生產(chǎn)方案和臨時工估計某廠利用原材料白坯紙生產(chǎn)稿紙、日記簿和練習(xí)本三種產(chǎn)品；現(xiàn)有工人100人，白坯紙的日供應(yīng)量30000公斤；若單獨生產(chǎn)產(chǎn)品，工人每日可生產(chǎn)稿紙30捆、日記簿30打、練習(xí)本30箱；資源消耗情況：每捆稿紙用白坯紙10/3公斤,每打日記簿用白坯紙40/3公斤,每箱練習(xí)本用白坯紙80/3公斤；產(chǎn)品盈利情況：每捆稿紙1元，每打日記簿2元，每箱練習(xí)本3元問題1：每天生產(chǎn)稿紙、日記簿和練習(xí)本各多少（可取小數(shù)），利潤才最好？問題2：如果工人數(shù)量不足，可招臨時工，其費用每天每人15元，問在目前的條件下，該廠是否需要招臨時工？如果招臨時工，那么招多少才好？第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置SetTargetCell(設(shè)置目標(biāo)單元格)：一些單元格、具體數(shù)值、運算符號的組合。注意：目標(biāo)單元格一定要是公式，即一定是以“=”開始。類似于線性規(guī)劃中的目標(biāo)函數(shù)。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置Max,Min,Valueof(最大值、最小值、給定值)：在此指定是否希望目標(biāo)單元格為最大值、最小值或某一特定數(shù)值。如果需要指定數(shù)值，請在右側(cè)編輯框中鍵入該值;ByChangingcells(可變單元格)：在此指定可變單元格。求解時其中的數(shù)值不斷調(diào)整，直到滿足約束條件并且“設(shè)置目標(biāo)單元格”框中指定的單元格達(dá)到目標(biāo)值。可變單元格必須直接或間接地與目標(biāo)單元格相關(guān)聯(lián)。類似于線性規(guī)劃中的變量。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置Guess(推測)：單擊此按鈕，自動推測“設(shè)置目標(biāo)單元格”框中的公式所引用的所有非公式單元格，并在“可變單元格”框中定位這些單元格的引用。SubjecttotheConstraints(約束)：列出了規(guī)劃求解的所有約束條件。Add(添加)：顯示“添加約束”對話框。Change(更改)：顯示“更改約束”對話框。注意：單擊此按鈕的時候，要先選擇需要更改的約束。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置Delete(刪除)：刪除選定的約束條件。同樣單擊此按鈕前，要先選擇需要刪除的約束。Solve(求解)：對定義好的問題進(jìn)行求解。Close(關(guān)閉)：關(guān)閉對話框，不進(jìn)行規(guī)劃求解。但保留通過“選項”、“添加”、“更改”或“刪除”按鈕所做的更改。也就是說，當(dāng)你下次再次單擊“規(guī)劃求解”按鈕后，對話框顯示上回所設(shè)置的參數(shù)。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置Options(選項）：顯示“規(guī)劃求解選項”對話框。在其中可加載或保存規(guī)劃求解模型，并對求解過程的高級屬性進(jìn)行控制。下面詳細(xì)介紹選項中的各項設(shè)置的具體含義。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置MaxTime(最長運算時間)：在此設(shè)定求解過程的時間?？奢斎氲淖畲笾禐?2767（秒），默認(rèn)值100（秒）可以滿足大多數(shù)小型規(guī)劃求解要求。Durations(迭代次數(shù))：在此設(shè)定求解過程中迭代運算的次數(shù)，限制求解過程的時間?？奢斎氲淖畲笾禐?2767，默認(rèn)值100次可滿足大多數(shù)小型規(guī)劃求解要求。Precision(精度)：在此輸入用于控制求解精度的數(shù)字，以確定約束條件單元格中的數(shù)值是否滿足目標(biāo)值或上下限。精度值必須表示為小數(shù)（0到1之間），輸入數(shù)字的小數(shù)位越多，精度越高。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置Tolerance(允許誤差)：在此輸入滿足整數(shù)約束條件并可被接受的目標(biāo)單元格求解結(jié)果與真實的最佳結(jié)果間的百分偏差。這個選項只應(yīng)用于具有整數(shù)約束條件的問題。設(shè)置的允許誤差值越大，求解過程就越快。Convergence(收斂度)：在此輸入收斂度數(shù)值，當(dāng)最近五次迭代后目標(biāo)單元格中數(shù)值的變化小于“收斂度”框中設(shè)置的數(shù)值時，“規(guī)劃求解”停止運行。收斂度只應(yīng)用于非線性規(guī)劃求解問題，并且必須表示為小數(shù)（0到1之間）。設(shè)置的數(shù)值越小，收斂度就越高。例如，0.0001表示比0.01更小的相對差別。收斂度越小，“規(guī)劃求解”得到結(jié)果所需的時間就越長。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置AssumeLinearModel(采用線性模型)：當(dāng)模型中的所有關(guān)系都是線性的，并且希望解決線性優(yōu)化問題時，選中此復(fù)選框可加速求解進(jìn)程。AssumeNon-Negative(假定非負(fù))：如果選中此復(fù)選框，則對于在“添加約束”對話框的“約束值”框中沒有設(shè)置下限的所有可變單元格，假定其下限為0（零）。UseAutomaticScaling(自動按比例縮放)：如果選中此復(fù)選框，當(dāng)輸入和輸出值量級差別很大時，可自動按比例縮放數(shù)值。例如，基于百萬美元的投資將利潤百分比最大化。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置ShowDurationResults(顯示迭代結(jié)果)：如果選中此復(fù)選框，每進(jìn)行一次迭代后都將中斷“規(guī)劃求解”，并顯示當(dāng)前的迭代結(jié)果。Estimates(估計)：指定在每個一維搜索中用來得到基本變量初始估計值的逼近方案。正切函數(shù)：使用正切向量線性外推二次方程：用二次方程外推法，提高非線性規(guī)劃問題的計算精度。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置Derivatives(導(dǎo)數(shù))：指定用于估計目標(biāo)函數(shù)和約束函數(shù)偏導(dǎo)數(shù)的差分方案。Forward(向前差分)：用于大多數(shù)約束條件數(shù)值變化相對緩慢的問題。Center(中心差分)：用于約束條件變化迅速，特別是接近限定值的問題。雖然此選項要求更多計算，但在“規(guī)劃求解”不能返回有效解時也許有幫助。Search(搜索)：指定每次的迭代算法，以確定搜索方向。牛頓法：用準(zhǔn)牛頓法迭代需要的內(nèi)存比共軛法多，但所需的迭代次數(shù)少。共軛法：比牛頓法需要的內(nèi)存少，但要達(dá)到指定精度需要較多次的迭代運算。當(dāng)問題較大和內(nèi)存有限，或步進(jìn)迭代進(jìn)程緩慢時，可用此選項。第一章用Excel求解規(guī)劃問題規(guī)劃求解中的參數(shù)和設(shè)置LoadModel(裝入模型)：顯示“裝入模型”對話框，輸入對所要加載的模型的引用。SaveModel(保存模型)：顯示“保存模型”對話框，在其中可指定保存模型的位置。只有需要在工作表上保存多個模型時，才單擊此命令。第一個模型會自動保存。第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃用Excel求解整數(shù)規(guī)劃的步驟與一般線性規(guī)劃問題相同，只是在約束條件中添加一個“整數(shù)”約束。在Excel的“添加約束”對話框中，用int表示整數(shù)，因此，只要在該參數(shù)對話框中添加一個約束條件，在左面輸入要求取整的決策變量的單元格地址，然后選擇“int”即可。第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃例：某公司的新產(chǎn)品選擇問題。某公司開發(fā)了三種新產(chǎn)品，相關(guān)數(shù)據(jù)如表。管理層決定，選擇其中兩種產(chǎn)品進(jìn)行生產(chǎn)，且兩個工廠中必須選出一個專門生產(chǎn)新產(chǎn)品，那么如何選擇產(chǎn)品、工廠并確定各種產(chǎn)品的周產(chǎn)量，使得總利潤最大。第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃決策變量：

x1,x2,x3:產(chǎn)品1，2，3的每周產(chǎn)量；

y1,y2,y3（0-1量）:y1=1表示生產(chǎn)產(chǎn)品1，=0表示不生產(chǎn)；

y2=1表示生產(chǎn)產(chǎn)品2，=0表示不生產(chǎn)；

y3=1表示生產(chǎn)產(chǎn)品3，=0表示不生產(chǎn)；

y（0-1量）:y=0表示選擇工廠1，=1表示選擇工廠2；約束1:選擇其中兩種產(chǎn)品進(jìn)行生產(chǎn)y1+y2+y3<=2;x1<=M*y1;x2<=M*y2;x3<=M*y3;(M為大數(shù))

（x1如果非零，那么y1必須為1）第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃約束2:兩個工廠中必須選出一個專門生產(chǎn)新產(chǎn)品3*x1+4*x2+2*x3<=30+M*y;(y如果等于1，即選擇工廠2，則不等式無效)4*x1+6*x2+2*x3<=40+M*(1-y);約束3：周產(chǎn)量受到周可銷售量的限制x1<=7;x2<=5;x3<=9;考慮x1<=M*y1;x2<=M*y2;x3<=M*y3;(M為大數(shù))因為每種產(chǎn)品的周最大產(chǎn)量就是周可銷售量，因此二者可合并為

x1<=7*y1;x2<=5*y2;x3<=9*y3約束4：變量類型約束x1,x2,x3>=0,y1,y2,y3=1or0,y=1or0;第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃綜上，該問題的整數(shù)規(guī)劃模型如下：Maxz=5*x1+7*x2+3*x3s.t.y1+y2+y3<=2;x1<=7*y1;x2<=5*y2;x3<=9*y3;3*x1+4*x2+2*x3<=30+M*y;4*x1+6*x2+2*x3<=40+M*(1-y);x1,x2,x3>=0;y1,y2,y3=1or0;y=1or0;第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃建立Excel規(guī)劃模型：常量(黃色);決策變量(綠色);中間變量(藍(lán)色)Examp01-02.xls第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃建立Excel規(guī)劃模型：常量(黃色);決策變量(綠色);中間變量(藍(lán)色)注意：SUMPRODUCT的用法即兩個矩陣各個相對應(yīng)元素乘積的和。第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃建立Excel規(guī)劃模型：常量(黃色);決策變量(綠色);中間變量(藍(lán)色)第一章用Excel求解規(guī)劃問題用Excel求解整數(shù)規(guī)劃Options：Assum