线性规划例子.pptx

1例1：背包问题 一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤，如何安排才能使得所携带物品最具重要性。第1页/共14页2序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备重量重量5 55 52 26 612122 24 4重要重要系数系数20201515181814148 84 41010第2页/共14页3解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:Max Z=20 x1+15x2+18x3+14x4 +8x5+4x6+10 x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7 25xi=1或xi=0 i=1,2,.7第3页/共14页4例：某公司在不同的工厂生产3种钢材。下表给出了生产1吨钢材（不考虑型号）需要的时间以及每个工厂的成本。每周每种型号(1、2和3)的钢材都必须生产130吨。每家工厂每周的工作时间为40小时。如何安排生产可使生产成本最小。工厂工厂成本成本时间时间(min)钢材钢材1钢材钢材2钢材钢材3160402820250303016343202020例2：生产计划问题第4页/共14页5每个工厂每周工作40小时，即2400分钟。因此3个工厂每周可生产的钢材如下：分别可生产的钢材 工厂1：2400/20120吨工厂2：2400/16150吨工厂3：2400/20120吨第5页/共14页6设xij为第i个工厂生产钢材j的数量满足运输问题特征！第6页/共14页7转化为运输问题的图表示法第7页/共14页8求得生产方案为工厂工厂钢材钢材1钢材钢材2钢材钢材3产量产量1120120210101301503120120需求需求130130130最优总生产成本为14660第8页/共14页9每种钢材需要130吨每家工厂每周可工作40小时假设生产1吨钢材需要的时间取决于钢材的型号以及生产的工厂。是否能描述成运输问题？工厂工厂时间时间钢材钢材1钢材钢材2钢材钢材3115121521515203101015工厂工厂成本成本钢材钢材1钢材钢材2钢材钢材3160402825030303432020问题改为形式1：第9页/共14页10设xij为第i个工厂生产钢材j的数量不满足运输问题特征！第10页/共14页11每种钢材需要130吨每家工厂每周可工作40小时对工厂3来说，如果要产生钢材1就必需生产钢材2应如何描述模型？问题改为形式2：工厂工厂成本成本时间时间(min)钢材钢材1钢材钢材2钢材钢材3160402820250303016343202020第11页/共14页12新的约束相当于要表达 if x310 then x320假设约束条件假设有一个足够大的M，使得x31 M-x32 M引入如下约束x31My-x32M(1-y)y=0或1由于工厂3的最大生产能力为120吨，故取M为120设xij为第i个工厂生产钢材j的数量第12页/共14页13故模型为第13页/共14页14感谢您的观看！第14页/共14页