第二章-线性规划-山大刁在筠-运筹学讲义

第二章线性规划

教学重点：线性规划可行区域的几何结构，根本可行解及可行区域的根本定理，单纯

形方法，两阶段法，对偶和对偶理论，灵敏度分析。

教学难点：线性规划可行区域的几何结构，根本可行解及可行区域的根本定理，单纯

形方法，两阶段法，对偶性，灵敏度分析。

教学课时：24学时

主要教学环节的组织：首先通过各种形式的例子归纳出线性数学规划的一般形式，然

后在详细讲解主要内容的根底上，尽可能以图形和例题的形式给以形象的说明，使学生对

知识点有更直观、具体的认识。再通过大量习题稳固知识，也可以应用软件包解决一些实

际问题。

第一节线性规划问题

教学重点：线性规划问题的实例，线性规划的一般形式、标准形式和标准形式

教学难点：线性规划一般形式转换成标准形式。

教学课时：2学时

主要教学环节的组织：首先通过几个实例总结出线性规划问题的一般形式，再介绍如

何将一般形式转换成标准形式。

1、线性规划问题举例

生产方案问题

某工厂用三种原料生产三种产品，的条件如下表所示，试制订总利润最大的生产方案

单位产品所需原产品Q1产品产品原料可用量

料数量（公斤）Q2Q3（公斤/日）

原料P12301500

原料P2024800

原料P33252000

单位产品的利润354

1千元）

可控因素（所求变量）：设每天生产3种产品的数量分别为占,马，£・

目标：使得每天的生产利润最大，就是使得利润函数：

3X1+5X2+4X3

到达最大.

受制条件：

每天原料的需求量不超过可用量：

原料弋：2再+3/41500

原料尸2：2X2+4X3800

原料尸3：3x,+2x2+5x3<2000

蕴含约束：产量为非负数巧,心，£之0

模型

max3.r,+S.r2+4.r3

2工］+3X2<1500

2X2+4X34800

3工］+2石+5叼42000

{.，吃，工320

运输问题

一个制造厂要把假设干单位的产品从两个仓库A,;i=1,2发送到零售点B.;j=1,2,3,4,

仓库4能供给的产品数量为%"=1,2,零售点与所需的产品的数量为号;，=1.2,3,4。假

设供给总量和需求总量相等，且从仓库运一个单位产品往吃的运价为％。问应如何组

织运输才能使总运费最小？

求解

设专（i=l,2,j=l,2,3,4）表示从仓库4运往零售点吃的产品数量。

模型：

24

min£2%与

1=1j=l

「Xil+Xi2+xi3+Xj4=%；i=1,2

s.1.+X［j—bj—1,2,3,4

.30;i=l,2,j=l,2,3,4

2、线性规划模型

minz=qx+c2x2+,・・+cnxn

+・・•〃加

%%+ai2x2=b"=l,2,・.・,p

・・.，

+ai2x2+・・•%£?>b^i-p+1,m

"Xj>0;y=1,2,...,^

X,无限制；J=q+1,…,〃

LJ

xRj=1,2,...,n为待定的决策变量，

C=（C］,C，2,…,c〃）为价值向量，

Cj；j=n为价值系数，

b=（d,%,・“,力,）为右端向量，

44〃、

矩阵A="：为系数矩阵

线性规划模型的概念

可行解［或可行点）：满足所有约束条件的向量”=（占户2,…A：3'

可行集（或可行域）：所有的可行解的全体&={x|Ax=AxZ0}

最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合

O={xe£)|CTX<cTj,VyeD}

最优值：最优解的目标函数值y=cTx,xwO

线性规划解的情况：

无解或不可行D={x\Ax=b,x>d]

无界DW0但目标函数在可行域上无界

有最优解。W0且目标函数在D上有有限的

现象规划模型的标准形式和标准形式：

标准形式：

mincJx

Ax>b

x>()

标准形式：

mincTx

Ax=b

S.t.'

x>0

形式转换

一般形式转换成标准式：

等式化成不等式：

。“占+624+〜〃"〃=可

口

fa

i^^ai2x2+-ainxn<ibi

+62工2+…°加x八之々

自由变量化成非负变量：

令自由变量壬J=邛J-石J，其中XJ；/J；为非负变量

Q,i~+62%2+

口

。“马+62工2+NO

或

ax

ixx+af2x24-•••«,„xn>^.

口

+«f2x2+--«/nx/J-s.=^.,s.>0

目标函数的最大问题向最小问题的转换

TP*T*

maxcx—>min-cx

例：将下述问题转换成标准形式：

maxz=—x\+xl

2X1-x?2—2

X1-2x,<2

x}+x2<5

xi>0

解：

minz=x,-(x3-x4)

2占一(4一34)-乙=-2

占-2(£74)+工6=2

X,+(x3-x4)+x7=5

巧>0;i=1,3,4,5,67

第二节可行域与根本可行解

教学重点：线性规划问题的图解法，可行区域的几何结构和线性规划根本定理。

教学难点：线性规划的根本定理。

教学课时：4学时

主要教学环节的组织：首先通过图解法求出两个变量时可行区域的结构和最有点的位

置，再进行一般情况下可行区域的结构进行讨论，得到线性规划的根本定理。

1、图解法

对于只有两个变量的线性规划问题可以用图解法求解：

变量用直角坐标系中的点表示，约束条件用坐标系中的半空间或直线的交表示，可行区域

是一个凸多面体，目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最

后的交点就是最优解

例1、

maxz=-X1+x2

2X|一%2—2

x,-2X<2

s.t.\7

X1+x2<5

>0

例2、假设将例中的目标函数改为求N=4M—2七的最小值

当目标函数改变后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平

行，那么该函数值线上的所有可行解都是最优解

，最优解(1,4)

目标函数值可能出现的情况：

1、可行域是空集；

2、可行域无界无最优解；

3、最优解存在且唯一，那么一定在顶点上到达；

4、最优解存在且不唯一，一定存在顶点是最优解。

从图解法的几何直观易得：

线性规划的可行域是假设干个半平面的交集，它形成了一个有界或无界的凸多边形。

对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上到

达。

2、可行区域的结构

定义：设ScK”是〃维欧氏空间的点集，假设对任意

彳€£。€5的和任意力£[0,1]都有力:+(1-4”£5就称5是一个凸集。

定理：线性规划的可行域D={x|Ax=A,xNO}是凸集

证明：略。

定理.：任意多个凸集的交还是凸集

定义：超平面H={xeRn\aTx=b}

半空间H+={xeRn\aTx>b}；={xeRn\aTx<b]

n

定义：多面凸集S={XGR\aJx=bt;i=1,2,…,N4"=p+l,p+2,…,p+q}

定义：设S为凸集xwS,如果对任意eS和0vAv1,

都有x/Ay+(l-4)z,那么称x为S的顶点。

根本可行解

令A=(B,N),其中8为A的一个满秩子方阵，

Ax=b分块.8+NXN=b

左乘XB+B-'NXN=B-'b

即XR=『b-『Nx、

定义：设3是秩为机的约束矩阵A的一个，〃阶满秩子方阵，那么称3为一个基（或

基阵）；区中机个线性无关的列向量称为基向量，变量x中与之对应的次个分量称为基

变量，其余的变量为非基变量，令所有的非基变量取值为0,得到的解工=”称为相

I。）

应于5的根本解。当20那么称根本解为根本可行解.，这时对应的基阵。为可行基。

如果万一%>0那么称该基可行解为非退化的，如果一个线性规划的所有基可行解都是

非退化的那么称该规划为非退化的。

定理可行解工是根本可行解的充要条件是它的正分量所对应的矩阵A中列向量线

性无关。

证明：不妨设亍=（不……,0/■，可>0"=L・・，h

假设亍是根本可行解，那么取正值的变量对应的列向量A，为基向量，故线性

无关.

反之，假设A，…,线性无关，那么有2弓4=瓦k<m.

j=i

假设攵=机，那么有3=（4,…4）为基.亍为基可行解；

假设女<加，那么可从其余〃-Z个列向量中再挑选m-4列向量与4，组成基，易

知，元为基可行解.

定理工是根本可行解的充要条件是元是可行域。的顶点。

定理一个标准的LP问题如果有可行解，那么至少有一个根本可行解

证明：设.丁是任意一个可行解，那么有

Q

Ax=byx°>0.

不妨设¥>OJ=1,,上后〃-％个向量为o.假设4，,4线性无关,那么由定理知x°

是根本叫丁解；杏那么存在小全为零的H，使得£>必=0,补充a=0,，=k+l,…，〃得5,

>1

满足Ab=0.

定理一个标准的LP问题如果有有限的最优值，那么一定存在一个根本可行解是最优

解。

证明：设是一个最优解，如果x0是根本可行解，那么问题得证；否则按定理的证

明可得到x°+靖和x°—靖，由才/0+872和。々°一方苇之。0°知c,b=0,故有

，（x°+蜡）=c々°.按照定理2.2.5的证明方法迭代，最终可得到根本可行解亍，满足

cTx=cTxQ.

第三节单纯型方法

教学重点：单纯形算法和单纯形表。

教学难点：单纯形算法，单纯形表。

教学课时：4学时

主要教学环节的组织：首先给出单纯形算法，然后给出单纯形算法的一种实现手段,

单纯形表。

1、单纯型方法

考虑标准形式的线性规划问题

・T

minex

(Ax=b

其中并且假定〃且可行域。={X£R[Ar=b,xNO}工。，系

数矩阵A是行满秩的，即r(A)=*

给定一个非退化的根本可行解至，对应的可行基为那么等式约束AX=b可以变为:

l

xR+B-NxN=B'b>0--------典式

l

或xH=Bb-B^NxN

_/y\/D-lt''

此时令/=0,那么4=5".所以最="=>0.

I0)

ii

目标函数。晨=。"+clxN=c1(B~b-B~NxN)+c}xN

ii

=c]tB-b-(c^B-N-cl)xN

令久=以歹卬-。3金=o,那么。％=或夕?-9x

minc^B^b-x

1

规划等价于xH+BNXN=B'b

xNO

定理(最优性准那么)如果JKO,那么基可行解土为原问题的最优解。

证：设工为原问题的任一可行解。由于转0,而440,所以夕x《0.从而

Jx=z0x>z0=JX.

定理如果向量4的第A个分量服>0,而向量8TAA«0,那么原问题无界。

证明：令d=4+ek,其中q是第2个分量为1,其余分量为0的〃4W0,所以有

J＞0,而

/_7\

Ad=(B,N)~k+A.=0

(())

对于充分大的正数凡观察向量工+如，此时有

AJ0d)=b

x+0d＞0

它所对应的目标函数值为

cT(x+0d)=cTx+0crd=crx-A—q)=cTx-殴

由于金＞0,而。〉0可任意的大，故原问题目标函数无下

定理对于非退化的根本可行解"假设向量J的第A个分量短＞0,而向量夕|4.至少有

一个正分量，那么可以找到一个新的根本可行解上使得cT^vJ土。

证明：只需将土具体的找出来.

令

-A.

[o)+/

满足Ad=0

令

%-西、

x=x+3d=十%

、()；

下面证明，当适中选取。＞0后，土即为所求.

显然，Ax=Ax+9Ad=b,为使£20,那么要求。—。4之。，所以令

瓦

0=minV幻〃>0,i=l,…，m

纵

定理的一些说明：

1、检验数向量：7T=以田”-/,它的每个分量称为检验数。

2、第k列称为进入基列，第k个变量称为进基变量；第i列称为退出基列，第i个变量称

为离基变量。

定理对于任何非退化的LP问题，从任何根本可行解开始，经过有限屡次迭代，或得到

一个根本可行的最优解，或作出该LP问题无界的判断。

单纯型方法的算法步骤：

stepl找一个初始可行基3；

step2求出典式和检验数彳：

step3求媒=maxCj|j=l,2,・・・M

step4如果1W0,停止,

/]=已：及最优值2=°»；

己找到最优解x

step5如果&KO,停止，原问题无界；

step6求。=min也/aik\ajk>0,/=1,2,...,m}=br/4

step7以&替代4得到一个新的基，转st2

2、单纯形表

一般假设当前的基8=（4，A2，...，4〃）对应的单纯形表为

•••x•••xXX

X]rm+\…k…n

••否火…瓦

1alm+\瓦

•****

*■(•••*

■**•***

1ann+\…irk…瓦

*■e•••

■«**B*

•*•**••

1anun+\…再位…0mn

bin

如果乙为入基变量，吟为出基变量，那么经过变换单纯形表为

x•••x•••XX

\rmm+\…Xk…4

A

1加力切+1…0・••力〃瓦

*••****

■**•***

*•****•

•[•••八人

1凡karnhr

■■•**

•■a**••

•■•••**

A・A

^mr10...a

bm

其中4=%-arjaik/a^;i=1,2,・・・/〃#arj=arjlark,

k="法，A=”一%”/心。

目标函数Z=。；夕》-(c；B'N-)小等价于

2+（。：夕7"—或）£>=以6%

由于3=。，八=或8一"-。3所以Z+夕=或"一?。把z看成变量在单纯形表中加上

一列，同时加上一行描述方程Z+夕=或歹］,那么可以得到新的单纯形表：

・・Y•••

Zx{•X»”…工〃？八皿+14…4

10…0…0如+1…获…露c^B-lb

1即〃+1…年…而瓦

■•**■■•■

*••*•*•*•*•

1万"…arn

br

■*■■■•

•■***•*•**•

1W加+1…可心…

"加〕bm

当进行转换时只需要把短转换成0对应其它位置等价变换即可。

7v•••Y•••Yv•••Y•••v

A人l人r人小人〃i+l人k人〃

10…-4/心…0盲"+1…0…总c^b

A

1加山〃田…0…ah

Xn\

1/W火&r，〃+l・••1・••那“

br

■••••♦

••••♦♦

^mr14加+]…0***6〃in源

其中a=务一％务/以；c^B-'b=clB-'b-b^/a^。

例求解问题：

minz=-x2+2x3

X1-2x2+x3=2

x,-3X3+x4=1

与-Z+/=2

XjNO;j=1,2,…5

解：以占、X,和人为基变量就可以得到初始基可行解(2,0,0,1,2)1

其对应的单纯形表为

工3/

1-2

1-212

1-311

1-112

由于虞=1>0,所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取

々为入基变量。计算e=min{；A}=l,所以取第二个约束对应的基变量乙为出基变量，

就可以得到一个新的基可行解，在上表中把与对应的列变成单位向量，系数矩阵第2行对

应的元素为1,那么可以得到该基可行解的单纯形表

*心必%

01-1-1

10-524

1-311

02-111

由于乙=1>0,所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取

/为入基变量。计算所以取第3个约束对应的基变量与为出基变量，就可以得到

一个新的基可行解，在上表中把心对应的列变成单位向量，系数矩阵第3行对应的元素为

1,那么可以得到该基可行解的单纯形表：

与%

00-1/2-1/2-3/2

10-5-1/25/213/2

10-1/23/25/2

01-1/21/21/2

由于检验数都小于等于0,所以该基可行解就是最优解,

对应的最优解为(13/2,572,1/2,0,0),最优值为-3/2。

注：

1.该算法在实际应用中非常有效，被广泛采用，

但在理论上不是多项式时间算法。

2.现在还有待解决的问题是如何给出初始基可行

解以及出现退化的时候如何处理。

第四节初始解

教学重点：两阶段算法的思想。

教学难点：两阶段算法的思想。

教学课时：4学时

主要教学环节的组织：给出两阶段算法的思想，并用单纯形表进行求解。

两阶段法

根本思想

第一阶段：通过求解辅助问题的最优基可行

解得到原问题的初始基可行解。

第二阶段；求原问题的最优解

设原问题为

•T

minex

[Ax=b（2.4.1）

s.t.<

[x>0

不妨假设力之0,如果某一个元素小于0,该方程两边乘于-1后那么可以使右端数变成正数。

考虑如下辅助问题：

ming=Xu

/=M+，（2.4.2）

Ax+x=b

s/・《a

x>0,xa>0

其中X。=（X“+”X“+2…，X"+,”）T。首先用单纯形法解这个辅助问题。

1.显然如果原问题（）有可行解，那么辅助规划（2.4.2）的最优值为0,反之亦然。

2.由于〃之0,所以以乙=（工田,西,+2，・・・，与.广为基变量，就可以得到规划（）的初

始基可行解（0,从产。

n-¥m

3.规划（）有可行解（0,所）\同时与之0,所以即辅助问题的目标函数

i=〃+1

有下界，所以该问题一定有最优解。

4.因此我们可以首先求规划（）的最优基可行解（月月），如果最优值为0,那么口=0,

所以1是问题（2.4.1）的可行解。由于行，耳）是规划（2.4.2）的基可行解，所以其非零分

量对应系数矩阵的列向量线性无关。所以土的非零分量对应的系数矩阵的列向量也线性无

关，所以工是问题（2.4.1）的基可行解。在规划（2.4.2）,我们称右为人工变量。

i.£肛=0且乙为非基变量，那么此时文是问题（）的基可行解，

i=n+l

且基变量不变。在最优基可行解的单纯形表里删除与对应的列,

同时计算出检验数就可以得到原问题的单纯形表。

2.£巧=0旦/中有局部变量为基变量，此时X是问题（）的基

i=〃+l

可行解，不同的是基变量会有些改变。

n+nr

3.£a>0,那么原问题没有可行解。

i=〃+1

例求解

minz=5x,4-21x3

*

-x2+6X3-x4=2

・〈

s/x,+x2+2X3-x5=1

Xj；j=l,2,3,4,5

如果以%、/为基变量，那么可以得到该问题的基解（0,0,0,-2厂1）\不是可行解，而其第

一个基可行解不能直接给出。

首先引入人工变量，考虑问题

minz=x64-x7

T,—T,4-613—x4+x6=2

s・f・(X[+x2+2X3-xs+x7=1

以乙和工7为B；j=123,4,5,6,7基变量可得其第一个基可行解

（0,0,0,0,0,2,1产，

其对应的单纯形表为

工2%%X]

-5-210

28-1-13

1-16-112

112-111

由于么=8>0,所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取

心为入基变量。计算e=min{3H=/所以取第1个约束:对应的基变量与为出基变量，

就可以得到一个新的基可行解，在上表中把心对应的列变成单位向量，系数矩阵第I行对

应的元素为1,那么可以得到该基可行解的单纯形表

工1犬2工4%%

-3/2-7/2-7/221/67

2/34/31/3-1-4/31/3

1/6-1/61-1/61/61/3

2/34/31/3-1-1/311/3

由于&=4/3>0,所以该基可行解不是最优解，同时系数矩阵该列有大于。的元素，所以

取也为入基变量。计算6=所以取第2个约束对应的基变量与为出基变量，就可以

得到一个新的基可行解，在上表中把X2对应的列变成单位向量，系数矩阵第2行对应的元

素为1,那么可以得到该基可行解的单纯形表

工4%%X1

1/4-21/8-21/821/821/863/8

-1-10

I-1/8-1/81/81/83/8

1/211/4-3/4-1/43/41/4

由于检验数都小于等于0,所以对应的基可行解就是维助问题

的最优解，最优值为0,且人工变量都是非基变量，所以得到

原问题的基可行解，对应的基变量为12和13,

对应的单纯形表为

修元2元3工4%

1/4-21/8-21/863/8

1/41-1/8-1/83/8

1/211/4-3/41/4

由于4=1/4>0,所以该基可行解不是原问题最优解，同时系数矩阵该列有大于0的元素,

所以取为为入基变量。计算e=min{，3!G}=!6,所以取第2个约束对应的基变量12

为出基变量，就可以得到一个新的基可行解，在上表中把川对应的列变成单位向量，系数

矩阵第2行对应的元素为1,那么可以得到该基可行解的单纯形表

3x2£X4•4

-1/2-11/4-9/431/4

-1/21-1/41/41/4

121/2-3/21/2

由于检验数都小于等于0,所以对应的基可行解就是原问题的最优解，最优值为

31/4,对

应的最优解为(1/2,0,1/4,0,0)，

第五节对偶和对偶单纯形方法

教学重点：对偶性，对偶理论，对偶单纯形方法。

教学难点：对偶性，互补松紧条件，对偶单纯形方法。

教学课时：6学时

主要教学环节的组织：首先给出对偶性，然后通过对偶理论得到互补松紧条件，最后

介绍对偶单纯形方法。

定义

给定一个一般形式的LP问题，称它为原始LP问题，它的对偶问题定义如下：

原始对偶（D）

•T

mincxmaxbfw

i=L…,p

afx=bzW任意

i=p+1,・・•,〃?

afx>bzwz>0

s.t.<

Xj>0j=h…,qAjw<Cj

厂q+l,・・・,〃

匕任意卬=c

标准形式线性规划的对偶规划

minc'x

考虑线性规划的标准形式Ax=h(I)

s.t.

x>0

根据单纯形理论，假设I是最优基可行解，其对应的基阵为8那么其检验数为

品=丹8-8-4=0,£N=C；BTN-C：,<0,同时，8=夕"，丸=0，最优值为

TlTJ

cx=c}B-bo如果令而=c；ZrL那么有ba）=cxo

同时而是以下规划的可行解

maxb1co（口）

s.t.

对于规划（I）的任意可行解x和规划（H）的任意可行解由于“NO所以有

co1b=co1Ax<cTx

由此可知而是规划（H）的最优解，反之亦然。两人规划的最有解之间存在着密切的关

系，通过一个规划可以得到另一个规划的最优解。同时从形式上两者之间也有本质的相似,

给定（A也c）后两个规划相伴而存在，因而称两个规划互为对偶规划。

标准形式的线性规划

mi•neTxm•ineTx

（P）[Axb____K（Ax-ly=b

s,tA।一。s/・,

其对偶规划为

maxb'co

max/7”

(D)

<(cT,0)

69>0

对于一般形式的线性规划

minz=C1X]+c2x2+・••+",

ai}x}+ai2x2+ainxn=bi\i=1,2,...,〃

sj.aj}x}+ai2x2+••%£]>Z?；;z=〃+1,

>0;y=1,2…q

通过把其转化为标准形式同样可以得到其对偶规划为：

maxl/co

，T

A,co<c'j=q+1,...,〃

s.t.<Ais=c”j=T2...,q

g=();/=p+

min5x)+21x3

X]-W+6七-x=2

例：写出以下规划的对偶规划：4

s.t.<xi+x2+2x3-x5=1

X；J=1,2,,5

min5X[+21x3

-x2+6X3-x4=2

s,tAxt+x2+2X3-x5=1

qj=1,2,…5

max2(z?I+a)2

+。245q+生45min5~+21x3

一+。2V°----->一0+gV0一►Xi-x2+6*3>2

+2G)2<216(y,+2a)2<21Xi+工2+2%N1

一?40叫N0xy;j=1,2,3

一七3002NO

2、对偶理论

定理如果一个线性规划有最优解，那么其对偶规划也有最优解，且它们的最优值相等。

证明：对于标准形式的线性规划（I）的任意可行解工和它的对偶规划（H）的任意可行解。，

由于xNO所以有

db=69^（Ax）<cTx

假设三是（I）的最优基可行解，其对应的基阵为4令习=c'B-',那么而是（II）的可行

解.根据上面的不等式可知：（II）有最优解。同时又有齿丁〃二F无，所以它们的最优值相

等。

推论假设X和①分别是原规划和对偶规划的可行解，那么X和。分别是原规划和对偶

规划的最优解的充要条件是C、=cJb

定理线性规划的对偶规划的时偶规划是原始规划。

证明：

min-力

maxb'co----->

AJCDJ-ATGTT+y=c

s.t.co1A<c{

◎丁，力1N0

maxxTc

s.t./(A，,—A\/)W(—/?,/?,())

maxcTxmax-cTx

mi•neTx

xTAJ<-br-xTAT>^T

Ax=b

-xTAT<,bTs.t.'XTAT2-bT

xNO

xWO-xNO

定理给定一个原规划和对偈规划，那么下面三种情况必有其一（具体见教科书上表2.5.1）：

定理（互补松紧性）

假设x和。分别是原规划和对偶规划的可行解，那么x和g分别是原规划和对偶规

划的最优解的充要条件是：

Ui=x—bj=0;z=1,2,...,加

T

匕=（Cj-coAj）x}=0;j=1,2,n

例题：考虑在例给出的原始问题和其对偶问题。由于原始问题是标准形式，故互补松紧条

11T

件（）自动满足。在例2.4.1中，已求出这个原始LP问题的最优解为x=（5,0,10,0）"

其中%>0,毛〉。所以（2.5.14）变为

1

c,-wA,=0

。3-卬73=0

即对偶问题最优解必使第一个和第三个约束取等式，有

W1+W2=5

6WJ+2卬2=21

11931

由此可解出叱=0吗=7,其对应的目标函数值为三，由定理知，此为对偶问题的最优

解。

对偶问题与原问题，一个线性规划的规模较大时或许改为求解它的对偶问题反而比拟适当。

对偶单纯形方法的步骤

第1步列出初始单纯形表（它含有原问题的一个根本解和对偶问题的一个可行解）；

第2步求a=minm|i=1,.・;

笫3步假设瓦20,停止。已找到原始问题最优解工=4=及最优值z=45；

第4步假设EN0,./=l,,〃，那么原始问题无可行解，停止；

第5步求min＜刍万＜0,j=1,…，〃二堂；

&4

第6步以纵为转轴元做一次旋转变换，转到第2步

例：运用对偶单纯形法解以下规划

minx]+x2+x3

3Xj+x2+xy>\

-x1