3.无界性如果原问题（对偶问题）有无界解，则其对偶问题（原问题）无可行解。若原问题为无界解，则对偶问题无可行解：若对偶问题为无界解，则原问题无可行解。（不可逆）即：若原问题（对偶问题）无可行解，则其对偶问题（原问题）无界解。（×)因为：无界解无可行解一无可行解2024-10-2717
2024-10-27 17 3. 无界性 如果原问题（对偶问题）有无界解，则其对偶问题 （原问题）无可行解。 若原问题为无界解，则对偶问题无可行解； 若对偶问题为无界解，则原问题无可行解。 （不可逆）即：若原问题（对偶问题）无可行解，则其对偶问题（原 问题）无界解。（×） 因为： 无界解 无可行解 无可行解
4.强对偶性如果原问题有最优解，则其对偶问题也必有最优解且两者最优目标函数值相等，即J max z = min w maxZ=CX+0X,maxZ=CX证明设有线性规划问题[AX+X,=b[AX<bX,X,≥0X≥0经单纯形法计算后，令Y=CB->O，最终表中基变量非基变量基可行解B-1b'N'1C,B-1a_→C.B-N0=C-CB-"BON=C即:YA≥C.α,=C-YA≤0,αx=-C,B, =-Y≤0.Y≥0由此可知Y是对偶问题的可行解；又CX=C,B"b=Yb，．Y就是最优解。2024-10-2718
2024-10-27 18 4. 强对偶性 如果原问题有最优解，则其对偶问题也必有最优解， 且两者最优目标函数值相等，即 。 证明 设有线性规划问题 经单纯形法计算后，令 ， 最终表中 ∴ , 即： 由此可知Y是对偶问题的可行解； 又 ∵ ， ∴ Y 就是最优解。 0 max X AX b Z CX 基可行解 基变量 非基变量 0 1 Y CB B b 1 I N B j N CN CB B N 1 1 C C B B CB B B B 1 0 C YA 0 x YAC CX C B b Yb B 1 max z min w , 0 max 0 s s s X X AX X b Z CX X 0, x CBB1 Y s Y 0
线性规划单纯形法的矩阵描述设有线性规划问题的标准形式max z = CXmaxz = CX +0XsAX≤b[AX + IXs = b将系数矩阵表示成：A=(B,NI)s.ts.tX≥0X,X,≥0初始解非基变量基变量NBX.1初始单纯形表bC0g,CNCB7基可行解基变量非基变量初等行变换后XBB-11B-'bB-'N0C,B-19i→Cn-C,B-N初始表中是I的位置，经变换后成为B-1。192024-10-27
2024-10-27 19 线性规划单纯形法的矩阵描述 设有线性规划问题的标准形式 0 .max X AX b st z CX 将系数矩阵表示成： A (B, N I) 初始单纯形表 初始解 非基变量 基变量 0 b B N I j CB CN 基可行解 基变量 非基变量 0 初等行变换后 B b 1 1 B N B 1 I j CN CBB 1N 1 CB B Xs XB 初始表中是 I 的位置，经变换后成为 。 , 0 .max 0 S S S X X AX IX b st z CX X