运筹学教案.doc

目标规划
线性目标规划的基本概念与数学模型
线性目标规划的图解法
线性目标规划的单纯形算法
线性目标规划的基本概念
与数学模型
一、问题的提出
应用线性规划可以处理许多线性系统的最优化问题,但线性规划,整数规划和非线性规划都只有一个目标函数,而在实际问题中,常常需要考虑多个目标:如设计一个新产品的工艺过程,不仅希望获利大,而且希望产量高,消耗低,质量好,投入少等。而这些目标之间通常是矛盾的。所以这类问题多目标问题比单目标问题要复杂得多,我们把这一类问题称为目标规划问题。
二、目标规划的数学模型
例某工厂生产两种产品,受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下,要求制定一个获利最大的生产计划,具体数据见表:
产品
甲
乙
限量
原材料(Kg/件)
5
10
60
设备工时(h/件)
4
4
40
利润(元/件)
6
8
解:设该厂每周安排生产甲、乙两种产品的产量分别为x1,x2吨,则有
解得X*=(8,2)’ Z*=64
但现在要考虑如下问题:
(1)由于产品乙销售疲软,故希望乙的产量不超过甲的一半
(2)原材料短缺,生产中避免过量消耗
(3)最好能节约4小时设备工时
(4)计划利润不少于48元
一致意见:(1)原材料限额不得突破(2)产品乙产量必须优先考虑,设备工时问题其次考虑(3)最后考虑计划利润的问题
几个基本概念
1、理想值(期望值):目标规划是解决多目标规划问题的,而决策者事先对每个目标都有个期望值——理想值。
2、偏差变量:对每一个决策目标,引入正、负偏差变量d+和d-,分别表示决策值超过或不足目标值的部分。
d+≥0,d-≥0, d+d-=0
3、绝对约束和目标约束
绝对约束是指必须严格满足的等式或不等式约束,如线性规划问题中所有约束条件都是绝对约束。绝对约束是硬约束,对它的满足与否,决定了解的可行性。
目标约束是目标规划特有的概念,是一种软约束,目标约束中决策值和目标值之间的差异用偏差变量表示。
由各目标约束的偏差变量及相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值,
4、优先因子和权系数
目标规划中,多个目标之间往往有主次,缓急之分,把首先要达到的目标,赋予优先级P1,第二位达到的目标赋予优先级P2………
P1>>P2>>……>> Pk
权系数用来区别同一优先级中不同偏差变量的重要性。重要性大的在偏差变量前赋予大的系数。
如 P2(2d3-+d3+)
5、目标规划的目标函数(准则函数,达成函数)
由各目标约束的正、负偏差变量及其相应的优先级,权因子构成,且对此函数求极小值
对于 fi(x) +d- -d+=gi
(1)要求恰好达到目标值
即fi(x) =gi 取min{f(d++d-)}
(2)要求不超过目标值,但允许不足目标值

即 fi(x) ≤gi 取min{f(d+)}
(3)要求不低于目标值,但允许超过目标值

即fi(x) ≥gi 取 min{f(d-)}
上例的目标规划数学模型如下:
目标规划数学模型的一般形式
图解法
对于只有两个变量的目标规划问题,可用图解法求解
例1
满意解为 X=(,)
例2
图解法解线性目标规划问题,可能遇