下载文档原格式
第三讲 整数规划⎧:0,j MaxZ CX AX b ST x ==⎨≥⎩x j 部分或全部为整数一、整数规划模型（12年，第一题，15分）一家公司打算在甲地、乙地或甲乙两地新建工厂，一地至多建一个工厂，并且在甲乙两地至多建一个仓库，仓库位置随工厂地点而定（即，如某地有工厂，该地可设仓库或不设仓库；但如该地不设工厂，则该地一定不设仓库），若总资本可用量为20（百万元），其他数据如下表所示，问一个最大化净现值收益的决策是什么？只建模不求解。
例：一辆货车的有效载重量是20吨，载货有效空间是35立方米。
现有六件货物可选择运输，每件货物的重量、体积及收入见下表。
另外，货物2和货物3不能混装；如果装载货物4，就必须装载货物5。
问怎样安排货物装载才能使收入最大，建立数学模型（不用求解）。
例：某大型企业每年需要进行多种类型的员工培训。
假设共有需要培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为a i，i=1,...,6，可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的最高培训人数为b j，j=1,...,5。
又设若选择了第1种培训方式，则第3种培训方式也要选择。
记x ij为第i种需求由第j种方式培训的人员数量，Z为培训总费用。
费用的构成包括固定费用和可变费用，第j种方式的固定培训费用为h j（与人数无关），与人数x ij相应的可变费用为c ij。
如果以成本费用为优化目标，试建立该培训问题的结构优化模型。
二、分支定界法（07年，第三题15分）设有整数规划问题如下，其松弛问题的最优解为（7/6，8/3），若要用分支定界法求其整数解，需要对其进行分支（仅作一级分支，不要求求解）。
是以x1为分之对象，用示意图表示其分支问题的可行域，并写出可行域的约束方程。
12121212542,0z x x x x x x x x =++≤-≥≥max s.t. 2 且为整数12121212121211121255B 42 B 4221,0,0z x x z x x x x x x x x x x x x x x x x =+=+⎧⎧⎪⎪+≤+≤⎪⎪⎪⎪-≥-≥⎨⎨⎪⎪≥≤⎪⎪⎪≥⎪≥⎩⎩max max s.t. 2s.t. 2问题1 问题2三、割平面法（11年，第五题，10分）对于MAX 型整数规划问题，若其松弛问题的最优单纯形表中有一行数据如表3。
