線性規(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ù),