《理学整数规划》ppt课件

《《理学整数规划》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学OPERATIONALRESEARCH广东培正学院迟彦惠“四舍五入”取x1=2,x2=7.×3第五章整数规划引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413两种货物各托运多少箱使利润最大？MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x10Ax1,x2为整数ZA=96A(4.8,0)MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ

2、A=96x1,x2为整数(4,0)Z=80(5,0)(4,1)maxZ=90第一节整数规划的数学模型一、整数规划问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题二、整数线性规划问题的模型j=1,2,…,ni=1,2,…,mxj中取部分或全部为整数三、整数规划问题的类型：纯整数规划问题minZ=x1+x2+x3+x4+x5+x6+x7+x8x18x1+x28x1+x2+x37x1+x2+

3、x3+x41x2+x3+x4+x52x3+x4+x5+x61x4+x5+x6+x75x5+x6+x7+x810x6+x7+x810x7+x86x86xi0(i=1,…,8)且为整数2.0-1型整数线性规划例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之，不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？1对项目j

4、投资0对项目j不投资xj=MaxZ=∑cjxj∑ajxj≤Bx2≥x1x3+x4≥1x5+x6+x7=2xj=0或1（j=1,2,…n）3.混合整数规划例3工厂A1和A2生产某种物资，由于该种物资供不应求，还需要建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(j=1,2,3,4)。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量

5、350400300150y——0-1变量y=1若建工厂A30若建工厂A4设xij为由Ai送往Bj的物资数量。则总费用为:minZ=∑∑cijxij+[1200y+1500(1-y)]x11+x21+x31+x41=350x12+x22+x32+x42=400x13+x23+x33+x43=300x14+x24+x34+x44=150x11+x12+x13+x14=400x21+x22+x23+x24=600x31+x32+x33+x34=200yx41+x42+x43+x44=200(1-y)xij≥0,y=0

6、或1第二节解纯整数规划的割平面法一、基本思想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。二、割平面求解举例MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0且为整数松弛问题MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0-x1+x2+x3=13x1+x2+x4=4x1,x2≥0不考虑整数解约束，解松弛问题的最优单纯形表为：CBXBb1100x1x2x3x40

7、x31-11100x443101σ-1-100…………………1x13/410-1/41/41x27/4013/41/4Z=5/2σ001/21/2x2+3/4x3+1/4x4=7/4x2-1=3/4-3/4x3-1/4x4将-3x3-x4+x5=-3（切割方程）代入最优表CBXBb11000x1x2x3x4x51x13/410-1/41/401x27/4013/41/400x5-300-3-11Z=5/2σ00-1/2-1/201x111001/31/121x2101001/40x310011-1/3Z=2σ0

8、00-1/3-1/3x2-1=3/4-3/4x3-1/4x43/4-3/4x3-1/4x4≤03-3x3-x4≤03-3x3-x4+x5=0MaxZ=3x1-x23x1-2x2≤35x1+4x2≥102x1+x2≤5x1,x2≥0且为整数MaxZ=3x1-x23x1-2x2≤35x1+4x2≥102x1+x2≤5x1,x2≥0CBXBb11000x1x2x3x4x53x113/7101