線性規(guī)劃第一講一般線性規(guī)劃問題的數(shù)學(xué)模型.ppt

《線性規(guī)劃第一講一般線性規(guī)劃問題的數(shù)學(xué)模型.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《線性規(guī)劃第一講一般線性規(guī)劃問題的數(shù)學(xué)模型.ppt（21頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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