最优化方法单纯形表VIP免费

1.4.5单纯形表及其计算步骤知识点回顾针对线性规划问题，我们需要①知道问题是否有解②求出问题的基本解③确定问题的基本可行解④知道问题是否有最优解⑤确定问题的最优解知识点回顾理论上，穷举法可以帮我们求出最优解；但是，在基可行解很多且事先无法判断是否存在最优解的情况下，穷举法无法施行。1947年，美国数学家G.B.丹齐克迎来了新的黎明———单纯形法人物简介丹齐克，G.B.GeorgeBernardDantzig(1914～)美国数学家，美国全国科学院院士。线性规划的奠基人。1914年11月8日生于美国俄勒冈州波特兰市。在马里兰大学获数学和物理学学士学位。在密歇根大学获数学硕士学位。1946年在伯克利加利福尼亚大学数学系获哲学博士学位。1974年丹齐克在总结前人工作的基础上创立了线性规划,确定了这一学科的范围,并提出了解决线性规划问题的单纯形法。1937～1939年任美国劳工统计局统计员，1941～1952年任美国空军司令部数学顾问、战斗分析部和统计管理部主任。知识点回顾单纯形法是一种迭代算法，其主要步骤流程如下初始基可行解是最优解？输出最优解停止无最优解？生成更优的基可行解NNYY开始单纯形表法单纯形表法是指利用表格（单纯形表）计算基可行解和检验数的方法。它用将表格中数据进行初等行变换的方法取代之前利用当前基的逆矩阵计算出对应的基可行解及检验数的方法。这在一定程度上简化了计算并将结果直观地表达了出来。假设线性规划问题表示为：maxZ=CXs.t.AX=b,b≥0X≥0记A=(B,N)其中B是当前的基将目标行改写为：-Z+CX=0将Z视为由向量X所决定的变量，则原问题的原始数据可用下表表示：ZXBXNb0BNb-1CBCN0表格中间部分XB和XN为约束方程组的系数，第二行为约束条件的有关数据，第三行为目标行的有关数据对上表中的数据施以关于行的初等变换具体要求：基变量所对应的系数矩阵B化成单位矩阵E，且下一行中基变量对应的系数向量CB化为零向量具体操作：将上表中间行（即约束方程组系数增广矩阵）的各项同乘以当前基B的逆矩阵B-1,再将中间行各项乘以（-CB）后加到最后一行上得到的新表格即单纯形表，表格如下：ZXBXNb0EB-1NB-1b-10CN-CBB-1N-CBB-1N分别令N’=B-1NC’N=CN-CBB-1N（即C’N是非基变量XN所对应的检验数向量）b’=B-1bη’=-CBB-1N转换后的单纯形表如下：ZXBXNb0EN’b’-10C’Nη’为不失一般性，可假设b’≥0（可通过挑选换基迭代的主元而办到），则上表等价于：XB+N’XN=b’-Z+C’N=η’令非基变量XN=0，则有：XB=b’Z=-η’上式表明，若B是可行基，则b’的分量是基B所对应的基变量的值，而-η’则是对应的基可行解的目标函数值注：因为目标变量Z所在列的数据始终没有发生过变化，为使表中数据简明，可删除此列利用单纯形表求解线性规划的步骤例1求解线性规划问题maxZ=-3x1-2x2–x3+2x4s.t.x1-2x2+4x4=4x2+x3+2x4=5xj≥0,j=1,2,3,4①将线性规划标准化，并使之含有标准基（即一个与约束方程的个数同阶的单位矩阵）解：原问题已是标准形式的线性规划，其数据为：C=(c1,c2,c3,c4)=(-3,-2,-1,2)b=(b1,b2)T=(4,5)TA=(P1,P2,P3,P4)=1-2040112其中已含有一个标准基B0=(P1，P3)=E②按规定形式将原始数据填入表中（可不填Z列），并化为单纯形表x1x2x3x4b1-204401125-3-2-120将最后一行中的-3和-1用初等行变换化为0x1x2x3x4b1-2044011250-701617③检查非基变量的检验数σj,若所有的σj≤0，则当前的基可行解就是最优解，计算停止；④若存在某个σk>0，且所对应的列向量P’k没有正分量，则表明原问题不存在最优解，计算停止；在本例中，存在σ4=16>0，且所对应的列向量P’4存在正分量，所以原问题存在最优解。⑤若最大的正检验数为σk，则取xk为入基变量，并在对应的列向量P’k中确定一个正分量a’lk为主元，使之满足：b’l／a’lk=minb’﹛l／a’lk|a’lk>0﹜即表明原来基中的变量xl退出基。因为在本例中只有非基变量x4所对应的检验数σ4大于零且对应列向量P’4有正分量，在所得单纯形表中加入bi/ai4一列但是，上表中依旧存在正检验数σ4>0，且有a14=4>0，a24=2>0这里根据前面所提到的θ规则，有b1/a14=4/4=min{4/4,5/2}=min{b1/a14,b2/a24}所以应选a14为主元，为计算方便起见，习...