管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 E-mail:jiapingxie@sina.com.cn 电话:55036936(H)65903541(O
管理运筹学 谢家平 博士 副教授 研究领域：系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程：管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单 位：上海财经大学国际工商管理学院供应链管理研究中心 E-mail：jiaping_xie@sina.com.cn 电 话：55036936(H) 65903541(O)
SHUFE 线性规划问题 线性规划主要解决有限资源的最佳分配问题 决策变量 决策变量的取值要求非负。 约束条件 存在一组决策变量构成的线性等式或不等式的约束条件。 目标函数 存在唯一的线性目标函数(极大或极小) 求解方法: 图解法 单纯形解法 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 2 线性规划问题 • 线性规划主要解决有限资源的最佳分配问题 • ▪ 决策变量的取值要求非负。 • ▪ 存在一组决策变量构成的线性等式或不等式的约束条件。 • ▪ 存在唯一的线性目标函数（极大或极小）。 • 求解方法： ▪ 图解法 ▪ 单纯形解法
SHUFE 线性规划的一般模型 线性规划模型的构建 例1生产计划问题 某厂生产甲乙两种产品,各自的零部件分别在A、B车间 生产,最后都需在C车间装配,相关数据如表所示 产品 工时单耗 生产能力 资源 甲 ABC 1033 024 12 36 单位产品获利 问如何安排甲、乙两产品的产量,使利润为最大 3上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 3 线性规划的一般模型 • 例1.生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间 生产，最后都需在C车间装配，相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。 • 线性规划模型的构建 产品 资源 工时单耗 甲 乙 生产能力 A B C 1 0 0 2 3 4 8 12 36 单位产品获利 3 5
SHUFE 线性规划的一般模型 建立模型 (1)决策变量:设x1为甲产品产量,x2为乙产品产量。 (2)约束条件:A车间能力约束x-8 B车间能力约束 2x2≤12 C车间能力约束3x1+4x2≤36 (3)目标函数:mz=3x1+5x2 (4)非负约束:x1≥0,x2≥0 线性规划数学模型为 maxz=3x,+5x <8 2x2≤12 3x1+4x,<36 x1≥0,x2≥0 4上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 4 线性规划的一般模型 (1)决策变量：设x1为甲产品产量，x2为乙产品产量。 (2)约束条件：A车间能力约束 x1 ≤8 B车间能力约束 2x2 ≤12 C车间能力约束 3x1 +4 x2 ≤36 (3)目标函数：maxZ= 3x1 +5 x2 (4)非负约束： x1 ≥0， x2 ≥0 • 线性规划数学模型为 maxZ=3x1 +5 x2 x1 ≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 • 建立模型
SHUFE 线性规划问题的图解法 线性规划的图解法 满足所有约束条件的解的集合,称之为可行域。 所有约束条件共同围城的区域。 例1的数学模型为 9 maxz= 3x, +5 ≤86 C(4,6) 2x,=12 2x,<12 S t 3x1+4x2<36 Z=30 B Z=42 x1≥0,x2≥0 Z=15 0 4 12 3x1+4x2=36 最优解:可行解中使目标函数最优(极大或极小)的解。 最优值一定在可行域的边界达到,而不可能在其内部 5上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 5 线性规划问题的图解法 • 线性规划的图解法 • 例1的数学模型为 maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 S.t. • 最优解：可行解中使目标函数最优(极大或极小)的解。 最优值一定在可行域的边界达到，而不可能在其内部。 • 满足所有约束条件的解的集合，称之为可行域。 所有约束条件共同围城的区域。 Z=30 Z=42 Z=15 x1 =8 2x2 =12 3x1 +4 x2 =36 x1 x2 4 8 12 3 6 9 0 A B D C(4,6)
SHUFE 线性规划问题的图解法 解的可能性 唯一最优解:只有一个最优点。 多重最优解 两个顶点同是最优解,其连线上的每一点都是最优解,即无穷 多个最优解。 判据:最优单纯形表中存在非基变量的检验数等于=0。 无界解 LP问题的可行域无界,目标函数无限增大,缺乏必要的约束。 判据:若某个k20所对应的系数列向量Pk≤0(有进基变量但无离 基变量),则是无界解。 无可行解 n若约束条件相互矛盾,则可行域为空集。 判据:最终单纯形表中人工变量仍没有置换出去,则没有可行 解 6上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 6 线性规划问题的图解法 • 唯一最优解：只有一个最优点。 • 多重最优解 ▪ 两个顶点同是最优解，其连线上的每一点都是最优解，即无穷 多个最优解 。 ▪ 判据：最优单纯形表中存在非基变量的检验数等于k= 0。 • 无界解 ▪ LP问题的可行域无界，目标函数无限增大，缺乏必要的约束 。 ▪ 判据：若某个k ≥0所对应的系数列向量Pk ′≤0（有进基变量但无离 基变量），则是无界解。 • 无可行解 ▪ 若约束条件相互矛盾，则可行域为空集。 ▪ 判据：最终单纯形表中人工变量仍没有置换出去，则没有可行 解。 • 解的可能性
SHUFE 线性规划标准型 标准型 目标函数极大化, 约束条件为等式, 右端常数项b≥0, 决策变量非负。 maxz=cux+Cxx,+.+crrn maze aurr +aj2x2+. +aurn=b pta,x,+. tern >Gir;=b;( x≥0(产=1,2,…,n) amrxtam2x2t. +amn b xx2…xn≥0 7上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 7 线性规划标准型 • 标准型 ▪ 目标函数极大化， ▪ 约束条件为等式， ▪ 右端常数项bi≥0， ▪ 决策变量非负。 maxZ=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn ＝b1 a21x1+a22x2+…+a2nxn ＝b2 … … … … … am1x1+am2x2+…+amnxn ＝bm x1 ,x2 ,…,xn ≥0 maxZ= cjxj aijxj＝bi ( i=1,2,…,m) xj≥0 ( j=1,2,…,n) = n j 1 = n j 1 简记
SHUFE 线性规划标准型 非标准型向标准型转化 目标函数极小化问题 只需将目标等式两端乘以-1即变为极大化问题。 右端常数项非正 将约束等式两端同乘以-1 约束条件为不等式 当约束方程为“≤”时,左端加入一个非负的松弛变量; 当约束条件为“≥”时,不等式左端减去一个非负的剩余变量 (也可称松弛变量)即可。 决策变量xk没有非负性要求 令 Ckk'"r k”,k-k!k 用xxk〃取代模型中xk 8上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 8 线性规划标准型 • 目标函数极小化问题 只需将目标等式两端乘以 -1 即变为极大化问题。 • 右端常数项非正 将约束等式两端同乘以 -1 • 约束条件为不等式 ▪ 当约束方程为“≤”时，左端加入一个非负的松弛变量； ▪ 当约束条件为“≥”时，不等式左端减去一个非负的剩余变量 (也可称松弛变量)即可。 • 决策变量xk没有非负性要求 令xk=xk ′-x k〃 ， xk=xk ′ ，x k〃 ≥0， 用xk ′ 、x k〃 取代模型中xk • 非标准型向标准型转化
SHUFE 线性规划解的概念 线性规划解的概念 基 m个线性无关的约束方程,称为一个基,用B表示。 称基矩阵的列为基向量,用P表示(=1,2,,m) 基变量 与基向量P相对应的m个变量x称为基变量 其余的m-n个变量为非基变量。 基解 单位矩阵 令所有非基变量等零求出基变量的值, 基解是各约程坐栋轴间交点的坐标。 基可行解:满定非负性约束的基解 最优基最优解对应的基矩阵,称为最优基。 9上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 9 线性规划解的概念 • 基 ▪ m个线性无关的约束方程，称为一个基，用B表示。 ▪ 称基矩阵的列为基向量，用Pj表示(j=1,2,…,m) 。 • 基变量 ▪ 与基向量Pj相对应的m个变量xj称为基变量 ▪ 其余的m-n个变量为非基变量。 • 线性规划解的概念 = 1 0 0 0 1 0 3 4 0 0 2 0 1 0 1 A x1 x2 x3 x4 x5 单位矩阵 • 基解 ▪ 令所有非基变量等于零，求出基变量的值， ▪ 基解是各约束方程及坐标轴之间交点的坐标。 • 基可行解：满足非负性约束的基解。 • 最优基：最优解对应的基矩阵，称为最优基
SHUFE 表格单纯形法 单纯形法计算 mLz=3x1+5x2+0x2+0x+05;=0 +x3 8 2 3x+4x, +x:=36 3 0 0 0比 B b 2 3 5 值 0 8 0 0 0 4 12 0 12/2=6 0 5 36 3 36/4-=9 检验数o;0 0 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 10 表格单纯形法 maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5 =36 • 单纯形法计算 Cj 比 CB XB b 值 检验数j x1 x2 x3 x4 x5 3 5 0 0 0 8 1 0 1 0 0 12 0 2 0 1 0 36 3 4 0 0 1 x3 x4 x5 0 0 0 0 3 5 0 0 0 - 12/2=6 36/4=9