基本定理
闭集
【定理 1】
任意多面体都是闭集。
Weierstrass 定理
【定理 2】
Weierstrass 定理 若是连续函数，且是的非空闭有界子集，则存在，使得对所有均成立。类似地，存在使得对所有均成立。
分离超平面定理
【定理 3】
分离超平面定理 设是的一个非空闭凸子集，且为不属于的向量，则存在向量，使得对于所有均成立。
Farkas引理回顾
下面证明 Farkas 引理可以由分离超平面定理推导得出。
且向量不属于。显然，集合是凸集，且由可得其非空。此外，集合也是闭集，证明如下：是多面体在轴上的投影，则其本身也是多面体，因此是闭集。
对偶定理回顾
下面将通过 Farkas 引理推导对偶定理。
并且假设主问题有一个最优解。下面证明对偶问题有一个具有相同成本的可行解，由此即可从弱对偶定理推导出强对偶定理。
上式表明对偶可行解的成本与最优主问题成本相同，由此可推导得对偶定理。
总结
本节首先证明了分离超平面定理，其后利用分离超平面定理建立了 Farkas 引理，并证明了强对偶定理是 Farkas 引理的一个简单推论，从而实现了从分离超平面到对偶的反向论证。下一节将介绍锥和极射线的相关概念和性质。
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：交通与优化
责任编辑：江镕行
微信编辑：疑疑
文章转载自『交通与优化』公众号，原文链接：书籍导读 | Introduction to Linear Optimization 第16节：从分离超平面到对偶的反向论证
关注我们
FOLLOW US
