6第六章 单纯形法的灵敏度分析与对偶

第一章

思考题、主要概念及内容

1、了解运筹学的分支，运筹学产生的背景、研究的内容和意义。

2、了解运筹学在工商管理中的应用。

3、体会管理运筹学使用相应的计算机软件，注重学以致用的原则。

第二章

思考题、主要概念及内容

图解法、图解法的灵敏度分析

复习题

1. 考虑下面的线性规划问题：

max z=2x1+3x2 ； 约束条件：

x1+2x2 <6

5x1+3x2 < 15

x1, x2 >0

(1) 画出其可行域．

(2) 当 z=6 时，画出等值线 2x1+3x2=6 ．

(3) 用图解法求出其最优解以及最优目标函数值．

2. 用图解法求解下列线性规划问题，并指出哪个问题具有惟一最优解、无穷多最优解、无 界解或无可行解．

(1) min f=6x1+4x2 ； 约束条件：

2x1+x2 >1，

3x1+4x2 >3，

x1 ， x2 >0

(2) max z=4x1+8x2 ； 约束条件：

2x1+2x2 < 1，0

-x1+x2 >8，

x1,x2 >0

(3) max z=3x1-2x2 ；

约束条件：

x1+x2 <1，

2x1+2x2 >4，

x1 ， x2 >0

(4) max z=3x1+9x2 ； 约束条件：

x1+3x2 w 22

-x1+x2 <4 x2w6，

2x1-5x2 <0

x1, x2 >0

3. 将下述线性规划问题化成标准形式：

(1) max f=3x1+2x2 ；

约束条件：

9x1+2x2 < 30

3x1+2x2 < 13

2x1+2x2 <9

x1 ， x2 >0．

(2) min f=4x1+6x2 ；

约束条件：

3x1-x2>6

x1+2x2 < 10

7x1-6x2=4 ，

x1 ， x2 >0．

(3) min f=-x1-2x2 ；

约束条件：

3x1+5x2 < 70,

-2x1-5x2=50 ，

-3x1+2x2 > 30

x1 O, x2

运筹学课程

运筹学对偶单纯形法与单纯形法

对比分析大作业

哈尔滨工业大学工业工程系

学 生 姓 名:

学 号：

指 导 教 师：

成 绩：

评 语：

运筹学对偶单纯形法与单纯形法对比分析

摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。

关键词：对偶单纯形法；对偶理论；单纯形法；基本思想

在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。这个发现指出，对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系在众多领域都非常有用。 （一）教学目标：

通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围

（二）教学内容：

1）对偶单纯形法的思想来源

2）对偶单纯形法原理

3）对偶理论的实质

4）单纯形法和对偶单纯形法的比较

（三）教学进程：

一、对偶单纯形法的思想来源

所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。

二、对偶问题的实质

下面是原问题的标准形式以及其对应的对偶问题：

原问题 对偶问题

Max Z=∑cjxjnj=1

s.t. ∑aijxj≤bi i=1,2,?,mnj=1

xj≥0 j=1,2,?,n Min W=∑biyimj=1

s.t. ∑aijyi≥cj j=1,2,?,nnj=1

yi≥0 i=1,2,?,m 从而可以发现如下规律：

1.原问题目标函数系数是对偶问题约束方程的右端项。

管理运筹学教学大纲

讲 节 知识点

第1讲

绪论 1.1管理运筹学是什么 运筹学定义，历史

1.2运筹学的决策过程 决策7个步骤，弗兰茨.厄德曼奖，优选法，统筹法

1.3运筹学在日常管理中解决哪些问题及软件应用 学以致用，应用计算机软件

第2讲

线性规划的图解法 2.1问题的提出 决策变量，目标函数，约束条件，线性规划问题的建模过程

2.2线性规划的图解法 可行域、等值线，最优解，线性规划的标准形式

2.3图解法灵敏度分析 目标函数中系数的灵敏度分析、

约束条件中常数项的灵敏度分析

第3讲

线性规划问题的计算机求解 3.1“管理运筹学”软件介绍 输出结果解读，对偶价格，松弛/剩余变量，灵敏度分析

3.2手把手教你用软件 软件安装，操作

第4讲

线性规划在工商管理中的应用 4.1人力资源如何合理分配，既能满足工作需要又使安排人力最少 建模、运筹学软件的应用

4.2如何制定生产计划，以获得最大利润 建模、运筹学软件的应用

4.3如何合理套裁下料，使原料最省 建模、运筹学软件的应用

4.4如何配置产品原料，才能获得最大利润 建模、运筹学软件的应用

4.5如何投资，以获取最大收益 建模、运筹学软件的应用

第5讲

单纯形法 5.1单纯形法---知其然，知其所以然 单纯形法的思路、原理、求解过程和基本步骤

5.2线性规划单纯性表格求解法 迭代，入基变量，出基变量，主元，检验数

5.3如何求解成本最小的方案？ 人工变量，大M法，两阶段法

5.4不是所有的线性规划都有唯一最优解 无可行解，无界解，无穷多最优解，退化

第6讲

单纯形法的灵敏度分析与对偶问题 6.1利润、成本及资源变化了怎么办？ 单纯形表灵敏度分析

6.2怎么定租金？ 构造线性规划的对偶问题

6.3原问题与对偶问题的关系 对称性，弱对偶性，强对偶性，互补松弛性 6.4对偶单纯形法 对偶单纯形使用范围，计算的方法

第7讲

运输问题 7.1如何运输成本最小 产销平衡，假想产地、销地

1

1.对偶问题模型

2.对偶例子，总结特点

3.对偶的相关性质定理

4.对偶单纯形法

1. 对偶问题模型

例：某化工厂利用R1、R2、R3 三种原料，生产Q1、Q2两种产品，生产每公斤产品所需的各单位原料、工厂所拥有的个资源最大量及每公斤产品销售利润如下表所示，问每天应生产多少公斤Q1、Q2才能使利润最大。

原料-产品-利润表

产品

资源 生产每公斤产品Q1 生产每公斤产品Q2 每天原料的最大

用量（公斤）

R1原料（公斤） 3.0 10.0 300

R2原料（公斤） 4.0 5.0 200

R3原料（公斤） 9.0 4.0 360

利润（万元/公斤） 0.7 1.2

设每天生产Q1、Q2的产品量为x1，x2，可得到约束方程

Max s=0.7 x1 +1.2 x2

3x1 + 10x2300

4x1 + 5x2200

9x1 + 4x2360

x10, x20

现在的问题是，如果另一个化工厂想全部购买该厂R1、R2、R3 三种原料，那么该厂在什么条件下出售这三种原料，才能使该厂在经济收入上不低于用等量的三种原料生产Q1、Q2产品获得的最大利润。

设三种原料出售单价分别为u1, u2, u3, 可得到约束方程

Min W= 300 u1 +200 u2 +360 u3

3 u1 +4 u2 +9 u3  0.7

10 u1 +5 u2 +9u3  1.2

u10, u20, u30

一半钱这问题成为L，后者为其对偶问题成为D

比较两个线性规划模型，其特征有

 目标函数的要求上两者相反，s求max，w求min

 右端向量和目标函数的价值系数两者对调

 约束方程两者符号相反，s是“”，w是“”

 由s的约束方程书引入了同等数量的另一组非负变量u=( u1, u2, u3)T,且作为w的决策变量，约束方程数由m个变为n个

2. 对偶问题及其转化方

对偶问题在理论和实践方面有着广泛的应用