運(yùn)籌學(xué)第1章線性規(guī)劃與單純形法-第1節(jié)

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

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

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

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

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

6、nx,x,x21)n,j;m,i (c;ajij11共同的特征（繼續(xù)）(3) 存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示;(4) 要有一個(gè)達(dá)到目標(biāo)的要求，它可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。它們的對(duì)應(yīng)關(guān)系可用表格表示：nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21價(jià)值系數(shù)動(dòng)活資源決策變量線性規(guī)劃的一般模型形式 ) 3 . 1 (0,),()2 . 1 (),(),() 1 . 1 (max(min)21221122222121112121112211nmnm

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

8、2x1+4x2 圖1-5-1 無(wú)界解ox ,xxxxxxxzmax2121121242通常因?yàn)楹鲆暳四臣s束條件 無(wú)可行解當(dāng)存在矛盾的約束條件時(shí)，為無(wú)可行域。85 . 121xx如果在例1的數(shù)學(xué)模型中增加一個(gè)約束條件: 該問(wèn)題的可行域?yàn)榭占占?，即無(wú)可行解， 圖1-5-2 不存在可行域85121x.x增加的約束條件通常因?yàn)橛胁槐匾募s束條件簡(jiǎn)單直觀的結(jié)論（猜想） 1.可行域非空時(shí)是凸多邊形，有界或無(wú)界。 2.若有最優(yōu)解，則在可行域某頂點(diǎn)達(dá)到。 3.若在兩個(gè)頂點(diǎn)達(dá)到最優(yōu)，則有無(wú)窮多最優(yōu)解。1.3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型11221111221121122222112212:,01nnnnnnmmmnn

9、mnMmax zc xc xc xa xa xa xba xa xaxbaxaxaxbx xx目標(biāo)函數(shù)：約束條件：mn 線性規(guī)劃問(wèn)題的幾種表示形式n ,j,xm,i,bxaxczmax:Mjnjijijnjjj21021111約束條件：目標(biāo)函數(shù)：用向量表示為：n,j;bbbb;aaaP;xxxX;c,c,cCn,j,xbxPCXzmax:Mmmjjjjnnjnjjj 212102121212111約束條件：目標(biāo)函數(shù)：用矩陣表示為：Tnnmnmn x,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000決策變量向量：；資源向量：零向量：系數(shù)矩陣：約束條件：目

10、標(biāo)函數(shù)：如何變換為標(biāo)準(zhǔn)型：(1) 若要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化，即min z=CX。這時(shí)只需將目標(biāo)函數(shù)最小化變換求目標(biāo)函數(shù)最大化，即令z= -z，于是得到max z= -CX。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形式一致了。(2) 約束方程為不等式。這里有兩種情況：一種是約束方程為“”不等式，則可在“”不等式的左端加入非負(fù)松弛變量，把原“”不等式變?yōu)榈仁?；另一種是約束方程為“”不等式，則可在“”不等式的左端減去一個(gè)非負(fù)剩余變量(也可稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束條件。下面舉例說(shuō)明。例3 將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。 例1的數(shù)學(xué)模型,加松馳變量后0,124164820,1241648200032ma

11、x32max432152413212121215432121xxxxxxxxxxxxxxxxxxxxxxxzxxz(3) 若存在取值無(wú)約束的變量xk,可令,其中。 kkkxxx0,kkxx例4 將下述線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型為無(wú)約束3213213213213210533732x;x ,xxxxxxxxxxxxxzmin處理的步驟：(1) 用x4-x5替換x3，其中x4，x50；(2) 在第一個(gè)約束不等式號(hào)的左端加入松弛變量x6；(3) 在第二個(gè)約束不等式號(hào)的左端減去剩余變量x7；(4) 令z= -z，把求min z 改為求max z，即可得到該問(wèn)題的標(biāo)準(zhǔn)型例4的標(biāo)準(zhǔn)型0,5)(232)(7)(0

12、0)(32max7654214217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz1.4 線性規(guī)劃問(wèn)題的解的概念 1.可行解 2.基 3.基可行解 4.可行基1. 可行解滿足約束條件(1-5)，(1-6)式的解X=(x1,x2，xn)T，稱為線性規(guī)劃問(wèn)題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。6)(1, 2 , 1, 05)(1, 2 , 1,4)(1max11njxmibxaxczjnjijijnjjj2. 基，基解，基向量，基變量為基變量。為基向量，為線性規(guī)劃問(wèn)題的基。稱階非奇異子矩陣中的是系數(shù)矩陣)m,j()m,j(P,P,PaaaaaaaaaBmmBmmmmmmm21x21PB0BAjj212122221112113.基可行解 滿足非負(fù)條件（1-6）的基解，稱為基可行解. 基可行解的非零分量的數(shù)目也不大于m，并且都是非負(fù)的。 ?, 04321頂點(diǎn)是基可行解QQQQ4. 可行基 對(duì)應(yīng)于基可行解的基，稱為可行基。 約束方程組(1-5)具有基解的數(shù)目最多是 個(gè)。一般基可行解的數(shù)目要小于基解的數(shù)目。 以上提到的幾種