数学建模整数规划

数学建模整数规划

ID:44933813

大小:431.50 KB

页数:34页

时间:2019-11-05

数学建模整数规划_第1页
数学建模整数规划_第2页
数学建模整数规划_第3页
数学建模整数规划_第4页
数学建模整数规划_第5页
资源描述:

《数学建模整数规划》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第二章整数规划1.整数规划的基本概念2.分枝定界法解整数规划3.0-1规划4.指派问题的解法第一节概述人们探讨某些线性规划问题,有时必须把全部或部分决策变量限制为整数。这样的线性规划问题,通常称为整数规划。作为线性规划的特殊情况,整数规划也有最小化和最大化之别。此外,整数规划还可以分成纯整数规划和混整数规划。二者的区别在于:前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。例1某医药公司现有两个制药厂A1和A2,三个销售店B1、B2和B3。公司打算由两个拟建的制药厂A3和A4中选择一个,来兴建新厂。各销售店每周药品需求量见表2-1。各制药厂每周药品产量和每箱

2、药品运费见表2-2。新厂投产后,估计每周的操作费(含折旧费):A3是100元,A4是120元。在两个拟建的制药厂中,应当选择哪个呢?销售店需求量(箱/周)B150B260B330产量制药厂(箱/周)运资(元/箱)B1B2B3A150323A2701058A3201310A420453表2-1表2-2设:制药厂Ai每周运到销售店Bj的药品为xij箱(i=1,2,3,4;j=1,2,3);解:建立数学模型两个老厂A1和A2及一个新厂A3和A4每周的总费用为y元。新厂厂址的选择应该确保y达到最小值。于是,y是目标函数,xij、u和v都是决策变量。它们之间的关系可以表述为:y=

3、3x11+2x12+3x13(A1每周的运费)+10x21+5x22+8x23(A2每周的运费)+x31+3x32+10x33(A3每周的运费)+4x41+5x42+3x43(A4每周的运费)+100u(A3每周的操作费)+120v(A4每周的操作费)(1)u和v全是0-1变量:约束条件:x11+x12+x13≤50x21+x22+x23≤70x31+x32+x33≤20ux41+x42+x43≤20vu,v=0,1(2)由A3和A4选择一个来兴建新厂:u+v=1(3)每个制药厂每周运到各销售店的药品不会超过其产量:(4)每个销售店每周药品的需求量能够得到各制药厂的充分

4、供应:(5)药品箱数一定取非负值:xij≥0x11+x21+x31+x41=50x12+x22+x32+x42=60x13+x23+x33+x43=30例1的数学模型为:Miny=3x11+2x12+3x13+10x21+5x22+8x23+x31+3x32+10x33+4x41+5x42+3x43+100u+120vx11+x12+x13≤50x21+x22+x23≤70x31+x32+x33≤20ux41+x42+x43≤20vx11+x21+x31+x41=50x12+x22+x32+x42=60x13+x23+x33+x43=30xij≥0(i=1,2,3,4;

5、j=1,2,3)u,v=0,1本数学模型属于最小化混整数规划例2某医疗器械厂生产A1和A2两种产品。出厂前,每种产品均须经过两道工序:先用机器B1制造,后由机器B2包装。每台产品的利润和加工时间见表2-3。在下周内,机器B1和B2分别可以使用45小时和6小时。问怎样安排下周的生产任务,才能使所获利润最大?解:建立数学模型设:在下周产品A1和A2分别生产x1合和x2合,所获利润为y百元。例2的数学模型为:产品利润(百元/合)加工时间(小时/合)B1B2A1551A2891表2-3最大化纯整数规划其中:“xk´为整数”,称为整数条件。一般地,可把整数规划的数学模型写为:整数

6、规划问题及其数学模型一律简称为整数规划;整数规划删去整数条件之前和之后,分别称为原整数规划和相应线性规划。按照四舍五入的规则,使相应线性规划的最优解整数化,在通常情况下,不能作为原整数规划的最优解。这可以从两个方面来说明:其一、相应线性规划的最优解化整后,已经不是原整数规划的可行解,当然也就不可能是它的最优解。其二、相应线性规划的最优解化整后,虽然是原整数规划的可行解,但是有可能不是它的最优解。例2是最大化纯整数规划,其相应线性规划为:下面求解这个相应线性规划。我们采用图解法。并且最优解是:(x1,x2)=(2.25,3.75)。按照四舍五入的规则,将这个最优解整数化,

7、就得到:(x1,x2)=(2,4)。它对应于点D,而点D却位于可行域R之外,因此,D(2,4)不是例2的可行解。从而,D(2,4)也不可能是例2的最优解。容易断定,点A(0,5)才是例2的最优解。图解法:相应线性规划的可行域R为图中的四边形OABC,5x1+9x2=45x1+x2=6B(2.25,3.75)D(2,4)x2ox19C(6,0)RA最优解A(0,5)整数规划常用的解法是分枝定界法和割平面法。一旦遇到仅含两个决策变量的情况,可以采用图解法,其计算方法与线性规划图解法大同小异,就不再赘述。求解整数规划不宜采用枚举法。第二节分枝定

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。