运筹学复习资料

1、. .一、 某钢筋车间要制作一批钢筋直径一样，长为3m的要90根，长为4m的要60根。原材料长10m长，问如何下料，可使所用原材料最省(建立线性规划模型，不求解)。二、 用大M法或两阶段法求解以下线性规划问题，并指出属于哪一类解：三、线性规划问题为15分：其最优解为，试用对偶理论求其对偶问题的最优解。四、求以下运输问题的最优调运方案和最小费用：产地销 地产量B1B2B3B4A11067124A21610599A35410104销量5246五、用匈牙利法求解以下指派问题目标函数为：六、VsV2V4V1V3V5Vt8，614，105，36，68，73，34，110，33，17，76，63，0求解以

2、下列图所示网络中从Vs到Vt的最大流，并且给出一个最小截集，每条弧旁的数字为。七、某厂对某种材料的全年需求量为1040吨，其购价为每吨1200元，每次订货费为2040元，每年每吨的保管费为170元。1试求最正确订货批量及年最小费用；2假设允许缺货，且知缺货损失费为每吨每年500元，求最正确订货批量及年最小费用。V1V2V3V4V6V7152384212973V5八、用破圈法或避圈法求以下列图中的最小树：答案：一、【解】标准化和参加人工变量：CBXBb2110-M00iX1X2X3X4X5X6X7-MX54422-110010X6202400010100X71648200014-Z4M2+4M1

3、+2M1+2M-M0002X1111/21/2-1/41/4000X61803-11/2-1/210360X7120601-10112-Z-20001/2-M-1/2002X14121/20001/40X61200-1001-1/20X4120601-101-Z-80-300-M0-1/2由于所有检验数小于或等于0，已得最优解：但由于非基变量X3的检验数为0，所以本线性规划问题存在无穷多个最优解。二、【解】其对偶问题是：根据互补松弛定理，由原问题的最优解知：1原问题约束：3X1+10X2+X3=3*1/4+19/4=11/2<7，那么Y30；2由于X1、X3不等于零，那么对偶问题的约束、

4、约束为等式。解方程：得对偶问题的解为：Y=(5/2,5/2,0)Z15X1+20X2+5X327.5；W55/227.5Z=W，所以Y=(5/2,5/2,0)为对偶问题的最优解三、产地销 地产量UiB1B2B3B4A13-3-1140106712A294459-3161059A322734-5541010销量5246Vj109812产地销 地UiB1B2B3B4A112-110106712A29745-3161059A34373-5541010Vj106812产地销 地UiB1B2B3B4A112110106712A28636-2161059A34384-5541010Vj106711由于所有

5、检验数都已经大于0，所以当前的方案为最优方案。Z10*1+6*2+7*1+5*3+9*6+5*4118四、D由于0*的个数等于矩阵的阶数，根据匈牙利法的第三个原理，知道已经得到最优解，最优解为：。Z91281443五、VsV2V4V1V3V5Vt8，614，105，36，68，73，34，110，33，17，76，63，00,(Vs,4)(V2,3)(V3,3)(Vs,2)(V3,3)(V2,1)增广链为Vs,V2,V3,Vt,t=3VsV2V4V1V3V5Vt8，614，135，36，68，73，34，110，63，17，76，63，30,(Vs,2)(V5,1)(V3,1)(Vs,2)(V2,1)增广链为Vs,V2,V5,V3,Vt,t=1VsV2V4V1V3V5Vt8，614，145，36，68，83，34，110，73，27，76，63，30,(-V1,2)(Vs,2)最大流的流量为V(f)=6+14=20V1=(v1,vs,v2)；1=(v3,v4,v5,vt)最小截集为：(V1,1)=(v1,v4), (v1,v3), (v2,v3), (v2,v5)六