《數(shù)學(xué)規(guī)劃模型》PPT課件.pptVIP

第6章 數(shù)學(xué)規(guī)劃模型,在一系列客觀或主觀限制條件下，尋求使關(guān)注的某個或多個指標(biāo)達(dá)到最大（或最?。┑臎Q策。 例如：運(yùn)輸方案要在滿足物資需求和裝載條件下安排從各供應(yīng)點(diǎn)到各需求點(diǎn)的運(yùn)量和路線，使運(yùn)輸總費(fèi)用最低；生產(chǎn)計劃要按照產(chǎn)品工藝流程和顧客需求，制定原料、零件、部件等訂購、投產(chǎn)的日程和數(shù)量，盡量降低成本使利潤最高。 上述這些決策問題通常稱為優(yōu)化問題 。 雖然最優(yōu)化可以追溯到十分古老的極值問題，然而，它成為一門獨(dú)立的學(xué)科是在上世紀(jì)40年代末，是在1947年Dantzing提出求解一般線性規(guī)劃問題的單純型法之后。,問題驅(qū)動：高等教育收費(fèi),學(xué)費(fèi)問題涉及到每一個大學(xué)生及其家庭，是一個敏感而又復(fù)雜的問題：過高的學(xué)費(fèi)會使很多學(xué)生無力支付，過低的學(xué)費(fèi)又使學(xué)校財力不足而無法保證質(zhì)量。高等教育屬于非義務(wù)教育，其經(jīng)費(fèi)在世界各國都由政府財政撥款、學(xué)校自籌、社會捐贈和學(xué)費(fèi)收入等幾部分組成。對適合接受高等教育的經(jīng)濟(jì)困難的學(xué)生，一般可通過貸款和學(xué)費(fèi)減、免、補(bǔ)等方式獲得資助，品學(xué)兼優(yōu)者還能享受政府、學(xué)校、企業(yè)等給予的獎學(xué)金。 學(xué)費(fèi)問題近來在各種媒體上引起了熱烈的討論。據(jù)中國國情，利用數(shù)學(xué)建模的方法，收集諸如國家生均撥款、培養(yǎng)費(fèi)用、家庭收入等相關(guān)數(shù)據(jù)，就幾類學(xué)校或?qū)I(yè)的學(xué)費(fèi)標(biāo)準(zhǔn)進(jìn)行定量分析，得出明確、有說服力的結(jié)論。,問題背景分析,要確保有良好的高等教育質(zhì)量，必須有相應(yīng)的經(jīng)費(fèi)保障。高等教育的學(xué)費(fèi)問題涉及到每一個大學(xué)生及其家庭。根據(jù)相關(guān)規(guī)定，高等教育屬于非義務(wù)教育，其成本主要是根據(jù)高等教育收益分享情況進(jìn)行分?jǐn)?，即遵循“誰收益、誰負(fù)擔(dān)”的原則?；诖死碚?，我國于1993年試行并軌招生，繳費(fèi)上學(xué)制度開始在部分高校試行。到1997年，全國高校全部并軌收費(fèi)。然而，自高等教育實(shí)行收費(fèi)政策以來，收費(fèi)標(biāo)準(zhǔn)出現(xiàn)了逐步攀升的情況，以至于學(xué)費(fèi)水平在一定程度上成了人們關(guān)注的社會問題，也成為人們爭議的社會焦點(diǎn)。,高等教育的經(jīng)費(fèi)主要由政府撥款、學(xué)校自籌、社會捐贈和學(xué)費(fèi)收入等幾部分組成，其中由受教育者及其家庭所承擔(dān)的學(xué)費(fèi)是本文主要的討論對象。目前學(xué)費(fèi)收入已成為高等學(xué)校辦學(xué)經(jīng)費(fèi)的主要來源之一，也已成為維系學(xué)生與學(xué)校經(jīng)濟(jì)關(guān)系的主要紐帶。,目標(biāo)分析,高等教育收費(fèi)要滿足如下幾個需求因素： 目標(biāo)1：培養(yǎng)質(zhì)量指標(biāo)（師資力量、教育設(shè)備、教學(xué)氛圍）； 目標(biāo)2：學(xué)生就讀指標(biāo)； 目標(biāo)3：辦學(xué)收益指標(biāo)（辦學(xué)獲利）； 目標(biāo)4：學(xué)生收益指標(biāo)。 這是一個多因素的問題，多因素分析的方法有很多，解決高等教育收費(fèi)問題的方法也有很多，但是結(jié)合實(shí)際，主要考慮制定最合理的學(xué)費(fèi)價格和生均獎貸助學(xué)金。 而“最”在數(shù)學(xué)上通常就是我們所說的優(yōu)化問題。,6.1規(guī)劃模型簡介,模型分類 在很多實(shí)際問題中，所能夠提供的決策變量取值受到很多因素的制約，這樣就產(chǎn)生了一般的優(yōu)化模型，統(tǒng)稱為數(shù)學(xué)規(guī)劃模型。按照數(shù)學(xué)規(guī)劃模型的具體特征可以將數(shù)學(xué)規(guī)劃分為：線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，多目標(biāo)規(guī)劃，目標(biāo)規(guī)劃等。,規(guī)劃問題結(jié)構(gòu)（三要素）,1、決策變量，通常是該問題要求解的那些未知量； 2、目標(biāo)函數(shù)，通常是該問題要優(yōu)化（最小或最大）的那個目標(biāo)的數(shù)學(xué)表達(dá)式； 3、約束條件，由該問題對決策變量的限制條件給出，即允許取值的范圍，稱為可行域，常用一組關(guān)于的不等式（也可以有等式）來界定 。,規(guī)劃模型的一般形式,規(guī)劃模型的分類,1、在模型中若目標(biāo)函數(shù)和約束條件中的函數(shù)均為線性函數(shù) ，則稱為線性規(guī)劃（簡記為LP），否則就稱為非線性規(guī)劃（簡記為NLP）。 2、規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃（簡記為IP）。 3、若整數(shù)規(guī)劃模型中的決策變量只能取0或1，則稱模型為0-1規(guī)劃 。 如不加特殊說明，整數(shù)規(guī)劃一般指整數(shù)線性規(guī)劃,例1,s.t.,例2,s.t.,62數(shù)學(xué)規(guī)劃模型實(shí)例及求解,1、線性規(guī)劃問題數(shù)學(xué)模型 例2.1 加工奶制品的生產(chǎn)計劃 一奶制品加工廠用牛奶生產(chǎn)A1、A2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時加工成3公斤A1 ，或者在設(shè)備乙上用8小時加工成4公斤A2 。根據(jù)市場需求，生產(chǎn)的A1、A2能全部售出，且每公斤A1獲利24元，每公斤A2獲利16元。現(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480小時，并且設(shè)備甲每天至多能加工100公斤，設(shè)備乙的加工能力沒有限制。試為該廠制定一個生產(chǎn)計劃，使每天獲利最大。,決策變量 設(shè)每天用x1桶牛奶生產(chǎn)A1，用x2桶牛奶生產(chǎn)A2 目標(biāo)函數(shù) 設(shè)每天獲利為Z元。 x1桶牛奶可生產(chǎn)3x1公斤A1 ，獲利24*3x1 ， x2桶牛奶可生產(chǎn)4 x2公斤A2 ，獲利16* 4 x2 ，故Z= 24*3x1+ 16* 4 x2 約束條件 原料供應(yīng) 勞動時間 非負(fù)約束、均不能為負(fù)值,在LINGO模型窗口輸入如下： Max =72*x1+64*x2; X1+x2=50; 12*x1+8*x2=480; 3*x1=100;,用鼠標(biāo)單擊菜單中的求解命令（SOLVE）就可以得到解答， 結(jié)果窗口顯示如下： Global optimal solution found at iteration: 2 Objective value: 3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000,假定A,B,C,D四種產(chǎn)品價格隨產(chǎn)量的擴(kuò)大而遞減，其需求函數(shù)分別為,試確定四種產(chǎn)品的產(chǎn)量，以便使總收益最大。,例 設(shè)用甲、乙、丙三種有效資源生產(chǎn)A,B,C,D四種產(chǎn)品， 產(chǎn)品的資源消耗定額及資源的有效供應(yīng)量如表所示,解 設(shè)A,B,C,D四種產(chǎn)品的產(chǎn)量分別為x1,x2,x3和x4， 則問題的目標(biāo)函數(shù)（總收益函數(shù)）為：,注意到資源約束，上述問題可表為,下面用Lingo軟件來求解上述的例子， 打開Lingo執(zhí)行文件，編程如下： Model: max=11*x1+12*x2+13*x3+14*x4-x5; x5=0.01*(x1*x1+2*x2*x2+3*x3*x3+4*x4*x4); x1+2*x2+3*x3+2*x4200; 7*x1+9*x2+8*x3+x4300; 3*x1+x3+7*x4400; end 為了編制程序的方便，我們引入了中間變量 選擇菜單“Solve”進(jìn)行求解，得到輸出 Objective value: 1003.010 Variable Value Reduced Cost X1 0.000000 1.713858 X2 6.900608 0.4349500E-07 X3 23.00476 0.000000 X4 53.85646 0.000000 X5 132.8497 0.000000,。,某航空公司為滿足客運(yùn)量日益增長的需要， 欲購置一批新的遠(yuǎn)程、中程及短程客機(jī)。 每架遠(yuǎn)程客機(jī)價格6700萬元，中程客機(jī)5000萬元， 短程客機(jī)3500萬元。該公司現(xiàn)有資金7.5億元可用于購買飛機(jī)。 估計年凈利潤每架遠(yuǎn)程客機(jī)為420萬元， 中程客機(jī)300萬元，短程客機(jī)230萬元。 該公司現(xiàn)有熟練駕駛員可用來配備30架新飛機(jī)。 維修設(shè)備足以維修新增加40架新的短程客機(jī)， 每架中程客機(jī)的維修量相當(dāng)于4/3短程客機(jī)， 而每架遠(yuǎn)程客機(jī)的維修量相當(dāng)于5/3架短程客機(jī)。 為獲取最大利潤，該公司應(yīng)購買各類客機(jī)多少架？,設(shè)購買遠(yuǎn)程、中程、短程客機(jī)的數(shù)量分別為x1,x2,x3架,問題的數(shù)學(xué)模型為,， （目標(biāo)函數(shù)）,，,，,， （約束條件）,，,。,將上述模型輸入Lingo如下： max= 420*x1+300*x2+230*x3; 6700*x1+5000*x2+3500*x375000; x1+x2+x330; 5*x1+4*x2+3*x3120; gin(x1);gin(x2);gin(x3);,得到最優(yōu)解為,最優(yōu)解為,元,6.4多目標(biāo)規(guī)劃,在許多實(shí)際問題中，衡量一個方案的好壞標(biāo)準(zhǔn)往往不止一個，例如設(shè)計一個導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高. 這一類問題統(tǒng)稱為多目標(biāo)最優(yōu)化問題或多目標(biāo)規(guī)劃問題. 設(shè)在一段時間（比如兩年）內(nèi)，某市有b億元資金可用于投資，有m個項(xiàng)目，A1，A2,Am 可供選擇。若對第i個項(xiàng)目投資，需要資金bi億元，可安排勞動力ai人就業(yè)，消耗能源ei(t)標(biāo)準(zhǔn)煤，可獲利稅收入ci億元，若該市在這段時間內(nèi)的能耗限額為e(t)標(biāo)準(zhǔn)煤，有a個人急需安置就業(yè)，欲確定一個最佳的投資方案，使該市所獲得的利稅總收入最多、安置的勞動力最多，而能耗最少？,z1為所獲得的利稅總收入，,z2為安置的勞動力的總數(shù)，,z3為總能耗,改寫為如下形式：,，,，,多目標(biāo)規(guī)劃問題的求解 多目標(biāo)規(guī)