线性规划原问题与对偶问题的转化及其应用

线性规划对偶问题线性规划是一种优化问题的数学建模方法，在实际生产和管理中广泛应用。

线性规划问题通常包括最大化或最小化一个线性目标函数的约束条件下的一组线性不等式或等式。

对于一个线性规划问题，其对偶问题是通过对原问题的目标函数和约束条件进行变换而得到的。

对偶问题有助于理解原问题的特性，并提供关于原问题的附加信息。

具体来说，对于一个原问题：最小化 C^T * X约束条件 A * X >= bX >= 0其中，C是目标函数的系数矩阵，X是决策变量向量，A是约束条件的系数矩阵，b是约束条件的右侧向量。

对于原问题的对偶问题，其形式为：最大化 b^T * Y约束条件 A^T * Y <= CY >= 0其中，Y是对偶变量向量。

对偶问题的最优解被称为对偶可行解，对偶问题的最优解与原问题的最优解之间存在弱对偶性和强对偶性。

弱对偶性指的是对于原问题的任意可行解X和对偶问题的任意可行解Y，有C^T * X >= b^T * Y。

这意味着对于原问题的任意最优解X*和对偶问题的任意最优解Y*，有C^T * X* >=b^T * Y*。

强对偶性指的是如果原问题和对偶问题的任意一个都有有界解，那么它们必然存在一对最优解，使得C^T * X* = b^T * Y*。

对偶问题的解决可以通过使用单纯形法或内点法等优化算法来进行求解。

对偶问题对线性规划问题的求解具有重要的应用价值和理论意义。

它可以用于确定原问题的可行解的界限，还可以提供原问题的敏感性分析和稳定性分析。

总之，线性规划的对偶问题是通过对原问题的目标函数和约束条件进行变换而得到的，对偶问题为理解原问题的特性和提供附加信息提供了一种有力的工具。

用对偶单纯形法求解线性规划问题对偶单纯形法是一种常用于求解线性规划问题的方法。

它通过对原始线性规划问题进行对偶化，将原问题转化为对偶问题，并通过迭代的方式逐步优化，最终得到最优解。

本文将详细介绍对偶单纯形法的基本原理和步骤，并通过一个实例来演示其具体应用。

对偶单纯形法的基本原理是基于线性规划的对偶性理论。

根据对偶性理论，对于原始线性规划问题的最优解，一定存在一个对偶问题，其最优解与原问题的最优解相等。

因此，我们可以通过求解对偶问题来得到原问题的最优解。

对偶问题的形式如下：最大化 W = b'y约束条件为：A'y ≤ c其中，A是原始线性规划问题的约束矩阵，b是原始问题的目标函数系数矩阵，c是原始问题的约束条件矩阵，y是对偶问题的变量向量。

对偶单纯形法的步骤如下：步骤1: 初始化将原始线性规划问题转化为标准型，并初始化基变量和非基变量的初始解。

步骤2: 计算对偶变量值根据对偶问题的约束条件，计算对偶变量的初始值。

步骤3: 计算对偶目标函数值根据对偶问题的目标函数，计算初始的对偶目标函数值。

步骤4: 检验最优性判断当前解是否为最优解。

如果是，则终止算法；否则，进入下一步。

步骤5: 选择入基变量和出基变量根据当前解，选择一个入基变量和一个出基变量。

步骤6: 更新解通过列生成法或其他方法，更新当前解。

步骤7: 更新对偶变量和对偶目标函数值根据更新后的解，更新对偶变量和对偶目标函数值。

步骤8: 转至Step 4重复步骤4至步骤7，直到找到最优解。

下面以一个具体的线性规划问题为例来演示对偶单纯形法的应用。

假设有以下线性规划问题：最大化 Z = 3x1 + 5x2约束条件为：2x1 + x2 ≤ 10x1 + 3x2 ≤ 15x1, x2 ≥ 0首先，将原始问题转化为标准型：最大化 Z = 3x1 + 5x2约束条件为：2x1 + x2 + s1 = 10x1 + 3x2 + s2 = 15x1, x2, s1, s2 ≥ 0初始化基变量和非基变量的初始解为：x1 = 0, x2 = 0, s1 = 10, s2 = 15根据对偶问题的约束条件，计算对偶变量的初始值：y1 = 0, y2 = 0根据对偶问题的目标函数，计算初始的对偶目标函数值：W = 0检验最优性，发现当前解不是最优解，需要进入下一步。

对偶问题的原理和应用1. 对偶问题的概述对偶问题是线性规划领域的一个重要概念，它通过将原始问题转化为对偶形式，从另一个角度来解决问题。

对偶问题在优化领域有着广泛的应用，尤其在线性规划中起到了重要的作用。

2. 对偶问题的原理对偶问题的转化是基于线性规划的标准形式进行的。

假设我们有一个原始线性规划问题：最小化：c T x约束条件：$Ax \\geq b$ 变量约束：$x \\geq 0$其中，c是目标函数的系数向量，A是约束矩阵，b是约束条件的右侧常数向量。

对于原始问题，我们可以定义一个对偶问题。

对偶问题的定义如下：最大化：b T y约束条件：$A^Ty \\leq c$ 变量约束：$y \\geq 0$其中，y是对偶问题的变量向量。

对偶问题的目标函数和约束条件是原始问题的线性组合，并且满足一定的对偶性质。

3. 对偶问题的求解方法对偶问题的求解方法有两种：一种是通过求解原始问题得到对偶问题的最优解，另一种是通过求解对偶问题得到原始问题的最优解。

这两种方法都可以有效地解决线性规划问题。

3.1 原始问题到对偶问题的转换原始问题到对偶问题的转换可以通过拉格朗日对偶性定理来实现。

该定理表明，原始问题的最优解与对偶问题的最优解之间存在一种对偶性关系。

通过求解原始问题的对偶问题，我们可以获得原始问题的最优解。

3.2 对偶问题到原始问题的转换对偶问题到原始问题的转换可以通过对偶定理来实现。

该定理表明，对偶问题的最优解与原始问题的最优解之间存在一种对偶性关系。

通过求解对偶问题，我们可以获得原始问题的最优解。

4. 对偶问题的应用对偶问题在实际应用中具有广泛的应用，下面介绍几个常见的应用场景。

4.1 线性规划问题对偶问题在线性规划中得到了广泛的应用。

通过将原始问题转化为对偶形式，我们可以使用对偶问题的求解方法来求解线性规划问题。

对偶问题可以提供原始问题的最优解，并且可以帮助我们理解原始问题的性质和结构。

4.2 经济学和管理学对偶问题在经济学和管理学中也有重要的应用。

线性规划原问题与对偶问题的转化及其应用 Revised as of 23 November 2020线性规划原问题与对偶问题的转化及其应用摘要线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解.关键词：线性规划；原问题；对偶问题；转化LinearProgrammingistheOriginalProblemandtheTransformationoftheDualProblemandApplicationsAbstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandw ideapplication,themethodisanimportantbranchofmature,目录1引言线性规划问题是运筹学里的一个重要的分支，它的应用比较广泛，因而是辅助人们进行现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题则称为它的对偶问题.对偶性不仅仅是数学上的理论问题，而且也是线性规划中实际问题的内在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产计划进行分析，从而使管理者能够间接地获得更多比较有用的信息.2文献综述国内外研究现状在所查阅到的国内外参考文献[1-15]中，有不少文章是探讨了原问题转化为对偶问题的方法以及对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在[1]、[10]中主要介绍了线性规划中原问题与对偶问题中的一些基本概念，探究了实际问题中的数学模型以及解.孙君曼，冯巧玲，孙慧君，李淑君等在[2]中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷志祥等在[3]、[5]中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在[6]、[8]中用不同例子来说明了原问题转化为对偶问题的必要性.崔永新等在[9]、[15]中探讨了对偶问题的相关定理以及对偶问题的可行解和最优解之间的若干性质.李师正，王德胜在[11]中探讨了如何用计算机计算对偶问题的最优解.岳宏志，蔺小林，孙文喻等在[12]、[14]中探讨了对偶理论的证明过程，并用常见的例子来说明对偶理论的基本思想和解题方法.曾波，叶宗文在[13]中主要从经济管理的实际问题中阐述了线性规划的基本概念，基本原理，对偶理论，灵敏度分析等.国内外研究现状评价文献[1-15]分别探讨了线性规划问题中原问题转化为对偶问题的理论依据以及如何利用对偶理论去解决实际生产问题.文献中主要探讨了对称型的原问题转化为对偶问题的方法.没有全面介绍非对称型的原问题与对偶问题之间转化的具体步骤，而且文献中对原问题转化为对偶问题的步骤提及甚少，大都一带而过，对应用中存在的问题也未给出详细深入的说明.提出问题在线性规划问题中,根据实际生产中具体情况的需要,我们常常要把原问题与它的对偶问题进行转换,以解决一些复杂的线性规划问题,因而对偶问题的应用较为广泛.但大部分书籍都只介绍了线性规划问题的基础知识，并没有给出原问题与对偶问题转换的具体步骤.因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会不同类型原问题的转化过程.3预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些基本的知识.对称形式的原问题我们将满足下列条件的线性规划问题称之为具有对称形式的线性规划问题.这类问题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“≤”号，当目标函数求极小值时它的约束条件均取“≥”号.因而，这类数学模型的特点是：（1）所有的决策变量都是非负的；（2）所有的约束条件都是“≤”型；（3）目标函数是最大化类型.线性规划原问题的对称形式的]1[一般形式为：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+++≤+++≤+++),,2,1(0.22112222212111212111n j x bx a x a x a b x a x a x a b x a x a x a t s j mn mn m m n n n n非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件≥,=,≤；变量≥0,≤0，或是无限制的随意的组合.例如：⎪⎪⎩⎪⎪⎨⎧≤≥≤++=++≤++无约束321333323213123232221211313212111,0,0.x x x b x a x a x a b x a x a x a b x a x a x a t s 对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的]2[定义如下.设给定的线性规划为：⎩⎨⎧≥≤0.X bAX t s 其中()T n x x x X ,,,21 =，()n m ij a A ⨯=，()Tm b b b b ,,,21 =，()n c c c C ,,,21 =因此，定义它的对偶问题为：⎩⎨⎧≥≥0.Y CYA t s 其中()m y y y Y ,,,21 =是行向量.是对偶问题，是原问题，与合在一起我们就称为是一对对称形式的对偶规划问题.原问题转化为对偶问题的理论依据我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下]3[1表所示：表14原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有相同的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问题.原问题与对偶问题的关系一对对偶的线性规划问题具有相互对应的关系：（1）原问题中的目标函数值是max ，约束条件是“≤”的形式；对偶问题的min 目标函数值为，”约束条件是“≥的形式.（2）原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.（3）原问题的变量和对偶问题的约束条件对应，即，原问题中有个n 变量，那么对偶问题就有个n 约束条件；原问题有个m 约束条件，那么对偶问题就有个m 变量. （4）对偶问题的系数矩阵就是原问题的系数矩阵的转置. 用矩阵表示，原问题为： 则对偶问题为：需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.对称型原问题转化为对偶问题当线性规划问题为一般形式（）时，我们将根据下面的四条规则转换为它的对偶问题：（1）原问题和它的对偶问题之间的系数矩阵互为转置.（2）原问题中变量的个数等于它的对偶问题的约束条件的个数.（3）原问题的右端常数就是对偶问题的目标函数的系数.（4）原问题的目标函数求极大时，约束条件是“≤”类型，而它的对偶问题的目标函数求极小，约束条件则为“≥”类型.形式：因此，它的对偶问题可以转变为如下的]4[例1生产计划问题云南一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供应.已知制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表2所示.问题：云南的这家公司应该怎样制定每天的生产计划，才能使它的产量得到最大表2分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定达到目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大设1x 和分别表示该公司A ，B 产品的数量，用z 表示产值，则每天的产值表示为2115090x x z +=，使其最大化，即2115090m ax x x z +=，称为目标函数.将制约因素表达出来，即有：人力不超过320工时，为3206821≤+x x ；设备不超过260台时有，2608621≤+x x ；原材料不超过300公斤有，30010421≤+x x 。

线性规划中的对偶算法优化策略在线性规划中，对偶算法是一种常用的优化策略。

通过建立原问题和对偶问题之间的关系，对偶算法可以帮助我们更好地理解和解决线性规划问题。

本文将介绍线性规划中的对偶算法及其优化策略。

一、对偶问题的引入在线性规划中，我们常常面临的是最大化或最小化一个目标函数，同时满足一系列线性约束条件。

以最小化为例，我们的目标是找到使得目标函数取得最小值的变量取值，同时满足约束条件。

在线性规划问题中，我们可以建立原问题和对偶问题之间的对应关系。

对于一个最小化问题而言，我们可以通过引入松弛变量和拉格朗日乘子来构建与之对应的对偶问题。

具体而言，设原问题的约束条件为Ax≥b，目标函数为 f(x)，对应的对偶问题可以描述为：最大化g(λ) = min f(x) + λ^T(Ax-b)，其中λ≥0其中，λ是对偶变量，类似于原问题中的拉格朗日乘子。

对偶问题的求解可以通过最大化g(λ) 来得到。

二、对偶算法的优化策略对偶算法可以通过求解对偶问题来优化原问题。

下面将介绍几种常用的对偶算法优化策略。

1. 对偶单纯形法对偶单纯形法是对单纯形法在对偶问题上的拓展。

通过互补松弛性和非负约束性等性质，对偶单纯形法可以在对偶问题上进行迭代求解。

对偶单纯形法的基本思想是通过迭代调整对偶变量的取值，不断提高对偶问题的目标函数值，直至达到最优解。

通过对原问题和对偶问题的求解过程进行迭代，可以同时获得原问题和对偶问题的最优解。

2. 内点法内点法是一种常用的对偶算法，通过在可行域内部搜索最优解。

与单纯形法不同的是，内点法允许在可行域内部搜索，而不是只在极点上搜索。

内点法的基本思想是通过引入一个可行的初始点，并采用迭代的方式逐步逼近最优解。

在每一次迭代中，通过调整对偶变量的取值，将可行点推向可行域内部，直至达到最优解。

3. 半定规划半定规划是一种基于矩阵的对偶算法，适用于解决某些特殊类型的线性规划问题。

它将线性规划问题转化为半定规划问题，通过求解半定规划问题来得到线性规划问题的解。

线性规划原问题与对偶问题的转化及其应用摘要线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解.关键词：线性规划；原问题；对偶问题；转化Linear Programming is the Original Problem and the Transformation ofthe Dual Problem and ApplicationsAbstract: Linear programming in operational research is research earlier, rapid development and wide application, the method is an important branch of mature, it is one of the scientific management of auxiliary people mathematical method. Can from different angles to linear programming dual problem for policy makers to provide more scientific theory basis. This article mainly probes into the linear programming problem and the relationship between the dual problem, linear programming problem and the transformation of the dual problem, the application of linear programming dual problem. This article is the complex of the original problem into its dual problem to be solved, simplifies the linear programming problem, enables us to rapidly find the optimal solution of linear programming problem.Keywords: linear programming; the original problem; the dual problem; conversion目录1 引言 (1)2 文献综述 (1)2.1国内外研究现状 (1)2.2国内外研究现状评价 (2)2.3提出问题 (2)3 预备知识 (2)3.1对称形式的原问题 (2)3.2非对称形式的原问题 (3)3.3对偶问题的定义 (3)3.4原问题转化为对偶问题的理论依据 (4)4 原问题与对偶问题的转化 (5)4.1原问题与对偶问题的关系 (5)4.2对称型原问题化为对偶问题 (6)4.3对称型对偶问题转换为原问题 (9)4.4非对称型原问题转化为对偶问题 (10)4.5对偶问题的应用 (13)5 结论 (15)5.1主要发现 (15)5.2启示 (15)5.3局限性 (15)5.4努力方向 (15)参考文献 (15)1 引言线性规划问题是运筹学里的一个重要的分支，它的应用比较广泛，因而是辅助人们进行现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题则称为它的对偶问题.对偶性不仅仅是数学上的理论问题，而且也是线性规划中实际问题的内在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产计划进行分析，从而使管理者能够间接地获得更多比较有用的信息.2 文献综述2.1 国内外研究现状在所查阅到的国内外参考文献[1-15]中，有不少文章是探讨了原问题转化为对偶问题的方法以及对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在[1]、[10]中主要介绍了线性规划中原问题与对偶问题中的一些基本概念，探究了实际问题中的数学模型以及解.孙君曼，冯巧玲，孙慧君，李淑君等在[2]中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷志祥等在[3]、[5]中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在[6]、[8]中用不同例子来说明了原问题转化为对偶问题的必要性. 崔永新等在[9]、[15]中探讨了对偶问题的相关定理以及对偶问题的可行解和最优解之间的若干性质.李师正，王德胜在[11]中探讨了如何用计算机计算对偶问题的最优解.岳宏志，蔺小林，孙文喻等在[12]、[14]中探讨了对偶理论的证明过程，并用常见的例子来说明对偶理论的基本思想和解题方法. 曾波，叶宗文在[13]中主要从经济管理的实际问题中阐述了线性规划的基本概念，基本原理，对偶理论，灵敏度分析等.2.2 国内外研究现状评价文献[1-15]分别探讨了线性规划问题中原问题转化为对偶问题的理论依据以及如何利用对偶理论去解决实际生产问题.文献中主要探讨了对称型的原问题转化为对偶问题的方法.没有全面介绍非对称型的原问题与对偶问题之间转化的具体步骤，而且文献中对原问题转化为对偶问题的步骤提及甚少，大都一带而过，对应用中存在的问题也未给出详细深入的说明.2.3 提出问题在线性规划问题中,根据实际生产中具体情况的需要,我们常常要把原问题与它的对偶问题进行转换,以解决一些复杂的线性规划问题,因而对偶问题的应用较为广泛.但大部分书籍都只介绍了线性规划问题的基础知识，并没有给出原问题与对偶问题转换的具体步骤.因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会不同类型原问题的转化过程.3 预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些基本的知识.3.1对称形式的原问题我们将满足下列条件的线性规划问题称之为具有对称形式的线性规划问题.这类问题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“≤”号，当目标函数求极小值时它的约束条件均取“≥”号. 因而，这类数学模型的特点是：（1）所有的决策变量都是非负的；（2）所有的约束条件都是“≤”型；（3）目标函数是最大化类型.线性规划原问题的对称形式的]1[一般形式为：n n x c x c x c z +++= 2211m ax⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+++≤+++≤+++),,2,1(0.22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n (3.1)3.2 非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件；，或是无限制的随意的组合.例如：332211m ax x c x c x c z ++= ⎪⎪⎩⎪⎪⎨⎧≤≥≤++=++≤++无约束321333323213123232221211313212111,0,0.x x x b x a x a x a b x a x a x a b x a x a x a t s (3.2)3.3 对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的]2[定义如下.设给定的线性规划为：CX z =max⎩⎨⎧≥≤0.X b AX t s (3.2) 其中()T n x x x X ,,,21 =，()nm ij a A ⨯=，()T m b b b b ,,,21 =，()n c c c C ,,,21 = 因此，定义它的对偶问题为：Yb w =min⎩⎨⎧≥≥0.Y C YA t s (3.4) 其中()m y y y Y ,,,21 =是行向量. (3.4)是对偶问题，(3.3)是原问题，(3.3)与(3.4)合在一起我们就称为是一对对称形式的对偶规划问题.3.4原问题转化为对偶问题的理论依据我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下]3[1表所示：表14 原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有相同的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问题.4.1原问题与对偶问题的关系一对对偶的线性规划问题具有相互对应的关系：（1）原问题中的目标函数值是max ，约束条件是“≤”的形式；对偶问题的min 目标函数值为，”约束条件是“≥的形式.（2）原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.（3）原问题的变量和对偶问题的约束条件对应，即，原问题中有个n 变量，那么对偶问题就有个n 约束条件；原问题有个m 约束条件，那么对偶问题就有个m 变量.（4）对偶问题的系数矩阵就是原问题的系数矩阵的转置.用矩阵表示，原问题为：CX z =max⎩⎨⎧≥≤0..X b AX t s 则对偶问题为：Yb w =min⎩⎨⎧≥≥0..Y C YA t s 需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.4.2 对称型原问题转化为对偶问题当线性规划问题为一般形式（3.1）时，我们将根据下面的四条规则转换为它的对偶问题：（1）原问题和它的对偶问题之间的系数矩阵互为转置.（2）原问题中变量的个数等于它的对偶问题的约束条件的个数.（3）原问题的右端常数就是对偶问题的目标函数的系数.（4）原问题的目标函数求极大时，约束条件是“≤”类型，而它的对偶问题的目标函数求极小，约束条件则为“≥”类型.因此，它的对偶问题可以转变为如下的]4[形式：m m y b y b y b w +++= 2211m in⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥+++≥+++≥+++),,1(0..22112222211211221111n i y c y a y a y a c y a y a y a c y a y a y a t s i n m mn n n m m m m例1 生产计划问题云南一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供应.已知制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表2所示.问题：云南的这家公司应该怎样制定每天的生产计划，才能使它的产量得到最大？表2 分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定达到目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大？设1x 和2x 分别表示该公司A ，B 产品的数量，用z 表示产值，则每天的产值表示为2115090x x z +=，使其最大化，即2115090m ax x x z +=，称为目标函数.将制约因素表达出来，即有：人力不超过320工时，为3206821≤+x x ；设备不超过260台时有，2608621≤+x x ；原材料不超过300公斤有，30010421≤+x x 。