教学设计教案 优化问题与规划模型

1、3.6 优化问题与规划模型 与最大、最小、最长、最短等等有关的问题都是优化问题。 优化问题分类：（非）线性规划、整数规划、0-1规划、（多）目标规划、（与时间有关的）动态规划、（系数是随机变量的）随机规划。6.0 多变量优化 一个城郊的社区计划更新消防站。原来的消防站在旧城中心。规划要将新的消防站设置得更科学合理。在前一个季度收集了消防队对火警反应时间的资料：平均要用3.2分钟派遣消防队员；消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。行车时间的资料列于表1Distance（miles）：距离（英里）Drive Time（minutes）：行车时间（分）表1 关于设备位置问题的反

2、应时间资料从消防官员处得到的从城区的不同区域打来的求救电话频率的数据列于图1。其中每一格代表一平方英里，格内的数字为每年从此区域打来的紧急求救电话的数量。1）求反应时间。消防队对离救火站r英里处打来的一个求救电话需要的反应时间估计为d分钟。2）求平均反应时间。设城区位区域0,60,6内，(x,y)是新的消防站的位置。根据求救电话频率，确定消防队对求救电话的平均反应时间z=f(x,y) 3）求新的消防站的最佳位置。即确定函数f(x,y)的极小值点。首先， 用随机搜索算法：在可行域0,60,6内简单地选取n个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用Matlab求最值

3、点程序求出精确的最小值点: 求函数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. 求什么？分别安排多少亩地种蔬菜、棉花

4、、水稻？ x1 亩、 x2 亩、 x3 亩 2. 优化什么？ 产值最大 max f=10 x1+75x2+60 x33. 限制条件？ 田地总量 x1+x2+x3 50 劳力总数 1/2x1+1/3x2+1/4x3 20模型 I : 设决策变量：种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩，求目标函数 f=110 x1+75x2+60 x3在约束条件x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值规划问题：求目标函数在约束条件下的最值,规划问题包含3个组成要素: 决策变量、目标函数、约束条件。当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,

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

6、原点的直线所穿过的凸多边形的顶点即为取的极值的极点最优解。单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x1,x2,xn. 目标函数: Z=c1x1+c2x2+cnxn. 约束条件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的标准化10. 引入松弛变量将不等式约束变为等式约束. 若有 ai1x1+ainxnbi, 则引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 则引入 xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj.

7、 且有 Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m. 20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z=Z, 则问题变为 max Z .30. 引入人工变量,使得所有变量均为非负. 若 xi 没有非负的条件,则引入 xi 0 和 xi0, 令 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个分

8、量对应A的m个线性无关列, 则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解. 命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法，改进单纯形方法等。按这些计算方法编制程序，产生了Matlab优化工具箱和专门解优化问题的软件 Lindo、Lingo 。 用Matlab求解：标准的线性规划的模型： min f=cTxs.t. Ax b A1x=b1 LB x UBMatlab求解程序: x

9、,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+20y2 3. 限制条件？蔬菜的市场价 y1+1/2

10、y2 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 xi0, i=1,2,n.对偶问题: min f=yb s.t. yA c yi0, i=1,2,m.对偶定理: 互为对偶的两个线性规划问题, 若其中一个

11、有有穷的最优解, 则另一个也有有穷的最优解, 且最优值相等. 若两者之一有无界的最优解, 则另一个没有可行解模型 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元收入。

12、也就是说, 此时一个劳动力的估价为200元,而一亩土地估价为10元.这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出的贡献确定的估价, 被称为“影子价格”. 再进一步问，棉花价格提高到多少才值的生产？ 由 y1+1/3y2=10+200/3=76.675, （而其它两个约束条件是等式）可见，只有当棉花价格提高到 76.6元时才值得生产.Lingo命令Model:Max=110*x1+75*x2+60*x3;x1+x2+x3=50;1/2*x1+1/3*x2+1/4*x30表示每件第 j 类仪器的科学价值; aj 0表示每件第 j 类仪器的重量. 每类仪器件数不限, 但

13、装载件数只能是整数. 飞船总载荷不得超过数 b. 设计一种方案, 使得被装载仪器的科学价值之和最大.建模 记 xj 为第 j 类仪器的装载数. 求 目标函数 f= j cj xj 在约束条件 jaj xj b, xj 为正整数, 下的最大值.用分枝定界法求解整数规划问题基本思想:反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题, 且缩小最优质的取值范围,直到求得最优解. 例:求目标函数 f=3x1+2x2 在约束条件: 2x1+3x2 14, 2x1+x 2 9, x1 x 2为自然数下的最大值.用Lingo软件求解整数规划model:max =3*x1+2*x2;2*x1+

14、3*x2=14;2*x1+x2=9;gin(x1);gin(x2);end6.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=x 1 +1.2x 2 +0.9x 3 +1.

15、1x 4 在约束条件 2x 1 +3x 2 +3x 3 +4x 4 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 条航线, 一个航班可以飞不同的航线组合, 不同组合成本不同, 求开通所有航线且总费用最小的方案.抽

16、象为集合覆盖问题：设集合 S=1,2,3,4,5 有一个子集类=1,2,1,3,5,2,4,5,3,1,4,5其中每一个元素对应一个数 cj , 称为该元素的费用. 选 的一个子集使其覆盖S , 且总费用最低.即实际问题 1中5种产品能存放在一起的各种组合为 =1,2,1,3,5,2,4,5,3,1,4,5第 i 种组合的存储费用为 cj , 求这五种产品费用最低的储存方案。模型: 设决策变量：设是 S 的一个覆盖（一种存储方案）. 当的第 i 个元素属于, （即第 i 种组合被采用）记 xi=1，否则xi=0求 目标函数 f= i cixi在约束条件 x1 +x2 + x51 x1 + x3

17、 1 (因为第2种产品只在第1，3个组合中出现) x2 + x4 1 x3 + x6 1 x2 +x3 + x6 1 xi0，1， I=1,2, ,6, 下的最小值.混合问题例： 供货问题一家公司生产某种商品. 现有n 个客户, 第 j 个客户需要货物量至少为 bj, 可在m 各不同地点设厂供货. 在地区 i 设厂的费用为 di , 供货能力为 hi , 向第 j 个客户供应单位数量的货物费用为 cij. 如何设厂与供货使总费用最小.模型： 设决策变量： xij 为在地区 i 向第 j 个客户供货数量, 在地区 i 设厂，记 yi =1 , 否则 记 yi =0 求 目标函数 f= i (j

18、cij xij + yi di )在约束条件 i xij = bj, j xij -hi yi 0, xij0, yi 0，1 下的最小值6.4 多目标线性规划目标函数 fk=c (k)T x k=1,2, , m,s.t. Ax b A1x=b1 LB x UB有最优解 x (k), 记 f (k) =f(x (k)整体评价法min S=(f (k) - c(k)T x)/ f (k) （使相对偏差最小）s.t. Ax b A1x=b1 LB x UB有最佳妥协解 x*.习题:1. 资源分配, 生产甲肥1吨, 需要磷酸盐0.4吨, 硝酸盐1.8吨,利润1万元;生产乙肥1吨,需要磷酸盐0.1吨

19、,硝酸盐1.5吨,利润0.5万元. 现有磷酸盐10吨,硝酸盐66吨, 问甲、乙肥各生产多少吨获利最大？2. 营养配餐, 甲种食品每10克含5个单位的蛋白, 10个单位的铁, 单价3元;乙种食品每10克含7个单位的蛋白,4个单位的铁, 单价2元. 现需要一份食品, 含有35个单位的蛋白,40个单位的铁, 问如何配餐最省钱?3 资源的最优配置策略某工厂有1000台机器, 生产两种产品 A, B, 若投入 y 台机器生产A 产品, 则纯收入为 5y .若投入 y 台机器生产B 产品, 则纯收入为 4y . 又知, 生产A 种产品机器的年折损率为20%, , 生产B 种产品机器的年折损率为10%, 问

20、在5年内如何安排各年度的生产计划, 才能使总收入最高. 4. 混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据 4位运动员的4种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。 蛙泳 蝶泳 自由泳 仰泳甲 99 60 59 73 乙 79 65 93 87丙 67 93 63 81丁 56 79 86 76 5. 一家出版社准备再某市开设两个销售点，向七个区的大学生售书。每个区的大学生数量（千人）如图。 71 18 18 21 42 34 5629每个销售点只能向本区和一个相邻区的大学生售书。这两个销售点应该设在何处，才能使所供应的学生数量最大。6 仍考虑例2中的土方问题。在使用10立方码载

21、重量的自动倾卸卡车运输的情况下，公司已经确定了最优的运输方案。公司又有三辆更大的卡车可用于运输，载重量为20立方码。使用这些车辆可能会在运输中节省一些资金。载重10立方码载的卡车平均用20分钟装车，5分钟卸车，每小时平均开20英里，费用为每英里单位重量20美元；载重20立方码载的卡车平均用30分钟装车，5分钟卸车，每小时平均开20英里，费用为每英里单位重量30美元，为最大限度地节约运输费用，应如何安排车辆的使用？表3-5 例3.7中卡车问题的运输路线数据路线从到英里数运量（立方码）11B212522A417533C422543D410054D43507. 有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不许插队（即在任何阶段4位同学的顺序是