线性规划例题

发布时间：2023-06-04 作者：admin 来源：文学

线性规划例题

2023年2月15日发(作者：工会培训)

习题

2-1判断下列说法是否正确：

（1）任何线性规划问题存在并具有惟一的对偶问题；

（2）对偶问题的对偶问题一定是原问题；

（3）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，

当对偶问题无可行解时，其原问题具有无界解；

（4）若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优

解；

（5）若线性规划问题中的b

，c

值同时发生变化，反映到最终单纯形表中，不会出

现原问题与对偶问题均为非可行解的情况；

（6）应用对偶单纯形法计算时，若单纯形表中某一基变量xi<0，又xi所在行的元素全

部大于或等于零，则可以判断其对偶问题具有无界解。

（7）若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加

5个单位时，相应的目标函数值将增大5k；

（8）已知y

为线性规划的对偶问题的最优解，若y

>0，说明在最优生产计划中第

i种资源已经完全耗尽；若y

=0，说明在最优生产计划中的第i种资源一定有

剩余。

2-2将下述线性规划问题化成标准形式。





















无约束

4321

,0,,

232

142

224

5243max)1(

xxxx

xxxxz



















无约束

321

,0,0

322min2

xxx

xxxz

解：(1)令'''

444

xxx

，增加松弛变量

x，剩余变量

x，则该问题的标准形式如下

所示：

'''

12344

'''

12344

'''

123445

'''

123446

'''

1234456

max34255

422

2214

232

,,,,,,0

zxxxxx

xxxxx

xxxxxx

xxxxxxx























(2)令'zz，'

xx，'''

333

xxx，增加松弛变量

x，则该问题的标准

形式如下所示：

'''''

1233

''''

1233

''''

12334

''''

12334

max2233

..26

,,,,0

zxxxx

xxxx

stxxxxx

xxxxx



















2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基

可行解对应图解法中可行域的哪一顶点。



















825

943

510max1

xxz

















2426

1553

2max2

xxz

解：(1)图解法

最优点为B点，最优解为x1=1,x2=3/2，最优值为35/2。

单纯形表计算过程：

初始单纯形表（对应O点）

z’

RHS

z’1-10-5000

0341099/3

0[5]20188/5

第一次迭代（对应A点）

z’

RHS

+2x

O(0,0)

A(8/5,0)

B(1,3/2)

+4x

z’10-10216

00[14/5]1-3/521/5

21/5/14/5

1012/501/58/5

8/5/4/5

第二次迭代（对应B点，即最优解）

z’

RHS

z’1005/1425/1435/2

5015/14-3/143/2

1010-1/72/71

(2)图解法

最优点为B点，最优解为x1=15/4,x2=3/4，最优值为33/4。

单纯形表计算过程：

初始单纯形表（对应O点）

z’

RHS

z’1-2-1000

035101515/3

0[6]2012424/6

第一次迭代（对应A点）

z’

RHS

z’10-1/301/38

00[4]1-1/233/4

211/301/64

4/1/3

第二次迭代（对应B点，即最优解）

+2x

=24

O(0,0)

A(4,0)

B(15/4,3/4)

+5x

=15















572342

19532

54321

xxxxx



















4321

421

xxxx

xxx

z’

RHS

z’1001/127/2433/4

1011/4-1/83/4

210-1/125/2415/4

2-4已知线性规划问题，写出其对偶问题：

（1）

(2)

解：(1)原问题的对偶问题为：

min1957

210

424

2320

3220

525

































(2)原问题的对偶问题为：

54321

2520202410maxxxxxxz

)5,4,3,2,1(j

4321

6368minxxxxz

)4,3,2,1(j

















无约束

321

,0,0

xxx

kxxx

xxx

1234

124

234

123

1234

max3622

..3

,,,0

yyyy

yyy

styyy

yyy

yyyy





























2-5运用对偶理论求解以下各问题：

（1）已知线性规划问题：

其最优解为

（a）求k的值；

（b）写出并求出其对偶问题的最优解。

解：原问题的对偶问题为：

max46

yky























无约束，

设该对偶问题的三个人工变量为123,,

sss

yyy

，由于原问题的最优解中的

,0xx，则根据互补松弛性，所增加的人工变量130,0

yy

，则：

2yy，

2yky。

另外，原问题的最优值*

123

222(5)02(1)12zxxx

，也

321

22minxxxz

123

5,0,1xxx

为对偶问题的最优值，即：*

4612yy。

结合上述三式可得：

















（2）已知线性规划问题：

其对偶问题的最优解为，。

试根据对偶理论求出原问题的最优解。

解：首先写出原问题的对偶问题如下：

min2020

233

324





























由于该对偶问题的最优解为**

1.2,0.2yy，代入对偶问题的约束条件中可

得

1.61

2.62



























，即对偶问题中的松弛变量1234,0,,0

ssss

yyyy

。则根据互补

松弛性可知，原问题中的决策变量

,xx必为0。

将

,xx=0代入原问题中的约束条件，可得：

4321

432maxxxxxz















0,,,

20232

20322

4321

xxxx

2.1

y2.0

y

2320

3220

xxx











。又因为**

1.2,0.2yy均不为0，则同样根据互补松

弛性可知，12,0

xx。则有：34

2320

3220











。求解该方程组可得：

4,4xx。

（3）已知线性规划问题:



















0,,

max

321

xxx

xxz

试根据对偶问题性质证明上述线性规划问题目标函数值无界。

解：首先写出原问题的对偶问题如下：

min2























，

由于该对偶问题中前两个约束条件所确定的可行域为空集，可知该对偶问题无

解。则根据对偶性质可知，原问题无解可无界。

另外，(0,0,0)x必为原问题的解之一，则可证原问题无界。

2-6已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形

表如表2-44所示，求表中各括弧内未知数的值。

表2-44初始单纯形表及最终单纯形表

RHS

z1-3-2-20000

0111100（b）

0(a)1201015

02(c)100120

：：

RHS

0（k）（g）05/4（j）

95/4

000（d）(l)-1/4-1/45/4

310（e）0

3/4（i）25/4

201（f）0

（h）1/25/2

解：由初始单纯形表中的基变量为

456

,,xxx可知，1B为最终单纯形表中

456

,,xxx所

对应的消耗系数矩阵，即：

11/41/4

03/4

01/2















则有：1

11100

1210

2101

Bae













，可求得：2,3,1/4,5/4,acde

1/2,1/2,1/4fhi。

另外：1

5/4

1525/4

205/2

B











，可求得10b。

再由检验数计算公式1

jBjj

CBpc可求得

3/4,1/4；而基变量

的检验数必为零，所以

0。即0,3/4,1/4kgj。

2-7用对偶单纯形法求解下列线性规划问题。



















0,,

522

18124min1

321

xxx

xxxz

















0,,

10536

423

325min2

321

xxx

xxxz

解：(1)令z，=-z引进松弛变量x

，x

≥0，标准化

123

134

235

12345

max'41218

.225

,,,,0

zxxx

xxx

stxxx

xxxxx



















列出初始单纯形表

z，x

RHS

z，141218000

0-10-310-3

00[-2]-201-5

-12/-2-18/-2

选取x

进基。即选取a

=-2为主元，进行旋转运算，得到以下单纯形表。

z，x

RHS

z，140606-30

0-10[-3]10-3

-120110-1/25/2

-4/-1-6/-3

选取x

出基，a

=-3为主元进行旋转运算。

z，x

RHS

z，120026-36

-181/301-1/301

-12-1/3101/3-1/23/2

当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为

=0，x

=3/2，x

=1，maxz，=-36，即minz=36

(2)令z，=-z引进松弛变量x

，x

≥0，标准化

123

1234

1235

12345

max'523

324

.63510

,,,,0

zxxx

xxxx

stxxxx

xxxxx



















列出初始单纯形表

z，x

RHS

z，1523000

0-3-1-210-4

0-6-3[-5]01-10

-2/-3-3/-5

选取x3进基。即选取a

=-5为主元，进行旋转运算，得到以下单纯形表。

z，x

RHS

z，17/51/5003/5-6

0-3/51/501-2/50

-36/53/510-1/52

当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为

=0，x

=2，maxz，=-6，即minz=6

2-8已知2-45表为求解某线性规划问题的最终单纯形表，表中x

为松弛变量，

问题的约束为≤形式。

表2-45最终单纯形表

RHS

04042

01/211/20

5/2

1-1/20-1/61/3

5/2

（1）写出原线性规划问题；

（2）写出原问题的对偶问题；

（3）直接由原问题的最终单纯形表写出对偶问题的最优解。

解：（1）由于x

为松弛变量，则从表2-45可知，1

1/20

1/61/3

B











。设原问

题模型为：

112233

1111221331

2112222332

123

max

,,0

zcxcxcx

axaxaxb

staxaxaxb

xxx



















则由初始单纯形表和最终单纯形表之间的关系可得：

111213

212233

01/21

11/20

aaa













，则可得到

0a，

1a，

2a，

3a，

1a，

1a。

5/2











，则可得

5b，

10b。

另外，由最终单纯形表中检验数的计算公式可知，

312

ccc



















则可得

6c，

2c，

10c。

综上，原线性规划模型为：

123

max6210

..310

,,0

zxxx

stxxx

xxx



















（2）该模型的对偶问题为：

min510

210























（3）由原问题的最终单纯形表可以得出，单纯形表中的检验数行是对偶问题决

策变量的值。其中，

对应对偶问题松弛变量的值，

对应对偶问题

决策变量的值。则对偶问题的最优解为：

4y，

2y。

2-9已知线性规划问题：

123

max2

.24

,,0

zxxx

xxx

stxx

xxx



















先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。

（1）目标函数变为

321

32maxxxxz

（2）约束右端项由













变为













;

（3）增添一个新的约束条件

xx

。

解：首先用单纯形法得到原问题的最优单纯形表。

RHS

z10312012

2111106

00311110

且可得到，最终单纯形表中1

B









。

（1）由于x

在最优单纯形表中是非基变量，因此只影响它本身的检验数。计

算：

22112522222

()(2103)20zccycyccc

得到

2c时问题的最优解不变。但由于

c由-1变为3，此时必然造成检验数的符

号发生变化，相应的单纯形表如下：

RHS

z10-112012

2111106

00[3]11110

以

a为主元，对该单纯形表进一步迭代可得：

RHS

z1004/37/31/346/3

2102/32/3-1/38/3

3011/31/31/310/3

此时最优解变为

123

8/3,10/3,0xxx。目标函数值变为46/3。

（2）当初始单纯形表中右端常数从(6,4)T变为(3,4)T时，即右端常数第一项减少

3，则最终单纯形表中的右端常数项应为原最终单纯形表中的右端常数与B-1中第一

列与（-3）乘积之和，即：(6,10)T+(-3)*(1,1)T=(6-3,10-3)=(3,7)T。

则可知，最优解变为

123

3,7,0xxx，最优值变为27。

（3）先将原问题最优解变量值代入，因有

-6+0=-6<2，即原问题的最优解不满足新的约束条件。

故将约束条件写成：

-x

两边同乘以-1，得到

-x

=-2

并取x

作为新的基变量，得到新的单纯形表：

RHS

z103120012

21111006

003111010

010-1001-2

消去x

在第三个约束中的系数，使得基变量x

在约束条件中的系数成为单位向量：

RHS

z103120012

21111006

003111010

00-1[-2]-101-2

用对偶单纯形法继续求解，x

离基，x

进基：

RHS

z105/205/301/38

211/201/201/22

005/201/211/26

101/211/20-1/21

新的最优解为（x

）T=（2,0,1,6,0,0）T，maxz=8。

2-10某厂生产A，B，C三种产品，其所需劳动力、材料等有关数据见表2-46。要

求：（1）确定利润最大的产品生产计划；（2）产品A的利润在什么范围内变动时，

上述最优计划不变；（3）如果设计一种新产品D，单件劳动力消耗为8单位，材料

消耗为2单位，每件可获利3元，问该种产品是否值得生产？（4）如果劳动力数量

不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生

产，以购多少为宜。（5）由于某种原因该厂决定暂停A产品的生产，试重新确定该

厂的最优生产计划。

表2-46产品单位利润及资源消耗

消耗定额产品

资源

ABC可用量（单位）

劳动力

材料

635

345

产品利润（元/件）314

解：（1）设生产A,B,C三种产品的件数分别为

123

,,xxx，则依据题意可得问题的线性

规划模型如下：

123

max34

63545

..34530

,,0

zxxx

xxx

stxxx

xxx



















用单纯形法求得该模型的最优单纯形表如下：

RHS

z10201/53/527

31-1/301/3-1/35

4011-1/52/53

即：为使获得利润最大，产品A需生产5件，产品B不生产，产品C生产3

件，此时获得总利润为27元。

（2）设产品A的利润为

c，由于决策变量

x在最优单纯形表中是基变量，此

时

c的变化会带来所有非基变量检验数的变化。为使（1）所求得的最优计划不变，

需要下表中所有非基变量检验数的值均为非负，即：

RHS

z10

0



27

1-1/301/3-1/35

4011-1/52/53

1/34110

1/341/50

1/342/50



















解该不等式组可得：

12/524/5c。即

c在[12/5,24/5]的范围内最优计划不

变。

（3）设计新产品D相当于增加决策变量

x。首先可由（1）中的最优单纯形表

得到1

1/31/3

1/52/5

B













，

(3,4)

C，则由于增加决策变量

x带来最优单纯形

表中

x的检验数为1

66B

CBpc=-1/5，且消耗系数列1

YBp=(2,-4/5)T。则新的

单纯形表为：

RHS

z10201/53/5-1/527

31-1/301/3-1/325

4011-1/52/5-4/53

由于增加决策变量

x后求得的最优单纯形表为：

RHS

z11/1089/3007/3017/30055/2

31/2-1/601/6-1/615/2

42/513/151-1/154/1505

由于生产产品D后带来最优总利润变为55/2>27，即该产品值得生产。

（4）由原问题的最优单纯形表可知，该问题对偶问题的最优解为：

0.2,0.6yy，即劳动力的影子价格为0.2，材料的影子价格为0.6。

而市场上材料的价格仅为0.4。由于影子价格>市场价格，此时可以通过购买材

料进行生产。设从市场上购买个单位的材料，则问题的最优单纯形表变为：

RHS

z10201/53/5

27+



31-1/301/3-1/3



4011-1/52/5



此时当

，即15时，问题的最优解为

123

5,0,3

xxx。但当15时，右端项第一行<0，此时根据对偶

单纯形法，需要x

出基，x

进基，可得x

的检验数为零，即材料的影子价格变为零。

因此，应从市场上购买15个单位的材料。

（5）暂停A产品的生产，相当于删除决策变量

x，对由剩余变量求解，可得

问题的模型变为：

max4

3545

..4530

zxx

stxx



















可求得最优解为：

06xx，，最优值24z。

2-11已知运输问题的供求关系和单位运价表如表2-47所示，试用表上作业法求出问

题的最优解。

（1）表2-47（a）

销地

产地

产量

327650

752360

254525

销量60402015

解：采用Vogel法获得初始基本可行解。

B1B2B3B4

A1327650

1040

7523

252015

2545

60402015

计算该解下各非基变量的检验数，可得：

B1B2B3B4

3276

1040

7523

252015

2545

60402015

的检验数<0，此时应将X

进基，更新解及非基变量的检验数可得：

B1B2B3B4

3276

3515

7523

252015

2545

60402015

可知，该解中非基变量检验数均为非负，为最优解。即A1往B1运35，往B2

运15；A2往B2、B3、B4分别运25、20、15单位；A3往B1运25单位。最优值

为：395。

（2）表2-47（b）

销地

产地

产量

-1

581315100

177129150

销量50706080

解：由于总产量为350，而总销量为260，即产大于销的运输问题。因此，通过增加

一个假想的销地B

，销量为90，运价均为0，使其变为产销平衡的运输问题。问题

更新为：

销地

产地

产量

181417120

100

581315

1771290150

销量5070608090

采用Vogel法获得初始基本可行解，并计算非基变量的检验数如下：

B1B2B3

181417

100

1090

5813

100

5050

17712

150

700

507060

的检验数<0，此时应将X

进基，更新解及非基变量的检验数可得：

B1B2B3

181417

100

5813

100

5050

A317712

0150

-2

7010

507060

可知，该解中非基变量检验数均为非负，为最优解。即A1往B4运10，往B5

运90；A2往B1运50，往B3运50；A3往B2运70，B3运10，B4运70单位。最

优值为：2260。

2-121，2，3三个城市每年需分别供应电力320,250,和350单位，由Ⅰ，II两个电站

提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表2-23所

示。由于需要量大于可供量，决定城市1的供应量可减少0~30单位，城市2的供应

量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案（将可供

电量用完）。

表2-48供应电力单位费用表

城市

电站

123

I151822

II212516

解：建立该问题的表式模型如下：

城市

电站

11’233’供给量

I00

II20

III(虚拟)M0MM070

需求量29

对该运输问题进行求解，可得

11’2

3’

151518

400

150250

II212125

16450

140

270

III

M0M

3040

29030250

270

为该问题的最优解，即I向城市1供电150单位，向2供电250单位；II向城市1

供电140单位，向城市3供电310单位。此时总费用为：14650。

2-13已知某运输问题的运输表及给出的一个最优调运方案分别见表2-49，试确定表

2-49中k的取值范围。

表2-49运输表及最优调运方案

1234

1012011

510

12k920

01015

2141618

5151510

解：计算表中非基变量的检验数，直接标示在表2-49中。

如该表为最优方案，则需：

k-3>=0,k+10>=0,10-k>=0,24-k>=0,18-k>=0。

取前述不等式解的交集，可得k的取值范围为：3<=k<=10。

2-14某糖厂每月最多生产糖270t，先运至A

三个仓库，然后再分别供应

五个地区的需要。已知各仓库的容量分别为50,100,150（t），各地区的需要量分别为

25,105,60,30,70（t）。已知从糖厂经各仓库然后供应各地区的运费和存储费如表2-50

所示。

表2-50运费及存储费

1015202040

2040153030

3035405525

试确定一个使总费用最低的调运方案。（暂时不用考虑本题，待和出题老师核实后再

公布该题答案）

2-15一艘货轮分前、中、后三个舱位，它们的容积与最大允许的载重量如表2-51和

2-52所示，现有三种货物待运，已知有关数据列于表2-27（b）

2-51容积及最大允许的载重量

M-5M-8M

K-3

K+10

10-K

24-K

18-K

项目前舱中舱后舱

最大允许载重量（t）2

容积（m3）4

2-52待运货物单件体积、重量及运价

商品数量（件）每件体积（m3/

件）

每件重量（t/

件）

运价（元/件）

A6001081000

B100056700

C80075600

又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的

比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15%,前后

舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入才最大？试建立这

个问题的线性规划模型。

解：设决策变量

（1,2,3;1,2,）表示由前、中、后舱装载货物A、

B、C的数量，则模型为：

333

123

111

max1000+700600

iii

Pxxx





s.t.

111213

8+6+52000xxx，

212223

8+6+53000xxx，

313233

8+6+51500xxx（船

舱载重量约束）

111213

10+5+74000xxx，

212223

10+5+75400xxx，

313233

10+5+71500xxx（船舱体积约束）

600



，

1000



，

800



（货物数量约束）

0.850



，

1.150



，

0.850



，

1.150



，

0.90



，

1.10



（载重量

比例约束）

2-16一贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月

1日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表

2-53所示。

如买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望

本季末库存为2000担。问：应采取什么样的买进与卖出的策略使3个月总的获利最

大？（列出问题的线性规划模型，不求解）

表2-53各月份的进货单价及出货单价

月份进货价/（元/担）出货价/（元/担）

12.853.10

23.053.25

32.902.95

解：设决策变量

（1,2,3;1,）表示1、2、3月买进、卖出的杂粮担数，

则模型如下：

max3.1+3.25+2.95-2.85-3.05-2.9Pxxxxxx

s.t.

1112

1000+-5000xx，

11122122

1000+-+-5000xxxx，（仓库容量约束）

1000+-+-2000xxxxxx，（季末库存约束）

1112

20000-2.85+3.10xx，

11122122

20000-2.85+3.1-3.05+3.250xxxx，

20000-2.85+3.1-3.05+3.25-2.9+2.950xxxxxx（资金约束）

1000-0x，

111222

1000+--0xxx，

1112212232

1000+-+-0xxxxx（“下月

卖出”约束）

2-17某农户年初承保了40亩土地，并备有生产专用资金25000元。该户劳动力情

况为：春夏季4000工时，秋冬季3500工时。若有闲余工时则将为别的农户帮工，

其收入为：春夏季5元/工时，秋冬季4元/工时。该户承包的地块只是以种植大豆、

玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养

奶牛和鸡。每头奶牛每年需投资4000元，每只鸡需投资30元。每头奶牛需用地1.5

亩种植饲草，并占用劳动力：春夏季50工时、秋冬季100工时，每年净收入4000

元。每只鸡占用劳动力：春夏季0.3工时、秋冬季0.6工时，每年净收入100元。该

农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需

要的劳动力及收入情况见表2-54。问该农户应如何拟定经营方案才能使当年净收入

最大？试建立该问题的数学模型。

表2-54三种农作物需要的劳动力及收入情况

种类

需用工时（工时/亩）

春夏季需工时秋冬季需工时净收入/（元/亩）

大豆2050500

玉米3575800

小麦1040400

解：设决策变量

x表示饲养牛、鸡的头数(1,2i)，决策变量

为种植大豆、玉米

和小麦的亩数(1,2,3j)，则模型如下：

12123

1212312123

max4400

+5(4000-50-0.3-20-35-10)4(3500-100-0.6-50-75-40)

Pxxyyy

xxyyyxxyyy





s.t.

1123

1.5+=40xyyy（土地面积约束）

4000+3025000xx（资金约束）

8x，

300x（鸡舍、牛棚约束）

12123

50-0.3-20-35-104000xxyyy，

12123

100-0.6-50-75-403500xxyyy（劳动力约束）

2-18对某厂I，II，III三种产品下一年各季度的合同预订数如表2-55所示。

表2-55三种产品下一年各季度的合同预订数

产品季度

1234

I1500

II1500

III1500

该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度

生产工时为15000h，生产I，II，III产品每件分别需时2、4、3h。因更换工艺装

备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交

一个季度赔偿20元，产品III赔偿10元；又生产出的产品不在本季度交货的，每件

每季度的库存费用为5元。问该厂应如何安排生产，使总的赔偿加库存费用为最小

（要求建立数学模型，不需求解）。

解：设Xij为第j季度生产的产品i的数量，sij为第j季度末需库存的产品i的数量，

Fij为第j季度末交货的产品i的数量，Rij为第j季度对产品i的预订数，则有































0,,

)3,2,1(

)3,2,1(150

)4,3,2,1(15000342

5)51020(min

321

ijijij

ikijij

ijij

jjj

ijjj

Fsx

iRsFx

iRx

jxxx

sFFFZ

👁️ 阅读量：0

🔖 本文标签：

🔥 最新发布文章