第六章---运筹学-整数规划案例
第六章整数规划
用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。
1、 max z=3x1+2x2
. 2x1+3x2≤12
2x1+x2≤9
x1、x2≥0
解：
2、 min f=10x1+9x2
. 5x1+3x2≥45
x1≥8
x2≤10
x1、x2≥0
求解下列整数规划问题
1、 min f=4x1+3x2+2x3
. 2x1-5x2+3x3≤4
4x1+x2+3x3≥3
x2+x3≥1
x1、x2、x3=0或1
解：最优解（0，0，1），最优值：2
2、 min f=2x1+5x2+3x3+4x3
. -4x1+x2+x3+x4≥2
-2x1+4x2+2x2+4x2≥4
x1+x2-x2+x2≥3
x1、x2、x3、x3=0或1
解：此模型没有可行解。
3、max Z=2x1+3x2+5x3+6x4
. 5x1+3x2+3x3+x4≤30
2x1+5x2-x2+3x2≤20
-x1+3x2+5x2+3x2≤40
3x1-x2+3x2+5x2≤25
x1、x2、x3、x3=正整数
解：最优解（0，3，4，3），最优值：47
4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+
5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19
约束条件x1 + x2+x3≤30
x4+ x5＋ x6-10 x16≤0
x7+ x8＋ x9-20 x17≤0
x10+ x11＋ x12-30 x18≤0
x13+ x14＋ x15-40 x19≤0
x1 + x4+ x7+x10+ x13＝30
x2 + x5+ x8+x11+ x14＝20
x3 + x6+ x9+x12+ x15＝20
x i为非负数（i=1,2…..8）
x i为非负整数（i=9,10…..15）
x i为为0－1变量（i=16,17…..19）
解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860
一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：
公司办公会决定选择原则如下：
（1）B5、B3和B7只能选择一个。
（2）选择了B1或B14就不能选B6。
（3）B2、B6、B1、B12，最多只能选两个。
（4）B5、B7、B10、B8，最少要选两个。
问应选择哪几个点，使总的建店费用为最低
解：数学模型：
min f＝ x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8+ x9+3 x10+ x11+ x12+ x13+ x14
. x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8
x3+ x5-2 x7=2
x1+ x6=1
x6+ x14=1
x1+x2+x6+x12≤2
x5+x7+x8+x10≥2
x i≥0且x i为0－1变量，i＝1，2，3， (14)
最优解：（1，1，1，1，1，0，0，0，1，0，0，0，1，1）最优值：。
即：B1，B2，B3，B4,B5,B9,B13,B14选中，建店的最低费用万元。
有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（A、B、C、D），请按以下要求求解指派问题。
1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少
每人完成各项工作的所需时间小时
2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最多
解：1
线性规划数学模型：
min f=18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21x10+12x11+15x12+20x13
. x1+x2+x3 =1
x4+x5+x6=1
x7+x8+x9+x10=1
x11+x12+x13=1
x1+x7+x11 =1
x2+x4+x8 +x12 =1
x5+x9+x13 =1
x3+x6+x10 =1
x i≥0且x i为0－1变量，i＝1，2，3， (13)
最优解：（0，1，0，0，1，0，0，0，0，1，1，0，0，），最优值：65。
即：给甲分配工作B，给乙分配工作C，给丙分配工作D，给丁分配工作A，所用最少的时间为65小时。
2、总的创利为最多问题
线性规划数学模型：
max Z =41+52+73+94+75+5x6+6x7+8x8+3x9+4x10+3x11+5x12+7x13+6x14+8x15+8x16
. x1+x2+x3 +x4 =1
x5+x6+x7+x8=1
x9+x10+x11+x12=1
x13+x14+x15+x16=1
x1+x5+x9 +x13 =1
x2+x6+x10+x14=1
x3+x7+x11+x15=1
x4+x8+x12+x16=1
x i≥0且x i为0－1变量，i＝1，2，3，…，16
最优解：（0，0，0，1，1，0，0，0，0，1，0，0，0，0,1,0），最优值：28。
即：给甲分配工作D，给乙分配工作A，给丙分配工作B，给丁分配工作C，所创最多的利润为28元。
某企业在A1地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2地建厂的固定成本为万元，在A3地建厂的固定成本为30万元，在A4地建厂的固定成本为万元，在A5地建厂的固定成本为50万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运价（万元/万箱）如下表所示。
（1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小；
（2）如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂
解（1）
整数规划数学模型：
min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x40+7 x11+
5 x12 +10 x13+4 x14+2 x15+ x16+30x17+ x18 +50 x19
. x1 + x2+x3≤3
x4+ x5＋ x6- x16≤0
x7+ x8＋ x9-2x17≤0
x10+ x11＋ x12-3x18≤0
x13+ x14＋ x15-4x19≤0
x1 + x4+ x7+x10+ x13＝3
x2 + x5+ x8+x11+ x14＝2
x3 + x6+ x9+x12+ x15＝2
x i为非负整数(i=1,2…..15)
x i为0－1变量(i=16,17…..19)
最优解：（3，0，0，0，0，0，0，0，0，0，0，0，0，2，2，0，0，0，1）最优值：86。
即：安排A1地到B1地3万箱，A5地到B2，B3地各2万箱，选中A5地。
(2) 我们只要在以上模型上加上一个约束条件：x16+ x17=1，就得到了问题（2）的数学模型：
min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x40+7 x11+
5 x12 +10 x13+4 x14+2 x15+ x16+30x17+ x18 +50 x19
. x1 + x2+x3≤3
x4+ x5＋ x6- x16≤0
x7+ x8＋ x9-2x17≤0
x10+ x11＋ x12-3x18≤0
x13+ x14＋ x15-4x19≤0
x1 + x4+ x7+x10+ x13＝3
x2 + x5+ x8+x11+ x14＝2
x3 + x6+ x9+x12+ x15＝2
x16+ x17=1
x i为非负整数(i=1,2…..15)
x i为0－1变量(i=16,17…..19)
最优解：（0，1，2，0，1，0，0，0，0，3，0，0，0，0，0，1，0，1，0）
最优值：94。
即：安排A1地到B2地1万箱，B3地2万箱
A2地到B2地1万箱
A4地到B1地3万箱
A4地到B1地3万箱
选中A2，A4两地。
某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州—北京飞行时间为2小时；北京—广州飞行时间为3小时；广州—兰州飞行时间为3小时；这些航线每天班机起飞与到达时间如下表：
设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要2小时的时间准备。确定一个使总的停留费用损失为最小的方案。
解：现在有两本题需注意的两个问题
1、三个城市间的飞行，航班的安排分别是在三个城市中完成的；
2、到站的航班必须2小时后才能起飞。
这是一个指派问题，
（1）城市兰州
效益表：
指派结果：
（2）城市北京
指派结果：
（3）城市广州
收益表：
指派结果：
用的最少时间为117 a。
某地区有两个镇，它们每周分别产生700吨和1200吨固体废物。现拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理。两城镇至各处理场所的运输费用、
解：
混合整数规划问题数学模型：
min f=+21x2+21x3+17x4+++3850y1+1150y2+1920y3
. x1+x2+x3=700
x4+x5+x6=1200
x1+x4-1000y1≤0
x2+x5-500y2≤0
x3+x6-1300y3≤0
x i (i=1,2….6) y1、y2、y3=0—1
结果：
即两城镇处理固体废物的方案
城镇1焚烧100吨，掩埋600吨
城镇2填海500吨，掩埋700吨
总的最小费用：46170元。
某建设公司有四个正在建设的项目，按目前所配给的人力、设备和材料，这四个项目将分别可以在15、20、18和25周内完成，管理部门希望提前完工，决定追加35000元资金分配给这四个项目，并规定追加资金只能以5000元为单位进行分配。对于各个项目，资金追加后的工期变化情况如下表：
解：
本问题的0-1整数规划数学型：
min f = 15x1+20x2+18x3+25x4+12x5+16x6+15x7+21x8+10x9+13x10+12x11
+18x12+8x13+11x14+10x15+16x16+7x17+9x18+9x19+14x20+6x21
+8x22+8x23+12x24+5x25+7x26+7x27+11x28+4x29+7x30+6x31+10x32
. x1+x5+x9+x13+x17+x21+x25+x29=1
x2+x6+x10+x14+x18+x22+x26+x30=1
x3+x7+x11+x15+x19+x23+x27+x31=1
x4+x8+x12+x16+x20+x24+x28+x32=1
0x1+1x5+2x9+3x13+4x17+5x21+6x25+7x29+
0x2+1x6+2x10+3x14+4x18+5x22+6x26+7x30+
0x3+1x7+2x11+3x15+4x19+5x23+6x27+7x31+
0x4+1x8+2x12+3x16+4x20+5x24+6x28+7x32≤7
x i≥0 (i=......32)
用模板求解结果见《第六章习题》
求得最小时间为55周，比不追加投资节省了（15+20+18+25）-55=23周。
某公司要生产2000件某种产品，这种产品可利用设备A、B、C中的任意一种来加工，但若要使用这三种设备中的任意一种，都需要垫付相应的生产准备费（若不用该设备就不用垫付）
解：
本问题的混合整数规划数学模型：
min f=7x1+2x2+5x3+100y1+200y2+300y3
. ++x3≤2500
x1+x2+x3=2000
x1-800y1≤0
x2-1200y2≤0
x3-1400y3≤0
x1、x2、x3≥0
y1、y2、y3=0,1
其结果为：分别安排在设备B，C上加工625，1375件，最低费用为8625元。
运筹学整数规划补例样本
运筹学难点辅导材料 整数规划补例 1、 对( IP) 整数规划问题12 12121212max 14951631..0,0,z x x x x x x s t x x x x =++≤?? -+≤?? ≥≥???为整数, 问用先解相应的线性规划然后凑 整的办法能否求到最优整数解? 再用分支定界法求解。 解 先不考虑整数约束, 得到线性规划问题( 一般称为松弛问题LP) 12 12121 2max 14951..6310,0 z x x x x s t x x x x =++≤?? -+≤??≥≥?用图解法求出最优解12310 ,23x x ==且296z =。 如用”舍入取整法”凑整可得到四个点, 即( 1, 3) 、 ( 2, 3) 、 ( 1, 4) 、 ( 2, 4) 。代入约束条件发现她们都不是可行解。可将可行域内的所有整数点一一列举( 完全枚举法) , 本例中( 2, 2) 、 ( 3, 1) 点为最大值4z =。 令() 0310,23T X ??= ??? 及最优值()0 296z =。可行域记为D, 显然()0X 不是整数解。 定界: 取()0296z z == , 再用视察法找一个整数可行解()0,0T X '=及0z '=, 取0z z '==, 即*2906 z ≤≤ 分支: ( 关键点, 在B 的最优解中任选一个不符合整数条件的变量j x , 其值为 j b , 构造两个约束条件1,j j j j x b x b ????≥+≤????, 这里用了取整函数呵! ) 任取最 优解中一个不为整数的变量值, 例如132x = , 根据312?? =???? , 构造两个约束条件,
第六章---运筹学-整数规划案例
第六章整数规划 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 . 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 . 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0
求解下列整数规划问题 1、 min f=4x1+3x2+2x3 . 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 . -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解：此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 . 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5＋ x6-10 x16≤0 x7+ x8＋ x9-20 x17≤0 x10+ x11＋ x12-30 x18≤0 x13+ x14＋ x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 x i为非负数（i=1,2…..8） x i为非负整数（i=9,10…..15） x i为为0－1变量（i=16,17…..19） 解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：
运筹学整数规划例题
练习4.9 连续投资问题 某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限. 项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元. 项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元. 项目D:五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益. (1) x 为项目各年月初投入向量。 (2) ij x 为 i 种项目j 年的月初的投入。 (3) 向量c 中的元素 ij c 为i 年末j 种项目收回本例的百分比。 (4) 矩阵A 中元素 ij a 为约束条件中每个变量ij x 的系数。 (5) Z 为第5年末能拥有的资金本利最大总额。 因此目标函数为 4325max 1.15 1.28 1.40 1.06A B C D Z x x x x =+++ 束条件应是每年年初的投资额应等于该投资者年初所拥有的资金. 第1年年初该投资者拥有10万元资金,故有 11100000A D x x +=. 第2年年初该投资者手中拥有资金只有()116%D x +,故有 22211.06A C D D x x x x ++=. 第3年年初该投资者拥有资金为从D 项目收回的本金: 21.06D x ,及从项目A 中第1年投资收回的本金: 11.15A x ,故有 333121.15 1.06A B D A D x x x x x ++=+ 同理第4年、第5年有约束为 44231.15 1.06A D A D x x x x +=+, 5341.15 1.06D A D x x x =+
运筹学整数规划
实验报告 课程名称：___ 运筹学 ____ 项目名称：整数规划问题_ 姓名：__专业：、班级：1班学号：同组成员：_ __ 1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。 2、若是单人单组实验，同组成员填无。
例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。假设值班人员分别在各时间段开时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名班人员？ 解： 根据题意，假设用i x（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数， 每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：目标函数： i i x z 6 1 min = ∑ = 约束条件： ? ? ? ? ? ? ? ? ? ? ? = ≥） 且为整数（6 ... 1 ,0 x 30 >= x6 + x5 20 >= x5 + x4 50 >= x4 + x3 60 >= x3 + x2 70 >= x2 + x1 60 >= x6 + x1 i i model: sets: num/1,2,3,4,5,6/:b,x; endsets data: b=60,70,60,50,20,30; enddata [obj]min=@sum(num(i):x(i)); x(1)+x(6)>=60; x(1)+x(2)>=70; x(2)+x(3)>=60; x(3)+x(4)>=50; 2注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加。
解： 目标函数： y3*2000-y2*2000-y1*5000-x3*200)-(300+x2*30)-(40+x1*280)-(400=z max 约束条件：???????y3 *300<=x3*2y2*300<=x2*0.5y1*300<=x1*32000<=x3*4+x2+x1*5 model : sets : num/1,2,3/:x,y; endsets [obj]max =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)-2000*y(2)-2000*y(3); 5*x(1)+x(2)+4*x(3)<=2000; 3*x(1)<=300*y(1); 0.5*x(2)<=300*y(2); 2*x(3)<=300*y(3); @for (num(i):x(i)>=0;@bin (y(i));); end
运筹学经典案例
运筹学经典案例 案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的P.M.S.Blachett为首，组织了一个小组，代号为“Blachett 马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团”是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。
运筹学经典案例
案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的为首，组织了一个小组，代号为“Blachett马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团” 是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。
《管理运筹学》第三版案例题解
《管理运筹学》案例题解 案例1：北方化工厂月生产计划安排 解：设每月生产产品i （i=1，2，3，4，5）的数量为X i ，价格为P 1i ，Y j 为原材料j 的数量，价格为P 2j ，a ij 为产品i 中原材料j 所需的数量百分比，则： 5 10.6j i ij i Y X a ==∑ 总成本：TC=∑=15 1 2j j j P Y 总销售收入为：5 11 i i i TI X P ==∑ 目标函数为：MAX TP （总利润）=TI-TC 约束条件为： 10 30 24800215 1 ?? ?≤∑=j j Y X 1+X 3=0.7∑=5 1 i i X X 2≤0.05∑=5 1 i i X X 3+X 4≤X 1 Y 3≤4000 X i ≥0,i=1,2,3,4,5 应用计算工具求解得到： X 1=19639.94kg X 2=0kg X 3=7855.97kg X 4=11783.96kg X 5=0kg 最优解为：348286.39元
案例2：石华建设监理工程师配置问题 解：设X i 表示工地i 在标准施工期需要配备的监理工程师，Y j 表示工地j 在高峰施工期需要配备的监理工程师。 约束条件为： X 1≥5 X 2≥4 X 3≥4 X 4≥3 X 5≥3 X 6≥2 X 7≥2 Y 1+Y 2≥14 Y 2+Y 3≥13 Y 3+Y 4≥11 Y 4+Y 5≥10 Y 5+Y 6≥9 Y 6+Y 7≥7 Y 7+Y 1≥14 Y j ≥ X i （i=j ，i=1,2,…,7） 总成本Y 为： Y=∑=+7 1)12/353/7(i i i Y X 解得 X 1=5；X 2=4；X 3=4；X 4=3；X 5=3；X 6=2；X 7=2； 1Y =9；2Y =5；3Y =8；4Y =3；5Y =7；6Y =2；7Y =5; 总成本Y=167.
运筹学第4章整数规划习题.doc
第四章 整数规划 4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料B ，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 解：设生产甲、乙这两种设备的数量分别为x 1、x 2，由于是设备台数，则其变量都要求为整数，建立模型如下： 2123max x x z += ????? ? ?≥≤+≤+为整数 21212121,0,5 .45.01432x x x x x x x x 4.2 2197max x x z += ??? ??≥≤+≤+-且为整数 0,35 76 3.212121x x x x x x t s 割平面法求解。（下表为最优表） 线性规划的最优解为： 63max ,0,2/7,2/94321=====z x x x x 由最终表中得： 2 7 221227432=++ x x x ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 132********+=++x x x 移项后得： ①②③④ ①②③
即： 2 1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。 由x 1行得： 7 32 7171541= -+ x x x 将系数和常数项分解成整数和非负真分数之和： 74476715541+=+-+x x x x 得到新的约束条件： 74 767154-≤--x x 7 47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 则最优解为3,421 ==x x ，最优目标函数值为z *=55。 4.3 max z ＝4x 1＋3x 2＋2x 3
运筹学实例分析及lingo求解
运筹学实例分析及lingo 求解 一、线性规划 某公司有6个仓库，库存货物总数分别为60、55、51、43、41、52，现有8个客户各要一批货，数量分别为35，37，22，32，41，32，43，38。各供货仓库到8个客户处的单位货物运输价见表 试确定各仓库到各客户处的货物调运数量，使总的运输费用最小。 解：设 ij x 表示从第i 个仓库到第j 个客户的货物运量。ij c 表示从第i 个仓库到第 j 个客户的单位货物运价，i a 表示第i 个仓库的最大供货量，j d 表示第j 个客户的订货量。 目标函数是使总运输费用最少，约束条件有三个：1、各仓库运出的货物总量不超过其库存数2、各客户收到的货物总量等于其订货数量3、非负约束 数学模型为： ∑∑===6 18 1)(min i j ij ij x c x f ????? ??????≥===≤∑∑==08,,2,1,6,2,1,,. .6 1 8 1ij j i ij i j ij x j d x i a x t s ΛΛ 编程如下： model : Sets : Wh/w1..w6/:ai; Vd/v1..v8/:dj;
links(wh,vd):c,x; endsets Data: ai=60,55,51,43,41,52; dj=35,37,22,32,41,32,43,38; c=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3; Enddata Min=@sum(links(i,j):c(i,j)*x(i,j)); @for(wh(i):@sum(vd(j):x(i,j))<=ai(i)); @for(vd(j):@sum(wh(i):x(i,j))=dj(j)); end Global optimal solution found. Objective value: Total solver iterations: 0 Variable Value Reduced Cost AI( W1) AI( W2) AI( W3) AI( W4) AI( W5) AI( W6) DJ( V1) DJ( V2) DJ( V3) DJ( V4) DJ( V5) DJ( V6) DJ( V7) DJ( V8) C( W1, V1) C( W1, V2) C( W1, V3) C( W1, V4) C( W1, V5) C( W1, V6) C( W1, V7)
运筹学实验报告四整数规划
2018-2019学年第一学期 《运筹学》 实验报告（四） 班级：交通运输171 学号： 1000000000 姓名： ***** 日期： 2018.11.22
实验一： 用Lingo 软件求解下列整数规划问题（要求附程序和结果） 12 121212max 2506221 0,1,2i z x x x x x x x x x i =++≤?? -+≤?? +≤??≥=?且取整数 12312323123123 123max 232 45 2244 ,,01 z x x x x x x x x x x x x x x x x x =+-++≤??+≤?? +-≤??+-≤?=??或 解：例题（左）解题程序及运行结果如下： sets : bliang/1,2/:x,a; yshu/1,2,3/:b; xshu(yshu,bliang):c; endsets data : a=2,1; b=5,0,21; c=1,1 -1,1 6,2; enddata max =@sum (bliang(i):a(i)*x(i)); @for (yshu(j):@sum (bliang(i):x(i)*c(j,i))<=b(j)); @for(bliang(i):@gin(x(i))); Global optimal solution found. Objective value: 7.000000 Objective bound: 7.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 3.000000 -2.000000 X( 2) 1.000000 -1.000000 A( 1) 2.000000 0.000000
第六章运筹学整数规划案例教材
第六章整数规划 6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 S.T. 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 S.T. 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0
6.2 求解下列整数规划问题 1、 min f=4x1+3x2+2x3 S.T. 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 S.T. -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解：此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 S.T. 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5＋x6-10 x16≤0 x7+ x8＋x9-20 x17≤0 x10+ x11＋x12-30 x18≤0 x13+ x14＋x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 x i为非负数（i=1,2…..8） x i为非负整数（i=9,10…..15） x i为为0－1变量（i=16,17…..19） 解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860 6.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：
运筹学实用案例分析过程
案例2 解：设工地ｉ在标准施工期需要配备的监理工程师为Xi, 工地j在高峰施工期需要配备的监理工程师为Yｉ. ７ 总成本: minZ=∑ ( 7Xi／3 + ３5Yj/12) i=1 x1≥5 Ｘ２≥4 X3≥4 X4≥3 X５≥3 X6≥２ Ｘ7≥2 Ｙ１+Y2≥1４ Ｙ2＋Y3≥１3 Y3+Y４≥1１ Y４＋Ｙ5≥１０ Y5+Y６≥9 Y6+Y７≥7 Y７+Ｙ1≥１4 Yj≥Ｘｉ (i＝j i,j=１,2,3,4,5,６,7) 结果如下：
解：穷举两种车可能的所有路线。 设x i为第i条路线的车的数量，那么： 求ｍｉn ｆ= 1２(x1+…+x１2) + 18(x13＋…+ｘ２１） 因为50个点属于A,３6个点属于B，2０个点属于C,所以约束条件是以上所有xｉ乘上它对应的路线中去各个点的数量的总和分别大于等于实际这些点的数量，因为表达式过于冗长，这里省略。 因为派去的车应该是整数,所以这是整数规划问题,运用软件求解。 最后得出结果： x9=4 ｘ12=3 x19=8 ｘ21=2 其余都等于零。 所以结果是派7辆２吨车,10辆４吨车。 路线如表格,这里不赘述。
解:设ｘiｊ表示在i地销售的j规格的东西。其中i=1到6对应福建广东广西四川山东和其他省区，j=1和2对应９0０-1６０0和３50-8０0。 求mａx f＝270x11+ ２４0x21+ ２９５x3１+３００ｘ４1＋242ｘ５1 +260x61+63ｘ1２+60 x22 + 6０x32 +64x４2 +5９x52 +57ｘ62– 14５000０ 在下图软件操作中,用x1到x１２代表以上的未知数。 约束条件如上 运用软件求解，结果为: 由于软件中没有添加– 14５0000， 所以最大利润为：５７310０0元。