当前位置:文档之家› 第二章 线性规划习题(附答案)

第二章 线性规划习题(附答案)

第二章 线性规划习题(附答案)
第二章 线性规划习题(附答案)

习题

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

(1) 任何线性规划问题存在并具有惟一的对偶问题; (2) 对偶问题的对偶问题一定是原问题;

(3) 根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之,

当对偶问题无可行解时,其原问题具有无界解;

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

解;

(5) 若线性规划问题中的b i ,c j 值同时发生变化,反映到最终单纯形表中,不会出

现原问题与对偶问题均为非可行解的情况; (6) 应用对偶单纯形法计算时,若单纯形表中某一基变量x i <0,又x i 所在行的元素全

部大于或等于零,则可以判断其对偶问题具有无界解。 (7) 若某种资源的影子价格等于k ,在其他条件不变的情况下,当该种资源增加

5个单位时,相应的目标函数值将增大5k ;

(8) 已知y i 为线性规划的对偶问题的最优解,若y i >0,说明在最优生产计划中第

i 种资源已经完全耗尽;若y i =0,说明在最优生产计划中的第i 种资源一定有剩余。

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

???

??

?

?≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()???

??≥≤≤-+-=++-+-=无约束

321

3213213

21,0,06

24

.322min 2x x x x x x x x x st x x x z 解:(1)令'''

444

x x x =-,增加松弛变量5x ,剩余变量6x ,则该问题的标准形式如下所示:

'''

12344'''

12344'''

123445'''

123446'''1234456max 342554222214..232

,,,,,,0

z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-?-+-+-=?+-+-+=??-++-+-=??≥? (2)令'

z z =-,'11x x =-,'''

333x x x =-,增加松弛变量4x ,则该问题的标准

形式如下所示:

'''''

1233''''

1233''''

12334''''12334

max 22334

..26,,,,0z x x x x x x x x s t x x x x x x x x x x =+-+?++-=?+-++=??≥? 2-3分别用图解法和单纯形法求解下述线性规划问题,并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

()???

??≥≤+≤++=0,825943.510max 12

1212121x x x x x x st x x z ()???

??≥≤+≤++=0,242615

53.2max 22

121212

1x x x x x x st x x z 解:(1)图解法

最优点为B 点,最优解为x1=1,x2=3/2,最优值为35/2。 单纯形表计算过程:

初始单纯形表(对应O 点)

z ’ x

x x x RHS z ’ x 3 9/3 x 4 8/5 第一次迭代(对应A 点)

z ’ x

x x x RHS z ’

x 3 /14/5

x 1

8/5/4/5

●第二次迭代(对应B 点,即最优解)

z ’ x 1 x 2 x 3 x 4 RHS z ’

x 2 x 1

(2)图解法

最优点为B 点,最优解为x1=15/4,x2=3/4,最优值为33/4。 单纯形表计算过程:

初始单纯形表(对应O 点)

z ’ x

x x x RHS z ’ x 3 15/3 x 4 24/6

第一次迭代(对应A 点)

z ’ x

x x x RHS z ’ x 3 3/4 x 1 4/1/3 ●第二次迭代(对应B 点,即最优解)

z ’

x x x x

RHS

z ’

x 2 x 1

??

?

??≥≤++++≤++++057234219

532..5432154321j x x x x x x x x x x x t s ???????

??≥≥+≥+≥+++≥++022633

2..31434321421j x x x x x x x x x x x x t s 2-4已知线性规划问题,写出其对偶问题:

(1)

(2)

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

12121

21

2121212min 1957210424

2320..3220525,0

y y y y y y y y s t y y y y y y ω=++≥??+≥??+≥??+≥??+≥?≥??

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

123412412234123

1234max 36223826

..36

,,,0

y y y y y y y y y s t y y y y y y y y y y ω=+++++≤??+≤??++≤??++≤?≥??

2-5运用对偶理论求解以下各问题: (1)已知线性规划问题: 543212*********max x x x x x z ++++=)5,4,3,2,1(=j 43216368min x x x x z +++=)4,3,2,1(=j 3

2

1

22min x

x x z +-=

?????≥≤≤-+-=++-无约束321

321321,0,06

4..x x x kx x x x x x t s

其最优解为 (a )求k 的值;

(b )写出并求出其对偶问题的最优解。 解:原问题的对偶问题为:

12

121

21212max 4621..20

y y y y y y s t y ky y y ω=+--≥??+≤-??-=??≤?无约束,

设该对偶问题的三个人工变量为123,,s s s y y y ,由于原问题的最优解中的

13,0x x ≠,则根据互补松弛性,所增加的人工变量130,0s s y y ==,则:

122y y --=,122y ky -=。

另外,原问题的最优值*123222(5)02(1)12z x x x =-+=?--+?-=-,也

为对偶问题的最优值,即:*124612y y ω=+=-。

结合上述三式可得:

*1*

20

21y y k ?=?=-??=?

(2)已知线性规划问题:

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

1235,0,1x x x =-==-4

321432max x x x x z +++=?????≥≤+++≤+++0

,,,20

23220322..4

32143214321x x x x x x x x x x x x t s 2.11=y 2.02=y

试根据对偶理论求出原问题的最优解。 解:首先写出原问题的对偶问题如下:

1212121212

12min 20202122

..233324

,0

y y y y y y s t y y y y y y ω=++≥??+≥??+≥??+≥?≥??

由于该对偶问题的最优解为**121.2,0.2y y ==,代入对偶问题的约束条件中可

121.61

2.62..3344,0

s t y y >??>??=??=?≥??,即对偶问题中的松弛变量1234,0,,0s s s s y y y y ≠=。则根据互补松弛性可知,原问题中的决策变量12,x x 必为0。

将12,x x =0代入原问题中的约束条件,可得:

1

342

3

423203220s s x x x x x x ?++=?++=?。又因为**

121.2,0.2y y ==均不为0,则同样根据互补松弛性可知,1

2,0s

s

x x =。则有:343

423203220x x x x +=??+=?。求解该方程组可得:344,4x x ==。

(3)已知线性规划问题:

???

??≥≤-+-≤++-+=0,,12

.max 3

213213212

1x x x x x x x x x st x x z 试根据对偶问题性质证明上述线性规划问题目标函数值无界。 解:首先写出原问题的对偶问题如下:

121212

1212min 211..00

y y y y y y s t y y y y ω=+--≥??+≥??-≥??≥?, 由于该对偶问题中前两个约束条件所确定的可行域为空集,可知该对偶问题无

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

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

2-6已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-44所示,求表中各括弧内未知数的值。

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

z x 4 x 5 x 6 ::

z x 4 x 1 x 2

解:由初始单纯形表中的基变量为456,,x x x 可知,

1

B -为最终单纯形表中456,,x x x 所对应的消耗系数矩阵,即:

111/41/403/401/2B i h ---??

?= ? ???

则有:11110012102101d B a e c f -????

? ?= ? ? ? ?????,可求得:2,3,1/4,5/4,a c d e ====

1/2,1/2,1/4f h i =-=-=-。

另外:15/41525/4205/2b B -????

? ?= ? ? ? ?????

,可求得10b =。 再由检验数计算公式1j B j j C B p c σ-=-可求得363/4,1/4σσ==;而基变量的检验数必为零,所以20σ=。即0,3/4,1/4k g j ===。 2-7用对偶单纯形法求解下列线性规划问题。

()???

??≥≥+≥+++=0,,5223

3.18124min 13

213231321x x x x x x x st x x x z ()???

??≥≥++≥++++=0,,10536423.325min 23

213213213

21x x x x x x x x x st x x x z

解:(1) 令z ,

=- z 引进松弛变量x 4,x 5≥0,标准化

123

134********

max '4121832.225,,,,0z x x x x x x st x x x x x x x x =---+-=??

++=??≥?

列出初始单纯形表

z ,

x 4x 5

-12/-2

-18/-2 选取x 2进基。即选取a 22=-2为主元,进行旋转运算,得到以下单纯形表。

z ,

x 4x 2

-4/-1

-6/-3

选取x 4出基,a 13=-3为主元进行旋转运算。

z ,

x 3x 2当前基既是原始可行基,又是对偶可行基,因而是最优基。最优解为

x 1=0,x 2=3/2,x 3=1,max z ,

=-36,即min z=36

(2) 令z ,

=- z 引进松弛变量x 4,x 5≥0,标准化

1231234123512345

max '523324

.63510,,,,0z x x x x x x x st x x x x x x x x x =---++-=??

++-=??≥? 列出初始单纯形表

z ,

x 4x 5

-2/-3

-3/-5

选取x3进基。即选取a 23=-5为主元,进行旋转运算,得到以下单纯形表。

z ,

x 4x 3当前基既是原始可行基,又是对偶可行基,因而是最优基。最优解为 x 1=0,x 2=0,x 3=2,max z ,

=-6,即min z=6

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

x 4 , x 5为松弛变量,问题的约束为≤形式。

表2-45 最终单纯形表

z X 3 X 1

(1)写出原线性规划问题; (2)写出原问题的对偶问题;

(3)直接由原问题的最终单纯形表写出对偶问题的最优解。 解:(1)由于x 4 , x 5为松弛变量,则从表2-45可知,11/2

01/61/3B -??= ?-??

。设原问

题模型为:

112233

1111221331

2112222332

123

max ..,,0z c x c x c x a x a x a x b s t a x a x a x b x x x =++++≤??

++≤??≥? 则由初始单纯形表和最终单纯形表之间的关系可得:

1112

131********/2111/20a

a a B a a a -????

= ? ?-??

??,则可得到110a =,121a =,132a =,213a =,221a =-,231a =。

1125/25/2b B b -????

= ? ??

???,则可得15b =,210b =。

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

312311114221

14

261

23c c c c c c ?--=??

?-=???=??

则可得16c =,22c =-,310c =。 综上,原线性规划模型为:

12323123123

max 621025..310,,0z x x x x x s t x x x x x x =-++≤??-+≤??≥?

(2)该模型的对偶问题为:

12212

1212min 51036

2..210,0

y y y y y s t y y y y ω=+≥??-≥-??+≥??≥?

(3)由原问题的最终单纯形表可以得出,单纯形表中的检验数行是对偶问题决策变量的值。其中,13σσ:

对应对偶问题松弛变量的值,45σσ:对应对偶问题

决策变量的值。则对偶问题的最优解为:14y =,22y =。

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

先用单纯形法求出最优解,再分析在下列条件单独变化的情况下最优解的变化。 (1)目标函数变为32132max x x x z ++= (2)约束右端项由????

??46变为???

? ??43;

(3)增添一个新的约束条件231≥+-x x 。 解:首先用单纯形法得到原问题的最优单纯形表。

z x 1

x 5

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

1110B -??

= ???

(1)由于x 2在最优单纯形表中是非基变量,因此只影响它本身的检验数。计

123

12312123

max 26.24,,0z x x x x x x st x x x x x =-+++≤??

-+≤??≥?

算:

22112522222()(2103)20z c c y c y c c c -=+-=?+?-=-≥

得到22c ≤时问题的最优解不变。但由于2c 由-1变为3,此时必然造成检验数的符号发生变化,相应的单纯形表如下:

z x 1 x 5

以22a 为主元,对该单纯形表进一步迭代可得:

z x 1 x 2

此时最优解变为1238/3,10/3,0x x x ===。目标函数值变为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 。

则可知,最优解变为1233,7,0x x x ===,最优值变为27。 (3)先将原问题最优解变量值代入,因有

-6+0=-6< 2 ,即原问题的最优解不满足新的约束条件。 故将约束条件写成: -x 1+x 3-x 6=2 两边同乘以-1,得到

x 1-x 3+x 6=-2

并取x 6作为新的基变量,得到新的单纯形表:

z x 1 x 5

x6

消去x1在第三个约束中的系数,使得基变量x1在约束条件中的系数成为单位向量:

z

x1

x4

x5

用对偶单纯形法继续求解,x6离基,x3进基:

z

x1

x4

x3

新的最优解为(x1,x2,x3,x4,x5,x6)T=(2,0,1,6,0,0)T,max z=8。

2-10某厂生产A,B,C三种产品,其所需劳动力、材料等有关数据见表2-46。要求:(1)确定利润最大的产品生产计划;(2)产品A的利润在什么范围内变动时,上述最优计划不变;(3)如果设计一种新产品D,单件劳动力消耗为8单位,材料消耗为2单位,每件可获利3元,问该种产品是否值得生产?(4)如果劳动力数量不增,材料不足时可从市场购买,每单位0.4元。问该厂要不要购进原材料扩大生产,以购多少为宜。(5)由于某种原因该厂决定暂停A产品的生产,试重新确定该厂的最优生产计划。

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

123

规划模型如下:

123

123123123

max 3463545

..34530,,0z x x x x x x s t x x x x x x =++++≤??

++≤??≥? 用单纯形法求得该模型的最优单纯形表如下:

z x 1

x 3 C 生产3件,此时获得总利润为27元。

(2)设产品A 的利润为1c ,由于决策变量1x 在最优单纯形表中是基变量,此

时1c 的变化会带来所有非基变量检验数的变化。为使(1)所求得的最优计划不变,需要下表中所有非基变量检验数的值均为非负,即:

z x 1 x 3

21415

11/341101/341/501/342/50

c c c σσσ=-?+?-≥??

=?-?≥??=-?+?≥?

解该不等式组可得:112/524/5c ≤≤。即1c 在[12/5,24/5]的范围内最优计划不

变。

(3)设计新产品D 相当于增加决策变量6x 。首先可由(1)中的最优单纯形表

得到1

1/31/31/52/5B

--??

= ?-??

,(3,4)B C =,则由于增加决策变量6x 带来最优单纯形表中6x 的检验数为1

66B C B p c --=-1/5,且消耗系数列1

66Y B p -==(2,-4/5)T 。则新的

单纯形表为:

z x 1 x 3

由于增加决策变量6x 后求得的最优单纯形表为:

z x 6

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

(4)由原问题的最优单纯形表可知,该问题对偶问题的最优解为:

120.2,0.6y y ==,即劳动力的影子价格为0.2,材料的影子价格为0.6。

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

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

z x 1 x 3

此时当503

ξ-≥,即15ξ≤时,问题的最优解为

12312

5,0,335

x x x ξξ=-==+。但当15ξ>时,右端项第一行<0,此时根据对偶

单纯形法,需要x 1出基,x 5进基,可得x 5的检验数为零,即材料的影子价格变为零。

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

(5)暂停A 产品的生产,相当于删除决策变量1x ,对由剩余变量求解,可得

问题的模型变为:

23232323

max 43545

..4530,0z x x x x s t x x x x =++≤??

+≤??≥? 可求得最优解为:2306x x ==,,最优值24z =。

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

解:采用V ogel 法获得初始基本可行解。

A1 50 A2 60 A3 25 60

40

20

15

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

A1 50 A2 60 A3 25

60

40

20

15

X 22的检验数<0,此时应将X 22进基,更新解及非基变量的检验数可得:

A1 50 A2 60 A3 25

60

40

20

15

可知,该解中非基变量检验数均为非负,为最优解。即A1往B1运35,往B2运15;A2往B2、B3、B4分别运25、20、15单位;A3往B1运25单位。最优值为:395。

解:由于总产量为350,而总销量为260,即产大于销的运输问题。因此,通过增加一个假想的销地B 5,销量为90,运价均为0,使其变为产销平衡的运输问题。问题更新为:

采用V ogel 法获得初始基本可行解,并计算非基变量的检验数如下:

A1

100

A2 100

A3 150

50 70 60 80 90

X14的检验数<0,此时应将X14进基,更新解及非基变量的检验数可得:

B4

A1 100

A2 100

A3 150

50 70 60 80 90

可知,该解中非基变量检验数均为非负,为最优解。即A1往B4运10,往B5运90;A2往B1运50,往B3运50;A3往B2运70,B3运10,B4运70单位。最优值为:2260。

2-12 1,2,3三个城市每年需分别供应电力320,250,和350单位,由Ⅰ,II两个电站提供,它们的最大可供电量分别为400个单位和450个单位,单位费用如表2-23所示。由于需要量大于可供量,决定城市1的供应量可减少0~30单位,城市2的供应量不变,城市3的供应量不能少于270单位,试求总费用最低的分配方案(将可供电量用完)。

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

1 1’

2

3 3’

I

400

II 450

III 70

290 30 250 270 80

为该问题的最优解,即I向城市1供电150单位,向2供电250单位;II向城市1供电140单位,向城市3供电310单位。此时总费用为:14650。

2-13已知某运输问题的运输表及给出的一个最优调运方案分别见表2-49,试确定表2-49中k的取值范围。

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

1 15

2 25

3 5

5 15 15 10

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

如该表为最优方案,则需:

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

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

2-14某糖厂每月最多生产糖270 t ,先运至A 1A 2A 3三个仓库,然后再分别供应 五个地区的需要。已知各仓库的容量分别为50,100,150(t ),各地区的需要量分别为25,105,60,30,70(t )。已知从糖厂经各仓库然后供应各地区的运费和存储费如表2-50所示。

公布该题答案)

2-15一艘货轮分前、中、后三个舱位,它们的容积与最大允许的载重量如表2-51和2-52所示,现有三种货物待运,已知有关数据列于表2-27(b )

又为了航运安全,前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求:前、后舱分别与中舱之间载重量比例的偏差不超过15%,前后舱之间不超过10%。问该货轮应装载A 、B 、C 各多少件运费收入才最大?试建立这个问题的线性规划模型。

解:设决策变量ij x (1,2,3;1,2,3.i j ==)表示由前、中、后舱装载货物A 、

B 、

C 的数量,则模型为:

333

1231

1

1

max 1000+700600i i i i i i P x x x ====+∑∑∑

s.t.

1112138+6+52000x x x ≤,2122238+6+53000x x x ≤,3132338+6+51500x x x ≤(船

128499-管理运筹学-第二章线性规划-习题

11(2),12,14,18 习题 2-1 判断下列说法是否正确: (1) 任何线性规划问题存在并具有惟一的对偶问题; T (2) 对偶问题的对偶问题一定是原问题;T (3) 根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之, 当对偶问题无可行解时,其原问题具有无界解;F (4) 若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无穷多最优 解; (5) 若线性规划问题中的b i ,c j 值同时发生变化,反映到最终单纯形表中,不会出 现原问题与对偶问题均为非可行解的情况; (6) 应用对偶单纯形法计算时,若单纯形表中某一基变量x i <0,又x i 所在行的元素全 部大于或等于零,则可以判断其对偶问题具有无界解。 (7) 若某种资源的影子价格等于k ,在其他条件不变的情况下,当该种资源增加 5个单位时,相应的目标函数值将增大5k ; (8) 已知y i 为线性规划的对偶问题的最优解,若y i >0,说明在最优生产计划中第 i 种资源已经完全耗尽;若y i =0,说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z 2-3分别用图解法和单纯形法求解下述线性规划问题,并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题,写出其对偶问题: 5 43212520202410max x x x x x z ++++=

线性规划经典例题及详细解析

一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值就是 。 3. 已知变量x,y 满足约束条件+201-70x y x x y -≤??≥??+≤? ,则 y x 的取值范围就是( )、 A 、 [95,6] B 、(-∞,95 ]∪[6,+∞) C 、(-∞,3]∪[6,+∞) D 、 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 与y 须满足约束条件?? ???≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大值 就是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件1422x y x y ≤+≤??-≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥??-+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的值为( ) A. -3 B 、 3 C 、 -1 D 、 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥??+-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B 、 1 C 、 5 D 、 无穷大

线性规划典型例题

例1:生产计划问题 某工厂明年根据合同,每个季度末向销售公司提供产品,有关信息如下表。若当季生产的产品过多,季末有积余,则一个季度每积压一吨产品需支付存贮费O.2万元。现该厂考虑明年的最佳生产方案,使该厂在完成合同的情况下,全年的生产费用最低。试建立模型。 解: 法1 设每个季度分别生产x1,x2,x3,x4 则要满足每个季度的需求x4≥26 x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 考虑到每个季度的生产能力 0≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10 每个季度的费用为:此季度生产费用+上季度储存费用 第一季度15.0x1 第二季度14 x2 0.2(x1-20) 第三季度15.3x3+0.2(x1+ x2-40) 第四季度14.8x4+0.2(x1+ x2+ x3-70)

工厂一年的费用即为这四个季度费用之和, 得目标函数;minf=15.6 x1+14.4 x2+15.5 x3+14.8 x4-26 s.t.x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 20≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10。 法2:设第i季度生产而用于第j季度末交货的产品数量为xij吨 根据合同要求有: xll=20 x12+x22=20 x13+x23+x33=30 x14+x24+x34+x44=10 又根据每季度的生产能力有: xll+x12+x13+x14≤30 x22+x23+x24≤40 x33+x34≤20 x44≤10 第i季度生产的用于第j季度交货的每吨产品的费用cij=dj+0.2(j-i),于是,有线性规划模型。 minf=15.Oxll+15.2x12+15.4xl3+15.6xl4+14x22+14.2x23+14.4x24+15.3 x33+15.5x34+14.8x44 s.t. xll=20, x12+x22=20, x13+x23+x13=30, x14+x24+x34+x44=10, x1l+x12+x13+x14≤30, x22+x23+x24≤40, x33+x34≤20,

线性规划题及答案

线性规划题型及解法 一、已知线性约束条件,探求线性目标关系最值问题 2x -y _2 例1、设变量x、y满足约束条件x 一y _ _1,则z =2x ? 3y的最大值为__________ 。 x y _1 二、已知线性约束条件,探求非线性目标关系最值问题 \ >1, 例2、已知」x-y+1兰0,则x2+y2的最小值是_」“(x-1)2+(y+2『”值域? 2x - y - 2 <0 三、约束条件设计参数形式,考查目标函数最值范围问题。 Zf x _0 例3、在约束条件y_0 下,当3乞s乞5时,目标函数Z=3x?2y的最大值的变化范围是() |y x _s y 2x^4 A. [6,15] B. [7,15] C. [6,8] D. [7,8] 四、已知平面区域,逆向考查约束条件。 例4、已知双曲线x2-y2 =4的两条渐近线与直线x=3围成一个三角形区域,表示该区域的不等式组是() fx-yZ0 「x-yX0 『x-y^0 "x-y 兰0 (A) x y _ 0 (B) x y 乞0 (C) x y 乞0 (D) x y _ 0 0 _x _3 0 _x _3 0 _x _3 0 _x _3 五、已知最优解成立条件,探求目标函数参数范围问题。 (1 ::: x :「v ‘::4 例5已知变量x,y满足约束条件若目标函数ax y (其中a 0)仅在 [―2 兰x—y 兰2 点(3,1)处取得最大值,则a的取值范围为 __________ 。 六、设计线性规划,探求平面区域的面积问题 丄x y _ 2 _ 0 _ 例6在平面直角坐标系中,不等式组x_y,2_0表示的平面区域的面积是()(A)4、、2 (B)4 [八0 (C) 2.2 (D)2 七、研究线性规划中的整点最优解问题 ”5x-11y —22, 例7、某公司招收男职员x名,女职员y名,x和y须满足约束条件<2x+3yX9, 则 、2x 兰11. z =10x 10y 的最大值是(A)80 (B) 85 (C) 90 (D)95 八、比值问题 当目标函数形如z =-—a时,可把z看作是动点P x, y与定点Q b, a连线的斜率,这样目 x —b 标函数的最值就转化为PQ连线斜率的最值。 x—y+ 2W 0,V

六种经典线性规划例题

线性规划常见题型及解法 求线性目标函数的取值范围 2 2 2 x y A D y 2 O x x=2 求可行域的面积 y y M 5 2 x y 2 y x y 2 x y 2 x y x (3,5] y =2 ( 13 例1 x+2y 时 6 的点 C 、 x , 个 y 6 y 3 2 x + y —3 = 0 C 、 5 A 、 4 B 、 1 D 、无穷大 () 0,将 有 最小值 故选A .B A --- 作出可行域如右图 点个数为13个,选D x + y =2 则z=x+2y 的取值范围是 () 旦y =2 0 0表示的平面区域的面积为 三、求可行域中整点个数 解:|x| + |y| <2等价于 解:如图,作出可行域,作直线I : I 向右上方平移,过点A ( 2,0 ) 2,过点B ( 2,2 )时,有最大值 [2,6] B 、[2 ,5] C 、[3,6] 解:如图,作出可行域,△ ABC 的面积即为所求,由梯形OMBC 的面积减去梯形OMAC 的 面积即可,选B 例 3、满足 |x| + |y| <2 A 、9 个 B 、10 个 由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性 目标函数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 (x 0,y 0) (x 0,y p 0) (xp 0,y 0) (xp 0,y p 0) 是正方形内部(包括边界),容易得到整 y)中整点(横纵坐标都是整数)有() D 、 14 个 2x 例2、不等式组x x 若x 、y 满足约束条件 y O C V —? x 2x + y —6= 0

线性规划习题附答案模板

习题 2-1 判断下列说法是否正确: (1)任何线性规划问题存在并具有惟一的对偶问题; (2)对偶问题的对偶问题一定是原问题; (3)根据对偶问题的性质, 当原问题为无界解时, 其对偶问题无可行解, 反之, 当对偶问题无可行解时, 其原问题具有无界解; (4)若线性规划的原问题有无穷多最优解, 则其对偶问题也一定具有无穷多最优解; (5)若线性规划问题中的b i, c j值同时发生变化, 反映到最终单纯形表中, 不会出现原问题与对偶问题均为非可行解的情况; (6)应用对偶单纯形法计算时, 若单纯形表中某一基变量x i<0, 又x i所在行的元素全部大于或等于零, 则能够判断其对偶问题具有无界解。 (7)若某种资源的影子价格等于k, 在其它条件不变的情况下, 当该种资源增加5个单位时, 相应的目标函数值将增大5k;

(8) 已知y i 为线性规划的对偶问题的最优解, 若y i >0, 说明在最优生产计划中第i 种资源已经完全耗尽; 若y i =0, 说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()??? ??≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 解: (1)令'''444x x x =-, 增加松弛变量5x , 剩余变量6x , 则该问题的标准形式如下所示: ''' 12344''' 12344''' 123445''' 123446'''1234456max 342554222214..232 ,,,,,,0 z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-?-+-+-=?+-+-+=??-++-+-=??≥? (2)令'z z =-, '11x x =-, '''333x x x =-, 增加松弛变量4x , 则该问题的标准形式如下所示: ''''' 1233'''' 1233'''' 12334''''12334 max 22334 ..26,,,,0z x x x x x x x x s t x x x x x x x x x x =+-+?++-=?+-++=??≥? 2-3分别用图解法和单纯形法求解下述线性规划问题, 并对照

八种 经典线性规划例题(超实用)

线性规划常见题型及解法 由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 2 2 2 x y x y ≤ ? ? ≤ ? ?+≥ ? ,则z=x+2y的取值范围是() A、[2,6] B、[2,5] C、[3,6] D、(3,5] 解:如图,作出可行域,作直线l:x+2y=0,将l向右上方平移,过点A(2,0)时,有最小值2,过点B(2,2)时,有最大值6,故选 A 二、求可行域的面积 例2、不等式组 260 30 2 x y x y y +-≥ ? ? +-≤ ? ?≤ ? 表示的平面区域的面积为() A、4 B、1 C、5 D、无穷大 解:如图,作出可行域,△ABC的面积即为所求,由梯形OMBC 的面积减去梯形OMAC的面积即可,选 B 三、求可行域中整点个数 例3、满足|x|+|y|≤2的点(x,y)中整点(横纵坐标都是整数)有() A、9个 B、10个 C、13个 D、14个 解:|x|+|y|≤2等价于 2(0,0) 2(0,0) 2(0,0) 2(0,0) x y x y x y x y x y x y x y x y +≤≥≥ ? ?-≤≥ ? ? -+≤≥? ?--≤ ? 作出可行域如右图,是正方形内部(包括边界),容易得到整点个数为13个,选 D

四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 5 50 3 x y x y x +≥ ? ? -+≤ ? ?≤ ? ,使z=x+ay(a>0) 取得最小值的最优解有无数个,则a的值为() A、-3 B、3 C、-1 D、1 解:如图,作出可行域,作直线l:x+ay=0,要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个,则将l向右上方平移后与直线x+y=5重合,故a=1,选 D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 220 240 330 x y x y x y +-≥ ? ? -+≥ ? ?--≤ ? ,则z=x2+y2的最大值和最小值分别是() A、13,1 B、13,2 C、13,4 5 D 、 解:如图,作出可行域,x2+y2是点(x,y)到原点的距离的平方,故最大值为点A(2,3)到原点的距离的平方,即|AO|2=13,最小值为原点到直线2x+y-2=0的距离的平方, 即为4 5 ,选 C 六、求约束条件中参数的取值范围 例6、已知|2x-y+m|<3表示的平面区域包含点(0,0)和(-1,1),则m的取值范围是() A、(-3,6) B、(0,6) C、(0,3) D、(-3,3) 解:|2x-y+m|<3等价于 230 230 x y m x y m -++>? ? -+- ? ? -< ? ,故0<m<3,选 C

(完整版)简单的线性规划问题(附答案)

简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法,并能应用它解决一些简单的实际问题. 知识点一线性规划中的基本概念 知识点二线性规划问题 1.目标函数的最值 线性目标函数 z=ax+by (b≠0)对应的斜截式直线方程是 y=-a x+z,在 y 轴上的 截距是z, b b b 当 z 变化时,方程表示一组互相平行的直线. 当 b>0,截距最大时, z 取得最大值,截距最小时, z 取得最小值; 当 b<0,截距最大时, z 取得最小值,截距最小时, z 取得最大值. 2.解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下,解决简单线性规划问题的步骤可以概括为:“画、移、求、答”四步,即, (1)画:根据线性约束条件,在平面直角坐标系中,把可行域表示的平面图形准确地画出来,可行域可以是封闭的多边形,也可以是一侧开放的无限大的平面区域.(2)移:运用数形结合的思想,把目标函数表示的直线平行移动,最先通过或最后通过的顶点 (或边界 )便是最优解. (3)求:解方程组求最优解,进而求出目标函数的最大值或最小值. (4)答:写出答案.

知识点三简单线性规划问题的实际应用 1.线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源,问怎样运用这些资源,使完成的任务量最大,收到的效益最大; (2)给定一项任务,问怎样统筹安排,使完成这项任务耗费的人力、物力资源量最小.常见问题有: ①物资调动问题例如,已知两煤矿每年的产量,煤需经两个车站运往外地,两个车站的运输能力是有限的,且已知两煤矿运往两个车站的运输价格,煤矿应怎样编制调动方案,才能使总运费最小? ②产品安排问题例如,某工厂生产甲、乙两种产品,每生产一个单位的甲种或乙种产品需要的A、B、C 三种 材料的数量,此厂每月所能提供的三种材料的限额都是已知的,这个工厂在每个月中应如何安排这两种产品的生产,才能使每月获得的总利润最大? ③下料问题例如,要把一批长钢管截成两种规格的钢管,应怎样下料能使损耗最小?2.解答线性规划实际应用题的步骤 (1)模型建立:正确理解题意,将一般文字语言转化为数学语言,进而建立数学模型,这需要在学习有关例题解答时,仔细体会范例给出的模型建立方法. (2)模型求解:画出可行域,并结合所建立的目标函数的特点,选定可行域中的特殊点作为最优解. (3)模型应用:将求解出来的结论反馈到具体的实例中,设计出最佳的方案. 题型一求线性目标函数的最值 y≤2, 例 1 已知变量 x,y 满足约束条件 x+y≥1,则 z=3x+y 的最大值为 ( ) x-y≤1, A . 12 B .11 C .3 D .- 1 答案 B 解析首先画出可行域,建立在可行域的基础上,分析最值点,然后通过解方程组得最值点 的坐标,代入即可.如图中的阴影部分,即为约束条件对应的可行域,当直线y=-3x+z 经 y=2,x= 3,

高考全国卷及各省数学线性规划真题附答案.docx

2017 高考全国卷及自主招生数学高考真题 线性规划专题真题整理(附答案解析) x 3y 3, 1. ( 17 全国卷 I ,文数 )设 x ,y 满足约束条件 x y 1, 则 z=x+y 的最大值为( ) 7 y 0, A . 0 B . 1 C .2 D .3 答案: D 解析:如图,由图易知当目标函数 z x y 经过 直线 x 3 y 3 和 y 0 (即 x 轴)的交点 A(3,0) 时, z 能取到最大值,把 A(3,0) 代入 z=x+y 可得 z max 3 0 3 ,故选 D. x 2 y 1 2.(17 全国卷 I, 理数 14 题)设 x ,y 满足约束条件 2x y 1,则 z 3x 2 y 的最小值 x y 0 为 答案: 5 x 2 y 1 解析:不等式组 2x y 1 表示的平面区域如图所示。 x y 0 由 z 3x 2 y 变形得 y 3 x z 。要求 z 的最小值, 2 2 即求直线 y 3 x z 的纵截距的最大值。由右图,易知 2 2 当直线 y 3 x z 过图中点 A 时,纵截距最大。 2 2 联立方程组 2 x y 1 ,此时 z 3(1) 2 1 5 。 x 2 y 1 ,解得 A 点坐标为 ( 1,1) 故 z 3x 2 y 的最小值是 -5.

2x+3y 30 3. (17 全国卷Ⅱ,文数 7、理数 5)设 x、y 满足约束条件2x 3 y 3 0 .则z2x y的 y 30 最小值是() A.-15 C.1D9 答案: A 2x+3y 30 解析:不等式组2x 3y 30 表示的可行域如图所示, y30 易知当直线z 2x y 过到y 2 x 1与 y 3 交点 3 6 ,3 时,目标函数 z2x y 取到最小值,此时有 z min 26315 ,故所求z 最小值为15. )设,满足约束条件 3x 2 y60 的取值范围是 4. (17 全国卷Ⅲ,文数 5 x0,则 z=x-y x y y0 () A.[-3,0] B.[-3,2] C.[0,2] D.[0,3] 答案: B 解析:绘制不等式组表示的可行域,结合目标函数 的几何意义可得目标函数z x y 在直线3x 2y 60 与= - 直线 x0 (即x 轴)的交点A0,3处取得最小值, 此时 z min0 3 3。在点B2,0处取得最大值,此时 z max 2 0 2 . 故本题选择 B 选项 . 5.(17 全国卷Ⅲ,理数13)若 x,y 满足约束条件x y 0 x y 2 0 则z3x 4 y 的最小值为y 0 ________.

高中数学线性规划经典题型

高考线性规划归类解析 一、平面区域和约束条件对应关系。 例1、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是() (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥?? +≤??≤≤? (C) 003x y x y x -≤?? +≤??≤≤? (D) 0003x y x y x -≤?? +≥??≤≤? 解析:双曲线224x y -=的两条渐近线方程为y x =±,与直线3x =围 成一个三角形区域(如图4所示)时有0 003x y x y x -≥?? +≥??≤≤? 。 点评:本题考查双曲线的渐近线方程以及线性规划问题。验证法或排除法是最效的方法。 例2:在平面直角坐标系中,不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是() (A)42 (B)4 (C) 22 (D)2 解析:如图6,作出可行域,易知不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域是一个三角形。容 易求三角形的三个顶点坐标为A(0,2),B(2,0),C(-2,0).于是三角形的面积为: 11 ||||42 4.22 S BC AO =?=??=从而选B。 点评:有关平面区域的面积问题,首先作出可行域,探求平面区域图形的性质;其次利用面积公式整体或部分求解是关键。 二、已知线性约束条件,探求线性截距——加减的形式(非线性距离——平方的形式,斜率——商的形式)目标关系最值问题(重点) 例3、设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则 ①y x 32+的最大值为 。(截距) 解析:如图1,画出可行域,得在直线 2x-y=2与直线x-y=-1 的交点A(3,4)处,目标函数z 最大值为18 点评:本题主要考查线性规划问题,由线性约束条件画出可行域,然后求出目标函数的最大值.,是一道较为简单的送分题。数形结合是数学思想的重要手段之一。 ②则2 2 x y +的最小值是 . ③1y x =+的取值范围是 . 图1

线性规划经典例题及详细解析

1 / 6 一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22 x y +的最小值是 。 3. 已知变量x ,y 满足约束条件+201-70x y x x y -≤?? ≥??+≤? ,则 错误! 的取值范围是( )。 A 。 [错误!,6] B.(-∞,错误!]∪[6,+∞) C.(-∞,3]∪[6,+∞) D 。 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 和y 须满足约束条件?? ? ??≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大 值是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件14 22x y x y ≤+≤?? -≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处 取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的 值为( ) A. -3 B. 3 C 。 -1 D. 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B. 1 C. 5 D 。 无穷大

线性规划经典例题

线性规划常见题型及解法 由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、 若x 、y 满足约束条件222x y x y ≤?? ≤??+≥? ,则z=x+2y 的取值范围是 ( ) A 、[2,6] B 、[2,5] C 、[3,6] D 、(3,5] 解:如图,作出可行域,作直线l :x+2y =0,将 l 向右上方平移,过点A (2,0)时,有最小值 2,过点B (2,2)时,有最大值6,故选A 二、求可行域的面积 例2、不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 ( ) A 、4 B 、1 C 、5 D 、无穷大 解:如图,作出可行域,△ABC 的面积即为所求,由梯形OMBC 的面积减去梯形OMAC 的面积即可,选B 三、求可行域中整点个数 例3、满足|x|+|y|≤2的点(x ,y )中整点(横纵坐标都是整数)有( ) A 、9个 B 、10个 C 、13个 D 、14个 x y O 2 2 x=2 y =2 x + y =2 B A 2x + y – 6= 0 = 5 x +y – 3 = 0 O y x A B C M y =2

解:|x|+|y|≤2等价于2(0,0)2(0,0)2(0,0) 2 (0,0)x y x y x y x y x y x y x y x y +≤≥≥??-≤≥? ? -+≤≥??--≤? 作出可行域如右图,是正方形内部(包括边界),容易得到整 点个数为13个,选D 四、求线性目标函数中参数的取值范围 例4、已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ,使z=x+ay(a>0) 取得最小值的最优解有无数个,则a 的值为 ( ) A 、-3 B 、3 C 、-1 D 、1 解:如图,作出可行域,作直线l :x+ay =0,要使目标函数z=x+ay(a>0)取得最小值的最优解 有无数个,则将l 向右上方平移后与直线x+y =5重合,故a=1,选D 五、求非线性目标函数的最值 例5、已知x 、y 满足以下约束条件220240330x y x y x y +-≥?? -+≥??--≤? ,则z=x 2+y 2的最大值和最小值分别是( ) A 、13,1 B 、13,2 C 、13,4 5 D 、 5 解:如图,作出可行域,x 2+y 2是点(x ,y )到原点的距离的平方,故最大值为点A (2,3)到原点的距离的平方,即|AO|2=13,最小值为原点到直线2x +y -2=0的距离的平方,即为 4 5 ,选C 六、求约束条件中参数的取值范围 例6、已知|2x -y +m|<3表示的平面区域包含点 (0,0)和(- 1,1),则m 的取值范围是 ( ) A 、(-3,6) B 、(0,6) C 、(0,3) D 、(-3,3)

《运筹学》习题线性规划部分练习题及答案

《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型,在模型中各系数的经济意义是什么? 2.线性规划问题的一般形式有何特征? 3.建立一个实际问题的数学模型一般要几步? 4.两个变量的线性规划问题的图解法的一般步骤是什么? 5.求解线性规划问题时可能出现几种结果,那种结果反映建模时有错误? 6.什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。 7.试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8.试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9.在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 10.大M 法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什么?最大化问题呢? 11.什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情况下,继续第二阶段? 二、判断下列说法是否正确。 1.线性规划问题的最优解一定在可行域的顶点达到。 2.线性规划的可行解集是凸集。 3.如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。 4.线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。 5.线性规划问题的每一个基本解对应可行域的一个顶点。 6.如果一个线性规划问题有可行解,那么它必有最优解。 7.用单纯形法求解标准形式(求最小值)的线性规划问题时,与 > j σ 对应的变量都 可以被选作换入变量。 8.单纯形法计算中,如不按最小非负比值原则选出换出变量,则在下一个解中至少有一个基变量的值是负的。 9.单纯形法计算中,选取最大正检验数k σ对应的变量k x作为换入变量,可使目标函数值得到最快的减少。 10.一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。 三、建立下面问题的数学模型 1.某公司计划在三年的计划期内,有四个建设项目可以投资:项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资,年末可收回本利120% ,每年又可以重新将所获本利纳入投资计划;项目Ⅱ需要在第一年初投资,经过两年可收回本利150% ,又可以重新将所获本利纳入投资计划,但用于该项目的最大投资额不得超过20万元;项目Ⅲ需要在第二年年初投资,经过两年可收回本利160% ,但用于该项目的最大投资额不得超过15万元;项目Ⅳ需要在第三年年初投资,年末可收回本利140% ,但用于该项目的最大投资额不得超过10万元。在这个计划期内,该公司第一年可供投资的资金有30万元。问怎样的投资方案,才能使该公司在这个计划期获得最大利润? 2.某饲养场饲养动物,设每头动物每天至少需要700克蛋白质、30克矿物质、100克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单 价如下表2—1所示:

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1. 什么是线性规划模型,在模型中各系数的经济意义是什么? 2. 线性规划问题的一般形式有何特征? 3. 建立一个实际问题的数学模型一般要几步? 4. 两个变量的线性规划问题的图解法的一般步骤是什么? 5. 求解线性规划问题时可能出现几种结果,那种结果反映建模时有错误? 6. 什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。 7. 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8. 试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 10.大M 法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什么?最大化问题呢? 11.什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情况下,继续第二阶段? 二、判断下列说法是否正确。 1. 线性规划问题的最优解一定在可行域的顶点达到。 2. 线性规划的可行解集是凸集。 3. 如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。 4. 线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。 5. 线性规划问题的每一个基本解对应可行域的一个顶点。 6. 如果一个线性规划问题有可行解,那么它必有最优解。 7. 用单纯形法求解标准形式(求最小值)的线性规划问题时,与0 >j σ对应的变量都可以被选作换入变量。 8. 单纯形法计算中,如不按最小非负比值原则选出换出变量,则在下一个解中至少有一个基变量的值是负的。 9. 单纯形法计算中,选取最大正检验数k σ对应的变量k x 作为换入变量,可使目 标函数值得到最快的减少。 10. 一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。 三、建立下面问题的数学模型 1. 某公司计划在三年的计划期内,有四个建设项目可以投资:项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资,年末可收回本利120% ,每年又可以重新将所获本利纳入投资计划;项目Ⅱ需要在第一年初投资,经过两年可收回本利150% ,又可以重新将所获本利纳入投资计划,但用于该项目的最大投资额不得超过20万元;项目Ⅲ需要在第二年年初投资,经过两年可收回本利160% ,但用于该项目的最大投资额不得超过15万元;项目Ⅳ需要在第三年年初投资,年末可收回本利140% ,但用于该项目的最大投资额不得超过10万元。在这个计划期内,该公司第一年可供投资的资金有30万元。问怎样的投资方案,才能使该公司在这个计划期获得最大利润? 2.某饲养场饲养动物,设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单 价如下表2—1所示:

线性规划练习题含答案

线性规划练习题含答案 一、选择题 A .4 5 - B .1 C . 2 D .无法确定【答案】B 【解析】解:如图所示 要是目标函数取得最小值的最优解有无穷多个,则令ax+y=0,并平移过点C 24 (,)33 ,(可行域最 左侧的点)的边界重合即可。注意到a>0,只能与AC 重合,所以a=18.已知点集{}2 2 (,)48160A x y x y x y =+--+≤, {} (,)4,B x y y x m m 是常数=≥-+,点集A 所表示的平面区域与点集B 所表示的平面区域的边界的交点为,M N . 若点(,4)D m 在点集A 所表示的平面区域内(不在边界上),则△DMN 的面积的最大值是 A. 1 B. 2 C. 22 D. 4【答案】B 【解析】解:因为点集A 表示的为圆心为(2,4),半径为2的圆,而点集B 表示为绝对值函数表示的区域则利用数形结合思想,我们可以求解得到。【题型】选择题 9.在平面直角坐标系中,若不等式组101010x y x ax y +-≥??-≤??-+≥? (α为常数)所表示的平面区域内的面积等于2,则a 的值为( )A . -5 B .1 C . 2 D . 3 【答案】D 【解析】解:当a<0时,不等式表示的平满区域如图中的M ,一个无限的角形区域,面积不可能为2,故只能a 0≥,此时不等式表示的区域为如图中的N ,区域为三 角形区域,若这个三角形的面积为2,则AB=4,即点B (1,4),代入y=ax+1,得a=310.已知方程:2 20x ax b ++= (,)a R b R ∈∈,其一根在区间(0,1)内,另一根在区间(1,2)内,则22 (3)z a b =++的取值范围为 A. B. 1(,4)2 C. (1,2) D. (1,4)【答案】B 【解析】解: 2( ,2)2222f (x)x ax 2b,f (0)0 f (1)0,f (3)0b 0,a 2b 10,2a 2b 40a b z (a 3)b -1z 2解:设由图像可知,三者同时成立,求解得到由线性规划知识画出可行域,以为横轴,为纵轴,再以为目标,几何意义为区域内的点到(3,0)的距离的平方,当a=-1,b=0时,z 最大为4,当点到直线 a+2b+1=02的距离为,最小为,由题目,不能去边界2=++><>>++<++>=++11.的取值范围是则满足约束条件变量122,012430 ,++=≤-+≥≥?????x y s y x x y x y x ( )A .[1,4] B .[2,8] C .[2,10] D .[3,9]【答案】B 【解析】约束条件034120x y x x y ≥≥+-≤?????表示的区域如图,221112y y s x x ++=++=?,11y x ++表示点(x ,y )与点(-1,-1)的斜率,PB 的斜率为最小值,PA 的斜率为最大值,斜率的取值范围是[1,4],112y x ++?的取值范围是[2,8]。 12.若变量x,y 满足约束条件1 325x y x x y ≥-?? ≥??+≤? 则z=2x+y 的最大值为 (A )1 (B)2 (C)3 (D)4【答案】C 【解析】:∵ 作出可行域,作出目标函数线,可得直线与 y x = 与325x y +=的交点为最优解点,∴即为(1,1),当1,1x y ==时max 3z =13.在集合 }4,1,1|),{(≤+≥≥=y x y x y x A 中,y x 2+的最大值是

线性规划题及答案完整版

线性规划题及答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

线性规划题型及解法 一、已知线性约束条件,探求线性目标关系最值问题 例1、设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、已知线性约束条件,探求非线性目标关系最值问题 例2、已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值是 . “()()2221++-y x ”值域? 三、约束条件设计参数形式,考查目标函数最值范围问题。 例3、在约束条件0 024x y y x s y x ≥??≥??+≤??+≤?下,当35s ≤≤时,目标函数32z x y =+的最大值的变化范 围是() A.[6,15] B. [7,15] C. [6,8] D. [7,8] 四、已知平面区域,逆向考查约束条件。 例4、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是() (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥??+≤??≤≤? (C) 0003x y x y x -≤??+≤??≤≤? (D) 0003x y x y x -≤??+≥??≤≤? 五、已知最优解成立条件,探求目标函数参数范围问题。 例5已知变量x ,y 满足约束条件1422x y x y ≤+≤??-≤-≤? 若目标函数z ax y =+(其中0a >)仅在点(3,1)处取得最大值,则a 的取值范围为 。 六、设计线性规划,探求平面区域的面积问题 例6在平面直角坐标系中,不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是() (A) 七、研究线性规划中的整点最优解问题 例7、某公司招收男职员x 名,女职员y 名,x 和y 须满足约束条件 ?? ???≤≥+-≥-.112, 932,22115x y x y x 则1010z x y =+的最大值是(A)80 (B) 85 (C) 90 (D)95 八、比值问题 当目标函数形如b x a y z --= 时,可把z 看作是动点()y x P ,与定点()a b Q ,连线的斜率,这样目标函数的最值就转化为PQ 连线斜率的最值。

线性规划期末复习题

《线性规划》期末复习题1 一、将下列线性规划问题化成标准型 3412281221212(1).21612,0 12MaxZ x x x x x x st x x x x =+-+≤+≤+≤≥????? 4612361221012(2).764120,0 12MinZ x x x x x x st x x x x =+-≥+≤-=≥≤????? 二、考虑下述线性规划问题 1105234912.52812,012 Maxf x x x x st x x x x ???????=++≥+≤≥ 求: (1) 用图解法求解。 (2) 写出此线性规划问题的标准型。 (3) 求出此线性规划问题的两个松弛变量的值。 三、考虑下述线性规划问题 118121022012331812..493612,012MinZ x x x x x x st st x x x x =++≥+≤+≥≥????? 求: (1) 用图解法求解。 (2) 写出此线性规划问题的标准型。 (3) 求出此线性规划问题的三个剩余变量的值。 四、考虑下述线性规划问题的灵敏度分析 431261282.231812,0 12MaxZ x x x x st x x x x =+≤≤+≤≥????? (1) 用图解法求最优解和最优目标函数值。 (2) 假定1c 值不变,求出使最优解不变的2c 值的变化范围。 (3) 假定2c 值不变,求出使最优解不变的1c 值的变化范围。 (4) 当1c 值从4变为1,2c 值不变,求出新的最优解。 (5) 当1c 值从4变为2.5,2c 值从3变为2时,其最优解是否发生变化?为什么? (6) 当右端项由(6,8,18)变为(7,8,18)时,最优解怎么变化? (7) 如果1x 的约束系数由(1,0,2)变为(1,0,3时),最优解怎么变化? (8) 如果增加一个约束5 x 1 +3 x 2≤25,最优解怎么变化?

2020年运筹学考试复习题及答案

2020年运筹学考试复习题及答案 5、线性规划数学模型具备哪几个要素?答:(1).求一组决策变量x i或x ij的值(i =1,2,…m j=1,2…n)使目标函数达到极大或极小;(2).表示约束条件的数学式都是线性等式或不等式;(3).表示问题最优化指标的目标函数都是决策变量的线性函数 第二章线性规划的基本概念 一、填空题 1.线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 2.图解法适用于含有两个变量的线性规划问题。 3.线性规划问题的可行解是指满足所有约束条件的解。4.在线性规划问题的基本解中,所有的非基变量等于零。5.在线性规划问题中,基可行解的非零分量所对应的列向量线性无关 6.若线性规划问题有最优解,则最优解一定可以在可行域的顶点(极点)达到。 7.线性规划问题有可行解,则必有基可行解。 8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其基可行解_的集合中进行搜索即可得到最优解。9.满足非负条件的基本解称为基本可行解。 10.在将线性规划问题的一般形式转化为标准形式时,引入的

松驰数量在目标函数中的系数为零。 11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入松弛变量。12.线性规划模型包括决策(可控)变量,约束条件,目标函数三个要素。 13.线性规划问题可分为目标函数求极大值和极小_值两类。14.线性规划问题的标准形式中,约束条件取等式,目标函数求极大值,而所有变量必须非负。 15.线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解 16.在用图解法求解线性规划问题时,如果取得极值的等值线与可行域的一段边界重合,则这段边界上的一切点都是最优解。17.求解线性规划问题可能的结果有无解,有唯一最优解,有无穷多个最优解。 18.如果某个约束条件是“≤”情形,若化为标准形式,需要引入一松弛变量。 19.如果某个变量X j为自由变量,则应引进两个非负变量X j′,X j〞,同时令X j=X j′-X j。 20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。 21..(2.1 P5))线性规划一般表达式中,a ij表示该元素位置在i 行j列。 二、单选题 1.如果一个线性规划问题有n个变量,m个约束方程(m

相关主题
相关文档 最新文档