上海财经大学国际工商管理学院：《管理运筹学》课程教学资源（PPT课件）第一讲 线性规划

管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 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 第一章线性规划的数学模型 线性规划 Linear programming LP 规划论中的静态规划 解决有限资源的最佳分配问题 求解方法: 图解法 单纯形解法 3上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 3 第一章 线性规划的数学模型 • 线性规划 Linear Programming LP • 规划论中的静态规划 • 解决有限资源的最佳分配问题 • 求解方法： ▪ 图解法 ▪ 单纯形解法

SHUFE 第一章线性规划的数学模型 第一节线性规划一般模型 第二节线性规划的图解法 第三节线性规划的标准型 第四节线性规划解的概念 4上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 4 第一章 线性规划的数学模型 第一节 线性规划一般模型 第二节 线性规划的图解法 第三节 线性规划的标准型 第四节 线性规划解的概念

SHUFE 第一节线性规划一般模型 、线性规划问题的三个要素 决策变量 决策问题待定的量值称为决策变量。 决策变量的取值要求非负 约束条件 任何问题都是限定在一定的条件下求解,把各种限制条件表示 为一组等式或不等式,称之为约束条件。 约束条件是决策方案可行的保障。 LP的约束条件,都是决策变量的线性函数。 目标函数 衡量决策方案优劣的准则,如时间最省、利润最大、成本最低。 目标函数是决策变量的线性函数。 有的目标要实现极大,有的则要求极小。 5上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 5 第一节 线性规划一般模型 一、线性规划问题的三个要素 • ▪ 决策问题待定的量值称为决策变量。 ▪ 决策变量的取值要求非负。 • 约束条件 ▪ 任何问题都是限定在一定的条件下求解，把各种限制条件表示 为一组等式或不等式，称之为约束条件。 ▪ 约束条件是决策方案可行的保障。 ▪ LP的约束条件，都是决策变量的线性函数。 • 目标函数 ▪ 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 ▪ 目标函数是决策变量的线性函数。 ▪ 有的目标要实现极大，有的则要求极小

SHUFE 第一节线性规划一般模型 线性规划模型的构建 例1.生产计划问题 某厂生产甲乙两种产品,各自的零部件分别在A、B车间 生产,最后都需在C车间装配,相关数据如表所示 产品 工时单耗 生产能力 车间 甲 ABC 0245 36 单位产品获利 问如何安排甲、乙两产品的产量,使利润为最大。 6上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 6 第一节 线性规划一般模型 • 例1. 生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间 生产，最后都需在C车间装配，相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。 二、线性规划模型的构建 产品 车间 工时单耗 甲 乙 生产能力 A B C 1 0 0 2 3 4 8 12 36 单位产品获利 3 5

SHUFE 第一节线性规划一般模型 建立模型 (1)决策变量。要决策的问题是甲、乙两种产品的产量,因 此有两个决策变量:设x为甲产品产量,x2为乙产品产量。 (2)约束条件。生产这两种产品受到现有生产能力的制约, 用量不能突破。 生产单位甲产品的零部件需耗用A车间的生产能力1工时, 生产单位乙产品不需耗用A车间的生产能力, A车间的能力总量为8工时,则A车间能力约束条件表述为 <8 同理,B和C车间能力约束条件为 2x2≤12 3xn+4x2<36 7上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 7 第一节 线性规划一般模型 (1)决策变量。要决策的问题是甲、乙两种产品的产量，因 此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。 (2)约束条件。生产这两种产品受到现有生产能力的制约， 用量不能突破。 ▪ 生产单位甲产品的零部件需耗用A车间的生产能力1工时， ▪ 生产单位乙产品不需耗用A车间的生产能力， ▪ A车间的能力总量为8工时，则A车间能力约束条件表述为 x1 ≤8 ▪ 同理，B和C车间能力约束条件为 2x2 ≤12 3x1 +4 x2 ≤36 • 建立模型

SHUFE 第一节线性规划一般模型 (3)目标函数。目标是利润最大化,用Z表示利润,则 maxz= 3x+ x2 (4)非负约束。甲乙产品的产量不应是负数,否则没有实际 意义,这个要求表述为 x1≥0,x2≥0 综上所述,该问题的数学模型表示为 maxz=3x, + x2 <8 2x,<12 St 3x1+4x,<36 x7≥0,x,≥0 8上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 8 第一节 线性规划一般模型 (3)目标函数。目标是利润最大化，用Z表示利润，则 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 S.t

SHUFE 第一节线性规划一般模型 例2.运输问题 某名牌饮料在国内有三个生产厂,分布在城市A1、 A2、A3,其一级承销商有4个,分布在城市B1、B2、B3 B4,已知各厂的产量、各承销商的销售量及从A到B 的每吨饮料运费为C为发挥集团优势,公司要统 筹划运销问题,求运费最小的调运方案。 产地 销地B1B2 AAA 123 329 销量2314 9上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 9 第一节 线性规划一般模型 某名牌饮料在国内有三个生产厂，分布在城市A1、 A2、A3 ,其一级承销商有4个，分布在城市B1、B2、B3、 B4，已知各厂的产量、各承销商的销售量及从Ai到Bj 的每吨饮料运费为Cij，为发挥集团优势，公司要统 一筹划运销问题，求运费最小的调运方案。 • 例2. 运输问题 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 6 3 2 5 7 5 8 4 3 2 9 7 5 2 3 销量 2 3 1 4

SHUFE 第一节线性规划一般模型 (1)决策变量。设从A到B运输量为xn (2)目标函数。运费最小的目标函数为 ninz=6x1+3x12+2x13+5x14+7x21+5x218x23+4x2+3x3+2x32+9x3+7x3y (3)约束条件。产量之和等于销量之和要满足: 供应平衡条件xt+xn2+x+x5 x2+x2+x23+x22 x3+x32+x3+x3=3 销售平衡条件x1+x2+x3=2 x12+x2+x32=3 x13+x23+x3=1 14+x24+x34 非负性约束0(12,3;问=1,3,4 上海财经大学国际工商管理学院

上海财经大学国际工商管理学院 SHUFE 10 第一节 线性规划一般模型 (1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数。运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： ▪ 供应平衡条件 x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3 ▪ 销售平衡条件 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4 ▪ 非负性约束 xij≥0 (i=1,2,3；j=1,2,3,4)