当前位置：文档之家 › 第三章线性规划的对偶理论及灵敏度分析1总结

第三章线性规划的对偶理论及灵敏度分析1总结

  • 格式：docx
  • 大小：75.83 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

第三章 线性规划的对偶理论

第三章 线性规划的对偶理论

s.t. AX=b X≥0 由于 AX=b 即 AX=b
AX≤b AX≥b
AX≤b -AX≤-b 所以，原问题可化为 max z=CX s.t. AX≤b -AX≤-b X≥0
A
X≤ -A
b
-b
14
设Y'：AX≤b的对偶变量（行向量） Y''：-AX≤-b的对偶变量（行向量） 按对称形式的对偶关系可得出原问题的对偶问题如下： min w =Y'b-Y''b= （Y'-Y''）b （Yb=bTYT） s.t Y'A-Y''A≥C （ YA=ATYT） Y'≥0，Y''≥0 令Y= Y'-Y''，则对偶问题为 min w =Yb s.t YA≥C Y符号不限 结论：原问题中约束条件为等式，对应的对偶变量 无非负要求；反过来同样成立。
s.t. 2y1+ y2+ 4y3 ≥2
2y1+2y2+ 4y4 ≥3 y1, y2 , y3 , y4 ≥ 0
解：2.首先将原式变形
m axZ 2 x1 3 x 2 4 x 3 2 x 3 x 2 5 x 3 2 3 x1 x 2 7 x 3 3 x1 4 x 2 6 x 3 5 x1 , x 2 , x 3 0
对于非对称形式的规划，可以按照下面的对应关系直接给 出其对偶规划。 （1）对原问题模型为“max，约束条件为≤”或“min，约 束条件为≥” 的形式，对应的对偶规划的变量大于 0 ；反之， 若原问题模型为“max，≥”或“min，≤” 的形式，对应的 对偶规划的变量小于0。 （ 2 ）原问题线性规划的决策变量大于 0 ，则对偶问题的模 型为“max，约束条件为≤”或“min，约束条件为≥” 的形 式；若原问题线性规划的决策变量小于0；则对偶问题的模型 为“max，≥”或“min，≤” 的形式。

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第3章 对偶理论与灵敏度分析

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第3章 对偶理论与灵敏度分析

⎟ ⎟ ⎟⎟⎠
⎪⎩x1, x2 ,", xn ≥ 0
min z = b1y1 + b2y2 +" + bm ym
（3-5）
⎪⎧⎜⎛ s.t.⎪⎪⎪⎪⎨⎜⎜⎜⎜⎝
a11 a12 #
a1n
a21 a22 #
a2n
" "
"
am1 ⎟⎞⎜⎛ y1 ⎟⎞ ⎜⎛ c1 ⎟⎞
am2 #
amn
⎟⎜ y ⎟⎟⎟⎠⎜⎜⎜⎝#y
+ −
y3* =3 y3* = 4
把 X * 代入原问题 3 个约束中可知原问题式（3）是不等式，故 y 3 * =0，然后解方程组
得到
⎧⎪ ⎨ ⎪⎩
2y1* 3y1*
+ +
3y2* =3 2 y2* = 4
⎧⎪ ⎨ ⎪⎩
y1* =6/5 y2* = 1/ 5
故对偶最优解为 Y * =(6/5,1/5,0), z * =w * =28.
⎪⎪⎪⎨22yy11++3yy22
− +
y3 y3
≥2 ≥3
⎪⎪3y1 + 2 y2 − y3 ≥ 4
⎪⎩y1, y2 , y3 ≥ 0
由于 x 3 * =x 4 * =4>0，故对偶问题约束方程式（3）、（4）是等式约束，即对 Y * 成立等式
⎧⎪ ⎨ ⎪⎩
2y1* 3y1*
+ +
3 y2* 2 y2*
推论 3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。
定理 3.2 最优性准则定理
若 X 和 Y 分别为互为对偶问题的线性规划（3-5）与（3-6）的可行解，且使 CX = bT Y T ，

3对偶理论与灵敏度分析解析

3对偶理论与灵敏度分析解析
X ≥0
对偶的定义 min W= Y b s.t. ATY ≥ C
Y≥0
min Z’= - CX
max W’ = -Yb
s.t. - AX ≥ - b
s.t. -ATY ≤ -C
X ≥0 对偶的定义
Y≥0
__
__
（2）弱对偶性：设 X和 分Y 别是问题（P）和（D）的
可行解，则必有
__ __
n
m
C X Y b, 即 c j x j yibi
i 1
m
aij yi
c j ( j 1,2,, n)
i1
yi无符号限制（无约束）(i 1,2,, m)
例： 原问题为
max Z 2 x1 3 x2 4 x3
2 x1 3 x2 5 x3 2
3
x1
x2
7 x3 3
x1 4 x2 6 x3 5
x1 , x2 , x3 0
对偶问题的无界性。
无界
关于无界性有如下结论：
minW 4 y1 2 y2
原问题 问题无界
对偶问题 无可 行解
（D）
y1 y1
y2 y2
2 1
y1
0,
y2
0
无可 行解
问题无界
无可 行解
推论3：在一对对偶问题（P）和（D）中，若一个可行 （如P），而另一个不可行，（如D），则该可行的问 题无界。
一、问题的提出
• 对偶是什么：对同一事物（或问题），从不同 的角度（或立场）提出对立的两种不同的表述。 • 在平面内，矩形的面积与其周长之间的关系， 有两种不同的表述方法。 （1）周长一定，面积最大的矩形是正方形。 （2）面积一定，周长最短的矩形是正方形。 • 这种表述有利于加深对事物的认识和理解。 • 线性规划问题也有对偶关系。

对偶问题与灵敏度分析

对偶问题与灵敏度分析
②告诉经营者以怎样的代价去取得紧缺资源。 ③提示设备出租或原材料转让的基价。 ④告诉经营者补给紧缺资源的数量，不要盲目大量补给。 ⑤借助影子价格进行内部核算。
第一讲 对偶理论
解释例1的对偶问题的数学模型
Max Z= 3x1 +5 x2
x1
≤8
S.t.
2x2 ≤12 3x1 +4 x2 ≤36
x1 , x2 ≥0
第一讲 对偶理论
一、对偶问题
• 对原企业而言，它用于出租或转让的资源收益不应 低于自行生产产品所获得的利润，才肯出租或转让。
• 在这个问题上厂长面临着两种选择：自行生产或出 租设备。首先要弄清两个问题：
①如何合理安排生产，取得最大利润? ②为保持利润水平不降低，资源转让的最低价格是多少？
• 问题 ①的最优解：x1=4，x2=6，Z*=42。
(3) 按照θ=Min{j /alj | alj<0 }= k /alk确定xk进基变量。 (4) 以alk为主元素，按单纯形法的方法进行迭代，得到新的表重复
(2).
第一讲 对偶理论
例题：使用对偶单纯形法
• Min W= 8y1+12y2+36y3
y1 + 0y2 + 3y3 ≥ 3 S.t. 0y1 + 2y2 + 4y3 ≥ 5
此时，同时达到最优解
j 1
i 1
Z bi
*

yi*
bi为第i种资源的拥有量
• 说明yi是右端项bi每增加一个单位的第i种资源对目标函数Z的贡献。 • 对偶变量 yi在经济上表示原问题第i种资源的边际价值。
• 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。

对偶理论与灵敏度分析

对偶理论与灵敏度分析
对偶理论与灵敏度分析
第三章 对偶理论与灵敏度分析
第一节 对偶问题的提出
例：常山机械厂生产Ⅰ和Ⅱ两种产品。生产中需使用A、B、C三种设备进行加工，加工每件Ⅰ产品或Ⅱ产 品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生 产Ⅰ和Ⅱ产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。
4x1 +2x2 - x3 20 y2 x1，x2 ， x3 0 解：该问题的对偶问题： min w = 10 y1 + 20 y2 s.t. y1 + 4y2 10
y1 + 2y2 1 2 y1 - y2 2
y1，y2 0
第一节 对偶问题的提出
例：写出下列线性规划问题的对偶问题 min w = x1 + 2x2 + 3x3
解：化为对称形式。 令 x2 x2，x3 x3 x3 (x3 0, x3 0) max z c1x1 c2x2 c3x3 c3x3
s.t. a11x1 a12x2 a13x3 a13x3 b1
aaa222a111xxx2111x1 aaa222a222xx2x2222x2 aaa222a333xxx23333x3 aaa222a333xxx23333x3 bbb222b2 a3a13x11x1 a3a23x22x2 a3a33x33x3 a3a33x33x3 b3b3 x1, x2 , x3, x3 0
a21x1 + a22x2 + … + a2nxn ≤ b2 ……
am1x1 + am2x2 + … + amnxn ≤ bm xj ≥ 0 （j = 1,2,…,n）
则称下列 LP 问题
min w = b1 y1 + b2 y2 + … +bm ym s.t. a11y1 + a21 y2 + … + am1ym ≥ c1

第三章 对偶理论及灵敏度分析

第三章 对偶理论及灵敏度分析

灵敏度分析 —图解法
2x1 + x2 = 400
上页 下页 返回
C B D
（斜率为0） x2 = 250
x1 + x2 = 300
（斜率为-1）
A
| E | | | 100 200 300 400
x1
对 偶 问 题
分析资源系数b的改变产生的影响
Max Z = 50 x1 + 100 x2 x1 + x2 ≤ 310 2 x1 + x2 ≤ 400 x2 ≤ 250 x 1、 x 2 ≥ 0
上页 下页 返回
对 偶 问 题
► 问题：
上页 下页 返回
当这些系数中的一个或多个发生变化 时，原最优解会怎样变化？ 当这些系数在什么范围内变化时，原 最优解仍保持不变？ 若最优解发生变化，如何用最简单的 方法找到现行的最优解？
► 研究内容：
对 偶 问 题
研究线性规划中， aij , bi , c j 的 变化对最优解的影响。
上页 下页 返回
1
min w = 15 y + 24 y + 5 y
2
3
Ⅰ 设备A 设备 设备B 设备 调试工序 利润（ 利润（元） 0 6 1 2
Ⅱ 5 2 1 1
D 15时 时 24时 时 5时 时
对 偶 问 题
原 问 题
m z = 2x1 + x2 ax s.t. 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1, x2 ≥ 0
设备A 设：设备A —— 设备B 设备B –––– 调试工序 ––––
y1元／时 y2元／时 y3元／时
付出的代价最小， 付出的代价最小， 且对方能接受。 且对方能接受。

第三章对偶理论

右边项的系数对应目标 函数系数 约束条件个数 n 变量个数 m 约束条件类型
目标函数系数与右边项 目标函数各变量系数对应 的对应关系 约束条件右边项的系数 变量个数与约束条件个 变量个数 n 数的对应关系 约束条件个数 m
原问题变量类型与对偶 问题约束条件类型的对 变量类型 应关系
原问题约束条件类型与 对偶问题变量类型的对 约束条件类型 应关系
原始问题有4个变量，3个约束，对偶问题应该有3个变量， 4个约束。根据定义，对偶问题为：
x1 x2 x3 x4
非对称形式的对偶—原始问题有“=”约束
max z=2x1+3x2-x3
s.t. x1+2x2+x3=6 2x1-3x2+2x3≤9
x1, x2, x3≥0
min w=6y1+9y2 s.t. y1+2y2 ≥ 2 2y1- 3y2 ≥ 3 y1+2y2 ≥ -1 y1:Free y2≥0
y1=w2-w1,y1:Free,y2=w3
如果原始问题中一个约束是等号约束，则对偶问题中相应的变 量没有符号限制
非对称形式的对偶—原始问题有“≥”约束
max z=2x1+3x2-x3 s.t. x1+2x2+x3 ≥ 6 2x1-3x2+2x3≤9 x1, x2, x3≥0 max z=2x1+3x2-x3
s.t. -x1-2x2-x3≤-6 2x1-3x2+2x3≤9 x1, x2, x3≥0 min w=-6y1’+9y2 s.t. -y’1+2y2≥2 -2y’1 -3y2≥3 -y’1+2y2≥-1 y’1, y2≥0
min w=6y1+9y2 s.t. y1+2y2≥2 2y1- 3y2≥3 y1+2y2≥-1 y1≤0, y2≥0

第三章 线性规划的灵敏度分析和最优解的解释

3
3.1 灵敏度分析简介
灵敏度分析是研究线性规划的参数(非可控输入)发生 变化对最优解的影响程度
线性规划的参数包括：
• 目标函数系数 • 约束条件右侧值 • 约束条件系数矩阵
最优解中包含的信息：
• 目标函数值 • 决策变量值 • 递减成本(reduced cost) • 松弛/剩余变量
4
3.1 灵敏度分析简介
利用Lingo 软件做灵敏度分析
16
17
利用Excel做灵敏度分析
Microsoft Excel 16.0 敏感性报告 工作表: [数据模型与决策第3章例题.xlsx]第三章例题1 报告的建立: 2021/5/29 10:48:56
可变单元格
单元格 $B$15 $C$15
名称 决策变量值 x1 决策变量值 x2
作者
John Loucks
St. Edward’s University
1
第三章 线性规划的灵敏度分析和最优解的解释
3.1 灵敏度分析简介 3.2 目标函数系数变化的分析 3.3 约束条件右端值变化的分析 3.4 传统灵敏度分析的局限性
2
第三章 线性规划的灵敏度分析和最优解的解释
3.1 灵敏度分析简介 3.2 目标函数系数变化的分析 3.3 约束条件右端值变化的分析 3.4 传统灵敏度分析的局限性
6
x1 < 6
2x1 + 3x2 < 19 x1 + x2 < 8
x1, x2 > 0
固定x2的系数7，改变x1 的系数
5
最优解:
Max 14/3x1 + 7x2
4
x1 = 5, x2 = 3
3
Max 7x1 + 7x2

第3章线性规划的灵敏度分析


又获得了10个小时的切割与印染时间，我 们可以扩展问题的可行域，如图3-3所示。可 行域变大了，现在我们考虑是否有新的解会使
目标函数值更大。运用图解法可以看出，极点 S=527.5，D=270.5是最优解点。新的目标函数 值为10×527.5 + 9×270.5=7711.75美元，比原 来利润增加了7711.75 – 7688.00=43.75美元。 因此，利润的增加率为43.75/10=4.375美元/小 时。
在式（3-2）中，我们计算出只要满足 下列条件，极点③仍然是最优点
如果CS升高到13美元，同时使CD降低到8美 元，新的目标函数斜率将变成
由于这个值要小于下限，因此当前的解 S=540,D=252不再是最优的。把CS=13，CD =8代入，可得出极点②是新的最优解。
观察最优范围，我们得出结论，无论是
（3-2） 为了计算标准袋利润最优的范围，我们 假设高级袋的利润CD＝9，代入式（3-2）， 我们得到： 从左边的不等式，我们得到
因此
从右边的不等式，我们得到
因此， 综合标准袋利润CS的极限，标准袋利润最优 范围为：
6.3≤CS≤13.5
在最初Par公司的问题中，标准袋的利润 是10美元。最优解是540个标准袋和252个高级 袋。标准袋利润CS的最优范围告诉Par公司的 管理者：在其他系数不变的情况下，只要标准 袋的利润在6.3美元与13.5美元之间，540个标 准袋和252个高级袋总是最优产量。然而值得 注意的是，即使产量不变，总的利润也可能由 于每一个标准袋利润的变化而变化。
灵敏度分析还可以用来分析模型中的系
数哪个更能左右最优解。比如，管理层认为 高级袋的利润9美元只是一个估计量。如果 通过灵敏度分析得到，当高级袋的利润在 6.67美元与14.29美元之间变化时，模型的最 优解都是540个标准袋和252个高级袋，那么 管理层就必须思考每个高级袋获利9美元这 个估计量的可信程度有多大了。管理层希望 知道如果高级袋的利润下降，最优产量会怎 样变化。

(整理)第三章 线性规划的对偶理论及灵敏度分析

精品文档第三章 线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质； 2、对偶单纯形法；3、灵敏度分析。

重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方法。

要 求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。

§1 对偶问题的对称形式一、对偶问题引例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及A 、B 两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？解：设1x 、2x 分别为甲、乙两种产品的产量则目标函数2132m ax x x z +=约束条件 ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0,12416482212121x x x x x x(1)假设该工厂决定不再生产甲、乙产品，而将其出租或出售。

这时要考虑每种资源的定价问题，设321,,y y y 分别为出租单位设备台时的租金和出让单位原材料A 、B 的附加额。

作一比较：若用一个单位台时和4个单位原材料A 生产一件产品甲，可获利2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。

即：2421≥+y y同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。

即：精品文档34231≥+y y将工厂所有设备台时和资源都出租和出让，其收入为32112168y y y ++=ω对工厂来说，ω越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足≥所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。

为此，得到如下模型：32112168m in y y y ++=ω⎪⎩⎪⎨⎧=≥≥+≥+3,2,1,0342243121j y y y y y j(2)我们就称(2)为模型(1)的对偶问题。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第三章线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质；2、 对偶单纯形法；3、 灵敏度分析。

重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方 法。

要求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。

§ 1对偶问题的对称形式一、对偶问题弓侧，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及 A 、B 两种原材料的消耗，该工厂每生产一件产品甲可获利 2元，每生产一件产品乙可获利 3元，问应如何安排计划才能使该工厂获利最多？解：设X i 、X 2分别为甲、乙两种产品的产量作一比较：若用一个单位台时和 4个单位原材料 A 生产一件产品甲，可获利 2元，那么生产每件产品甲的设备台 y^ 4y^ 2同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。

即:2力 4y 33将工厂所有设备台时和资源都出租和出让，其收入为则目标函数maxz 二2x 「3x 2x 「2x 2 岂8i4x 1 - 16 i4x 2 兰12约束条件-x 1,x^ 0(1)不再生产甲、乙产品，而将其出租或出售 3分别为出租单位设备台时的租金和出让单位原材料这时要考虑每种资源的定价问题，设A 、B 的附加额。

时和原材料出租和出让的收入应不低于生产一件甲产品的利润。

即:。

=8y 〔+ 16y 2 + 12y 3对工厂来说，••越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足》所有产品的利润前提下, 使其总收入尽可能小，才能实现其愿望。

为此，得到如下模型：min =8y 1 16y 212y 3"+4丫2工 2< 2y i +4y ^ 3 J j > 0 , j =1,2,3我们就称（2）为模型（1）的对偶问题。

一般地，设原问题为max z = c/ c 2x 2 ……c x n'a ii X i +a i2X 2 + … +amX n 兰 b a 2l X l +a 22X 2 +■八 +a 2n X n 兰 b 2a a a a ■■■■■s■■■■a mi Xi +a m2X2 +*a mn X n 兰 *X j _0 , j =i,2, ,n则其对偶问题为：min 二 by b ?y 2^^nNiy i +a 2〃2 + …+a mi y m A"a i2yi +a 22y2 * +a m2ym ®C 2m- a - < ■■■■a inyi +a 2ny2 + +a mnym ®C ny i 一0 , i =i,2, ,m矩阵形式：原问题 对偶问题max z = cX mi n = Yb'AX E b , 、Y A 启C （实际为A T y T ^C T ）X >07 >0、原问题与对偶问题的关系例1求下列问题的对偶问题min z =2x1 3x2- 5x3x4x1 +x2-3x3 +x4 >52x1+2x3—x4兰41x2+x3+ x4=6捲_ 0, x2, x3- 0, x4无约束解：max = 5y! 4y26y3» +2y2 3 2y i *3 兰3«—3% +2y? +y3 兰一5y i -丫2*3=1y i -0』2空0小无约束§ 2对偶问题的基本性质、对称性：对偶问题的对偶是原问题。

证：设原问题为max z 二cXi X 0mi n = Yb则其对偶问题为：YA_ Ci y 0-min 二-Yb对上式两边取负号，得YA C1y0-max(-代)= min wmax(-⑷)=_Yb-YA-JCY -0上式的对偶问题为min(v)=CX-AXJ--bX-0(两边同取负号)-min(- v)二maxv maxv 二CX 二maxzAX bX 0(0)(0) cX (0)：：Y(°)b二、弱对偶性：若X 是原问题的可行解，Y 是对偶问题的可行解，则存在CX 一丫b。

(0)证：X 是原问题的可行解同理Y(0)A— C，用X(0)右乘之得丫(0)AX(0)一CX(0)已知Y (0)是对偶问题的可行解，用Y(0)左乘上式得Y (0)AX(0)二Y(0)bCX (0) ’ Y (0)AX (0)’ 丫⑼b ,故CX (0X Y (0)b三、 无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。

注意：此性质不可逆。

(0) (0)四、 可行解是最优解时的性质最优性：设X是原问题的可行解，Y是对偶问题的可行解，当(0) . (0) (0) (0)CX - 丫 b 时，X 、丫是最优解。

五、 对偶定理(强对偶性)：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。

反之，若其一 无最优解，则另一也无最优解。

(0)(0) (0)、 ^六、 互补松弛性：若X 、Y分别是原问题和对偶问题的可行解，那么Y X s 二0和二 YAX YX s若Y s X (0)= 0, 丫(0)X s 二 0 ；则 Y (0)b 二 Y (0)AX(0)二CX (0)(0) (0)由性质4知，X 、 Y为最优解。

又如果X(0)、丫(0)为原问题和对偶问题的最优解，由性质4有CX (0)= Y (0)AX (0)= Y (0)b 即Y (0)AX (0)-Y s X (0)= 丫⑼AX (0)= Y (0)AX (0)Y (0)X s必有Y s X (0) = 0，丫(0)X s =例2已知线性规划问题(0) (0)Y S X 0，当且仅当X证：设原问题和对偶问题的标准型是max z CXAX X s = b X,X s - 0将C 二 YA - Y s , b 二 AX(0)Y 为最优解。

mi n =YbYA- Y s 二 C Y,Y s - 0X s 分别代入原问题和对偶问题目标函数得maxz= x「x2捲 + x 2 + X 3 兰2 r2x< x 2 x 3 ' 1 X i , X 2, X 3试用对偶理论证明上述线性规划问题无最优解。

上述问题的对偶问题为min 二 2y 「y 2-y< 2y^ 1 y 「y 2 - 1 yi - y^ 0 y i , y^ 0由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。

七、对偶问题的经济解释----影子价格由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有求z 对b 的偏导数得:其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。

i 的值代表对第i 种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影 子价格”。

影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该 资源用于扩大生产；而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。

可见，影子价格对证：原问题存在可行解，如(0,0,0)Tz cX ⑼二 丫⑼b 二y 10)b iy 20)b 2（0）y：z （0）石，y 2(0)，y mb m*即y i*■:z b i§ 3对偶单纯形法—、基本思路对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。

首先讨论这样一个问题：min 二 Yb; YA 丫眇 c; Y,Y s 0设B 是原问题的一个可行基，于是 A=(B|N)，原问题可改写为：maxz 二 C B X B C N XBX B NX N X s = b &B ,X N ,X s = 0相应地对偶问题可以表示为minmin 二 YbY B 飞=C B ................. (1) Y N - Ys^ = C N .. (2)丫,丫0,丫5 - 0这里Y s = (Yd%)Y$ ----对应原问题中基变量 X B的剩余变量市场有调节作用。

Ys 2 ----对应原问题中非变量X N 的剩余变量设原问题: maxz=cX; AX 空 b, X - 0则其对偶问题：min=Yb; YA - c; 丫- 0化为标准型：max zcX; AX X sb;X,X s 0C B B 1。

现当求得原问题的一个基解X B二B’b，其相应的检验数为C N一C B B 1N与一分析这些检验数与对偶问题的解之间的关系：，1代入⑴、(2)得令Y = C B BY S^ 0飞=C N C B B1N由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：说明：在单纯形表中若在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。

根据对偶问题的对称性，可这样考虑：若保持对偶问题的解是基可行解，即C j -C B B」P j乞0，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最优解。

方法是：设原问题maxz=CX；AX =bX艺0设B是一个基，令B =(Ph，P2,…,P m)，它对应的变量为X B=(为公2,…,X m)T当非基变量都为零时，可以得到X B=B，b，若在B4b中至少有一个负分量，设2北)「：：0，并且在单纯形表的检验数行中的检验数都为负值，即对偶问题保持可行解，它的各分量是：1. 对应基变量x1, x2 / ,x m的检验数是-^c^C B B4P i =0, i =1,2, ,m2. 对应非基变量x m 1,x m -2/' ,x n的检验数是：■j =C j -C B B P j g j 二m 1,m 2, ,n每次迭代是将基变量中的负分量X l取出，去替换非基变量中的X k，经基变换，所有检验数仍保持负值，原问题逐步由非可行解向可行解靠近，当原问题得到可行解时，便得到了最优解。

二•计算步骤(1) 列出初始单纯形表，若所0，‘ j ' 0，则停止计算，已得到最优解。

若b中含有负元素，有b ■则需继续计算。

⑵确定换出变量叫门{( B b)i (B b)i < 0} = (B b)i ，基变量X |为换出变量。

(3)确定换入变量检查X |行的系数aj ,若所有a ij > 0,则无可行解，停止计算。

若存在 3|j <0,则继续计算。

(4)以 a lk 为主元素进行取主变换。

例3、用对偶单纯形法求解。

min z = 2x 「3x 2 4x 3x 「2X 2 X 33 r2x< x 2 3X 3 4x i , X 2, X 3解：化为标准型max z 二 2x< 3x 24x 3maxz 二 -2捲 - 3x 2 - 4x 3 0x 4 0x 5-- 2x 2 - x 3兰-3l2x 「x 23x 3 '4 心X 2, X 3— Y — O Y — Y + w 兰 —O12342x 「x 23x 3 x 5'4 X j - 0 ,厂 1,2, ,5I 貯,日9 =min t 一 按"规则， ja,,ijIf Io<_ka ，非基变量x k 为换入变量。