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

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