胡运权第三版运筹学总复 习(2).ppt

2017/11/11
1
运筹学总复习
主讲:陆际恩
Tel:**********
Email:lujien@
运筹帷幄之中决胜千里之外
第四、五章
2017/11/11
2
第四章目标规划
[本章学习要求]
⒈掌握目标规划的图解法求解模型
⒉掌握目标规划的单纯形法的求解模型。
[主要概念及算法]
1、目标函数
⑴多目标的情况下,要用偏差变量限定成目标约束。
⑵多目标的重要程度不同,用优先因子Pi可以认为是一个大的常数,计算不同目标的优先顺序,确定P1》P2》P3…》Pn。
2017/11/11
3
⑶将所有的目标偏差总和在一起,组成一个新的目标函数,求极小。
难点:在进行目标约束的转换过程中,要有较好的应用题分析能力,或者说是语文逻辑分析能力。
即,当目标要求准确完成时,使
当目标允许超额完成(如利润、产值)时,使
2017/11/11
4
当目标允许不完成(如能源、原材料)时,使
2、约束条件
当把目标函数变成目标约束时,有
当把原问题中的资源约束标准化后,有
上述两式就是目标规划中的约束方程。
2017/11/11
5
3、模型
⑴列出全部约束条件。
4、建模步骤
⑵把要达到的约束不等式加上正、负偏差变量后,化为目标约束等式。
2017/11/11
6
⑶对目标赋予相应的优先因子。
⑷对同一级优先因子中的各偏差变量,若重要程度不同时,可赋予不同(根据题意)的加权系数。
⑸构造一个按优先因子及加权系数和对应的目标偏差量所要实现最小化的目标函数。
5、解目标规划的单纯形法
目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别,所以可用单纯形法求解。但要考虑目标规划的数学模型的一些特点,故有以下规定:
⑴因目标规划问题的目标函数都是求最小化,所以,以σj=cj-zj≥0(j=1,2,…,n)为最优准则。
2017/11/11
7
⑵因非基变量的检验数中含有不同等级的优先因子,即:cj-zj=∑akjPk,(j=1,2,…,n k=1,2,…,K)
因P1》P2》…》Pk;从每一个检验数的整体来看,检验数的正负首先决定于P1的系数a1j的正负;若a1j=0,这时此检验数的正负就决定于P2的系数a2j的正负,下面可依此类推。
解目标规划问题的单纯形法的计算步骤:
①建立初始单纯形表,在表中将检验数行按优先因子个数分别列成K行,置k=1;
②检验该行中是否存在负数,且对应的前k-1行的系数是零。若有负数,取其中最小者对应的变量为换入变量,转步骤③,若无负数,则转步骤⑤。
2017/11/11
8
③按最小比值规则确定换出变量,当存在两个或两个以上相同的最小比值时,选取具有较高级别的变量为换出变量。
④按单纯形法进行基变换运算,建立新的计算表,返回步骤②。
⑤当k=K时,计算结束。表中的解即为满意解。否则置k=k+1,返回步骤②。
2017/11/11
9
第四章复习思考题
1、试述目标规划的数学模型同一般线性规划数学模型异同。
⑴两种类型的数学模型都有目标函数;
目标规划与一般线性规划问题数学模型的共同点:
⑵两种类型的数学模型都有约束条件;
⑶两种类型的数学模型其决策变量都要求是连续的;
⑷两种类型的数学模型的右端常数项都要求非负;
2017/11/11
10
⑴LP问题的目标函数是求最大化,而目标规划的目标函数是求极小化;
目标规划与一般线性规划问题数学模型的不同点:
⑶LP问题的约束条件都是绝对约束,目标规划的约束条件既有目标约束,有时同时存在绝对约束。
⑵目标规划的目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子及系数而构造,而LP问题的目标函数是按一个单一目标(即利润最大)构造。
2、解释下列概念
⑴什么是正负偏差变量;⑵什么是绝对约束和目标约束;⑶什么是优先因子与权系数。
⑷LP问题没有优先因子和权系数,而IP中有这两个。