原问题
运筹学术语
原问题,又称原线性规划问题,是指每一个线性规划的原始问题,每个原问题均可以转化为与其对称的对偶问题。
内容概述
最优化理论研究的是在众多的方案中哪种方案最优,以及怎样找出最优方案的问题。该理论发展至今已出现线性规划整数规划非线性规划几何规划动态规划随机规划网络流等众多分支,其中线性规划与非线性规划是最优化理论的重要分支,也是最基本的部分。线性规划中普遍存在配对现象,对每个线性规划问题,都有另一个与其密切相关的线性规划问题存在,其中前者称为原问题,而后者即为它的对偶问题
转化规则
原问题与对偶问题是相对的,二者为同类型的规划,构成对偶规划的一般规则如下:
举例
原问题:某企业计划生产甲、乙两种产品,该两种产品均需要A、B、C、D 四种不同的材料,按工艺资料规定,生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?
解:设企业生产甲产品为 件,乙产品为 件,则
目标函数:
约束条件:
对偶问题:如果另外一企业想将上述企业拥有的资源收买过来,至少应付出多少代价,才能使第一个企业愿意放弃生产活动,出售资源?
解:设第i种资源单位增值价(售价=成本+增值)为 ,则
目标函数:
约束条件:
应用
线性规划的原问题与对偶问题的对应关系决定了二者之间可通过一定规则相互转化。因此可将复杂的原问题转化成其对偶问题进行解决,从而简化线性规划问题。教师在教学中可以引导学生将运筹学知识点进行归纳总结,以加深理解,提高学习效率的观点。并以线性规划中原问题与对偶问题转化为例,探讨了转化规律的总结过程及其教学体会,为运筹学教学中对其它知识点的归纳总结提供了启示。
参考资料
最新修订时间:2022-08-25 16:45
目录
概述
内容概述
转化规则
参考资料