數(shù)學(xué)建模：線性規(guī)劃問題(超全)

線性規(guī)劃問題的提出線性規(guī)劃的基本概念線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃問題的標準形式繼續(xù)返回第一節(jié)線性規(guī)劃問題

及其數(shù)學(xué)模型問題的提出例:生產(chǎn)計劃問題產(chǎn)品I產(chǎn)品2如何安排生產(chǎn)使利潤最大？決策變量（Decisionvariables）目標函數(shù)（Objectivefunction）約束條件（Constraintconditions）可行域（Feasibleregion)最優(yōu)解（Optimalsolution)基本概念問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。它是決策變量的函數(shù)指決策變量取值時受到的各種資源條件的限制，通常表達為含決策變量的等式或不等式。滿足約束條件的決策變量的取值范圍可行域中使目標函數(shù)達到最優(yōu)的決策變量的值是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。第1步-確定決策變量設(shè)——I的產(chǎn)量——II的產(chǎn)量——利潤第2步--定義目標函數(shù)MaxZ=x1+x2決策變量

MaxZ=2x1+3x2系數(shù)第2步--定義目標函數(shù)對我們有何限制?第3步--表示約束條件

x1+2x2

84x1

164x2

12x1、x2

0該計劃的數(shù)學(xué)模型

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0x1

x2線性規(guī)劃問題的共同特征一組決策變量X表示一個方案,一般X大于等于零。約束條件是線性等式或不等式。目標函數(shù)是線性的。求目標函數(shù)最大化或最小化

線性規(guī)劃模型的一般形式???????íì33=￡+++3=￡+++3=￡++++++=0,...,,),(......................................................),(...),(......)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax線性規(guī)劃問題的標準形式標準形式為:目標函數(shù)最大約束條件等式?jīng)Q策變量非負

簡寫為

用矩陣表示C—價值向量b—資源向量X—決策變量向量

minZ=CX等價于maxZ’=-CX“”約束：加入非負松馳變量一般線性規(guī)劃問題的標準化例：

目標函數(shù)MaxZ=2x1+3x2約束條件x1+2x2

84x1

164x2

12x1、x2

0

minZ=CX等價于maxZ’=-CX“”約束：加入非負松馳變量一般線性規(guī)劃問題的標準形化例：

“”約束：減去非負剩余變量；

Max例：可正可負（即無約束）；

解：標準形為線性規(guī)劃模型舉例(一)運輸問題(二)布局問題(三)分派問題(四)生產(chǎn)計劃問題(五)合理下料問題線性規(guī)劃模型的條件（1）要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；（2）存在著多種方案；（3）要求達到的目標是在一定約束條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來描述。(一)運輸問題設(shè)某種物資有m個產(chǎn)地，A1，A2，…，Am；聯(lián)合供應(yīng)n個銷地：B1，B2，…，Bn。各產(chǎn)地產(chǎn)量（單位：噸），各銷地銷量（單位：噸），各產(chǎn)地至各銷地單位運價（單位：元／噸）如下表所示。應(yīng)如何調(diào)運，才使總運費最少？表中：ai表示產(chǎn)地Ai的產(chǎn)量(i=1，2，…，m)；

bj表示產(chǎn)地Bj的產(chǎn)量(j=1，2，…，n)；

cij表示AiBj間的單位運價（元／噸）(i=1，2，…，m;j=1，2，…，n)；單價（元／噸）銷地產(chǎn)地產(chǎn)量（噸）

B1B2…BnA1A2

┇

Am銷量（噸）

C11C12…C1nC21C22…C2n

┇

┇

…┇Cm1Cm2…Cmnb1b2…bna1a2┇

am

設(shè)xij表示由產(chǎn)地Ai運往銷地Bj的物資數(shù)(i=1,2,…,m;j=1,2,…,n)。那么，上述運輸問題的數(shù)學(xué)模型為：求一組變量xij(i=1,2,…,m;j=1,2,…,n)

的值,使它滿足即(一)運輸問題(Ⅰ)產(chǎn)銷平衡

(Ⅰ)產(chǎn)銷平衡

(Ⅱ)產(chǎn)銷不平衡

約束條件產(chǎn)地Ai發(fā)到各銷地的發(fā)量總和應(yīng)等于Ai的產(chǎn)量各產(chǎn)地發(fā)到銷地Bj的發(fā)量總和應(yīng)等于Bj的銷量調(diào)運量不能為負數(shù)0(Ⅰ)產(chǎn)銷平衡的模型約束條件產(chǎn)地Ai發(fā)到各銷地的發(fā)量總和應(yīng)等于Ai的產(chǎn)量各產(chǎn)地發(fā)到銷地Bj的發(fā)量總和應(yīng)等于Bj的銷量調(diào)運量不能為負數(shù)0(Ⅰ)產(chǎn)銷平衡的模型(Ⅰ)產(chǎn)銷平衡的模型()()()njmixnjbxmiaxijijiijmijnj,,1;,,2,1

0,,2,1

,,2,1

11

LLLL==3====??==約束條件()()()njmixnjbxmiaxijijiijmijnj,,1;,,2,1

0,,2,1

,,2,1

11

LLLL==3====??==(Ⅰ)產(chǎn)銷平衡的模型這一問題的數(shù)學(xué)模型應(yīng)為：

求一組變量的值,使它滿足(Ⅱ)產(chǎn)銷不平衡—產(chǎn)大于銷(一)運輸問題調(diào)運量不能為負數(shù)(Ⅱ)產(chǎn)銷不平衡—產(chǎn)大于銷的模型產(chǎn)地Ai發(fā)到各銷地的發(fā)量總和不超過Ai的產(chǎn)量各產(chǎn)地發(fā)到銷地Bj的發(fā)量總和應(yīng)等于Bi的銷量約束條件（二）布局問題作物布局

在n塊地上種植m種作物，已知各塊土地畝數(shù)、各種作物計劃播種面積及各種作物在各塊的單產(chǎn)（每畝的產(chǎn)量）如表—（與運輸問題相似），問：如何合理安排種植計劃，才使總產(chǎn)量最多。

產(chǎn)量（噸）

B1B2…BnA1A2

┇

Am銷量（噸）

C11C12…C1nC21C22…C2n

┇

┇

…┇Cm1Cm2…Cmnb1b2…bna1a2┇

am（二）布局問題n塊土地每畝的產(chǎn)量m種農(nóng)作物總產(chǎn)量最多方法與運輸問題類似銷地產(chǎn)地單價（元／噸）(三）分派問題

設(shè)有n件工作分派給n人去做，每人只做一件工作且每件工作只分派一人去做。設(shè)Ai完成Bj的工時為。問：應(yīng)如何分派才使完成全部工作的總工時最少。(完成全部工作的總工時最少）(三）分派問題解：設(shè)為Bj分派給人Ai情況：

Bj分派給Ai時，；不分派給Ai時，。那末這一問題的數(shù)學(xué)模型為：ijx1=ijx()njixij,,2,1,0L==

求一組變量的值，使目標函數(shù)的值最小。??===nimjijijxcs11

()njixij,,2,1,L=分派問題的模型約束條件目標函數(shù)??===nimjijijxcs11

min()()()njixnixnjxijijijnjni,,2,1,

1

0,,2,1

1,,2,1

111LLL======??==或每件工作只分派一人去做每人只做一件工作每人對每件工作只有做與不做兩種情況(四）生產(chǎn)組織與計劃問題(Ⅰ)總的加工成本最低(Ⅱ)生產(chǎn)存儲問題

某工廠用機床加工種零件。在一個生產(chǎn)周期，各機床只能工作的機時、工廠必須完成各零件加工數(shù)、各機床加工每個零件的時間（單位：機時／個）和加工每個零件的成本（單位：元／個）如表1及表2所示。問：在這個生產(chǎn)周期，怎樣安排各機床的生產(chǎn)任務(wù)，才能既完成加工任務(wù)，又使總的加工成本最低。(Ⅰ)總的加工成本最低(四）生產(chǎn)組織與計劃問題加工每個零件的時間零件機床在一周期能工作機時

B1B2…BnA1A2

┇

Am必須加工零件數(shù)

C11C12…C1nC21C22…C2n

┇

┇

…┇Cm1Cm2…Cmnb1b2…bna1a2┇

am表1：加工每個零件的時間(Ⅰ)總的加工成本最低(四）生產(chǎn)組織與計劃問題表

2：加工每個零件的成本(Ⅰ)總的加工成本最低(四）生產(chǎn)組織與計劃問題

零件加工每個零件的成本機床

B1B2…BnA1A2

┇

Am

d11d12…d1nd21d22…d2n

┇

┇…┇dm1dm2…dmn

求一組變量的值,使它滿足

解：設(shè)為機床在下一生產(chǎn)周期加工零件的個數(shù)。這一問題的數(shù)學(xué)模型為：(Ⅰ)總的加工成本最低(四）生產(chǎn)組織與計劃問題(加工零件個數(shù)不能為負數(shù)、分數(shù)）(機床加工各零件總機時不能超過能工作機時）(各機床加工零件的總數(shù)不能少于需要數(shù)）約束條件()()()njmixnjbxmiaxcijiijiijijninj,,2,1,,,2,1

,

0,,2,1

,,2,1

11LLLL==3=3=￡??==整數(shù)(Ⅰ)總加工成本最低的模型(四）生產(chǎn)組織與計劃問題(Ⅰ)總加工成本最低的模型(四）生產(chǎn)組織與計劃問題約束條件目標函數(shù)()()()njmixnjbxmiaxcijiijiijijninj,,2,1,,,2,1

,

0,,2,1

,,2,1

11LLLL==3=3=￡??==整數(shù)??===njmiijijxds11

min某廠簽訂了5種產(chǎn)品上半年的交貨合同。已知各產(chǎn)品在第月

的合同交貨量，該月售價成本價及生產(chǎn)1件時所需工時。該廠第月的正常生產(chǎn)工時為，但必要時可加班生產(chǎn)，第月允許的最多加班工時不超過，并且加班時間內(nèi)生產(chǎn)出來的產(chǎn)品每件成本增加額外費用元。若生產(chǎn)出來的產(chǎn)品當(dāng)月不交貨，每件庫存1個月交存貯費元。試為該廠設(shè)計一個保證完成合同交貨，又使上半年預(yù)期盈利總額為最大的生產(chǎn)計劃安排。(四）生產(chǎn)組織與計劃問題(Ⅱ)生產(chǎn)存儲問題()5,,1L=ij()6,,1L=jijDijsijcijajjtjjt'ijc'ip解：設(shè)為種產(chǎn)品月份在正常時間內(nèi)生產(chǎn)的數(shù)量，為第種產(chǎn)品月份在加班時間內(nèi)生產(chǎn)的數(shù)量。該廠盈利總額為生產(chǎn)的5種產(chǎn)品銷售價減去成本和庫存費用。問題的限制條件有兩項：

一是各個月的正常和加班的允許工時；

二是滿足交貨要求。

(四）生產(chǎn)組織與計劃問題(Ⅱ)生產(chǎn)存儲問題jijx'ijxiij該生產(chǎn)存儲問題的線性規(guī)劃模型為目標函數(shù)盈利總額=生產(chǎn)的5種產(chǎn)品銷售價

—成本和庫存費用(四）生產(chǎn)組織與計劃問題

一是各個月的正常和加班的允許工時；二是滿足交貨要求。

約束條件()()()()?????????íì==3=3+=￡=￡????====

,6)1,j,5;1,(i

0

6,,1

'6,,1

''6,,1

115151LLLLLijikikikjijijjijijxjDxxjtxajtxajkjkii

設(shè)用某原材料(條材或板材)下零件