§3.6 优化问题与规划模型与最大、最小、最长、最短等等有关的问题都是优化问题。
解决优化问题形成管理科学的数学方法：运筹学。
运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。
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+60x33. 限制条件？田地总量 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 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。
于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法，改进单纯形方法等。
按这些计算方法编制程序，产生了专门解优化问题的软件 Lindo、Lingo 。
用Matlab求解：标准的线性规划的模型：min f=c T xs.t. Ax ≤ bA1x=b1LB ≤ x ≤ UBMatlab求解程序: [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 劳动力成本价格 y22. 优化什么？成本价格最低 Min g=50y1+20y23. 限制条件？蔬菜的市场价 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=c T x 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元时才值得生产.4 灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时, 最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题, 被称为参数线性规划.例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规划书籍将实际问题归结为线性规划模型是一个探索创造的过程。
线性规划模型的求解仍是计算数学的一个难题。
例 2 供货问题一家公司生产某种商品. 现有n 个客户, 第 j 个客户需要货物量至少为 bj,可在m 各不同地点设厂供货. 在地区 i 设厂的费用为 di , 供货能力为 hi,向第 j 个客户供应单位数量的货物费用为 cij. 如何设厂与供货使总费用最小.模型：设决策变量： xij为在地区 i 向第 j 个客户供货数量, 在地区 i 设厂，记 yi =1 , 否则记 yi=0求目标函数 f= ∑i (∑jcijxij+ yidi)在约束条件∑i xij=bj, ∑jxij-hiyi≤0, xij≥0, yi∈{0，1} 下的最小值例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=100xi≥0 , i=1,…,8 下的最小值用Matlab程序解得 xopt =(40, 20, 0, 0, 30, 0, 0, 0) , f (xopt)= 7（实际上应要求xi为正整数。
这是一个整数规划问题）。
6.2 整数规划如果要求决策变量取整数, 或部分取整数的线性规划问题, 称为整数规划.例 4 . 飞船装载问题设有n种不同类型的科学仪器希望装在登月飞船上, 令cj>0表示每件第 j 类仪器的科学价值; aj>0表示每件第 j 类仪器的重量. 每类仪器件数不限, 但装载件数只能是整数. 飞船总载荷不得超过数 b. 设计一种方案, 使得被装载仪器的科学价值之和最大.建模记 xj为第 j 类仪器的装载数.求目标函数 f= ∑j cjxj在约束条件∑jajxj≤ b, xj为正整数, 下的最大值.用分枝定界法求解整数规划问题基本思想:反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题, 且缩小最优质的取值范围,直到求得最优解.例:求目标函数 f=3x1+2x2在约束条件: 2x1+3x2≤14, 2x1+x2≤ 9, x1x2为自然数下的最大值.用Lindo软件求解整数规划max 3x1+2x2s.t.2x1+3x2<=142x1+x2<=9endgin x1gin x2(或者用 gin 2 代替gin x1 gin x2)6.3 0-1规划如果要求决策变量只取0 或 1的线性规划问题, 称为0-1规划.0-1 约束不一定是由变量的性质决定的, 更多地是由于逻辑关系引进问题的例5 背包问题一个旅行者的背包最多只能装 6 kg 物品. 现有 4 件物品的重量和价值分别为2 kg ,3 kg, 3 kg,4 kg, 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大?建模: 记 xj为旅行者携带第 j 件物品的件数, 取值只能为 0 或 1.求目标函数 f=x1 +1.2x2+0.9x3+1.1x4在约束条件 2x1+3x2+3x3+4x4≤ 6下的最大值.用Lingo 软件求解0-1规划Model:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4<=6;@int(x1);@int(x2);@int(x3);@int(x4);end例 6 集合覆盖问题实际问题 1 某企业有5种产品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于组合不同所需费用不同. 求费用最低的储存方案.实际问题 2 某航空公司在不同城市之间开辟了 5 条航线, 一个航班可以飞不同的航线组合, 不同组合成本不同, 求开通所有航线且总费用最小的方案.抽象为集合覆盖问题：设集合S={1,2,3,4,5} 有一个子集类φ={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}其中每一个元素对应一个数 c j , 称为该元素的费用. 选φ的一个子集使其覆盖S , 且总费用最低.即实际问题 1中5种产品能存放在一起的各种组合为φ={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}第 i 种组合的存储费用为 cj, 求这五种产品费用最低的储存方案。