运筹学讲义(复习).ppt

1 第一章线性规划及单纯形法 线性规划主要解决有限资源的最佳分配问题决策变量 决策变量的取值要求非负 约束条件 存在一组决策变量构成的线性等式或不等式的约束条件 目标函数 存在唯一的线性目标函数 极大或极小 求解方法 图解法单纯形解法 2 线性规划标准型 标准型目标函数极大化 约束条件为等式 右端常数项bi 0 决策变量非负 简记 maxZ cjxaijxj bi i 1 2 m xj 0 j 1 2 n 3 非标准型向标准型转化目标函数极小化问题只需将目标等式两端乘以 1即变为极大化问题 右端常数项非正将约束等式两端同乘以 1约束条件为不等式当约束方程为 时 左端加入一个非负的松弛变量 当约束条件为 时 不等式左端减去一个非负的剩余变量 也可称松弛变量 即可 决策变量xk没有非负性要求令xk xk xk xk xk xk 0 用xk xk 取代模型中xk 4 线性规划解的概念 基m个线性无关的约束方程 称为一个基 用B表示 称基矩阵的列为基向量 用Pj表示 j 1 2 m 基变量与基向量Pj相对应的m个变量xj称为基变量其余的m n个变量为非基变量 基解令所有非基变量等于零 求出基变量的值 基解是各约束方程及坐标轴之间交点的坐标 基可行解 满足非负性约束的基解 最优基 最优解对应的基矩阵 称为最优基 5 线性规划的解题思路线性规划问题可以有无数个可行解 最优解只可能在顶点上达到 顶点对应的是基可行解 故只要在有限个基可行解中寻求最优解 从一个顶点出发找到一个可行基 得到一组基可行解 以目标函数做尺度衡量是否最优 若不是 则向邻近的顶点转移 换一个基再求解 检验 如此迭代使目标值逐步改善 直至求得最优解 6 解的可能性 唯一最优解 只有一个最优点 多重最优解两个顶点同是最优解 其连线上的每一点都是最优解 即无穷多个最优解 判据 最优单纯形表中存在非基变量的检验数等于 k 0 无界解LP问题的可行域无界 目标函数无限增大 缺乏必要的约束 判据 若某个 k 0所对应的系数列向量Pk 0 有进基变量但无离基变量 则是无界解 无可行解若约束条件相互矛盾 则可行域为空集 判据 最终单纯形表中人工变量仍没有置换出去 则没有可行解 7 人工变量问题 没有单位列向量的约束方程 需加入人工变量 人工变量最终必须等于0才能保持原问题性质不变 在目标函数中令其系数为 M M为无限大的正数 若人工变量不为0 则目标函数永远达不到最优 所以必须将人工变量逐步从基变量中替换出去 如若到最终表中人工变量仍没有置换出去 那么这个问题就没有可行解 当然亦无最优解 8 1 下表为用单纯形法计算时某一步的表格 已知该线性规划的目标函数为约束形式为x1 x2 x3为松弛变量 表中解代入目标函数后得Z 14 9 2 某医院昼夜24h各时段内需要的护士数量如下 2 00 6 0010人 6 00 10 0015人 10 00 14 0025人 14 00 18 0020人 18 00 22 0018人 22 00 2 0012人 护士分别于2 00 6 00 10 00 14 00 18 00 22 00分6批上班 并连续工作8小时 试确定 a 该医院至少应设多少名护士 才能满足值班需要 b 若医院可聘用合同工护士 上班时间同正式工护士 若正式工护士报酬为10元 h 合同工护士报酬为15元 h 问医院是否应聘合同工护士及聘多少名 10 第二章线性规划的对偶理论与灵敏度分析 对偶问题的数学模型原问题一般模型 对偶问题一般模型 maxZ CXmin YbAX bYA CX 0Y 0 11 对偶问题的基本性质 一 单纯形法计算的矩阵描述 表2 3 表3 4 见书P54 12 二 基本性质 P57 1 弱对偶性 极大化原问题的任一可行解的目标函数值 不大于其对偶问题任意可行解的目标函数值 2 最优性 3 强对偶性 4 互补松弛性 13 三 影子价格 对偶问题的经济解释这说明yi是右端项bi每增加一个单位对目标函数Z的贡献 对偶变量的值yi 所表示的第i种资源的边际价值 称为影子价值 若原问题的价值系数Cj表示单位产值 则yi称为影子价格 若原问题的价值系数Cj表示单位利润 则yi称为影子利润 影子价格不是资源的实际价格 而是资源配置结构的反映 是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化 对资源i总存量的评估 购进or出让对资源i当前分配量的评估 增加or减少 14 四 对偶单纯形法五 灵敏度分析 1 给出线性规划问题 要求 1 写出其对偶问题2 其对偶问题最优解为 试根据对偶问题性质求出原问题的最优解 15 1 其对偶问题为 2 根据对偶问题互补松弛性质 由代入对偶问题约束条件 可知有 解得 原问题最优解为 16 第三章运输问题 一 数学模型设从Ai到Bj的运输量为xij 假定产销平衡 则总运费 minZ Cijxij产量约束 xij aii 1 2 m 销量约束 xij bjj 1 2 n 非负性约束 xij 0 17 二 表上作业法1 确定初始方案 最小元素法 西北角法和Vogel法 2 解的最优性检验 闭回路法和对偶变量法 位势法 3 解的改进 三 进一步讨论将产销不平衡的问题转换为产销平衡问题 18 1 已知运输问题的供需关系与单位运价表 试用表上作业法求最优解 19 20 第四章整数规划 一 数学模型 21 二 分枝定界法 分枝定界法 BranchandBoundMethod 基本思想 先求出整数规划相应的线性规划 即不考虑整数限制 的最优解 若求得的最优解符合整数要求 则这个解就是原整数规划的最优解 若不满足整数条件 则任选一个不满足整数条件的变量来构造新的约束 在原可行域中剔除部分非整数解 然后 再在缩小的可行域中求解新构造的线性规划的最优解 这样通过求解一系列线性规划问题 最终得到原整数规划的最优解 定界的含义 整数规划是在相应的线性规划的基础上增加变量为整数的约束条件 整数规划的最优解不会优于相应线性规划的最优解 对极大化问题来说 相应线性规划的目标函数最优值是原整数规划函数值的上界 22 分枝定界法 例maxZ 5x1 8x2x1 x2 6 5x1 9x2 45x1 x2 0 x1 x2取整数第一步 不考虑变量的整数约束 求相应LP 问题1 的最优解 x1 2 4 x2 3 3 4 Z1 41 1 4第二步 定界过程上界41 1 4 下界为0 第三步 分枝过程将不满足整数约束的变量x1进行分枝 构造两个新的约束条件 x1 2 x1 3 23 分枝定界法 问题2 maxZ 5x1 8x2问题3 maxZ 5x1 8x2x1 x2 6 x1 x2 65x1 9x2 455x1 9x2 45x1 2x1 3x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数求解问题2相应的线性规划的最优解 x1 2 x2 3 8 9 Z2 41 1 9求解问题3相应的线性规划的最优解 x1 3 x2 3 Z3 39第四步 定界过程下界39 上界41 1 9 第五步 分枝过程将不满足整数约束的变量x2进行分枝 构造两个新的约束条件 x2 3 x2 4 24 分枝定界法 问题4 maxZ 5x1 8x2问题5 maxZ 5x1 8x2x1 x2 9 x1 x2 95x1 9x2 455x1 9x2 45x1 2x1 2x2 3x2 4x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数求解问题4相应的线性规划的最优解 x1 2 x2 3 Z4 34求解问题5相应的线性规划的最优解 x1 1 4 5 x2 4 Z5 41第六步 定界过程下界39 上界41 第七步 分枝过程将不满足整数约束的变量x1进行分枝 构造两个新的约束条件 x1 1 x1 2 25 分枝定界法 问题6 maxZ 5x1 8x2问题7 maxZ 5x1 8x2x1 x2 6 x1 x2 65x1 9x2 455x1 9x2 45x1 2x1 2x2 4x2 4x1 1x1 2x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数求解问题6相应的线性规划的最优解 x1 1 x2 4 4 9 Z6 40 5 9求解问题7相应的线性规划的最优解 无可行解第八步 定界过程LP7的无最优解 不必再分枝 下界39 上界为40 5 9 第九步 分枝过程将不满足整数约束的变量x2进行分枝 构造两个新的约束条件 x2 4 x2 5 26 分枝定界法 问题8 maxZ 5x1 8x2问题9 maxZ 5x1 8x2x1 x2 6 x1 x2 65x1 9x2 455x1 9x2 45x1 2x1 2x2 4x2 4x1 1x1 1x2 4x2 5x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数求解问题8相应的线性规划的最优解 x1 1 x2 4 Z8 37求解问题9相应的线性规划的最优解 x1 0 x2 5 Z9 40第十步 定界过程下界为40 上界为40 上界 下界 得整数规划问题的最优解 x1 0 x2 5 Z 40 27 分枝定界过程 x1 2 x1 3 x2 3 x2 4 x1 1 x1 2 x2 4 x2 5 分枝定界法 28 x2 3 x2 4 x1 1 x1 2 x2 4 x2 5 分枝定界法 29 三 指派问题的数学模型及其解法 匈牙利法设xij 0或1 为1时表示第i个人做第j事为0时表示不指派第i个人做第j事数模 minZ cijxij xij 1i 1 n xij 1j 1 nXij 0或1 30 最有值为 21 31 第五章网络计划 一 绘制网络图二 计算时间参数和求关键路线1 事项时间 最早和最迟2 工作时间 工序最早可能开工时间与工序最早可能完工时间 工序最迟必须开工时间与工序最迟必须完工时间3 时差 工序总时差 在不影响其紧后工序最迟必须开工时间的前提下 本工序可以推迟的时间工序单时差 在不影响其紧后工序最早可能开工时间的前提下 本工序可以推迟的时间图上计算法和表上计算法 三 网络优化 32 已知下列资料 要求绘制网络图 并计算最早开工 最迟开工及总时差 指出关键路线 33 第六章排队论 一 基本概念及肯道尔 D G Kendall 分类1 队长N t 和排队长Nq t 2 等待时间T t 和逗留时间Tq t 3 忙期B和闲期I4 记为Pn t 时刻时系统处于状态n的概率分布 N t N LNq t Nq LqT t T WTq t Tq WqB B I I Pn t Pn n 当系统处于状态n时 新来顾客的平均到达率 n 当系统处于状态n时 整个系统的平均服务率 记s系统中并行的服务台数 34 二 Poisson过程和负指数分布状态平衡方程和状态转移 概率分布 三 M M S等待制排队模型1 单服务台模型M M 1 队长的