优化问题与规划模型

《优化问题与规划模型》由会员分享，可在线阅读，更多相关《优化问题与规划模型（7页珍藏版）》请在金锄头文库上搜索。

1、3.63.6 优化问题与规划模型优化问题与规划模型与最大、最小、最长、最短等等有关的问题都是优化问题与最大、最小、最长、最短等等有关的问题都是优化问题与最大、最小、最长、最短等等有关的问题都是优化问题。解决优化问题形成管理科学的数学方法： 运筹学。 运筹学主要分支： （非） 线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划1939 年苏联数学家康托洛维奇发表生产组织与计划中的数学问题1947 年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理 论. 1. 问题 例 1 作物种植安排一个农场有 50 亩土地, 20 个劳动力, 计划种蔬菜,棉花和水

2、稻. 种植这三 种农作物每亩地分别需要劳动力 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

3、在约束条件 x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值规划问题：求目标函数在约束条件下的最值, 规划问题包含 3 个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称 为非线性规划问题。2. 线性规划问题求解方法称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平 面上的凸多边形。 命题 2 线性规划问题的最优解一定在可行解集的某个极点上达到

4、. 图解法图解法： 解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各 极点处的值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行 直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶 点即为取的极值的极点最优解。 单纯形法单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型:决策变量: x1,x2,xn. 目标函数: Z=c1x1+c2x2+cnxn.约束条件: a11x1+a1nxnb1, am1x1

5、+amnxnbm, 模型的标准化 10. 引入松弛变量将不等式约束变为等式约束.若有 ai1x1+ainxnbi, 则引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 则引入 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= x

6、i 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 是线性规划问题可行解集的一个极点, 当且仅当它是约束方 程的一个基本可行解。 于是寻找取得极值的凸集极点的几何问

7、题变成了求代数方程基本解的问题，形成了 解优化问题的单纯形方法，改进单纯形方法等。按这些计算方法编制程序，产生了 专门解优化问题的软件 Lindo、Lingo 。 用 Matlab 求解： 标准的线性规划的模型：min f=cTx s.t. Ax bA1x=b1LB x UB Matlab 求解程序: x,f=linprog(c,A,b,A1,b1,LB,UB) 还有软件 Excel 也可应用于解优化问题。3 对偶问题 例 1 作物种植安排一个农场有 50 亩土地, 20 个劳动力, 计划种蔬菜,棉花和水稻. 种植这三 种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为

8、 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

9、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 xi0, i=1,2,n. 对偶问题: min f=yb s.t. yA c yi0, i=1,2,m.对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一 个也有有穷的最优解, 且最优值相等. 若两者之一有无界的最优解, 则另一个没 有可行解 模型 I II 构成对偶问题. 模型 I 解得最优解(optimun solution) Xopt=(30 0 20),

10、最大值 f(xopt) =4500 模型 II 解得最优解 yopt=(10 200), 最小值 g(yopt)=4500.模型 I 给出了生产中的资源最优分配方案 模型 II 给出了生产中资源的最低估价. 进一步问：如果增加对土地和劳动力的投入，每种资源的单位投入增加会带来多少 产值？ 由最优解 y=(10,200) 可见, 多耕一亩地增加 10 元收入，多一个劳动力增加 200 元收入。也就是说, 此时一个劳动力的估价为 200 元,而一亩土地估价为 10 元.这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出 的贡献确定的估价, 被称为“影子价格”. 再进一步问，

11、棉花价格提高到多少才值的生产？由 y1+1/3y2=10+200/3=76.675, （而其它两个约束条件是等式）可见，只有当 棉花价格提高到 76.6 元时才值得生产.4 灵敏度分析 当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时, 最优解 是否会随之变化? 通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题, 被称为参数线性规划. 例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规 划书籍将实际问题归结为线性规划模型是一个探索创造的过程。 线性规划模型的求解仍是计算数学的一个难题。例 2 供货问题 一家公司生产某种商品. 现

12、有 n 个客户, 第 j 个客户需要货物量至少为 bj,可在 m 各不同地点设厂供货. 在地区 i 设厂的费用为 di , 供货能力为 hi , 向第 j 个客户供应单位数量的货物费用为 cij. 如何设厂与供货使总费用最 小.模型： 设决策变量： xij 为在地区 i 向第 j 个客户供货数量, 在地区 i 设厂，记 yi =1 , 否则 记 yi =0 求 目标函数 f= i (j cij xij + yi di ) 在约束条件 i xij = bj, j xij -hi yi 0, xij0, yi 0，1 下的 最小值例 3 钢材截短有一批钢材, 每根长 7.3 米. 现需做 100

13、套短钢材. 每套包括长 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 根钢材。

14、求目标函数 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 下的最小值用 Matlab 程序解得 xopt=(40, 20, 0, 0, 30, 0, 0, 0) , f (xopt )= 7 （实际上应要求 xi 为正整数。这是一个整数规划问题） 。 6.2 整数规划 如果要求决策变量取整数, 或部分取整数的线性规划问题, 称为整数规划. 例 4 . 飞船装载问题设有 n 种不同类型的科学仪器

15、希望装在登月飞船上, 令 cj0 表示每件第 j 类仪 器的科学价值; aj 0 表示每件第 j 类仪器的重量. 每类仪器件数不限, 但装 载件数只能是整数. 飞船总载荷不得超过数 b. 设计一种方案, 使得被装载仪器 的科学价值之和最大.建模 记 xj 为第 j 类仪器的装载数. 求 目标函数 f= j cj xj 在约束条件 jaj xj b, xj 为正整数, 下的最大值.用分枝定界法求解整数规划问题 基本思想:反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问 题, 且缩小最优质的取值范围,直到求得最优解. 例:求目标函数 f=3x1+2x2 在约束条件: 2x1+3x2 14, 2x1+x 2 9, x1 x 2为自 然数下的最大值. 用 Lindo 软件求解整数规划 max 3x1+2x2 s.t. 2x1+3x2=14 2x1+x2=9 end gin x1 gin x2 (或者用 gin 2 代替 gin x1 gi