运筹学
运筹学 — 线性规划
概述
- 基本假设（线性）
- 决策变量每增加一个单位，对目标函数的贡献是一样的
- 可加性
- 允许非整数
- 所有参数均已知
- 标准形式
- 形式
- maxZ = CX
- AX = b
- X >= 0
- 约束条件
- 目标函数为求最大值（如果是最小值，可以转换成最大值）
- 约束条件均为等式方程
- 变量 X 为非负
- 常数 b 都大于等于零
- 形式
- 转化标准型
- 注意点一：如果不等式为绝对值，需拆分成两个不等式
- 线性规划的解
- 概念
- 可行解：满足线性规划模型约束条件的解
- 最优解：使目标函数达到最大值的可行解
- 解的四种情况
- 有唯一最优解
- 有多重解：有多组最优解
- 有无界解：满足约束条件，但是找不到最优解
- 无可行解
- 概念
- 可行角点（CPF）
- 有可行解且有界
- 必定会有CPF，且 至少一个最优解
- 如果有一个最优解，必定是CPF
- CPF中最好的，必定是最优解
- 如果有多重最优解，至少有两个角点
- 有可行解且有界
单纯性法
- 步骤
- 构建初始单纯性表
- 求检验数并判断
- 所有检验数都满足 Q <= 0，得到最优解
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
- 若存在检验数Q > 0，且其对应的变量x的系数列向量P <= 0，则为无界解
- 所有检验数都满足 Q <= 0，得到最优解
- 基变换
- 重复 步骤二 和 步骤三
- 大M法和两阶段法
- 问题
- 如果一开始的时候，无法找到初始基变量，可以人为的添加基变量
- 但是加入约束变量之后，则认为的改变了约束条件
- 算法
- 大M法
- 步骤
- 构建初始单纯性表
- 求检验数并判断
- 所有检验数都满足 Q <= 0，且基变量中无人工变量，得到最优解
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
- 所有检验数都满足 Q <= 0，但基变量中含有非零的人工变量，则无可行解
- 若存在检验数Q > 0，且其对应的变量x的系数列向量P <= 0，则为无界解
- 所有检验数都满足 Q <= 0，且基变量中无人工变量，得到最优解
- 基变换
- 重复 步骤二 和 步骤三
- 步骤
- 两阶段法
- 步骤
- 第一阶段：求人工变量之和的最小值
- 如果第一阶段 目标函数最优解不等于零，说明原问题无可行解
- 第二阶段
- 步骤
- 构建初始单纯性表
- 初始解为第一阶段的解
- 求检验数并判断
- 所有检验数都满足 Q <= 0，得到最优解
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
- 若存在检验数Q > 0，且其对应的变量x的系数列向量P <= 0，则为无界解
- 所有检验数都满足 Q <= 0，得到最优解
- 基变换
- 重复 步骤二 和 步骤三
- 构建初始单纯性表
- 步骤
- 第一阶段：求人工变量之和的最小值
- 步骤
- 大M法
- 问题
对偶理论
- 问题描述
- 原问题
- maxZ = CX
- AX <= b
- X >= 0
- 对偶问题
- minZ’ = Yb
- YA <= C
- Y >= 0
- 原问题
- 性质
- 对称性
- 对偶问题的对偶是原问题
- 无界性
- 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解
- 弱对偶性
- 若X是原问题（Max问题）的可行解，Y是对偶问题（Min问题）的可行解，则CX <= Yb
- 最优性
- 若X是原问题的可行解，Y是对偶问题的可行解，则CX = Yb，X、Y是最优解
- 对偶定理
- 若原问题有最优解，则对偶问题也有最优解，且目标函数值相等
- 互补松弛性
- 设X、Y分别是原问题和对偶问题的可行解，XS、YS分别是其松弛变量的可行解， - 则X、Y是最优解当且仅当X * YS = 0 和 Y * XS = 0
- 求解问题
- 原问题（Max）的检验数的相反数（乘负号）对应于对偶问题的一组基本解
- 对偶问题的检验数对应于原问题的一组基本解
- 对称性
- 对偶单纯形法的优点
- 初始解可以是非可行解，当检验数都非正时（目标函数为最小值则检验数都非负）， - 就可以进行基变换，不需要添加人工变量，可简化计算
- 当变量多于约束条件时，用对偶单纯形法可减少计算工作量
- 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法
- 一般很少单独使用
灵敏度分析
- 问题
- aij、bi、cj系数中有一个或几个变化时，原线性规划最优解会有什么变化
- 思路
- 把发生变化的系数经过一定的计算代入原最终表中，进行检查和分析
- 四种情况
- 第一种
- 原问题：可行解
- 对偶问题：可行解
- 结论或继续计算的步骤：表中的解仍为最优解
- 第二种
- 原问题：可行解
- 对偶问题：非可行解
- 结论或继续计算的步骤：用单纯形法继续迭代求最优解
- 第三种
- 原问题：非可行解
- 对偶问题：可行解
- 结论或继续计算的步骤：用对偶单纯形法继续迭代求最优解
- 第四种
- 原问题：非可行解
- 对偶问题：非可行解
- 结论或继续计算的步骤：引入人工变量，编制新的单纯性表，求最优解
- 第一种
- 价值系数C的灵敏度分析
- Cj 发生变化，检验数Qj发生变化
- Cj 对应非基变量，重新计算Cj 对应的检验数
- Cj 对应基变量，重新计算所有非基变量检验数
- Cj 发生变化，检验数Qj发生变化
- 资源限量B的灵敏度分析
- 技术系数A的灵敏度分析
运输问题
- 产销平衡的运输问题
- 表上作业法（本质上是单纯形法）
- 步骤
- 求初始基本可行解（最小元素法/伏格尔法）
- 求检验数并判断（位势法）
- 调整运量（闭回路法）
- 重复步骤二、三，直到求得最优解
- 步骤
- 表上作业法（本质上是单纯形法）
- 产销不平衡的运输问题
- 产大于销
- 增加虚拟销地，单位运价为0
- 销大于产
- 增加虚拟产地，单位运价为0
- 销量不确定
- 产大于销
整数规划问题
- 问题
- 取数必须为整数
- 方法
- 图解法
- 分支定界法
- 步骤
- 不断将线性规划问题B的可行域分为子区域，逐步缩小Z的上界和增加Z的下界，最终求得Z*
- 上下界更新：问题B（线性规划问题）各分支最优目标函数中的最大值作为新的上界； 在已求出整数条件的解中的最大值作为新的下界
- 步骤
运筹学
运筹学 — 线性规划
概述
- 基本假设（线性）
- 决策变量每增加一个单位，对目标函数的贡献是一样的
- 可加性
- 允许非整数
- 所有参数均已知
- 标准形式
- 形式
- maxZ = CX
- AX = b
- X >= 0
- 约束条件
- 目标函数为求最大值（如果是最小值，可以转换成最大值）
- 约束条件均为等式方程
- 变量 X 为非负
- 常数 b 都大于等于零
- 形式
- 转化标准型
- 注意点一：如果不等式为绝对值，需拆分成两个不等式
- 线性规划的解
- 概念
- 可行解：满足线性规划模型约束条件的解
- 最优解：使目标函数达到最大值的可行解
- 解的四种情况
- 有唯一最优解
- 有多重解：有多组最优解
- 有无界解：满足约束条件，但是找不到最优解
- 无可行解
- 概念
- 可行角点（CPF）
- 有可行解且有界
- 必定会有CPF，且 至少一个最优解
- 如果有一个最优解，必定是CPF
- CPF中最好的，必定是最优解
- 如果有多重最优解，至少有两个角点
- 有可行解且有界
单纯性法
- 步骤
- 构建初始单纯性表
- 求检验数并判断
- 所有检验数都满足 Q <= 0，得到最优解
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
- 若存在检验数Q > 0，且其对应的变量x的系数列向量P <= 0，则为无界解
- 所有检验数都满足 Q <= 0，得到最优解
- 基变换
- 重复 步骤二 和 步骤三
- 大M法和两阶段法
- 问题
- 如果一开始的时候，无法找到初始基变量，可以人为的添加基变量
- 但是加入约束变量之后，则认为的改变了约束条件
- 算法
- 大M法
- 步骤
- 构建初始单纯性表
- 求检验数并判断
- 所有检验数都满足 Q <= 0，且基变量中无人工变量，得到最优解
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
- 所有检验数都满足 Q <= 0，但基变量中含有非零的人工变量，则无可行解
- 若存在检验数Q > 0，且其对应的变量x的系数列向量P <= 0，则为无界解
- 所有检验数都满足 Q <= 0，且基变量中无人工变量，得到最优解
- 基变换
- 重复 步骤二 和 步骤三
- 步骤
- 两阶段法
- 步骤
- 第一阶段：求人工变量之和的最小值
- 如果第一阶段 目标函数最优解不等于零，说明原问题无可行解
- 第二阶段
- 步骤
- 构建初始单纯性表
- 初始解为第一阶段的解
- 求检验数并判断
- 所有检验数都满足 Q <= 0，得到最优解
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
- 若存在检验数Q > 0，且其对应的变量x的系数列向量P <= 0，则为无界解
- 所有检验数都满足 Q <= 0，得到最优解
- 基变换
- 重复 步骤二 和 步骤三
- 构建初始单纯性表
- 步骤
- 第一阶段：求人工变量之和的最小值
- 步骤
- 大M法
- 问题
对偶理论
- 问题描述
- 原问题
- maxZ = CX
- AX <= b
- X >= 0
- 对偶问题
- minZ’ = Yb
- YA <= C
- Y >= 0
- 原问题
- 性质
- 对称性
- 对偶问题的对偶是原问题
- 无界性
- 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解
- 弱对偶性
- 若X是原问题（Max问题）的可行解，Y是对偶问题（Min问题）的可行解，则CX <= Yb
- 最优性
- 若X是原问题的可行解，Y是对偶问题的可行解，则CX = Yb，X、Y是最优解
- 对偶定理
- 若原问题有最优解，则对偶问题也有最优解，且目标函数值相等
- 互补松弛性
- 设X、Y分别是原问题和对偶问题的可行解，XS、YS分别是其松弛变量的可行解， - 则X、Y是最优解当且仅当X * YS = 0 和 Y * XS = 0
- 求解问题
- 原问题（Max）的检验数的相反数（乘负号）对应于对偶问题的一组基本解
- 对偶问题的检验数对应于原问题的一组基本解
- 对称性
- 对偶单纯形法的优点
- 初始解可以是非可行解，当检验数都非正时（目标函数为最小值则检验数都非负）， - 就可以进行基变换，不需要添加人工变量，可简化计算
- 当变量多于约束条件时，用对偶单纯形法可减少计算工作量
- 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法
- 一般很少单独使用
灵敏度分析
- 问题
- aij、bi、cj系数中有一个或几个变化时，原线性规划最优解会有什么变化
- 思路
- 把发生变化的系数经过一定的计算代入原最终表中，进行检查和分析
- 四种情况
- 第一种
- 原问题：可行解
- 对偶问题：可行解
- 结论或继续计算的步骤：表中的解仍为最优解
- 第二种
- 原问题：可行解
- 对偶问题：非可行解
- 结论或继续计算的步骤：用单纯形法继续迭代求最优解
- 第三种
- 原问题：非可行解
- 对偶问题：可行解
- 结论或继续计算的步骤：用对偶单纯形法继续迭代求最优解
- 第四种
- 原问题：非可行解
- 对偶问题：非可行解
- 结论或继续计算的步骤：引入人工变量，编制新的单纯性表，求最优解
- 第一种
- 价值系数C的灵敏度分析
- Cj 发生变化，检验数Qj发生变化
- Cj 对应非基变量，重新计算Cj 对应的检验数
- Cj 对应基变量，重新计算所有非基变量检验数
- Cj 发生变化，检验数Qj发生变化
- 资源限量B的灵敏度分析
- 技术系数A的灵敏度分析
运输问题
- 产销平衡的运输问题
- 表上作业法（本质上是单纯形法）
- 步骤
- 求初始基本可行解（最小元素法/伏格尔法）
- 求检验数并判断（位势法）
- 调整运量（闭回路法）
- 重复步骤二、三，直到求得最优解
- 步骤
- 表上作业法（本质上是单纯形法）
- 产销不平衡的运输问题
- 产大于销
- 增加虚拟销地，单位运价为0
- 销大于产
- 增加虚拟产地，单位运价为0
- 销量不确定
- 产大于销
整数规划问题
- 问题
- 取数必须为整数
- 方法
- 图解法
- 分支定界法
- 步骤
- 不断将线性规划问题B的可行域分为子区域，逐步缩小Z的上界和增加Z的下界，最终求得Z*
- 上下界更新：问题B（线性规划问题）各分支最优目标函数中的最大值作为新的上界； 在已求出整数条件的解中的最大值作为新的下界
- 步骤