线性规划对偶理论

1、1.运筹学，陈志松，2。线性规划对偶理论，线性规划对偶理论概述。提出了线性规划的对偶问题。规范形式的线性规划对偶问题。一般形式的对偶问题。线性规划对偶问题的基本性质。线性规划对偶问题的经济学解释。3.线性规划对偶理论综述。自1947年提出以来，线性规划对偶理论取得了很大的进展，已经成为线性规划的一个重要基础理论。对偶理论是线性规划中最重要和最有趣的概念之一。支持对偶理论的基本思想是每个线性规划问题都有一个对偶问题。当我们找到一个问题的解时，我们也给出了另一个问题的解。线性规划的对偶问题和对偶理论中对偶定理的应用是线性规划的主要检验点。4。提出双重问题。提出双重问题。在提出对偶问题时，线性规划问

2、题LP1和LP2的表达式和系数之间有许多对应关系。我们称前者为原始问题，而后者是前者的双重问题。7，标准型对偶关系的一般形式，8，标准型对偶关系的一般形式，9，标准型原问题和对偶问题的变换规则，10，线性规划问题中对偶问题的一个例子，例3.1，写出下列线性规划问题的对偶问题，11，非标准形式的对偶关系，12，如何直接写出非对称对偶问题，13，如何直接写出非对称对偶问题。14、表3-1、表15，如何直接写出非对称形式的对偶问题，只要你记住规范形式的对偶关系和上面的规则，你就能准确、快速地写出对偶问题。16，例3.3写出下列线性规划的对偶问题。为了找到目标函数的最小值，表31的右侧应该被视为原始问

3、题，左侧是对偶问题。如果原问题有三个约束和四个变量，那么对偶问题有三个变量和四个约束，对偶问题是：=，=，y10，y20，y3，没有约束。对偶问题是(表示为DP):其中A是mn矩阵，X是n1列向量，Y是1m行向量。假设Xs和Ys分别是(LP)和(DP)的松弛变量。让原问题为(表示为LP):18，性质1对称对偶问题的对偶性是原问题。让原来的问题等价于下面的线性规划问题：然后写出它的对偶问题。这相当于下面的线性规划问题，也就是原来的问题。可以看出，它的双重问题是19。证明因为X和Y是可行解，所以有AXb，X0和YAC，Y0。如果不等式AXb和性质2中的弱对偶分别是LP(最大)和DP(最小)的可行解

4、，那么两边用Y相乘，得到Y0AXY0b。这个性质表明，当两个线性规划是对偶时，寻求最大值的线性规划的任何目标值都不会大于寻求最小值的线性规划的任何目标值，这不能理解为原问题的目标值不超过对偶问题的目标值。无界如果原问题(对偶问题)有无界解，那么它的对偶问题(原问题)就没有可行解。可以理解，在两个对偶问题中，如果一个问题是可行的并且有无界解，那么另一个问题就没有可行解。证明了原问题有无界解，对偶问题有可行解y和Yb。原来的问题有无界解，也就是说，存在C X。根据二元性存在的明显矛盾，这个命题成立。注：(1)这个定理的逆定理是无效的，即如果一个问题没有可行解，另一个问题可能没有无界解或可行解；(2

5、)如果原问题是可行的，而另一个问题是不可行的，那么原问题有无界解，21例如，没有可行解，而对偶问题有可行解，根据性质(3)，它必须是无界的。22，性质4最优性定理假设X0和Y0分别是(LP)和(DP)的可行解，那么当X0=Y0B时，X0和Y0是(LP)和(DP)的最优解。证明如果X0=Y0B，对偶问题的所有可行解Y都通过性质2存在。因为C X0=Y0b，所以Y b Y0b，可以看出Y0是使目标函数值最小的可行解，所以Y0是最优解。同样，X0是最优解，23。性质5弱对偶如果两个对偶问题中的一个有最优解，另一个有最优解，并且最优值是相同的。如果(LP)具有最优解X0，那么对于最优基b，即YAC和Y

6、0，必须有C-CBB-1A0和CBB-10，其中Y=CBB-1，所以Y是可行解，对于目标函数，Y是来自性质4的最优解。从性质5可以得出另一个结论：如果(LP)和(DP)都有可行解，那么两者都有最优解；如果一个问题没有最优解，另一个问题就没有最优解。24，例3.4证明下列线性规划没有最优解：证明很容易看出x=(4，0，0)是可行解，所以问题是可行的。在对偶问题中，三个约束的两端分别相加，第二个约束有y21，这是矛盾的，所以对偶问题没有可行解，所以原问题有无界解，即没有最优解。25，证明让X和Y成为最优解。根据属性4，X0=y0b，因为XS和YS是松弛变量，所以有一个X0XSb Y0AYS=C，第

7、一个公式是左乘以Y0，第二个公式是右乘以X0，y0ax0y0by0ax0=x0，26，很明显。相反，当YXS=0和YS X=0时，存在YA XYb YA X=C X，显然存在Y0b=C X，并且从性质4可知，y和X是(LP)和(DP)的最优解。证书已完成。27和性质6告诉我们，当我们知道一个问题的最优解时，如何找到另一个问题的最优解，也就是说，我们知道Y*找到X*或X*找到Y*。Y * XS=0和YS X *=0，它们被称为互补松弛条件。互补弛豫条件写成下面的公式。由于所有变量都是非负的，如果求和公式等于零，那么每个分量都必须为零，所以有以下关系：28，(1)当yi*0时，反之亦然，当Yi *

8、=0时；利用上述关系，建立对偶问题(或原问题)的约束线性方程组，方程组的解即为最优解。性质6的结论和证明假定(p)和(d)是对称形式。事实上，性质6的结论对于不对称形式仍然有效。例3.5众所周知，线性规划的最优解是找到对偶问题的最优解。对偶问题是因为X10和X20，对偶问题的第一和第二约束的松弛变量等于零，也就是说，当求解这个线性方程组时，y1=1，y2=1，因此对偶问题的最优解是Y=(1，1)，最优值是w=26。已知线性规划对偶问题的最优解是y=(0，2)，并且找到了原问题的最优解。解决方案双重问题是31。在求解方程组时，x 1=5，x 3=1 5，x 3=1，所以原问题的最优解是x=(5，

9、0，1)，最优值是Z=12。由于y20，原问题的第二个松弛变量是0，由Y1=0和y2=-2可知，松弛变量是x2=0，那么原问题的约束条件是线性方程组的测试数的相位：32，33，34，35，36，37，性质6互补对偶LP(max)。相反，(DP)的测试数(注意：不要乘以负号)对应于(LP)的一组基本解。省略了证明。38，例3.9线性规划，(1)用单纯形法寻找最优解；(2)写出每次迭代对应的对偶问题的基本解；(3)从最优表中写出对偶问题的最优解；解决方案 (1)添加松弛变量x4和x5后，单纯形迭代如表2-2所示。，39，表3-1，40，最优解X=(4，6，0)，最优值z=6426=12(2)设对偶变量为