-M521100-115/2

2M+10M+15M+1200-M0

109/513/51/51/50009

02409[16]11003/2

—M7/50-1/53/5-2/50-117/3

09-M/53M/5+10-2M/5-20-M0

1()3/2139/8003/16-1/8()00

123/209/1611/161/1600

-M1/20-43/800-7/16-3/80-11

027/8-43M/800-21/8-7M/16-5/8-3M/8-M0

所有變量的檢驗數均為負數或零，單純形表“算完畢，但人工變量與仍在基變

量中，故原問題無可行解。

例6：求解下述LP問題

解.：用兩階段法求解。先將原問題化為標準型，可得:

引入人工變量，可得第一階段的問題為：

構造單純形表，計算如下：

000000111

16111—1001006

12-2010-10010—

100[2]-100-10010

1-3-1111000

16103/2-101/210-1/24

12-20[1]0-100102

0()01-1/200-1/2001/2—

10-5/2i1-1/2003/2

13[4]00-13/21/21-3/2-1/23/4

02-2010-10010—

01-1100-1/2-1/201/21/2—

-4001-3/2-1/205/23/2

03/4100-1/43/81/81/4-3/8-1/8

07/2001—1/2-1/41/41/21/4-1/4

07/4010-1/4-1/8-3/81/41/83/8

000000111

Q77

故'第一階段的最優解為『二右，『5，。，。，。，。，。，。尸

第二階段的單純形表如下:

2-12000

03/4100-1/43/81/8

07/2001-1/2-1/41/4

07/4010-1/4-1/8-3/8

0005/4-3/8-9/8

非基變量匕的檢驗數為正，但其系數向量為負，故原問題為無界解。

例7：已知下述線性規劃

的最優基為8*=H，46],求其最優單純形表。

解：由8*=有工,用,可知:

故由單純形表的行變換過程可知：

-01/401F8121001F41001/40

『3,A]=-21/211640010=400-21/21

1/2-1/80j[120

40012011/2-1/80

原問題的最優單純形表為：

23000

241001/40

0400-21/21

32011/2-1/80

00-3/2-1/80

例8：已知某線性規劃的最優單純形表為:

23000

241001/40

0400-21/21

32011/2-1/80

00-3/2-1/80

其中，毛，%，工5為松弛變量，求該線性規劃的初始單純形表。

解.：由七,七,七為松弛變量，可知它們在約束條件中的系數矩陣為單位矩陣，故

在最優單純形表中，它們的系數矩陣為即:

01/40102

=-21/21可得400

1/2-1/80014

由：

-1021「41001/40]「81200

BTBF,400400-21/21=1640010

4_||_2

01011/2-1/80J|_1204001

可知最初單純形表為:

23000

0812100

01640010

0120[4]001

23000

的最優解為X*=(6,2,0)"試利用互補松弛定理，求對偶問題的最優解。

解：原問題的對偶問題為：

揩X*=(6,2,。)/代入原問題的約束條件，可得：

[6+2*2=10=y；＞0

《力(1)

[2*6+2*2=16=＞y；＞0

又由

x；>0=>），；+2y；=3

x；>0=>2y；+2y；=4(2)

x；=0=y；+y；21

將結論(1)和(2)結合起來，可解得y：=y；=l。

例已知線性規劃問題

其對偶問題的最優解為y：=4、y；=l,試用對偶理論求解原問題的最優解。

解：原問題的對偶問題為：

將對偶問題的最優解代入約束條件，可得：

2*4+2*1〉2nx；=0

2*4>1=x：=0

~(1)

4+1=5x；>()

4+2*1=6nx；>0

又由

y；>0=2X；+X；+"=8(2)

72>0=>2<+2"+七*+2X4=12

將結論(1)和(2)結合起來，可得：

苫丁"不，解得卜=4

x3+2X4=12[x4=4

即原問題的最優解為X*=(0,0,4,4),O

解：先將原問題改寫為：

建立單純形表計算如下：

-2-3-400

0-3-1-2-110

0-4[-2]1-301

-2-3-400

0-10[-5/2]1/21-1/2

-221-1/23/20-1/2

0—4-10-1

-32/501-1/5-2/5V5

-211/5107/5-1/5-2/5

00-9/5-8/5-1/5

故，原問題的最優解為X*=(ll/5,2/5,0)"z*=28/5o

先用單純形法求出最優解，再分析以下各種條件下，最優解分別有什么變化:

(1)約束條件①的右端常數由20變為30；

(2)約束條件②的右端常數由90變為85；

(3)目標函數中七的系數由13變為8；

(4)%的系數列向量由［-1,12』變為［0,5『；

(5)占和馬的系數列向量由［-1，12/、［1,4/變為［0,5］T、［2,1R

(6)增力口一個約束條件③2%+3々+5元3<50；

(7)將約束條件②改變為10%+5X2+10七410°。

解：分別在約束條件①和②中引入松弛變量8和公，列單純形表計算如下:

-551300

020-11[3]1020/3

09012410019

-551300

1330/3-1/3[1/3]11/3020

070/346/32/30-10/3135

-2/32/30-13/30

520-11310

010160-2-41

00-2-50

由此可得，原問題的最優解為X'nO)；。,。,。［。)7',z*=100o

由單純形表可知，原問題中8一1=o

-41

(1)約束條件右端常數此時為〃=(30,90)1由

可知，單純形表應變為:

-551300

530-11310

0-30160[-2]-41

00-2-50

5-152310[-5]3/2

1315-8012-1/2

-1600-1-1

03-23/5-1/501-3/10

1396/52/5101/10

-103/5-1/500-13/10

由此可得，最優解變為x*=（0,0,9,3,0）,，z*=117o

（2）約束條件右端常數此時為〃=（20,85尸，由

可知，最優基不變，最優解為X*=（0,20,0,0,5）7,z*=10（）o

（3）若c\變為8,則鼻的檢驗數變為

故最優解不變。

（4）占在原最優解中為非基變量，若』的系數列變為［=；,由

可知，檢驗數?由0變為一5,故最優解不變。

（5）與在原最優解中為基變量，若用和馬的系數列變為有，4〕二；;，則

在約束①中引入人工變量兒，單純形表變為:

-551300-M

-M2009[3]10120/3

0105-7-2-410

-55+2M13+3MM00

1320/302/311/301/3

070/35-17/30-10/312/3

-5-11/30-13/30-M-I3/3

故，最優解為X*=(0,0,20/3,0,70/3,0)7,z*=260/3o

（6）若引入一個約束③，單純形表將增加一行。在約束③中引入松弛變量4,

單純形表變為：

-5513000

520-113100

010160-2-410

050235001

520-113100

01()160-2-410

0-1050[-4]-301

00-2-500

525/211/410-5/403/4

01527/200-5/21-1/2

05/2-5/4013/40-1/4

-5/200-7/20-1/2

由此可得，最優解為X*=(0,25/2,5/2,0,15,0)1z"=95。

（7）若約束條件②變為10%+5工2+10戈3<10°，即玉、￡的系數分別變為

20

b列變為〃=,則

100

由于基變量％的系數發生變化，故在約束條件①中引入人工變量4，單純形表

變為：

-551300-M

-M20-11[3]10120/3

020141-2-410

-5-M5+M13+3MM00

1320/3-1/31/311/301/320

0100/340/3[5/3]0-10/312/320

-2/32/30-13/30-M-13/3

130-3011-1/51/5

520810-23/52/5

-600-3-2/5-M23/5

故，最優解為X*=(0,20,0,0,0,0)\z*=最"

試分析當參數，之。變化時，Z"(f)的變化，其中z”是下述線性規劃的最優目標函

數值。

解.：引入松弛變量九3、&和毛，令，=0,列單純形表計算，可得：

35000

020011/3-1/3

560101/20

32100-1/31/3

000-3/2-1

將C=(3+2，,5T)代入,可得:

3+215-1000

020011/3-1/3

5-t60101/20

3+2t2100-1/31/3

000-3/2+71/6

37

a.=——+-r<0

26Al，可知當參數，從。開始增大到9/7,即

由?

CT=-1--/<()t>--

5S32

次［0,9/7］時，檢驗數都保持為非正，故此時最優解保持為X*=(2,6,2,0,01,

z*(r)=36-2ro

當參數f開始超過9/7,即f>9/7時，檢驗數。4>0,但其他檢驗數仍為非

正，此時選擇匕為換入變量，用單純形表迭代計算可得:

3+2t5-t000

060031-1

5-t301-3/201/2

3+2t410100

009/2-71/20-5/2+1/2

a.=-----<0

22

由，7，可知當參數如(9/7,5］時,最優解為

5t/

c5=---1—<0/<5

X’=(4,3,0,6,0)7,z"Q)=27+5f。

當參數，開始超過5,即，>5時，檢驗數%〉。，但其他檢驗數仍為非正，

此時選擇以為換入變量，用單純形表迭代計算可得:

3+215-t000

01202010

0602-301

3+2t410100

05-t-3-2t00

E=5-r<0[/>5

由<=?可知當(5,8)時，最優解為

(T3=-3-2r<0[f>-3/2

X*=(4,0,0,12,6)"，(1)=12+8人

綜述所述，可知：

例某個求最大值的線性規劃問題的最優單純形表如下，其中乙、看為松弛變量。

20-1131

41-10-10

0-30-3-1

(1)寫出該問題的最優解；

(2)當Aj為何值時，其對偶問題無解?

解：(1)最優解為X*=(4,020,0)7。

(2)由最優單純形表的檢驗數，可得方程組：

02+03+q=—3

<0-3%+〉=-3,可得。=(0,-4,1,0,0)o

0-c3=-l

若其對偶問題無解，則原問題為無解或無界解。當q變化時，原最優單純形表中

只有檢驗數將變化，故(4,0,2,0,0)/總是原問題的可行解。因此，要使對偶問題

無解，原問題必為無界解。

由原最優單純形表可知，馬的最終列向量為負，故當q=-3+AC3〉0,

即AC3〉3時，原問題有無界解，其對偶問題無解。

例1已知線性規劃

的最優單純形表為

250101/21/2

1310001

03001-1/23/2

000-1-2

（1）寫出最優基矩陣B及其逆矩陣3-

（2）寫出其對偶問題；

（3）給出對偶問題的最優解；

解：（1）由最優單純形表，可知

-21101/21/2

8==-120,B1=001

1001-1/23/2

（2）原問題的對偶問題為

（3）由原問題變量（內,工2，七，七,七）’與對偶問題變量（）1，%，%）'4,”），之間的對應

關系，以及對偶理論，可知:

即對偶問題的最優解為y*=（0,1,2,0,0）、

例2已知線性規劃

的最優單純形表為

621200

1284/31/311/30

06-250-11

-10-20-40

其中，山、.分別為第1、2個約束的松弛變量"

（1）求出最優基不變的。2變化范圍；

（2）求出最優解不變的C、變化范圍；

（3）在原問題中增加約束條件%+2%+2芻412,求最優解。

O-

解：由原問題的最優單純形表，可知8-=O

-11

「]/30-1「2Q

（1）記〃=[24,4r，則由夕%=、二,?可知，要使最優基

—11b4一24

不變，只需4—2420,即囪之24。

（2）要使最優解不變，只需保證所有檢驗數仍保持非正，即

6-4c3/3<0c3>9/2

2-C3/3<0,可得卜3之6,即C3N6。

-<:3/3<0c3>0

（3）在新約束條件中引入松弛變量X，在原最優單純形表中增加一行，可得:

6212000

1284/31/311/300

06-250-110

012122001

1284/31/311/300

06-250-110

0-45/34/30[-2/3]01

-10-20-400

1261/311001/2

012-1/23001-3/2

065/2-2010-3/2

0-10000-6

故，最優解變為X*=(0,0,6,6,12,0)"￡=72。

例1.用表上作業法求解下述運輸問題。

甲乙丙T產量

A1067124

B161()599

C541()1()4

銷量5246

解：這是一個產銷平衡問題，可用表上作業法求解。

用最小元素法求得初始解：

甲乙丙T產量

A314

B459

C224

銷量5246

用位勢法計算U和V：

甲乙丙Tui

A(10)(12)0

B(5)(9)-3

C(5)(4)-5

vj109812

計算非基本變量的檢驗數:

甲乙丙Tui

A-3(6)-1⑺0

B9(16)4(10)-3

C7(10)3(10)-5

vj109812

以（A乙）作為調入格，用閉回路調整法計算（A乙）的新運量:

甲乙丙T產量

A1214

B459

C44

銷量524