PDF《第二章》

第二章 线性规划 线性规划是运筹学中最重要的分支,也是运筹学的基础.

线性规划问题最早 是苏联学者康托洛维奇(L.V. Kantorovich,1912―1986)于1939 年提出的,但他 的工作当时并未广为人知.第二次世界大战中,美国空军的一个研究小组 SCOOP(Scientific Computation Of Optimum Programs,最优程序的科学计算)在研 究战时稀缺资源的最优化分配问题时, 提出了线性规划问题. 丹齐格(G.B.Dantzig) 于1947 年提出了求解线性规划问题的单纯形法,单纯形法至今还是求解线性规 划最有效的方法之一. 本章将介绍线性规划的模型和基本概念以及单纯形法的基本原理、 软件求解 方法及线性规划在经济分析中的应用. 运筹学(第二版)

12

第一节 线性规划实例与模型 运用线性规划方法解决实际问题的前提是把实际问题转化为数学问题,也就是建立线 性规划模型,不同类型的问题建立线性规划模型的方法不尽相同.下面通过具体实例学习 建立线性规划模型的方法.

一、线性规划实例 线性规划的应用领域十分广泛,主要包括生产计划、物资调运、资源优化配置、物料配 方和经济规划等问题,在

第一章(绪论)中介绍了生产计划问题,下面介绍另外两种决策问题. 例2-1 合理配料问题. 某饲料厂用玉米胚芽粕、大豆饼和酒糟等

3 种原料生产

3 种不同规格的饲料,由于

3 种原料的营养成分不同,因而不同规格的饲料对

3 种原料的比例有特殊要求,具体要求及 产品价格、原料价格、原料数量见表 2-1,试制订总利润最大的生产计划. 表2-1 工厂生产数据 规格要求 产品 Q1 产品 Q2 产品 Q3 原料单价/(元/kg) 原料可用量/kg 原料 P1 ≥15% ≥20% 25% 1.7

1500 原料 P2 ≥25% ≥10% 1.5

1000 原料 P3 ≤40% 1.2

2000 单位产品的利润/(元/kg)

2 3 2.3 (1) 问题分析. 合理配料问题是一个特殊的生产计划,该问题与

第一章中案例的生产计划的不同之处 在于产品对原料的消耗量不明确,只给了一个限制范围,同时原料之间不发生化学反应, 产品的产量等于原料之和.因而方案就不是只确定产品的产量,还需要明确生产不同产品 原料的数量,设 为生产第 种饲料使用第 种原料的数量 ,则第 种饲 料的产量为 ,第 种原料的使用量为 . 问题的目标是生产利润最大化,而利润等于销售收入减去成本,销售收入等于价格乘 以产量,即 ,成本等于购买原料的支出,等于原料价格乘以原料 需求数量,即 .所以总利润为 问题的约束包括原料供给限制、产品规格限制和变量自身限制,其中原料供给限制要 求原料的需求量小于等于最大供给量,即

第二章 线性规划

13 产品的规格限制要求不同原料占总产量的比例符合要求,即 上述约束是分式约束,为了写成线性规划形式,转化成以下等价形式,即 变量非负限制为 (2) 模型. 该工厂的生产计划问题就是在原料需求不超过可用量的限制下使得总利润最大,因而 对应的数学模型为 (2-1) 运筹学(第二版)

14 提示(1) 配料问题是一种特殊的生产计划问题,其与

第一章(绪论)中的生产计划问题的区别 在于一般生产计划问题中生产单位产品对原料的消耗量是确定的,但配料问题中生产单位 产品对原料的消耗量是不确定的,只给了一个数量限制范围,因而仅用每种产品的产量不 能表示出原料的消耗量,需要把产品产量和原料的消耗量同时作为变量. (2) 由于配料问题中没有发生化学反应,原料的数量和就是产品的产量,因而题目中把 产品的产量用原料数量和替换,减少了

3 个变量.不替换也可以,但必须在约束中添加 产 量等于原料消耗量和 这一组约束. 例2-2 运输问题. 一个啤酒公司在山东有 个生产厂, 每个生产厂计划期内生产的数量为 . 这 个生产厂的产品销往山东各市地,公司把山东市场分成了 个销售区,每个销售区计 划期内的销售量预计为 .假设生产总量和预期销售总量相等,且已知从第 个生产厂运单位产品到第 个销售区的运价为 .问应如何组织 运输才能使总运费最小? (1) 问题分析. 该问题是一个典型的运输问题,生产厂是供应地,销售区是需求地.问题的变量是从 第 个生产厂运到第 个销售区的产品数量,设为 ,则总运费为 ,从第 个生产厂运出的总量为运到各销售区之和,即 ,运到第 个销售区的产品数量等于从各生产厂运输之和,即 .显然,运出的量 不能超过生产量,运入的量不能低于需求量,由于生产总量和预期销售总量相等,所以每 个生产厂运出量正好等于生产量,每个销售区的运入量等于需求量,即有约束 (2) 模型. 在供求约束下使得总费用最小的线性规划模型为 (2-2)

第二章 线性规划

15 该规划是针对一般情况建立的,不同公司的具体数据不同,把数据代入模型就可以得 到具体实例的模型. 提示(1) 建立模型的基础是对问题的分析,分析问题需要明确问题的基本要素,问题的基本 要素对应模型的变量、目标和约束等基本要素. (2) 建立模型的过程就是用数学语言表述模型的

3 个基本要素的过程.首先确定变量, 也就是主动改变量,然后用变量表示其他量,给出约束和目标函数. (3) 在建立模型时不要遗漏变量非负约束,当变量表示数量时,如果取值不会为负值, 则需要添加变量非负约束.

二、线性规划模型 通过上面

3 个实例可以看出,线性规划的目标可能是最大也可能是最小,约束可能是 等式也可能是不等式,3 个实例的变量都是非负的,有时变量或部分变量要求允许取负值, 称为自由变量.因而,一般的线性规划模型的形式为 (2-3) 其中 为决策变量, 为目标函数系数, 为约束系数.记 变量为 ,向量 为价值向量,向量 为右端 向量,矩阵 为系数矩阵. 如果变量都是非负的,约束都是不等式,并且对于目标是求最小的线性规划模型,不 等号都是大于等于号,或者对于目标是求最大的线性规划模型,不等号都是小于等于号, 则称为规范形式的线性规划模型,模型为 或 如果线性规划的目标是求最小,约束都是等式,变量都是非负,则称为标准形式的线 性规划模型,其形式为 运筹学(第二版)

16 提示(1) 有些教材中标准形式是以最大为目标,这不影响问题的说明,只要在一本书中统一 要求就可以. (2) 一般形式的线性规划不能用矩阵形式表示,因为其约束的符号不统一.

三、基本概念 为了求解模型,首先给出一些常用的概念,给变量的每个分量一个赋值就得到规划的 一个解,如果解满足所有的约束条件,则称为可行解,由可行解组成的集合称为可行解集, 也称为可行域,对于标准形式的线性规划,其可行解集可写为 求解线性规划是要在可行解集合中寻找使得目标函数值最优的解,在可行域中目标函 数值最小(或最大)的可行解称为最优解,最优解的目标函数值为最优值.最优解的全体称为 最优解集合,对于以最小为目标的线性规划,其最优解集合可写为 } 提示(1) 线性规划的解不要求是可行的,这与方程组或不等式组的解有所区别. (2) 最优解不一定唯一,可以有多个解是最优解,但最优值一定是唯一的.

四、模型转换 实际问题的线性规划模型往往是一般形式的,而在求解或者分析模型时需要标准形式 或者规范形式,这就需要把一般形式的线性规划转化为标准形式或者规范形式.模型形式 的转化主要是把不符合要求的格式转化为符合要求的格式,如把自由变量转化为非负变量、 把不等式约束转化为等式约束及把求最大的目标转化为求最小的目标等.下面分别考虑变 量、目标和约束的转化问题. 1. 变量转换 为了保证模型等价,需要用非负变量替换自由变量,如果用一个非负变量无法保证模 型的线性,因而用两个非负变量的差来替换一个自由变量,即令自由变量 ,其中为非负变量. 显然,如果 ,则 ;

如果 ,则 ;

如果 ,则 .这 样就把 的正负转化为 与 的大小关系. 在模型中把所有的 用 替换, 则可以减

第二章 线性规划

17 少一个自由变量,如果还有自由变量可用同样方法处理. 2.目标转换 一个函数的最大值与其相反数函数的最小值在同一个变量取值上达到,并且两个目标 值互为相反数,即 .在目标转化时对于 ,用 替换, 求得的最优解相同,而最优值互为相反数. 3.约束转换 约束的转换主要是需要把不等式转化为等式,在转化时用一个新的非负变量表示不等 式两边的差,用大的一边减去小的一边,通过变量非负约束来代替不等式约束. 对于大于等于的不等式 , 令,则与不等式等价,约束可以写成 对于小于等于的不等式 ,令,则与不等式等价,约束可以写成 引入的非负变量称为松弛变量,表示不等式的松紧性,当其等于

0 时不等式取等号, 当其大于

0 时不等式取严格大于号.对于两种不等式之间的转化,通过不等式两边同乘以 -1 就可以实现,一个等式等价于两个符号相反的不等式. 提示(1) 引入的非负变量和松弛变量的符号可以和模型原有变量一致, 也可以用新的符号在 同一个模型中统一起来,一个符号不能表示两个变量. (2) 模型转化一般先转化变量,再考虑目标和约束. (3) 不等式转化为等式可以简单记为加上或减去一个非负变量,左边大则是减法,左边 小则是加法. 例2-3 把问题转化为标准形式. 解:该题目有一个自由变量,约束都是不等式,目标函数求最大,因而转化为标准形 式需要把自由变量化为非负变量,把目标变成最小,约束化为等式.首先引入两个非负变 量,即 ,令 ,代入规划变为 运筹学(第二版)

18 然后目标函数乘负号........