对偶单纯形法与单纯形法对比分析
1．教学目标：
通过对偶单纯形法的学习，加深对对偶问题的理解 2．教学内容：
1）对偶单纯形法的思想来源 2）对偶单纯形法原理 3．教学进程：
1）讲述对偶单纯形法解法的来源：
所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。
2）为什么要引入对偶单纯形法：
单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点： （1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算； （2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。 由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w 。据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。
我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函数的最优值。那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即达到了目标函数的最优值。其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。 一.单纯形法和对偶单纯性法
单纯形法是求解线性规划的主要方法, 单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为
Max ∑==n
j j j x c Z 1
?????=≥=≤∑=),....,1(0)
,...,1(..1n j m i t s x b x a j
n
j i j ij ⑴
将其化为标准形式，得
Max Z= CX
s.t. ?????≥=+0,X X s
s X b
AX ⑵
其中),(C C N B C =，)0,...,0,0(0==C N ，),(N B A =，?????=X X N
B
X ，则其对应的线性约束
转换为
01
1
=++--X B
X B
X s N B ，
X
B
X B
B X s
N B b 1
1
1---+-=，代入目标函数得
X
B
C X B C C B C S
B N B N B b Z 1
1
1
)(-----+=，相应的一个基解为
b B X B 1
-=，
0=X
N
，0=X S 。显然，若01
≥-b B ，且0)(1
≥--N B C C B N ，01
≥--X
B C S
B ，
则基解??
?
???????=-01
b X B 为该线性规划的最优解, 此时检验数均大于零, 见表1。
通过上面的分析, 我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个( 加一个负号) 基解。那么
表中b 列的数字仅仅表示的是X B 的取值吗? 我们可以猜想b B 1
- 很可能是对偶问题的检验数。这里首先给出问题(1) 的对偶问题的一般形式
Min ∑==m
i i
i y b w 1
s.t.?????=≥=≥∑=),....,1(0)
,...,1(1m i n j y c y a i
m
i j i ij ⑶
将问题（3）化为标准形式，得 Min YB w =
s.t.?????≥=-0
,Y Y S S Y C
YA ⑷
由),(C C N B C =，),(N B A =，Ys 为松弛变量，Ys 相应分解为Y sB 、Y sN ，其中
0),....,,(21
1
≥=++y y
y
Y
m
m m sB
，0),....,,(22
21
2≥=++y y
y
Y n
m m sN 。得：
C Y B sB YB =- ⑸ C Y N sN YN =- ⑹ 由式⑸得到
B Y B
C sB B Y 1
1
--+= ⑺
通过令
0=Y sB ，由式(5)得对偶问题的基解B
C B Y 1
-=,代入式(6)得
C B C Y N B sN N -=-1
,将式(7)对偶问题的目标函数得b b w B Y B C sB B 1
1
--+=。显然若
目标函数达到最小,非基变量Y sB 的价值系数要求大于等于零,单纯形表b 列01
≥-b B , 即
01
≥-b B
实际上是对偶问题的非基变量检验数。
二．对偶单纯形法的算法步骤 (1)确定换出基的变量
设原问题为（1），对偶问题为（3）。由),(),,(C C N B C N B A ==，不等式C YA ≥则可分解为 C C N B YN YB ≥≥, (8)
进一步添加松弛变量有等式（5）、（6），对等式（5）两端同时左乘B 1
-有 B C B Y B sB Y 1
1--=- (9) 将B Y sB 1
-移至等式右端得
B C B Y B sB Y 1
1--+= (10) 由不等式（8）得
0≤-YB C B (11) 0≤-YN C N (12) 将式（10）代入不等式（11）、（12）得
01
1≤--=---B B YB B Y B C C C sB B B B (13) 01
1≤--=---N N YN B Y B C C C sB B N N (14) 将（13）、（14）合并得
0),)((),(),(),(1
1≤+-=---N B N B Y B Y B C C C C C sB B N B N B (15) 整理得
01
1≤----A A C B Y B C sB B (16)
其中A C B C B 1--是单纯形表中X 变量的检验数,记)(1
σj B A C B C =--，(j=1,2,....,n),n m ij a B
A x '
1
)(=-矩阵，显然，若Y 为基可行解，而若
01
<-b B
，则对偶问
题的目标函数
b
b w B Y B C sB B 1
1--+=未取得最小值，取
{
}
l i i b b b B B B )(0)(|)(min 1
1
1---=<，确定单纯形表的换出基变量x l ，即（在单纯形表中的）对偶问题相应的换入基变量
y
l
m +，令
Y
sB
其余分量为零，即
)0,...,,0,...,0(),...,,(22
1
y
y y
y
Y
l
m m
m m sB
+++==，y
l
m +可能取大，使对偶问题的目标函数值
下降，由Y 为基可行解，则要求满足式（16），即对于任意的j ，均有0'
≥-+a
y
ij
l
m j σ，得
a a a y k
m l k m ij j ij j l m ',''0,0|min +++=??????????≤≤=σσσ，从而确定单纯形表中换入基变量x k
m +，同时确定对偶问题（在单纯形表中）换出基变量y k
。这与单纯形法确定换出基变量的规则是完
全一样的。
3）例题讲解
下面举例说明对偶单纯形法的算法步骤： 【例题】用对偶单纯形法求解线性规划问题： min y y y w 3
2
1
52415++=
解：1）将问题改写为： 2）算法步骤
第一步：建立一个初始单纯形表，使表中检验行的σj 值全部大于或等于零， 即对其对偶问题而言是一基本可行解。 约束条件两端乘 -1，得：
根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字 相当于对偶问题解的非基变量的检验数。
第二步：由于对偶问题的求解是使目标函数达到最小值，所以最优判别准则是 当所有检验数大于或等于零时为最优（也即这时原问题是可行解）。 如果不满足这个条件，找出绝对值最大的负检验数，设为b i -，其对应 的原问题的基变量x l 即为对偶问题的换入变量。 第三步：将σj 行数字与表中第l 行对应的数字对比，令
a C a a C lk
j ij ij j =
??????????<=0||min θ，a lk 即为主元素，x k 为对偶问题的换出变 量。
第四步：用换入变量替换对偶问题中的换出变量（在单纯形表中反映为用替原问 题的基变量），得到一个新的单纯形表。
表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本 可行解，原问题基变量列数字列数字相当于对偶问题的检验数。
据此可以完成对这个对偶问题的求解。 4．总结。
1）对比单纯形法&对偶单纯形法单纯性法基本思想
2）对偶单纯形法优点
这里我们需要对单纯形法和对偶单纯形法做一个详细的对比： 1，单纯形法中的b 对应于对偶单纯形法中的σ；
2，单纯形法中的σ作为检验数，对偶单纯形法中的b 作为检验数； 3，单纯形法中的0≥b ，对偶单纯形法中的0≤σ；
4，单纯形法中当0≤σ时得到最优解，对偶单纯形法中当0≥b 时得到最优 解；
5，单纯形法的可行解为b X B 1-=，对偶单纯形法的可行解为B C B Y 1
-=； （由于松弛变量X s 对应的检验数为B C B 1
--，由于X s 与Y 对应，又由于 01<--B C B ，可得01
≥=-B C B Y ）
。 对于单纯形法和对偶单纯形法，我们建立了使用单纯形法解决线性规划问题
的依据：
1，表中有单位矩阵I ，当0≥b 时用单纯形法； 2，表中有单位矩阵I ，当0≤σ时用单纯形法； 3，两者都不满足时，使用人工变量法或两阶段法。
接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便 捷，我将通过下面的例子来说明：
min x x x x Z 43211216812+++= 令Z Z -=-
，则问题可变为
max x x x x Z 43211216812----=-
取),(65P P B =为初始基，易见所有检验数0≤σj ，从而建立单纯形表，计 算结果如下：
本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算 量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，
计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一 定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规
划问题具备下面条件时，可以用对偶单纯形法求解： ①问题标准化后，价值系数全非正； ②所有约束全是不等式。 总结上面的分析过程可知，对偶单纯形法本质上就是单纯形法,只不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的b 列b B 1
-实际上是对偶问题的非基变量Y sB 的检验数, 而原单纯形表的检验数为对偶问题的( 负的) 基解, 这
样可以理解为通过旋转90°运用单纯形法求解线性规划。
题目：对偶单纯形法解线性规划问题 小组成员：
摘要： 运筹学是辅助人们进行科学管理的一种数学方法.而对偶单纯形法是线性规划中重要的数学方法，在简化运算，解决实际问题中具有重要的应用。它是解决研究线性约束条件下线性目标函数的极值问题的数学理论和方法，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求。 关键词：对偶单纯形法线性规划最优解 正文： 单纯形法和对偶单纯形法的基本思想： 给出一个线性规划问题: Max z = CX AX≤b X≥0 其对偶问题是: Min w = Yb YA≥C Y≥0 单纯形法解决线性规划问题的思想是: 从问题(1)的一个基解X0开始迭代到另一个基解,在迭代过程中保持基解的可行性,同时它对应的对偶问题(2)的基解Y0= CBB-1的
不可行性逐步消失,直到Y0是问题(2)的可行解时,X0就是问题(1)的最优解了。 对偶单纯形法正是基于对称的想法,从一个基解X0开始,X0不是基可行解,但它的检验数全部非正,对应的对偶问题的基解Y0= CBB-1是基可行解;从X0迭代到另一个基解X1,在迭代过程中保持它对应的对偶问题的基解是基可行解,逐步消除原问题基解的不可行性,最终达到两者同时为可行解，也就同时是最优解了。这就是对偶单纯形法的基本思想。 算法： 用对偶单纯形法解决生产资料分配问题的步骤: Step1 找出一组以定基元素x0i和人工变量为基变量的正则解X0,若X0是可行的,则X0是最优解, 停止,否则转向STEP2; Step2 确定换出变量x0l,其中x0l=min{x0r;x0r<0}; Step3 如果对所有非基变量x0j,βlj≥0,则该问题无可行解,运算停止,否则转向STEP4; Step4 确定换入变量x0k,其中σkβlk=minσtβlt;βlt<0;1≤t≤n+m ; Step5 取x0l为换出变量,x0k为换入变量进行迭代,然后重复上过程直到得到最优解。
《运筹学》第三版（清华大学出版社）P79例1，表上作业法，运用西北角法确定初始基可行解。 西北角法是从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数；然后按行（列）标下一格的数；若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去；如此进行下去，直至得到一个基本可行解的方法。 西北角法的例子：P79例1 从表1中可知，总的产量=总的销量，故产销是平衡的。 第一步：列出运价表和调运物资平衡表。 运用表上作业法时，首先要列出被调运物资的运价表和供需平衡表（简称平衡表），如表1，2所示。 第二步：编制初始调运方案。 首先在表2的西北角方格（即左上角方格，对应变量x11），尽可能取最大值： x =min{3,7}=3 11 将数值3填入该方格(见表3)。由此可见x21,x31必须为0，即第一列其他各方格都不能取非零值，划去第一列。在剩下的方格中，找出其西北角方格x12，x =min{6,7-3}=4 12 将4填入它所对应方格，第一行饱和，划去该行。再找西北角方格x22， x =min{6-4,4}=2 22
将2填入x22所对应方格，于是第二列饱和，划去该列。继续寻找西北方格为x23， x =min{5,4-2}=2 23 将2填入x23所对应方格，第二行饱和，划去该行。剩下方格的西北角方格为x33， x 3=min{5-2,9}=3 3 将3填入x33所对应方格，第三列饱和，划去该列。最后剩下x34方格，取x34 = 6。 这样我们就找到了m＋n-1＝3＋5-1＝7个基变量，它们为：x11= 3,x12= 4,x22 = 2,x23 = 2,x33 = 3,x34 = 6。显然它们用折线连接后不形成闭回路。这就是西北角法所找初始基可行解，所对应的目标值为： 2×200＋1×250＋3×150＋1×150＋3×250＋3×300＋4×200＝4000 我们找到的初始基可行解可通过各行方格中数值之和是否等于产量，各列方格中数值之和是否等于销量来简单验证。 利用西北角法找初始基可行解简单可行，但也存在问题。例如在表3中可见c = 4，单价高于该行其他各方格，最简单想法是单价小的情况下多运些货物，35 这样总运费会更小些，最小元素法就改进了西北角法的缺点。
课程名称：对偶单纯形法 一、教学目标 在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。 二、教学内容 1) 对偶单纯形法的思想来源(5min) 2) 对偶单纯形法原理(5min) 3) 总结对偶单纯形法的优点及适用情况(5min) 4) 对偶单纯形法的求解过程(10min) 5) 对偶单纯形法例题(15min) 6) 对比分析单纯形法和对偶单纯形法(10min) 三、教学进程： 1）讲述对偶单纯形法思想的来源： 1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method ）。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 2）讲述对偶单纯形法的原理 A.对偶问题的基本性质 依照书第58页，我们先介绍一下对偶问题的六个基本性质： 性质一：弱对偶性 性质二：最优性。如果 x j （j=1...n)原问题的可行解，y j 是其对偶问题可 行解，且有 ∑=n j j j x c 1 =∑=m i i i y b 1 ，则x j 是原问题的最优解，y j 是其对偶问题的最
优解。 性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。 性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。 性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w. B.对偶单纯形法（参考书p64页） 设某标准形式的线性规划问题，对偶单纯形表中必须有c j -z j ≤0（j=1...n),但b i (i=1...m)的值不一定为正，当对i=1...m ，都有b i ≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。 3）为什么要引入对偶单纯形法 从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引入人工变量，使计算简化。 例如，有一线性规划问题： min ω =12 y 1 +16y 2 +15 y 3 约束条件 ?? ?? ???≥=≥+≥+0)3,2,1(3522 423121 i y y y y y i
哈工大运筹学大作业-对偶 单纯形法对比 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-
运筹学课程 运筹学对偶单纯形法与单纯形法 对比分析大作业 哈尔滨工业大学工业工程系 学生姓名: 学号： 指导教师： 成绩： 评语：
运筹学对偶单纯形法与单纯形法对比分析 摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。 关键词：对偶单纯形法；对偶理论；单纯形法；基本思想 在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。这个发现指出，对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系在众多领域都非常有用。 （一）教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围 （二）教学内容： 1）对偶单纯形法的思想来源 2）对偶单纯形法原理 3）对偶理论的实质 4）单纯形法和对偶单纯形法的比较 （三）教学进程： 一、对偶单纯形法的思想来源
所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954 年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 二、对偶问题的实质 下面是原问题的标准形式以及其对应的对偶问题： 原问题对偶问题 从而可以发现如下规律： 1.原问题目标函数系数是对偶问题约束方程的右端项。 2.原问题约束方程的右端项是对偶问题目标函数的系数。 3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。 三、对偶单纯形法原理 对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法，它的应用包括影子价格和灵敏度分析等。为了理解对偶单纯形法为什么能够解出原方程的最优解，我们需要对对偶理论的几个基本原理有所了解。 1.弱对偶性 如果是原问题的可行解，是其对偶问题的可行解，则恒有
运 筹 学 考 卷 1 / 51 / 5
考试时间: 第十六周 题号一二三四五六七八九十总分 评卷得分 ： 名 一、单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确 姓 答案的字母写这答题纸上。（10 分, 每小题2 分） 1、使用人工变量法求解极大化线性规划问题时，当所有的检验数j 0 ，在 线 基变量中仍含有非零的人工变量，表明该线性规划问题（） A. 有唯一的最优解； B. 有无穷多个最优解； C. 无可行解； D. 为无界解 2、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）： 号 A．b 列元素不小于零B．检验数都大于零 学 C．检验数都不小于零D．检验数都不大于零 3、在产销平衡运输问题中，设产地为m 个，销地为n 个，那么基可行解中非 零变量的个数（） 订 A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。 4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（） A. d 0 B. d 0 C. d 0 D. d 0,d 0 5、下列说法正确的为（） ： 业 A．如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 专 B．如果线性规划的对偶问题无可行解，则原问题也一定无可行解 装 C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原 问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 ： 院
学 2 / 52 / 5
二、判断下列说法是否正确。正确的在括号内打“√”，错误的打“×”。（18 分，每 小题2 分） 1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（） 2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一 个基变量的值为负。（） 3、任何线性规划问题存在并具有惟一的对偶问题。（） 4、若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。 （）5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之 一：有惟一最优解，有无穷多最优解，无界解，无可行解。（） 6、如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k ， 最有调运方案将不会发生变化。（） 7、目标规划模型中，应同时包含绝对约束与目标约束。（） 8、线性规划问题是目标规划问题的一种特殊形式。（） 9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（） 三、解答题。（72 分） max z 3x 3x 1 2 1、（20分）用单纯形法求解 x x 1 2 x x 1 2 4 2 ；并对以下情况作灵敏度分析：（1）求 6x 2 x 18 1 2 x 0, x 0 1 2 5 c 的变化范围；（2）若右边常数向量变为2 b ，分析最优解的变化。 2 20 2、（15 分）已知线性规划问题： max z x 2x 3x 4x 1 2 3 4 s. t. x 2x 2x 3x 20 1 2 3 4 2x x 3x 2x 20 1 2 3 4 x x x x , , , 0 1 2 3 4 其对偶问题最优解为y1 1.2, y2 0.2 ，试根据对偶理论来求出原问题的最优解。
线性规划建模及单纯形法 思考题 主要概念及内容： 线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式； 可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基 向量；基本解、基本可行解、可行基、最优基。 复习思考题： 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它 们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个 最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继续第二阶段？ 作业习题 1、将下列线性规划问题化为标准型 （1）???????≥=--+-≥-+-≤+-++-+=0,,953413223183622453max 4214321432143214321x x x x x x x x x x x x x x x x x x x z （2）???????≤≥=+-+-≥-+--≤--++++=0 ,0,15 2342722351232243min 4214321432143214 321x x x x x x x x x x x x x x x x x x x f 2、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）： ?????≥≤++-≤++0,,1243263323 21321321x x x x x x x x x （2）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解. ??? ????≥=-=+-+=+++++=)6,,1(00 31024893631223max 61532143213 21K K j x x x x x x x x x x x x x x z j 3、用图解法求解下列线性规划问题
No .1 线性规划 1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而成。 工厂有供纺纱的总工时7200h ，织带的总工时1200h 。 (1) 列出线性规划模型，以便确定产品的数量使总利润最大； (2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的 解是否有影响？（所谓一次性投入就是与产量无关的初始投资） 2、将下列线性规划化为极大化的标准形式 3、用单纯形法解下面的线性规划 ??? ??? ?≥≤++-≤++-≤-+++= ,0,,4205.021********* ..352)(m ax 3213213213213 21x x x x x x x x x x x x t s x x x x f No .2 两阶段法和大M 法 2、用大M 法解下面问题，并讨论问题的解。 ??? ??? ?≥≥++≤++-≤++++= ,0,,52151565935 ..121510)(max 3213213213213 21x x x x x x x x x x x x t s x x x x f 1、用两阶段法解下面问题： ??? ??≥≥+≥++=0,75 3802 ..64)(min 2 121212 1x x x x x x t s x x x f ?????? ?±≥≤+-=-+--≥-+++=不限 321321321321321 ,0,13|5719|169765 ..532)(m in x x x x x x x x x x x x t s x x x x f
No .3 线性规划的对偶问题 ?????-≤≤-≤≤≤≤-+-=8121446 2 ..834)(min 3213 21x x x t s x x x x f 2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解 3、用对偶单纯形法求下面问题 ??? ??≥≥+≥++=0,75 3802 ..64)(min 2 121212 1x x x x x x t s x x x f No .4 线性规划的灵敏度分析 原问题为max 型，x 4，x 5为松驰变量，x 6为剩余变量，回答下列问题： (1)资源1、2、3的边际值各是多少？(x 4，x 5是资源1、2的松驰变量，x 6是资 源3的剩余变量) (2)求C 1, C 2 和C 3的灵敏度范围； (3)求?b 1，?b 2的灵敏度范围。 1、写出下列线性规划问题的对偶问题： (1) ???????±≥≤=++≤+≥+-+-+=不限 432143231 4321321 ,0,,06 4 2 5 ..532)(max x x x x x x x x x x x x x t s x x x x f (2) ?????? ?≥≤+--≤-≤+--= ,0, 121 1 ..34)(m ax 212122121x x x x x x x t s x x x f
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>* i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0运筹学课程设计报告书---运输问题的表上作业法
运筹学课程设计报告书 专业 班级 学号 姓名LMZZ 日期2011.09.01
设计题目：运输问题的表上作业法 设计方案：运输问题是一种应用广泛的网络最优化模型，该问题的主要目的是为物资调运、车辆高度选择最经济的运输路线。有些问题，如m 台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最佳方案。 运输问题的一般提法： 某种物资有m 个产地Ai ，产量是ai （i ＝1，2,…,m ），有m 个销售地Bi ，销量(需求量)是bj(j=1,2,…,m)。若从Ai 运到Bi 单位运价为dij(i=1,2,…,m;j=1,2,…,m),又假设产销平衡，即 ∑∑===m i n j j i b a 11 问如何安排运输可使总运费最小？ 若用x ij (i=1,2,…,m;j=1,2,…,n)表示由A i 运到B j 的运输量，则平衡运输问题可写出以下线性规划模型：
∑∑===m i n j ij ij x d Z 11min 约束条件 ?????????==≥====∑∑==) ,...,2,1;...,2,1(0)...,2,1()...,2,1(11n j m i x n j b x m i a x ij m i j ij n j i ij 表上作业法原理同于单纯形法，首先给出一个初始的调运方案(实际上是初始基本可行解)，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个基本可行解转换成另一个基本可行解)，再判定是否为最优解，重复以上步骤，直到获得最优解为止。这些步骤在表上进行十分方便。 操作过程在表上进行 方案实施：通过运输问题在C++程序中的运用，从而实现方案的最优。程序主要分两部：（1）求解，（2）最优解判断 结果与结论：程序运行过程中，依次输入所需要的运价，产量，销量等数据，单击回车可以再次现实所需数据，按任意键可以运行至求出初始可行解并显示，再次按任意键程序进行最优解的判断，并求出最优解，显示在程序页面上，从而可以得到该运输问题的最优方案。
例4-7用对偶单纯形法求解线性规划问题. Min z =5x1+3x 2 ≥6 s.t. -2 x1 + 3x 2 ≥4 3 x1 - 6 x 2 Xj≥0（j=1,2） 解：将问题转化为 Max z = -5 x1 - 3 x 2 + x3 = -6 s.t. 2 x1 - 3x 2 -3 x1 + 6 x + x4≥-4 2 Xj≥0（j=1,2，3,4） 其中，x3 ，x4为松弛变量，可以作为初始基变量，单纯形表见表4-17. 在表4-17中,b=-16<0,而y≥0,故该问题无可行解. 注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况. 若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解. 在计算机求解时,只有人工变量法,没有对偶单纯形法. 3.对偶问题的最优解 由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解. (1)设原问题(p)为 Min z=CX
s.t. ?? ?≥=0 X b AX 则标准型(LP)为 Max z=CX s.t. ? ??≥=0X b AX 其对偶线性规划（D ）为 Max z=b T Y s.t. ? ? ?≥=0X b AX 用对偶单纯形法求解（LP ），得最优基B 和最优单纯形表T （B ）。对于（LP ）来说，当j=n+i 时，有Pj=-e i ，c j =0 从而，在最优单纯形表T （B ）中，对于检验数，有 （σn+1，σn+2…σn+m ）=（c n+1，c n+2…，c n+m ）-C B B -1（Pn +1,Pn+2…,Pn+m ）=- C B B -1 (-I) 于是，Y*=（σn+1，σn+2…σn+m ）T 。可见，在（LP ）的最优单纯形表中，剩余变量对应的检验数就是对偶问题的最优解。 同时，在最优单纯形表T （B ）中，由于剩余变量对应的系数 所以 B -1 =（-y n+1，-y n+2…-y n+m ） 例4-8 求下列线性规划问题的对偶问题的最优解。 Min z =6x 1+8x 2 s.t. x 1 + 2x 2≥20 3 x 1 + 2x 2≥50 Xj ≥0（j=1,2） 解： 将问题转化为 Max z =-6x 1-8x 2 s.t. -x 1 — 2x 2 + x 3=20 -3 x 1 - 2x 2+ x 4 =50 Xj ≥0（j=1,2，3,4）
第三章线性规划对偶理论与灵敏度分析习题 一、 思考题 1． 对偶问题和对偶变量的经济意义是什么 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么 3．什么是资源的影子价格它和相应的市场价格之间有什么区别 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化有多少种不同情况如何去处理 二、 判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0对偶单纯形法
1.对偶单纯形法 2.F(x)=3x1+4x2+5x3 X1+2x2+3x3>=5 2x1+2x2+x3>=6 xi>=0 f=[3;4;5]; A=[-1 -2 -3 -2 -2 -1]; b=[-5;-6]; lb=zeros(3,1); [x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb) x = 1.0000 2.0000 0.0000 fval = 11.0000 exitflag = 1 output = iterations: 8 algorithm: 'large-scale: interior point' cgiterations: 0 message: 'Optimization terminated.' lambda = ineqlin: [2x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double] x, lambda.ineqlin, lambda.lower x = 1.0000 2.0000 0.0000 ans = 1.0000 1.0000 ans = 0.0000 0.0000 1.0000
2.单纯形法 f(x)=-9x1+-16x2 x1+4x2+x3=80 2x1+3x2+x4=90 xi>=0 f=[-9;-16;0;0]; Aeq=[1 4 1 0 2 3 0 1]; beq=[80;90]; lb=zeros(4,1); [x,fval,exitflag,output,lambda] = linprog(f,[],[],Aeq,beq,lb) Optimization terminated. x = 24.0000 14.0000 0.0000 0.0000 fval = -440.0000 exitflag = 1 output = iterations: 5 algorithm: 'large-scale: interior point' cgiterations: 0 message: 'Optimization terminated.' lambda = ineqlin: [0x1 double] eqlin: [2x1 double] upper: [4x1 double] lower: [4x1 double] x, lambda.ineqlin, lambda.lower x = 24.0000 14.0000 0.0000 0.0000 ans = Empty matrix: 0-by-1 ans =
第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为
min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
运筹学作业2（第二章部分习题）答案 2．1 题 （P . 77） 写出下列线性规划问题的对偶问题： （1）123123123123123m ax 224..34223343500,z x x x s t x x x x x x x x x x x x =++? ? ++≥??++≤? ? ++≤? ≥≥??无约束，； 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 123123123123123m ax 235..223424334,0,0w y y y s t y y y y y y y y y y y y =++??++≤??++≤? ?++=? ≥≤≤?? （2）111 1 m in ,1,,,1,,0,1,,;1,,m n ij ij i j n ij ij i j n ij ij j j ij z c x c x a i m c x b j n x i m j n ====?=? ? ? ==????==??≥==??∑∑∑∑ 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 11m ax 1,,;1,,m n i i j j i j i j ij i w a u b v u v c i m j n u ==? =+???+≤? ?==? ??∑∑ j 无约束，v 无约束 2．2判断下列说法是否正确，为什么？ （1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。 因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。
例如原问题 12 12212m ax 31..30,0z x x x x s t x x x =++≥??≤? ?≥≥?有可行解，但其对偶问题 12 11212m in 33..10,0w y y y s t y y y y =+≥??+ ≥??≤≥?无可行解。 （2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错，如（1）中的例子。 （3） 在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可 行解的目标函数值一定不超过其对偶问题可行解的目标函数值。 答：错。正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。 （4） 任何线性规划问题具有唯一的对偶问题。 答：正确。 2．5给出线性规划问题 123 123123123123m ax 221.. 22 0,0,0z x x x x x x x x x s t x x x x x x =+++-≤? ?-+=?? ++≥??≥≥≥? 写出其对偶问题；（2）利用对偶问题性质证明原问题目标函数值1z ≤ 解：（1）原问题的对偶问题为： 123 123123123123m in 22212.. 10,,0w y y y y y y y y y s t y y y y y y =++++≥? ?-+≤?? -++=? ?≥≤?无约束 （2）取()011T y =，既1230,1,0y y y ===，经验证，()011T y =是对偶问题的一个可行解，并且1w =。由对偶问题的性质可得1z w ≤= 2．9 用对偶单纯形法求解下列线性规划问题： （2）123 123123 123m in 524324..63510,,0z x x x x x x s t x x x x x x =++++≥??++≥??≥? ,
强对偶性，运筹学中的术语。如果x*是原问题的最优解，y*是对 各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢 强对偶性。强对偶性。运筹学中的术语。如果x*是原问题的最优解。对偶y*是对偶问题的最优解。那么有如下关系：cx*=y*b。 中文名,强对偶性。别称,cx*=y*b。应用学科,运筹学。 定律定义。矩阵形式的线性规划问题的原问题为：。 其对偶问题为：若原问题及其对偶问题均有可行解。则两者均具有最优解。且它们最优解的目标函数值相等：其中X*和Y*是最优解。T上标表示转置。 推导过程。由于原问题和对偶问题均有可行解。 根据弱对偶性的推论。原问题的目
标函数值具有上界。而对偶问题的目标函数值具有下界。因此不可能具有无界解的情况。而且“可行解”的前提也保证了没有无解的情况。所以两者都一定具有最优解。既然原问题有最优解。初始单纯形表进过若干步迭代变成最终单纯形表后。对偶其非基变量的检验数均小于等于0：。将上式变形。T≥CT。ATT≥CT。将此式与对偶问题的约束条件ATY≥CT做比较。 可以看出初始基变量Xs的检验数-CBB-1的相反数。若原问题是极小化问题Xs的检验数即为CBB-1。恰好是其对偶问题的一个可行解Y=T。由此可知。原问题有最优解时。其对偶问题有可行解使得对偶问题的可行解的目标函数值w等于原问题最优目标函数值z。w=YTb=CBB-1b=z存在两者的可行解。使得原问题和对偶问题的的目标函数值相等。由对偶问题的最优性。这时令两者的目标函数值相等的可行解均为最优解。即此时原问题和对偶问题它们最优
解下的目标函数值相等。 适用范围。无论原问题是极大化问题和极小化问题均适用。 定律定义推导过程 由于原问题和对偶问题均有可行解，根据弱对偶性的推论，原问题的目标函数值具有上界，而对偶问题的目标函数值具有下界，因此不可能具有无界解的情况，而且“可行解”的前提也保证了没有无解的情况，所以两者都一定具有最优解。 将上式变形，T≥CT，ATT≥CT，将此式与对偶问题的约束条件ATY≥CT做比较，可以看出初始基变量Xs的检验数-CBB-1的相反数，若原问题是极小化问题Xs的检验数即为CBB-1，恰好是其对偶问题的一个可行解Y=(CBB-1)T。由此可知，原问题有最优解时，其对偶问题有可行解使得对偶问题的可行解的目标函数值w等于原问题最优目标函数值z，w=YTb=CBB-1b=z 存在两者的可行解，使得原问题和
运筹学大作业单纯性法 与对偶单纯性法比较 Pleasure Group Office【T985AB-B866SYT-B182C-BS682T-STT18】
对偶单纯形法与单纯形法对比分析1．教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解 2．教学内容： 1）对偶单纯形法的思想来源 2）对偶单纯形法原理 3．教学进程： 1）讲述对偶单纯形法解法的来源： 所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 2）为什么要引入对偶单纯形法： 单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点： （1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算； （2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。 由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。 我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就
第三章运输问题 一、学习目的与要求 1、掌握表上作业法及其在产销平衡运输问题求解中的应用 2、掌握产销不平衡运输问题求解方法 二、课时 6学时 第一节 运输问题及其数学模型 一、运输问题的数学模型 单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？ 表中x ij i j ij i j 如果运输问题的总产量等于其总销量，即有 ∑∑===n j j m i i b a 1 1 则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。 产销平衡运输问题的数学模型如下：
???? ? ????≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 1 111 1 ij m i j ij n j i ij m i n j ij ij x n j b x m i a x t s x c z 这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。 二、运输问题数学模型的特点 1、运输问题有有限最优解，即必有最优基本可行解 2、运输问题约束条件的系数矩阵A 的秩为(m+n-1) 该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j 对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1 (2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。 此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和
用对偶单纯形法求对偶问题的最优解 摘要：在线性规划的应用中，人们发现一个线性规划问题往往伴随着与之配对的另一个线性规划问题.将其中一个称为原问题，另一个称为对偶问题.对偶理论深刻揭示了原问题与对偶问题的内在联系.由对偶问题引申出来的对偶解有着重要的经济意义.本文主要介绍了对偶问题的基本形式以及用对偶单纯形法求解对偶问题的最优解. 关键词：线性规划；对偶问题；对偶单纯形 Using Dual Simplex Method To Get The Optimal Solution Of The Dual Problem Abstract：In the application of the linear programming，people find that a linear programming problem is often accompanied by another paired linear programming problem. One is called original problem. Another is called the dual problem. Duality theory reveals the internal relations between the dual problem and the original problem. The solution of the dual problem is of a great economic significance. In this paper，we mainly discuss the basic form of the dual problem and how to use dual simplex method to get the optimal solution of the dual problem. Key words: linear programming；dual problem；dual simplex method 1 引言 首先我们先引出什么是线性规划中的对偶问题.任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题.每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系.下面将讨论线性规划的对偶问题的基本形式以及用对偶单纯形法求最优解.在一定条件下，对偶单纯形法与原始单纯形法相比有着显著的优点. 2 对偶问题的形式 对偶问题的形式主要包括对称形对偶问题[]3和非对称性对偶问题. 2.1对称形对偶问题 设原线性规划问题为 Max 1122... n n Z c x c x c x =+++