整数规划新.ppt

整数规划 作业讲解 工厂商品调拨(平衡运输问题) 数学模型 决策变量：每个工厂运往调拨站的货物数量 目标函数：运费最小 约束条件: s.t. 不平衡运输问题 数学模型 决策变量：每个产地运往销售地的货物数量 目标函数：运费最小 约束条件 客户定销问题 数学模型 约束条件： 整数规划简介 在工程设计和企业管理中，常会遇到要求决策变量取离散的非负整数值的线性规划问题。例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划问题，也经常简称为整数规划问题。 整数规划问题举例 问题：公交公司乘务人员安排问题 某昼夜服务的公交线路每天各时间区段内所需乘务人员如下： 分析问题建立模型 决策变量： 目标函数： 约束条件s.t. 求解模型 0-1整数规划问题 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xj 只取两个值0或1 瑞福公司的投资决策问题 瑞福公司是一家小型的风险投资公司，现在有800万元的资金可以投资。目前的投资方向可以有三个独立的项目可供选择，不同的项目投资额度与收益见下表。瑞福公司如何分配这些资金，以最佳的投资组合取得最大的投资收益？ 指派问题 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 指派问题举例 教师分配教学任务问题 某系有4名教师甲、乙、丙和丁，均有能力讲授A,B,C和D课程。由于经验上的原因，各名教师每周所需备课时间不同(见下表)。教务部门的要求是：每一门课程由一名教师担任，同时每一名教师只能担任一门课程的教学任务。针对以上情况，给出教师整体备课时间最小的排课方案。 教师分配教学任务问题的数学模型 决策变量 约束条件 ?矩阵中所有元素或被划去，或打上( )号，但打( )号的零元素个数少于4。为设法使得每一行都有一个打( )号的零元素，按下述步骤继续变换。 (1)从矩阵未被直线覆盖的数字中找出一个最小的数k； (2)对矩阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖的，令ui=k； (3)从矩阵中有直线覆盖的列，令vj=-k,对无直线覆盖的列，令vj=0； (4)从原矩阵的每个元素中分别减去ui和vj，得到一个新的矩阵 第五步：回到第三步，反复进行，直到矩阵每一行都有一个打( )号的零元素为止，即找到了最优分配方案。 练习： 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ * * 调拨站3 工厂3 工厂2 工厂1 调拨站4 调拨站2 调拨站1 工厂的运量和等于产量 非负约束 调拨站的运量和等于销量 销地B4 销地B3 产地A3 产地A2 产地A1 销地B5 销地B2 销地B1 产地的运量和等于产量 非负约束 销地的运量和小于等于销量 客户3 工厂3 工厂2 工厂1 客户4 客户2 客户1 决策变量:每个工厂销售给客户的产品数量 目标函数:工厂的获利最大 工厂的出售货物数量等于产量 出售4000件给客户1 出售3000件给客户2 至少1000件给客户3 客户3与4都想尽可能多购剩下的件数 非负约束 客户4最多购到4000件 30 2:00-6:00 6 20 22:00-2:00 5 50 18:00-22:00 4 60 14:00-18:00 3 70 10:00-14:00 2 60 6:00-10:00 1 所需人数 时间 班次 假设乘务人员分别在各时间区段一开始时上班，并连续工作八小时。该公交线路应该至少配备多少名乘务人员？ 14:00- 6:00- 10:00- 18:00- 22:00- 2:00- 每个时间段所需人数的限制 6:00-10:00（60） 10:00-14:00（70） 14:00-18:00（60） 18:00-22:00（50） 22:00-2:00（20） 2:00-6:00（30） 非负和整数约束 每个时间段开始上班的乘务人员人数 总的乘务人员最少 分支 定界法 整数规划的 求解算法 割平面法 52 74 98 7 53 51 50 45 40 26 4 0 丙项目 75 73 70 60 40 15 5 0 乙项目