§3.6 优化问题与规划模型
与最大、最小、最长、最短等等有关的问题都是优化问题。 优化问题分类：（非）线性规划、整数规划、0-1规划、（多）目标规划、（与时间有关的）动态规划、（系数是随机变量的）随机规划。 6.0 多变量优化
一个城郊的社区计划更新消防站。原来的消防站在旧城中心。规划要将新的消防站设置得更科学合理。在前一个季度收集了消防队对火警反应时间的资料：平均要用3.2分钟派遣消防队员；消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。行车时间的资料列于表1
Distance（miles）：距离（英里）
Drive Time（minutes）：行车时间（分）
表1 关于设备位置问题的反应时间资料
从消防官员处得到的从城区的不同区域打来的求救电话频率的数据列于图1。其中每一格代表一平方英里，格内的数字为每年从此区域打来的紧急求救电话的数量。 1）求反应时间。
消防队对离救火站r英里处打来的一个求救电话需要的反应时间估计为d分钟。 2）求平均反应时间。 设城区位区域[0,6]′[0,6]内，(x,y)是新的消防站的位置。根据求救电话频率，确定消防队对求救电话的平均反应时间z=f(x,y) 3）求新的消防站的最佳位置。
即确定函数f(x,y)的极小值点。首先， 用随机搜索算法：在可行域[0,6]′[0,6]内简单地选取n个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用Matlab求最值点程序求出精确的最小值点: 求函数fun在x0点附近的最小值点 [x，f] = fminsearch(fun, x0) 6.1 线性规划
1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》
1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题
例1 作物种植安排
一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大.
分析：以取得最高的产值的方式达到收益最大的目标.
1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x1 亩、 x2 亩、 x3 亩 2. 优化什么？ 产值最大 max f=10x1+75x2+60x3
3. 限制条件？ 田地总量 x1+x2+x3 ? 50 劳力总数 1/2x1+1/3x2+1/4x3 ? 20
模型 I : 设决策变量：种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩， 求目标函数 f=110x1+75x2+60x3
在约束条件x1+x2+x3 ? 50 1/2x1+1/3x2+1/4x3 ?20 下的最大值
规划问题：求目标函数在约束条件下的最值,
规划问题包含3个组成要素: 决策变量、目标函数、约束条件。
当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。
2. 线性规划问题求解方法
称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集.
因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。
命题2 线性规划问题的最优解一定在可行解集的某个极点上达到.
图解法： 解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。
命题3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。
于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。
单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型:
决策变量: x1,x2,…,xn. 目标函数: Z=c1x1+c2x2+…+cnxn. 约束条件: a11x1+…+a1nxn≤b1, …… am1x1+…+amnxn≤bm, 模型的标准化
10. 引入松弛变量将不等式约束变为等式约束.
若有 ai1x1+…+ainxn≤bi, 则引入 xn+i≥ 0, 使得 ai1x1+…+ainxn+ xn+i =bi 若有 aj1x1+…+ajnxn≥bj, 则引入 xn+j≥ 0, 使得 aj1x1+…+ajnxn- xn+j =bj. 且有 Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.
20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z’=–Z, 则问题变为 max Z’ . 30. 引入人工变量,使得所有变量均为非负. 若 xi 没有非负的条件,则引入 xi’≥ 0 和 xi’’≥0, 令 xi= xi’– xi’’, 则可使得问题的全部变量均非负. 标准化模型
求变量 x1, x2,…, xn, max Z = c1x1+…+ cnxn,
s. t. a11x1+…+ a1nxn= b1, …… am1x1+…+ amnxn= bm, x1 ≥ 0,…, xn ≥ 0,
定义: 若代数方程AX=B的解向量有n-m个分量为零, 其余m个分量对应A的m个线性无关列, 则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解.
命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。
于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法，改进单纯形方法等。按这些计算方法编制程序，产生了Matlab优化工具箱和专门解优化问题的软件 Lindo、Lingo 。
用Matlab求解：
标准的线性规划的模型： min f=cTx s.t. Ax ? b
A1x=b1 LB ? x ? UB
Matlab求解程序: [x,f]=linprog(c,A,b,A1,b1,LB,UB) 还有软件Excel 也可应用于解优化问题。
3 对偶问题
例1 作物种植安排
一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大.
分析：以最经济的投入达到收益最大的目标.
（或者说以直接出售土地和劳动力的方式达到收益最大的目标.） 1 求什么？土地成本价格 y1 劳动力成本价格 y2 2. 优化什么？ 成本价格最低 Min g=50y1+20y2 3. 限制条件？
蔬菜的市场价 y1+1/2y2 ? 110 棉花的市场价 y1+1/3y2 ? 75
水稻的市场价 y1+1/4y2 ? 60 模型 II .
设决策变量: 对单位土地和对单位劳力投入成本价格分别为 y1 y2 求目标函数 g=50y1+20y2
在约束条件 y1+1/2y2 ? 110 y1+1/3y2 ? 75 y1+1/4y2 ? 60 下的最小值.
设 A 是m ? n 矩阵，
c 是 n ? 1向量，b 是 m ? 1向量
x是 n ? 1向量, y是1 ? m 向量
问题: max f=cTx s.t. Ax ? b xi?0, i=1,2,?,n.
对偶问题: min f=yb s.t. yA ? c yi?0, i=1,2,?,m.
对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一个也有有穷的最优解, 且最优值相等. 若两者之一有无界的最优解, 则另一个没有可行解 模型 I II构成对偶问题.
模型 I 解得最优解(optimun solution) Xopt=(30 0 20), 最大值 f(xopt)=4500 模型 II 解得最优解 yopt=(10 200), 最小值 g(yopt)=4500.
模型I 给出了生产中的资源最优分配方案 模型 II 给出了生产中资源的最低估价.
进一步问：如果增加对土地和劳动力的投入，每种资源的单位投入增加会带来多少产值？ 由最优解 y=(10,200) 可见, 多耕一亩地增加10元收入，多一个劳动力增加200元收入。也就是说, 此时一个劳动力的估价为200元,而一亩土地估价为10元.
这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出的贡献确定的估价, 被称为“影子价格”.
再进一步问，棉花价格提高到多少才值的生产？
由 y1+1/3y2=10+200/3=76.6>75, （而其它两个约束条件是等式）可见，只有当棉花价格提高到 76.6元时才值得生产.
Lingo命令 Model:
Max=110*x1+75*x2+60*x3; x1+x2+x3<=50;
1/2*x1+1/3*x2+1/4*x3<=20; end
输出结果
Global optimal solution found at iteration: 2
Objective value:最优值 4500.000 Variable Value最优解 Reduced Cost
X1 30.00000 0.000000 X2 0.000000 1.666667 X3 20.00000 0.000000 Row Slack or Surplus Dual Price对偶价格 1 4500.000 1.000000 2 0.000000 10.00000 3 0.000000 200.0000
结果解释
reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量 Row Slack or Surplus 松弛量或剩余量，土地、劳动力剩余量为零。“资源” 剩余为零的约束为紧约束（有效约束）
4 灵敏度分析
当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时, 最优解是否会随之变化?
通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题, 被称为参数线性规划.
例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规划书籍
将实际问题归结为线性规划模型是一个探索创造的过程。
线性规划模型的求解仍是计算数学的一个难题。
例2 一家大建筑公司正在三个地点开掘。同时又在其他四个地点建筑，这里需要土方的填充。在1、2、3处挖掘产生的土方分别为每天150，400，325立方码。建筑地点A、B、C、D处需要的填充土方分别为175，125，225，450立方码。也可以从地点4用每立方码5美元的价格获得额外的填充土方。填充土方运输的费用约为一货车容量每英里20美元。一辆货车可以搬运10立方码的土方。表3-3给出了各地点间距离的英里数。求使公司花费最少的运输计划。
表3-3 例3.5中土方问题的英里数：建筑地点间的距离
挖掘地点
1 2 3 4
6.2 整数规划
在许多实际问题中，我们必须要处理离散变量如整数。离散数学曾被认为是比较神秘的领域，没有或几乎没有什么实际的应用。随着数字计算机的发明，离散数学变得极其重要。离散优化对时间安排、物资存储、投资、运输、制造业、生态学和计算机科学等方面的问题都非常有用。
如果要求决策变量取整数, 或部分取整数的线性规划问题, 称为整数规划.
当连续的决策变量变为离散变量时非线性优化问题通常会难解得多。没有连续性后可行域会变得很复杂，通常用一个图或树结构来描述。对一些类型的问题已经开发出了有效的求解算法，对这些算法的改进是一个非常活跃的研究领域，但与连续的情形一样，迄今还没有求解离散优化问题的普遍的有效算法。 例3 钢材截短
有一批钢材, 每根长7.3米. 现需做100套短钢材. 每套包括长2.9米, 2.1米,1.5米的各一根. 至少用掉多少根钢材才能满足需要, 并使得用料最省.
分析： 可能的截法和余料 第1种 7.3-(2.9× 2+1.5)=0 第2种 7.3-(2.9+2.1 × 2)=0.2 第3种 7.3-(2.9+1.5 × 2)=1.4 第4种 7.3-(2.9+2.1+1.5)=0.8
第5种 7.3-(2.1 × 2+1.5 × 2)=0.1 第6种 7.3-(2.1 × 3)=1
第7种 7.3-(2.1+1.5 × 3)=0.7 第8种 7.3-(1.5 × 4)=1.3
模型：设决策变量：按第i种方法截 xi 根钢材。 求目标函数 f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8
在约束条件 2x1+x2+x3+x4=100 2x2+x4+2x5+3x6+x7=100 x1+2x3+x4+2x5+3x7+4x8=100 xi ?0 , i=1,…,8 下的最小值
解得 xopt=(40, 20, 0, 0, 30, 0, 0, 0) , f (xopt )= 7
实际上应要求xi 为正整数。这是一个整数规划问题， 这里碰巧最优解是整数，所以用Matlab程序可以求得解。
接收填充土方的地点A B C D 5 2 6 10 4 5 7 5 7 6 4 4 9 10 6 2
§6优化问题与规划模型
