运筹学第五章.pptVIP

第一节整数规划数学模型及解的特点二、整数规划的数学模型的表示max（min）z=xj≥0，xj部分或全部取整数(j=1，2,……,n)st.cjxjaijxj≤(或=,≥)bi(i=1,2,……,m)整数规划的矩阵表示：整数规划的松弛问题：整数规划的最优值不优于其松弛问题的最优值。整数规划的可行解一定是其松弛问题的可行解。整数规划与其松弛问题最优解和最优值的关系CBA三、整数规划数学模型举例解设：xi为服务员在i时段开始上班人数minz=x1+x2+x3+x4+x5+x6+x7+x8约束条件x1≥10st.例1时段（2h）12345678服务员最少数目10891113853要求：服务员要连续工作4个时段目标：人数最少目标x1+x2≥8x1+x2+x3≥9x1+x2+x3+x4≥11x2+x3+x4+x5≥13x4+x5≥5x3+x4+x5≥8x5≥3且xj为整数xj≥0(j=1,2,3,4,5)例2、例3见书P124，125例1时段（2h）12345678服务员最少数目10891113853要求：服务员要连续工作4个时段目标：人数最少四、整数线性规划的数学模型及解的特点max（min）z=xj≥0且取整数(j=1,2,……,n)st.cjxjaijxj≤(或=,≥)bi(i=1,2,……,m)整数线性规划问题与一般线性规划最大区别是：(1)整数规划中决策变量必须为整数(2)设两组可行解X1、X2，(aX1+bX2)不一定是整数规划的解（其中，a，b0且a+b=1）(3)一般线性问题的可行域为一个凸集，而整数规划的可行域是一些离散点。?取整数全部决策变量都取整数时称全（纯）整数规划部分决策变量取整数时称混合整数规划决策变量只能取0或1时称0-1型整数规划?五、整数线性规划的求解方法maxz=x1+4x2例2-2x1+3x2≤3x1+2x2≤8x1,x2≥0且取整数St.x1=18/7x2=19/7Z=94/7x1=3x2=3Z=15x1=2x2=3Z=14x1=2x2=2Z=10x1=3x2=2Z=11X1*=4x2*=2Z*=12一种最简单的方法：枚举法这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题的最优解0102第二节整数规划的割平面法红色区域与原区域区别：1.是原区域的一部分2.与原问题有相同的可行解这种方法的思路：把原区域割去不含原问题可行解的那部分区域，从而可以求得原问题的最优解。我们称这种思路为割平面法第二节整数规划的割平面法第一步：先不考虑整数约束，利用单纯形法进行求解割平面法——如何割？1958年，高莫瑞提出一种每次增加一个约束——割平面约束，来割除一些多余的可行域。Cj1400CB基bx1x2x3x400x3x438-23101201δ1400……………….41x2x119/718/7011/72/71