◆线性规划。
lp数学模型】
max/min z =c1x1 + c2x2 + cnxn
满足(a1,1)x1+(a1,2)x2+..a1,n)xn≤（≥b1(a2,1)x1+(a2,2)x2+..a2,n)xn≤（≥b2...
am,1)x1+(am,2)x2+..a1,m)xn≤（≥bmxj≥0，对一切j
本章单纯形算法，将针对目标为求极小值且约束都转换为等式的问题而设计。
算法思想】一、求最优解。
.找出线性规划问题的初始基本可行解x，列出初始单纯形表。单纯形表的特点是，解的变量对应的约束方程系数构成单位矩阵。
如有线性规划问题。
min z=-40x1-45x2-24x3满足2x1+3x2+x3+x4=1003x1+3x2+2x3+x5=120xj≥0, j=1,2,3
如果约束全部都是“≤”型，那么松驰变量的约束系数恰构成单位矩阵，即松驰变量构成了基变量。如果表中没有单位矩阵，则可加入人工变量，以形成单位矩阵。但需保证在最优解中不包含任何人工变量。
其初始单纯形表为。
cj-40 -45 -24 0 0c′x′b┃x1 x2 x3 x4 x50 x4 100┃2 3 1 1 0x5 120┃3 3 2 0 1z┃0 0 00 0cj-zj┃4045 240 0
.判别x是否已达到最优。判断的准则是：如果还存在任一非基变量，将它引入基内，即令它取大于零的值，能使目标函数值有所改进，那么x就不是最优解。即对于求极小值问题，存。
m在xj，有cj-σ ci'aij＜0，则现行基本可行解x尚未达到最优。i=1
式中ci,为第i行基变量目标函数系数。
对于现行基本可行解，如果令非基变量xj进入基，那末xj=1时第i行基变量的减少值就等于aij，所以检验数中第2项表示引入xj=1后目标函数的减少值。
.如果x未达到最优，则可用一非基变量换出一个基变量，得到一个新的基本可行解x，并通过初等变换使单纯形表中的新的基变量的系数构成单位矩阵，然后再做新的一轮判别计算。计算将一直这样继续下去，直至达到最优。
.保证最优解中不包含人工变量的方法有两种：大m法和两阶段法。本程序采用的是两阶段法。第一阶段，制造出一个新的目标函数来求解。对于求极小值问题，新。
目标函数仅包含人工变量，并令系数为1。如果原问题有最优解，这个阶段的最优解为零，且不含人工变量，如不为零则原问题不可行。如果第一阶段得到不含人工变量最优解，则立即转入第二阶段，恢复原目标函数，开始新的迭代计算。
.既然xj=1时，第i行基变量的减少值为aij，因此，在迭代过程中，如果存在xj，有ai,j≤0，i=1,2,..m，那末要将xj引入基中，现行解中任何一个基变量的值都不会变为零，即不会退出现行基。
此时，原问题的解无界，即无最优解。
二、灵敏度分析。
在求解一个线性规划问题时，方程系数和常数项(a,b,c)当然是作为常数看待的。但实际上这些数据并不完全是确知的，我们采用了估计值，那么结果可靠吗？或者在花了很大气力求解一个问题之后，有关数据发生了变化，是不是需要再计算一次呢？
在此情况下，就要求确定这些数据在什么范围变化时，问题的最优解保持不变（指最优解的基变量构成保持不变），从而不必为每一种可能的数据变动，都去进行一次从头至尾的迭代计算。
1b的灵敏度分析。
当某个bi发生变化时，将影响基变量的取值（增大或减小）。为保持基变量的构成，这种变化应以不致使任何一个基变量退出基为度。据此，可推导出以下计算公式：
如果xn+i为松驰变量，则bi的增加值-bk'δbi≥max━━━k ak' ,n+i
ak' ,n+i>0
bk'δbi≤min━━━k ak' ,n+i
ak' ,n+i<0
式中的bk',ak',n+i均指最优单纯形表中的数据，n为实在变量数（不包括松驰和负松驰（多余）变量）。
如果xn+i为负松驰变量，则bi的增加值。
bk'δbi≥max━━━k ak' ,n+i
ak' ,n+i<0
bk'δbi≤min━━━k ak' ,n+i
ak' ,n+i>0
对于等式约束，如将它分解为≥和≤两个约束，亦可求出其右端值的bi变动范围。
2c的灵敏度分析。
目标方程的某个系数cj发生变化时，对现行基变量的影响可分两种情况讨论：
a. cj对应的基变量是非基变量。
此时，对于求极大值的线性规划问题，cj减少，不会引起基的变动；cj增加，则检验数cj-zj可能变为正数而使xj进入基。
据此，应有-∞≤cj≤-(cj-zj)
b. cj对应的变量是基变量。
当基变量的cj发生变化时，检验数行的每一个值都将发生变化。因此cj的变动，应不致使任何一个非基变量的cj-zj值变为正值（求极大问题），才能保持最优解的基不变。据此可以推出如下计算对应第k行基变量xk的目标方程系数增量δc'k的公式：
cj-zjδck'≥max━━━对非基变量xj ak' ,j
ak' ,j>0
cj-zjδck'≤min━━━对非基变量xj ak' ,j
ak' ,j<0
最后，还需指出一点，如在容许范围内变化，不仅基变量构成不会变化，且基变量的值也不会变化，因为基变量值的计算和目标函数无关。
运筹学试卷 物流运筹学
2012 2013学年第一学期。运筹学 试卷。试卷 自拟送卷人 唐文广打印 校对 唐文广。一 6分 已知线性规划模型。写出该问题的对偶问题。二 15分 用单纯形法求解下面线性规划问题 作1张表即可 三 10分 求解下面标准指派问题，其中效率矩阵为。四 15分 某项工程由a b i j k等11项工序...
运筹学试题与案例集 运筹学
20xx年运筹学试题与案例集 天津。全国运筹学精品课程建设与题库案例交流研讨会运筹学试题与案例集 内部交流资料 中国运筹学会教育普及工作委员会 天津运筹学会 天津工业大学 20xx年5月 全国运筹学精品课程建设与题库案例交流研讨会 2010.05 目录 第一部分运筹学试题4 试题 1 北京工商大学4...
运筹学作业
运筹学关于库存的分析。主讲 秦舟 200900709071 摘要 关键词编辑 梁海琳 200900709074 模型制作 软件求解 欧迅 200900709077 秦舟 200900709071 理论综述与结果分析 林建佳 200900709069 秦普满 200900709067 参考文献与结论 ...