2.1用圖解法求解下列線性規劃問題，并指出各問題具有唯一最優解、無窮多最優解、無界

解還是無可行解。

maxz=2x,+x2

4內+3當<12

(1)2x+x<8

s.t.t2

4.%-x2<8

xpx2>0

4X1+3X2=12

所以：maxz=2x—+1=一

42

所以有唯一解

max=3x1+lx2

-XI+2X2<4

⑵311+2X2<14

xt-x2<4

為,看20

解:

X2

5

------>Xt——

(-x.+2x,=4

八?2解得：2

3XI+2X=1413

2x^=—

一4

513

所以:maxz=3x—+2x一=14

24

因為直線3再+2X2=0與直線3$+2々=14平行,

所以有無窮多最優解，maxz=14

maxz=2AJ+3x2

X-X<2

(3)12

-3X1+x2<4

X),x2>0

解：

maxz=Xj+x2

X]-x>0

(4)2

3*-x2<-3

xpx2>0

解:

2.2將卜列線性規劃問題化為標準形式

minz=32+2x2-x3

minz=2xt-2x2+3x3

2x)-X32一3

一X]+%+5=4

(1)s.t.(2)^1+x3<1

-2x)+x2-<6s.t.

-2Xf+3X2-x3=-2

X1<0,x2>0,與無約束

X120,々無約束，右?0

解：(1)令X]——X]—O巧=13‘一"3''("3'，兀3''20)

則上述形式可化為:

M

maxz=2x('+2x2-3(x3'-x3)

M—2+(X3'_彳3'')=4

,,

2xt'+x2-(x3'-x3)+x4=6

，，，，

X,,X2,X3,X3,X4>0

minz=3X]+2x2-x3

24一匕之—3

(2)x1+<1

-2玉+3X2-x3=-2

xx>0,工2無約束，/VO

解：令尤；二一心0)

則上述形式可化為:

,M1

maxz=-3再-2(x2-x2)-x3

—2(/3")—'+"4=3

(X,'_X-,")—/'+%5=]

2xt-3(x2-x2")-A3*=2

,,,

XI,X2,X2,X3',X4,A5>0

2.3.在下列線性規劃問題中，找出所有基解，指出哪些是基可行解并分別代入目標函數,

比較找出最優解。

maxz=3]+5x2

X1+刀3=4

(1)2X2+匕=12

3%1+2X2+X5=18

xy>0(7=1,2,34)

10500

CBXBXiX2X3X4b0

0x3341093

0X4[5J20188/5

10500

0Xa0[14/5]1/3-1/521/53/2

10Xi12/501/58/54

010-216

5x2015/14-3/143/2

10Xi10-1/72/71

00-5/14-25/1435/2

所以，最優解目標函數值為maxz=35/2

3

戶=(《,(),0)r/

(2)

maxz=1OOX1+2OOx2

x1+x2<500

x,<200

2—+6X2<1200

xpx2>0

解：化為線性標準形式有:

maxz=1OOX]+200x2

*

X]+工2+X3--500

%1+x4=20C)

2M+6X2+x5=1200

jrpx2,x3,x4,x5>0

100200000

b

CBXBX1x2x3X4x5e

0X311100500500

+

0X410010200

0001200200

x52[5]1

100200000

0X32/3010-1/6300450

0X4[1]0010200200

2001/3001/6200600

x21

100/3000-100/340000

0X3001-2/3-1/6500/3

100X110010200

200010-1/31/6400/3

x2

0000-100/3140000/

3

山…口小口站心以140000丈CM40°5()0八八、

所以，最優目標函數值為maxz=---------x*=(200,-----,-----,0,0)

333

2.5.分別用大M法和兩階段法求解下列線性規劃問題，并指事問題的解屬于哪一類:

maxz=3x)+2x2

xi+2X2<7

(I)%1—X2>1

x,+x2>2

xl9x2>0

解：化為標準形式：

maxz=3內+2x2-Mx6-Mx7

X1+2X2+工3=7

X]-X2-X4+X6=}

X1+x2-x5+x7=2

XpX2,X3,X4,X5,X6,X7>0

32000-M-M

b

CBXBX.x2X3x4x5x6x7

0200007

x311

-MX6[1J-10-10101

-Mx71100-1012

3+2M20-M00

003006

X311-1

3X11-10-10101

-MX70[2]01-1-111

05+2M03+2M-M-3-2M0

000-1/2[3/2]1/2-39/2

X31

3X1100-1/2-1/21/21/23/2

2x20101/2-1/2-1/21/21/2

0001/2-M5/2-1/2-M-5/2-M

0X5002/3-1/311/3-26

3X1101/3-2/302/3-3/21

0

2x2001/3[1/3]-1/3-1/21

0001/2-M5/2-1/2-M-5/2-M

000005

X511-1

3X112100007

0

0X40311-106

0-4-300-M-M21

所以Z*=21x*=(7,0,0,6,5,0,0)

⑵

maxz=2xt-x2-x3

3為+2X2+.>18

2x+x<4

<}2

x]+x2-x3=5

X,占,與20

解：化為標準形式：

minz=%十七

32+2X2+x3-x4+x6=18

2X1+x2+x5=4

X1+x2-x3+=5

xpx2,x3,x4,x5,x6x7>0

0000011

b

CBXBX1x2x3x4X5x6X7

1X6321-101018

0X5[2]1001004

1X711-100015

-4-301000

1X601/21-1-3/21012

0X11[1/2]001/2002

1X701/2-10-1/2013

0-102-20-1

1X6-101-1-21010

0x221001004

1X7-10-10-1012

200130011

因為最優目標函數值=11工0,所以，此線性規劃問題無可行解

(3)

maxz=-xi+x2

4/1+3X2>12

3X]-x2<6

x2>2

xpx2>0

解：

(4)

minz=X]+3x2+4x3+3x4

3x,+6X2+七+2X4>15

,6X]+3X2+2X3+乙>12

解:

2.6線性規劃問題〃如'znCX,AX=b,X20,如X*是該問題的最優解，又'＞（）為某

一常數，分別討論下列情況時最優解的變化：

（2）目標函數變為maxz=】CX：

（3）目標函數變為morz=（C+^）X；

（4）目標函數變為/MXZ=±X,約束條件變為AX=^b。

解：（1）最優解不變，最優值變為人倍。

（2）不確定

（3）最優解變為1倍，最優值不變

2

2.7下表是一個求極大值線性規劃的單純形表，其中心，心，死是松弛變量。

表2.13

Cj22

CBXBX\X2X3X4與X6b

X512-12

2X2-11-21

X\2a-1-a+84

Gj-1

（I）把表中缺少的項目填上適當的數或式子。

（2）要使上表成為最優表，。應滿足什么條件？

（3）何時有無窮多最優解？

（4）何時無最優解？

（5）何時應以右替換內？

解：⑴

000001

b

CBXBX1X2X3X4x5x6

0X600121-12

21-110-21

x20

1Xi102a-10-a+84

004-2a-10a-4

（2）要使表2-14稱謂最優表，a應滿足條件

4-2a<0

s.t.<2WaW4

?-4<0

(3)a=2或a=4

IT-a戶

-a+8<0

（5）

4一。〉0

，2。>（）

—2>一4

112a

2.6線性規劃問題加以z=CX,AX=b,X20,如X*是該問題的最優解，又、>0為某

一常數，分別討論下列情況時最優解的變化：

（1）目標函數變為maxz=4CX：

（2）目標函數變為marz=（C+）X：

（3）目標函數變為，MXZ=￡X,約束條件變為H='b。

解：

2.7下表是一個求極大值線性規劃的單純形表，其中X4,冷，死是松弛變量。

表2.13

22

CBXBX\X2X3X4與X6b

X512-12

2X2-11-21

X\2a-1-a+84

Gj-1

（I）把表中缺少的項目填上適當的數或式子。

（2）要使上表成為最優表，。應滿足什么條件？

（3）何時有無窮多最優解？

（4）何時無最優解？

（5）何時應以右替換內？

解：

2.8戰斗機是一種重要的作戰工具，但要使戰斗機發揮作用必須有足夠的駕駛員。因此

生產出來的戰斗機除一部分直接用于戰斗外，需抽一部分用于培訓駕駛員。已知每年生產的

戰斗機數量為卬。=/「?,〃），又每架戰斗機每年能培訓出k名駕駛員，問應如何分配每年

生產出來的戰斗機，使在〃年內生產出來的戰斗機為空防作出最大貢獻？

解：

2.9.某石油管道公司希望知道，在下圖所示的管道網絡中可以流過的最大流量是多少

及怎樣輸送，弧上數字是容量限制。請建立此問題的線性規劃模型，不必求解。

2.10.一家酒店24小時都需要安排服務員上班，在各時間段中所需要的服務員數量見

表

班次時間所需人數

16:00-10:0060

210:00-14:0070

314:00-18:0060

418:00-22:0050

522:00-2:0020

62:00-6:0030

設服務員分別在各時間區段一開始時上班，并連續工作八小時，問該酒店至少配備多少名服

務員。列出此問題的線性規劃模型。

解：

2.11某班有男生30人，女生20人，周日去植樹。根據經驗，一天男生平均每人挖坑

20個，或栽樹30棵，或給25棵樹澆水；女生平均每人挖坑10個，或栽樹20棵，或給15

棵樹澆水。問應怎樣安排.才能使植樹（包括挖坑、栽樹、澆水）最多？請建立此問題的線

性規劃模型，不必求解。

解：設

男生女生

挖坑XIIXI2

栽樹X21X22

澆水X31X32

共計植樹Z

maxz

Ml+X2\+X3I-30

X[2+X22+X32-20

20xn+10xl2>z

z

“30X2|+20工22-

25%+15X32>z

>0J=1,2,3;/=1,2

2.12某糖果廠用原料A、B、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果

中A、8、C三種原料的含量要求、各種原料的單位成本、各種原料每月的限制用量、三種

牌號糖果的單位加工費及售價如表1所示。問該廠每月生產這三種牌號糖果各多少千克，才

能使該廠獲利最大？試建立這個問題的線性規劃模型。

表2.15

甲乙丙原料成本限制用量

A60%以上15%以上2.002000

B1.502500

C20%以下60%以下50%以下1.001200

加工費0.500.400.30

售價3.402.852.25

解：設

甲乙丙

AXIIX12XI3

BX21X22X23

CX31X32X33

產量X41X42X43

)x)

maxZ=2.9X41+2.45x42+1.95.r43-2(^1+x12+XI3)-1.5(JT21+x22+々3一(工31+?>2+工33

+x}2+x]3<2000

x2]+x22+x23<2500

x++x<

31x32331200

x}l-0.6X4I>0

x]2-0.15X42>0

x31-0.2X41<0

x32-O.6X42-0

x33-O.5X43-0

Ml+X2\+叫一％=0

$2++X32-82=0

為3+工23+%33-工43二°

勺>0,z=l,2,3,4;j=1,2,3

2.13.某商店制定7—12月進貨售貨計劃，已知商店倉庫容量不得超過500件，6月底

已存貨200件，以后每月初進貨一次，假設各月份此商品買進售出單價如下表所示，問各月

進貨售貨各多少，才能使總收入最多？請建立此問題的線性規劃模型，不必求解。

月份78910II12

買進單價282425272323

售出單價292426282225

解:

2.14某農場要購買一批拖拉機以完成每年三季的工作量：春種330公頃，夏管130公頃，秋

收470公頃。可供選擇的拖拉機型號、單臺投資額及工作能力如下表所示。

拖拉機型號單臺投資單臺工作能力（公頃）

（元）春種夏管秋收

東方紅5000301741

豐收4500291443

躍進4400321642

勝利5200311844

問配購哪幾種拖拉機各幾臺，才能完成上述每年工作量且使總投資最小？（建立線性規劃模

型，不需求解）

解

2.15某療養院營養師要為某類病人擬訂本周菜單。可供選擇的蔬菜及其費用和所含營養

成分的數量，以及這類病人每周所需各種養分的最低數量如卜.表所示:

分每份所含養分數量（亳克）每份的費用

蔬菜鐵磷維生素A維生素C煙酸（元）

青豆0.451041580.30.15

胡蘿卜0.4528906530.350.15

花菜1.055()2550530.60.24

卷心菜0.42575270.150.06

甜菜0.5221550.250.18

土豆057523580.80.10

每周養分最低需求量60325175002455.0

另外為了口味的需求，規定一周內所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人

每周需14份蔬菜，問選用每種蔬菜各多少份？（要求建立數學模型，不需求解）

解：

2.16對某廠I,II,III三種產品下一年各季度的合同預訂數如下表所示。

季度

產品1234

I1500100020001200

II1500150012001500

III10002(X)015(X)2500

該三種產品1季度初無庫存，要求在4季度末各庫存150件。已知該廠每季度生產工時

為1500（）小時，生產I、II、HI產品每件分別需時2、4.3小時。因更換工藝裝備，產品I

在2季度無法生產。規定當產品不能按期交貨時，產品I,II每件每遲交一個季度賠償20

元，產品III賠償10元；又生產出來產品不在本季度交貨的，每件每季度的庫存費用為5元。

問：該廠應如何安排生產，使總的賠償加庫存的費用為最小（要求建立數學模型，不需求解）。

解：

2.17某公司有三項工作需分別招收技工和力工來完成。第一項工作可由一個技工單獨

完成，或由一個技工和兩個力工組成的小組來完成,第二項工作可由一個技工或一個力工單

獨去完成。第三項工作可由五個力工組成的小組完成，或由一個技工領著三個力工來完成。

己知技工和力工每周工資分別為100元和80元，他們每周都工作48小時，但他們每人實際

的有效工作小時數分別為42和36。為完成這三項工作任務，該公司需要每周總有效工作小

時數為：第一項工作10000小時。第二項工作20000小時，第三項工作30000小時。又能招

收到的工人數為技工不超過400人，力工不超過800人。試建立數學模型，確定招收技工和

力工各多少人。使總的工資支出為最少（建立數學模型，不需求解）。

解：

3.1寫出下列線性規劃的對偶規劃。

（1）maxz=3xi+2x3—4x4

2X1—X2+%3+%42—3

3x1+2x2-X3+X4<S

x\-X2+2x4-5

x.X\>0,X2<0,X3,X4無約束

解:

mmw=-3y[+Sy2+5y3

2y+3%+為23

_y+2y2-y3Vo

s.t.<y_%=2

3y+%+2y3=-4

yWO,%2。，為無約束

⑵minz=5斗+2x2-3x3

2%1—3%2+—2

%+2X2+3X3=3

s.t.<

3%+3X2+x3<5

玉VO,工2無約束，X3之0

解:

maxw=-2yl+y2+3^3>5

-2y+2%+3%=2

4y+3%+%?-3

j無約束，y3so

3.2判斷下列說法是否正確，并說明原因。

（1）如果線性規劃的原問題存在可行解，其對偶問題也一定存在可行解。

答：不一定。對偶問題可能存在唯一解或無界解。

（2）如果線性規劃的原問題無可行解，則其對偶問題?定存在無界解。

答：錯。其對偶問題可能存在無可行解或無界解。

（3）線性規劃的原問題的任一可行解的函數值一定不大于其對偶問題的任一可行解的函數

值。

答：正確。

（4）任何線性規劃問題存在唯一的對偶問題。

答：正確。

3.3試運用對偶理論證明下面的線性規劃問題存在無界解。

maxz=3玉+2x2+2x3

2x}-3%+4X3<7

s.tA4%j-x2+2X3<5

%,々，七-0

minw=ly1+5%

‘2%+4y2>3

-3yr-2y2>2

s.tA

解:4y+2%22

畫圖可得其對偶函數無可行解。

,?根據推論得，原函數也無可行解。

3.4設有如下線性規劃問題：

maxz=2x1-x2+x3

2xl-x2+3X3<2

3x1+4%+X3>5

x2-x3=2

<O,x2>0,尤3無約束

①寫出其對偶問題；

②利用對偶理論證明原問題目標函數值z一<(

解：①對偶規劃為

minw=2y+5%+2%

2y+3%W2

s.tA一兇+4%+%2—1

3y+%-%=1

y2。,%?0，>3無約束

②以'1為Y軸，,2為x軸建立直角坐標系并畫出出①中對偶規劃所表示的區域,

當=I，,2=U時，此時對偶規劃所表示的區域有最大值點，此時，3-，

Vi—1,—0,Vo=2

即當“2'^3時，對偶規劃取得最大值為6,又

牧

CX<bYy門乂

原問題目標函數值Z<6。

35給出如下線性規劃問題:

maxz

%+3X2+x3<6

s.tA一為+2X2<4

x>O,(j=1,2,3)

<J

要求：①寫出其對偶問題；②已知原問題最優解為X=(6，°，°),試運用互不松弛

定理求出對偶問題的最優解。

解：①

minvv=6y+4%

X-

3M+2%2-1

s.t.<

y+2%21

yx>^y2>o

②

?.?原問題的最優解為r=（6,0,0）

?/x}二6〉0

Xv-6<4,/.%=0

?二X=2

y*=（2,0）

3.6有一個求利潤最大的生產計劃問題，其最優單純形表如下所示。

ClC2b

3000

XiX2

XBX3x1X5

C2011/2-1/202

x2

2

C110-1/83/80

3

0&0001-21

00~4~40

其中，，43為松弛變量，試根據表回答下述問題；

⑴求,1'，2的數值：

（2）工廠應如何安排生產，最大利潤是多少？

（3）哪種資源有剩余，剩余量是多少？

（4）三種資源的影子價格是多少？

（5）在保持最優基不變的情況下，若要擴大某種資源的數量，應擴大哪一個？最多擴

大多少？并求出新的目標函數值。

(\1、1

-a—c.

2'8?4q=2

解:⑴131解得

一W

*

X

(5)人二(3/2,2,0,0,4)

Q7

z*=2x2+-xl+0=-

最大利潤22

Y

(6)由原問題的最優單純形表可得，其對偶問題的最優解7所

以由其對偶問題最優解可得，第三種資源有剩余，剩余量是4個單位;

(7)三種資源的影子價格分別為(1/4,1/4,())

(8)①當擴大第一種資源時

△b=0

O

j_

0

2~2

J_3

\x=B'AZ?=0

B88

1-21

2

3

-

XR~XH+2

4

-A+2>0

2

--A+->0

22

4+420

.\-4<2<12

⑹若最優值不變，

當9由2變成2+4,由1變成1+X,

4=-：（1+；）+：（2+7”0

檢驗數W.,解得一*W/lW2,即

134

%=5（1+義）一￡（2+幾）工。

Zo

4

-Kq?4

3,因此，若使最優基不變,橫取值范圍為“，的取值范圍為1,3.

3.7線性規劃

內+七

maxz=32x2+5

12411

-XH--X）H---&?-

3?3-336

421010

-X.H--X,H----W—

3?3-3'3

xy>0,7=1,2,3

經過單純形算法求解，最優單純形表3-16表示

310213/2

00-3-29

(I)當03由5增加為8時，最優解如何變化?

(2)當"1由11/6變為11/3時，最優解如何變化？當"2由10/3變為7/3時，最優解如

何變化?

11、

(3)如果原問題增加一個變量,對應。6=2,凡=

42J，請問最優解如何變

化？

解：⑴當與由5-8,則q=8-2-3X2=0

因此線性規劃有無窮最優解。

-

H

-

（2）①當弓由11/6—>11/3得△/?=6

O

1一H11

2--

-XB=X*+AX=

AX=Z?-1AZ?=2X6ToK

W1O11

-1

L工

得到如下單純形表:

32

500b

CRXB再九2元3工4元5

20112-1/217/3

x2

3王102[-1]1-1/3

00-3-1-2

21503/25

4-10-21-11/3

-10-50-3

r1T

因此，當乙由11/6變為11/3時，最優解變為X=050-0

②當口2由10/3變為7/3時,

-I2—

AXn?=BAb=-j>x>0

-11

此時最優解為x11000

1

-

4553

一

1一-2>O

⑶機會成本=YXE=[I2]x4=----所以

-44

2

應該生產。

耳y2

-i

20112-1/21/42

x2

3再102-111/43/2

00-3-1-23/4

2-11-13-3/201/2

2%6408-4416

-30-92-50

-1/31/3-1/31-1/201/6

4834/3