最优解一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系【例】某工厂利用
现有的三种资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115
时24时5时产品Ⅰ产品Ⅱ资源一、对偶问题的提出如何安排生产，使获利最多？厂商设Ⅰ产量为
Ⅱ产量为设：设备A元／时设备B元／时调试工序元／时收
购方付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备A
设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：
收购方的意愿：单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产
的利润。对偶问题原问题一对对偶问题原问题的一般模型可定义为：对偶规划的一般数学模型nnxcxc
xcZ+++=...max2211s.t.11212111...bxax
axann￡+++22222121...bxaxaxann￡+++
……….mnmnmmbxaxaxa￡++
+...22110,...,,213nxxx相应的对偶问题的一般模型可定义为：mm
ybybybS+++=...min2211s.t.11221111
...cyayayamm3+++22222112...cyayayamm
3+++………nmmnnncyayay
a3+++...22110,...,,213myyy原问题与对偶问题的对应关系讨论对偶
问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格
的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。下表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划
原问题转化为对偶问题的一般规律。原问题线性规划模型对偶线性规划模型原问题为maxZ的线性规划问题对偶关系表原问题（或对偶问
题）对偶问题（或原问题）目标函数最大化(maxZ)n个变量m个约束约束条
件限定向量（右边项）目标函数价值向量（系数）≥0变量≤0
≥无限制约束≤＝目标函数最小化（minS
）n个约束m个变量目标函数价值向量（系数）约束条件限定向量（右边项）≥约束
≤≤0＝变量≥0
无限制由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3（还可依对偶问题写出原问题）
例1maxZ=2x1+x25x2≤15
6x1+2x2≤24x1+x2≤5x1,x
2≥0minw=15y1+24y2+5y36y2+y3≥2
5y1+2y2+y3≥1s.t.y1,y2,y3≥0原问题为m
inS的线性规划问题对偶关系表原问题（或对偶问题）对偶问题（或原问题）目标函数最小化(minS)n个变量
m个约束约束条件限定向量（右边项）目标函数价值向量≥0变量≤0
≥无限制约束≤＝目标函数最大化（maxZ）
n个约束m个变量目标函数价值向量（系数）约束条件限定向量≤约束≥
≥0＝变量≤0无限制由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3321
34maxyyyZ+-=s.t.12321￡--yy2y-332
1￡+-y4y42321￡++yyy01￡y，02￡y例32
143MinxxxS+-=s.t.1321￡+-4xx2x4
23321-￡++-xxx3-231￡+xxx1,x2,x33003
￡y，原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变
量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函
数变量的系数目标函数变量的系数约束条件右端项例:对偶问题为§3对偶问题的基本性质原问题对偶问题性质1：弱
对偶性。如果是原问题的可行解，是其对偶问题的可行解，则恒有性质2：最优性。如果是原问题的可行解，是其
对偶问题的可行解，且有则分别为原问题与对偶问题的最优解。性质3：无界性。如果原问题（对偶问题）为无界解，则
其对偶问题（原问题）无可行解。反之，则不成立。性质4：强对偶性（对偶定理）。如果原问题有最优解，则其对偶问题也一定具有最优解，且
有maxz=minω。性质5：互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非0，则该约束条件取严格
等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为0.即性质6：线性规划的原问题与其对偶问题之间存在一对互补的基解，其
中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一
个问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=ω。对偶问题原问题（
）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题化为极小问题，最终单
纯形表：原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表（
）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题最优解对偶问题
最优解原问题化为极小问题，最终单纯形表：两个问题作一比较:1.两者的最优值相同2.变量的解在两个单纯形表中互相包含原问题
最优解（决策变量）对偶问题最优解（决策变量）对偶问题的松弛变量原问题的松弛变量对偶单纯形法由对偶问题的基本性质6知
，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标
函数时其值相等。单纯形法求解的基本思想：保持原问题为可行解，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函
数的最优值。对偶单纯形法的基本思想：保持对偶问题为可行解，通过迭代，减小目标函数，当原问题也达到可行解时，即得到了目标函数的最优值。对偶单纯形法的计算步骤确定出基变量对于小于〇的bi,令br=min{bi}，其对应变量xr为出基变量。确定入基变量为使迭代后表中对偶问题的解仍为可行解，令则ars为主元素，xs为入基变量。用入基变量替换出基变量，得到新基。判断原问题是否可行。对偶单纯形法的计算步骤【例】用对偶单纯形法求解下述线性规划问题：初始可行基换出换出 |
|
