搜索
第六章整数规划6.1用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。1、maxz=3x1+2x2S.T.2x1+3x2≤122x1+x2≤9x1、x2≥0解：2、minf=10x1+9x2S.T.5x1+3x2≥45x1≥8x2≤10x1、x2≥06.2求解下列整数规划问题1、minf=4x1+3x2+2x3S.T.2x1-5x2+3x3≤44x1+x2+3x3≥3x2+x3≥1x1、x2、x3=0或1解：最优解（0，0，1），最优值：22、minf=2x1+5x2+3x3+4x3S.T.-4x1+x2+x3+x4≥2-2x1+4x2+2x2+4x2≥4x1+x2-x2+x2≥3x1、x2、x3、x3=0或1解：此模型没有可行解。3、maxZ=2x1+3x2+5x3+6x4S.T.5x1+3x2+3x3+x4≤302x1+5x2-x2+3x2≤20-x1+3x2+5x2+3x2≤403x1-x2+3x2+5x2≤25x1、x2、x3、x3=正整数解：最优解（0，3，4，3），最优值：474、minz=8x1+4x2+3x3+5x4+2x5＋3x6＋4x7＋3x8+4x9+9x10+7x11+5x12+10x13+4x14+2x15+175x16+300x17+375x18+500x19约束条件x1+x2+x3≤30x4+x5＋x6-10x16≤0x7+x8＋x9-20x17≤0x10+x11＋x12-30x18≤0x13+x14＋x15-40x19≤0x1+x4+x7+x10+x13＝30x2+x5+x8+x11+x14＝20x3+x6+x9+x12+x15＝20xi为非负数（i=1,2…..8）xi为非负整数（i=9,10…..15）xi为为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），最优值：8606.3一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：店名B1B2B3B4B5B6B7B8B9B10B11B12B13B14费用(万元)1.21.51.72.13.31.22.82.51.93.02.42.42.11.6公司办公会决定选择原则如下：（1）B5、B3和B7只能选择一个。（2）选择了B1或B14就不能选B6。（3）B2、B6、B1、B12，最多只能选两个。（4）B5、B7、B10、B8，最少要选两个。问应选择哪几个点，使总的建店费用为最低？解：数学模型：minf＝1.2x1+1.5x2+1.7x3+2.1x4+3.3x5+1.2x6+2.8x7+2.5x8+1.9x9+3x10+2.4x11+2.4x12+2.1x13+1.6x14S.T.x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8x3+x5-2x7=2x1+x6=1x6+x14=1x1+x2+x6+x12≤2x5+x7+x8+x10≥2xi≥0且xi为0－1变量，i＝1，2，3，…，14。最优解：（1，1，1，1，1，0，0，0，1，0，0，0，1，1）最优值：15.4。即：B1，B2，B3，B4,B5,B9,B13,B14选中，建店的最低费用15.4万元。6.4有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（A、B、C、D），请按以下要求求解指派问题。1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少？每人完成各项工作的所需时间小时是工作否分工人配工作A工作B工作C工作D甲1816-19乙-201620丙19181721丁121520-2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最多？所工作创利工人益工作A工作B工作C工作D甲4579乙7568丙3435丁7688解：1、消耗时间为最少问题线性规划数学模型：minf=18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21x10+12x11+15x12+20x13S.T.x1+x2+x3=1x4+x5+x6=1x7+x8+x9+x10=1x11+x12+x13=1x1+x7+x11=1x2+x4+x8+x12=1x5+x9+x13=1x3+x6+x10=1xi≥0且xi为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、总的创利为最多问题线性规划数学模型：maxZ=41+52+73+94+75+5x6+6x7+8x8+3x9+4x10+3x11+5x12+7x13+6x14+8x15+8x16S.T.x1+x2+x3+x4=1x5+x6+x7+x8=1x9+x10+x11+x12=1x13+x14+x15+x16=1x1+x5+x9+x13=1x2+x6+x10+x14=1x3+x7+x11+x15=1x4+x8+x12+x16=1xi≥0且xi为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元。6.5某企业在A1地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2地建厂的固定成本为17.5万元，在A3地建厂的固定成本为30万元，在A4地建厂的固定成本为37.5万元，在A5地建厂的固定成本为50万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运价（万元/万箱）如下表所示。运销地输价产地格B1B2B3固定成本（万元）产量（万箱）A184303A252317.51A3434302A497537.53A51042504销量（箱）322（1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小；（2）如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂？解（1）整数规划数学模型：minz=8x1+4x2+3x3+5x4+2x5＋3x6＋4x7＋3x8+4x9+9x40+7x11+5x12+10x13+4x14+2x15+17.5x16+30x17+37.5x18+50x19S.T.x1+x2+x3≤3x4+x5＋x6-x16≤0x7+x8＋x9-2x17≤0x10+x11＋x12-3x18≤0x13+x14＋x15-4x19≤0x1+x4+x7+x10+x13＝3x2+x5+x8+x11+x14＝2x3+x6+x9+x12+x15＝2xi为非负整数(i=1,2…..15)xi为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）的数学模型：minz=8x1+4x2+3x3+5x4+2x5＋3x6＋4x7＋3x8+4x9+9x40+7x11+5x12+10x13+4x14+2x15+17.5x16+30x17+37.5x18+50x19S.T.x1+x2+x3≤3x4+x5＋x6-x16≤0x7+x8＋x9-2x17≤0x10+x11＋x12-3x18≤0x13+x14＋x15-4x19≤0x1+x4+x7+x10+x13＝3x2+x5+x8+x11+x14＝2x3+x6+x9+x12+x15＝2x16+x17=1xi为非负整数(i=1,2…..15)xi为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两地。6.6某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州—北京飞行时间为2小时；北京—广州飞行时间为3小时；广州—兰州飞行时间为3小时；这些航线每天班机起飞与到达时间如下表：航班号起飞城市起飞时间到达城市到达时间1011兰州6:00北京8:001012兰州12:00北京14:001013兰州18:00北京20:002011兰州7:00广州10:002012兰州9:00广州12:001021北京7:00兰州9:001022北京10:00兰州12:001023北京17:00兰州19:002021广州14:00兰州17:002022广州17:00兰州20:003011北京5:00广州8:003012北京9:00广州12:003013北京13:00广州16:003014北京18:00广州22:003021广州6:00北京9:003022广州10:00北京13:003023广州14:00北京17:003024广州18:00北京21:00设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要2小时的时间准备。确定一个使总的停留费用损失为最小的方案。解：现在有两本题需注意的两个问题1、三个城市间的飞行，航班的安排分别是在三个城市中完成的；2、到站的航班必须2小时后才能起飞。这是一个指派问题，（1）城市兰州效益表：起飞10112011201210121013起飞到达202110222021102310234413061691211004843611961441215364412561961699536361289256813662552948411111到达11111指派结果：起飞10112011201210121013起飞20211022202110231023--1-----1-----11-----1---11111到达11111用的最少时间为527a。（2）城市北京效益表：起飞3011102130121022301310233014起飞1011302130221012302310133024441400256225144816452948432428919612110062557640036125616914446254414002891961692516576576400289256816416165764414001008125815294844411111111到达1111111指派结果：起飞3011102130121022301310233014起飞1011302130221012302310133024----1-------1-------11-------1--------1-----1----1111111到达到达到达到达1111111用的最少时间为476a。（3）城市广州收益表：起飞302130222021302320223024起飞301120112012301230133014484324324324196644576576576324144361644484256361644484256814925256253611006436364400111111到达111111指派结果：起飞302130222021302320223024起飞301120112012301230133014-----11--------1---1------1-------1-111111到达111111用的最少时间为117a。6.7某地区有两个镇，它们每周分别产生700吨和1200吨固体废物。现拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理。两城镇至各处理场所的