運(yùn)籌學(xué)-線性規(guī)劃_第1頁(yè)
運(yùn)籌學(xué)-線性規(guī)劃_第2頁(yè)
運(yùn)籌學(xué)-線性規(guī)劃_第3頁(yè)
運(yùn)籌學(xué)-線性規(guī)劃_第4頁(yè)
運(yùn)籌學(xué)-線性規(guī)劃_第5頁(yè)
已閱讀5頁(yè),還剩32頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

實(shí)用運(yùn)籌學(xué)

-運(yùn)用Excel建模和求解第1章線性規(guī)劃LinearProgramming本章內(nèi)容要點(diǎn)線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型;線性規(guī)劃問(wèn)題的電子表格建模;線性規(guī)劃問(wèn)題的多解分析。本章內(nèi)容1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型1.2線性規(guī)劃問(wèn)題的圖解法1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題1.4線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果線性規(guī)劃是運(yùn)籌學(xué)中研究較早,理論和算法比較成熟的重要分支之一。它主要研究在線性等式(或不等式)的限制條件下,使某一線性目標(biāo)函數(shù)取得最大值(或最小值)問(wèn)題。本章主要內(nèi)容框架圖1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型例1.1

某工廠要生產(chǎn)兩種新產(chǎn)品:門(mén)和窗。經(jīng)測(cè)算,每生產(chǎn)一扇門(mén)需要在車間1加工1小時(shí)、在車間3加工3小時(shí);每生產(chǎn)一扇窗需要在車間2和車間3各加工2小時(shí)。而車間1每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間為4小時(shí)、車間2為12小時(shí)、車間3為18小時(shí)。已知每扇門(mén)的利潤(rùn)為300元,每扇窗的利潤(rùn)為500元。而且根據(jù)經(jīng)市場(chǎng)調(diào)查得到的該兩種新產(chǎn)品的市場(chǎng)需求狀況可以確定,按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷售出去。問(wèn)該工廠應(yīng)如何安排這兩種新產(chǎn)品的生產(chǎn)計(jì)劃,可使總利潤(rùn)最大?1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型在該問(wèn)題中,目標(biāo)是總利潤(rùn)最大化,所要決策的變量是新產(chǎn)品的每周產(chǎn)量,而新產(chǎn)品的每周產(chǎn)量要受到三個(gè)車間每周可用于生產(chǎn)新產(chǎn)品時(shí)間的限制。因此,該問(wèn)題可以用目標(biāo)、決策變量和約束條件三個(gè)因素加以描述。實(shí)際上,所有的線性規(guī)劃問(wèn)題都包含這三個(gè)因素:(1)決策變量是問(wèn)題中有待確定的未知因素。例如決定企業(yè)經(jīng)營(yíng)目標(biāo)的各產(chǎn)品的產(chǎn)量等。(2)目標(biāo)函數(shù)是指對(duì)問(wèn)題所追求的目標(biāo)的數(shù)學(xué)描述。例如利潤(rùn)最大、成本最小等。(3)約束條件是指實(shí)現(xiàn)問(wèn)題目標(biāo)的限制因素。如原材料供應(yīng)量、生產(chǎn)能力、市場(chǎng)需求等,它們限制了目標(biāo)值所能到達(dá)的程度。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型解:例1.1可用表1-1表示。車間單位產(chǎn)品的生產(chǎn)時(shí)間(小時(shí))每周可獲得的生產(chǎn)時(shí)間(小時(shí))門(mén)窗11042021233218單位利潤(rùn)(元)3005001.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(1)決策變量本問(wèn)題的決策變量是每周門(mén)和窗的產(chǎn)量??稍O(shè):x1為每周門(mén)的產(chǎn)量(扇);

x2為每周窗的產(chǎn)量(扇)。(2)目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是總利潤(rùn)最大。由于門(mén)和窗的單位利潤(rùn)分別為300元和500元,而其每周產(chǎn)量分別為x1和x2,所以每周總利潤(rùn)z為:

z=300x1+500x2

(元)1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(3)約束條件本問(wèn)題的約束條件共有四個(gè)。車間1每周可用工時(shí)限制:x1

4車間2每周可用工時(shí)限制:2x212車間3每周可用工時(shí)限制:3x1

+2x218非負(fù)約束:x10,x201.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型例1.1的線性規(guī)劃模型:這是一個(gè)典型的利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題。其中,“Max”是英文單詞“Maximize”的縮寫(xiě),含義為“最大化”;“s.t.”是“subjectto”的縮寫(xiě),表示“滿足于……”。因此,上述模型的含義是:在給定的條件限制下,求使得目標(biāo)函數(shù)z達(dá)到最大時(shí)x1,x2的取值。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

本章討論的問(wèn)題均為線性規(guī)劃問(wèn)題。所謂“線性”規(guī)劃,是指如果目標(biāo)函數(shù)是關(guān)于決策變量的線性函數(shù),而且約束條件也都是關(guān)于決策變量的線性等式或線性不等式,則相應(yīng)的規(guī)劃問(wèn)題就稱為線性規(guī)劃問(wèn)題。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型例1.2某公司有100萬(wàn)元的資金要投資(要求全部用完)。該公司有六個(gè)可選的投資項(xiàng)目,其各種數(shù)據(jù)如表1-2所示。投資項(xiàng)目風(fēng)險(xiǎn)(%)紅利(%)增長(zhǎng)(%)信用度118422426571031091224478105126154688861.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型該公司想達(dá)到的目標(biāo)為:投資風(fēng)險(xiǎn)最小,每年紅利至少為6.5萬(wàn)元,最低平均增長(zhǎng)率為12%,最低平均信用度為7。請(qǐng)用線性規(guī)劃方法求解該問(wèn)題。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型解:(1)決策變量本問(wèn)題的決策變量是在每種投資項(xiàng)目上的投資額。設(shè)xi為項(xiàng)目i的投資額(萬(wàn)元)(i=1,2,,6)(2)目標(biāo)函數(shù)本問(wèn)題的目標(biāo)為總投資風(fēng)險(xiǎn)最小,即1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型(3)約束條件本問(wèn)題共有五個(gè)約束條件:①各項(xiàng)目投資總和為100萬(wàn)元;②每年紅利至少為6.5萬(wàn)元;③最低平均增長(zhǎng)率為12%;④最低平均信用度為7;⑤非負(fù)約束。1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型得到的線性規(guī)劃數(shù)學(xué)模型為:這是一個(gè)典型的成本(或風(fēng)險(xiǎn))最小化問(wèn)題。其中,“Min”是英文單詞“Minimize”的縮寫(xiě),含義為“最小化”。因此,上述模型的含義是:在給定的條件限制下,求使得目標(biāo)函數(shù)z達(dá)到最小時(shí)的x1,x2,x3,x4,x5,x6取值1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃的模型結(jié)構(gòu):從以上兩個(gè)例子中可以歸納出線性規(guī)劃問(wèn)題的一般形式:對(duì)于一組決策變量x1,x2,xn,取1.1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型在線性規(guī)劃模型中,也直接稱z為目標(biāo)函數(shù);稱xj(j=1,2,,n)為決策變量;稱cj(j=1,2,,n)

為目標(biāo)函數(shù)系數(shù)或價(jià)值系數(shù)或費(fèi)用系數(shù);稱bi(i=1,2,,m)為函數(shù)約束右端常數(shù)或簡(jiǎn)稱右端值,也稱資源常數(shù);稱aij(i=1,2,,m;j=1,2,,n)為約束系數(shù)或技術(shù)系數(shù)或工藝系數(shù)。這里,cj,bi,aij均為常數(shù)。線性規(guī)劃的數(shù)學(xué)模型可以表示為下列簡(jiǎn)潔的形式:1.2線性規(guī)劃問(wèn)題的圖解法對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題,可以在二維直角坐標(biāo)平面上作圖求解??尚杏蚺c最優(yōu)解線性規(guī)劃的圖解法1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題在Excel電子表格中建立線性規(guī)劃模型用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題使用單元格命名建好電子表格模型的幾個(gè)原則1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題在用電子表格建立數(shù)學(xué)模型(這里是一個(gè)線性規(guī)劃模型)的過(guò)程中,有三個(gè)問(wèn)題需要得到回答:(1)要作出的決策是什么?(決策變量)(2)在作出這些決策時(shí),有哪些約束條件?(約束條件)(3)這些決策的目標(biāo)是什么?(目標(biāo)函數(shù))1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題

用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題(P8有界變量單純形法和分支定界法)(如果“工具”菜單中沒(méi)有“規(guī)劃求解”選項(xiàng),請(qǐng)參見(jiàn)SOLVER文件夾下的“Excel規(guī)劃求解工具的安裝說(shuō)明.doc”)1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題在用Excel的“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題,為單元格命名能使線性規(guī)劃問(wèn)題的電子表格模型更加容易理解。主要表現(xiàn)在兩個(gè)方面:(1)在公式中使用名稱使人們更容易理解公式的含義;(2)在“規(guī)劃求解參數(shù)”對(duì)話框中使用名稱使人們更加容易理解線性規(guī)劃模型的含義。所以,一般給跟公式和模型有關(guān)的四類單元格命名。例如:在例1.1電子表格模型中,單元格命名如下:(1)數(shù)據(jù)單元格:?jiǎn)挝焕麧?rùn)(C4:D4)、可用工時(shí)(G7:G9);(2)可變單元格:每周產(chǎn)量(C12:D12);(3)輸出單元格:實(shí)際使用(E7:E9);(4)目標(biāo)單元格:總利潤(rùn)(G12)。1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題1.3用Excel“規(guī)劃求解”工具求解線性規(guī)劃問(wèn)題電子表格建模是一門(mén)藝術(shù),建立一個(gè)好的電子表格模型應(yīng)遵循以下幾個(gè)原則:(1)首先輸入數(shù)據(jù);(2)清楚地標(biāo)識(shí)數(shù)據(jù);(3)每個(gè)數(shù)據(jù)輸入到唯一的單元格;(4)將數(shù)據(jù)與公式分離;(5)保持簡(jiǎn)單化(使用SUMPRODUCT函數(shù)、SUM函數(shù)、中間結(jié)果等);(6)使用區(qū)域名稱;(7)使用相對(duì)引用和絕對(duì)引用簡(jiǎn)化公式的復(fù)制;(8)使用邊框、底色來(lái)區(qū)分單元格類型(四類單元格);(9)在電子表格中顯示整個(gè)模型(包括符號(hào)和數(shù)據(jù))。Excel提供許多有效的工具來(lái)幫助用戶進(jìn)行模型調(diào)試,其中一個(gè)工具是電子表格的輸出單元格在數(shù)值和公式之間進(jìn)行切換(“工具”->“選項(xiàng)”->“視圖”->“公式”)。Excel的“審核”工具欄也提供了幾個(gè)有用的工具。1.4線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果唯一解無(wú)窮多解無(wú)解可行域無(wú)界(目標(biāo)值不收斂)1.4線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果唯一解線性規(guī)劃問(wèn)題具有唯一解是指該規(guī)劃問(wèn)題有且僅有一個(gè)既在可行域內(nèi)、又使目標(biāo)值達(dá)到最優(yōu)的解。例1.1就是一個(gè)具有唯一解的規(guī)劃問(wèn)題。1.4線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果無(wú)窮多解線性規(guī)劃問(wèn)題具有無(wú)窮多解是指該規(guī)劃問(wèn)題有無(wú)窮多個(gè)既在可行域內(nèi)、又使得目標(biāo)值達(dá)到最優(yōu)的解。在例1.1中,設(shè)門(mén)的單位利潤(rùn)從300元增加至750元,這時(shí)該問(wèn)題的解將發(fā)生變化1.4線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果無(wú)解當(dāng)線性規(guī)劃問(wèn)題中的約束條件不能同時(shí)滿足時(shí),無(wú)可行域的情況將會(huì)出現(xiàn),這時(shí)不存在可行解,即該線性規(guī)劃問(wèn)題無(wú)解。在例1.1中,若要求門(mén)的每周產(chǎn)量不得少于6,則需再加上一個(gè)約束條件:x161.4線性規(guī)劃問(wèn)題求解的幾種可能結(jié)果可行域無(wú)界(目標(biāo)值不收斂)線性規(guī)劃問(wèn)題的可行域無(wú)界,是指最大化問(wèn)題中的目標(biāo)函數(shù)值可以無(wú)限增大,或最小化問(wèn)題中的目標(biāo)函數(shù)值可以無(wú)限減少。在例1.1中,如果沒(méi)有車間可用工時(shí)的約束,但要求門(mén)與窗的總產(chǎn)量不得少于4。上機(jī)實(shí)驗(yàn)一

線性規(guī)劃(-)實(shí)驗(yàn)?zāi)康模喊惭bExcel軟件“規(guī)劃求解”加載宏,用Excel軟件求解線性規(guī)劃問(wèn)題。(二)內(nèi)容和要求:安裝并啟動(dòng)軟件,建立新問(wèn)題,輸入模型,求解模型,結(jié)果的簡(jiǎn)單分析。(三)實(shí)例操作:求解習(xí)題1.1(或其他例題、習(xí)題、案例等)。(1)建立電子表格模型:輸入數(shù)據(jù)、給單元格命名、輸入公式等;(2)使用Excel軟件中的規(guī)劃求解工具求解模型;(3)結(jié)果分析:如五種家具各生產(chǎn)多少?總利潤(rùn)是多少?哪些工序的時(shí)間有剩余,并對(duì)結(jié)果提出你的看法;(4)在Excel或Word文檔中寫(xiě)實(shí)驗(yàn)報(bào)告,包括線性規(guī)劃模型、電子表格模型和結(jié)果分析等。習(xí)題1.1某家具制造廠生產(chǎn)五種不同規(guī)格的家具。每件家具都要經(jīng)過(guò)機(jī)械成形、打磨、上漆幾個(gè)主要生產(chǎn)工序。每種家具的每道工序所使用的時(shí)間及每道工序的可用時(shí)間、每種家具的利潤(rùn)等數(shù)據(jù)如表1-3所示。問(wèn)工廠應(yīng)如何安排生產(chǎn),才能使總利潤(rùn)最大?表1-3家具生產(chǎn)數(shù)據(jù)生產(chǎn)工序所需時(shí)間可用時(shí)間(小時(shí))一二三四五成型346233600打磨435643950上漆233432800利潤(rùn)(百元)2.734.52.53表1習(xí)題1.22. 某公司受委托,準(zhǔn)備把120萬(wàn)元投資兩種基金A和B,其中A基金的每單

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論