線性規(guī)劃問題及其數(shù)學(xué)模型

1、 （第二版）刁在筠等 編高等教育出版社運(yùn)籌學(xué)運(yùn)籌學(xué)第1章 線性規(guī)劃與單純形法第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型二. 線性規(guī)劃與目標(biāo)規(guī)劃第第1 1章章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法第2章 對偶理論與靈敏度分析第3章 運(yùn)輸問題第4章 目標(biāo)規(guī)劃第第1章章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型第2節(jié) 線性規(guī)劃問題的幾何意義第3節(jié) 單純形法第4節(jié) 單純形法的計算步驟第5節(jié) 單純形法的進(jìn)一步討論第6節(jié) 應(yīng)用舉例第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型 1.1 問題的提出 1.2 圖解法 1.3 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 1.4 線性規(guī)劃問題的解的概念第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)

2、模型 線性規(guī)劃是運(yùn)籌學(xué)的一個重要分支。線性規(guī)劃在理論上比較成熟，在實用中的應(yīng)用日益廣泛與深入。特別是在電子計算機(jī)能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計劃和管理決策等領(lǐng)域都可以發(fā)揮作用。它已是現(xiàn)代科學(xué)管理的重要手段之一。解線性規(guī)劃問題的方法有多種，以下僅介紹單純形法 。1.1 問題的提出 從一個簡化的生產(chǎn)計劃安排問題開始例 1 某工廠在計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如表1-1所示。資源 產(chǎn) 品 擁有量設(shè) 備1 2 8臺時原材料

3、 A 40 16 kg原材料 B04 12 kg續(xù)例1 該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利3元，問應(yīng)如何安排計劃使該工廠獲利最多? 如何用數(shù)學(xué)關(guān)系式描述這問題，必須考慮稱它們?yōu)闆Q策變量。產(chǎn)品的數(shù)量，分別表示計劃生產(chǎn)設(shè)III,21xx12416482212121x;x;xx,x ,x這是約束條件。即有量的限制的數(shù)量多少，受資源擁生產(chǎn)021x,x,即生產(chǎn)的產(chǎn)品不能是負(fù)值這是目標(biāo)。最大如何安排生產(chǎn)，使利潤,數(shù)學(xué)模型 0124164823221212121x,xxxxx:xxzmax約束條件目標(biāo)函數(shù)例2. 簡化的環(huán)境保護(hù)問題 靠近某河流有兩個化工廠(見圖1-1)，流經(jīng)第一化工廠的河流

4、流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。 圖1-1續(xù)例2 第一 化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。這兩個工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米。 第二 化工廠處理工業(yè)污水的成本是800元/萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最小。建模型之前的分析和計算設(shè)設(shè)：第一化工廠每天

5、處理工業(yè)污水量為x1萬立方米，第二化工廠每天處理工業(yè)污水量為x2萬立方米 100027004128021000250022211)x.()x(.)x(工廠后的水質(zhì)要求：經(jīng)第工廠前的水質(zhì)要求：經(jīng)第數(shù)學(xué)模型0,4 . 126 . 18 . 018001000min212121121xxxxxxxxxz約束條件目標(biāo)函數(shù)共同的特征(1)每一個線性規(guī)劃問題都用一組決策變量 表示某一方案，這組決策變量的值就代表一個具體方案。一般這些變量取值是非負(fù)且連續(xù)的；(2)要有各種資源和使用有關(guān)資源的技術(shù)數(shù)據(jù)，創(chuàng)造新價值的數(shù)據(jù)；nx,x,x21)n,j;m,i (c;ajij11共同的特征（繼續(xù)）(3) 存在可以量化

6、的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示;(4) 要有一個達(dá)到目標(biāo)的要求，它可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來表示。按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化或最小化。它們的對應(yīng)關(guān)系可用表格表示：nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21價值系數(shù)動活資源決策變量線性規(guī)劃的一般模型形式 ).(x,x ,xb),(xaxaxa).(b),(xaxaxab),(xaxaxa).(xcxcxczmax(min)nmnmmmnnnnnn310211121221122222121112121112211約束條件目標(biāo)函數(shù)1.2 圖解法

7、例1是二維空間（平面）線性規(guī)劃問題，可用作圖法直觀地來表述它的求解。因存在 必須在直角坐標(biāo)的第1象限內(nèi)作圖，求解。021x ,x圖1-20124164223221212121x,xxxxxxxzmax圖1-3 目標(biāo)值在（4，2）點，達(dá)到最大值14目標(biāo)函數(shù)2132xxzmax表示一簇平行線33212zxx可能出現(xiàn)的幾種情況（1）無窮多最優(yōu)解(多重最優(yōu)解)，見圖1-4（2）無界解，見圖1-5-1（3）無可行解，見圖1-5-2圖1-4 無窮多最優(yōu)解(多重最優(yōu)解) 目標(biāo)函數(shù) max z=2x1+4x2 圖1-5-1 無界解ox ,xxxxxxxzmax2121121242 無可行解當(dāng)存在矛盾的約束條件

8、時，為無可行域。85 . 121xx如果在例1的數(shù)學(xué)模型中增加一個約束條件: 該問題的可行域為空集空集，即無可行解， 圖1-5-2 不存在可行域85121x.x增加的約束條件1.3 線性規(guī)劃問題的標(biāo)準(zhǔn)型式0aczmax212211222221211121211122111nnnmnmmnnnnnnx ,x ,xbxaxaxabxaxaxabxaxaxxcxcx:M約束條件：目標(biāo)函數(shù)：線性規(guī)劃問題的幾種表示形式n ,j,xm,i,bxaxczmax:Mjnjijijnjjj21021111約束條件：目標(biāo)函數(shù)：用向量表示為：n,j;bbbb;aaaP;xxxX;c,c,cCn,j,xbxPCXzm

9、ax:Mmmjjjjnnjnjjj 212102121212111約束條件：目標(biāo)函數(shù)：用矩陣表示為：Tnnmnmn x,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000決策變量向量：；資源向量：零向量：系數(shù)矩陣：約束條件：目標(biāo)函數(shù)：如何變換為標(biāo)準(zhǔn)型：(1) 若要求目標(biāo)函數(shù)實現(xiàn)最小化，即min z=CX。這時只需將目標(biāo)函數(shù)最小化變換求目標(biāo)函數(shù)最大化，即令z= -z，于是得到max z= -CX。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形式一致了。(2) 約束方程為不等式。這里有兩種情況：一種是約束方程為“”不等式，則可在“”不等式的左端加入非負(fù)松弛變量，把原“”不等式變

10、為等式；另一種是約束方程為“”不等式，則可在“”不等式的左端減去一個非負(fù)剩余變量(也可稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束條件。下面舉例說明。例3 將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。 例1的數(shù)學(xué)模型,加松馳變量后0124164820124164823232432152413212121215432121x ,x ,x ,x ,xxxxxxxxx ,xxxxxxxxxxzmaxxxzmax(3) 若存在取值無約束的變量xk,可令,其中。 kkkxxx0,kkxx例4 將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型為無約束3213213213213210533732x;x ,xxxxxxxxxxxxxzmin處理的

11、步驟：(1) 用x4-x5替換x3，其中x4，x50；(2) 在第一個約束不等式號的左端加入松弛變量x6；(3) 在第二個約束不等式號的左端減去剩余變量x7；(4) 令z= -z，把求min z 改為求max z，即可得到該問題的標(biāo)準(zhǔn)型例4的標(biāo)準(zhǔn)型0,5)(232)(7)(00)(32max7654214217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz1.4 線性規(guī)劃問題的解的概念 1.可行解 2.基 3.基可行解 4.可行基1. 可行解滿足約束條件(1-5)，(1-6)式的解X=(x1,x2，xn)T，稱為線性規(guī)劃問題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大

12、值的可行解稱為最優(yōu)解。)(n,j,x)(m,i ,bxa)(xczmaxjnjijijnjjj61210512141112. 基，基向量，基變量為基變量。為基向量，為線性規(guī)劃問題的基。稱階非奇異子矩陣中的是系數(shù)矩陣)m,j()m,j(P,P,PaaaaaaaaaBmmBmmmmmmm21x21PB0BAjj212122221112113.基可行解 滿足非負(fù)條件（1-6）的基解，稱為基可行解. 基可行解的非零分量的數(shù)目也不大于m，并且都是非負(fù)的。 是基可行解43210Q,Q,Q,Q,4. 可行基 對應(yīng)于基可行解的基，稱為可行基。 約束方程組(1-5)具有基解的數(shù)目最多是 個。一般基可行解的數(shù)目要小于基解的數(shù)目。 以上提到的幾種解的概