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

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

主要内容 讲授重点 讲授方式

对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划 对偶基本性质、对偶单纯形方法、灵敏度分析 讲授式、启发式

本章知识结构图

对偶问题灵敏度分析对偶单纯形法参数线性规划基本性质影子价格解的关系 第一节 线性规划的对偶问 题

一、对偶问题的提出

首先通过实际例子看对偶问题的经济意义。

例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为： (LP1) max z＝2xl+x2

现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利。设分别用y1、y2、和y3代表单位时间(h)设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和1小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电Ⅱ，盈利1元。由此y1，y2，y3的取值应满足

摘 要

线性规划是解决稀缺资源最优分配的有效方法，使付出的费用最少或获得的利益最大。它的研究对象是有一定的人力、财力、资源条件下，如何合理安排使用，效益最高；某项任务确定后，如何安排人、财、物，使之最省。它要解决的问题的目标可以用数值指标反映，对于要实现的目标有多种方案可以选择，有影响决策的若干约束条件。本文主要介绍了线性规划模型在实际生活中的应用，其中包括解线性方程组的各种方法，如图解法、单纯形法、以及对偶单纯形法等等，以及简单介绍了有关灵敏度分析的方法。由于许多问题仅仅利用线性规划的方法还不足以解决，因此用到了对偶理论，也因此引出了对偶单纯形法。对偶规划是线性规划问题从另一个角度进行研究，是线性规划理论的进一步深化，也是线性规划理论整体的一个不可分割的组成部分。灵敏度分析是对线性规划结果的再发掘，是对线性规划理论的充要应用，本文以实例验证灵敏度分析的实际应用。

关键词：线性规划；单纯形法；对偶单纯形法

ABSTRCT

Linear programming is an effective method to solve the optimal allocation of scarce resources, make the cost of p

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

例一美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设 备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．对偶问题和对偶变量的经济意义是什么？

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

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

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

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

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

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

n k

0（标准形为

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

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

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

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

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

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

对偶理论与灵敏度分析

第二章 对偶理论与灵敏度分析对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶问题的经济解释---影子价格 对偶单纯形法 灵敏度分析 参数线性规划

对偶理论与灵敏度分析

§2.1 对偶问题的提出 一、对偶线性规划问题【例1】 某工厂计划安排生产Ⅰ、Ⅱ两种产品，已知每种单位产品的 利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、 现有原材料和设备台时的定额如下表所示：Ⅰ 设 备 1 4 0 2 原 材 料 A 原 材 料 B 每单位产品利润(万元) 每单位产品利润(万元) Ⅱ 2 0 4 3 8台时 台时 16Kg 12Kg

原问题的策略: 原问题的策略: 问应如何安排生产才能使工 厂获利最大？ 厂获利最大？

现在的策略: 现在的策略: 假设不生产Ⅰ 假设不生产Ⅰ、Ⅱ产品 ,而是计划将 现有资源出租或出售,从而获得利润, 现有资源出租或出售,从而获得利润,这 时需要考虑如何定价才合理? 时需要考虑如何定价才合理?

对偶理论与灵敏度分析

Ⅰ 设 备 1 4 0 2

Ⅱ 2 0 4 3 8台时 台时 16Kg 12Kg

原问题的模型

原 材 料 A 原 材 料 B 每单位产品利润(万元) 每单位产品利润(万元)

第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章 线性规划 灵敏度分析

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

第四章 线性规划的对偶理论

一、填空题

1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的

线性规划问题与之对应，反之亦然。

2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。

5．若原问题可行，但目标函数无界，则对偶问题不可行。

6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。

﹡－

7．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。

﹡﹡﹡﹡

8．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX= Yb。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。

﹡﹡﹡

10．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*b。

11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条

第四章 线性规划的对偶理论

一、填空题

1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的

线性规划问题与之对应，反之亦然。

2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。

5．若原问题可行，但目标函数无界，则对偶问题不可行。

6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。

﹡－

7．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。

﹡﹡﹡﹡

8．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX= Yb。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。

﹡﹡﹡

10．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*b。

11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条

习 题 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

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

1、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 （ ） A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零

2、关于线性规划的原问题和对偶问题，下列说法正确的是 （ ） A．若原问题为元界解，则对偶问题也为无界解

B．若原问题无可行解，其对偶问题具有无界解或无可行解 c．若原问题存在可行解，其对偶问题必存在可行解 D．若原问题存在可行解，其对偶问题无可行解

3、下面哪些不是线性规划问题的标准形式所具备的（ ） A 所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式 C 添加新变量时，可以不考虑变量的正负性 D 求目标函数的最小值

4、已知线性规划问题 Max Z=4X1+7X2+2X3 X1+2X2+X3 ≤10 S.t 2X1+3X2+3X3≤10 X1，X2，X3 ≥0

应用对偶理论证明该问题最优解的目标函数值不大于25

5、已知线性规划问题max Z=3x1+4x2+x3