第三章(肖健华)

1、1第三章 线性规划的对偶理论2 内涵一致但从相反角度提出的一对问题互为对偶问题。 原问题P与对偶问题D的对应关系：相伴而生。3本章主要内容n给定LP原问题P后，如何写出对偶问题D；n原问题与对偶问题的关系；n给出解LP问题的对偶单纯形算法；n灵敏度分析43.1 对偶问题的提出 例1：某家具厂木器车间生产木门与木窗两种产品，加工木门收入为56元/扇，加工木窗收入为30元/扇，生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时，该车间每日可用木工总工时为120小时，油漆工总工时为50小时，问该车间如何安排生产才能使每日收入最大？ 5 例2：某工厂在某一计划期内准备生

2、产甲、乙两种产品，生产需要消耗A、B、C三种资源，各种资源拥有量分别为8、16、12。生产甲需A、B、C分别为1，4，0，生产乙需A、B、C分别为2，0，4。现已知甲、乙的利润分别为2，3.问：如何安排生产，以使计划期内的生产获利最大？6原问题与对偶问题的对应原问题 对偶问题 ), 2 , 1(0max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn), 2 , 1(0min221122222112112211112211mjycyayayacyayayacyayayaybybybwjnmmnnnmmmmm

3、m7注意：83.2 对偶关系及对偶性质一、原问题与其对偶问题的对应关系 对称形式的原问题：目标函数求极大值、约束条件取小于等于号、决策变量非负的线性规划问题。9对称形式的原问题与对偶问题具有对应关系： 原问题目标函数求极大值，对偶问题目标函数求极小值； 原问题约束条件的数目等于对偶问题决策变量的数目； 原问题决策变量的数目等于对偶问题约束条件的数目； 原问题的价值系数成为对偶问题的资源系数；10对称形式的原问题与对偶问题具有对应关系： 原问题的资源系数成为对偶问题的价值系数； 原问题的技术系数矩阵与对偶问题的技术系数矩阵互为转置； 原问题的约束条件为小于等于号，对偶问题的决策变量大于等于0；

4、原问题的决策变量大于等于0，对偶问题的约束条件为大于等于号。11例1：设LP的数学模型如下，求其对称形式下的对偶问题的数学模型。2122maxxxz0,121214221212121xxxxxxxx 12例2：写出如下线性规划问题的对偶问题32132maxxxxz0,6325324321321321321xxxxxxxxxxxx 13 本例表明：原问题约束条件不等号的方向决定对偶决策变量取值的正负。 原问题的约束条件取等号，那么与它对应的对偶变量取无约束； 原问题(max)的约束条件取小于等于号，那么与它对应的对偶变量取值非负； 原问题(max)的约束条件取大于等于号，那么与它对应的对偶变量取

5、值非正。14例3 写出以下线性规划问题的对偶问题 32132maxxxxz无约束321321321321, 0, 06325324xxxxxxxxxxxx 15本例表明：原问题的决策变量的取值决定其对偶约束条件不等号的方向。 原问题决策变量取值无约束，其对应的对偶约束条件取等号； 原问题(max)决策变量取值非负，那么与之对应的对偶约束条件取大于等于号； 原问题(max)决策变量取值非正，那么与之对应的对偶约束条件取小于等于号。16对偶关系表 17例4：根据对偶关系表写出下述线性规划的对偶规划 3213225minxxxz 无限制321321321321, 0, 012121xxxxxxxxx

6、xxx18二、对偶性质（1）对偶性：对偶问题的对偶是原问题；（2）弱对偶性：若X和Y分别是原问题（max）的任一可行解和对偶问题的任一可行解，则一定存在CX YB；（3）无界性：若原问题有无界解，则其对偶问题无可行解；（4）最优性：若X是原问题（max）的可行解， Y是对偶问题的可行解，当CX YB时，X是原问题的最优解，Y是对偶问题的最优解；（5）强对偶性：弱原问题有最优解，那么对偶问题也一定有最优解，且两者的目标函数值相等。19二、对偶性质（6）互补松弛性：在线性规划的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格的等式；反之，若约束条件取严格的不等式，则其对应的对偶变

7、量为零。（7）用单纯形法求解线性规划问题时，迭代的每一步在得到原问题的一个基本可行解的同时，其检验数行j的值是其对偶问题的一个基本解；在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。20对性质7的说明例：原问题 212maxxxz0,524261552121212xxxxxxx 21对偶问题 32152415minyyyw0,1252632132132yyyyyyyy 223.3 对偶单纯形法n对偶单纯形法是利用的对偶原理来求解原问题的一种方法，而不是用来求解对偶问题；n之前第

8、2章的单纯形法称为原始单纯形法。23注意： n对偶单纯形方法并不需要把原问题转化为对偶问题，只需利用原问题与对偶问题的数据相同（只是所处位置不同）这一特点，直接在反映原问题的单纯形表上进行计算；n对偶单纯形法并不要求原问题的初始解是基可行解，因此，可以从非可行的基解开始迭代，从而省去了引入人工变量的麻烦；n对偶单纯形法要求对偶问题的解始终是基可行解，即要求原问题的所有变量的检验数非负，这是对偶单纯形法应用的前提，十分苛刻，所以直接应用对偶单纯形法求解线性规划问题并不多见，主要用于灵敏度分析。24二、对偶单纯形法的计算步骤2526例1：用对偶单纯形法求解LP问题 42134minxxxw0,24

9、232432143214321xxxxxxxxxxxx27例2：用对偶单纯形法求解LP问题 32152415maxxxxz0,1252632132132xxxxxxxx28二、对偶单纯形法中无可行解的识别n在对偶单纯形法中，总是存在着对偶问题的可行解，因此对于能用对偶单纯形法求解的线性规划问题来说，其解不存在无界解的可能；n对偶单纯形法无可行解的识别是通过入基变量选择失败来加以反映的，即当主行的所有元素均为非负时，线性规划问题无可行解。29例3：用对偶单纯形法求解下述线性规划问题 3212minxxxw0,122102321321321xxxxxxxxx30思考题：n问：是否存在某一单纯形表，

10、既可用单纯形法求解，又可用对偶单纯形法法求解？ 31答：不行如果可用单纯形法法求解，必然存在b 0；如果可用对偶单纯形法求解，必然存在 0；若b 0和 0同时成立，则得到最优解。32思考题问：对于一个LP问题，有可能用单纯形法求解，也有可能用对偶单纯形法求解，问可否在一个LP中先用单纯形法求解，后用对偶单纯形法求解？或反之？33答：不会 因为在求解过程中，始终有b 0或 0。 343.4 灵敏度分析 n灵敏度分析是指对系统因环境变化显示出来的敏感程度分析。 n就LP问题而言，决策者还需要掌握两方面的信息： LP问题中的各项系数（价值系数、技术系数、资源项）一个或几个发生变化时，已求得的最优解会

11、有什么变化？ 上述系数在什么范围内发生变化时，线性规划问题的最优解（或最优基）不变。35将变化直接反映到最终单纯形表中，并按下表处理： 原问题对偶问题 结论或继续计算步骤可行解可行解最优解可行解非可行解 用单纯形法求解非可行解 可行解用对偶单纯形法求解非可行解 非可行解 引入人工变量再求解不含单位矩阵先作初等行变换获取单位矩阵，再操作36一、资源系数变化的分析 37例2 某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸供应限量30000kg。如果单独生产各种产品时，每个工人每天可生产原稿纸30捆或日记本30打或练习本30箱。已知原材料消耗为：每捆

12、原稿纸用白坯纸10/3kg，每打日记本用白坯纸40/3kg，每箱练习本用白坯纸80/3kg，又知每生产一捆原稿纸可盈利2元，每生产一打日记本可盈利3元，每生产一箱练习本可盈利1元。试决定：在现有生产条件下，工厂盈利的最大方案；如果白坯纸的供应量不变，当工人人数不足时，可招收临时工，临时工每人每天40元，问该厂要不要招收临时工，最多招收多少人？ 38二、价值系数变化的分析 39情况1：价值系数发生变化的变量在最终单纯形表中为非基变量40情况2：价值系数发生变化的变量在最终单纯形表中为基变量41三、技术系数变化的分析n情况1：技术系数发生变化的变量在最终单纯形表中为非基变量。n例1 线性规划问题如

13、下，问a23在什么范围内变化时，最优解保持不变。543210032minxxxxxw0,974352153214321xxxxxxxxxxx42情况2：技术系数发生变化的变量在最终单纯形表中为基变量例2 同上题，问当a11由1变为3时，原最优解是否发生改变，如果改变，求出新的最优解。543210032minxxxxxw0,974352153214321xxxxxxxxxxx434445四、增加一个新的变量的分析 n从形式上讲，增加一个新的变量相当于在单纯形表中增加一列，只要新增加的变量在最终单纯形表中的检验数非负（min），原问题的最优解就不会改变。如果检验数为负数，则需要重新迭代，以获取新的最优解；n在实际问题中，增加一个新的变量相当于增加一