2.098/15.093J:练习3 1.对偶理论 直凳上，对偶变量可以看作是价格咸怎罚。不是在问题中加强约束条作，而是当钓束条 件不能满足时，要对目标成本递行惩得。 问题1 给出一般的线性规划问愿， min c'x sI Axzb 使用拉格朗日乘子构造其对偶付题。 解 设函数g(p)=min,c女+p(b-Ax) g(p)=p'b+min,(c'-p'Ab 可以得出， min.e c'-pA≠0 因此ma8(P)=maxp'b min b'p 付题可以写成如下形式： P'A=c p20 月题2 给出标准形式的基矩库B 1求原问题的基木解 2求对偶问愿的基本解 3求该基矩防的最优性条件 4如果原间愿是退化的，请说出相应的对偶基本解的情况。 5如果原问题的基本可行解不是最优解，请说出对应的对偶月题的基木解的情况：
2.098/15.093J:练习 3 1．对偶理论 直观上，对偶变量可以看作是价格或惩罚。不是在问题中加强约束条件，而是当约束条 件不能满足时，要对目标成本进行惩罚。 问题 1 给出一般的线性规划问题， st Ax b c x ≥ ′ . . min 使用拉格朗日乘子构造其对偶问题。 解： 设函数 g( ) p c x p (b Ax) = minx ′ + ′ − g( ) p p b (c p A)x x = ′ + min ′ − ′ 可以得出， ( ) ⎩ ⎨ ⎧ ′ − ′ = − ∞ ′ − ′ ≠ ′ − ′ = 0 0 0 min c p A c p A c p A x x 因此 g p p b p R p R p A c m m = ′ ∈ ∈ ′ = ′ + + max : max ( ) 问题可以写成如下形式： 0 . . min ≥ ′ = ′ ′ p st p A c b p 问题 2 给出标准形式的基矩阵 B 1.求原问题的基本解 2.求对偶问题的基本解 3.求该基矩阵的最优性条件 4.如果原问题是退化的，请说出相应的对偶基本解的情况。 5.如果原问题的基本可行解不是最优解，请说出对应的对偶问题的基本解的情况。 1
6如果原始基本可行解是最优解，请说明相应的对偶基本解的情况 7如果对偶基木解是是化的，请说出相应的原始基木解的情况， 解答： 1.Xg=B-b 2.p'=c4B 3.原始可行性：Bb≥0 对偶可行性：C'-pA20 4.存在两个或两个以上与退化原始基本解有关的对偶基本解， 5。与此原始基本可行解有关的所有基础解都不是最优解，说明所有的对偶基本解都不可行： 6。至少存在一个与此原始基本可行解有关的最优基，说明至少存在一个对偶基本解可行， 7。有两个或两个以上与此对偶琴本解有关的基，因觉，其中一个基矩阵至少有一列含有基 变量，另外的基矩阵也至少含有一列非基变量。 此外，可以的得出，对偶问思中有大于m个起作用的束，说明原问题的非基变量中存在不 能降低成本的变量。 原始单纯形法和对偶单纯形法 原始单纯形法不改变源问墨的可行性，求借对偶问思的可行性，成本逐渐地降低至最优成本。 对钙单纯形法不改变对偶问题的可厅生，来解原问测的可」性。成本组建增加至最优成本。 原始单纯形法检验原问题的最优成本，而对属单纯形法检验原问题的可行性。 2,皱感性分析 基矩阵的两个最优性条件： 1.原始可行Bb20 2.对偶可行C'-CB-A≥0 改变成本向量C→C十定 不改变原问题可行性，改变对偶问题的可行性 1.jEN 仅影响到C,→C,十6 c,+620台62c 2
6.如果原始基本可行解是最优解，请说明相应的对偶基本解的情况 7.如果对偶基本解是退化的，请说出相应的原始基本解的情况。 解答： 1． x B b B −1 = 2． −1 p′ = c′ B B 3．原始可行性： 0 1 ≥ − B b 对偶可行性：c′ − p′A ≥ 0′ 4．存在两个或两个以上与退化原始基本解有关的对偶基本解。 5．与此原始基本可行解有关的所有基础解都不是最优解，说明所有的对偶基本解都不可行。 6．至少存在一个与此原始基本可行解有关的最优基，说明至少存在一个对偶基本解可行。 7．有两个或两个以上与此对偶基本解有关的基，因此，其中一个基矩阵至少有一列含有基 变量，另外的基矩阵也至少含有一列非基变量。 此外，可以的得出，对偶问题中有大于 m 个起作用约束，说明原问题的非基变量中存在不 能降低成本的变量。 原始单纯形法和对偶单纯形法 原始单纯形法不改变原问题的可行性，求借对偶问题的可行性。成本逐渐地降低至最优成本。 对偶单纯形法不改变对偶问题的可行性，求解原问题的可行性。成本组建增加至最优成本。 原始单纯形法检验原问题的最优成本，而对偶单纯形法检验原问题的可行性。 2．敏感性分析 基矩阵的两个最优性条件： 1．原始可行 0 1 ≥ − B b 2．对偶可行 0 1 ′ − ′ ≥ ′ − c cB B A 改变成本向量 j c → c +δe 不改变原问题可行性，改变对偶问题的可行性 1． j ∈ N 仅影响到 cj → cj + δ j j c + δ ≥ 0 ⇔ δ ≥ c 2
2.G→c-s4BA,=c-dB-Al a-dB-4l20台B-Al≤a 希如新的不等式约束条件 带如不等式：ax之b 1,若原来的最优解满足新的购束条件，则该最优解也是新问题的最优解 2.若原来的最优解不满足新的约束条科dX一X1=bn1,则地加轴助变量x, 新表未东李的阿 s- 新的苯本 (6x,ax-bn） 检验新基矩阵的逆 1=「8101 o6B-1 检验新的成木驿低向量： c'-cB-A 0 食验新表的土零部分：
2． [ ] i i k B A i i B Ai ki c c e B A c k j 1 1 : − − → − δ ′ = = − δ [ ] [ ] i i ki i ki i c − B A ≥ ⇔ B A ≤ c − − δ δ 1 1 0 增加新的不等式约束条件 增加不等式： +1 ≥ +1 ′ m bm a x 1．若原来的最优解满足新的约束条件，则该最优解也是新问题的最优解。 2．若原来的最优解不满足新的约束条件 +1 − +1 = +1 ′ m n m a x x b ，则增加辅助变量 n+1 x 构造初始对偶表来求解新的问题: 新的基矩阵： ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ′ − = 1 0 B a B B 新的基本解： ( ) 1 1 , + ∗ + ∗ m ′ − bm x a x 检验新基矩阵的逆： ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ′ − = − − − 1 0 1 1 1 a B B B B 检验新的成本降低向量： [ 0] 1 c cB B A− ′ − ′ 检验新表的主要部分： ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ′ − ′ − = + − − − 1 0 1 1 1 1 aB B A am B A B A 3