运筹学10-目标规划-112.pptVIP

第10讲 目标规划 10.1 多目标决策问题 10.2 多目标规划问题解的概念 10.3 目标规划方法 一、目标规划的建模 二、目标规划的图解法 三、目标规划的单纯形法 10.1 多目标决策问题 现实中面临的很多决策问题通常是多目标的(Multi-Objective) 的。 例如你要购买一辆汽车，你的决策目标可能会有多个：价格、外观、品牌、油耗、安全性、舒适性等等。 大学毕业生在选择职业的时候，其决策目标通常有：薪资水平、公司的名气、发展机会、工作环境等。 多目标规划模型 多目标规划模型： 10.2 多目标规划问题解的概念 绝对最优解 定义1 设X*∈R，若对任意i =1, ..., m以及任意X ∈R，均有 则称X*为该多目标规划问题的绝对最优解。根据定义，绝对最优解在所有目标上均优于其他可行解。 有效解(非劣解) 定义2 设X*∈R，若不存在X ∈R，对于任意 i =1, ..., m, 有 并且至少存在一个X ∈R，满足 则称X*为该多目标规划问题的有效解(非劣解)。 10.3 目标规划方法 目标规划是处理多目标决策问题的一种方法，这一方法是美国学者查恩斯（A. Charnes）和库伯(W.W. Cooper)于1961年在线性规划的基础上提出来的. 目标规划方法的思想： 指定各目标的目标值或理想值，决策者希望决策点的各目标实现值与各目标的理想值偏差尽可能小; 指定各目标的优先级，决策者按照优先级别的高低依次处理各目标，在满足优先级高的目标的基础上，再依次满足优先级低的目标. 目标规划方法 一、目标规划建模 fi(x) —— 目标 i 的目标函数 bi —— 目标 i 的理想值 相关概念： (1) 偏差变量： —— 决策点的目标i的实现值与目标i的理想值之间的偏差。正偏差变量表示实现值超过理想值的部分，负偏差变量表示实现值未达到理想值的部分。且有： (2) 绝对约束与目标约束： 绝对约束，必须严格满足的等式约束和不等式约束，譬如，线性规划问题的所有约束条件都是绝对约束，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。 目标约束，目标规划所特有的，由目标函数引入正、负偏差变量转化而来，目标约束方程的右端项是该目标的理想值，加入正、负偏差变量表示在达到此目标值时可能发生的正的或负的偏差，因此目标约束是软约束。 目标规划的建模思路 (1). 通过引入正、负偏差变量，把原问题中的各个目标函数转化为目标约束; (2). 按照优先级高低依次控制(最小化)不同目标的偏差变量, 以此作为目标规划模型的目标函数. 例1：一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1： 设x1、x2分别表示投资商所购买的A股票和B股票的数量。 新的目标函数： 资金约束(硬约束)： 目标规划模型： 例2：某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时，预计市场每周彩色电视机的销量是24台，每台可获利80元，黑白电视机的销量是30台，每台可获利40元，该厂确定的目标为：P1：充分利用装配线每周计划开动40小时；P2：允许装配线加班，但加班时间每周昼不超过10小时；P3：装配电视机的数量尽量满足市场需要. 试建立该问题的目标规划模型。 解：设 分别表示黑白和彩色电视机的产量，问题的目标规划模型为 目标规划建模小结 二、目标规划的图解法 对于只有两个决策变量的目标规划问题，可以考虑用图解法来求解。在用图解法求解时，首先必须满足所有的绝对约束(硬约束)，然后，在此基础上按照优先级的次序逐个考虑各个目标约束，以缩小解的范围。 图解法的求解步骤 例3：用图解法求解下列线性规划问题： 例5：用图解法求解例2，取W33=2,W34=1 (三)目标规划的单纯形法 ③ 按? 规则计算： ，所以 d2- 为换出变量，转入④。 ④ 进行换基运算，得表3。以此类推，直至得到最终单纯形表4为止。 表2 表3 由表3可知，x1* =2，x2* =4，为最优解。检查检验数行，发现非基变量d3+的检验数为0，这表明该问题存在多重解。 表4 在表3中，以非基变量d3+为换入变量，d1-为换出变量，经迭代得到表4。 从表4可以看出，x1*=10/3，x2*=10/3也是该问题的最优解。 例7： 用目标规划的单纯形法求解如下目标规划