- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
z = c1 x1 + c2 x2 + ... + cm xm + cm +1 xm +1 + ... + cn xn ′ ′ ′ = c1 ( b1′ − a1, m +1 xm +1 − a1, m+ 2 xm+ 2 − ... − a1n xn ) + ... ′ ′ ′ ′ + c2 ( b2 − a2,m +1 xm +1 − a2,m + 2 xm + 2 − ... − a2 n xn ) ′ ′ ′ ′ + cm ( bm − am,m +1 xm +1 − am ,m + 2 xm + 2 − ... − amn xn ) + cm +1 xm +1 + ... + cn xn ′ = c1b1′ + c2b′ + ... + cmbm
m
)
′ = c n − c1a1, n + c 2 a′ , n + ... + c m a′ , n 2 m
i =1
(
)
′ ′ c1 1 0 ... 0 a1, m +1 ... a1n × c 2 0 1 ... 0 a2, m +1 ... a2 n ′ ′ : × ...... c m 0 0 ... 1 am, m +1 ... amn ′ ′
School of Business ECUST
′ ′ ′ ′ x1 = b1 − a1,m+1xm+1 − a1,m+2xm+2 −... − a1n xn ′ ′ ′ ′ x2 = b2 − a2,m+1xm+1 − a2,m+2xm+2 −... − a2n xn ...... ′ ′ ′ ′ xm = bm − am,m+1xm+1 − am,m+2xm+2 −... − amn xn
School of Business ECUST
考虑线性规划的标准型： 考虑线性规划的标准型：
max z = c1 x1 + c2 x2 + ... + cm xm + cm +1 xm +1 + ... + cn xn a11 x1 + a12 x2 + ... + a1,m xm + a1,m +1 xm +1 + ... + a1n xn = b1 a21 x1 + a22 x2 + ... + a2,m xm + a2,m +1 xm +1 + ... + a2 n xn = b2 s.t. ...... a x + a x + ... + a x + a m,m m m , m +1 xm +1 + ... + amn xn = bm m1 1 m 2 2 x j ≥ 0, j = 1, 2, ..., n
m
′ ′ ′ − c1a1, m + 2 − c2 a2, m + 2 − ... − cm am , m + 2 ) xm + 2
i =1
′ ′ ′ + ( cn − c1a1n − c2 a2 n − ... − cm amn ) xn
非基变量前的系数：σ j
m
cn − ∑ ci ai′,n
i=1 =
′ ′ 1 0 ... 0 a1, m +1 ... a1n ′ ′ 0 1 ... 0 a2, m +1 ... a2 n ...... ′ ′ 0 0 ... 1 am, m +1 ... amn
0 0 … 0
cm +1
m i =1
σj
….
cn
m i =1
−∑ ci ai′, m +1 −∑ c a′ i i,n
(
(
)
)
解的判别：
① 若 X ( k ) = ( b1′, b2 ,..., bm ,0,...,0 )T 是对应于基Bk = (P1,P2, ..., Pm)的 ′ ′ 基可行解，对于一切 j = m+1,...,n, 均有检验数 σ j ≤ 0 ，则 k X ( ) 为最优解； ② 若 X ( k ) = ( b1′, b2 ,..., bm ,0,...,0 )T 是对应于基 Bk = (P1,P2, ..., Pm)的基 ′ ′ 可行解，对于一切 j = m+1,...,n, 均有检验数 σ j ≤ 0，并且 存在某个非基变量(比如xm+r)的检验数 σ m + r = 0 ，则该线性规 划问题有无穷多最优解； ③ 若 X ( k ) = ( b1′, b2 ,..., bm ,0,...,0 )T是对应于基 Bk = (P1,P2, ..., Pm)的基 ′ ′ 可行解，若存在某个非基变量(比如xm+r)的检验数 σ ， m+r > 0 并且对i=1,2,…,m, 均有 a′ ≤ 0，则该线性规划问题有无界 i,m+ r 解(无最优解)。
为了将目标函数全部用 非基变量表达，我们要 将基变量x1，x2, ...,xm用非 基变量xm+1,...,xn来表达
′ ′ ′ x1 = b1′ − a1,m+1xm+1 − a1,m+2 xm+2 − ... − a1n xn ′ ′ ′ ′ x2 = b2 − a2,m+1xm+1 − a2,m+2 xm+2 − ... − a2n xn ...... ′ ′ ′ ′ xm = bm − am,m+1xm+1 − am,m+2 xm+2 − ... − amn xn
即：通过求非基变量的检验数来判定是否为最优解！ 通过求非基变量的检验数来判定是否为最优解！
检验数公式
σ j = c j − ∑ ci a′ , j = m + 1,..., n ij
i =1
School of Business ECUST
m
σ j = c j − ∑ ci a′ , j = m + 1,..., n ij
i =1
m
σm+1 = cm+1 − ∑cia′,m+1 i
′ = cm+1 − c1a1,m+1 + c2a′,m+1 + ... + cma′ ,m+1 2 m
m
max z = c1 x1 + c2 x2 + ... + cm xm + cm +1 xm +1 + ... + cn xn x1 x2 a11 a12 ... a1, m a1, m +1 ... a1n b : 1 a21 a22 ... a2, m a2, m +1 ... a2 n b xm = 2 s.t. ...... x : m +1 a a ... a m1 m 2 m , m am , m +1 ... amn : bm x n x ≥ 0, j = 1, 2,..., n j
School of Business ECUST
′ z = c1b1′ + c2 b′ + ... + cm bm + ( cm + 2 + ...
cm+1 − ∑ ci ai′,m +1
i =1
m
′ ′ ′ + ( cm +1 − c1a1, m +1 − c2 a2, m +1 − ... − cm am , m +1 ) xm +1 c − c a′ ∑ i i ,m + 2 m+2
(
i =1
)
对增广矩阵 作初等行变换 将基变为单位阵
1 0 0
x2 ′ ′ 0 ... 0 a1, m +1 ... a1n b′ : 1 ′ ′ 1 ... 0 a2, m +1 ... a2 n b′ xm = 2 ...... x : ′ ′ , m +1 ... amn m +1 bm ′ 0 ... 1 am : x n
′ σ n = cn − c1a1, n + c 2 a′ , n + ... + c m a′ , n 2 m
×
c m +1
cn
′ σ m +1 = c m +1 − c1a1, m +1 + c 2 a′ , m +1 + ... + c m a′ , m +1 2 m
School of Business ECUST
School of Business ECUST
4.2 单纯形表
′ z = c1b1′ + c2b′ + ... + cmbm ′ ′ ′ + ( cm +1 − c1a1, m +1 − c2 a2, m +1 − ... − cm am , m +1 ) xm +1 + ... ′ ′ ′ + ( cn − c1a1n − c2 a2 n − ... − cm amn ) xn
