第五章 整数规划.ppt

应用实例 宾馆的排班问题 数学模型 根据对问题的分析，我们可以总结得到该问题的数学模型为： 应用实例 宾馆的排班问题 代码和结果 由此可知，按照运行结果中的人数进行排班，即在各时间段的开始时刻分别安排50、70、23、37、0、50个服务员上班，所需要的总人数最少，一共为230个服务员。 f=ones(1,6); A=[-1 -1 0 0 0 0; 0 -1 -1 0 0 0; 0 0 -1 -1 0 0; 0 0 0 -1 -1 0; 0 0 0 0 -1 -1; -1 0 0 0 0 -1]; b=[-120;-80;-60;-30;-50;-100]; lb=[0;0;0;0;0;0];ub=[Inf;Inf;Inf;Inf;Inf;Inf]; M=[1;2;3;4;5;6]; %所有变量均为整数变量，故将所有序号组成向量M Tol=1e-8; %判定为整数的误差限 [x,fval,exitflag]=intprog(f,A,b,[],[],lb,ub,M,Tol) x = 50 70 23 37 0 50 fval = 230 exitflag = 1 应用实例 宾馆的排班问题 问题的反思 在这里需要指出的是，根据实际的需求，我们在问题中设置不等式约束是符合实际情况的，即并不一定要求恰好为限定的人数，多于此人数也是可以的。如果我们将不等式约束变为等式约束，即设定每个时间段的服务员人数为固定值，将不等号换成等号，此时可能出现如下情况： (1) 问题不一定有可行解，当有效等式约束的个数大于或者等于设计变量的个数时，就可能出现矛盾方程组导致失去优化的自由度 (2) 即便有可行解，也不一定会优于我们设定约束为不等式时的目标函数值，最多等于设定约束为不等式时的目标函数值。 应用实例 合理下料问题 问题的提出 某厂商只有一种规格的特质钢管，其固定长度为17m。现在需要根据客户对长度的要求对其生产的钢管进行切割，如果客户需要20根8m长、40根6m长和80根4m长的该种特制钢管，则应当如何对钢管进行切割才能使用料最省？ 应用实例 合理下料问题 问题分析 对于合理下料问题的关键问题在于确定合适的切割方案。所谓一个切割方案，是指按照客户要求的长度在原料钢管上安排切割的一种组合。例如，我们可以将17m长的钢管切割成4根4m长的钢管，余料为1m；或者切割成8m长和6m长的钢管各1根，余料为3米。在即便不能穷尽所有的方案的前提下，则需要收集尽可能多的切割方案以考虑更多的情况。在此需指出，切割模式必须合理，即余料应当小于客户要求的最小尺寸，否则原料则可以继续被切割满足客户的一种需要。例如，将17m长的钢管切割成2根6m长的钢管，余料为5m，可以进一步将5m的余料切割成4m长的钢管，余料为1米。于是本例的切割模式有： 然后确定设计目标，所谓的用料最省，我们可以有两种理解：(1) 所用的钢管数量最少，这种情况适用于余料不能用作他用(2) 余料最少，例如余料可以用于别的用途。在这两种前提下的目标函数不同，解也可能不同，在此，我们采用第一种理解。 方案1 方案2 方案3 方案4 方案5 8m 0 0 0 1 1 6m 0 1 2 0 1 4m 4 2 1 2 0 余料 1 3 1 1 3 应用实例 合理下料问题 问题解答 假设用第i种方案切割的钢管根数为xi (i=1,2,...,5)，则所需要的原钢管的数量为切割的钢管数总和，即： 根据表格中的数据和上述假设，可以知道经过切割以后获得符合客户要求的各种规格的钢管的数目如下，设用pi表示i m长的钢管的数量，即： 由于客户需要50根8m长、60根6m长和30根4m长的钢管，故各种规格的钢管数目应当不小于客户的要求，即需要满足p8≥20、p6≥40、p4≥80，于是： 由于钢管的数量是非负整数值，故所采用的切割方案中的各设计变量也均为非负整数。 应用实例 合理下料问题 数学模型 对于该问题的目标，要求所用的钢管数最少，目标函数f=S ，故该问题的数学模型为： 应用实例 合理下料问题 代码和结果 根据上述结果可以知道，所用钢管的最少数目为45根，其中采用各个方案切割钢管的数目如最优解向量x中的各