王家荣-运筹学习题

112131111112131111323112131121212312112311112121112习Exercises

题第一章线性规划一、以下集合中，哪些是凸集，哪些不是凸集?(1)｛x)｜x+x≤｝(2)｛xx)x+x≤1,x-x≤2｝(3)｛x)｜x=0｝(4)｛xx)x≥x,+x+x≤｝(5)｛x)｜x=1,x｜≤｝(6)｛x,)=x|x≤4二、求出以下不等式组所定义的多面体的所有极点，x+x≤5

-xxx

+x+2x≤xx≥0+x+x≤-x

2

≤4x

xx≥0三、用图解法求解以下线性规划问题

s.t.

x+3xx+x≤-2x+2x≤x

1

≤x

x≥

minz=xs.t.2x

1

-x

≤4x+xx

2

≥3≤5x1x

x

2

≤4≥0z=x+2xs.t.

x

1

-x≤

112111121313131231222111211112131313123122211212121212311211313131123124x+2x≤4x

1

≤3

minz=

xx≥x+3xs.t.

x+2x2x+x

≥4≥4x

x≥四、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。

z=2x

+x

2

-xs.t.

x+x+2x≤x

-x≤xx,x≥0五、对于以下的约束x≤x

1

-x≤x≤x,x≥(1).画出该可行域，并求出各极的座标。(2).从原点开始，从一个基础可解移到下一个“相邻的”基础可行解，指出每一次叠代，哪个变量进基，哪个变量离基。六、用单纯形原理求解以下线性规划问题z=s.t.2x≤3-x+x≤xx≥0七、已知x，，x)(40是以下线性规划的一个基础可行解，以这个基为初始可行基，求解这个线性规划问题z=x-2xs.t.3x+4x＝122x

1

-x≤xx

2

≥0八、用单纯形表求解以下线性规划问题maxz=+xs.t.

x+x+x≤2x+x-x≤-x+3x≤xxx≥0minz=-2x

-x-5x/

13413412341211112121311341341234121111212131231221323131231313113123s.tx+2x

-x≤62x+3x

-x+x≤x

1

+x

3

+x≤4minz=

xxx3x-x

x≥0s.t.-2x+3x

≥-3≥-62x+x≤84x

-x≤16xx≥0九、用两阶段法求解以下线性规划问题maxz=+3xs.t.

3x+2x

≤13x+3x≤2x

1

+x

2

+x

3

=13xx

x

3

≥0maxz=

1

-x+xs.t.

x+x-2x≤84x

1

-x

+x≤22x+3x

-x≥xxx≥minz=x+3x

-xs.t.

x+x+x≥3-x+2x

≥2-x+5x+x≤4xxx≥/

11121213413123123413131211112121341312312341313121234121245145311222123第二章

对偶线性划和灵敏度析一写出以下问题的对偶问题

z=s.t.

-x+2x3x+4x≤-x≥22xxx≥0z=+3x+6xs.t.

x+2x

+x

4

≥2-2x

-x

-x+3x≤xx,xxz=+3x-5x

≥0s.t.x

+x

2

-x

+x

4

≥52x

+x

3

≤4x

+x

3

+x

4

=6x≤x≥0,x≥0,x无符号限制二、设原始问题为z=2x+3xs.t.

1

+x

2

≤4xxx

≤3≥0写对偶问题用解法分别求出原始问题和对偶问题的各基础可行解，并求出各基础可行解的目标函数值，并比较他们的大小。(3)验证原始问题和对偶问题的最解满足Kuhn-Tucker最优性条件。三、已知如下最优单纯形表，其中，是弛变量，两个约束都是≤的。z

x

x

2

x

3

x

x

RHSzxx

1/2

1/2

1/3

5/25/2（1写出原始问题及对偶问题。（2从上表中直接求出对偶问题的最优解。四、对于以下线性规划问题

z=+6xs.t.

xx

11

+x+x≤10-x+3x≤6xxx≥0/

13213123TB11212311121211113213123TB11212311121211112311312335(1).写出对偶问题(2).写出原始问题所有的基，判这些是否原始可行基，是否对偶可行基。(3).求出原始问题和对偶问题的优解。五、对于以下问题z=

-xs.t.

x

1

+x+2x

≤6xxx,写对偶问题

-xx

≤4≥0用纯形表求解原始问题，求出每一次叠代的当前基CTB，并判断每次得到的对偶变量是否满足对偶可行条件。六、用对偶单纯形法求解以下问题

B对的对偶变量W＝z=+6x

3s.t.

x

3

≥3x

3

≥5xx,x≥0z=10xs.t.x

+x

2

≥22x

-x

≥6xx

≥0七、对以下问题min

x

1

+x

2s.t.

2x

+x

2

≥3xxxx

≥4≥3≥0（1用图解法画出可行域和各个极点。（2用对偶单纯形表求解以上问题，并在图上画出叠代路线。八、已知以下线性规划问题

z=2x

1

+x

2

-xs.t.

x

2

+x

3

≤8-x

+x

2

-2x

≤4x及其最优单纯形表如下：

xx≥0z

x

1

x

2

x

x

4

x

RHSz

x

1

/

22113232366221变为22113232366221变为2x

6

-112（1求使最优基保持不变的=1变化范围。如果c从成，最优基是否变化，如果变化，求出新的最优基和最优解。（2对c进灵敏度分析，求出由变为4的最优基和最优解。（3对变量在第二个约束中系数=-2进行灵敏度分析，求出从变为1新的最优基和最优解。（4增加一个新的变量x，在目标函数中的系数c，约束条件中的系数向量为

，求的最优基和最优解。（5增加一个新的约束x求新的最优基和最优解。（6设变量x在束条件中的数向量由解。

，求出新的最优基和最优九、某工厂用甲、乙、丙三种原料生A、C、D四种产品，每种产品消耗原料定额以及三种原料的数量如下表所示:产

品

A

B

C

D

原料数量（吨）对原料甲的单耗(吨万件对原料乙的消耗(吨万件对原料丙的消耗(吨万件单位产品的利润(万元万件

－

－

（1）使总利润最大的生产计划和按最优生产计划生产时三种原料的耗量和剩余量。（2求四种产品的利润在什么范围内变化，最优生产计划不会变化。（3求三种原料的影子价格和四种产品的机会成本，并解释最优生产计划中有的产品不安排生产的原因。（4在最优生产计划下，哪一种原料更为紧?如甲原料增加1吨，这时紧缺程度是否有变化?/

1121111121111121212123第三章数规、分用割平面法和分枝定界法求以下整数规划问题

z=x

1

2s.t.

14x+42x≤196-x

≤

x

1

x

2

≥、用枝定界法求解以下混合整数规划问题3x+7xs.t.12≤12-x≤2xx≥0x为数、求以下整数规划问题+30x

3s.t.

2x+3x+xxxx

33

≤≥x，x，为整数/

1122=3ijijij1121122=3ijijij112ijij第四章运输问题、求如下图所示运输问题，并将最优解在网络中表示。

=1s=2

=3s=5

、将表所示的一解作为初始解，分别用闭回法和对偶变量法求出非基变量的z-c，并求出运输问题的最优解。

、对表所示的运问题（表内部的数字表示c，表右面和下面的数分别表示供应量和需求量）。B

1

B

2

B

3

B

4AAA

123

（1分用西北角法和最小元素法得到初始基础可行解；（2选其中一个基础可行解，从这个基础可行解出发，求出这个问题的最优解；（3如c变-4，最优解是否改变？如改变，求出新最优解；（4在来的问题中，如果从A到B的道路被阻，最优解是否会改变？如改变，求出新的最优解。、求下表所示的求不平衡的运输问题，其中A—格子中的数字表示c。/

ijijijijn供求地

B

1

B

2

B

3

B

4

供应量AAA

123

需求量

、有n项任务分配给n个人去完成项任务只需要一个人去做个人只做一项任务。第i项务分配给第j个去所需要的费用为c。如何分配各项任务，使完成n项任务的总费用最小。这个问题称为指派问题（）。矩阵C=[c]称为指派问题的费用矩阵。指派问题是一类特殊的运输问题。用运输问题算法求解以下指派问题，费用矩阵如下表所示：任务1任务2任务3

人员

人员2

人员/

1ij234=-6512ij34ij11271ij234=-6512ij34ij1127第五章网络优化、对下网络，用凑的方法得到一个初始可行的生成树，求这个网络的最小费用流。=5

c

=-4

=2

=3、求下图所示的小费用流问题（注意：

）i=3

=1

c=1

=-3、求下图所示的有中转站的运输问题，其中节点1、3是地、7是地4是中转站。边上的数字是。s

s

s3=153

、用两阶段法求解下图所示的网络最小费用流问题。/

12ij34121121112ij341211211211=1

=-2

c=3

=-2、求以下的生产运输—存储问题。一个公司在A、两生产同一种产品，考虑一、二两个季度的生产。不同的产地，不同的季节，生产费用和生产能力都不相同。产地AA两季度的生产费用和生产能力如下表。产地

第一季度生产费用生产能力

第二季度生产费用生能力AA

12

元吨元吨

吨

元吨元吨

AA生的产品可以运输到两个销地B（输时间可以计），以满足两地的需求，、B两地的需求量如下表所示。销地

第一季度

第二季度BB

12

运输费用也随运输路线和季节不同而变化。如下表所示。产地

第一季度销地B销地B

2

第二季度销地B销地B

2AA

12

元吨元吨

元吨元吨

元吨元吨

元吨元吨另外，每个产地和销地都可以库存第一季度的产品，以供第二季度之用，库存费用如下表所示。产销地

库存费用////求两个季度的最优生产、库存计划，使两个季度的总费用最小。/

ijijijij、求下图所示网络的最大流（1

ij

（2

、求以下网络从节点1到余各节点的最短路径（1

c

（2/

cc

ij

/

1122112213131231313312312313第六章

动态规划一、用动态规划求解以下网络从AF的最短路径，路径上的数字示距离。A5

BBB

123

CC

12

DDD

123

EE

12

F二、某公司有台备，分配给所属三工厂。各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。求最优分配方案，使总效益最大。工厂

台数

ABC

三、用动态规划求解以下非线性整数规划问题：min-5x-3x-7xs.t.+3x≥16x,x≥,x,x为数四、用动态规划求解以下背包问题（1z=12x+22x+15xs.t.2x+4x+3x

≤x,x≥xx,x为整数（2z=17x+72x+35xs.t.10x≤x,x≥xx,x为整数五、某工厂要安排某种产品一年中四个季度的生产计划。生产费用的经验公式是：元(本季度产量产品的存储费用为每件每季度1元。设初始存储量为0，大存储量为500件四个季度的市场销售量预测如下：/

季度一二三四

销售量（件）

累计销售量（件）用动态规划确定四个季度的生产量和储存量在满足各季度销售额的条件下使总生产、存储费用为最小。六、有三种新产品A，，C有待研制。种新产品在一年内研制不成功的概率与投入该产品的研制费用有关，有关数据如下表。设总的研制经费为万元。试求三个项目研制费用的分配方案，使这三个产品研制全不成功的概率为最小。产

品

A

B

C万元万元万元

七、求解以下设备更新问题：当设备年龄k时，设备运行每年所得的净收入可用下式表示：I=26-2k-0.5kk设备用过4后就被废弃，更新设备的费用为。现有一台设备，已用过一年，要这种设备更新的五年计划，决定每一年初设备更新或留用，使总收入最大。八、求以下货郎担问题的最小旅行费用周游线路，以下是5个市中从城市