优化问题与规划模型

1、3.6优化问题与规划模型与最大、最小、最长、最短等等有关的问题都是优化问题.解决优化问题形成管理科学的数学方法：运筹学运筹学主要分支：（非）线性规 划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论.6. 1 线性规划1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题1947年美国数学家乔治丹契克、冯诺伊曼提出线性规划的一般模型及理 论.1. 问题例1作物种植安排一个农场有50亩土地，20个劳动力，计划种蔬菜,棉花和水稻.种植这三种农 作物每亩地分别需要劳动力1/2 1/3 1/4,预计每亩产值分别为110元，75元, 60元.如何规划经营使经济效益最大分析：以取得最高的产值

2、的方式达到收益最大的目标.1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ X亩、X：亩、X3亩2. 优化什么？产值最大max f =10x1+75x2+60x33. 限制条件？田地总量 X1+X2+X3S 50劳力总数l/2xl+l/3x2+l/4x3 20模型I :设决策变量：种植蔬菜X1亩，棉花氐亩，水稻X3亩，求目标函数 f=110xi+75x2+60x3在约束条件xx+x:+x3 501/2x】+1/3x：+1/4x3S20下的最大值规划问题：求目标函数在约束条件下的最值，规划问题包含3个组成要素：决策变量、目标函数、约束条件.当LI标函数和约束条件都是决策变量的线性函数时，称为线

3、性规划问题，否则称 为非线性规划问题.2. 线性规划问题求解方法称满足约束条件的向量为可行解,称可行解的集合为可行域，称使目标函数达最值的可行解为最优解.命题1线性规划问题的可行解集是凸集.因为可行解集山线性不等式组的解构成两个变量的线性规划问题的可行解集是平 面上的凸多边形.命题2线性规划问题的最优解一定在可行解集的某个极点上达到.图解法：解两个变量的线性规划问题，在平面上画出可行域，计算L1标函数在各 极点处的值，经比较后，取最值点为最优解.命题3当两个变量的线性规划问题的L1标函数取不同的口标值时，构成一族平行 直线，目标值的大小描述了直线离原点的远近.于是穿过可行域的U标直线组中最远离

4、（或接近）原点的直线所穿过的凸多边形的顶 点即为取的极值的极点一最优解.单纯形法：通过确定约束方程组的基本解，并计算相应LI标函数值，在可行解 集的极点中搜寻最优解.正则模型：决策变量:xn x2, , xn. U标函数：ZxXi+CzX：+crxn模型的标准化1.引入松弛变量将不等式约束变为等式约束.aiiXi+-+axnXn+ Xn-i =bx xn-j 二bj若求min Z,令Z二-Z,则问x,没有非负的条件,则引入x/ M若有 aiiXi+-+ainXr.bi,则引入 0,使得 若有3X1+5x36,则引入Xr-j 0,使得 且有 Z=c1x1+c2x2+ +caxn+0xa-i+ +

5、0xe2.将LI标函数的优化变为U标函数的极大化. 题变为max Z3.引入人工变量，使得所有变量均为非负.若 0和x/ $0,令XF x/ - xj ,则可使得问题的全部变量均非负. 标准化模型求变量xn x2,，xn,max Z = 6Xi+ CnXn, s匕 a11x1+-+ alaxR= bn&収+ amxn= ba,Xi0, X 0,定义：若代数方程/二b的矗向量有n-m个分量为零，其余m个分量对应A的m 个线性无关列，则称该解向量为方程组的一个基本解在一个线性规划问题中，如 果一个可行解也是约束方程组的基本解，则称之为基本可行解.命题4 一个向量x是线性规划问题可行解集的一个极点，

6、当且仅当它是约束方 程的一个基本可行解.于是寻找取得极值的凸集极点的儿何问题变成了求代数方程基本解的问题，形成了 解优化问题的单纯形方法，改进单纯形方法等.按这些计算方法编制程序，产生了 专门解优化问题的软件Lindo、Lingo用Mat lab求解：标准的线性规划的模型：min f=cTxs. t Ax bAlx=blLB x UBMat lab 求解程序:x, f=l inprog (c, A, b, Al, bl, LB, UB)还有软件Excel也可应用于解优化问题.3对偶问题例1作物种植安排一个农场有50亩土地，20个劳动力，计划种蔬菜,棉花和水稻.种植这三种农 作物每亩地分别需要劳

7、动力1/21/3 1/4,预计每亩产值分别为110元，75元,60元.如何规划经营使经济效益最大分析：以最经济的投入达到收益最大的目标.(或者说以直接出售土地和劳动力的方式达到收益最大的U标)1求什么？ 土地成本价格刃劳动力成本价格y：2优化什么？成本价格最低Min g=50yi+20y23限制条件？ 蔬菜的市场价 棉花的市场价 水稻的市场价 模型IIyx+l/2y2 110yi+l/3y： 75 yi+l/4y：60设决策变量：对单位土地和对单位劳力投入成本价格分别为yx兀求目标函数 goOyOy：在约束条件 yi+l/2y： nil0yi+l/3y& 75yi+l/4yQ60 下的最小值.

8、设A是mxn矩 阵，c 是 nxl 向量，b 是 mxl 向量 x是n x 1向量，y是1 x m向量问题：max f=cTxs. t. Ax 0, i=l, 2, n.对偶问题：min f=ybs. t. yA cyO, i=l, 2, m.对偶定理：互为对偶的两个线性规划问题，若其中一个有有穷的最优解，则另一 个也有有穷的最优解，且最优值相等.若两者之一有无界的最优解，则另一个没 有可行解模型I II构成对偶问题.模型 I 解得最优解(optimun solution)XOPt=(30 0 20), 最大值 f(x。二4500型型型一值 模模模进产II解得最优解y(10 200), 最小值

9、 g(y=4500I给出了生产中的资源最优分配方案II给岀了生产中资源的最低估价.:如果增加对土地和劳动力的投入，每种资源的单位投入增加会带来多少由最优解y二(10, 200)可见，多耕一亩地增加10元收入，多一个劳动力增加200 元收入也就是说，此时一个劳动力的估价为200元，而一亩土地估价为10元. 这种价格涉及到资源的有效利用，它不是市场价格，而是根据资源在生产中做出 的贡献确定的估价，被称为“影子价格” 再进一步问，棉花价格提高到多少才值的生产？由yx+l/3y：=10+200/3=76. 675,(而其它两个约束条件是等式)可见，只有当棉 花价格提高到76. 6元时才值得生产4灵敬度

10、分析当线性规划问题中的常数发生变化(山于测量误差或具有多个取值可能)时，最优解 是否会随之变化？通常假定变化的常数是某参数的线性函数讨论参数取值与最优解的关系的问题, 被称为参数线性规划.例如，当农作物的价格发生变化时，生产计划是否应马上随之改变？参见线性规 划书籍将实际问题归结为线性规划模型是一个探索创造的过程.线性规划模型的求解仍是计算数学的一个难题.例2供货问题一家公司生产某种商品.现有n个客户，第j个客户需要货物量至少为 可在m各不同地点设厂供货.在地区i设厂的费用为供货能力为h , 向第j个客户供应单位数量的货物费用为5如何设厂与供货使总费用最小. 模型：设决策变量：Xij为在地区i

11、向第j个客户供货数量，在地区i设厂，记Yi =1 ,否则记y =0求目标函数 f= E： (Ej Cij Xu + yi di )在约束条件二 x.j 二b”工j xj -h y 0表示每件第j类仪器 的科学价值。a, 0表示每件第j类仪器的重量.每类仪器件数不限，但装载 件数只能是整数.E船总载荷不得超过数b.设计一种方案，使得被装载仪器的 科学价值之和最大建模记为第j类仪器的装载数.求目标函数f二2 6Xj在约束条件Nd X芒b,Xj为正整数，下的最大值.用分枝定界法求解整数规划问题基本思想:反复划分可行域并确定最优值的界限，将原问题不断地分枝为若干个子问 题，且缩小最优质的取值范围，直到

12、求得最优解.例：求U标函数f=3x:+2x:在约束条件：2Xi+3x: 14, 2xj+x 2 9, Xj x :为自然 数下的最大值.用Lindo软件求解整数规划 max 3xl+2x2 2xl+3x2=142xl+x2二9endgin xlgin x2(或者用 gin 2 代替 gin xlgin x2)6.3 07规划如果要求决策变量只取0或1的线性规划问题，称为0-1规划.0-1约束不一定是山变量的性质决定的，更多地是山于逻辑关系引进问题的例5 背包问题一个旅行者的背包最多只能装6 kg物品.现有4件物品的重量和价值分别为2 kg , 3 kg, 3 kg, 4 kg, 1元，1. 2

13、元，0. 9元，1. 1元.应携带那些物品使 得携带物品的价值最大？建模：记X,为旅行者携带第j件物品的件数，取值只能为0或1.求 H 标函数 f二x j +1. 2x 2 +0. 9x 3+1. lx 4 在约束条件 2x 1 +3x 2 +3x 3 +4x 4 6 下的最大值.用Lingo软件求解0-1规划Model:Max=xl+1. 2*x2+0. 9*x3+l. I*x4o2*xl+3*x2+3*x3+4*x4=1,2, 1,3, 5), 2, 4,5, 3, 1, 4,5其中每一个元素对应一个数 6,称 为该元素的费用.选e的一个子集使其覆盖s,且总费用最低.即实际问题1中5种产品

14、能存放在一起的各种组合为二1,2, 1,3, 5), 2, 4,5, 3, 1, 4,5第 i 种组合的存储费用为 6 , 求这五种产品费用最低的储存方案.模型：设决策变量：设厶匸是S的一个覆盖(一种存储方案).当的第i个元 素属于厶（即第i种组合被采用）记XF1,否则XFO求目标函数f二匚CiXi在约束条件 Xi +x:+ x5l Xi + x3l（因为第2种产品只在第1, 3个组合中出现）X：+ X|1 X3 + X6 lx：+X3 + X6 1 Xi 0, 1 , 1=1, 2, 6,下的最小值.6.4多目标线性规划H 标函数 fk=c a）T x k-l, 2, .m,s. t Ax bAlx=blLB x .记 f （k） =f （x O）整体评价法min S二工（f oo - c（J x）/ f（k （使相对偏差最小）s. t Ax bAlx=blLB x UB有