《运筹学》实验教学指导书

实验三 灵敏度分析

一、实验目的

使学生了解lindo系统,熟练利用Lindo软件对价值系数的变化进行灵敏度分析,对资源拥有量的变化进行灵敏度分析,对增加一个变量进行灵敏度分析,对增加约束条件进行灵敏度分析利用单纯形法求解线性规划问题。 二、实验内容及要求

1. 安装Lindo6.1软件, 启动lindo6.1, 熟悉lindo6.1求解线性规划的过程和步骤,灵敏度分析的过程。

2. 对教材《运筹学基础及应用》上第二章线性规划对价值系数的变化进行灵敏度分析,对资源拥有量的变化进行灵敏度分析,对增加一个变量进行灵敏度分析,对增加约束条件进行灵敏度分析,编写简单的LINDO程序,利用lindo软件求解。

3.根据实际问题建立线性规划数学模型,利用lindo软件求解。 三、实验的重点和难点

1.实验的重点:灵敏度分析

2.实验的难点:线性规划模型的正确建立 四、实验准备

实验室电脑需要安装lindo软件。lindo软件在线性规划中灵敏度分析中的使用说明:(通过例子说明):

例如某家具公司制造书桌、餐桌和椅子,所用的资源有三种:木料、木工和漆工。生产数据如下表所示。

木料 漆工 木工 成品单价 每个书桌 8单位 4单位 2单位 60单位 每个餐桌 6单位 2单位 1.5单位 30单位 每个椅子 1单位 1.5单位 0.5单位 20单位 现有资源总数 48单位 20单位 8单位 若要求餐桌的生产量不超过5件,如何安排三种产品的生产可使利润最大? 用DESKS、TABLES和CHAIRS分别表示三种产品的生产量(决策变量),容易建立LP模型。 在LINDO模型窗口中输入模型:

MAX 60 DESKS + 30 TABLES + 20 CHAIRS SUBJECT TO

2) 8 DESKS + 6 TABLES + CHAIRS <= 48 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 20

- 13 -

4) DESKS + 15 TABLES + 0.5 CHAIRS <= 8 5) TABLES <= 5 END

解这个模型,并对弹出的对话框

“ DO RANGE (SENSITIVITY) ANALYSIS? ”

选择“是(Y)”按钮,这表示你需要做灵敏性分析。然后,查看输出结果。

1.输出结果的前半部分:

LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 280.0000

VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 24.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 10.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1

“LP OPTIMUM FOUND AT STEP1”表示一次迭代(旋转变换)后得到最优解。 “OBJECTIVE FUNCTION VALUE 1)280.0000”表示最优目标值为280。

给出最优解中各变量的值:造2个书桌(desks), 0个餐桌(tables), 8个椅子(chairs)。所以desks、chairs是基变量(取值非0),tables是非基变量(取值为0)。

“SLACK OR SURPLUS”给出松驰变量的值:

第2行松驰变量 =24 (第1行表示目标函数,第2行对应第1个约束) 第3行松驰变量 =0 第4行松驰变量 =0 第5行松驰变量 =5

“REDUCED COST”列出最优单纯形表中判别数所在行的变量的系数,表示当变量有微小变动时, 目标函数的变化率. 其中基变量的reduced cost值应为0, 对于非基变量 Xj(请注意,非基变量的取值一定是0), 相应的 reduced cost值表示当某个变量Xj 增加一个单位时目标函数减少的量( max型问题)。 本例中:变量TABLES对应的reduced cost值为5,表示当非基变量TABLES 的值从0变为 1时(此时假定其他非基变量保持不变,但为了满足约束条件,基变量显然会发生变化),最优的目标函数值 = 280 - 5 = 275。

- 14 -

“DUAL PRICE” (对偶价格)表示当对应约束有微小变动时, 目标函数的变化率. 输出结果中对应于每一个约束有一个对偶价格. 若其数值为p, 表示对应约束中不等式右端项若增加1 个单位, 目标函数将增加p个单位(max型问题)。 显然,如果在最优解处约束正好取等号(也就是“紧约束”,即起作用约束),对偶价格值才可能不是0。本例中:第3、4行是紧约束,对应的对偶价格值为10,表示当紧约束

3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 20 变为 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS <= 21

时,目标函数值 = 280 +10 = 290。对第4行也可类似解释。对于非紧约束(如本例中第2、5行是非紧约束),DUAL PRICE 的值为0, 表示对应约束中不等式右端项的微小扰动不影响目标函数。有时, 通过分析DUAL PRICE, 也可对产生不可行问题的原因有所了解。

2.输出结果的后半部分:

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE DESKS 60.000000 20.000000 4.000000 TABLES 30.000000 5.000000 INFINITY CHAIRS 20.000000 2.500000 5.000000 RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000 (报告中INFINITY表示正无穷 )

敏感性分析的作用是给出“RANGES IN WHICH THE BASIS IS UNCHANGED”,即研究当目标函数的系数和约束右端项在什么范围变化(此时假定其他系数保持不变)时,最优基(矩阵)保持不变。

这个部分包括两方面的敏感性分析内容: 1)目标函数中系数变化的范围

(OBJ COEFFICIENT RANGES)

如本例中:目标函数中DESKS变量当前的系数(CURRENT COEF) = 60,允许增加(Allowable Increase)=20、允许减少(Allowable Decrease)=4,说明当这个系数在[60-4,60+20] = [56,80]范围变化时,最优基保持不变。对TABLES、CHAIRS变量,可以类似解释。由于此时约束没有变化(只是目标函数中某个系数发生变化),所以最优基保持不变的意思也就是最优解不变(当然,由于目标函数中系数发生了变化,所以最优值会变化)。

2)约束右端项变化的范围(Right Hand Side RANGES)

- 15 -

如本例中:第2行约束中当前右端项(CURRENT RHS)=48,允许增加(Allowable Increase)=INFINITY(无穷)、允许减少(Allowable Decrease)=24,说明当它在 [48-24,48+ ) = [24, )

范围变化时,最优基保持不变。第3、4、5行可以类似解释。不过由于此时约束发生变化,最优基即使不变,最优解、最优值也会发生变化。如何变化呢?我们将在本节后面结合第1章1.2.1节例1.1给出的实际问题来进行说明。

最后,如果你对单纯形法比较熟悉,你可以直接查看最优解时的单纯形表,这只要选择菜单命令Reports | Tableau (Alt+7)执行即可,输出结果如下:

ROW (BASIS) DESKS TABLES CHAIRS

1 ART 0.000 5.000 0.000 2 SLK 2 0.000 -2.000 0.000 3 DESKS 1.000 1.250 0.000 4 CHAIRS 0.000 -2.000 1.000 5 SLK 5 0.000 1.000 0.000 ROW SLK 2 SLK 3 SLK 4 SLK 5

1 0.000 10.000 10.000 0.000 280.000 2 1.000 2.000 -8.000 0.000 24.000 3 0.000 1.500 -0.500 0.000 2.000 4 0.000 -4.000 2.000 0.000 8.000 5 0.000 0.000 0.000 1.000 5.000

在输出结果中, 基变量为BV={SLK2, Chairs, DESKS, SLK5},ART是人工变量(artificial variable),即相应的目标值z; 这样,你就可以知道

z = 5 TABLES + 10 SLK3 + 10 SLK4 = 280。

敏感性分析结果表示的是最优基保持不变的系数范围。由此,也可以进一步确定当目标函数的系数和约束右端项发生小的变化时,最优解、最优值如何变化。下面我们通过求解某个线性规划问题来进行说明。

3. 问题的数学模型:

Maxz?72x1?64x2x1?x2?5012x1?8x2?4803x1?100x1,x2?0在LINDO模型窗口中输入模型

MAX 72 x1 + 64 x2 SUBJECT TO

2) x1 + x2 <= 50 3) 12 x1 + 8 x2 <= 480

4) 3 x1 <= 100

- 16 -

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4