《运筹学》讲义 运筹学是一门应用科学,它广泛应用现代科学技术知识、用定量分析 的方法,解决实际中提出的问题,为决策者选择最优决策提供定量依据。 运筹学的核心思想是建立在优化的基础上。 例如,在线性规划中体现为两方面: (1)对于给定的一项任务,如何统筹安排,使以最少的资源消耗去完 成 (2)在给定的一定数量的资源条件下,如何合理安排,使完成的任务 最多? 运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问 题,用数学方法对模型进行求解,并对解的结果进行分析,为决策提供科 学依据 随着计算机及计算技术的迅猛发展,目前对运筹学的数学模型的求解 已有相应的软件。因此,在实际求解计算时常可借助于软件在计算机上进 行,这样可以节省大量的人力和时间
-1- 《运筹学》讲义 运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析 的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。 运筹学的核心思想是建立在优化的基础上。 例如，在线性规划中体现为两方面： （1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完 成？ （2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务 最多？ 运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问 题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科 学依据。 随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解 已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进 行，这样可以节省大量的人力和时间
第一部分线性规划内容框架 LP问题 基本概念数学模型「可行解、最优解 实际问题 LP问题 解的概念一基本解、基可行解 基本最优解 基本方法 图解法 原始单纯形法 单纯形法 大M法 人工变量法 对偶单纯形法 两阶段法 对偶理论 进一步讨论 敏度分析—参数规划* 在经济管理领域内应用 运输问题(转运问题) 特殊的LP问题 整数规划 多目标LP问题* 第一部分线性规划( Linear Programming) 及其应用 第一章P问题的数学模型与求解 §1LP问题及其数学模型 (一)引例1(生产计划的问题) 某工厂在计划期内要安排生产I、Ⅱ的两种产品,已知生产单位产品
-2- 第一部分 线性规划内容框架 LP问题 基本概念 数学模型 可行解、最优解 实际问题 LP问题 解的概念 基本解、基可行解 提 出 基本最优解 基本方法 图解法 原始单纯形法 单纯形法 大M法 人工变量法 对偶单纯形法 两阶段法 对偶理论 进一步讨论 灵敏度分析──参数规划* 在经济管理领域内应用 运输问题（转运问题） 特殊的LP问题 整数规划 多目标LP问题* 第一部分 线性规划（Linear Programming） 及其应用 第一章 LP问题的数学模型与求解 §1 LP问题及其数学模型 （一）引例1（生产计划的问题） 某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品
所需的设备台时,A、B两种原材料的消耗以及每件产品可获的利润如下表 所示。问应如何安排计划使该工厂获利最多? 资源限量 设备 8(台时) 原材料A 0 16(kg) 原材料B 12(kg) 单位产品利润(元)2 该问题可用一句话来描述,即在有限资源的条件下,求使利润最大的 生产计划方案 解:设x1,x分别表示在计划期内生产产品I、Ⅱ的产量。由于资源的 限制,所以有: 机器设备的限制条件:x1+2x2≤8 原材料A的限制条件:4x≤16 (称为资源约束条件) 原材料B的限制条件:4x2≤12 同时,产品I、Ⅲ的产量不能是负数,所以有 X1≥0,x2≥0 (称为变量的非负约束) 显然,在满足上述约束条件下的变量取值,均能构成可行方案,且有 许许多多。而工厂的目标是在不超过所有资源限量的条件下,如何确定产 量x1,x以得到最大的利润,即使目标函数 Z=2x1+3x2 的值达到最大。 综上所述,该生产计划安排问题可用以下数学模型表示: maxz2X1t3X2
-3- 所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表 所示。问应如何安排计划使该工厂获利最多？ Ⅰ Ⅱ 资源限量 设备 1 2 8(台时) 原材料A 4 0 16(kg) 原材料B 0 4 12(kg) 单位产品利润（元） 2 3 该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的 生产计划方案。 解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的 限制，所以有： 机器设备的限制条件：x1+2x2≤8 原材料A的限制条件： 4x1≤16 （称为资源约束条件） 原材料B的限制条件： 4x2≤12 同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有 x1≥0，x2≥0 （称为变量的非负约束） 显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有 许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产 量x1，x2以得到最大的利润，即使目标函数 Z=2x1+3x2 的值达到最大。 综上所述，该生产计划安排问题可用以下数学模型表示： maxz=2x1+3x2
x.+2x、<8 4x.<16 4x.<12 引例2.(营养配餐问题) 假定一个成年人每天需要从食物中获取3000卡路里热量,55克蛋白质 和800毫克钙。如果市场上只有四种食品可供选择,它们每千克所含热量和 营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使 购买食品的费用最小? 序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元) 猪肉 1000 400 鸡蛋 800 大米 300 白菜 解:设x(=1,2,3,4)为第j种食品每天的购买量,则配餐问题数学模型为 minz= 3x3 2x4 10000x1+800x,+900x2+200x4≥3000 50x+60x2+20x3+10x4≥55 x t 400x1+200x2+300x3+500x4≥800 x≥0(=12,34) (二)LP问题的模型 上述两例所提出的问题,可归结为在变量满足线性约束条件下,求使 线性目标函数值最大或最小的问题。它们具有共同的特征。 (1)每个问题都可用一组决策变量(x1,x2…x)表示某一方案,其具体 的值就代表一个具体方案。通常可根据决策变量所代表的事物特点,可对
-4- + 0 4 12 4 16 2 8 . . 1 2 2 1 1 2 x x x x x x st 引例2. （营养配餐问题） 假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质 和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和 营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使 购买食品的费用最小？ 序号 食品名称 热量(卡路里) 蛋白质(克) 钙(mg) 价格(元) 1 猪肉 1000 50 400 10 2 鸡蛋 800 60 200 6 3 大米 900 20 300 3 4 白菜 200 10 500 2 解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为 minz=10x16x23x32x4 = + + + + + + + + + 0( 1,2,3,4) 400 200 300 500 800 50 60 20 10 55 10000 800 900 200 3000 . 1 2 3 4 1 2 3 4 1 2 3 4 x j x x x x x x x x x x x x x t j （二）LP问题的模型 上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使 线性目标函数值最大或最小的问题。它们具有共同的特征。 （1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体 的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对
变量的取值加以约束,如非负约束 (2)存在一组线性等式或不等式的约束条件。 (3)都有一个用决策变量的线性函数作为决策目标(即目标函数) 按问题的不同,要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为LP的数学模型,其一般形式为 max(或minz=cx1+c2x2+…+cnxn (1.1) a1x2+a12x2+…+a1nxn≤(=,≥)b a2x2+a2x2+…+a2nxn≤(=,≥)b2 st (1.2) anx2+an2x2+…+anxn≤(=,≥)b (1.3) x2…xn≥0 或紧缩形式 max(或mn)z= 分s(=,≥)b,(t=1,2,…m) (1.4) ≥0 或矩阵形式 max(或min)z=cx AX≤(=,≥)b X≥0 或向量形式 max(或min)z=cx
-5- 变量的取值加以约束，如非负约束。 （2）存在一组线性等式或不等式的约束条件。 （3）都有一个用决策变量的线性函数作为决策目标（即目标函数）， 按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为LP的数学模型，其一般形式为： max(或min)z=c1x1+c2x2+…+cnxn (1.1) + + + = + + + = + + + = 0 ( , ) ( , ) ( , ) . 1 2 1 2 2 2 21 2 22 2 2 2 11 2 12 2 1 1 n m m mn n m n n n n x x x a x a x a x b a x a x a x b a x a x a x b st (1.2) 或紧缩形式 max(或min)z= = n j j j c x 1 = = = 0 ( , ) ( 1,2, , ) 1 j n j j j i x a x b i m (1.4) 或矩阵形式 max(或min)z=cx = 0 ( , ) X AX b (1.5) 或向量形式： max(或min)z=cx (1.3)
∑Px≤(=2)b (1.6) X≥0G=12,…,n) 其中C=(cl,c2,…cn),称为价值系数向量: A=(anax“an|称为技术系数矩阵(并称消耗系数矩阵) b b 称资源限制向量 X=(x1,x2,…,xn)称为决策变量向量。 (三)LP问题的标准型 1为了讨论LP问题解的概念和解的性质以及对LP问题解法方便,必须 把LP问题的一般形式化为统一的标准型: maxz> C maXz-c =b(i=1,2,…,m)「AX=b 或 x,≥0(=1,2, X≥0 ∑P,x=b x,≥0(=12,…,n)
-6- = = = 0 ( 1,2, , ) ( , ) 1 X j n p x b j n j j j (1.6) 其中C=(c1,c2,…,cn)，称为价值系数向量； = m m mn n n a a a a a a a a a A , , , , , , 1 2 21 22 2 11 12 1 称为技术系数矩阵（并称消耗系数矩阵） =(p1,p2,…,pn) = m b b b b 2 1 称资源限制向量 X=(x1,x2,…,xn) T称为决策变量向量。 （三）LP问题的标准型 1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须 把LP问题的一般形式化为统一的标准型： maxz= = n j j j c x 1 ； = = = = 0( 1,2, , ) ( 1,2, , ) 1 x j n a x b i m j n j j j i 或 = X 0 AX b maxz=cx 或 = = = 0( 1,2, , ) 1 x j n p x b j n j j j maxz=cx
标准型的特点: ①目标函数是最大化类型 ②约束条件均由等式组成 ③决策变量均为非负 ④b(i=1,2…,n) 2化一般形式为标准型 ①minz→>max(-z)=cx ②“≤”→左边+松驰变量;“≥”→左边一“松驰变量” ③变量x≤0>x≥0变量x无限制→令x=x-xj” ④b<0→等式两边同乘以(-1) 3模型隐含的假设 ①比例性假定:决策变量变化的改变量与引起目标函数的改变量成比 例;决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假 定意味着每种经营活动对目标函数的贡献是一个常数,对资源的消耗也是 一个常数。 ②可加性假定:每个决策变量对目标函数和约束方程的影响是独立于 其它变量的。 ③连续性假定:决策变量应取连续值。 ④确定性假定:所有的参数(ai,b,c)均为确定,所以LP问题是确定型问 题,不含随机因素。 以上4个假定均由于线性函数所致。在现实生活中,完全满足这4个假 定的例子并不多见,因此在使用LP时必须注意问题在什么程度上满足这些 假定。若不满足的程度较大时,应考虑使用其它模型和方法。如非线性规 划,整数规划或不确定型分析方法
-7- 标准型的特点： ①目标函数是最大化类型 ②约束条件均由等式组成 ③决策变量均为非负 ④bi(i=1,2,…,n) 2.化一般形式为标准型 ①minz→max(-z)=-cx ②“”→左边+松驰变量；“”→左边－“松驰变量” ③变量xj0→-xj0变量xj无限制→令xj=xj－xj ④bi<0→等式两边同乘以(-1)。 3.模型隐含的假设 ①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比 例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假 定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是 一个常数。 ②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于 其它变量的。 ③连续性假定：决策变量应取连续值。 ④确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问题是确定型问 题，不含随机因素。 以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假 定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些 假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规 划，整数规划或不确定型分析方法
对LP标准型,我们还假定(A=m<n。 (四)LP问题的解的概念 设LP问题 maⅹz= ∑ (1.7) ax=b(i=12,…,m) (1.8) x≥0(=12,…,m) (1.9) 1从代数的角度看: 可行解和最优解满足约束条件(.8)和(19)的解X=(x1,x2,…,xn)称为 可行解。所有可行解构成可行解集,即可行域S={XA,=b,x≥0} 而使目标函数达到最大值的可行解称为最优解,对应的目标函数值称为最 优值。 求解LP问题就是求其最优解和最优值,但从代数的角度去求是困难 的 2从LP角度看 基:设A为mxn矩阵,r(A)=m,B是A中的mxm阶非奇异子矩阵(即B|=0), 则称B是LP问题的一个基。 若B是LP问题的一个基,则B由m个线性独立的列向量组成,即 B=(PP2,…,Pm),其中P(an,arn…,am),(=12;…,m)称为基向理。与其 向量P相对应的变量x称为基变量,其它变量称为非基变量。显然,对应 于每个基总有m个基变量,n-m个非基变量。 基本解与基可行解设B是LP问题的一个基,令其n-m个非基变量均 为零,所得方程的解称为该LP问题的一个基本解。显然,基B与基本解是
-8- 对LP标准型，我们还假定r(A)=m<n。 （四）LP问题的解的概念 设LP问题 maxz= = n j j j c x 1 (1.7) = = = n j a j x j bi i n 1 ( 1,2,, ) (1.8) x 0( j 1,2, , n) j = (1.9) 1.从代数的角度看： 可行解和最优解 满足约束条件(1.8)和(1.9)的解X=(x1,x2,…,xn) T称为 可行解。所有可行解构成可行解集，即可行域 S = {X A = b, x 0} x 。 而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最 优值。 求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难 的。 2.从LP角度看： 基：设A为mxn矩阵，r(A)=m，B是A中的mxm阶非奇异子矩阵（即|B|0）， 则称B是LP问题的一个基。 若B是LP问题的一个基，则B由m个线性独立的列向量组成，即 B=(Pr1,Pr2,…,Prm)，其中Prj=(a1rj,a2rj,…,amrj) T，(j=1,2,…,m)称为基向理。与其 向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应 于每个基总有m个基变量，n－m个非基变量。 基本解与基可行解 设B是LP问题的一个基，令其n－m个非基变量均 为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是
对应的,基本解的个数≤Cn。在基本解中,称满足非负条件的基本解 为基可行解,对应的基称为可行基。 退化解如果基解中非零分量的个数小于m,则称此基本解为退化 的,否则是非退化的 最优基如果对应于基B的基可行解是LP问题的最优解,则称B为LP 问题的最优基,相应的解又称基本最优解。 3.LP问题解之间的关系如图所示 基本解 可 基可行解 (五)两个变量LP问题的图解法 1LP问题解的几何表示。以引例为例说明 maxz=2x1+3x2 x1+2x2≤8① 4x.<16 4x2≤12 x≥0,x2≥0④ 按以下顺序进行 解:(1)画出直角坐标系; (2)依次做每条约束线,标出可行域的方向,并找出它们共同的 可行域
-9- 一一对应的，基本解的个数≤Cmn。在基本解中，称满足非负条件的基本解 为基可行解，对应的基称为可行基。 退化解 如果基解中非零分量的个数小于m，则称此基本解为退化 的，否则是非退化的。 最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为LP 问题的最优基，相应的解又称基本最优解。 3.LP问题解之间的关系如图所示 （五）两个变量LP问题的图解法 1.LP问题解的几何表示。以引例为例说明 maxz=2x1+3x2 + 0, 0 4 12 4 16 2 8 1 2 2 1 1 2 x x x x x x 按以下顺序进行： 解：（1）画出直角坐标系； （2）依次做每条约束线，标出可行域的方向，并找出它们共同的 可行域； ① ② ③ ④ 可 行 解 基本解 基可行解
(3)任取一目标函数值作一条目标函数线(称等值线),根据目标 函数(最大或最小)类型,平移该直线即将离开可行域上,则与目标函数 线接触的最终点即表示最优解 图1 其中,将目标函数乙2(+3x改写为x=-2x+12,因此,它可 以表示为:以z为参数,以一二为斜率的一族平行线。位于同一条直线上的 点具有相同的值。 解的几种情况 (1)此例有唯一解Q2,即x1=4x2=2,z=14 (2)有无穷多最优解(多重解),若将目标函数改为z2x1+4x2则线段 Q2,Q3上的点均为最优解。 (3)无界解
-10- （3）任取一目标函数值作一条目标函数线（称等值线），根据目标 函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数 线接触的最终点即表示最优解。 图1 其中，将目标函数Z=2x1+3x2改写为 x x z 3 1 3 2 2 = − 1 + ，因此，它可 以表示为：以z为参数，以 3 2 − 为斜率的一族平行线。位于同一条直线上的 点具有相同的值。 解的几种情况： （1）此例有唯一解Q2，即x1=4,x2=2,z=14 （2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段 Q2，Q3上的点均为最优解。 （3）无界解 x2 ② ③ ① Q2 Q4 Q3 B Q1 A x1 3 2 1 0 0 1 2 3 4
