線性規(guī)劃第一講一般線性規(guī)劃問題的數(shù)學模型.ppt
線性規(guī)劃問題的提出線性規(guī)劃的基本概念線性規(guī)劃的數(shù)學模型線性規(guī)劃問題的標準形式,1.1一般線性規(guī)劃問題及其數(shù)學模型,線性規(guī)劃簡介,LinearProgramming,LP是運籌學的重要分支之一,在實際中應用得較廣泛,其方法也較成熟,借助計算機,使得計算更方便,應用領域更廣泛和深入。線性規(guī)劃通常研究資源的最優(yōu)利用、設備最佳運行、成本收益平衡和網(wǎng)絡配送等問題。例如,當任務或目標確定后,如何統(tǒng)籌兼顧,合理安排,用最少的資源(如資金、設備、原標材料、人工、時間等)去完成確定的任務或目標;企業(yè)在一定的資源條件限制下,如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益(如產(chǎn)品量最多、利潤最大)。,線性規(guī)劃簡介,1902年,JuliusFarkas發(fā)表論文闡述線性規(guī)劃的問題;1938年,英國,康德進行較為詳細的研究;1947年,英國,GeorgeDantzig單純形法,從而為線性規(guī)劃的推廣奠定了基礎。,1.1.1問題的提出,例1:生產(chǎn)計劃問題,決策變量(Decisionvariables)目標函數(shù)(Objectivefunction)約束條件(Constraintconditions),基本概念,問題中要確定的未知量,表明規(guī)劃中的用數(shù)量表示的方案、措施,可由決策者決定和控制。,它是決策變量的函數(shù),指決策變量取值時受到的各種資源條件的限制,通常表達為含決策變量的等式或不等式。,是問題中要確定的未知量,表明規(guī)劃中的用數(shù)量表示的方案、措施,可由決策者決定和控制。,第1步-確定決策變量,設I的產(chǎn)量II的產(chǎn)量利潤,第2步-定義目標函數(shù),maxZ=x1+x2,Note:maxstandsformaximize,maxZ=2x1+3x2,第2步-定義目標函數(shù),第3步-表示約束條件,x1+2x284x1164x212x1、x20,該計劃的數(shù)學模型,目標函數(shù)maxZ=2x1+3x2約束條件x1+2x284x1164x212x1、x20,x1,x2,線性規(guī)劃問題的共同特征,一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標函數(shù)是線性的。求目標函數(shù)最大化或最小化,方法總結(jié):如何建立線性規(guī)劃數(shù)學模型研究的問題是求什么,即設置決策變量;(由研究者供決策部門加以確定,故得名)問題要達到的目標是什么,即建立目標函數(shù),目標函數(shù)一定是決策變量的線性函數(shù)并且求最大值或求最小值;限制達到目標的條件是什么,即建立約束條件。,例2餅干生產(chǎn)問題某廠生產(chǎn)兩類餅干,需攪拌機A1,成形機A2,烘箱A3三種設備,每天的所需機時及機時限制,利潤指標如下表,問如何制訂生產(chǎn)計劃,可使獲得最高利潤?,【解】設x1、x2為每天生產(chǎn)、兩種餅干的產(chǎn)量(單位:噸),則目標函數(shù)是,約束條件有:,攪拌機約束,成形機約束,烘箱約束,非負約束,本問題的數(shù)學模型,某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設備A、B上加工,需要消耗材料C、D,按工藝資料規(guī)定,單件產(chǎn)品在不同設備上加工及所需要的資源如表二所示。已知在計劃期內(nèi)設備的加工能力各為200臺時,可供材料分別為360、300公斤;每生產(chǎn)一件甲、乙、丙三種產(chǎn)品,企業(yè)可獲得利潤分別為40、30、50元,假定市場需求無限制。企業(yè)決策者應如何安排生產(chǎn)計劃,使企業(yè)在計劃期內(nèi)總的利潤收入最大?,例3、最優(yōu)生產(chǎn)計劃問題,表二產(chǎn)品資源消耗,【解】設x1、x2、x3分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學模型為:,目標函數(shù),資源約束,例4最優(yōu)人員安排某商場決定:營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天,輪流休息。根據(jù)統(tǒng)計,商場每天需要的營業(yè)員如表三所示。,表三營業(yè)員需要量統(tǒng)計表,商場人力資源部應如何安排每天的上班人數(shù),使商場總的營業(yè)員最少。,【解】設xj(j=1,2,7)為休息2天后星期一到星期日開始上班的營業(yè)員,則這個問題的線性規(guī)劃模型為,目標函數(shù):總?cè)藬?shù)最少,約束條件:上班人數(shù)不少于每天需要人數(shù),