§1对偶问题 对偶理论是线性规划的内容之一。任何一个线性 规划都有一个伴生的线性规划,称之为原规划的对偶 规划问题。下面通过实例引出对偶问题,然后给出对 偶线性规划的定义。 第一章例1提出的线性规划问题为:某工厂生产I、 Ⅱ两种型号计算机,每生产一台I型和Ⅱ型计算机所 需的原料、工时和提供的利润以及资源的限制量如下 表: 资源 产品 I 总量 原料 2 3 100 工时 4 2 120 利润 6 4 试确定获利最大的生产方案
§1 对偶问题 对偶理论是线性规划的内容之一。任何一个线性 规划都有一个伴生的线性规划,称之为原规划的对偶 规划问题。下面通过实例引出对偶问题,然后给出对 偶线性规划的定义。 第一章例1提出的线性规划问题为:某工厂生产Ⅰ、 Ⅱ两种型号计算机,每生产一台Ⅰ型和Ⅱ型计算机所 需的原料、工时和提供的利润以及资源的限制量如下 表: 试确定获利最大的生产方案。 资源 产品 Ⅰ Ⅱ 总 量 原 料 工 时 2 3 4 2 100 120 利 润 6 4
该问题的线性规划数学模型为: maxZ=6x +4x 2x1+3x,≤100 4x1+2x2≤120 X1,X2≥0 假如现在工厂自己不生产产品I、Ⅱ,而将可利用的资源都出 让给其它企业,试确定这些资源的最低可接受价格。最低可接受价 格是指按这种价格转让资源比自己生产产品I、Ⅱ合算的价格。 设yy,为这两种资源的价格,为了使工厂出让资源合算,显然 应该使出让原来生产一台产品I的资源所得收入不低于自己生产十 台产品I的利润,即2y,+4y≥6 对于产品Ⅱ,同样可以建立类似的约束条件3y+2y2≥4 显然在满足这两个约束的前提下,价格越高,该工厂越合算,但价 格太高,接受方面又不会愿意购买。因此,我们需要确定的价格是 使工厂合算的最低价格,故应建立目标函数: minW=100y1+120y2
该问题的线性规划数学模型为: maxZ=6x1+4x2 2x1+3x2 ≤100 4x1+2x2 ≤120 x1 ,x2 ≥0 假如现在工厂自己不生产产品Ⅰ、Ⅱ,而将可利用的资源都出 让给其它企业,试确定这些资源的最低可接受价格。最低可接受价 格是指按这种价格转让资源比自己生产产品Ⅰ、Ⅱ合算的价格。 设y1 ,y2为这两种资源的价格,为了使工厂出让资源合算,显然 应该使出让原来生产一台产品Ⅰ的资源所得收入不低于自己生产一 台产品Ⅰ的利润,即 2y1+4y2 ≥6 对于产品Ⅱ,同样可以建立类似的约束条件 3y1+2y2 ≥4 显然在满足这两个约束的前提下,价格越高,该工厂越合算,但价 格太高,接受方面又不会愿意购买。因此,我们需要确定的价格是 使工厂合算的最低价格,故应建立目标函数: minW=100y1+120y2
综上所述,出让资源问题的数学模型如下: minW=100y,+120y2 maxZ=6x +4x2 2y1+4y2≥6 2x1+3x2≤100 3y1+2y2≥4 4x1+2x2≤120 y1y2≥0 X1,X≥0 工厂决策者所面临的两个问题的数学模型都是线性规划,它们 在结构上具有某种对称性,称后一个线性规划为原规划的对偶问题。 定义称线性规划 minW-Yb D YA≥C Y≥0 其中Y=-(y1,y2,yn) 为原线性规划 maxZ=CX (L) AX≤b X≥0 的对偶规划问题
综上所述,出让资源问题的数学模型如下: minW=100y1+120y2 2y1+4y2 ≥6 3y1+2y2 ≥4 y1 ,y2 ≥0 工厂决策者所面临的两个问题的数学模型都是线性规划,它们 在结构上具有某种对称性,称后一个线性规划为原规划的对偶问题。 maxZ=6x1 +4x2 2x1+3x2 ≤100 4x1+2x2 ≤120 x1 ,x2 ≥0 定义 称线性规划 minW=Yb (D) YA≥C Y≥0 其中Y=(y1 ,y2 ,…,yn) 为原线性规划 maxZ= CX (L) AX≤b X≥0 的对偶规划问题
§2对偶理论 本节将深一步讨论线性规划的对偶问题的性质。 性质1(对称性)对偶问题(D)的对偶是原问题(L)
§2 对偶理论 本节将深一步讨论线性规划的对偶问题的性质。 性质1(对称性) 对偶问题(D)的对偶是原问题(L)
性质2若原问题第个约束为等式,则其对偶问题 中第个变量为自由变量;反之,若原问题的第个变量 是自由变量,则其对偶问题的第个约束为等式
性质2 若原问题第i个约束为等式,则其对偶问题 中第i个变量为自由变量;反之,若原问题的第j个变量 是自由变量,则其对偶问题的第j个约束为等式
线性规划的原问题与对偶问题的变换规则表: 原问题(或对偶问题 对偶问题(或原问题 目标函数maxZ 目标函数minW 价值系数 资源系数 资源系数 价值系数 行约束的个数为m 对偶变量的个数为m 第个行约束取“冬” 第i个变量y≥0 第个行约束取“=” 第个变量y无限制 原变量的个数为n 行约束的个数为n 第j个变量x≥0 第个行约束取“” 第k个变量x无限制 第k个行约束取
原问题(或对偶问题) 对偶问题(或原问题) 目标函数 maxZ 价值系数 资源系数 目标函数 minW 资源系数 价值系数 行约束的个数为m 第i个行约束取“≤” 第ι个行约束取“=” 对偶变量的个数为m 第i个变量yi ≥0 第ι个变量yι无限制 原变量的个数为n 第j个变量xj ≥0 第k个变量xk无限制 行约束的个数为n 第j个行约束取“≥” 第k个行约束取“=” 线性规划的原问题与对偶问题的变换规则表: