1第一章線性規(guī)劃

2

運(yùn)籌學(xué)的一大分枝是數(shù)學(xué)規(guī)劃，而線性規(guī)劃又是數(shù)學(xué)規(guī)劃的重要組成部分。線性規(guī)劃從二十世紀(jì)40年代前后創(chuàng)始至今，其理論的完整、方法的多樣、應(yīng)用的廣泛，都遠(yuǎn)較運(yùn)籌學(xué)的其它分支來(lái)得成熟。

3

求解線性規(guī)劃最常用的方法——單純形法，由美國(guó)數(shù)學(xué)家丹捷格（G.B.Dantzig）于1947年提出，迄今為止，仍是一般意義下實(shí)際求解線性規(guī)劃最為有效的方法，被譽(yù)為20世紀(jì)最好的10個(gè)算法之一。盡管后來(lái)又陸續(xù)出現(xiàn)一系列新的方法，如橢球法（Xачиян法）以及以Karmarkar算法為基礎(chǔ)的內(nèi)點(diǎn)法等，但在實(shí)用上仍未完全取代單純形法。

4

目前，線性規(guī)劃的發(fā)展幾乎已被人們認(rèn)為是二十世紀(jì)中葉最重要的科學(xué)進(jìn)步之一，且在應(yīng)用領(lǐng)域已成為一種標(biāo)準(zhǔn)的工具，在發(fā)達(dá)國(guó)家，即使是中等規(guī)模的企業(yè)，也會(huì)因線性規(guī)劃的有效使用而節(jié)省數(shù)百萬(wàn)資金。5

在這一部分，按照：

§1-1數(shù)學(xué)模型

§1-2圖解法

§1-3單純形法

§1-4對(duì)偶規(guī)劃

§1-5靈敏度分析

§1-6運(yùn)輸問(wèn)題等六大部分內(nèi)容和順序進(jìn)行講授。6§1-1數(shù)學(xué)模型模型的定義：模型是研究者對(duì)客觀現(xiàn)實(shí)經(jīng)過(guò)思維抽象后用文字、圖表、符號(hào)、關(guān)系式以及實(shí)體模樣描述所認(rèn)識(shí)到的客觀對(duì)象。模型的分類(lèi)：模型一般分為數(shù)學(xué)模型和模擬模型。數(shù)學(xué)模型：也稱(chēng)符號(hào)模型，由決策變量和參數(shù)、約束條件以及目標(biāo)三項(xiàng)要素組成。三者之間建立的函數(shù)關(guān)系表現(xiàn)了現(xiàn)實(shí)系統(tǒng)的基本特征，其解可用適當(dāng)?shù)姆椒ㄇ蟮?。模擬模型：是采用一種易于求解的模型去模仿另一種難以求解的模型的方法。例如用電路系統(tǒng)去模擬一個(gè)力學(xué)系統(tǒng)等。7

成功使用線性規(guī)劃的前提之一是合理地構(gòu)造問(wèn)題的數(shù)學(xué)模型，圖1-1給出的是運(yùn)籌學(xué)（包括線性規(guī)劃）建模的一般步驟：模型準(zhǔn)備模型假設(shè)模型構(gòu)成模型檢驗(yàn)?zāi)Ｐ蛻?yīng)用模型分析模型求解實(shí)際問(wèn)題數(shù)據(jù)準(zhǔn)備圖1-18

下面，我們首先通過(guò)一些簡(jiǎn)單的范例來(lái)闡明什么是線性規(guī)劃、如何構(gòu)造問(wèn)題的數(shù)學(xué)模型并化為標(biāo)準(zhǔn)型。

一.范例例1、例2、例3

二.線性規(guī)劃的標(biāo)準(zhǔn)形式

1.線性規(guī)劃的一般形式

2.線性規(guī)劃的標(biāo)準(zhǔn)形式

3.非標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)化

4.標(biāo)準(zhǔn)形式的其它表示形式9一.范例例1:生產(chǎn)計(jì)劃問(wèn)題某工廠生產(chǎn)A、B兩種產(chǎn)品，其成本決定于所用的材料。已知單位產(chǎn)品所需材料量、材料日供應(yīng)量及單價(jià)如表1-1所示。若每生產(chǎn)A或B產(chǎn)品一個(gè)單位，所費(fèi)工資同為30元，又A、B的每單位銷(xiāo)售價(jià)分別為120元和150元。問(wèn)：工廠應(yīng)如何安排生產(chǎn)，才能使所獲總利潤(rùn)最大。10表1-1材料AB日供應(yīng)量(kg)材料單價(jià)(￥/kg)a621801.00b4104002.30c3521014.6011求解：

由表1-1可得：生產(chǎn)A、B產(chǎn)品均需要用到材料a、b和c。生產(chǎn)A產(chǎn)品的單位材料成本為:1.00×6+2.30×4+14.60×3=59(元)

單位工資成本為30（元）單位售價(jià)為120（元）因此，其單位利潤(rùn)為:120–59–30（工資）=31(元)材料AB日供應(yīng)量(kg)材料單價(jià)(￥/kg)a621801.00b4104002.30c3521014.6012生產(chǎn)B產(chǎn)品的單位材料成本為:1.00×2+2.30×10+14.60×5=98(元)

單位工資成本為30（元）單位售價(jià)為150（元）因此，其單位利潤(rùn)為:150–98–30（工資）=22(元)材料AB日供應(yīng)量(kg)材料單價(jià)(￥/kg)a621801.00b4104002.30c3521014.6013

設(shè)工廠日產(chǎn)A、B產(chǎn)品分別為x1,x2單位，可獲利潤(rùn)為z元，則所得總利潤(rùn)z為：

Z＝31x1+22x2

由于材料a的日供應(yīng)量為180kg，這是一個(gè)限制產(chǎn)量的條件，因此在確定A、B產(chǎn)品產(chǎn)量時(shí)，須考慮到的材料總量不能超出其日供應(yīng)量，即可用不等式表示為:

6x1+2x2≤18014

同理，對(duì)材料b、c，可得以下不等式：

4x1+10x2≤4003x1+5x2≤210

又因產(chǎn)品的生產(chǎn)數(shù)不可能是負(fù)數(shù)，故：

x1≥0，x2≥015

由此，問(wèn)題變?yōu)樵鯓舆x擇x1、x2

，在滿足上述一系列條件下，使得利潤(rùn)最大。其數(shù)學(xué)模型為求x1、x2，在滿足：的條件下，使得z=31x1+22x2取得最大值。通常記為：

maxz=31x1+22x216例2:環(huán)境保護(hù)問(wèn)題

某河流旁設(shè)置有甲、乙兩座化工廠，如圖1-2所示。已知流經(jīng)甲廠的河水日流量為500萬(wàn)立方米，在兩廠之間有一條河水日流量為200萬(wàn)立方米的支流。甲、乙兩廠每天產(chǎn)生工業(yè)污水分別為2萬(wàn)立方米及1.4萬(wàn)立方米，甲廠排出的污水經(jīng)過(guò)主流和支流交叉點(diǎn)P后已有20%被自然凈化。按環(huán)保要求，河流中工業(yè)污水的含量不得超過(guò)0.2%，為此，兩廠必須自行處理一部分工業(yè)污水。甲、乙兩廠處理每萬(wàn)立方米污水的成本分別為1000元及800元。問(wèn)：在滿足環(huán)保要求的條件下，各廠每天應(yīng)處理多少污水，才能使兩廠處理污水的總費(fèi)用最少？圖1-2甲廠乙廠P17解：設(shè)甲、乙兩廠每天分別處理污水量為x1、x2萬(wàn)立方米。在甲廠到P點(diǎn)之間，河水中污水含量不能超過(guò)0.2%，即應(yīng)滿足：

在P點(diǎn)到乙廠之間，河水中污水含量也不能超過(guò)0.2%，即應(yīng)滿足：

流經(jīng)乙廠后，河水中污水含量仍不能超過(guò)0.2%，即應(yīng)滿足：18

比較式(1-1)與式(1-2)，不難看出，只要式(1-2)能夠成立，式(1-1)就必然成立。由此，式(1-1)為冗余約束，可予以刪去。由：＝>x1≥1再由：＝>0.8x1+x2≥1.6由于各廠每天處理污水量不能為負(fù)數(shù)，也不會(huì)超過(guò)每天所產(chǎn)生的污水總量，故有:x1≥0，x2≥0，x1≤2，x2≤1.419

以z表示兩個(gè)工廠用于處理污水的總費(fèi)用，則應(yīng)使得z=1000x1+800x2取最小值，通常記為：

minz=1000x1+800x2

對(duì)以上各式加以整理簡(jiǎn)化，即得環(huán)保問(wèn)題的數(shù)學(xué)模型為求x1、x2，使得:

minz=1000x1+800x2且滿足:20例3:一維下料問(wèn)題

今有一批長(zhǎng)為7.4m的圓鋼，需用來(lái)截成長(zhǎng)為2.9m、2.1m、1.5m三種規(guī)格的材料，依次各需100根、100根、200根。問(wèn)：應(yīng)如何合理下料，才能使所用圓鋼根數(shù)最少？21解：將一根圓鋼截成所需的三種規(guī)格材料，所有可能的截法共有8種，如下表所示：顯然，為了節(jié)省圓鋼，不能用一根圓鋼只截一段一種規(guī)格的材料，而應(yīng)采用合理的套截方法。為此，必須綜合考慮這八種截法。設(shè)xj為第j種(j=1,2,…,8)截法所用圓鋼的根數(shù)，z為所用圓鋼的總根數(shù)，則:表1-2截法2.9m2.1m1.5m料頭(m)12010.121200.331110.941030.050301.160220.270130.880041.422

在確定各種截法的根數(shù)時(shí)，必須使所截三種規(guī)格材料的數(shù)量滿足規(guī)定要求，即長(zhǎng)為2.9m、2.1m、1.5m的材料依次分別為100根、100根、200根，這些限制條件可表成下列各等式：由于采用任何一種截法所需的圓鋼根數(shù)不可能是負(fù)數(shù)，故有：表1-2截法2.9m2.1m1.5m料頭(m)12010.121200.331110.941030.050301.160220.270130.880041.423由此，下料問(wèn)題的數(shù)學(xué)模型為求xj(j=1,2,…,8),使得：且滿足：表1-2截法2.9m2.1m1.5m料頭(m)12010.121200.331110.941030.050301.160220.270130.880041.424

從上述三個(gè)范例可以看出，它們屬于一類(lèi)具有共同特征的優(yōu)化問(wèn)題，由這幾個(gè)例子，可以得出：（1）建模的基本步驟★設(shè)置決策變量，它們體現(xiàn)解決問(wèn)題的方案?！锎_定目標(biāo)函數(shù)，它是決策變量的函數(shù)?！锎_定約束條件，它們是含有決策變量的不等式或等式?！锎_定決策變量的取值范圍，給出優(yōu)化方向。25（2）數(shù)學(xué)模型的共同結(jié)構(gòu)★存在一組決策變量，對(duì)它們可有非負(fù)要求；★存在一個(gè)以決策變量為自變量的目標(biāo)函數(shù)，且它為線性函數(shù)；★存在一組約束條件，且每個(gè)條件都是由決策變量構(gòu)成的線性不等式或等式；★結(jié)構(gòu)要求出這樣的變量組，或者說(shuō)決策向量X，在滿足約束條件和非負(fù)約束的同時(shí)，使相應(yīng)的目標(biāo)函數(shù)值達(dá)到最大或者最小。簡(jiǎn)言之，在一定條件下使目標(biāo)函數(shù)優(yōu)化。26（3）線性規(guī)劃定義求一組變量x1、x2、…、xn的值，使之在滿足關(guān)于這組變量的若干個(gè)線性等式或不等式的約束條件時(shí)的某個(gè)線性函數(shù)取到極大值(或極小值)。這些變量稱(chēng)為決策變量，所要優(yōu)化的函數(shù)稱(chēng)為目標(biāo)函數(shù)，決策變量是取實(shí)數(shù)值的連續(xù)變量。這樣的問(wèn)題稱(chēng)為線性規(guī)劃（Linear