原问题

原问题，又称原线性规划问题，是指每一个线性规划的原始问题，每个原问题均可以转化为与其对称的对偶问题。

内容概述最优化理论研究的是在众多的方案中哪种方案最优，以及怎样找出最优方案的问题。该理论发展至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等众多分支，其中线性规划与非线性规划是最优化理论的重要分支，也是最基本的部分。线性规划中普遍存在配对现象，对每个线性规划问题，都有另一个与其密切相关的线性规划问题存在，其中前者称为原问题，而后者即为它的对偶问题。1

转化规则原问题与对偶问题是相对的，二者为同类型的规划，构成对偶规划的一般规则如下：1

若原问题是极大化问题，那么对偶问题就是极小化问题；若原问题是极小化问题，那么对偶问题就是极大化问题。

在原问题与对偶问题中，约束右端向量与目标函数中系数恰好对换。

对于极小化问题的“≥ ”型约束(极大化问题的“≤ ”型约束)，相应的对偶变量有非负限制；对于极小化问的“≤ ”型约束(极大化问题的“≥ ”型约束)，相应的对偶变量有非正限制；对于原问题的“=”型约束，相应的对偶变量无正负限制。

对于极小化问题的具有非负限制的变量(极大化问题的具有非正限制的变量)，在其对偶中相应的约束为“≤ ”型不等式；对于极小化问题的具有非正限制的变量(极大化问题的具有非负限制的变量)，在其对偶问题中相应的约束为“≥ ”型不等式；对于原问题中无正负限制的变量，在其对偶问题中相应的约束为等式。2

举例原问题：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大?

|| ||

解：设企业生产甲产品为 件，乙产品为 件，则

目标函数：

约束条件：

对偶问题：如果另外一企业想将上述企业拥有的资源收买过来，至少应付出多少代价，才能使第一个企业愿意放弃生产活动，出售资源？

解：设第i种资源单位增值价（售价=成本+增值）为 ，则

目标函数：

约束条件：

应用线性规划的原问题与对偶问题的对应关系决定了二者之间可通过一定规则相互转化。因此可将复杂的原问题转化成其对偶问题进行解决，从而简化线性规划问题。教师在教学中可以引导学生将运筹学知识点进行归纳总结，以加深理解，提高学习效率的观点。并以线性规划中原问题与对偶问题转化为例，探讨了转化规律的总结过程及其教学体会，为运筹学教学中对其它知识点的归纳总结提供了启示。3

本词条内容贡献者为:

杜强 - 高级工程师 - 中国科学院工程热物理研究所