实验十一 货车装货方案 整数规划

实验十一货车装货方案整数线性规划例1现有一节铁路货车，车箱长10米，最大载重量为40吨，可以运载7类货物包装箱。包装箱的厚度和重量不同，但宽和高相同且适合装车，每件包装箱不能拆开装卸，只能装或不装。每件货物的重量、厚度与价值如下表所示。请给出装货方案，使总的价值最大？货物厚度（厘米）重量（吨/件）价值（千元）件数1550.54082581.7378362.435864492.2367540.63353653.314547664508设xi代表该车箱装入第i类货物包装箱的件数，则容易得到下列数学模型整数规划是一类变量取整数值的数学规划。整数线性规划问题的标准形式为：A=(aij)m×n求解整数规划算法——分枝定界法原理步骤：将要求解的整数规划问题称为IL，与它相应的线性规划问题称为问题L。（1）解问题L，可能得到以下情况之一：（a）L没有可行解，这时IL也没有可行解；（b）L有最优解，且解变量都是整数，因而它也是IL的最优解，则停止；（c）L有最优解，但不符合IL中的整数条件，记它的目标函数值为f0，若记f为IL的最优目标函数值，则必有f

f0(2)迭代：第一步——分枝：在L的最优解中任选一个不符合整数条件的变量xj，设其值为lj，构造两个约束条件：xj≤[lj]和xj≤[lj]+1。将这两个条件分别加入问题L，将L分成两个后继问题L1和L2。求解L1和L2。——定界：以每个子问题的求解结果，与其它问题的解的结果一道，找出最优目标函数值最小者作为新的下界，替换f0，从已符合整数条件的各分枝中，找出目标数值为最小者作为新的上界f*，即有f

*

f

f0。第二步——比较与剪枝：各分枝的最优目标函数中若有大于f

*者，则剪掉这一枝；若小于f

*，且不符合整数条件，则重复第一步骤，一直到最后得到最优目标函数值f=

f

*

为止，从而得最优整数解x*。例1求解下列整数规划问题L：

x0=(0.4,3.8,0)

f0=14.2问题L2(x20≥4)

x2=(1/3,4,0)

f2=14.33问题L1(x20≤3)

x1=(0.5,3,0.5)

f1=14.5问题L4(x11≥1)x6=(1,0,7/3)f4=16.33

问题L5(x12=0)x3=(0,5,0)f5=15问题L6(x12≥1)x4=(1,4,0)

f6=19问题L3(x11=0)x5=(0,3,2)f3=17

广度优先问题L：

x0=(0.4,3.8,0)

f0=14.2问题L2(x20≥4)x2=(1/3,4,0)

f2=14.33问题L1(x20≤3)x1=(0.5,3,0.5)

f1=14.5问题L4(x11≥1)x6=(1,0,7/3)f4=16.33

问题L5(x12=0)x3=(0,5,0)f5=15问题L6(x12≥1)x4=(1,4,0)

f6=19问题L3(x11=0)x5=(0,3,2)f3=17

深度优先0-1型整数线性规划是一类特殊的整数规划，它的变量仅取值0或1；A=(aij)枚举法原理与算法步骤：1)

记可能的2n种取值组合按二进制排序；2)

按顺序对x的取值先检测将n个决策变量构成的x是否成立,若不成立则放弃,按次序换下一组的取值重复上述过程；若成立则转3)

3）对x逐一检测Ax≤b中的m个条件是否满足,一旦某条件不满足便停止而放弃这一组x,按次序换下一组x的取值执行2);若m个条件全满足,则转下步；4)记f0=min(f0

，

f)按次序换1)中下一组的x取值，执行2)；5)最后一组满足f=c’x≤f0和Ax≤b的x即为最优解注意：在执行上述算法步骤时，可以及时地记录所有满足f=c’x=f

*

（f*为最优值）的x，以便求所有最优解。例2求(x1,x2,x3)目标值f0f1234可行解(0,0,0)0(0,0,1)-5(0,1,0)2(0,1,1)-3(1,0,0)-3(1,0,1)-8(1,1,,0)-1(1,1,1)-6f=0f=-8f=-5f0=∞f0=0f0=-5例3一架货运