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

1、8s.t 2为2x22X412Xj0,j1-111,4题的性质，求原问题的最优解解其对偶问题为min w 8y： 12 y22 yi 2 y2 22y2 1st. y1 y2 5y1 2y2 6y1, y2 0由互补松弛性条件知5、用对偶单纯形法求解min z 2x1 3x2 4x3Xi,X2,X3 0先将约束不等式化为等式:maxz 2x1 3x2 4x3Xi2X2 X33X3 X5Xj o, j 1, ,6其对应初始单纯形表见表1CjCiC2C3C4C5CB基bX1X5-3-1-2-4【-2】j 9 Zj-2T单纯形表2【-2.5】0.5-0.51.5j Cj Zj-4T最终单纯形表30.

2、4-0.2-0.40.22.21.4-1.8-1.6从表中可以看出检验数行均小于等于零， 基变量对应的解均大于等于零，此时求得最终单纯形表。从最终单纯形表中可以看出， x*= 2.2, 0.4, 0，0，0，对应目标函数值为z*=5.6。&线性规划问题:maxz 5x1 5x2 13x3X x? 3x3 20s.t 12% 4x2 10x3 90X 0,j 1,川,3先用单纯形法求出最优解，然后分析在以下各种条件下，最优解分别有什么 变化？1约束条件一的右端由20变为30;目标函数中Xj的系数由13变为8；增加一个约束条件2 3x2 5x3 50；增加一个变量X4，对应系数为解化为标准型后用单

3、纯形法计算，如下表所示单纯形法初始表1C1Cb20【3】9010-513 t单纯形法表2x1320/3-1/3【1/3】1/380/346/32/3j Cj可-2/32/3 t13/3单纯形法表3X16j 5 Zj至此，所有的j 0, j 1,川,5，那么X （0,20,0,0,0）T是该线性规划问题的最优解，对应的目标函数值为z 5x, 5x2 13x3 100。1当约束条件一的右端由20变为30时，最优解变为X （0,0,9,0,0）T，此对应的目标函数值为z 5x! 5x2 13x3 117。2当目标函数中沟的系数由13变为8时，最优解不变，目标函数值也不变。1 、 0 一3当为系数列向

4、量由 变为 时，最优解不变，目标函数值也不变。12 54当增加一个约束条件2x 3x 5x3 50时，最优解变为X （0,50/3,0,0,0）T，此对应的目标函数值为z 5x1 5x2 13x3 250/3。- 3 一 一5当增加一个变量x4,对应系数为2时，最优解不变，目标函数值也不变。7、某公司面临一个是外包协作还是自行车生产的问题。该问题生产甲、乙、丙三种产品，这三种产品都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可以自行生产，但产品丙必须由本厂铸造才能保证质量。 有关情况见表2-12,该公司种可利用的总工时为：铸造8 000小时、机加工12 000 小时和

5、装配10 000小时。为使该公司获得最大利润，甲、乙、丙三种产品应各 生产多少件？甲、乙两种产品由该公司铸造及外包协作铸造各多少件？表2-12甲、乙、丙三种产品的工时与本钱、产品 工时与本钱 每时铸造工时小时7每件机加工工时小时6每件装配工时小自产铸件每件成本元外协铸件每件成机加工每件本钱元装配每件本钱每件产品售价2318解 设捲、X2、X3分别为三道工序都有公司加工的甲、乙、丙三种产品的 件数，X4、X5分别为由外协铸造再由该公司加工、 装配的甲乙两种产品的件数 每件产品的利润分别如下：每件产品甲全部自制的利润=233+2+3=15 元；每件产品甲由外协铸造，其余自制的利润 =235+2+3

6、=13 元；每件产品乙全部自制的利润=18（5+1+2） =10 （元）；每件产品乙由外协铸造，其余自制的利润 =18（6+1+2） =9 （元）;每件产品丙的利润=16（ 4+3+2）=8 （元）。建立此问题的线性规划问题如下：15x110X27X313x49x55x180006x14X28x36x44x512000s.t.3x12X22x510000Xj 0（ j 1,2,3,4,5）经计算得结果： X* （x1,x2,x3,x4,x5）T （1600,0,0,0,600）T , maxz 29400。 故最优方案为：产品甲生产1 600件，全部由该公司自己铸造；产品乙生产 600 件，由

7、外协铸造后再有该公司加工、装配；产品丙不生产。8、A公司需制造2 000件的某种产品，这种产品可利用 A，B，C设备的任意一种 加工，每种设备的生产准备结束费用， 生产该产品时的单件本钱，以及每种 设备的最大加工量如表8所示，试对此问题建立整数规划模型并求解。表8产品的准备结束费、生产本钱和最大加工量设备准备结束费（元）生产本钱（元:/ 件）最大加工数（件）6003008001 200解 设Xj为采用第j（j 1,2,3）种设备生产的产品数量，生产费用为kj 5Xj（Xj0）Cj（Xj）式屮，kj为固疋本钱准备结束费，Cj为生产成本。设0-1变量yj ，令 yj采用第j种设备生产，即Xj 0时

8、不采用第j种设备生产，即Xj 0时1,2,3目标函数为mi nz （100yi 10xJ （300y2 2x2） （200y3 5x3）Xj Myj 0 j 1,2,3为 x2 x3 2000为 600x2 800x3 1200x1,x2,x3 0,且均为整数 yj 1 或0, j 1,2,3解之得最优解为X （0,800,1200）T,Y （0,1,1）T即用设备B和C生产，分别生产 800件和 1200件09、某物流企业要从以下10个可供选择的地点中确定5个转运中心，使总的物流费 用最小。假设10个地点位的代号为3,川心0，相应的钻探费用为g,|,g。，并且井 位选择上要满足以下限制条件：

9、1选择3和S7，或选择S9 ；2选择了 S3或S4就不能选S5，反之亦然；3在S5,Sb,S7, S3中最多只能选两个。试建立这个问题的整数规划模型。i 1X9于是问题可列成：X6X7 X8 2，当Si未选用1,当Si选用10、用分枝定界法求解下面的整数规划问题maxz 3捲 2x22x1 x2 9s.t 2x1 3x2 14为,x2 0且取整解 解该问题（IP）的松弛问题（LP）得最优解X。 （3.25,2.5），目标函 数值为zo 14.75，xo不满足取整条件。分枝与定界定界：zo 14.5是原问题最优目标函数值 z*的一个上界，记为z 14.75 ； 显然x （0,0）是原问题的一个可

10、行解，相应目标函数值z=0是z*的一个下界，记 作 z=0，即有 0 z* 14.75。分枝：在x0中任取一非整分量，比方取x2 2.5作为分枝变量。在LP中分别增加约束X2 2和x 2 3，得两个分枝LP1和LP2。求各分枝最优解，填入分枝图， 如以下列图所示。可求得LP1的最优解为（3.5,2）, Z=14.5LP2的最优解为（2.5,3）,z=13.5,应选取边界值较大的子问题由于两个子问题的最优解仍非原问题的可行解LP1继续分枝.在LP1上分别加上约束X1 4得LP11和LP122x1 3x2 14LP11s.t. x2 2 LP12s.t. x2 2x1 3x1 4x1, x2 0x

11、1 ,x2 0可求得LPii最优解为3,2, z=13; LP12的最优解为4,1, z=14。因此保留可行解中较大的z=14。求解过程如下列图：11、用匈牙利解法求解下面的指派问题917151411解 每行减掉其所在行最小值，然后每列再减其所在列最小值，得新的矩阵0 2 3 410 4 412 0 00 14 4此时，C中各行各列都已出现零元素。为了确定C中的独立零元素，对C中零元素加圈，即0 2 3 4c 1 4 41 2 0 0.0 1 4 4由于只有3个独立零元素，少于系数矩阵阶数n=5,不能进行指派，为了增加 独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：用最少的直线覆盖

12、所有的“ 0得34444 41从矩阵未被直线覆盖的数据中找出一个最小的 k并且减去k，矩阵中k=32直线相交处的元素加上k，被直线覆盖没有相交的元素不变，得到以下矩 阵0 2 0 110 11c4 5 0 00 111此时，有四个独立零元素，独立零元素的个数与效率矩阵的阶数相同， 那么该 指派问题的最优解为0 0 100 10 00 0 0 110 0 012、某公司运输车队完成各项运输任务的效率矩阵如下， 解效率矩阵最小化指派问题。每行减掉其所在行最小值，然后每列再减其所在列最小值，得新的矩阵这里直线数为3 等于4时停止计算，要进行下一轮计算。从矩阵未被直线覆盖的数据中找出一个最小的 k并且

13、减去k，矩阵中k=3。直线相交处的元素加上k，被直线覆盖没有相交的元素不变，得到以下矩阵3 （）3 1）7）3J此时得到指派问题的最优解13、试述运输问题数学模型的特征，为什么模型的m+n个约束中最多只有m+n -1个是独立的？n m n m答 如果将全部发量约束 Xjj ai相加，就得到 Xjj ai ;将全部收m n m n m n量约束 Xjj bj相加，就得到 Xj bj ,由于收发平衡，有 ai bj ,i 1 j 1 i 1 j 1 i 1 j 1所以模型4-1 中m n个等式约束不是相互独立的。可以证明，在这 m n个等式约束中任取m n 1个，贝U它们是相互独立的，即不存在多余

14、的约束条件。在m n个等式约束中删除任何一个，运输问题的可行域不变。所以，运输问题 的基解仅有m n 1个基变量。14、如何把一个产销不平衡的运输问题含产大于销和销大于产转化为产销平 衡的运输问题？答对于总产量不等于总需求量的运输问题，不能直接采用表上作业法求最 优调运方案。而是将产销不平衡问题转化为产销平衡运输问题，然后再采用表上 作业法进行求解。产大于销问题：对于此类问题，设有一个假想销地 Bn 1，其销量为m nbn 1 ai bji 1 j 1但实际上没有运输，故其单位运价为 0,这样就转化为产销平衡问题，但没 有破坏原问题的性质，表4-44为产销平衡表。表4-44 产销平衡表销产地B

15、1B2BnBn+1产量A1C11C12C1na1A2C21C22C2na2-IHiaAmCm1Cm2+ Cmnam销量b1b2+ 4-1bnbn+1销大于产的问题：对于此类问题，设有一个假想产地 Am1，其产量为am 1 bj aij 1 i 1但实际上没有运输，故其单位运价为无穷大 M，这样就转化为产销平衡问题，但没有破坏原问题的性质，表 4-45为产销平衡表。表4-45 产销平衡表产地+ + *Fe+ + Am+1Mam+115、运输问题的供需关系表与单位运价表如表 15所示，试用表上作业法求最优解。表15运输表产地、丁50602540解 用最小元素法求解的整个求解过程如运算表 1、运算表

16、2所示:运算表1VjaiUiBiB3B4AiA3bj运算表235由上表知该运输问题的最优解为:*TX B X11 , X12 , X22 , X23 , X24 , X31X N X13 , X14 , X21 , X32 , X33 , X3435,15,25,20,15,25 TT0,Q0,0,0,0最优值为:z* 35 3 15 2 25 5 20 2 15 3 25 2 395。16、某运输问题的一个产销量及调运方案见表 16-1,单位运价表见表16-2判断所给出的调运方案是否为最优？并说明理由。表16-1 调运方案销 产地、B5B624A43130表16-2 单位运价表、销地 产地、

17、解 调运方案是最优，因为如果 上表是最优解，可以求得位势数为st min ij 0 i m,0 j n 0所以上表为最优解。17、某糖厂每月最多生产糖270吨，先运至三个仓库，然后再分别供应五个地区需要。各仓库容量分别为 50吨，100吨，150吨，各地区的需要量分别为 25吨，105吨，60吨，30吨，70吨。从糖厂经由各仓库然后供应各地区的 运费和储存费如表17所示。试确定一个总运费最低的调运方案。表17运费及存储费用表55解 仓库总容量为300吨，各地区需要量总计270吨。仓库有30吨装不满，各地区有20吨不能满足。可虚设一库容 20吨的仓库A4来满足需要，相应虚设一地区B6来虚购仓库中未装进的30吨糖。由此列出产销平衡表与单位运价表如下：10570按上表用表上作业法求之得最优调运方案为X11 0, X1250, X130,为40,X150,X2125, X220, X2360, X2415, X25 0,x；1 0, x；*50, X330,x；0, x；最优解为z*50 1520 6015 1530 5070 256100 018、公司有资金8万元，投资A、B、C三个工程，一个单位投资为 2万元。每 个工程的投资效益率与投入该工程的资金有关。三个工程 A、B、C的投资效益万元和投入资金万元的关系见下表。求对三个工程的最优投资分配，使 总投资效益最大。工程投入资