《管理运筹学》复习题及参

四、把下列线性规划问题化成标准形式：

                         

2、minZ=2x1-x2+2x3

              

                   

五、按各题要求。建立线性规划数学模型

1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：

根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。    问如何安排生产计划，使总利润最大。

2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?

1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示：

起运时间	服务员数
2—6     6—10     10一14     14—18     18—22     22—2	4     8     10     7     12     4

每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?

五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题：

           

七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。

   

         

 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10

		Xl	X2	X3	X4
	—10	b	-1	f	g
X3	2	C	O	1	1／5
Xl	a	d	e	0	1

(1)求表中a～g的值    (2)表中给出的解是否为最优解?

（1）a=2  b=0  c=0  d=1  e=4/5  f=0  g=－5      （2） 表中给出的解为最优解 

第四章          线性规划的对偶理论

五、写出下列线性规划问题的对偶问题

1．minZ=2x1+2x2+4x3

  

  

六、已知线性规划问题

          应用对偶理论证明该问题最优解的目标函数值不大于25

七、已知线性规划问题

    maxZ=2x1+x2+5x3+6x4

其对偶问题的最优解为Yl﹡=4，Y2﹡=1，试应用对偶问题的性质求原问题的最优解。

七、用对偶单纯形法求解下列线性规划问题：

             

八、已知线性规划问题

    

(1)写出其对偶问题   (2)已知原问题最优解为X﹡=(2，2，4，0)T，试根据对偶理论，直接求出对偶问题的最优解。

     W*  = 16

第五章  线性规划的灵敏度分析

四、某工厂在计划期内要安排生产I、Ⅱ两种产品。已知生产单位产品所需的设备台时及A、B两种原料的消耗如表所示：

	I	Ⅱ
设备 原材料A 原材料B	1 4 0	2 0 4	8台时 16kg 12kg

  该工厂每生产一件产品I可获利2百元，每生产一件产品Ⅱ可获利3百元。

    (1)单纯形迭代的初始表及最终表分别如下表I、Ⅱ所示：

x1    x2     x3     x4       x5

xB    -Z	0	2     3     O      0       0
X3     X4     X5	8     16     12	1     2     1      O       0     4     0     0      1       0     0     4     0      0       1
	14	0    0    -3/2   -1/8      0
Xl X5 X2	4 4 2	1    0     0     1/4       0 0    0     -2    1/2       1 0    1     1/2   -1/8      0

  说明使工厂获利最多的产品混合生产方案。 (2)如该厂从别处抽出4台时的设备用于生产I、Ⅱ，求这时该厂生产产品I、Ⅱ的最优方案。  (3)确定原最优解不变条件下，产品Ⅱ的单位利润可变范围。   (4)该厂预备引进一种新产品Ⅲ，已知生产每件产品Ⅲ，需消耗原材料A、B分别为6kg，3kg使用设备2台时，可获利5百元，问该厂是否应生产该产品及生产多少?

(1)使工厂获利最多的产品混合生产方案：生产I产品4件，生产II产品2件，设备台时与原材料A全部用完，原材料B剩余4kg，此时，获利14百元。  (2)X*=(4，3,2，0，o)Tz*=17      (3)0≤C2≤4    (4)应生产产品Ⅲ，产量为2。

         

五、给出线性规划问题

  

  用单纯形表求解得单纯形表如下，试分析下列各种条件变化下最优解(基)的变化：

xl    x2    x3     x4    x5

xB    -Z	-8	0    0    -3    -5    -1
xl     x2	1     2	1    0    -1     4    -1     0    1     2    -1     1

    (1)分别确定目标函数中变量X1和X2的系数C1，c2在什么范围内变动时最优解不变；  (2)目标函数中变量X3的系数变为6；  (3)增添新的约束X1+2x2+x3≤4     

 解：(1)3/4≤C1≤3       2≤C2≤8             (2)X*=(2，0，1，0，0，0)T       Z*=10

 (3)X*=(2，1，0，0，1，0)T       Z*=7            (4)X*=(0，2，0，0，0，1/3)T      Z*=25/3

  第六章       物资调运规划运输问题

三、判断表(a)(b)(c)中给出的调运方案能否作为表上作业法求解时的初始解，为什么?

(a)

	Bl	B2	B3	B4	B5	B6	产量
Al	20	10					30
A2		30	20				50
A3			10	10	50	5	75
A4						20	20
销量	20	40	30	10	50	25

 (b)                                              (c)

	Bl	B2	B3	B4	B5	B6	产量		Bl	B2	B3	B4	产量
Al					30		30	Al			6	5	11
A2	20	30					50	A2	5	4		2	11
A3		10	30	10		25	75	A3		5	3		8
A4					20		20	销量	5	9	9	7
销量	20	40	30	10	50	25

  (a)可作为初始方案；  (b)中填有数字的方格数少于9(产地数+销地数－1)，不能作为初始方案；

(c)中存在以非零元素为顶点的闭回路，不能作为初始方案

四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b)，判断给出的调运方案是否为最优?如是说明理由；如否。也说明理由。

表(a)产销平衡表及某一调运方案        单位运价表

销地

产地	Bl	B2	B3	B4	B5	B6	产量
l	30	20					50
A2		30	10				40
A3			10	40	10		60
A4					20	11	31
销量	30	50	20	40	30	11

五、给出如下运输问题

运价  

产	B1	B2	B3	B4	产量
Al	5	3	10	4	90
A2	1	6	9	6	40
A3	20	10	5	7	70
销量	30	50	80	40	200

 (1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案

六、用表上作业法求给出的运输问题的最优解

	甲	乙	丙	丁	产量
1	10	6	7	12	4
2	16	0	5	9	9
3	5	4	10	10	4
销量	5	2	4	6

	甲	乙	丙	丁	产量
1	1	2	1		4
2			3	6	9
3	4				4
销量	5	2	4	6

在最优调运方案下的运输费用最小为118。

第七章          整数规划

四、用分枝定界法求解下列整数规划问题：(提示:可采用图解法)

    maxZ=40x1+90x2

   

五、用割平面法求解 

                

六、下列整数规划问题

 

说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。

答：不考虑整数约束，求解相应线性规划得最优解为  x1=10/3，x2=x3=0，用四舍五人法时，令x1=3，x2=x3=0，其中第2个约束无法满足，故不可行。

七、若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列条件：

    (1)在s1，s2，S4中至多只能选择两个； (2)在S5，s6中至少选择一个；(3)在s3，s6，S7，S8中至少选择两个；    试建立这个问题的整数规划模型

八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少?

工作

人	I	Ⅱ	Ⅲ	Ⅳ
甲 乙 丙 丁	15 19 6 19	18 23 7 21	2l 22 16 23	24 18 19 17

第八章            图与网络分析

四、计算题

  1．下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做?最小的总长度是多少?

                  

2．对下面的两个连通图，试分别求出最小树。

             

3、第1题中的交通图，求城市A到D沿公路走的最短路的路长及路径。

  4．对下面两图，试分别求出从起点到终点的最短路线。

        

5．分别求出下面两图中从发点到收点的最大流。每条有向边上的数字为该边的容量。

          

   6．下面网络中，点①，②是油井，点⑥是原油脱水处理厂，点③、④、⑤是泵站，各管道的每小时最大通过能力(吨／小时)如有向边上的标注。求从油井①、②每小时能输送到脱水处理厂的最大流量。

 (提示：虚设一个发点S，令有向边(S，1)，(S，2)的容量为∞)。

        

十一章

1、需求：需求就是库存的输出。

2、存贮费：一般是指每存贮单位物资单位时间所需花费的费用。

3、缺货损失费：一般指由于中断供应影响生产造成的损失赔偿费。

4、订货批量Q：存贮系统根据需求，为补充某种物资的库存而向供货厂商一次订货或采购的数量。

5、订货间隔期T：两次订货的时间间隔可订货合同中规定的两次进货之间的时间间隔。

6、记账间隔期R：指库存记账制度中的间隔记账制所规定的时间。

十二章