定理 若标准LP问题有可行解，则必有基本可行解；若有最优解，则一定存在一个基本可行解是最优解。(证明略)
定理 若??0，则x是最优解。
T?1T?1证 ?x?0,??0,?Tx?0,z?cBBb??Tx?cBBb。
定理 若?的第k个分量?k?0，且Ak?B?1Ak?0，则该LP问题无界。这里Ak表示矩阵A的第k列。
?0???????0???证 取ek??1?，（这是一个n维的列向量，第k个分量为1，
?0???????0?????A?其余分量为0。）令???k??ek,取x?x+??,???0,(下面说明此
?0?x是可行解，且其指标值要多小有多小。)
??A?A?=A?k?+Aek?0???B?1Ak?= ?B,N????Ak = 0
?0?Ax?A(x???)?Ax??A??Ax?b x?0,
12
T?1T?1z?cBBb??Tx?cBBb??T(x+??)T?1?cBBb???T???B?1Ak?T?cBb??（???＋?ek）
?0?T?1?cBBb???kTB?1TT?1?cBBb?k?0
定理 若?的第k个分量?k?0，且Ak?B?1Ak中存在正分
??0，使得Ax??b且cTx??cTx。 量，则?x??x+??,（见前面定理中?的定义，这里??0但不证 令x能任意取。）
?为可行解： 1）可以适当取??0使得x由
??A?A?=A?k?+Aek?0???B?1Ak?=?B,N????Ak =0
?0???A(x???)?Ax??A??Ax?b； 知道Ax?B?1b???B?1Ak???0,即?要使得x?+?(??+ek)?0，只需
00?????B?1b???B?1Ak??1?1??+????0，Bb??BAk?0 ?0??0? 13
?b1??a1k????a?b2k?1?12设Bb???,BAk???, 由b1??a1k?0等知道
??????????b???amk??m??b取??min?i?aik2）
?aik?0,i?1,2,?,m?即可。
?T?1T?1??cBz?cBBb??TxBb??T(x+??)T?1?cBBb???T???B?1Ak?T?cBb??（???＋?ek）
?0?T?1?cBBb???kTB?1TT?1?cBBb这里?k?0，但因为?不能任意取大数，所以指标不能任意小。
§4 对偶线性规划
1．对偶线性规划
14
原始LP问题?mincTx?s.t.aiTx=bii?1,?,p??
aiTx?bii?p?1,?,m??xj?0j?1,2,?,q?j?q?1,?,nxj自由??对偶问题D：?maxbTw?s.t.wi 自由??wi?0??ATjw?cj?T?Ajw=cj?i??1,p,i?p?1?,m, j?1,2?,q,j?q?1,?n,aiT是约束矩阵A的第i行，Aj是约束矩阵A的第j列。
?mincTx?maxbTw??tAx?b的对偶问题为?s..tATw?c 规范形式?s..??x?0w ?0???mincTx?maxbTw??tAx?b的对偶问题为?s..tATw?c 标准形式?s..??x?0w 自由??2．对偶理论
定理 如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解值相等。
定理 对偶的对偶为原始的LP问题。 3．对偶LP的来历
将一般形式
?mincTx?s.t.aiTx=bii?1,?,p??aiTx?bii?p?1,?,m ??xj?0j?1,2,?,q?j?q?1,?,nxj自由?? 15
?化为标准形式?minc?Tx???s.t.Ax???b，其中 ???x??0c?T???c1,?,cq,cq?1,?cq?1,?,cn,?cn,0,?,0??，
x???x????ssT?1,?,xq,xq?1,xq?1,?,xn,xn,x1,?,xm?p??， A?????A0p?(m?p)??1,?,Aq,Aq?1,?Aq?1?,An,?An,?I?m?p??m?[q?2(n?q)?m?p]??a11a12?a1qa1,q?1?a1,q?1?a1,n?a1,n?????????????ap1ap2?apqap,q?1?ap,q?1?ap,q?1?ap,n?a?a?p?1,1ap?1,2p?1,qap?1,q?1?ap?1,q?1?ap?1,q?1?ap?1,n????????????am1am2?amqam,q?1?am,q?1?am,q?1?am,n，
??T?c?TB?B??1A??c?T?0，令wT?c?TB?B??1，则??T?0改写为 wTA??c?T，即A?Tw?c?，展开为 ??AT1??c1??AT1????w?c??1?T???????Aq??AT???cq????ATqw?cq?q?1??cq?1??ATq?1?????w????cq?1??， ???ATq?1w?cq?1T??A??ATq?1w?cq?1 q?1w??cq??????1T?An??cn?????AT???n??c?ATnw?cnT?0|?I??m?p??n??0???A???ATnw?cnnw??cn16
0?0?????0?0??1?0?????0??1?????