运筹学灵敏度分析题

第2章 线性规划 灵敏度分析

实用运筹学 -运用Excel建模和求解第2章 线性规划灵敏度分析 Sensitivity Analysis for Linear ProgrammingRUC, Information School, Ye Xiang

第2章 线性规划 灵敏度分析

本章内容要点线性规划灵敏度分析的概念和内容使用Excel进行灵敏度分析 影子价格的经济意义和应用

RUC, Information School, Ye Xiang

本章节内容2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 线性规划灵敏度分析 单个目标函数系数变动 多个目标函数系数同时变动 单个约束右端值变动 多个约束右端值同时变动 约束条件系数变化 增加一个新变量 增加一个约束条件 影子价格 (Shadow Price)RUC, Information School, Ye Xiang

第2章 线性规划 灵敏度分析

本章主要内容框架图

第2章 线性规划 灵敏度分析

单个 目标函数系数变动 多个 单个 约束右端值变动 多个 影子价格 内容 约束条件系数变化 灵敏度分析

实验报告

课程名称： 运 筹 学 实验项目名称： 应用Excel对线性规划进行灵敏度分析 班级与班级代码： 实验室名称（或课室）： 专 业： 任课教师： 学 号： 姓 名： 实验日期： 2010 年 10 月 18 日

广东商学院教务处 制

姓名 实验报告成绩

评语：

指导教师（签名）

《运筹学》 期末考试 试卷 习题库 答案

第三章线性规划对偶理论与灵敏度分析习题 一、思考题

1．对偶问题和对偶变量的经济意义是什么？

2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？

3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？

4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？

5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？

6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）xn k 0，其经济意 义是什么？

7．在线性规划的最优单纯形表中，松弛变量xn k的检验数 求最小值），其经济意义是什么？

n k

0（标准形为

ji的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 8．将ij

将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确

1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。

3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。

4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。

5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无

案例四 监理公司人员配置问题

某监理公司侧重于国家大中型项目的监理。每项工程安排多少监理工程师进驻工地，一般是根据工程的投资、建筑规模、使用功能、施工的形象进度、施工阶段来决定，监理工程师的配置数量随着变化。由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的。有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地。因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建（结构）专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理专业等，这就需要我们合理配置这些人力资源。为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度按标准施工期和高峰施工期来划分。通常标准施工期需求的人数教容易确定。但高峰施工期就比较难确定了，原因有两点：

（1）高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题。

（2）各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费。

因此，为了达到高峰施工期监理工程师配置

案例二 北方化工厂月生产计划安排

北方化工厂现有职工120人，期中生产工人105人，该厂主要设备是2套提取生产线，每套生产线容量为800kg，至少需要10人看管。该厂每天24小时连续生产，节假日不停机，从原料投入到成品出线平均需要10小时，成品率约为60％，该厂只有4t卡车1辆，可供原材料运输。

该厂目前的产品可分为5类，所用原料15种，根据厂方提供的资料，经整理得表1.

根据现有运输条件，原料3从外地购入，每月只能购入1车。根据前几个月的购销情况，产品1和产品3应占总产量的70％，产品2的产量最好不要超过总产量的5％，产品1的产量不要低于产品3与产品4产量之和。

问题：

（1） 请制定该厂的月生产计划，使得该厂的总利润最高； （2） 找出阻碍该厂提高生产能力的瓶颈问题，提出解决办法。

解：设X1为产品1的计划产量，X2为产品2的计划产量，X3为产品3的计划产量，X4为产品4的计划产量，X5为产品5的计划产量。

目标函数：maxZ 4.44x1 6.09x2 5.30x3 26.95x4 9.95x5

x1 x2 x3 x4 x5 800 2 (24 10) 60%

9.4%x1 5.40%x2 4.50%x3 1.70%x4 8.60%x5 4000x1 x

线性规划与灵敏度分析

1. 已知线性规划问题

maxs.t.z?c1x1?c2x2?c3x3??a11??a13??a12??b1??1??0?x?x?x?x?x????1??2??3??4??5??

?0??1???a21??a22??b2??a23??x?0,j?1,2,3,4,5?j用单纯形法求解，得到最终单纯性表如下。

XB x3 x2 σj b 3/2 2 x1 1 1/2 -3 x2 0 1 0 x3 1 0 0 x4 1/2 -1 0 x5 -1/2 2 -4 (1).求a11、a12、a13、a21、a22、a23、b1、b2的值； (2).求c1、c2、c3的值.

解：（1）由题意可设初始单纯形表的增广矩阵为

?a11a12AB?????a21a22最终单纯形表的增广矩阵为

a1310b1? ?a2301b2??101?A1B1???110??22?11?1223?2?， 2??对矩阵?A1B1?作初等行变换，使其第4,5列组成单位矩阵，

3?222??122???9??2021?13?141082? ?????5?512015?12015???2??2???A2B2??101?110??21?1由单纯形法的算法法则可知，?

第二章 线性规划的对偶理论与灵敏度分析

例一美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设 备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少 件.使获取的利润为最大。

设：

x1—— A产品的生产量 max z= 2 x1 + x2 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1,x2 ≥ 0

x2—— B产品的生产量

利润 约束 条件 st .

一、标准化 利润 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 5x2 + x3 = 15 约束 6x1 + 2x2 + x4 = 24 st . 条件 x1 + x 2 + x5 = 5 x1,x2 ,x3 ,x4 ,x5 ≥ 0 二、写出初始单纯形表(必定存在有单位矩阵)C CCB 0 0 0 2 0 1 XB b b

22

11

00xx4 3 11 00 00 00

00xx5 4 0 5/4 1 1/4 0 -1/4

00x5 0 -15/2 0-1/2 1 3/2 θ

xx1 x2x2 x3 1 00 61 10 20 50 20 11 10

15

线性规划与灵敏度分析

1. 已知线性规划问题

maxs.t.z?c1x1?c2x2?c3x3??a11??a13??a12??b1??1??0?x?x?x?x?x????1??2??3??4??5??

?0??1???a21??a22??b2??a23??x?0,j?1,2,3,4,5?j用单纯形法求解，得到最终单纯性表如下。

XB x3 x2 σj b 3/2 2 x1 1 1/2 -3 x2 0 1 0 x3 1 0 0 x4 1/2 -1 0 x5 -1/2 2 -4 (1).求a11、a12、a13、a21、a22、a23、b1、b2的值； (2).求c1、c2、c3的值.

解：（1）由题意可设初始单纯形表的增广矩阵为

?a11a12AB?????a21a22最终单纯形表的增广矩阵为

a1310b1? ?a2301b2??101?A1B1???110??22?11?1223?2?， 2??对矩阵?A1B1?作初等行变换，使其第4,5列组成单位矩阵，

3?222??122???9??2021?13?141082? ?????5?512015?12015???2??2???A2B2??101?110??21?1由单纯形法的算法法则可知，?

运筹学

第四章 灵敏度分析运筹学

运筹学

灵敏度分析

现在睡觉的话会做梦,而现在学习的话会让梦实现 哈佛图书馆的训言1

使用LP求解管理问题时，管理者需要

了解当环境和数据发生变化时，线性规划得出的结论还是否有效；

资源供应发生变化会有什么影响?成本变化后利润会发生什么变化? 如果模型使用的数据不精确会有什么影 响，数据允许在什么范围内变化? 如果结论无效如何快速求解？

运筹学

灵敏度分析主要内容1. 目标函数系数变化的灵敏度分析

2. 右边项变化的灵敏度分析3.约束条件中的系数变化的灵敏度分析 4.求解新的最优解 5.增加新变量的灵敏度分析 6.增加约束条件的灵敏度分析 7.灵敏度分析的几何意义

运筹学

1. 目标函数系数变化的灵敏度分析(1) 分析什么？

假定只有一个 cj 变化，假定 cj 从 cj 变到cj’=cj+Δ cj,当Δ cj在什么范围内变化时，不会

影响最优解。(2) 怎么分析？ 最优解不变的充要条件是：

C B A C 0* B 1 *

运筹学

假定只有一个cj变化，分两种情况讨论：1)cj 是非基变量的系数

设cj 变化量为 cj ,若希望cj 变化后最优基不变，检验数应满足以下条件：

j’= cBB-1pj -(cj + cj )=

习 题 6

6.1 试建立下述LP问题的对偶关系表，并写出其对偶问题： （1）max z=4x1+3x2+6x3

?3x1?x2?x3?60??2x1?2x2?3x3?40s.t. ?

2x?2x?x?623?1?x?0,x?0,x?023?1（2）min w=60x1+10x2+20x3

?3x1?x2?x3?2??x1?x2?x3??1s.t. ?

x?2x?x?123?1?x?0,x?0,x?023?1（3）min w=5x1-3x2

?2x1?x2?4x3?2??x1?x2?2x3?1s.t. ?

3x?x?x?323?1?x?0,x?0,x?023?1（4）max z=4x1+3x2+6x3

?x1?2x2?4x3?10?s.t. ?2x1?5x2?3x3?15

?x?0,x?0,x?023?1（5）min w=2x1+2x2+4x3

?2x1?3x2?5x3?2??3x1?x2?7x3?3s.t. ?

x?4x?6x?523?1?x?0,x?03?2(6) min w=2x1+3x2+6x3+x4

?3x1?4x2?4x3?7x4?21??2x1?7x2?3x3?8x4?18s.t. ?

x?2x?5x?3x?4234?1?x