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

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