运筹学课程设计--指派问题

《运筹学课程设计--指派问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、运筹学课程设计班级工管09二班姓名：赵小亮学号：0963131216目录一、指派问题1.1问题的提出1.2模型的建立1.3问题的求解二、最短路问题2.1问题的提出2.2模型的建立2.3问题的求解三、运输问题2.1问题的提出2.2模型的建立2.3问题的求解指派问题一、问题的提出现有一人要安排A、B、C、D四个教员分别到1、2、3、4四个授课点授课。因为每个人程度不等所以教课质量也不相同，同样得到的报酬也不等。如何安排这四个人的授课点才能使所得的利润最大。一、模型的建立指派问题我们借助于匈牙利法求解。假

2、设第i个教员Ai去第j个授课点Bj授课的报酬是Cij，并引入0-1变量Xij，表示Ai去Bj授课点授课，即Xij=1当指派某人去完成某授课点授课0当不指派某人去某个授课点授课i=1、2、3、4，j=1、2、3、4MaxZ=i=14j=148X11+10X12+9X13+3X14+7X21+8X22+11X23+2X24+2X31+4X32+6X33+4X34+7X41+7X42+5X43+2X44s.t=j=14Xij=1i=1、2、3、4i=14Xij=1j=1、2、3、4Xij=0或1问题的求解

3、1234A81093B78112C2464D7752由题意此指派问题的收益矩阵为Cij=810937811224647752将Max问题转化为Min问题，找到Cij最大元素11，元素均被11减，得到新矩阵：3128430997574469运算得2017430942020025运算得2015430742000023最大利润为Z=1×10+1×11+1×4+1×7=32二、运输问题2.1问题的提出包头某地有三个水泥厂分别向四个施工厂运送水泥，产地的供应量，施工厂地的需求量及各产地到各施工厂地的运费在下表

4、中已经给出，怎样安排才能是运费最低。1234供应量A675314B842727C591619需求量22131213602.2模型的建立设Xij为从ii=1、2、3地运到jj=1、2、3、4地的数量，则MinZ=i=13j=146X11+7X12+5X13+3X14+8X21+4X22+2X23+7X24+5X31+9X32+X33+6X34s.t=j=14Xij=1i=1、2、3i=13Xij=1j=1、2、3、4Xij≫02.3问题的求解675314111384272714141359161977

5、1222131213617553313U1=08-42+72U1=21413-25+9164U1=-178-12V1=6V1=2V1=2V1=3617553313U1=08241321272U2=2519981264U3=-1V1=6V2=2V3=2V4=3故初始方案为X11=1X13=13X21=2X22=13X23=12X19=19其余Xij=0故最小运费为Z=1×6+13×3+2×8+13×4+12×2+19×5=232