第二讲-运输问题与整数规划介绍.pptVIP

§1 运输问题的数学模型 例子的线性规划模型 产销平衡问题的数学模型 表上作业法 一般运输问题的表格表示 产销不平衡问题的数学模型 产大于销问题的标准化 产销不平衡问题的数学模型 产小于销问题的标准化 转运问题 转运问题的数学模型 转运问题的标准化 应用举例 表1 生产数据 表2 柴油机实际成本cij(生产成本+存护成本) 目标函数： 约束条件: 当i＞j时，xij=0，令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型: 用表上作业法求解，可得多个最优方案，表4列出最优方案之一。即第Ⅰ季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台，用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货。Ⅳ季度生产10台，于当季交货。按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。 例2 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表。 又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求? 解 该公司所需配备船只分两部分。 (1) 载货航程需要的周转船只数。例如航线1，在港口E装货1天，E→D航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转船只需57条。各条航线周转所需船只数见表3. (2) 各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B。各港口每天余缺船只数的计算见表4。 目标: 使用来作周转的空船数达最少。 用表上作业法求出空船的最优调度方案见表7. §2 整数(线性)规划的一般形式 整数规划的分类 例1：集装箱货运问题 例1：模型 例2：背包问题 例2：模型 例3：选址问题 例4：互斥约束问题 例1：原来的模型 一般情况 整数规划的解法 指派问题、分配问题（0-1规划） 指派问题标准形式 例7 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作，使所需总时间最少? 表5-7 以上讨论限于极小化的指派问题。对极大化的问题，即求 所得最小解就是原问题的最大解， 因为 1. 纯整数规划：xj 全部取整数的线性规划。 2. 混合整数规划：xj 部分取整数的线性规划。 3. 0-1型整数规划：xj 只能取0或1的线性规划。 货物 体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱) 甲 5 2 20 乙 4 5 10 装运限制 24 13 例1: 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表。问两种货物各托运多少箱，可使获得利润为最大? 解：设X1 , X2 为甲、乙两货物各托运箱数 5X1+4X2 ? 24 2X1+5X2 ? 13 X1 , X2 ?0 X1 , X2为整数 Max Z = 20 X1 + 10 X2 纯整数规划问题 背包可再装入8单位重量，10单位体积物品 物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 0-1规划问题 解：Xi为是否带第 i 种物品 maxZ=20X1 + 30X2 +10X3+18X4 +15X5 5X1+3X2 +X3 +2X4 +4X5 ? 8 2X1+X2 +4X3