第二章对偶理论与灵敏度分析练习题答案

第二章 对偶理论与灵敏度分析练习题答案

1．判断下列说法是否正确：

(1) 任何线性规划问题存在并具有惟一的对偶问题；(?)

(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(?)

(3) 设j ?x ，i ?

y 分别为标准形式的原问题与对偶问题的可行解，*

j x ，*i y 分别为其最优解，则恒有n n m m

**j j j j i i i i j 1j 1i 1i 1??c x c x b y b y ====≤=≤∑∑∑∑；(?) (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(?)

(5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(?)

(6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(?)

(7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；(?)

(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；(?)

(9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(?)

(10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。(?)

2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。

要求：(1)

(3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价2.5购入第一种资源是否值得，为什么？若有人愿意购买第二种资源应要价多少，为什么？

答案：

(1)注：该问题得解法非唯一，以下解法只是其中一种（各解法原理相同）。

由题意已知原线性规划问题目标函数为Max （因σj ≤0为最优），且c 4、c 5为0（松弛变量目标函数系数为0）。

根据1j j B j c C B P σ-=-知：23131111c c c 422110c c 42610c 23???-?-?=- ????????-?-?=-? ???????-?=-? ????

，得：123c 6c 2c 10=??=-??=? 根据()511222

151112632010B A|b 10-??= ?--??，得：()012105A|b 3110110??= ?-?? 则原线性规划问题的数学模型为：

123

23123123MaxZ 6x 2x 10x x 2x 53x x x 10

s.t.x ,x ,x 0=-++≤??-+≤??≥? 其对偶问题的数学模型为： 122121212Min 5y 10y 3y 6y y 2s.t.2y y 10

y ,y 0

ω=+≥??-≥-??+≥??≥? (2)直接由表写出对偶问题得最优解为：()*Y 4,2=

(3)令原解()()-1i B i i i x X B b b ===，得?b r 的变化范围为：

{}{}i ir ir r i ir ir i i

Max b /a |a 0b Min b /a |a 0?->≤≤-<，其中：()1ir ir a B -=。则： {}{()}15151Max b Min 2226

?-÷≤≤-÷-，即15b 15?-≤≤，则10b 20≤≤ (4)以单价2.5购入第一种资源是值得的，因其小于该资源“影子价格”（即2.5<4），可盈利；第二种资源应要价至少为2（影子价格），否则不如自己组织生产。

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案.doc

第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量 0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量 0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0

数学建模 对偶问题和灵敏度分析

对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为 c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批 混合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 m i n n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1,,m i j i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i 饲料加工厂面临的问题是：应把这m 种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。为该问题建立数学模型，即得如下线性规划(1—2)：

第3章对偶理论

第3章 对偶理论 §3.1 线性规划的对偶理论 3.1.1 对偶问题的表述 对称形式的对偶： （L ） cx min (D) wb max s.t. b Ax ≥ s.t. c wA ≤ 0≥x 0≥w 其中c 为n 维行向量，A 为n m ?矩阵，b 为m 维列向量，x 表示n 维列向量，w 表示m 维行向量。 称(D)为线性规划(L)的对偶规划问题。 定理1 (L)与(D)互为对偶规划问题。――（对合性） 例 设原问题 对偶问题 , 12 5 s.t.min 21212121≥≥-≥+-x x x x x x x x 0 , 1 2 1 s.t.5 max 2121212 1≥-≤-≤++w w w w w w w w 非对称形式的对偶： （LP ） cx min (DP) wb max s.t. b Ax = s.t. c wA ≤ 0≥x 例 设原问题 对偶问题 ,, 523 4 s.t.345min 321321321321≥=++=++++x x x x x x x x x x x x 3 4 2 5 3 s.t.5 4 max 2121212 1≤+≤+≤++w w w w w w w w 一般线性规划问题： 可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。

直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。 3.1.2 对偶定理(强对偶定理和弱对偶定理) 定理2 (弱对偶定理)：设x 和w 分别是 （L ） cx min 和 (D) wb max s.t. b Ax ≥ s.t. c wA ≤ 0≥x 0≥w 的可行解，则有下列不等式成立： b w x c ≥ 证明：由于b x A ≥和0≥w ，则有b w x A w ≥。 由于A w c ≥和0≥x ，则有x A w x c ≥。 因此有b w x c ≥ 推论 1 设x 和w 分别是(L)和(D)的可行解，且有b w x c =，则x 和w 分别是(L)和(D)的最优解。 推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。 推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。 定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。 证明：设原问题（L ）存在最优解，引进松弛变量，写成等价形式： s.t. min ≥≥=-v x b v Ax cx （1） 由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是?? ????=v x y ，相应的最优基是B 。此时所有判别数均非正，即 j c p w j j ?≤- ,0 （2） 1-=B c w B 为单纯形乘子。

对偶与灵敏度分析

§2 对偶与灵敏度分析 §2.1 LP 的对偶问题 无论从理论和实践角度，对偶理论是LP 中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP 问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。 一、问题的提出 例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD 进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表： 1.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？ 2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？ 解：1.设甲乙产品各生产1x 2x 件

LP1：?????? ?≥≤≤+≤++=0 ,1648 212 2232211 21212 1x x x x x x x x x MaxZ 2.设每台设备的机时最低价分别为：1y ，2y ，3y ，4y LP2：??? ??=≥≥++≥+++++=4,3,2,1,03422242121681242 13 214 321i y y y y y y y y y y y MinZ i 二、原问题和对偶问题之间的关系： 1.对称形式下的原问题与对偶问题 对称形式下原问题的一般式： 矩阵形式： ????? ?? ??=≥≤+++≤+++≤++++++=n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c MaxZ j m n mn m m n n n n n n ....... 21,0 (221) 1222221211 12121112211 ???≥≤=0X b AX CX Max 若用i y 代表第i 种资源的估价，则其对偶问题的一般式为： ????? ?? ??=≥≥+++≥+++≥++++++=m j y c y a y a y a c y a y a y a c y a y a y a y b y b y b MinZ j n m mn n n m mn m m m m ....... 21,0 (221) 1222221121 12211112211 ???≥≥=0Y C Y A Yb Min T T ω 2.非对称形式下原问题与对偶问题： 方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。

数学建模 对偶问题和灵敏度分析资料讲解

数学建模对偶问题和灵敏度分析

对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批混 合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 min n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养 鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1, ,m ij i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i

对偶理论与灵敏度分析练习题答案

第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，* j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1j 1i 1i 1??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 要求：(1) (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入第一种资源是否值得，为什么若有人愿意购买第二种资源应要价多少，为什么

第二章对偶理论与灵敏度分析练习题答案

第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1 j 1 i 1 i 1 ??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() $ (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 X B ｂ x 1 x 2 x 3 x 4 x 5 — x 3 5/2 0 1/2 1 1/2 0 x 1 5/2 1 — -1/2 0 -1/6 1/3 σj 0 -4 0 -4 -2 ; 要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入

第二章对偶问题一般题答案

对偶问题一般习题答案 ● 一般题目 内容1：根据原规划，写出对偶规划 1.1 写出下面线性规划问题的对偶问题 (a.) 234 1234123412341 234m a x 2343567358 ..12999200,0,0,z x x x x x x x x x x x x s t x x x x x x x x =+++-+--=?? ++-≥?? --+≤? ?≥≥≤?无约束 (b.) 1 111 11111m a x (1,)(1) ..0(1,)1n j j j n ij j i j n ij j i j j j z c x a x b i m m m a x b m i m s t x j n n n x n j n === = ? ≤ ≤≤≤???? = +≤≤?? ?≥ ≤≤≤? +≤≤??∑ ∑∑无约束,当 内容2：根据对偶问题，判定原问题有最优解、无解、有无穷大解 2.1 应用对偶理论, 证明线性规划问题有最优解。 12 12121 2m a x 3224 3214 ..301,2j z x x x x x x s t x x x j =+-+≤?? +≤?? -≤??≥ =? 提示：找到原问题和对偶问题的一个可行解，那么就能说明原问题有最优解。 2.2 应用对偶理论, 证明线性规划问题是可行的，但无最优解。 123 13123m a x 4 ..14 01,2,3j z x x x x x s t x x x x j =-+?-≥? -+≥?? ≥ =?

提示：说明对偶问题无解，再根据原问题有可行解，就说明原问题为无穷解，所以没有最优解。 2.3 应用对偶理论, 证明线性规划问题无解。 12 12121 2m a x 5241 ..23101,2j z x x x x x x s t x x x j =+-≥?? +≤?? -≤??≥ =? 提示：说明对偶问题有无穷解，就说明原问题无解。 内容3：由原问题的最优解得到对偶问题的最优解 3.1 课本2.11题。 （a ）写出最优单纯形表 由最优单纯形表 对于2x 有 []2311/2*(1/2)*4c c c -+-=- 对于2x 有 []43141/2*(1/6)*4(0)c c c c -+-=-= 对于5x 有 []53150*(1/3)*2(0)c c c c -+=-= 可得1c 、2c 和3c 的值

运筹学对偶理论与灵敏度分析作业

作业： 问题1：书本P71第7题 1、设x1 、x2 、x3分别为A产量，B产量，C产量 目标函数：Z=4 x1 +x2 +5x3 约束条件： +3x2 + 5x3<=45 6x 3x1 +4x2 +5x3<=30 x1 、x2 、x3>0 2、A的利润在3~6之间，最优计划不变。 3、设x1 、x2 、x3、x4 分别为A产量，B产量，C产量，D产量 目标函数：Z=4 x1 +x2 +5x3+2.5x4 约束条件： +3x2 + 5x3+3x4<=45 6x 3x1 +4x2 +5x3+2x4<=30 x1 、x2 、x3、x4>0 利润从35增加到37.5，值得生产。 4、见Excel 问题2：某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示： （1）如何充分发挥设备能力，使产品总产值最大？ 设x1 、x2 、x3分别为甲产量，乙产量，丙产量 目标函数：Z=3 x1 +2x2 +x3 约束条件： +2x2 + 1x3<=400 x 2x1 +1x2 +2x3<=500 x1 、x2 、x3>0 最优解 甲产量乙产量丙产量 200 100 0 总产值最大800 （2） 200个甲产品在A设备上加工1小时，B设备上加工2小时。

100个乙产品在A设备上加工2小时，B设备上加工1小时。 丙产品不生产。 使得总产值最大为80万。 （3）试分别确定甲产品单位产值、B设备供量各自的影响范围。 甲产品的范围是198~201。 B设备供量的范围是200~800。 （4）若每月能以39万元租金租用外厂B设备300台时，则应否租用？为什么？ 原来的产值为80万，租用外厂之后的产值为120万，则产值增加了40万，而租金要39万，则增加的产值足够支付租金，最后剩余1万，说明能租用。 （5）若每月A设备提供量减少200台时，B设备供量增加100台时，试问最优解与影子价格有何变化？ 最优解是600 影子价格：A设备从0.333~3 ；B设备从1.333~0

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

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

1 第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1) ?????? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343322 43422min x x x x x x x x x x x x x x x z (2) ?????? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 321321321321321x x x x x x x x x x x x x x x z 无约束 (3) ????? ??????==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1 111 n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij

2 (4) ????? ??????=≥++==<=<=∑∑∑===) ,,,,1(0),,2,1(),,1(min 1 211 111 n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行 解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行 解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶 问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对 偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。 3 2 2 0 0 0

《运筹学》第3章习题

第三章线性规划对偶理论与灵敏度分析习题 一、 思考题 1． 对偶问题和对偶变量的经济意义是什么 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么 3．什么是资源的影子价格它和相应的市场价格之间有什么区别 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化有多少种不同情况如何去处理 二、 判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0

对偶理论

第二篇 对偶规划 §2.1 问题的提出： 1. 在单纯形法实施中，我们是针对最大化目标来进行的，那末目标是最小化时则如何求？ 方法有二： （1）在单纯形法中最优性原则下，调入变量是f 方程中具有最大正系数的一个，可行性原则不变。 （2）把最大化线性规划目标化成最小化线性规划目标来求，则可用通常的单纯形法，问题是如何“化”。 这个问题就是这一篇中要讲的对偶问题。 2. 在有限的材料中加工若干个产品，如何安排生产产品数，使获取利润（或产值）最大—这是线性规划原始问题之一，反过来要问，在产值（利润）固定情形之下，使单位材料的产值最大，即资源单位价格—影子价格最大，这是本篇研究的第二个问题。 3. 3.1 上面所讨论的线性规划问题中，假定各参数j i ij c b a ,,都是已知的常数。但是 （1）这些参数往往是一些估计和预测的数字 （2）市场条件一变，j c 值就会变化 （3）工艺条件一变，ij a 也会变化 （4）资源可供使用量变化，也会引起i b 的变化 自然而然有下述问题： 3.2 Problem one ：当系数中一个或多个变化时，最优解如何变？ Problem two ：系数在何范围内变化，最优基仍然不变？ Problem three ：若最优解已经变化，如何用最简便的方法找到现行的规划问题的最优解呢？ 3.2 这些都是决策者所关心的。为了建立一个总的策略方法，以应付各种偶然发生情况，必经研究和分析，由于系数改变而导致最优解的变化，这样分析，称为灵敏度分析。 §2.2 线性规划的对偶问题： 一、原始问题是规范形式时的对偶问题： 1.定义：设???? ? ??=mn m n a a a a A 1 111 ????? ??=n x x X 1 ????? ??=m b b b 1 ? ?? ?? ??=n c c c 1 则称 f max x c T = f m i n x c T = s.t. AX ≤b 和 s.t. AX ≥b x ≥0 x ≥0 为规范线性问题。 2.例1 f max =2132x x + 例2 f min =2122x x +

对偶理论与灵敏度分析

对偶理论与灵敏度分析 对偶问题的提出 对偶理论 影子价格 对偶单纯形法 灵敏度分析

对偶问题的提出 定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题。 应用: 1. 在某些情况下，解对偶问题比解原问题更加容易 2. 对偶变量有重要的经济解释(影子价格) 3. 作为灵敏度分析的工具 4. 对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解) 5. 避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量) 一、对偶问题的提出 例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。 问：(1)该车间应如何安排生产才能使每日收入最大？ (2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。 解(1)：设该车间每日安排生产木门x 1扇，木窗x 2扇，则数学模型为 X*=(15,20)’ Z*=1440元 ?? ? ??≥≤+≤++=-0502120343056max 21212121x x x x x x x z

解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格 Y*=(2,24)’ W*=1440元 将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的练习与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。 二、L P 和D P 的联系与区别 (1)一个极大化，一个极小化 (2)L P 的价值系数行向量＝(D P 右端项)’ (3)L P 的系数矩阵＝(D P 系数矩阵)’ (4)L P 的右端项＝(D P 的价值系数)’ (5)L P 的约束个数＝D P 的变量个数 (6)L P 的变量个数＝D P 的约束个数 三、原问题与对偶问题的关系 1．对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式：(1)其变量均为非负约束；(2)其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时取“≥”号；(3)右端项b 可取负值。 ?? ? ??≥≥+≥++=-0303562450120min 2121212 1y y y y y y y w ????? ???????=≥≤+???++???? ??≤+???++≤+???++ +???++=),,1(0max :221122222121112121112211n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c z LP j m n mn m m n n n n n n

运筹学_第2章_对偶理论习题

第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为

min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。

第三章线性规划的对偶理论及灵敏度分析1总结

第三章线性规划的对偶理论及灵敏度分析 主要内容：1、对偶问题及其性质； 2、 对偶单纯形法； 3、 灵敏度分析。 重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方 法。 要 求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够 用这些数学方法解决实际问题。 § 1对偶问题的对称形式 一、对偶问题 弓侧，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及 A 、B 两种原材料 的消耗，该工厂每生产一件产品甲可获利 2元，每生产一件产品乙可获利 3元，问应如何安排计划才能使该工厂获利 最多？ 解：设 X i 、 X 2 分别为甲、乙两种产品的产量 作一比较：若用一个单位台时和 4个单位原材料 A 生产一件产品甲，可获利 2元，那么生产每件产品甲的设备台 y^ 4y^ 2 同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。即: 2力 4y 3 3 将工厂所有设备台时和资源都出租和出让，其收入为 则目标函数 maxz 二 2x 「 3x 2 x 「 2x 2 岂 8 i 4x 1 - 16 i 4x 2 兰 12 约束条件 -x 1,x^ 0 (1) 不再生产甲、乙产品，而将其出租或出售 3分别为出租 单位设备台时的租金和出让单位原材料 这时要考虑每种资源的定价问题，设 A 、 B 的附加额。 时和原材料出租和出让的收入应不低于生产一件甲产品的利润。即:

。 =8y 〔 + 16y 2 + 12y 3 对工厂来说，??越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足》所有产品的利润前提下, 使其总收入尽可能小，才能实现其愿望。为此，得到如下模型： min =8y 1 16y 2 12y 3 "+4丫2 工 2 < 2y i +4y ^ 3 J j > 0 , j =1,2,3 我们就称（2）为模型（1）的对偶问题。 一般地，设原问题为 max z = c/ c 2 x 2 … …c x n 'a ii X i +a i2X 2 + … +amX n 兰 b a 2l X l +a 22X 2 +■八 +a 2n X n 兰 b 2 a a a a ■ ■ ■ ■ ■s ■ ■ ■ ■ a mi X i +a m2X 2 + *a mn X n 兰 * X j _0 , j =i,2, ,n 则其对偶问题为： min 二 by b ?y 2 ^^n Niy i +a 2〃2 + …+a mi y m A" a i2y i +a 22 y 2 * +a m2 y m ?C 2 m - a - < ■ ■ ■ ■ a in y i +a 2n y 2 + +a mn y m ?C n y i 一0 , i =i,2, ,m 矩阵形式： 原问题 对偶问题 max z = cX mi n = Yb 'AX E b , 、Y A 启C （实际为A T y T ^C T ） X >0 7 >0 、原问题与对偶问题的关系

第三章 线性规划的对偶理论(管理运筹学,李军)

3 线性规划的对偶问题 1． 试从经济角度解释对偶变量的含义。 答：假设有一企业欲将另一个企业拥有的资源收买过来，至少应付出多少代价，才能使此企业愿意放弃生产活动，出让资源。显然后者放弃自己组织生产活动的条件时，对同等数量资源出让的代价不低于该企业自己组织生产活动是的产值。 2． 判断下列说法是否正确 （1） 任何线性规划问题都存在其对偶问题 （正确） （2） 如果原问题存在可行解，则其对偶问题也一定存在可行解；（错） （3） 当原问题为无界解时，对偶问题也为无界解；（错） （4） 当对偶问题无可行解时，原问题一定具有无界解；（错） （5） 若原问题有无穷多最优解，则对偶问题也一定具有无穷多最优解 （错） 3写出下列线性规划问题的对偶问题： （1）321422min x x x w ++= 1x + 22x + 3x ≥ 2 21x + 2x +33x ≤ 6 1x +42x +63x ≤ 5 0,,321≥x x x 解： 123123123123123max 65222423640,0,0 w y y y y y y y y y y y y y y y =++++≤++≤++≤≥≥≥ （2）32132max x x x ++= 1x + 22x + 3x ≥10 31x +23x ≤15 1x +22x + 3x =12 321,0,0x x x ≤≥无约束

解： 12312313123123min 10151232 2 23210,0,w y y y y y y y y y y y y y y =++++≥+≤++=≤≥无约束 4. 用对偶单纯形法求解下述线性规划问题 （1）32118124min x x x w ++= （2）4321432min x x x x w +++= 1x +33x ≥ 3 1x +22x +23x +34x ≥30 22x +23x ≥ 5 21x +2x +33x +24x ≥20 0,,321≥x x x 0,,,4321≥x x x x （1） 转换化成标准形式： 1231342351~5min 41218332250 w x x x x x x x x x x =+++-=+-=≥ X=(0,2/3,1,0,0) (2)转化为标准形式 123412345123461~6min 2322330232200 w x x x x x x x x x x x x x x x =++++++-=+++-=≥

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

2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题 (a) min z=2x1+2x2+4x3(b) max z=5x1+6x2+3x3 s.t. x1+3x2+4x3≥2 s.t. x1+2x2+2x3=5 2x1+x2+3x3≤3 -x1+5x2-3x3≥3 x1+4x2+3x3=5 4x1+7x2+3x3≤8 x1, x2≥0, x3无约束x1无约束,x2≥0, x3≤0 解：(a)对偶问题的原问题为 max w=2y1+3y2+5y3 s.t. y1+2y2+y3≤2 3y1+y2+4y3≤2 4y1+3y2+3y3=4 y1≥0, y2≤0, y3无约束 (b)原问题的对偶问题为 min w=5y1+3y2+8y3 s.t. y1-y2+4y3=5 2y1+5y2+7y3≥6 2y1-3y2+3y3≤3 y1无约束, y2≤0, y3≥0 2.3 已知线性规划问题： max z=x1+x2 s.t. -x1+ x2+ x3 ≤2 -2x1+x2- x3 ≤1 x1, x2, x3≥0 试应用对偶理论证明上述线性规划问题最优解为无界。 解：原问题的对偶问题为 min w=2y1+ y2 s.t. -y1- 2y2 ≥1 2y1+ 5y2 ≥1 y1- y2 ≥0 y1, y2≥0 由于约束条件3可得 y1-y2 ≥0 →y1≥y2 →-y1≤-y2 且y2≥0 所以 -y1-2y2 ≤-3y2≤0 （1） 由于约束条件1可得 -y1- 2y2 ≥1 （2） （1）（2）不等式组无解 所以其对偶问题无可行解,又知点X=(1,1,1)为原问题一个可行解,即原问题有可行解, 现在其对偶问题无可行解。根据对偶理论性质3原问题无界.