规划问题

第五章 规划问题

5.1线性规划

线性规划概述

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。以下通过几个例子加深对线性规划的理解

5.1.1 生产与销售计划问题

5.1.1.1 问题实例

例5.1 某公司用两种原油（A和B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油A和B的库存量分别为500t和1000t，还可以从市场上买到不超过1500t的原油A。原油A的市场价为：购买量不超过500t时的单价为10000元/t；购买量超过500t但不超过1000t时，超过500t的部分8000元/t；购买量超过1000t时，超过1000t的部分6000元/t。该公司应如何安排原油的采购和加工。

5.1.1.2 建立模型 问题分析

安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差。这里的难点在于原油A的采购价和购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。 模型建立

设原油A的购买量为x（单位：t），根据题目所给数据，采购的支出c(x)可表示为如下的分段线性函数（以下价格以千元/t为单位）：

?10x,0?x?500,?c(x)??1000?8x,500?x?1000, (1)

?3000?6x,1000?x?1500.? 设原油A用于生产甲、乙两种汽油的数量分别为x11和x12，原油B用于生产甲、乙两种汽油的数量分别为x21和x22，则总的收入为4.8(x11?x12)?5.6(x12?x22)(千元)。于是本例的目标函数（利润）为

max z?4.8(x11?x12)?5.6(x12?x22)?c(x) (2)

约束条件包括加工两种汽油用的原油A、原油B库存量的限制，原油A购买量的限制，

以及两种汽油含原油A的比例限制，它们表示为

x11?x12?500?x (3) x21?x22?1000 (4) x?1500 (5)

x11?0.5 (6) x11?x21x12?0.6 (7) x12?x22x11,x12,x21,x22,x?0 (8)

由于（1）式中的c(x)不是线性函数，（1）~（8）给出的是一个非线性规划。而且，对

于这样用分段函数定义的c(x)，一般的非线性规划软件业难以输入和求解。能不能想办法将该模型化简，从而用现成的软件求解呢？

5.1.1.3 求解模型

下面介绍3种解法。

第1种解法 一个自然的想法是将原油A的采购量x分解为三个量，即用x1,x2,x3分别表示以价格10千元/t、8千元/t、6千元/t采购的原油的吨数，总支出为c(x)?10x1?8x2?6x3，且

x?x1?x2?x3 (9)

这时目标函数（2）变为线性函数：

max z?4.8(x11?x12)?5.6(x12?x22)?(10x1?8x2?6x3) (10)

应该注意到，只有当以10千元/t的价格购买x1=500(t)时，才能以8千元/t的价格购买

x2(?0)，这个条件可以表示为

(x1?500)x2?0 (11)

同理，只有当以8千元/t的价格购买x2=500(t)时，才能以6千元/t的价格购买x3(?0), 于是

(x2?500)x3?0 (12)

此外x1,x2,x3的取值范围是

0?x1,x2,x3?500 (13)

由于有非线性约束（11）、（12）、（3）~（13）构成非线性规划模型。将该模型输入LINGO软件如exam0501a.lg4所示：

将文件存储并命名为exam0501a.lg4，执行菜单命令“LINGO|Solve”，运行该程序得到

最优解是用库存的500t原油A、500t原油B生产1000t汽油甲，不购买新的原油A，利润为4800（千元）。

但是此时LINGO得到的结果只是一个局部最优解（local optimal solution）,还能得到更好的解吗？

可以用菜单命令“LINGO|Options”在“Global Solver”选项卡上启动全局优化（use global solver）选项，然后重新执行菜单命令“LINGO|Solve”，运行该程序得到

此时LINGO得到的结果是一个全局最优解（global optimal solution）:购买1000t原油A，与库存的500t原油A和1000t原油B一起，共生产2500t汽油乙，利润为5000（千元），高于刚刚得到的局部最优解对应的利润4800（千元）。

第2种解法 引入0-1变量将（11）和（12）转化为线性约束。

令y1=1,y2=1,y3=1分别表示以10千/t、8千元/t/、6千元/t的价格采购原油A，则约束（11）和（12）可以替换为

500y2?x1?500y1 (14)

500y3?x2?500y2 (15)

x3?500y3 (16)

y1,y2,y3?0或1 (17)

式（3）~（10），式（13）~（17）构成混合整数线性规划模型，将它输入LINDO软件如exam0501b.ltx所示. 运行该程序得到

这个结果与前面非线性规划模型用全局优化得到的结果相同。

第3种解法 直接处理分段线性函数c(x).式（1）表示的函数c(x)如图5-1所示。

c(x)12000 9000 5000 01500 x 图5-1 分段线性函数c(x)图形

500 1000 记x轴上的分点为b1=0,b2=500,b3=1000,b4=1500.当x属于第1个小区间[b1,b2]时，记x=z1b1+zc(x)=z

12b

22,z1+zc(b

22=1,z1,z

2?0,因为c(x)在[b1,b2]上是线性的，所以

2c(b

1)+z).同样，当x属于第2个小区间[b,b

3]时，记

x=z2b2+z3b3,z2+z3=1,z2，z3?0,c(x)=z2c(b2)+z3c(b3).当x属于第3个小区间[b3,b4]时，x=z3b3+z4b4,z3+z4=1,z3，z4?0,c(x)=z3c(b3)+z4c(b4).为了表示x在哪个小区间，引入0-1变量yk(k=1,2,3),当x在第k个小区间时，yk=1，否则，yk=0.这样，z1，z2，z3，z4，y1,y2,y3应满足

z1?y1,z2?y1?y2,z3?y2?y3,z4?y3 （18）

z1?z2?z3?z4?1, zk?0 (k?1,2,3,4) （19）

y1?y2?y3?1 ， y1,y2,y3?0或1 （20）

此时x和c(x)可以统一地表示为

x?z1b1?z2b2?z3b3?z4b4?500z2?1000z3?1500z4 （21）

c(x)?z1c(b1)?z2c(b2)?z3c(b3)?z4c(b4)?5000z2?9000z3?12000z4 （22）

式（2）~（9），式（18）~（22）也构成一个混合整数线性规划模型，可以用LINDO求解。不过，我们还是将它输入LINGO软件，因为其扩展性更好（即当分段函数的分段数更多时，只需要对下面程序作很小的改动）。输入的LINGO模型如exam0501c.lg4所示：

求解，得到的结果如下（略去已知参数b和c的显示结果）：

可见，得到的最优解和最优值与第2种解法相同。

备注 这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第2种和第3种解法，第3种解法更具一般性，其做法如下。

设一个n段线性函数f(x)的分点为b1?```?bn?bn?1,引入zk将x和f（x）表示为

x??zkbkk?1n?1 （23）

f(x)??zkf(bk)k?1n?1 （24）

zk和0-1变量yk满足

Variable Value Reduced Cost P( 1) 1.000000 0.000000 P( 2) 0.000000 0.000000 P( 3) 0.000000 0.000000 Z( 1) 0.000000 0.000000 Z( 2) 0.000000 0.000000 Z( 3) 29.25000 0.000000 X( 1) 1.875000 0.000000 X( 2) 3.750000 0.000000 第一级的最优偏差为0，进行第二轮计算。

在做第二级目标计算时，P(1)，P(2)，P(3)分别输入0，1，0，由于第一级偏差为0，因此Goal(1)输入值为0，Goal(2)输入一个较大的值，计算结果如下（只列出相关结果）：

Global optimal solution found.

Objective value: 0.000000 Total solver iterations: 2

Variable Value Reduced Cost P( 1) 0.000000 0.000000 P( 2) 1.000000 0.000000 P( 3) 0.000000 0.000000 Z( 1) 0.000000 0.000000 Z( 2) 0.000000 1.000000 Z( 3) 29.25000 0.000000 GOAL( 1) 0.000000 0.000000

X( 1) 1.875000 0.000000

X( 2) 3.750000 0.000000 第二级的最优偏差仍为0，进行第三级计算。

在做第三级的计算中，P(1)，P(2)，P(3)分别输入0，0，1，由于第一级，第二级偏差均为0，因此Goal(1)和Goal(2)输入值也均为0，计算结果如下（只列出相关结果）： Global optimal solution found.

Objective value: 29.00000 Total solver iterations: 0

Variable Value Reduced Cost P( 1) 0.000000 0.000000 P( 2) 0.000000 0.000000 P( 3) 1.000000 0.000000 Z( 1) 0.000000 0.000000 Z( 2) 0.000000 -5.666667

Z( 3) 29.00000 0.000000 GOAL( 1) 0.000000 0.000000 GOAL( 2) 0.000000 0.000000 GOAL( 3) 0.000000 0.000000 X( 1) 2.000000 0.000000 X( 2) 4.000000 0.000000 B( 1) 12.00000 0.000000 G( 1) 1500.000 0.000000 G( 2) 0.000000 0.000000 G( 3) 16.00000 0.000000 G( 4) 15.00000 0.000000 DPLUS( 1) 100.0000 0.000000 DPLUS( 2) 0.000000 0.000000 DPLUS( 3) 0.000000 6.000000 DPLUS( 4) 5.000000 0.000000 DMINUS( 1) 0.000000 0.000000 DMINUS( 2) 0.000000 11.33333 DMINUS( 3) 8.000000 0.000000 DMINUS( 4) 0.000000 1.000000

最终结果是：x1?2,x2?4，最优利润是1600元，第三级的最优偏差为29。 比较多个LINGO程序和一个完整的LINGO程序，不难发现虽然它们的最终结果相同，但是某些中间结果不同，这是因为当线性规划问题有无穷多解时，LINGO软件只能给出一个最优解。由于线性规划的任一最优解均是全局解，因此，无论任何解，起最优目标函数值是相同的。

5.4 其他规划模型 5.4.1动态规划

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方

法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

5.4.2非线性规划

非线性规划具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个 n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。

非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩－塔克条件)的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法,它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。

要对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系,称之为目标函数。然后将各种限制条件加以抽象,得出决策变量应满足的一些等式或不等式，称之为约束条件。非线性规划问题的一般数学模型可表述为求未知量x1，x2，…，xn，使满足约束条件：

gi(x1，…，xn)≥0 i＝1,…,m hj(x1，…，xn)＝0 j＝1,…,p

并使目标函数f(x1，…,xn)达到最小值(或最大值)。其中f，诸gi和诸hj都是定义在n维向量空间Rn的某子集D(定义域)上的实值函数,且至少有一个是非线性函数。 上述模型可简记为： min f(x)

s.t. gi(x)≥0 i＝1,…,m hj(x)＝0 j＝1,…,p

其中x＝(x1，…,xn)属于定义域D，符号min表示“求最小值”，符号s.t.表示“受约束于”。

定义域D中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解x*,如果存在x*的一个邻域，使目标函数在x*处的值f(x*)优于 (指不大于或不小于)该邻域中任何其他可行解处的函数值，则称x*为问题的局部最优解（简称局部解）。如果f(x*)优于一切可行解处的目标函数值,则称x*为问题的整体最优解（简称整体解）。实用非线性规划问题要求整体解，而现有解法大多只是求出局部解。

5.4.3二次规划

二次规划是一类特殊的非线性规划。它的目标函数是二次函数，约束条件是线性的。求解二次规划的方法很多。较简便易行的是沃尔夫法。它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等

二次规划分为凸二次规划与非凸二次规划，前者的KT点便是其全局极小值点，而后者的KT点可能连局部极小值点都不是。若它的目标函数是二次函数，则约束条件是

线性的。由于求解二次规划的方法很多，所以较为复杂；其较简便易行的是沃尔夫法，它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。

本文来源：https://www.bwwdw.com/article/3lgv.html