作业：
问题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) 对偶单纯形法的思想来源(5min) 2) 对偶单纯形法原理(5min) 3) 总结对偶单纯形法的优点及适用情况(5min) 4) 对偶单纯形法的求解过程(10min) 5) 对偶单纯形法例题(15min) 6) 对比分析单纯形法和对偶单纯形法(10min) 三、教学进程： 1）讲述对偶单纯形法思想的来源： 1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method ）。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 2）讲述对偶单纯形法的原理 A.对偶问题的基本性质 依照书第58页，我们先介绍一下对偶问题的六个基本性质： 性质一：弱对偶性 性质二：最优性。如果 x j （j=1...n)原问题的可行解，y j 是其对偶问题可 行解，且有 ∑=n j j j x c 1 =∑=m i i i y b 1 ，则x j 是原问题的最优解，y j 是其对偶问题的最
优解。 性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。 性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。 性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w. B.对偶单纯形法（参考书p64页） 设某标准形式的线性规划问题，对偶单纯形表中必须有c j -z j ≤0（j=1...n),但b i (i=1...m)的值不一定为正，当对i=1...m ，都有b i ≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。 3）为什么要引入对偶单纯形法 从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引入人工变量，使计算简化。 例如，有一线性规划问题： min ω =12 y 1 +16y 2 +15 y 3 约束条件 ?? ?? ???≥=≥+≥+0)3,2,1(3522 423121 i y y y y y i
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 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)：
§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．已知以下线性规划问题 max z= 2x 1 +x 2 -x 3 s.t. x 1 +2x 2 +x 3 ≤8 -x 1 +x 2 -2x 3 ≤4 x 1, x 2, x 3 ≥0 的最优单纯形表如下： z x 1 x 5 (1) 求使最优基保持不变的c 2=1的变化范围 C 2 1+δ -1 0 0 0 C B z 2 x 1 0 x 5 3-δ≥0，δ≤3，即c 2≤4。当c 2=5 ，即δ=4 z x 1 8/2 x 5 12/3 x 2进基，x 1离基 z x 2 x 5 新的最优解为x 1=0，x 2=0，x 3=0，x 4=0，x 5=0，max z=20 (2) 对c 1=2进行灵敏度分析 C 2+δ 1 -1 0 0 0 z x x x x x RHS C B z 2+δ x 1 0 x 5 3203020+≥+≥+≥?????δδδ，δδδ≥-≥-≥-??? ? ?3232/，当δ≥-3/2时，即c 1≥1/2时，最优基保持不变。 当c 1=4时，δ=4-2=2，最优基保持不变，最优解的目标函数制为z=16+8δ=32。 （3）增加一个新的变量x 6，c 6=4，a 612=????? ?。
[] z c c T 666620124242-=-=???? ? ?-=-=-W a Y B a 61 610111213==???????????? =???? ? ?- 新的单纯形表为 z x 1 x 5 x 6进基，x 5离基 z x 1 x 6 新的最优解为x 1=4，x 2=0，x 3=0，x 4=0，x 5=0，x 6=4，max z=24。 （4）增加一个新的约束x 2+x 3≥2，求新的最优基和最优解。 z x x x x x x RHS z x 1 x 5 x 6 3/1 3/1 用对偶单纯形法求解 z x x x x x x RHS z x 1 x 5 x 2 新的最优解为x 1=4，x 2=2，x 3=0，x 4=0，x 5=6，x 6=0，max z=10。
数学建模对偶问题和灵敏度分析
对偶问题 例题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． 对偶问题和对偶变量的经济意义是什么 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：书本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
第二章线性规划的对偶理论 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中。
四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：
根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省 ? 1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?
五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 X l X2X3X4 —10 b -1 f g X3 2 C O 1 1／5 X l a d e 0 1 (1)求表中a～g的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解 第四章线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3
火烈鸟饭店模型 LINEAR PROGRAMMING PROBLEM MAX 55X1+20X2+5X3 S.T. 1) 1500X1+1200X2+800X3>59000 2) 1X1<20 3) -2X1+1X2>0 4) 10000X1>140000 5) 3000X2<99000 6) 1000X3>30000 7) 10000X1+3000X2+1000X3<279000 OPTIMAL SOLUTION Objective Function Value = 1635.000 Variable Value Reduced Costs -------------- --------------- ------------------ X1 15.000 0.000 X2 33.000 0.000 X3 30.000 0.000 Constraint Slack/Surplus Dual Prices -------------- --------------- ------------------ 1 27100.000 0.000 2 5.000 0.000 3 3.000 0.000 4 10000.000 0.000 5 0.000 0.001 6 0.000 -0.001 7 0.000 0.006 OBJECTIVE COEFFICIENT RANGES
Variable Lower Limit Current Value Upper Limit ------------ --------------- --------------- --------------- X1 No Lower Limit 55.000 No Upper Limit X2 16.500 20.000 No Upper Limit X3 No Lower Limit 5.000 5.500 RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit ------------ --------------- --------------- --------------- 1 No Lower Limit 59000.000 86100.000 2 15.000 20.000 No Upper Limit 3 No Lower Limit 0.000 3.000 4 No Lower Limit 140000.000 150000.000 5 93375.000 99000.000 109000.000 6 15000.000 30000.000 40000.000 7 269000.000 279000.000 294000.000 1. 根据计算机求解可以求得： 次数预算宣传率新客户数电视15$150000117547500