物流运筹学题库Word文件下载.docx

资源描述

物流运筹学题库Word文件下载.docx

《物流运筹学题库Word文件下载.docx》由会员分享，可在线阅读，更多相关《物流运筹学题库Word文件下载.docx（49页珍藏版）》请在冰点文库上搜索。

物流运筹学题库Word文件下载.docx

s.t2为

2x2

2X4

0,j

1-11

1,4

题的性质，求原问题的最优解

解其对偶问题为

minw8y：

12y2

2yi2y22

2y21

st.y1y25

y12y26

y1,y20

由互补松弛性条件知

5、用对偶单纯形法求解

minz2x13x24x3

Xi,X2,X30

先将约束不等式化为等式:

maxz2x13x24x3

2X2X3

3X3X5

Xjo,j1,,6

其对应初始单纯形表见表1

基

-3

-1

-2

-4

【-2】

j9Zj

-2T

单纯形表2

【-2.5】

0.5

-0.5

1.5

jCjZj

-4T

最终单纯形表3

0.4

-0.2

-0.4

0.2

2.2

1.4

-1.8

-1.6

从表中可以看出检验数行均小于等于零，基变量对应的解均大于等于零，此

时求得最终单纯形表。

从最终单纯形表中可以看出，x*=〔2.2,0.4,0，0，0〕，

对应目标函数值为z*=5.6。

线性规划问题:

maxz5x15x213x3

X\x?

3x320

s.t12%4x210x390

X0,j1,川,3

先用单纯形法求出最优解，然后分析在以下各种条件下，最优解分别有什么变化？

1约束条件一的右端由20变为30;

目标函数中Xj的系数由13变为8；

④增加一个约束条件2^3x25x350；

⑤增加一个变量X4，对应系数为

解化为标准型后用单纯形法计算，如下表所示

单纯形法初始表1

【3】

-5

13t

单纯形法表2

20/3

-1/3

【1/3】

1/3

80/3

46/3

2/3

jCj可

-2/3

2/3t

13/3

单纯形法表3

j5Zj

至此，所有的j0,j1,川,5，那么X（0,20,0,0,0）T是该线性规划问题的最

优解，对应的目标函数值为z5x,5x213x3100。

1当约束条件一的右端由20变为30时，最优解变为X（0,0,9,0,0）T，此

对应的目标函数值为z5x!

5x213x3117。

2当目标函数中沟的系数由13变为8时，最优解不变，目标函数值也不变。

1、0一

3当为系数列向量由变为时，最优解不变，目标函数值也不变。

125

4当增加一个约束条件2x3x>

5x350时，最优解变为X（0,50/3,0,0,0）T，

此对应的目标函数值为z5x15x213x3250/3。

-3一一

5当增加一个变量x4,对应系数为2时，最优解不变，目标函数值也不变。

7、某公司面临一个是外包协作还是自行车生产的问题。

该问题生产甲、乙、丙

三种产品，这三种产品都要经过铸造、机加工和装配三个车间。

甲、乙两种产品

的铸件可以外包协作，也可以自行生产，但产品丙必须由本厂铸造才能保证质量。

有关情况见表2-12,该公司种可利用的总工时为：

铸造8000小时、机加工12000小时和装配10000小时。

为使该公司获得最大利润，甲、乙、丙三种产品应各生产多少件？

甲、乙两种产品由该公司铸造及外包协作铸造各多少件？

表2-12甲、乙、丙三种产品的工时与本钱

、、、、产品工时与本钱\

每时铸造工时〔小

时〕

每件机加工工时

〔小时〕

每件装配工时〔小

自产铸件每件成

本〔元〕

外协铸件每件成

机加工每件本钱

〔元〕

装配每件本钱

每件产品售价

解设捲、X2、X3分别为三道工序都有公司加工的甲、乙、丙三种产品的件数，X4、X5分别为由外协铸造再由该公司加工、装配的甲乙两种产品的件数每件产品的利润分别如下：

每件产品甲全部自制的利润=23—〔3+2+3〕=15〔元〕；

每件产品甲由外协铸造，其余自制的利润=23—〔5+2+3〕=13〔元〕；

每件产品乙全部自制的利润=18—（5+1+2）=10（元）；

每件产品乙由外协铸造，其余自制的利润=18—（6+1+2）=9（元）;

每件产品丙的利润=16—（4+3+2）=8（元）。

建立此问题的线性规划问题如下：

15x1

10X2

7X3

13x4

9x5

5x1

8000

6x1

4X2

8x3

6x4

4x5

12000

s.t.

3x1

2X2

2x5

10000

Xj0（j1,2,3,4,5）

经计算得结果：

X*（x1,x2,x3,x4,x5）T（1600,0,0,0,600）T,maxz29400。

故最优方案为：

产品甲生产1600件，全部由该公司自己铸造；

产品乙生产600件，由外协铸造后再有该公司加工、装配；

产品丙不生产。

8、A公司需制造2000件的某种产品，这种产品可利用A，B，C设备的任意一种加工，每种设备的生产准备结束费用，生产该产品时的单件本钱，以及每种设备的最大加工量如表8所示，试对此问题建立整数规划模型并求解。

表8产品的准备结束费、生产本钱和最大加工量

设

备

准备结束费（元）

生产本钱（元

/件）

最大加工数（件）

600

300

800

1200

解设Xj为采用第j（j1,2,3）种设备生产的产品数量，生产费用为

kj5Xj

（Xj

0）

Cj（Xj）

式屮，kj为固疋本钱准备结束费，Cj

为生产成

本。

设0-1变量

yj，令yj

采用第j种设备生产，即Xj0时

不采用第j种设备生产，即Xj0时'

1,2,3

目标函数为

minz（100yi10xJ（300y22x2）（200y35x3）

XjMyj0j1,2,3

为x2x32000

为600

x2800

x31200

x1,x2,x30,且均为整数yj1或0,j1,2,3

解之得最优解为X（0,800,1200）T,Y（0,1,1）T即用设备B和C生产，分别生产800件和1200件0

9、某物流企业要从以下10个可供选择的地点中确定5个转运中心，使总的物流费用最小。

假设10个地点位的代号为3,川心0，相应的钻探费用为g,|||,g。

，并且井位选择上要满足以下限制条件：

1选择3和S7，或选择S9；

2选择了S3或S4就不能选S5，反之亦然；

3在S5,Sb,S7,S3中最多只能选两个。

试建立这个问题的整数规划模型。

于是问题可列成：

X7X82

，当Si未选用

当Si选用

10、用分枝定界法求解下面的整数规划问题

maxz3捲2x2

2x1x29

s.t2x13x214

为,x20且取整

解①解该问题（IP）的松弛问题（LP）得最优解X。

（3.25,2.5），目标函数值为zo14.75，xo不满足取整条件。

②分枝与定界

定界：

zo14.5是原问题最优目标函数值z*的一个上界，记为z14.75；

显然x（0,0）是原问题的一个可行解，相应目标函数值z=0是z*的一个下界，记作z=0，即有0z*14.75。

分枝：

在x0中任取一非整分量，比方取x22.5作为分枝变量。

在LP中分别

增加约束X22和x23，得两个分枝LP1和LP2。

求各分枝最优解，填入分枝图，如以下列图所示。

可求得LP1的最优解为（3.5,2）,Z=14.5

LP2的最优解为（2.5,3）,z=13.5

应选取边界值较大的子问题

由于两个子问题的最优解仍非原问题的可行解

LP1继续分枝.在LP1上分别加上约束X1<

3和X1>

4得LP11和LP12

2x13x214

LP11

s.t.x22LP12

s.t.x22

x13

x14

x1,x20

可求得LPii最优解为〔3,2〕,z=13;

LP12的最优解为〔4,1〕,z=14。

因此保

留可行解中较大的z=14。

求解过程如下列图：

11、用匈牙利解法求解下面的指派问题

解①每行减掉其所在行最小值，然后每列再减其所在列最小值，得新的

矩阵

0234

1044

1200

0144

②此时，C中各行各列都已出现零元素。

为了确定C中的独立零元素，对C中零元素加圈，即

■0234

c1「°

12'

.0144

由于只有3个独立零元素，少于系数矩阵阶数n=5,不能进行指派，为了增加独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：

用最少的直线覆盖所有的“0〞得

1从矩阵未被直线覆盖的数据中找出一个最小的k并且减去k，矩阵中k=3<

2直线相交处的元素加上k，被直线覆盖没有相交的元素不变，得到以下矩阵

0201

1011

4500

0111

此时，有四个独立零元素，独立零元素的个数与效率矩阵的阶数相同，那么该指派问题的最优解为

0010

0100

0001

1000

12、某公司运输车队完成各项运输任务的效率矩阵如下，解效率矩阵最小化

指派问题。

每行减掉其所在行最小值，然后每列再减其所在列最小值，得新的矩阵

这里直线数为3〔等于4时停止计算〕，要进行下一轮计算。

从矩阵未被直线覆盖的数据中找出一个最小的k并且减去k，矩阵中k=3。

直线相交处的元素加上k，被直线覆盖没有相交的元素不变，得到以下矩阵

3（

）

）7

）3

此时得到指派问题的最优解

13、试述运输问题数学模型的特征，为什么模型的〔m+n〕个约束中最多只有〔m+n-1〕个是独立的？

nmnm

答如果将全部发量约束Xjjai相加，就得到Xjjai;

将全部收

mnmnmn

量约束Xjjbj相加，就得到Xjbj,由于收发平衡，有aibj,

i1j1i1j1i1j1

所以模型〔4-1〕中mn个等式约束不是相互独立的。

可以证明，在这mn个

等式约束中任取mn1个，贝U它们是相互独立的，即不存在多余的约束条件。

在mn个等式约束中删除任何一个，运输问题的可行域不变。

所以，运输问题的基解仅有mn1个基变量。

14、如何把一个产销不平衡的运输问题〔含产大于销和销大于产〕转化为产销平衡的运输问题？

答对于总产量不等于总需求量的运输问题，不能直接采用表上作业法求最优调运方案。

而是将产销不平衡问题转化为产销平衡运输问题，然后再采用表上作业法进行求解。

①产大于销问题：

对于此类问题，设有一个假想销地Bn1，其销量为

bn1aibj

i1j1

但实际上没有运输，故其单位运价为0,这样就转化为产销平衡问题，但没有破坏原问题的性质，表4-44为产销平衡表。

表4-44产销平衡表

\销

产地\

〞・・

Bn+1

产量

C11

C12

C1n

C21

C22

C2n

■

Cm1

Cm2

+«

Cmn

销量

+4-1

bn+1

②销大于产的问题：

对于此类问题，设有一个假想产地Am1，其产量为

am1bjai

j1i1

但实际上没有运输，故其单位运价为无穷大M，这样就转化为产销平衡问

题，但没有破坏原问题的性质，表4-45为产销平衡表。

表4-45产销平衡表

产地\\

++*

・・・

++•■

Am+1

am+1'

15、运输问题的供需关系表与单位运价表如表15所示，试用表上作业法求

最优解。

表15运输表

产地、\

丁

解用最小元素法求解的整个求解过程如运算表1、运算表2所示:

运算表1

运算表2

由上表知该运输问题的最优解为:

XBX11,X12,X22,X23,X24,X31

XNX13,X14,X21,X32,X33,X34

35,15,25,20,15,25T

0,Q0,0,0,0

最优值为:

z*353152255202153252395。

16、某运输问题的一个产销量及调运方案见表16-1,单位运价表见表16-2

判断所给出的调运方案是否为最优？

并说明理由。

表16-1调运方案

\销产地'

、

表16-2单位运价表

、、、销地产地'

、、

解调运方案是最优，因为如果上表是最优解，可以求得位势数为

stminij0im,0jn0所以上表为最优解。

17、某糖厂每月最多生产糖270吨，先运至三个仓库，然后再分别供应五个地区

需要。

各仓库容量分别为50吨，100吨，150吨，各地区的需要量分别为25吨，105吨，60吨，30吨，70吨。

从糖厂经由各仓库然后供应各地区的运费和储存费如表17所示。

试确定一个总运费最低的调运方案。

表17运费及存储费用表

解仓库总容量为300吨，各地区需要量总计270吨。

仓库有30吨装不满，

各地区有20吨不能满足。

可虚设一库容20吨的仓库A4来满足需要，相应虚设

一地区B6来虚购仓库中未装进的30吨糖。

由此列出产销平衡表与单位运价表如

下：

105

按上表用表上作业法求之得最优调运方案为

X110,X12

50,X13

0,为4

0,X15

0,X21

25,X22

0,X23

60,X24

15,X250,

x；

10,x；

50,X33

0,x；

最优解为z*

5015

2060

1515

3050

7025

61000

18、公司有资金8万元，投资A、B、C三个工程，一个单位投资为2万元。

每个工程的投资效益率与投入该工程的资金有关。

三个工程A、B、C的投资效益

〔万元〕和投入资金〔万元〕的关系见下表。

求对三个工程的最优投资分配，使总投资效益最大。

工程

投入资

展开阅读全文