最优化多目标规划动态规划绪论.ppt

第五章 多目标规划 在实际问题中，衡量一个设计方案的好坏往往不止一个。例如：设计一个导弹，既要射程远，命中率高，还要耗燃料少；又如：选择新厂址，除了要考虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等社会因素。这类问题即为多目标数学规划问题。 第五章 多目标规划 早在1772年，Franklin就提出了多目标问题矛盾如何协调的问题，1896年，Pareto首次从数学角度提出了多目标最优决策问题，直到二十世纪50-70年代Charnes, Karlin, Zadeh等人先后做了许多较有影响的工作，多目标规划受到人们的关注。至今多目标规划已广泛应用于经济、管理、系统工程等科技的各个领域。 §1多目标规划问题举例 例1生产计划问题 某工厂计划生产两种产品甲和乙，生产每件甲的利润为4元，生产每件乙的利润为3元，每件甲的加工时间为每件乙的两倍，若全部时间用来加工乙，则每日可生产乙500件，但工厂每日供给的原料只够生产甲和乙的总数共400件，产品甲是紧俏商品，预测市场日需求量为300件。决策者希望制定一个日生产方案，不仅能得到最大的利润，且能最大地满足市场需求。 生产计划问题 [问题分析] 设每日生产甲、乙的数量分别为x1, x2, 令X=(x1, x2), 则其目标函数为利润 f1(X)=4x1 + 3x2 甲的产量 f2(X)=x1 都取最大值 满足约束条件 x1 + x2≤400（原料供应约束） 2x1 + x2≤500（加工时间约束） x1≥0，x2≥0 多目标规划问题举例 例2投资问题 假设在一段时间内有a（亿元）的资金可用于建厂投资，若可供选择的项目记为1,2,…,m, 而且一旦对第i个项目投资，则必须用掉ai（亿元）; 而在这段时间内这第个项目可得到的收益为ci（亿元）, 其中i=1,2,…,m, 问如何确定最佳的投资方案？ 投资问题 [问题分析] 上述要求的最佳方案应为：投资少，收益大。 多目标规划的标准形式 V-min F(X)=(f1(X), f2(X),…,fp(X))T s.t. gi(X)≤0, i=1,2,…,m 其中X=(x1,x2,…,xn)T, p≥2 这里V-min 是指对向量形式的p个目标(f1(X), f2(X),…,fp(X))T求最小。 一般假设多目标规划中的目标函数已经是规范化了的。 §2 多目标规划解的概念与性质 1. 多目标规划解的概念 例3 [解]分别对单个目标求出其最优解，对于第一个目标的最优解x(1)=1; 第二个目标的最优解x(2)=1, 为同一点，取x*=1作为多目标问题的最优解，其目标函数值F*(x) =(-2,-1). 可以用变量空间和目标函数空间来分别描述各种解的情况。 多目标规划解的概念 下面考察例1中生产计划问题。问：是否能找到一个可行解X*=(x1*, x2*)T使之同时为f1(X)与f2(X)的最大解？ 在可行域内容易求解 max f1(X)的唯一最优解为 (100, 300), 见图中B点。 max f2(X)的唯一最优解为 (250, 0), 见图中C点。 由此可得共同的最优解X*并不存在。当一目标达到最优时，另一目标达不到最优，两目标相互矛盾。因此需要根据别的原则，权衡两者之间的得失，从R中找出满意的方案来。 多目标规划解的概念 如何比较方案的好坏呢？ 就上述问题，设X∈R，Y∈R，称X比Y好（或Y比X劣），若 f1(X)f1(Y) f2(X) ≥f2(Y) 或 f1(X)≥f1(Y) f2(X) f2(Y) 不难得到除线段BC之外的其余R上的点均为劣解，而BC上无劣解，且两两无法比较，因此决策者只有根据某些别的考虑从BC上挑选出满意的方案来。这时称BC上的点为非劣解，或有效解。 多目标规划解的概念 对于一般的多目标规划问题： (VP) V-min F(X)=(f1(X), f2(X),…,fp(X))T s.t. gi(X)≤0, i=1,2,…,m 其中X=(x1,x2,…,xn)T, p≥2 设R={X| gi(X)≤0, i=1,2,…,m} 定义1 设X*∈R，若对任意j=1,2,…,p, 以及任意X∈R均有 fj(X)≥fj(X*), j=1,2,…,p 则称X*为问题(VP)的绝对最优解。最优解的全体记为Rab* 多目标规划解的概念 对于无绝对最优解的情况，引进下