《对偶单纯形法(3学时).ppt》由会员分享，可在线阅读，更多相关《对偶单纯形法(3学时).ppt（67页珍藏版）》请在三一办公上搜索。
1、第二章 对偶理论,2.1 对偶规划2.2 对偶定理2.3 对偶单纯形法2.4 线性规划灵敏度分析2.5 运输问题,弱对偶定理强对偶定理松紧定理,原规划和对偶规划最优解之间的关系,复习,第二章 对偶理论,第二节 对偶定理,一.弱对偶定理：,定理2-1：,推论1：,minS=maxZ,设X 和 分别是(P)和(D)的可行解，则有,若 和 分别是(P)和(D)的可行解，且,则 和 分别是(P)和(D)的最优解。,二.强对偶定理：,定理2-2：,推论3：,推论1：,(P)有有限的最优解(D)有有限的最优解,且相应的目标函数值相等，即,若 是(P)的最优基本可行解，B是相应的最优基，,则单纯形乘子 是(
2、D)的最优解。,若(P)和(D)中有一个有可行解，但没有有限的最优解，则另一个问题无可行解。,第二章 对偶理论,2.1 对偶规划2.2 对偶定理2.3 对偶单纯形法2.4 线性规划灵敏度分析2.5 运输问题,第三节 对偶单纯形法,基本思想迭代原理举例求解影子价格,第二章 对偶理论,单纯形法是保持 使迭代向实现 进行。,一.基本思想：,最优表,是基变量下标集,对偶单纯形法是保持 使迭代向实现 进行。,若，则这个解X是(P)的最优基本可行解。,若(P)的一个基B，使得单纯形乘子 是(D),的可行解，则(P)相应的基本解,对偶可行解，正则基：,称为对偶可行解，B称为正则基。,对偶可行解，正则基：,理
3、解：,若(P)的一个基B，使得单纯形乘子 是(D)的可行解,，则(P)相应的基本解 称为,对偶可行解，B称为正则基。,若，则X是(P)的最优解。,1)一个基B对应一个单纯形乘子,2)是(D)的可行解,正则基 B对应的基本解称为对偶可行解,B相应的单纯形表的检验数行,对应正则基的单纯形乘子是(D)的可行解；对应最优基的单纯形乘子是(D)的最优解。,B是正则基,对偶可行解，正则基：,若(P)的一个基B，使得单纯形乘子 是(D)的可行解,，则(P)相应的基本解 称为,对偶可行解，B称为正则基。,若，则X是(P)的最优解。,基,可行基,正则基,最优基,基本解,基本可行解,对偶可行解,最优基本可行解,可
4、逆,基本思想迭代原理举例求解影子价格,第三节 对偶单纯形法,第二章 对偶理论,二.迭代原理：,准备工作：,准备工作：,准备工作：,设 是(P)的一个正则基，,二.迭代原理：,是(D)的可行解,则,二.迭代原理：,设 是(P)的一个正则基，,则 是(P)的最优解,是(D)的最优解。,则当前基本解,不是最优解，因此进行换基运算，得到新表。,1.确定离基变量：,二.迭代原理：,则第r个方程的基变量 离基。,2.确定进基变量：,二.迭代原理：,不是(D)的最优解,不是(D)的最优值.,所以(D)有可行解 使目标值，即,的第r个行向量，,2.确定进基变量：,1)对,的第r个行向量，,2.确定进基变量：,
5、1)对,的第r个行向量，,(使(D)目标值),2.确定进基变量：,1)对,的第r个行向量，,2)取 使 是(D)的可行解,(P)无可行解,对偶单纯形法的求解过程：,(使(D)目标值),2.确定进基变量：,1)对,的第r个行向量，,2)取 使 是(D)的可行解,1,不离基的基列,(使(D)目标值),2.确定进基变量：,1)对,的第r个行向量，,(使(D)目标值),2)取 使 是(D)的可行解,1,不离基的基列,2.确定进基变量：,1)对,的第r个行向量，,(使(D)目标值),2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,2.确定进基变量：,1)对,的第r个行向量，,(使(D)目
6、标值),2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,2.确定进基变量：,1)对,的第r个行向量，,(使(D)目标值),2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,非基列,3,2.确定进基变量：,1)对,的第r个行向量，,(使(D)目标值),2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,非基列,3,非基列,2.确定进基变量：,的第r个行向量，,2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,3,1,若对,都有,二.迭代原理：,即对 是(D)的可行解。,非基列,2.确定进基变量：,的第r个行向量，,2)取 使 是(D)的可行
7、解,1,不离基的基列,2,离基的基列,3,1,若对,都有,则,但,即对 是(D)的可行解。,非基列,2.确定进基变量：,的第r个行向量，,2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,3,1,若对,都有,则,但,即(D)没有有限的最优解，,2,所以(P)无可行解。,若,使,二.迭代原理：,为进基变量，为主元,非基列,2.确定进基变量：,的第r个行向量，,2)取 使 是(D)的可行解,1,不离基的基列,2,离基的基列,3,1,若对,都有,(D)没有有限的最优解，,2,所以(P)无可行解。,若,使,要使,3.进行换基运算：,得到新的单纯形表,以 为主元进行换基运算，得到新的单纯形
8、表。,二.迭代原理：,为进基变量,所以新表对应的基本解目标值,两种算法比较：,单纯形法,对偶单纯形法,以 为主元进行换基运算，得到新的单纯形表。,二.迭代原理：,为进基变量,1.确定离基变量：,2.确定进基变量：,为离基变量,3.换基运算：,Ch2第二次课完,第二章 对偶理论,2.1 对偶规划2.2 对偶定理2.3 对偶单纯形法2.4 线性规划灵敏度分析2.5 运输问题,基本思想迭代原理举例求解影子价格,第三节 对偶单纯形法,第二章 对偶理论,二.迭代原理：,设 是(P)的一个正则基，,则 是(P)的最优解,是(D)的最优解。,则当前基本解,不是最优解，因此进行换基运算，得到新表。,复习,以
9、为主元进行换基运算，得到新的单纯形表。,二.迭代原理：,为进基变量,1.确定离基变量：,2.确定进基变量：,为离基变量,3.换基运算：,复习,三.举例：,对偶单纯形法开始于一个正则基B,即,注意：,例2-2：,标准形,正则基,所以适用于 且不等式约束都是 的问题。,-1,-2,-3,1,0,-5,-2,-2,-1,0,1,-6,3,4,5,0,0,0,3,4,5,0,0,0,0,?,正则基,为进基变量,例2-2：,-1,-2,-3,1,-5,-2,-2,-1,0,1,-6,3,4,5,0,0,0,0,1/3,(-1/3),2/3,1,-1/3,5/3,例2-2：,1/3,-2,-2,-1,0,
10、1,-6,3,4,5,0,0,0,0,2/3,1,-1/3,5/3,0,-5/3,-4/3,-1/3,-13/3,例2-2：,1/3,-5/3,-13/3,1,3,4,5,0,0,0,0,2/3,1,-1/3,5/3,0,-4/3,-1/3,(-5),0,4/3,2/3,5/3,-25/3,例2-2：,1,1/3,-5/3,-13/3,1,0,2/3,-1/3,5/3,0,-4/3,-1/3,0,0,4/3,2/3,5/3,-25/3,?,正则基,为进基变量,例2-2：,-4/3,1,1/3,-5/3,-13/3,1,0,2/3,-1/3,5/3,0,-1/3,0,0,4/3,2/3,5/3,
11、-25/3,(-3/4),1,5/4,1/4,-3/4,13/4,例2-2：,0,1,5/4,1/4,-3/4,13/4,1,1/3,0,2/3,-1/3,5/3,0,0,4/3,2/3,5/3,-25/3,(-2/3),0,-1/2,-1/2,1/2,-1/2,例2-2：,-1/2,-1/2,0,1,5/4,1/4,-3/4,13/4,0,0,4/3,2/3,5/3,-25/3,1,0,-1/2,1/2,(-2/3),0,1/2,3/2,1/2,-21/2,例2-2：,-1/2,-1/2,0,1,5/4,1/4,-3/4,13/4,1,0,-1/2,1/2,0,0,3/2,1/2,1/2,-
12、21/2,?,正则基,为进基变量,例2-2：,-1/2,-1/2,0,1,5/4,1/4,-3/4,13/4,1,0,-1/2,1/2,0,0,3/2,1/2,1/2,-21/2,(-2),1,-2,1,-1,1,例2-2：,0,1,-2,1,-1,1,0,1,5/4,1/4,-3/4,13/4,0,0,3/2,1/2,1/2,-21/2,(-5/4),0,-1,2,5/2,1/2,例2-2：,1,0,-1,2,5/2,1/2,0,1,-2,1,-1,1,0,0,3/2,1/2,1/2,-21/2,(-1/2),0,1,1,1,-11,例2-2：,1,0,-1,2,5/2,1/2,0,1,-2
13、,1,-1,1,0,0,1,1,1,最优表,?,最优基,正则基,最优解,原问题最优解,-11,例2-2：,例2-2：,1,0,-1,2,5/2,1/2,0,1,-2,1,-1,1,0,0,1,1,1,-11,0,0,E,(1,1),最优基,有最优解,例2-2：,3,4,5,0,0,3,4,对偶,对偶,标准形,例2-2：,基本思想迭代原理举例求解影子价格,第三节 对偶单纯形法,第二章 对偶理论,四.影子价格：,通常在实际问题中表示资源拥有量.,表示单位资源的价格，称为影子价格。,设B是(P)的最优基,则 是(P)的最优解，,是(D)的最优解。,且,是最优值。,例：,某工厂在计划期内要安排生产甲乙
14、两种产品，它们需要在四种不同的设备上加工。加工工时数、可得利润、总工时数均列于下表。,例：,(影子价格),A,B,C,D的资源拥有量,A,B,C,D的单位资源的价格,例：,甲乙最优产量,4种设备单位工时的最优定价,自己生产的利润收入,对外出租的租金收入,(影子价格),A,B,C,D的资源拥有量,A,B,C,D的单位资源的价格,最优解：,总收入：,第i 种资源 的影子价格,越多,越大,影子价格的经济解释：,资源拥有量,单位资源的价格(影子价格),越,设 是(P)的最优解，,是(D)的最优解.,且,当 增加一个单位时，收入S的增加量。,增加 一个单位时，S 不增加，则不应增加该种资源。,增加 一个单位时，S 增加，则 应增加该种资源。,基本思想迭代原理举例求解影子价格,第三节 对偶单纯形法,第二章 对偶理论,作业：P96 10(1)(2),作业：P84 2(1)(2),
