当前位置：文档之家 › 运筹学胡运权第五版课件(第二章)

运筹学胡运权第五版课件(第二章)

  • 格式：ppt
  • 大小：1.45 MB
  • 文档页数：55

下载文档原格式

  / 55

合集下载

运筹学胡运权第五版课件

运筹学胡运权第五版课件

V5 12 7
5
4
3
2
0
1 3
1
0 4
3
4 0
v7 ∞ 10 10 8
⑶ 构造任意两点间最多可经过3个中间点到达 的最短距离矩阵 D（2）= dij（2） 其中 dij（2）= min { dir（1）+ drj（1）}
r
i
dir
（1）
r
drj（1）
j
v1 v2 v3 v4 v5 v6 v7
• • •
悬挂边 孤立点 偶点 奇点
悬挂点的关联边，如 e8 次为0的点 次为偶数的点，如 v2 次为奇数的点, 如 v5
5、链：图中保持关联关系的点和边的交替序列，其 中点可重复，但边不能重复。 路：点不能重复的链。 圈：起点和终点重合的链。 回路：起点和终点重合的路。 连通图：任意两点之间至少存在一条链的图。 完全图：任意两点之间都有边相连的简单图。 n(n 1) 2 n阶完全图用Kn表示，边数= C n
狄克斯屈拉算法
既可以求两点之间的最短 距离，又可以确定最短路
求某两点之间的最短距离
（0）= V2 D
5
2
∞ ∞ ∞ ∞
5
0
∞ 2
7 0 2 7
7
6
∞ ∞
∞ ∞ 2
V3 2
∞ 0
∞ 4
V4 ∞ 2
V5 ∞ 7
∞ 6
0
1
1
0 6
3
6 0
V6 ∞ ∞ 4
v7 ∞ ∞ ∞ ∞ 3
注意：D(0)是一个对称矩阵，且对角线上的元素全是0.
⑵ 构造任意两点间直接到达、或者最多经过1 个中间点到达的最短距离矩阵D（1）= dij（1） 其中

运筹学PPT完整版胡运权

运筹学PPT完整版胡运权

C
m n
基可行解：满足变量非负约束条件的基本解，简称基可
行解。
可行基：对应于基可行解的基称为可行基。
可 行 解
非可行解
基解
基可行解
线性规划问题的数学模型
例1.4 求线性规划问题的所有基矩阵。
Page 30
解: 约束方程的系数矩阵为2×5矩阵 r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即
运筹学的历史
“运作研究(Operational Research)小组”:解决复 杂的战略和战术问题。例如：
1. 如何合理运用雷达有效地对付德军德空袭 2. 对商船如何进行编队护航，使船队遭受德国潜
艇攻击时损失最少； 3. 在各种情况下如何调整反潜深水炸弹的爆炸深
度，才能增加对德国潜艇的杀伤力等。
Page 4
线性规划问题的数学模型
约束方程的转换：由不等式转换为等式。
aij x j bi
aij x j xni bi
xni 0 称为松弛变量
aij x j bi
aij x j xni bi
xni 0 称为剩余变量
变量 x j 的变0换 可令 xj x，j 显x然j 0
Page 23
用 x3 x3 替换 x3 ，且 x3 , x3 0
线性规划问题的数学模型
Page 25
(2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4， x4≥0,化为等式；
(3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5， x5≥0；
(4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右 端常数项化为正数；
x
v a 2x2 x a dv 0 dx
2(a 2 x) x (2) (a 2 x)2 0

《运筹学教程》胡云权 第五版 运筹学--线性规划--2单纯形法

《运筹学教程》胡云权 第五版 运筹学--线性规划--2单纯形法

x1, x2, …, xn ≥ 0
其中bi ≥0 ，i = 1, 2, …, m
右端项非负
线性规划的求解方法——图解法
Max Z= x1 + 2 x2 2 x1 + 2 x2 ≤ 8 2 x1 + 2 x2 = 8
4
Z=6 3
最优解：x1=2, x2=2
最优值：Z=6
0 x1 + 2 x2 ≤ 4
线性规划问题数学模型的一般形式
Z c1x1 c2 x2 cn xn 目标函数： max(min)
三要素
a11 x1 a12 x2 a1n xn (, )b1 约束条件： a21 x1 a22 x2 a2 n xn (, )b2 a x a x a x (, )b mn n m m1 1 m 2 2 x1 , x2 ,, xn 0
x1 , x2 ≥ 0
2
2 x2 = 4
图解法步骤：
Z=2 1 o 1 2 3 4 x1
1、建立直角坐标系；
2 、图示约束条件，判断可行域；
3 、图示目标函数和寻找最优解；
解的重要概念
可行解（或可行点） ：满足所有约束条件的向量 x ( x1 , x2 , xn ) 可行域：所有的可行解的全体
1 x1 2 x2 x3 x4 3 2 x1 x2 x , x , x , x 0 1 2 3 4
6个基，最多 C m 个 n
线性规划标准型解的概念
基解：当A中的基B取定后，不妨设B表示A中的前m列，则可 记 A (B N ) ，相应地X ( X B X N )T , 约束条件AX=b可表示为 X B ，即 X B1b B1NX ，当取 X 0 时，则 X B1b B N AX ( B N ) b N B

运筹学胡运权第五版课件

运筹学胡运权第五版课件
运筹学胡运权第五 版课件大纲
单击此处添加副标题
汇报人：
目录
添加目录项标题 运筹学基础知识 整数规划 图论与网络优化
课件概览 线性规划 动态规划
01
添加章节标题
02
课件概览
课件简介
课程名称：运筹学胡运权第五版课件 课程内容：包括线性规划、非线性规划、整数规划、动态规划、图与网络优化等 课程目标：帮助学生掌握运筹学的基本理论和方法提高分析和解决问题的能力 课程特点：理论与实践相结合注重案例分析和实际问题的解决
最小生成树问题：在无向图中寻找最小生 成树
最大流问题：在流网络中寻找最大流
最小费用流问题：在流网络中寻找最小费 用流
网络可靠性问题：评估网络可靠性提高网 络稳定性
网络优化算法：如Dijkstr算法、Floyd算 法、Kruskl算法等
网络优化算法
最短路径算 法：Dijkstr
算法、 Floyd算法
等
图论与网络优化应用案例
物流网络优化：通过图论方 法优化物流网络降低物流成 本
社交网络优化：通过图论方 法优化社交网络提高社交网
络的稳定性和可靠性
交通网络优化：通过图论方 法优化交通网络提高交通效 率
电力网络优化：通过图论方 法优化电力网络提高电力系
统的稳定性和可靠性
感谢观看
汇报人：
课件结构
• 运筹学概述 • 线性规划 • 非线性规划 • 动态规划 • 随机规划 • 决策分析 • 网络规划 • 排队论 • 库存论 • 博弈论 • 运筹学应用案例 • 运筹学发展前景 • 运筹学与其他学科的关系 • 运筹学学习方法与技巧
课件特点
内容全面：涵盖了运筹学的基本概念、理论和方法 结构清晰：按照章节进行划分便于理解和掌握 实例丰富：提供了大量的实例和案例便于理解和应用 习题丰富：提供了大量的习题和练习便于巩固和提高

运筹学 胡运权 第二章

运筹学 胡运权 第二章
《运筹学》 运筹学》
第1页
第二章 线性规划的对偶理论
一、问题的提出: 设用两种原料（A、B）
生产三种产品的一个生产计划问题
m f ( x) = x1 + 2x2 + 4x3 ax x1 + 2x2 + 2x3 ≤ 25 s.t. 2x1 + x2 + 2x4 ≤15 x1, x2 , x3 ≥ 0
华东师范大学
《运筹学》 运筹学》
第11页 11页
弱对偶性的推论： 对偶性的推论：
max问题的任何可行解目标函数值是其对偶min问 题目标函数值的下限； min问题的任何可行解目标 函数值是其对偶max问题目标函数值的上限。 如果原max(min)问题为无界解，则其对偶 min (max) max(min) 问题无可行解。 如果原max(min)问题有可行解，其对偶 min (max) 问题无可行解，则原问题为无界解。 存在原问题和对偶问题同时无可行解的情况。
华东师范大学
14 December 2010
《运筹学》 运筹学》
第10页 10页
1. 弱对偶性定理（P55） 对偶问题(min)的任何可行解Y0，其目 标函数值 bTY0 总是不小于原问题(max) 的任何可行解X0的目标函数值CTX0, 即 CTX0 ≤ bTY0
14 December 2010
14 December 2010
华东师范大学
《运筹学》 运筹学》
第8页
表2.1 对偶变换的规则
原问题(max,≤) ≤ 原问题 系数矩阵 A 目 标 系数 C 常数 项 b 第 i 行约束条件为 ≤ 型 第 i 行约束条件为 ≥ 型 第 i 行约束条件为 = 型 决策变量 xj ≥ 0 决策变量 xj ≤ 0 决策变量 xj ±不限 ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ 对偶问题(min,≥) ≥ 对偶问题 系数矩阵 AT 常数项 b 目 标 系数 C 对偶变量 yi ≥ 0 对偶变量 yi ≤ 0 对偶变量 yi ±不限 第 j 行约束条件为 ≥ 型 第 j 行约束条件为 ≤ 型 第 j 行约束条件为 = 型

运筹学胡运权第02章

运筹学胡运权第02章

•极大化问题的每个约束对应于极小化问题 的一个变量，其每个变量对应于对偶问题 的一个约束。
max Z c1 x1 c2 x2 cn xn
对 偶 问 题 的 定 义
a11 x1 a12 x 2 a1n x n (, )b1 a 21 x1 a 22 x 2 a 2 n x n (, )b2 a x a x a x (, )b m2 2 mn n m m1 1 x j 0( 0, 或符号不限) j 1 ~ n
c3 x3 c3 x3 max z c1 x1 c2 x2
对偶变量 y1 y2′
y2″
y3′
非 对 偶 形 式 的 原对 偶 问 题

例2-4
b2 y2 b3 y3 min w b1 y1 b2 y2
令各约束对应的对偶变量分别为y1、y2′、y2″、 -y3′
（2.4a） （2.4b） （2.4c）
（2.4d）
先转换成对称形式，如下：
a11 x1 a12 x2 a13 x3 a13 x3 b1 a x a x a x a x b 2 21 1 22 2 23 3 23 3 s.t. a21 x1 a22 x2 a23 x3 a23 x3 b 2 a x a x a x a x b3 31 1 32 2 33 3 33 3 x1 0，x2 0，x3 0，x3 0
a11 y1 a21 y2 a21 y2 a31 y3 c1 a y a y a y a y c 2 12 1 22 2 22 2 32 3 s.t. a13 y1 a23 y2 a23 y2 a33 y3 c 3 a y a y a y a y c 3 23 2 33 3 13 1 23 2 y1 0，y2 0，y2 0，y3 0

运筹学胡运权第五版课件-第二章


min Z 3 x1 2 x2 3 x3 4 x4 x1 2 x2 3 x3 4 x4 3 x2 3x3 4 x4 5 s.t. 2 x1 3 x2 7 x3 4 x4 2 x1 0，x2 0, x3、x4无约束 解：对偶问题为： max W 3 y1 5 y2 2 y3
3、矩阵形式： P max z CX AX b s.t. X 0
其中
D min w bT Y AT Y C T s.t. Y 0
a1n a2 n amn
C (c1 , c2 , , cn )
b1 b2 b bm
T T
A Y C C Y A
T T T
CX Y AX Y b b Y
T T T
2、最优性： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = bT Y* ， 则X*，Y*分别是问题 P和D 的最优解。
对偶问题（D）：
max z 2 x1 3 x2 2 x1 2 x2 12 4 x 16 1 s.t. 5 x2 15 x1 , x2 0
min w 12 y1 16 y2 15 y3 2 2 y1 4 y2 s.t. 2 y1 5 y3 3 y , y , y 0 1 2 3
解：第一步 改写为 min 的基本形式
令x1 x1，x2 x2 x2 min z 7 x1 （ 4 x2 x2） 3x3 4 x （ 2 x2 x2） 6 x3 24 1 3x1 （ 6 x2 x2） 4 x3 15 s.t. （ 5 x2 x2） 3x3 30 （ 5 x2 x2） 3x3 30 x1 ，x2，x2，x3 0

运筹08(第二章)运筹学第五版课件(历史上最好的,最全面的课件)


初始表中是 I 的位置，经变换后成为 B 1
其中 Y ( y 1 , y 2 ,..., y m )
记
Y CBB
1
1
Y 0 CBB
N
1
则
CN CBB
1
1
N C N YN
1
b B b;
N B
N ,或
P j B
Pj
例：书 P36 例10，验证上述公式。 上述公式对于灵敏度分析很有帮助 。
b
i 1
m
i
ˆ y i ，于是上式应为等式，即有
a
i 1 j 1
m
n
ij
ˆ ˆ x j yi
b
i 1
m
i
ˆ yi
( a
i 1 j 1
m
n
ij
ˆ ˆ x j bi ) y i 0
2012-8-18
19
而
a
j 1
n
ij
ˆ x j bi 0 ;
ˆ yi 0
且两者最优目标函数值相等，即 证明 设有线性规划问题
max z min w
。
max Z CX ; AX X s b ; X , X s 0
经单纯形法计算后，令Y C B B
基可行解 基变量
1
0， 最终表中
非基变量
b
I
0 CB CBB
1
N
B
B
1

j

1 1 N C N C B B N Y C B B
6、设原问题是： max Z CX
2012-8-18
11

(完整版)运筹学胡运权第五版课件(第1章)

四运筹学研究的基本特点?系统的整体优化?多学科的配合?模型方法的应用五五运筹学研究的基本步骤运筹学研究的基本步骤?分析与表述问题?建立数学模型?对问题求解?对模型和模型导出的解进行检验?建立对解的有效控制?方案的实施第一章线性规划及单纯形法linearprogrammingandsimplexmethodggp11一般线性规划问题的数学模型11问题的提出例1用一块边长为a的正方形铁皮做一个无盖长方体容器应如何裁剪可使做成的容器的容积最大
（3）L.P. 的顶点与基可行解一一对应。
§1.3 单纯形法（Simplex Method）原理
3-1 预备知识：凸集与顶点
（1）凸集：对于集合C中任意两点连线段上的点，若全在C内， 则称集合C为凸集。
直观特征：图形从内部向外部凸出。
凸集
非凸集
（2）顶点：凸集中不在任意两点的连线段内部的点。
X1
转化为
（2）若约束条件为不等式，
则依次引入松弛变量或剩余变量（统称为松弛变量），
转化为等式约束条件。
约束为≥不等式，减去松弛变量，化为等式约束条件；
多 退
约束为≤不等式，加上松弛变量，化为等式约束条件。
少 补
注意：松弛变量在目标函数中系数全为0。
例：max z=2 x1+3 x2
2 x1+2 x2 12
s.t.
4x1
16
5 x2 15
x10， x2 0
标准化
max z 2x1 3x2 0x3 0x4 0x5
2x1 2x2 x3
12
s.t.
4
x1
5 x2
x4 16 x5 15
x1, x2 , x3, x4 , x5 0
（3）若决策变量xj≤0，则令

第二章 对偶理论参数线性规划运筹学基础及其应用胡运权第五版


2+2 λ 3+ λ cB XB b X1 x2 0 x3 6 2 0 0 x4 16 4 0 3+ λ x2 3 0 1 cj-zj 2+ 2λ 0
0 x3 1 0 0 0
0 0 x4 x5 0 - 2/5 1 0 0 1/5 0 -3/5-1/5 λ
§2.5参数线性规划
Ch2 Dual Problem
将其直接反映到最终单纯形表中得：
§2.5参数线性规划
Ch2 Dual Problem
cB 2 0 3
XB b x1 3-1/5λ x4 4+4/5λ x2 3+1/5λ cj-zj
2 X1 1 0 0 0
3 x2 0 0 1 0
0 0 x3 x4 1/2 0 -2 1 0 0 -1 0
0 x5 -1/5 4/5 1/5 -1/5
- 15 -5 - 5 15
15
-3
-1
1
2
λ
§2.5参数线性规划
Ch2 Dual Problem
例2：求解下述参数线性规划问题：
max z 2 x1 3x 2 2 x1 2 x 2 12 4x 16 1 s.t. 5 x 2 15 x1 , x 2 0
§2.5参数线性规划
0 0 0 x3 x4 x5 1/2 0 - 1/5 -2 1 4/5 0 0 1/5 -1- λ 0 -1/5+1/5 λ
§2.5参数线性规划
Ch2 Dual Problem
上表中最优基不变的条件是-1≤λ≤1，此时目标函数值为 Z=15+9 λ.当λ＜-1时，x3列的检验数-1- λ＞0.将x3作为进基变量进 行单纯形迭代得下表 表2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例：写出下列LP问题的对偶问题
max z 5 x1 6 x2 x1 4 x 1 s.t. 解：对偶问题为： 2 x2 4 x2 x1 , x2 8 16 12 0
min w 8 y1 16 y2 12 y3 5 y1 4 y2 s.t.2 y1 4 y3 6 y1 , y2 , y3 0
T T T
x1 x2 X xn
a11 a12 a1n a21 a22 a2 n A am1 am 2 amn
y1 y2 Y ym
b , A , C 为b, A, C的转置
解：第一步 改写为 min 的基本形式
令x1 x1，x2 x2 x2 min z 7 x1 （ 4 x2 x2） 3x3 4 x （ 2 x2 x2） 6 x3 24 1 3x1 （ 6 x2 x2） 4 x3 15 s.t. （ 5 x2 x2） 3x3 30 （ 5 x2 x2） 3x3 30 x1 ，x2，x2，x3 0
对偶的定义
max W’ = -bTY s.t. -ATY≤-CT Y≥0
例 写出下列问题的对偶问题。
min z 7 x1 4 x2 3 x3 4 x1 2 x2 6 x3 24 3 x 6 x 4 x 15 1 2 3 s.t. 5 x2 3 x3 30 x1 0, x2无约束，x3 0
如何安排生产才能使 总的利润最大？
解： LP1
max z=2 x1+3 x2 2 x1+2 x2 12 4x1 16
s.t.
5 x2 15 x10， x2 0
假设另有四海机器厂想租借常山机器厂的全部可用资源进 行生产。问：常山机器厂应该如何给这些资源定出一个合理 的租金，既使四海机器厂愿意租借，又使本厂能得到自己组 织生产这些产品时所能获得的最大收益。
对偶问题D
min w = b1 y1 + b2 y2 + · · · + bm ym s.t. a11 y1 + a21 y2 + · · · + am1 ym c1 a12 y1 + a22 y2 + · · · + am2 ym c2 · · · a1n y1 + a2n y2 + · · · + amn ym cn yi 0，(i=1,2,· · · ,m )
2y 3 3 y1 2y1 y 2 3y 3 2 s.t. 3y1 3y 2 7y 3 3 4y 4y 4y 4 1 2 3 y1 0, y 2 0, y 3无约束
§2.3 对偶问题的基本性质
在本节中设原问题和对偶问题如下：
对偶问题（D）：
max z 2 x1 3 x2 2 x1 2 x2 12 4 x 16 1 s.t. 5 x2 15 x1 , x2 0
min w 12 y1 16 y2 15 y3 2 2 y1 4 y2 s.t. 2 y1 5 y3 3 y , y , y 0 1 2 3
解：先改写为原问 题的基本形式：
再对偶化：
最后简化得到已知问 题的对偶问题：
3、互为对偶关系
若LP2是LP1的对偶问题，则LP1是LP2的对偶问题。
max Z=C X
s.t. AX≤b X ≥0
改写
对偶的定义
min W= b TY s.t. AT Y≥ CT Y≥0
改写
min Z’= - CX s.t. - AX≥- b X ≥0
变量
约束
2、一般形式
原问题P s.t. max z = c1 x1 + c2 x2 + · · · + cn xn a11 x1 + a12 x2 + · · · + a1n xn b1 a21 x1 + a22 x2 + · · · + a2n xn b2 · · · am1 x1 + am2 x2 + · · · + amn xn bm xj 0，（j=1,2, · · · ,n）
第二章 线性规划的对偶理论
Dual Theory
§2.1 对偶问题的提出
消耗设备 例 常山机器厂生产 I、 工时 II 两种产品。这两种产品 都分别要在ABC三种不同设 设备A 备上加工。按工艺规定，生 设备B 产每件产品的单位利润、消 设备C 耗三种设备的工时以及各种 利润（元） 设备工时的限额如表： I 2 4 0 2 II 设备工时限 量 2 0 5 3 12 16 15
P max z CX AX b s.t. X 0
D min w bT Y AT Y C T s.t. Y 0
1、弱对偶性（弱对偶原理）：设 X 和 Y 分别是问题P 和D的可行解，则必有
__
__
C X bT Y
证明：
__
AX b Y AX Y b
例 直接写出下列线性规划问题的对偶问题。
min z 2 x1 3 x2 5 x3 x4 x4 5 x1 x2 3 x3 2 x 2 x3 4 x4 4 1 s.t. x2 x3 x4 6 x1 0 , x2，x3 0 , x4 无约束
原问题
P
对偶问题 D 对偶变量 y1,y2,y3
对偶目标 w 对偶约束
2 2 y1 4 y2 5 y3 3 2 y1 y , y , y 0 1 2 3
原变量 x1,x2
原目标 z 原约束
2 x1 2 x2 12 4 x 16 1 5 x2 15 x1 , x2 0
3、矩阵形式： P max z CX AX b s.t. X 0
其中
D min w bT Y AT Y C T s.t. Y 0

C (c1 , c2 ,, cn )
b1 b2 b bm
max w 24 y1 15 y2 30 y3 30 y4
第二步 对偶化
7 4 y1 3 y2 2 y 6 y 5 y 5 y 4 1 2 3 4 s.t. 2y1 6 y2 5 y3 5 y4 4 6y 4 y 3 y 3 y 3 1 2 3 4 y1 , y2 , y3 , y4 0
§2.2 原问题与对偶问题
P max z CX AX b s.t. X 0
（max的基本形式） 1、基本形式的联系与区别
D min w bT Y AT Y C T s.t. Y 0
（min的基本形式）
（1）原目标求数
基本形式
非基本形式
4、原问题与对偶问题的互化
原问题（或对偶问题） 目标函数 max （基本） m个 约 束 ≤（基本） 条 ≥ 件 =
n个 变 量 ≥0 （基本） ≤0 无约束 约束条件的右端项 目标函数的系数
对偶问题（或原问题） 目标函数 min （基本） m个 变 ≥0 （基本） 量 ≤0
无约束 n个 ≥ （基本） ≤ = 目标函数的系数 约束条件的右端项 约 束 条 件
原约束决定对偶变量 原变量决定对偶约束；
（3）原约束≤方向，对偶约束≥方向； （4）原目标的系数对应对偶约束的右端常数 原约束的右端常数对应对偶目标的系数； （5）原系数矩阵与对偶系数矩阵互为转置； （6）原变量与对偶变量都是非负取值。
2、基本形式的表格比较
例 将下列问题作为原问题，写出其对偶问题。
解：设A、B、C设备每小时出租的价格分别为y1、y2、y3元， 则新的线性规划数学模型为： LP2
min w 12 y1 16 y2 15 y3 2 2 y1 4 y2 s.t. 2 y1 5 y3 3 y , y , y 0 1 2 3
1、基本概念
对偶性是线性规划问题的最重要的内容之一。 每一个线性规划（ LP1 ）必然有与之相伴而生的另一 个线性规划问题（ LP2 ），即任何一个求 max z 的LP1都 有一个求 min w的LP2 。 将LP1称为“原问题”，记为P ； 将LP2称为“对偶问题”，记为D 。 原问题（P）：
第三步 简化为已知 问题的对偶问题：
令y1 y1，y3 y3 y4 max w 24 y1 15 y2 30 y3 4 y 3 y 7 1 2 2 y1 6 y2 5 y3 4 s.t. 6y1 4 y2 3 y3 3 y1 0, y2 0, y3无约束
min Z 3 x1 2 x2 3 x3 4 x4 x1 2 x2 3 x3 4 x4 3 x2 3x3 4 x4 5 s.t. 2 x1 3 x2 7 x3 4 x4 2 x1 0，x2 0, x3、x4无约束 解：对偶问题为： max W 3 y1 5 y2 2 y3
对偶问题： max w 5 y1 4 y2 6 y3 y1 2 y2 2 y1 y3 3 s.t. 3 y1 2 y2 y3 5 y1 4 y2 y3 1 y1 0, y2 0, y3无约束
练习
写出下列问题的对偶问题。
T T
A Y C C Y A
T T T
CX Y AX Y b b Y
T T T
2、最优性： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = bT Y* ， 则X*，Y*分别是问题 P和D 的最优解。