數(shù)據(jù)處理與統(tǒng)計(jì)軟件補(bǔ)充資料

（內(nèi)部資料）

山東農(nóng)業(yè)大學(xué)

信息科學(xué)與工程學(xué)院

2016年6月

第一篇線性規(guī)劃

第一章線性規(guī)劃的數(shù)學(xué)模型

一、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、財(cái)貿(mào)工作等各項(xiàng)經(jīng)濟(jì)活動(dòng)中，必須提高經(jīng)濟(jì)效益，做到耗費(fèi)

較少的人力物力財(cái)力，創(chuàng)造出較多的經(jīng)濟(jì)價(jià)值。

提高經(jīng)濟(jì)效益可以通過(guò)兩種途徑L是技術(shù)方面的各種改進(jìn)例如工業(yè)生產(chǎn)上改善工藝，

使用新的設(shè)備和新型原材料等。二是生產(chǎn)組織和計(jì)劃的改進(jìn)，即合理安排人力物力資源，合

理組織生產(chǎn)過(guò)程，在條件不變的情況下，統(tǒng)籌安排，使總的經(jīng)濟(jì)效益最好。后者就是運(yùn)籌學(xué)

研究的主要內(nèi)容。

運(yùn)籌學(xué)有規(guī)劃論、排隊(duì)論、對(duì)策論等許多分支。線性規(guī)劃是其中的一個(gè)重要分支。早在

20世紀(jì)30年代末就有人從運(yùn)輸?shù)葐?wèn)題開(kāi)始研究它。它在運(yùn)籌學(xué)中是研究較早、發(fā)展較快、

應(yīng)用較廣、比較成熟的一個(gè)分支。它研究的問(wèn)題主要有兩類：一是一項(xiàng)任務(wù)確定后，如何統(tǒng)

籌安排，盡量做到用最少的人力物力資源去完成這一任務(wù)。二是已有一定數(shù)量的人力物力資

源，如何安排使用它們，使得完成任務(wù)最多。其實(shí)這兩類問(wèn)題是一個(gè)問(wèn)題的兩介方面，就是

所謂尋求整個(gè)問(wèn)題的某個(gè)整體指標(biāo)最優(yōu)的問(wèn)題。在經(jīng)濟(jì)領(lǐng)域里，這種問(wèn)題很多。

（—）運(yùn)輸問(wèn)題

在某一地區(qū)內(nèi)，有某種產(chǎn)品的產(chǎn)地與銷地各若干個(gè)，把這種產(chǎn)品從各個(gè)產(chǎn)地調(diào)運(yùn)到各個(gè)

銷地，調(diào)運(yùn)方案可以很多，應(yīng)如何調(diào)運(yùn)，才能使總的運(yùn)費(fèi)或運(yùn)輸量（即總的運(yùn)行噸公里數(shù)）

最少。

（二）生產(chǎn)的組織與計(jì)劃問(wèn)題

一個(gè)工廠或車間有各種不同類型的車床各若干臺(tái)，各種不同車床生產(chǎn)各種零件的效率不

同，在一個(gè)生產(chǎn)周期，應(yīng)如何安排個(gè)車床的生產(chǎn)時(shí)間，使得成套的產(chǎn)品總量最大。類似的還

有勞動(dòng)力的安排等問(wèn)題。

（三）合理下料問(wèn)題

在加工中需要將某類條材或板材下不同規(guī)格的毛坯，各種毛坯的數(shù)量也可能不同，應(yīng)如

何選取合適的裁法，使毛坯數(shù)量符合要求，并且使總料頭最少（即所用原材料最少1

（四）配料問(wèn)題

在食品、化工、冶煉等企業(yè)，常常用幾種原料，制成達(dá)到含有一定成分的產(chǎn)品，而這些

不同原料價(jià)格不同，應(yīng)如何決定配料的方案，才能使生產(chǎn)的產(chǎn)品所含成分合乎要求，而產(chǎn)品

的成本最低。

（五）布局問(wèn)題

各種作物在不同土壤上單位面積產(chǎn)量不一樣，如何合理安排各種作物在各種土壤上的種

植面積，達(dá)到因地制宜，在完成種植計(jì)劃的前提下，使總產(chǎn)量最多。這是作物布局問(wèn)題。將

某幾個(gè)地方出產(chǎn)的原料，集中到某幾個(gè)地方加工成成品，然后再運(yùn)到某幾個(gè)成品需要地。有

些地方可能既是原料出產(chǎn)地，又是產(chǎn)品需要地，也是成品加工地。因各地間運(yùn)費(fèi)不同，成品

加工費(fèi)不同，設(shè)廠條件不同，應(yīng)在什么地方設(shè)廠，規(guī)模多大，才能滿足成品需要他的需要,

又使費(fèi)用（包括運(yùn)費(fèi)、加工費(fèi)）最低。這是工廠布局問(wèn)題。

（六）分派問(wèn)題

〃件工作分派給“人去做，每人做一件工作，而各人對(duì)做各種工作的效率不同，問(wèn)應(yīng)如

何合理分派，才能使完成全部工作的總工時(shí)最少。類似的問(wèn)題還有作物的種植安排、機(jī)床加

工零件任務(wù)的分配問(wèn)題等。

數(shù)學(xué)模型是描述實(shí)際問(wèn)題共性的抽象的數(shù)學(xué)形式。對(duì)數(shù)學(xué)模型的研究，有助于我們認(rèn)識(shí)

這類問(wèn)題的性質(zhì)和尋求它的一般解法?，F(xiàn)在首先介紹幾個(gè)典型的實(shí)際問(wèn)題。

（—）運(yùn)輸問(wèn)題

例1設(shè)有兩個(gè)磚廠4，42,其產(chǎn)量分別為23萬(wàn)塊和27萬(wàn)塊，生產(chǎn)的磚全部銷往

B、，%,劣三個(gè)工地。其需要量分別為17萬(wàn)塊、18萬(wàn)塊和15萬(wàn)塊。自各產(chǎn)地到各銷地的

運(yùn)價(jià)如表1?1。問(wèn)應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最低？

表1?1

自產(chǎn)地到銷地的運(yùn)價(jià)產(chǎn)量

銷地（工地）

BiB2B3（萬(wàn)塊）

450607023

:磚

3C46011016027

銷量（萬(wàn)塊）171815

解設(shè)刖表示由磚廠4運(yùn)往工地與磚的數(shù)量（單位：萬(wàn)塊）（占1,2;01,2,3）,

例如Mi表示由磚廠4運(yùn)往工地?zé)o磚的數(shù)量等等?，F(xiàn)列表如下（見(jiàn)表1?2）

表1?2

工地

Aft產(chǎn)量

磚

4XuXL2XL323

4X21X22X2327

銷量17181550

磚廠A,運(yùn)往工地B出,生磚的數(shù)量之和等于A,的產(chǎn)量；工地Bj接收磚廠少,為磚的

數(shù)量之和等于嗎的需求量。于是有

x]]+xl2+M3=23

X2]+程+工23=27

xn+x21=17

約束條件5

xl2+x22=18

X13+X23=15

^>0(/=1,2;j=1,2,3)

顯然，可行的調(diào)運(yùn)方案很多，我們的目的是尋找運(yùn)費(fèi)最低的調(diào)運(yùn)方案，即求一組變量

X」，七2,為3，/1，工22，工23的值，使其滿足約束條件，并使運(yùn)價(jià)函數(shù)

工］3工21々2+

s=50x,1+60X12+70+60+11°160x23

達(dá)到最小。

一般地，設(shè)某種物資有個(gè)產(chǎn)地;聯(lián)合供應(yīng)〃個(gè)銷地瓦

m4.AT..........Am,B2.........

各產(chǎn)地產(chǎn)量（單位：噸｝各銷地銷量（單位：噸人各產(chǎn)地至各銷地單位運(yùn)價(jià)（單位：

Bno

元/噸）如表1?3所示。問(wèn)應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最少？

表1?3

銷地產(chǎn)量

Bi

B2???

產(chǎn)地（噸）

Ai0102???Clnai

4CziCn???C2n土

*?

??????

AmCm2???Cmn3m

銷量（噸）thbibn

表中：a,表示產(chǎn)地4的產(chǎn)量（/=1,2,…，m）;

力表示銷地易的銷量（戶1,2，…，〃）；

0表示40間的單位運(yùn)價(jià)（元/噸）（力1,2，…，m;>1,2，…，n\

解假定產(chǎn)銷平衡（即￡生=I設(shè)沏表示由產(chǎn)地4運(yùn)往銷地給的物資數(shù)

/=1；=1

（/=1,2，…，m;7=1,2，…，n\那么上述運(yùn)輸問(wèn)題的數(shù)學(xué)模型為：

求一組變量沏（，，，，〃）的值，使它滿足約束條件

/=1,2…m;y=lf2…

%］十七2十???十

Xm\+Xm2+，"+Xmn=4

X\\+X2\+"，+Xm\=b\

王“+工2〃+..?+/“=2

x..>0(z=l,2---,/7?；y=1,2,??.,/?)

并使目標(biāo)函數(shù)ACllXll+Q2XL2+???+CmnXmn的值最小。

利用連加號(hào)（工），上述模型可以寫為：求一組變量刖值，使?jié)M足約束條件

^=%(i=1,2,…,ni)

j=i

（產(chǎn)地A發(fā)到各銷地的發(fā)量總和等于a的產(chǎn)量）

=bj(j=L2,…，")

（各產(chǎn)地發(fā)到銷地嗎的發(fā)量總和等于約的銷量）

（調(diào)運(yùn)量不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)s=ZZ3的值最?。傔\(yùn)費(fèi)最少\

如果沒(méi)有產(chǎn)銷平衡這一限制，當(dāng)產(chǎn)大于銷時(shí)（即），這一問(wèn)題的數(shù)學(xué)模型應(yīng)

為：求一組變量^（/=1,2，…，m：#1,2，…，"）的值，使它滿足約束條件

Z%<4（i=l,2,…,機(jī)）

j=i

（產(chǎn)地4發(fā)到各銷地的發(fā)量總和不超過(guò)4的產(chǎn)量）

i=i

（各產(chǎn)地發(fā)到銷地約?的發(fā)量總和等于約.的銷量）

Xjj>0（7=12?見(jiàn)J=1,2,…,n）

.（調(diào)運(yùn)量不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)s=ZZC/ij的值最?。傔\(yùn)費(fèi)最少1

7=1;=1

（二）布局問(wèn)題

1.作物布局

某生產(chǎn)隊(duì)要在〃塊地?zé)o，員,…，8〃上，種植m種作物4,4，…，Amo各塊土地畝

數(shù)、各種作物計(jì)劃播種面積及各種作物在各塊地上的凈產(chǎn)值（單位：元）如表1-4所示，問(wèn)

mn

應(yīng)如何合理安排種植計(jì)劃，才能使總產(chǎn)量最多（這里假定即￡卬=22，即計(jì)劃播種總面積

i=i/=1

等于土地面積\

表1?4

±ffi

ftB2???Bn播種面積

作物

ACnC12???Cln31

A2C21C22???C2n32

??

:::

CmlCm2???Cmn3m

土地畝數(shù)bibi???bn

表中：司表示作物4的播種面積（/=1,2,…，6）;

切表示土地學(xué)的畝數(shù)（戶1,2，…，〃）；

q表示在土地學(xué)上種植作物4的凈產(chǎn)值（『=1,2，…，m;j=1.2，…，n\

解設(shè)物為土地與種植作物4的畝數(shù)（k1,2，…，m;>1,2，…，〃），那么作

物布局問(wèn)題的數(shù)學(xué)模型為：

求一組變量的（上1,2，…，m;7=1,2,的值，使它滿足約束條件

〃

Zxij~ai（!=1,2,…,m）

;=i

（在各地塊上種植作物4的總畝數(shù)等于4的計(jì)劃播種數(shù)）

,濁（八1,2,…，幾）

；=|

（在土地及上種J植各種作物的總畝數(shù)等J于鳥(niǎo)的面積）

/NO（i=1,2…，加;j=1,2,???,〃）

（種植數(shù)不能為負(fù)數(shù)）

〃

并且使目標(biāo)函數(shù)s=z￡%%的值最大（凈產(chǎn)值最大\

>1；=i

這一數(shù)學(xué)模型和前面運(yùn)輸問(wèn)題的數(shù)學(xué)模型相同，具有這樣數(shù)學(xué)模型的問(wèn)題還有機(jī)床加工

零件的問(wèn)題（見(jiàn)習(xí)題一第2題）等。我們稱這類問(wèn)題為康■希問(wèn)題，或統(tǒng)稱為運(yùn)輸問(wèn)題。

2.工廠布局問(wèn)題

設(shè)有〃個(gè)地區(qū)4,4，…，An,在某一介計(jì)劃期內(nèi)，4生產(chǎn)某種原料4噸,同時(shí)需要

用這種原料加工的某種產(chǎn)品切噸（乃1,2，…，〃，已知〃噸原料可制造1噸該產(chǎn)品。設(shè)

這"個(gè)地區(qū)所產(chǎn)原料的總數(shù)恰好能生產(chǎn)各地區(qū)所需該產(chǎn)品的總數(shù)，即￡%=應(yīng)"。另外

i=i/=i

已知在4設(shè)廠加工該產(chǎn)品的加工費(fèi)為每噸&元。在4設(shè)廠生產(chǎn)該產(chǎn)品的數(shù)量最多為e,噸，

最少為方噸（RI,2，…，辦從4運(yùn)原料或產(chǎn)品到Aj<ig,2,每噸為?元，

問(wèn)應(yīng)在何地設(shè)廠、生產(chǎn)多少該產(chǎn)品，才能既滿足需要，又使生產(chǎn)費(fèi)用（包括原料和產(chǎn)品運(yùn)費(fèi)、

產(chǎn)品加工費(fèi)）最少？

解設(shè)物表示由4運(yùn)到為的原料數(shù)（單位：噸）（/J=1,2，…，〃），其中0/時(shí)，

表示4留用數(shù)；%表示由4運(yùn)到4的成品數(shù)（單位：噸）"八1,2，…，n）,其中六/

時(shí)，表示4留用數(shù)；Z表示4設(shè)廠的年產(chǎn)成品數(shù)（單位：噸）（/=1,2，…，它們之間

的關(guān)系如表1?5所示。

表1-5

生產(chǎn)加

生產(chǎn)成品

Ai42???An原料I

數(shù)

數(shù)費(fèi)

MlX12Xm

4C11C12???Clnaidi

力1加y^n

X21X22X2n

A2C21C22???Clnaich.

sei

加yzi/2n

:

:::::::????:?

XnlXn2Xnn

fn&Zn

AnCnlCn2???Cnn3ndn

“n

ymYn2Ynn

需成th.bi???bn

品數(shù)

需原

kzikzz???kzn

料數(shù)

根據(jù)題意，得數(shù)學(xué)模型如下:

求一組變量用冰ygij=l,2，…，〃）的值，使它滿足約束條件

〃

WX=4（i=l,2,???,〃）

j=i

（從4運(yùn)往各地原料總數(shù)以及4的留用數(shù)等于A的原料產(chǎn)量）

Z為j=峪（/=1,2,…

i=\

（從各地運(yùn)往A的原料總數(shù)以及4的留用數(shù)等于在4設(shè)廠所需原料數(shù)）

〃

2方=Zj（，=12?..,〃）

j=i

,（由4運(yùn)往各地的成品總數(shù)以及a的留用數(shù)等于a的產(chǎn)品數(shù)）

=bj（j=l,2,…

1=1

（從各地運(yùn)到4的成品數(shù)以及A的留用數(shù)等于4所需成品數(shù)）

/.<zz<<?.（/=1,2--,/?）

（在4生產(chǎn)的成品數(shù)必須在/；至令之間）

%之o,y..>0,Zj>0

（調(diào)運(yùn)原料數(shù)，調(diào)運(yùn)成品數(shù)，生產(chǎn)成品數(shù)都不能為負(fù)數(shù)）

y.

并且使目標(biāo)函數(shù)$=汽*川+力）+￡>'的值最?。ㄉa(chǎn)總費(fèi)用最少\

/=1J=1/=1

（三）分派問(wèn)題

設(shè)有〃件工作員，民，…，4分派給〃人4,4，…，4去做，每人只做一件工

作，且每件工作只分派一個(gè)去做。設(shè)4完成功的工時(shí)為以3片1,2，…,〃）。問(wèn)應(yīng)如何分派

才使完成全部工作的總工時(shí)最少。

解設(shè)沏為學(xué)分派給4的情況：與分派給4時(shí)x產(chǎn)1;不分派給4時(shí)人尸0（Z戶

，）那末這一問(wèn)題的數(shù)學(xué)模型為：求一組變量殉（，，）的值，使它滿足

1,2…,ne0=1,2…"

約束條件

=1（y=l,2,???,/?）

*=1

（每件工作只分派一人去做）

宜%=10=1,2,...,71）

<j=i

（每人只做一件工作）

%=0或1（/,j=1,2,???,?）

（每人對(duì)每件工作只有做與不做兩種情況）

并且使目標(biāo)函數(shù)s='汽%”的值最小。

i=ij=\

分派問(wèn)題是運(yùn)輸問(wèn)題的特例。因?yàn)樽兞侩局蝗　：?,所以又稱它為0」規(guī)劃問(wèn)題。

（四）生產(chǎn)組織與計(jì)劃問(wèn)題

（1）設(shè)某車間用機(jī)床4,4,…，4n生產(chǎn)由ft,Bl，…，Bn這〃個(gè)不同零件構(gòu)成

的機(jī)器。如果每架機(jī)器需要各種零件的數(shù)目成比例九：無(wú)：…：/〃；機(jī)床4生產(chǎn)零件場(chǎng)的效

率（每日生產(chǎn)零件數(shù)）為問(wèn)應(yīng)如何分配機(jī)床負(fù)荷，才使生產(chǎn)的機(jī)器最多。

解設(shè)物為機(jī)床4生產(chǎn)零件馬的時(shí)間（單位：日）（/=1,2，…,nrt片1,2，…,n\這一

問(wèn)題的數(shù)學(xué)模型為：

=l（z=l,2,---,m）

j=i

（機(jī)床4生產(chǎn)各種零件時(shí)間總和應(yīng)等1）

?%：…：2%￡〃=4:4：…:4

1=11=1<=1

約束條件mm

2C"Xi\X@七2

i=l

即r=-^-------=5

4

（各機(jī)床一天生產(chǎn)各種零件總數(shù)，應(yīng)成已定比例）

Xu>0（i=1,2,…,〃2"=12…〃）

（生產(chǎn)零件時(shí)間不能為負(fù)數(shù)）

〃7

并且使目標(biāo)函數(shù)S=上匕一（零件"的數(shù)量）的值最大。

4

特別地，當(dāng)九：無(wú)：…：^=1：1：...：1（即每架機(jī)器需要各種零件數(shù)目相同）時(shí)，它

的數(shù)學(xué)模型為：

求一組變量沏（/=L2，…,/n;y=l,2，…，力的值，使它滿足約束條件

〃

X4=l(/=l,2,m)

j=i

"l

〃

Z?！埃盋i2Xi2>3

<=1__________/=l________i=1

4_4.T

Xq30"=1,2,???,孫/=1,2,???,〃)

并且使目標(biāo)函數(shù)，=2的因的值最大。

/=i

（2）設(shè)用m種原料4,4,…，Am,可以生產(chǎn)"種產(chǎn)品",民，…品現(xiàn)有原料

數(shù)、每單位產(chǎn)品所需原料數(shù)，及每單位產(chǎn)品可得利潤(rùn)數(shù)如表1?6所示。

問(wèn)應(yīng)如何組織生產(chǎn)才能使利潤(rùn)最大？

表16

單位7t

立a

nano

所需BiBi…Bn現(xiàn)有原料

原料

原料

AiC1102…Clnai

AiC21C22???C2n32

???????

AmCmlCm2…Cmn3m

單位產(chǎn)品可得利潤(rùn)bibi…bn

解設(shè)巧為生產(chǎn)產(chǎn)品與（戶L2，…，〃）的計(jì)劃數(shù)，這一問(wèn)題的數(shù)學(xué)模型為：

求一組變量為（六1,2，…,"）的值，使它滿足約束條件

=1

7=1

（只考慮單位成品）

,^C..xy.<a.（z=l,2,---,m）

j=i

（生產(chǎn)各種產(chǎn)品所需原料a的總數(shù)不能超過(guò)a現(xiàn)有數(shù)《）

Xj>0（j=l,2,---,n）

、（各種產(chǎn)品II劃生產(chǎn)數(shù)不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)$=力百的值最大（總利潤(rùn)最多X

j=i

（3）某工廠用機(jī)床,<2,???4n加工零件...Bno在一個(gè)生產(chǎn)周期，各機(jī)

床只能工作的機(jī)時(shí)、工廠必須完成各零件加工數(shù)、各機(jī)床加工每個(gè)零件的時(shí)間（單位：機(jī)

時(shí)/個(gè)）和加工每個(gè)零件的成本（單位：元/個(gè)）如表1?7和表1?8所示。問(wèn)在這個(gè)生產(chǎn)周

期，怎樣安排各機(jī)床的生產(chǎn)任務(wù)，才能既完成加工任務(wù)，又使總的加工成本最低。

表上7

加工

在一周期能工

零件

Bi民...Bn

作的機(jī)時(shí)

時(shí)間

機(jī)床

41QlC12...Clnai

4C21Cn...C2nai

????????

AmCmlCm2…Cmn3m

必須加工零件數(shù)

bi6...bn

表1?8

加工

BI82???Bn

成本

機(jī)床

4dudi2???Oin

dii…din

A2chi

-?::

Amdmldm2…dmn

解設(shè)均為機(jī)床4在一生產(chǎn)周期加工零件學(xué)的個(gè)數(shù)（/=1,2，…，m;j=l,2，…，

n\這一問(wèn)題的數(shù)學(xué)模型為：

求一組變量叼（k1,2，…，m;六1,2，…,加的值，使它滿足約束條件

Wq（i=l,2,…,〃2）

>1

（機(jī)床a加工各零件總機(jī)時(shí)不能超過(guò)a能工作機(jī)時(shí)）

,Z%2乙。=12…

/=i

（各機(jī)床加工零件約的總數(shù)不能少于約需要數(shù)）

.20,整數(shù)（i=1,2,…，m;/=1,2,???,〃）

（加工零件個(gè)數(shù)不能為負(fù)數(shù)、分?jǐn)?shù)）

〃m

并且使目標(biāo)函數(shù)s=的值最?。庸た偝杀咀钌賆

j=\1=1

（五）合理下料問(wèn)題

設(shè)用某原材料（條材或板材）下零件毛坯A,A,Am。根據(jù)過(guò)去經(jīng)驗(yàn)在一件原料

上有品，民，…品種不同的下料方式，每種下料方式可得各種毛坯個(gè)數(shù)及每種零件需要量

如表1?9所示。問(wèn)應(yīng)怎樣安排下料方式，使得既能滿足需要，用的原材料又最少。

表”9

并且使目標(biāo)函數(shù)s=￡勺的值最?。ㄋ迷牧狭可?

7=1

（六）配料問(wèn)題

設(shè)用〃種原料a,民，…&制成具有m種成分4,42,…4n的產(chǎn)品，其所含各成

分需要量分別不低于31,a2，…，癡各種原料的單價(jià)、各種原料所含成分的數(shù)量如表1?10

所示。問(wèn)應(yīng)如何配料，才使產(chǎn)品成本最低。

表1-10

一單位原原

產(chǎn)品所含

Bz...Bn

成分需要量

數(shù)量

原料所含成分名稱

4QiCl2...Cinai

A2C21C22...C2n力

????

AmCmlCm2…Cmn3m

單價(jià)bibi...bn

解設(shè)需原料均為巧單位（戶1,2，…,這一問(wèn)題的數(shù)學(xué)模型為：

求一組變量?jī)?nèi)（六1,2，…,"）的值，使它滿足

〃

ZCjjXj>%（i=1,2,…,〃2）

六1

<（所有各種原料所含成分4的總數(shù)應(yīng)不少于產(chǎn)品對(duì)4需要量q）

>（）（7=1,2,???,??）

.（所取原料不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)S=fbjXj的值最?。óa(chǎn)品成本最低\

7=1

線性規(guī)劃問(wèn)題數(shù)學(xué)模型的一般形式，是求一組變量芭，/，…,X”，使其滿足：

（或=伉，或之仇）

%]再十的2七十…十《白

aX

。2內(nèi)+。2212+…+2nn?%（或=%,或2/??）

約束條件............................................

aXaX

4滔+ml2+…+mnn（一（或=%或>一）

Xj>0（，=1,2,…/）

并使目標(biāo)函數(shù)S=。內(nèi)+c2xz+…+ctlxn達(dá)到最小（或最大X

為討論和計(jì)算方便，作如下規(guī)定：

1.如果約束條件中第攵個(gè)式子為4內(nèi)+以2々+…+。3〃<4，則人為地添加變量

七.>o,使之成為巴西+ak2x2+…+aknxn+=bko

如果約束條件中第一個(gè)式子為ar}x^ar2x2+-^arnxn>br，則人為地添加變量

%>o,使之成為限+a,+…+”+「二b，。

通過(guò)這種方法，使所有的約束條件都變成等式。稱/+妙x〃+,為松弛變量。

2.如果問(wèn)題是使目標(biāo)函數(shù)s=c內(nèi)+Q/+…+?！?達(dá)到最大，則化為使目標(biāo)函數(shù)

s'=-s=-cixi-c2x2-------cnxn達(dá)到最小。

3.如果某變量當(dāng)沒(méi)有非負(fù)限制，則引進(jìn)變量K>0,X；20,令與二K一/；，代入約

束條件和目標(biāo)函數(shù)中，化為對(duì)全部變量都有非負(fù)限制。

這樣，可以把線性規(guī)劃問(wèn)題寫成如下標(biāo)準(zhǔn)形式：

mins=GF+c?x?+???+ctlxn

+%2%+…+Q3〃=b\

d2lx]+a22x2^-^a2nxn=b2（1）

?！╠++…+《"〃=篇

Xj>0（j=1,2,???,?）

4a\2飛一%

a???a

a2T222nb2工2%

記A=b=?fX=*，?

??■Pj=

?????????????*

a,n2???A._x〃__amj_

C=（卬。2,…，％），則可將標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題（1）簡(jiǎn)記為

mins-ex

Ax=b(2)

<x>0

向量P1（\<j<n）為矩陣A的第j個(gè)列向量，稱為變量與對(duì)應(yīng)的系數(shù)列向量。

二,幾個(gè)基本概念

對(duì)于給定的實(shí)際問(wèn)題，首先是要建立線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（1）,其次是求問(wèn)題的最

優(yōu)解。我們不主張進(jìn)行手工求解的大量訓(xùn)練，僅要求大家理解單純形方法的基本思想，具體

計(jì)算通過(guò)計(jì)算機(jī)來(lái)實(shí)現(xiàn)。這里，先給出如下幾介基本概念。

1.如果d=（d4…琮）'滿足約束條件，即有Ar°=Ad2。，則稱/為可行

解。

2.如果可行解（向量）=0,或/的非零分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)，則稱

為基礎(chǔ)可行解。

3.使目標(biāo)函數(shù)取最小值的可行解稱為最優(yōu)解。

4.使目標(biāo)函數(shù)取最小值的基礎(chǔ)可行解稱為基礎(chǔ)最優(yōu)解。

習(xí)題一

寫出下列問(wèn)題的數(shù)學(xué)形式：

1.有兩個(gè)煤廠48,每月分別進(jìn)煤60噸、100噸。它們擔(dān)負(fù)供應(yīng)三個(gè)居民區(qū)用煤任

務(wù)。這三個(gè)居民區(qū)每月需用煤分別為45噸、75噸、40噸。2廠離這三居民區(qū)分別為1。公

里、5公里、6公里，8廠離這三居民區(qū)分別為4公里、8公里、15公里。問(wèn)這兩煤廠如何

分配供煤，才使運(yùn)輸量最小。

2,用機(jī)床4,4,4加工零件"和民分別為50個(gè)和70個(gè)；各機(jī)床必須加工出零

件數(shù)：4為40個(gè)，4為35個(gè)，4為45個(gè)；各種機(jī)床加工各種零件加工費(fèi)（單位:元/

個(gè)）如表1?11所示。問(wèn)如何分配這三臺(tái)機(jī)床加工這兩種零件的任務(wù)，才使總加工費(fèi)最少。

表1-11

3?設(shè)有某種原料產(chǎn)地41,42,力3,把這種原料經(jīng)過(guò)加工，制成成品，再運(yùn)往銷地。假

設(shè)用4噸原料可制成1噸成品。產(chǎn)地21年產(chǎn)原料30萬(wàn)噸，同時(shí)需要成品7萬(wàn)噸。產(chǎn)地力2

年產(chǎn)原料26萬(wàn)噸，同時(shí)需要成品13萬(wàn)噸。產(chǎn)地4年產(chǎn)原料24萬(wàn)噸，不需成品。4與力2

間距離150公里，4與4間距離100公里，4與4間距離200公里。又知原料運(yùn)費(fèi)為

0.3萬(wàn)元/萬(wàn)噸公里，成品運(yùn)費(fèi)為0.25萬(wàn)元/萬(wàn)噸公里。且知在21開(kāi)設(shè)加工廠加工費(fèi)為0.55

萬(wàn)元/萬(wàn)噸，在4為0?4萬(wàn)元萬(wàn)噸，在4為0?3萬(wàn)元/萬(wàn)噸。因條件限制，在4設(shè)廠規(guī)模

不能超過(guò)年產(chǎn)成品5萬(wàn)噸，4和4可以不限制。問(wèn)應(yīng)在何地設(shè)廠，生產(chǎn)多少成品，才能使

生產(chǎn)費(fèi)用（包括原料運(yùn)費(fèi)、成品運(yùn)費(fèi)、加工費(fèi)等）最小。

4.某木器廠生產(chǎn)圓桌和衣柜兩種產(chǎn)品。現(xiàn)有兩種材料，第一種有72立方米，第二種有56

立方米。假設(shè)生產(chǎn)每種產(chǎn)品都需要用兩種木料。生產(chǎn)一個(gè)圓桌和一個(gè)衣柜所需木料如表1-12

所示。每生產(chǎn)一個(gè)圓桌可獲得潤(rùn)6元；生產(chǎn)一個(gè)衣柜可獲利潤(rùn)10元。木器廠在現(xiàn)有木料條

件下，圓桌和衣柜應(yīng)各生產(chǎn)多少，才使獲得利潤(rùn)最多。

表12

木料（單位：立方米）

產(chǎn)品

第一種第二種

圓桌0.180.08

衣柜0.090.28

5.現(xiàn)有三種機(jī)床，生產(chǎn)某種產(chǎn)品的兩種零件。產(chǎn)品需要這兩種零件的數(shù)目相同。各機(jī)床

生產(chǎn)兩種零件的日產(chǎn)量如表113所示。問(wèn)應(yīng)如何組織生產(chǎn)，使總產(chǎn)量最大。

6.某班有男同學(xué)30人，女同學(xué)20人，星期天準(zhǔn)備去植樹(shù)。根據(jù)經(jīng)驗(yàn)，一天男同學(xué)平

均每人挖坑20個(gè)，或栽樹(shù)30棵，或給25棵樹(shù)澆水，女同學(xué)平均每人挖坑10個(gè)，或栽樹(shù)

20棵，或給15棵樹(shù)澆水。間應(yīng)怎樣安排才能使植樹(shù)（包括挖坑、栽樹(shù)、澆水）最多。

7.某鋼廠兩介煉鋼爐同時(shí)各用一種方法煉鋼。第一種煉法每爐用a小時(shí)；第二種用b

小時(shí)（包括清爐時(shí)間\假定這兩種煉法每爐出鋼都是々公斤，而煉1公斤鋼的平均燃料費(fèi)

第一法為S元，第二法為“元。若要求在C小時(shí)內(nèi)煉鋼公斤數(shù)不少于d,問(wèn)應(yīng)怎樣分配兩

種煉法的任務(wù)，才使燃料費(fèi)用最少。

8.用長(zhǎng)度為500厘米的條材，截成長(zhǎng)度分別為98厘米和78厘米兩種毛坯。要求共截

出長(zhǎng)98厘米的毛坯10000根，78厘米的20000根。問(wèn)怎樣截法，才使所用的原材料最

少。

9.某養(yǎng)雞場(chǎng)有1萬(wàn)只雞，用動(dòng)物飼料和谷類飼料混合喂養(yǎng)。每天每只雞平均吃混合飼

料0.5公斤。其中動(dòng)物飼料占的比例不得少于1/5.動(dòng)物飼料每公斤0.9元；谷類飼料每公

斤0.28元。飼料公司每周只保證供應(yīng)谷類飼料50000公斤。問(wèn)飼料應(yīng)怎樣混合，才使成本

最低。

10.某商店制訂某產(chǎn)品7—12月進(jìn)貨售貨計(jì)劃。己知商店倉(cāng)庫(kù)容量不得超過(guò)500件，

6月底已存貨200件，以后每月初進(jìn)貨一次。假設(shè)各月份某商品買進(jìn)、售出單價(jià)如表1?14

所示。問(wèn)各月進(jìn)貨售貨各多少，才能使總收入最多？

表1-14

月789101112

買進(jìn)（元/

282425272323

件）

售出（元/

292426282225

件）

11.設(shè)有〃種飼料，各含m種營(yíng)養(yǎng)成分。每只雞每天需要各營(yíng)養(yǎng)成分的數(shù)量、各種飼

料的單價(jià)，以及各種飼料所含營(yíng)養(yǎng)成分如表1口5所示。問(wèn)應(yīng)如何配合飼料，才能既滿足雞

的營(yíng)養(yǎng)需要，又使成本又最低。

表1-15

飼料所含、、

料BiBi???Bn營(yíng)需要■

營(yíng)養(yǎng)成分

4CL102???Cln出

???

A2C21C22C2n32

??

?????:

AmCmlCm2???Cmn3m

bibi

飼料單價(jià)???bn

12.在〃塊土地上種植n種作物。每塊土地只種一種作物且每種作物只在一塊土地上

種植。其數(shù)據(jù)如表1?16所示。問(wèn)應(yīng)如何制訂種植計(jì)劃，才使總產(chǎn)值最多。

表1-16

每塊土地種虐、

百神作物的不值、「土典

ft???

B2Bn

怖

4CllC12???Cln

A2C21C22???Cln

??:???:

AnCnlCn2???Cmn

第二章對(duì)偶線性規(guī)劃問(wèn)題

本章要求大家能正確給出線性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃；掌握互為對(duì)偶問(wèn)題的基本性質(zhì)；

充分理解對(duì)偶問(wèn)題的經(jīng)濟(jì)意義——影子價(jià)格。對(duì)偶單純形方法只進(jìn)行一般了解即可，具體

計(jì)算通過(guò)計(jì)算機(jī)實(shí)現(xiàn)。

一、對(duì)偶線性規(guī)劃問(wèn)題及基本性質(zhì)

我們把線性規(guī)劃問(wèn)題

(I)：mins=CjX]+c2x2+…+cnxtl

內(nèi)+a\2X2+???+。歷]〃之仇

。2”|+。22%2+?.?+。2/〃之4

^m\Xx+am2x2+-+anmxn>bm

Xj>0(j=1,2,???,/?)

與線性規(guī)劃問(wèn)題

b

(H)：maxg=4%+8必+…+mym

?！氨?。21乂+3+?！ā岸?〃46

a[2y^a22y2+--+ain2ym<c2

+32+,-+。。

V>0(i=1,2,…,m)

J

稱作互為對(duì)偶的線性規(guī)劃問(wèn)題。可將其中任意一個(gè)稱為原問(wèn)題，另一個(gè)稱為它的對(duì)偶問(wèn)題。

記y=(必，為，…,4J，則可將上述對(duì)偶規(guī)劃問(wèn)題寫成如下矩陣形式：

（I）：mins=ex

Ax>b（3）

,x>0

（II）：max^=yb

yA<c（4）

y>0

互為對(duì)偶的線性規(guī)劃問(wèn)題具有下列性質(zhì)。

定理1如果線性規(guī)劃問(wèn)題（I）的第k個(gè)約束條件是等式，那么它的對(duì)偶規(guī)劃（口）中的

第％個(gè)變量為用E負(fù)限制。反之亦然，即若線性規(guī)劃問(wèn)題（口）的第/個(gè)約束條件是等式，那

么它的對(duì)偶規(guī)劃（I）中的第/個(gè)變量占無(wú)非負(fù)限制。

證明略。

如果線性規(guī)劃問(wèn)題（I）的第k個(gè)約束方程為

則可將其改寫成

~Clk\X\~ak2X2-----aknXn2一仇

如果線性規(guī)劃問(wèn)題（I）的第k個(gè)約束方程為

4丙+%2工2+…+%占=4

則其對(duì)偶規(guī)劃（口）中的第k個(gè)變量為無(wú)非負(fù)限制。因此，無(wú)論線性規(guī)劃問(wèn)題（I）中的約束條

件如何，總能順利得到其對(duì)偶規(guī)劃問(wèn)題（口）。

由于inins=niax（-3）,inaxg=min（—g），而且約束與"N"約束可通過(guò)

方程兩邊同乘以口進(jìn)行轉(zhuǎn)換，理論上講，同一線性規(guī)劃問(wèn)題既可看成是問(wèn)題（I）,也可看成

是問(wèn)題（口）。

例1求線性規(guī)劃

mins——2x,+3x2+x3

2X]-4X2+>5

-3X1+7X-5X=8

V23

5x,-6X2+9X3<7

工2，工32。；王無(wú)非負(fù)限制

的對(duì)偶規(guī)劃。

解(1)保持目標(biāo)函數(shù)極小化不變，視為與規(guī)劃問(wèn)題(I)同類型。將“W"約束變成

約束，得到

mins=-2X[+3x2+

2xt-4X2+x3>5