x*=(15,20)’ z*=1440元。
y*=(2,24)’ w*=1440元。
将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的练习与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。
三、 原问题与对偶问题的关系。
则有。其对偶问题为：
令z’=-z，则有。
所以，对偶问题的对偶是原问题。
并非所有的lp问题都有对称形式，故讨论一般情况下lp问题如何写出其对偶问题。
解：先化为对称形式，因为目标函数求极大，所以约束条件变为“≤”决策变量≥0
令对应上述4个约束条件的对偶变量分别为。
则有。经过以上分析，可以总结出原规划与对偶规划相关数据间的联系。
列出初始单纯形表。
设若干步迭代后，基变量为xb, xb在初始单纯形表中的系数矩阵为b，而a中去掉b的若干列组成矩阵n，则迭代后的单纯形表为：
从表中看出：
1)对应初始单纯形表中的单位矩阵i，迭代后的单纯形表中为b-1
2)初始单纯形表中的基变量xs=b，迭代后为xb=b-1b
3)初始单纯形表中约束系数矩阵[a,i]=[b,n,i]，迭代后的表中为[b-1a, b-1i]=[b-1b, b-1n, b-1i]＝[i, b-1n, b-1]
4)若初始矩阵中变量xj的系数列向量为pj，迭代后为pj’，则。
pj’= b-1pj
5)当b为最优基时，应有。
又因为xb的检验数可写为。
将(1)和(3)合并，则有。
cbb-1称为单纯形因子，令cbb-1＝y则有。
cbb-1＝y，检验数行的相反数，恰好是对偶问题的可行解。
将y＝cbb-1代入对偶问题的目标函数值，
所以当原问题为最优解是，对偶问题为可行解，且两者目标函数值相同，根据下节的对偶问题的基本性质，将看到这时对偶问题的解也为最优解。
证明：x(0)是原问题的可行解， 所以a x(0) ≤b1)
y(0)是对偶问题的可行解，所以y(0) a ≥c (2)
x(0) ，y(0)≥0，用x(0)右乘(2)，y(0)左乘(1)
y(0)a x(0) ≤y(0)b
y(0) a x(0)≥c x(0)
证明：设x是lp的任一个可行解，则有。
c x≤ y(0) b＝c x(0)
所以 x(0) 是最大化问题的最优解。
y(0是最小化问题的最优解。
定理3(最优解存在定理)：若lp和dp同时存在可行解，则它们必都存在最优解。
证明同上。定理4(无界解定理)：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。
证明：反证法。
设原问题目标函数为极大值，无上界。
对偶问题的可行解为y(0)
则c x≤ y(0) b
根据定理1，原问题存在最优解，与假设矛盾，假设不成立。
证明：设lp存在最优解，将其化为标准型，则有。
xa为松弛变量，ca为其价值系数(ca=0)，设原问题的最优解为x(0)，基为b，则有。
即。令cbb-1＝y(0则有
所以y(0)是对偶问题的一个可行解。
引入定理2，w(0)=y(0) b＝cbb-1b=cbxb
也是对偶问题的最优解。
原问题与对偶问题的解之间只有以下3种可能的关系。
1) 两个问题都有可行解，从而都有最优解。
2) 一个为无界，另一个必无可行解。
3) 两个都无可行解。
证明：设原问题和对偶问题的标准型是。
则 充分性：若ysx=0 yxs=0 则有z=w 即cx(0)＝y(0)b
则x(0)，y(0)必是各自问题的最优解。
必要性：若x(0)，y(0)是各自问题的最优解。
则有cx(0)＝y(0)b＝y(0)a x(0)
即ysx=0 yxs=0
解：第一步，写出对偶问题。
第二步，将lp，dp都化为标准型。
第三步：将最优解代入标准型中，确定松弛变量取值。
第四步：利用互补松弛定理。
y3*=0
y1s=0 y2s=0
第五步：将y3*=0 y1s=0 y2s=0 代入约束条件。
则有。如果第i种资源供大于求，即达到最优解时，资源并没用完。
即xsi＞0 为非稀缺资源。
由互补松弛定理，yi*=0，即该资源的影子**＝0
增加该资源的**不会引起目标函数值的增加。
反之，如果yi*＞0，即影子**＞0，则说明增加该资源的**，会引起目标函数值的增加（yi*=增加量）
运筹学教案
第一章绪论。运筹学 operational research 直译为 运作研究。运筹学是应用分析 试验 量化的方法，对经济管理系统中的人力 物力 财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学的产生和发展。举例 丁谓修皇宫 田忌赛马 二战大西洋潜艇战，交通线战争 滇...
运筹学教案
第 1 次课 2 学时。注 本页为每次课教案首页。绪论。运筹学 operations research 是用数学方法研究各类系统最优化问题的学科。运筹学通过建立系统的数学模型并求解，为决策者制定最优决策提供科学依据。一 运筹学简史。二 运筹学的主要分支。1.线性规划 linear programmi...
运筹学教案
学习运筹学要结合实际的应用，不要被一些概念 理论的困难吓倒。学习运筹学要把注意力放在 结合实际问题建立运筹学模型 和 解决问题的方案或模型的解 两头，中间的计算过程尽可能让计算机软件去完成。本书附有运筹学教学软件，使用方法很简单。学员必须尽快学会使用这个运筹学教学软件，并借助它来学好本课程。学习运筹...