运筹学——.整数规划与分配问题.ppt

第四章整数规划与分配问题
测形冀蘑掉郧疙厉股吨迸卧缀熙歹节页成蹭们悬乒婿栖亚脐佑吝蘸蘑刨苑运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
对于线性规划问题,最优解可能是分数或小数。但是对于某些问题,会要求解答必须是整数(称为整数解)。
对于所求解是机器的台数、完成工作的人数、装货的车数、集装箱数量等;
对于一些决策变量必须取Boolean值时,如要不要在某地建工厂,可选用一个逻辑变量x,令x=0表示不在该地建厂,x=1表示在该地建厂。
这时,分数或小数的解就不合要求,我们称这样的问题为整数规划。
凭泞听已砧围邢艇铜测接屠稳秒竿业忱诵居燥匹熏夏咽派磺懦樱谴航忙惶运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
例:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表:
货物
体积
米3/箱
重量
百斤/箱
利润
百元/箱
甲
乙
5
4
2
5
20
10
托运限制
24
13
问两种货物各托运多少箱,可使获得的利润为最大?
能否先不考虑对变量的整数约束,作为一般线性规划来求解,当解为非整数的时候可以用“四舍五入”或“凑整”方法寻找最优解?
右滋蟹顺阜导粟排钎宏诽梭吝园悔较文垢柯杉桐芳糙近蜀趟闲蝗勋杯家在运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
对于变量取值很大时,用上述方法得到的解与最优解差别不大;但当变量取值较小时,得到的解就可能与实际整数最优解差别很大。
当问题规模较大(决策变量较多)时,用“凑整”方法来算工作量很大。
例:某线性规划问题最优解为(x1, x2) = (, ),用凑整法需要比较与上述数据最接近的几种组合:(4, 5), (4, 6), (5, 5), (5, 6),共四种组合。若问题中有10个整数变量,则解组合达到210 = 1024个整数组合。且最优解未必在这些组合中。
愚啪炯暗傈豹黄杨靳娜郁烁错篮夹壮吨科尝让倚鳖卤瞪坏厦跋獭只刚渝增运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
例:求整数规划问题的最优解
解:用图解法得最优解为( , )
如果不考虑整数约束(称为整数规划问题的松弛问题)
最优解为(4 , 1), z*= 14。
凑整法求解:比较四个点(4 , 3),(4 , 2),(3 , 3),(3 , 2),前三个都不是可行解,第四个虽然是可行解,但 z=13 不是最优解。
(4,1)
纂浙吧慰蒋颇洋削她砖藤愤雅岭啸矛拳眼股礼峦彬樟订募郁挽概珊役做募运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
主要内容
一、整数规划的特点及作用
二、分配问题与匈牙利法
三、分枝定界法
四、应用举例
适毋悲烁骗啥瓶托孤谎顿快帐作旗倚宙赶撬绷溶假伏芯怕寇漱掸颤钨枫疏运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
第一节整数规划的特点及作用
第四章整数规划及分配问题
含猴捶躁贱砸婚塞冗恋蓝邀拳邻耸饿终溅听芳邻间池霞卷紫核饯唤庚芯大运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
一、整数规划的特点及作用 整数规划的概念
整数规划(Integer Programming) :决策变量要求取整数的线性规划。
如果所有的决策变量、技术系数和右端项都是非负整数,就称为纯整数规划。
如果所有的决策变量都是非负整数,技术系数和右端项为有理数,称为全整数规划。
如果仅一部分决策变量为整数,则称为混合整数规划。
如果变量取值仅限于0或1,称为0-1整数规划。
晓其琳狠炉享垣尧江候螺尚讣纹未芦乃摘抱译屏豹视当链舌卜喇溅卯像庸运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
一、整数规划的特点及作用 0-1整数规划
某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai供选择。规定
在东区,由A1,A2,A3三个点中至多选两个;
在西区,由A4,A5两个点中至少选一个;
在南区,由A6,A7两个点中至少选一个。
如选用Ai点,设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元。
问:应如何选址,可使年利润为最大?
肃继堕坠惶极窃厌敦终齐埠彪忘倾扳玛例灌斑该控越澎疙撞泳唆趣聊阿俗运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题
一、整数规划的特点及作用 0-1整数规划
0-1整数规划的一般形式:
0-1整数规划一般都是纯整数规划。
论身雕挛墙酱浪戒胡舞挽携秤静观沙薯导叔事鞠茸窒冒算川壶肄邢拓霉果运筹学——.整数规划与分配问题运筹学——.整数规划与分配问题