快件全部三问思路

快件处理问题可以直接看作一个供需关系的模型，待处理的快件为需求，机器能处理的快件为供给，在满足一定工时和不连续工作的条件下使供求关系平衡。以下对此供求模型进行分析并对其进行规划。一、问题一分析1.1、机器工作能力分析根据题中所给信息，每台机器每小时的工作量都不相同，但都在400上下左右浮动，下图给出每台机器的各个小时的工作量的均值和方差。Table1.1机器工作量均值机器编号工作量均值方差1398.7524.72398.7539.33400.87551.54403.1254.695397.87522.16401.12574.67398.37517.48400.512940037.710399.62517.611399.1256.4112401.518即在数据波动不是很大的情况下，我们假设机器的工作量均值为机器每小时的工作量，由于12台机器是同一款机器，我们对12台机器工作量进行均值得到399.96约等于400。为计算方便我们对每台机器的每小时工作量取400。1.2、时间内需求关系分析根据题中所给条件，快件在处理是不是实时的，而是一个时间段内的需求必须由另一个时间段内供给。（1）12：00以前到达的快件必须在14：00以前处理完毕（2）16：00以前到达的快件必须在18：00以前处理完毕（3）22：00以前到达的快件必须在第二天零点以前处理完毕对于题中时间要求固定几点前满足需求这种非定时性的需求关系，前后几个时间段是相互影响的，普通方法不易解决。为此，我们引入三个不定时变量t描述每个时间段的结束点。为下文叙述方便，在此引入符号定义。Table1.2符号定义符号说明1kT第k天的12：00前快件的处理完时间2kT第k天的16：00前快件的处理完时间3kT第k天的22：00前快件的处理完时间Figure1.1时间供求关系示意图我们对上述时间供需关系进行分析后得到T的约束关系如下：24)1(2424)1(1824)1(141224)1(32211kTTkTTkTkkkkkk1.3、机器数量分析由于快件数量过多，我们想知道在现有机器数量下能否满足需求。如果不能满足需求我们在下一步对具体需要多少进行求解。对第一天的第一段需求和第一段供给进行分析，首先第一段需求是从0：00-12：00总快件数量经过计算后为63925，第一段供给按照所有机器全部工作并且工作到14：00满13（不能连续工作8小时）个小时，即12*13*400=6240063925所以现有条件下一定不能满足快件需求。按照以上计算方式，再不考虑前后关系，机器运算时间全满的条件下，我们近似计算了各个时间段最少需要的机器数量。Table1.3时间段快件数量最少需要的机器数量0：00-12：00639251312：00-16：00213141416：00-22：00319801422：00-第二天12：00746921512：00-16：00213551416：00-22：00323651422：00-第三天12：00748001512：00-16：00215371416：00-22：003240314由以上分析可知在每个时间段工作满的情况下，即不考虑前一个时间段机器连续工作对后一个时间段的影响，所需最少的机器数量在15个以上，那么我们就为机器数量设置了一个下界15，在考虑前后时间段的机器连续工作情况下机器数量一定会大于15，对于具体上界而言，就是每个时间段每台机器都要休息一小时。对此我们根据上表同样的算法求解最多需要的机器数量为18，则可以通过分析确定总机器数量一定在15-18之间。二、问题一建模为下文叙述方便，在此我们进行符号定义。Table1.4符号定义符号说明jN第j个小时的快件数量iS第i台机器的每小时工作量ijC第i台机器是否在j小时工作X机器总数量2.1、目标函数的确定根据题中描述，问题一的目标函数很容易确定，即满足总的使用机器数量最小Xmin2.2、供需约束122424241242411:1kkjjiXiTkjijkNSCTk时间段的供需）（824122412424221:2kkjjiXiTTkjijkNSCTkk时间段的供需）（22482412424332:3kkjjiXiTTkjijkNSCTkk时间段的供需）（其中个小时工作台机器在第，第小时工作台机器不在第，第ji1ji0ijC2.3、不连续工作约束为叙述方便我们在这里引入Mij新变量表示第i台机器在第j个工时的累计工作时间。对此我们有如下约束。KijCMMKijCMijijijijij,....,3,2,1,2,,...,3,2,1,1,1但对于Mij=8时，我们必须让这台机器下一个小时休息即Mij的约束条件修改为：81ijijijijijijCMCCMM最后经过求解得最少需要16台机器。三、问题二的分析问题二要求给出确切的方案，是购买第一种机器还是第二种机器。如果全部购买设备1则根据第一问的求解结果来看，需要增加4台机器。如果全部购买第二种机器的话将以上模型约束条件进行修改。Table1.5符号定义符号说明jN第j个小时的快件数量iS第i台第一类机器的每小时工作量ijC第i台第一类机器是否在j小时工作eiS第i台第二类机器的每小时工作量eijC第i台第二类机器是否在j小时工作A购入第二类机器数量3.1、目标函数的确定根据题中描述，问题二的目标函数很容易确定，即满足总的购买机器数量最小Amin3.2、供需约束由于购入第二类机器后，现有机器种类既有第一类也有第二类，则每小时总工作量等于第一类机器和第二类机器的总工作量之和12242424124241212424111:1kkjjeiAiTkjeijiTkjiijkNSCSCTkk时间段的供需）（824122412424121242422121:2kkjjeiAiTTkjijiTTkjiijkNSCSCTkkkk时间段的供需）（22482412424121242433232:3kkjjeiAiTTkjijiTTkjiijkNSCSCTkkkk时间段的供需）（个小时工作台机器在第，第二类第小时工作台机器不在第，第二类第ji1ji0eijC3.3、不连续工作约束为叙述方便我们在这里引入Meij新变量表示第二类第i台机器在第j个工时的累计工作时间。对此我们有如下约束。AijCMMAijCMijeijeijeijeij,....,3,2,1,2,,...,3,2,1,1,1但对于Meij=12时，我们必须让这台机器下一个小时休息即Mij的约束条件修改为：121eijeijeijeijeijeijCMCCMM基于上述更改后的模型，对其进行求解得到A=2。假设第一类机器的价格为1，则第二类的价格为1.5，更经济的方案是选择购买两台第二类机器。四、问题三的分析问题三中考虑了加急快件的问题，对于加急快件，必须在到达时刻之后的整点时刻处理完毕，这就要求将原来的快件分为两组，一组是非加急，一组是加急。于是，时间约束从单个的时间分为不加急时间和加急时间。对于加急时间，供给直接对于需求。Figure1.2加急时间供求关系图五、问题三的建模5.1、对购买第一类机器的建模如果只购买第一类机器的话，那么直接计算第一类机器的所需数量即可，所以我们在第一问的模型的基础上添加了加急时间约束，使模型可以计算的有加急快件的情况下的第一类机器的数量。Table1.6符号定义符号说明jNq第j个小时的加急快件数量jNs第j个小时的快件数量iS第i台机器的每小时工作量ijCq第i台机器是否在j小时处理快件ijCs第i台机器是否在j小时处理加急快件X机器总数量5.1.1、目标函数的确定根据题中描述，问题三的购入第一类模型的目标函数很容易确定，即满足总的使用机器数量最小Xmin5.1.2、供需约束由于一小时的加急快件数量远小于一台机器一小时的工作量，于是假设一台机器可以在第j个工时处理加急快件的同时处理快件。12242424242412424124241111:1kkjjTkjjXiTkjiijiXiTkjijkNsNqSCqSCsTkkk时间段的快件供需）（8241224242412424124242212121:2kkjjTTkjijiXiTTkjijiXiTTkjijkNsNqSCqSCsTkkkkkk时间段的快件供需）（224824242412424124243323232:3kkjjTTkjijiXiTTkjijiXiTTkjijkNsNqSCqSCsTkkkkkk时间段的快件供需）（72,....,4,3,2,1,:41jNqSCqjiXiij）加急快件供需（5.1.3、不连续工作约束8)()(1ijijijijijijijijijCqCsMCqCsCqCsMM为了防止重复计算：1ijijCqCs基于以上模型进行求解。5.2、对购买第二类机器进行建模Table1.7符号定义符号说明jNq第j个小时的加急快件数量jNs第j个小时的快件数量ijCs第i台第一类机器是否在j小时处理普通快件eijCs第i台第二类机器是否在j小时处理加普通件iS第i台第一类机器的每小时工作量ijCq第i台第一类机器是否在j小时处理加急快件eiS第i台第二类机器的每小时工作量eijCq第i台第二类机器是否在j小时处理加急快件A购入第二类机器数量3.1、目标函数的确定根据题中描述，问题三的购入第二类机器的模型目标函数很容易确定，即满足总的购买机器数量最小Amin3.2、供需约束由于购入第二类机器后，现有机器种类既有第一类也有第二类，则每小时总工作量等于第一类机器和第二类机器的总工作量之和12242424242412424124241111)()(:1kkjjTkjjiXiTkjijiijiijiXiTkjijkNsNqSeCqeSCqSeCeSCsTkkk）（8241224122412424124241212121)()(:22kTkjjTTkjjiXiTTkjijiijiijiXiTTkjijkkkkkkkNsNqSeCqeSCqSeCeSCsT）（22482424241242412424k32323232)()(:3kTkjjTTkjjiXiTTkjijiijiijiXiTTkjijkkkkkkkNsNqSeCqeSCqSeCeSCsT）（3.3、不连续工作约束12)()(8)()(11ijijijijijijijijijijijijijijijijijijCqeCseMeCqeCseCqeCseMeMeCqCsMCqCsCqCsMM为了防止重复计算：11ijijijijCsqCseCqCs