2021年度大学运筹学课程知识点总结

1.用图解法求解下列线性规划问题，并指出问题具备惟一最优解、无穷多最优解、无界解还是

无可行解。

maxz=%]+/

6匹+10%2(120

<5<Xj<10

3<x2<8

2.将下述线性规划问题化成原则形式。

minz=-3%]+4x2-2x3+5x4

4X|-/+2%3-%4=-2

%1+%2—％3+2匕<14

（1）4

—2X1+3%2+13—%4之2

xl,x2,x3>0,"无约束

解：令z'=_z,x4=x4-x4

ttt

maxz'=31]-4x2+2x3-5x4+5x4

广tIt

—4xj+%2—2%+%—%=2

Xj+%2—X3+2%4—2%4+£=14

—2%|+X3—%4+%4—

3%9+=2

龙1，龙2，％3，入4，%；，%5，％620

3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中各基可行解相应图

解法中可行域哪个顶点。

maxz=10x)+5x2

玉+

34X2<9

<5X[+2X2<8

X],々-0

②单纯形法：将原问题原则化:

maxz=10^+5x2

3x1+4X2+9=9

<5x1+2X2+x4=8

G10500相应图解法

Bb0

cBXlX2X3X4中点

0X3934103

0X48[5]2018/5o点

010500

0X321/50U4/5J1-3/53/2

10Xi8/512/501/54c点

Gj-16010-2

5X23/2015/14-3/14

1()Xl110-1/72/7B点

Gj35/200-5/14-25/14

最优解为(1,3/2,0,0),最优值Z=35/2。

单纯型法环节：转化为原则线性规划问题；找到一种初始可行解，列出

初始单纯型表；最优性检查，求cj-zj,若所有值都不大于0,则表中

解便是最优解，否则，找出最大值那一列，求出bi/aij,选用最小相

相应xij,作为换入基进行初等行变换，重复此环节。

4.写出下列线性规划问题对偶问题。

/〃，1

minz=>汇%

Z=1j=\

%/=4(i=l,…3篦)

/=1

(1)

/=]

Xjj>0。=1,…，帆;/=1,)

maxw=Z《y+tn

i=\i=\

c

yt+ym+jijG==•••,«)

七,y.无约束

n

maxz=Vc：x：

JJ

j=l

n

ZauXJ-bi(i=1,…叫<m)

(2)〃

(z=m,4-1,m+2,•一,m)

s.t.<1a/j="A

Xj>00=1,・・・巧<〃)

x.无约束(j=%+1,・・・，.)

m

minw=/biyi

i=l

C/=I,2，F<〃)

i=l

(J=«,+1,…,〃)

s.t.\^aijyi=cj

1=1

XNO(i=1,2,…叫<加)

必无约束(i=+1,---,m)

5.给出线性规划问题

maxz=2X]+4x24-x34-x4

x1+3X2+x4<8

2x]+x2<6

s.f.<x2+x3+x4<6

玉+x2+x3<9

Xj20(/=l,…4)

规定：Q）写出其对偶问题；（2）己知原问题最优解为X*=（2,2,4,0）、试依照对偶理论，直

接求出对偶问题最优解。

解:

minw=8y+6%+6%+9J4

M+2%+%22

3y,+%+必+”24

s.t.<乃+”21

M+%之1

y.>0G=l,--4)

(2)由于%,％2，刍>0,第四个约束取等号，依照互补松弛定理得:

,M+2y2+%=2

3M+为+%+%=4

V

%+以=1

.+>4=°

求得对偶问题最优解为：Y*1,0),最优值minw=16。

例已知原问题

Maxz=X]+2X2+3X3+4x4

x(+2X2+2x,+3x4W20

lx,+x2+3X3+2X4W20

X[、x2>X3、x4>0

和对偶问题

Minw=20y,+20y2

+

yt2y221

2y,+y2>2

2y「3y2二3

3yi+2y2>4

yi'y2^°

已知对偶问题的最优解y】=1.2、y2=0.2,最优值minw=28,

求原问题的最优解及最优值。

可用如下方法求解：

引入将原问题和对偶问题化为标准形式。

Maxz=x{+2X2+3X3+4X4

X]+2X2+2X3+3X4+x5=20

2xj+x2+3X3+2X4+x6=20

XpX2>X3、x4>x5>x6>0

和

Minw=20y1+20y2

y1+2y2一丫3=1

2y1+y2-y4=2

2y/3y2~y5=3

3y"2y2-y6=4

y2'y3'y4、y$、y6^°

(1)yj=1.2>0,而与X5中至少有一个为零，故X5=0。

(2)同理，y2=0.2>0,所以*6=0。

(3)对偶问题的第一个约束条件在取最优值时

y,+2y2=1.2+2X0.2=1.6>1

这就表示该约束条件的松弛变量：

y3=1.6—1=0.6>0

丫3与X]中至少有一个为零，故X[=()。

(4)同理，对于第2个约束条件在取得最优值时

2y(+y2=2X1.2+0.2=2.6>2

y4=2.6—2=0.6>0

丫4与X2中至少有一个为零，故X2=0。

（5）同理，对于第3个约束条件在取得最优值时

2yt+3y2=2X1.2+3X0.2=3

丫5=3-3=0

丫5与X3中至少有一个为零，故X3X）或者X3=0。

（6）对于第4个约束条件的分析也可得到x-0或者X4=00

对于（5）和（6）的分析，对于确定原问题的最优解没有

任何帮助。但从（1）到（4）的分析中得知，原问题取得

最优解时：

x-=0,x6=0,X]=0,x2=0

代入原问题的约束方程组得：

2X3+3X4=20

3X^+2X4=20

解此方程组，可求得原问题的最优解为：

X]=0,x2=0，X3=4*X4=4>x5=0,x6=0

弱对偶性推论：

（1）原问题任一可行解目的函数值是其对偶问题目的函数值下界；反之对偶问题任

一可行解a的函数值是其原问题目的函数值上界

（2）如原问题有可行解且目的函数值无界（具备无界解），则其对偶问题无可行解；

反之对偶问题有可行解且目的函数值无界，则其原问题无可行解。

注意：本点性质逆不成立，当对偶问题无可行解时，其原问题或具备无界解或无可

行解，反之亦然。

（3）若原问题有可行解而其对偶问题无可行解，则原问题目的函数值无界；反之对

偶问题有可行解而其原问题无可行解，则对偶问题目的函数值无界。

强对偶性（或称对偶定理）

若原问题及其对偶问题均具备可行解，则两者均具备最优解，且它们最优解目

的函数值相等。

互补松弛性

在线性规划问题最优解中，如果相应某一约束条件对偶变量值为非零，则该约

束条件取严格等式；反之如果约束条件取严格不等式，则其相应对偶变量一定为零。

影子价格

资源市场价格是其价值客观体现，相对比较稳定，而它影子价格则有赖于资

源运用状况，是未知数。因公司生产任务、产品构造等状况发生变化，资源影

子价格也随之变化。

影子价格是一种边际价格。

资源影子价格事实上又是一种机会成本。随着资源买进卖出，其影子价格也将

随之发生变化，始终到影子价格与市场价格保持同等水平时，才处在平衡状态。

生产过程中如果某种资源未得到充分运用时，该种资源影子价格为零；又当资源

影子价格不为零时，表白该种资源在生产中已耗费完毕。

影子价格反映单纯形表中各个检查数经济意义。

普通说对线性规划问题求解是拟定资源最优分派方案，而对于对偶问题求解则是拟

定对资源恰当估价，这种估价直接涉及资源最有效运用

对偶单纯型法：转化成原则线性规划问题；拟定换入基变量，bi不大于。中最小那

一排，再求(cj-zj)/aij,且aij<0,找出最小值，这相应xi便是换入基，若所有

bi都不不大于0,则找到了最优解

7下列表分别给出了各产地和各销地产量和销量，以及各产地至各销地单位运价，试用表上作

业法求最优解。

注意要基可行解个数一定是行列变量数减一

地

BIBB产量：

产地B234

A,41468

A212508

A337514

销量656320

解：

(1)拟定初始方案

西北角法:

销地

BiBBB产量

产地234

Ai628

358

A2

A3134

销量656320

最小元素法:

销地

BiBBB产量

产地234

A]538

A2538

A3134

销量656320

沃格尔法:

地行罚数

BiBB,B产量

产241234

14111416

8③022

A|53

11121510

A811@

262

[_3_Lz_|_5_

A41244

331

销量656320

12111

列

2②11

罚

311

数

41⑤

8.下表给出一种运送问题及它一种解，试问：

(1)表中给出解与否为最优解？请用位势法进行检查。

(2)若价值系数C24由1变为3,所给解与否仍为最优解？若不是，祈求出最优解。

(3)若所有价值系数均增长1,最优解与否变化？为什么？

(4)若所有价值系数均乘以2,最优解与否变化？为什么？

B)B.,产量

产地B2B4

4146

Ai8

53

6

12110

A282

37514

A331

销量856322

解：（1）

地

Bi产量Ui

产地B2B3B4

446

Ai180

53

26

11101

A282

375141

A331

销量856322

Vi0140

空格检查数为:

46

01

25

所有检查数均不不大于等于零，该方案为最优方案。

（2）若价值系数C24由1变为3,

66

-2-1

45

由于有检查数不大于零，因此此方案不是最优方案。

5(-2)3(+2)

8(+2)2(-2)

3(-2)1(+2)

调节为:

35

82

13

空格检查数为:

46

12

25

所有检查数均不大于等于零，该方案为最优方案。

minz=3xl+5x4+8xl+2x2+lx5+3xl=43。

（3）不变化，不影响检查数大小。

（4）不变化，不影响检查数符号。

解最优性检查：

1.闭回路法：找各个非基变量闭合回路，依次加减求检查数，是先减再

加，若所有检查数值都全非负，那么此可行解是最优解。

2.位势法（对偶变量法）：增长位势列ui和位势行vj;计算位势，ui+vj=

基可行解相应运费，指定其中某一值为0,算出其她几位值，填入表中；

计算检查数，某非基变量相应运费减相应位势行和位势列，若检查数全

为非负，则为最优解。

（检查数都是非基变量通过解决后值，解决过程中应用是基变量）

解改进：1.以检查数不大于Oxi为换入基（取最小那个）

2.找此xi闭合回路，以xi为始沿顺逆时针方向把定点依次编号

3.在所有偶数顶点中，找出运送量至少顶点作为xi换出变量

4.将基数顶点运送量增长xj,偶数顶点运送量减少xj,重新得到

一组新方案

5.进行解最优性检查

9.公司决定使用1000万元新产品开发基金开发A,B,C三种新产品。经预测预计，开发A,B,

C三种新产品投资利润分别为5%、7%、10%。由于新产品开发有一定风险，公司研究后拟定

了下列优先顺序目的：

第一，A产品至少投资300万元；

第二，为分散投资风险，任何一种新产品开发投资不超过开发基金总额35%；

第三，应至少留有10%开发基金，以备急用；

第四，使总投资利润最大。

试建立投资分派方案目的规划模型。

解，设A,B,C三种新产品开发投资额分别为王,乙,七万元，目的规划模型为:

milled；,舄("；+"；+若)%,P4dA}

项+4--4*=300

X,+一玄=1000x35%

x2-d；=1000x35%

s.tA/+/-d；=1000x35%

1000-2-/-W+4-d；=1000x10%

5%否+7%X2+10%x3+恶-霖=1000x10%

+

x1,x2,x3,jr,J/>0(/=1,•••,6)

PI是优先因子，关系为I越小，则有绝对优先性，尚有一种是相

对优先性，用权系数来表达

目的规划普通格式;min{pld+或dT（要明白为什么是写d+或d-,

min里d是要取值为零，即若不等式要不不大于零时，则写d-）;必要

要满足绝对约束，尚有目的约束；xj>0,d+,d->0

目的规划图解法：先画绝对约束可行域，然后按照优先性优先考虑

某个目的约束，随着min系数中d+或者d-增大移动曲线，画出最适当

那条，直到最后

1o.用割平面法解下列整数规划:

maxz=xx+x2

2x,+x<6

(1)2

s,t.<4芭+5尤2420

苞之0,且为整数

解：引进松弛变量七,工4,将问题化为原则形式，用单纯形法解其松弛问题。

Ci1100

0

CBXBbXlX2X3X4

0X36[2]1103

0X42045015

51100

1Xl311/21/206

0X480[3]-218/3

501/2-1/20

1X]5/3105/6-1/6

1X28/301-2/31/3

500-1/6-1/6

找出非整数解变量中分数某些最大一种基变量（x2）,并写下这一行约束:

21仁2

---心—九二2一

~333

将上式中所有常数分写成整数与一种正分数值之和得：

々+11+川+(0+：1卜=(2+:2

33

将上式中分数项移到等式右端，整数项移到等式左端得:

g211

X2-X3-2=-一产一产

得到割平面约束为:

11

一产_产

引入松弛变量七,得割平面方程为：

2

3

♦11000

b

CBXBXlX2X3X4x5

1Xl5/3105/6-1/60

1X28/301-2/31/30

0X5-2/300[-1/3]-1/31

500-1/6-1/60

Oj/ari1/21/2

1X)0100-15/2

1X240101-2

0X320011-3

50000-1