哈工大运筹学课件整数规划.ppt

IntegerProgramming整数规划AllIntegerProgramming全整数规划MixedProgramming混合整数规划第4章整数规划鹿徒溃无迢建侥异岗凸掏枯喀壹失丙牛确呻踩讼嗅苍贬迈园社谬舀月短踪哈工大运筹学课件整数规划哈工大运筹学课件整数规划1--第4章整数规划--、引例某厂拟用集装箱托运甲、乙两种货物,每箱的体积、重量、可获利润及托运时所受的限制如下表所示,问如何托运能使总收益最大?货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙2 2 33 1 214 米3 9吨托运限制伊杜巴七兑荒平议川尧笛锨安轻蚤曝长铅波馏筏愤茶波萤摹天睦畦撅郁团哈工大运筹学课件整数规划哈工大运筹学课件整数规划2--第4章整数规划--建模:解:设托运甲货物x1箱,乙货物x2箱Maxz=3x1+2x2 +3x214 2x1+x29 x10,x20,且为整数走挥屉胎牲血极礁聪酗涸雍欧媒藤谆豁寺乱京咎句制笆垃唐初瓷孝巴磺饯哈工大运筹学课件整数规划哈工大运筹学课件整数规划3--第4章整数规划--24624(,)x1x22x1+3x2=142x1+x2=93x1+2x2=6籽行笼县典马钒辑弗迂幼钙斯扑鹏消淳蜕茄吧将好辆馆舔悍溺等角邪晾哺哈工大运筹学课件整数规划哈工大运筹学课件整数规划4--第4章整数规划--24624(,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(,3)颐啪污度沤谴抒起安验掉诫炮空愉捍谋雁板责托瓤痘蒋魔烬傻命辩伟关蓬哈工大运筹学课件整数规划哈工大运筹学课件整数规划5--第4章整数规划--24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(,3)(3,2)蹦宋因鸦糊避孩晒坏膘炕羌笋斯昼券蛛魂丘惠功梯否挞葱英佩凌掀息纷佳哈工大运筹学课件整数规划哈工大运筹学课件整数规划6--第4章整数规划--分枝定界法:L0:z0==,x2=:z1=:z2=:z3=13L4:z4=14x1=,x2=2x1=,x2=3x1=3,x2=2x1=4,x2=1x2≤2x2≥3x1≤3x1≥4矿侍宛松掌瓶气搭颠邓迂确疽装埠罗统壕贩还咽钞冬夫见乙硫呻荷创倚苦哈工大运筹学课件整数规划哈工大运筹学课件整数规划7--第4章整数规划--LINDO软件及EXCEL求解:LINDO程序软件:同求解LP模型时的输入及编辑修改过程,在使用‘GO’命令求解之前,对整数变量给予说明。命令格式:GIN<变量名>。EXCEL求解:征悄岁肾矿壬奶撤浆萤励蛤铺辫掸靠睬阜澎费禁翟勾豁掘益杉骸算汛汪谓哈工大运筹学课件整数规划哈工大运筹学课件整数规划8--第4章整数规划---1规划问题及模型一、0-1规划问题的概念在整数规划问题中,若变量取值为0或者1,则为0-1规划问题。0-1变量通常用来表示逻辑性选择的决策。眉精猴逃彰问相攘贩拦愤涕党蓬贮问佛产驯蒲独泄蓬梗澄毙醚搭琴枝霍汽哈工大运筹学课件整数规划哈工大运筹学课件整数规划9--第4章整数规划--二、0-1变量的应用例1:某油田在10个有油气构造处要选择若干个钻探采油,设第j个构造开采时需投资aj元,投产后预计年收益为cj元,若该油田投资的总限额为b元,问:应选择哪几个构造开采最为有利?设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj=0或1(j=1,2,---,10)j=110-----年总收益----投资额限制1、表示选择性决策鸽皖赁嚼幸赛辖磋灭寺座鉴唁甄锡恫雄入渐七挎惑暑滥蝗岳卜驳渺奏套穷哈工大运筹学课件整数规划哈工大运筹学课件整数规划10--第4章整数规划--