1.4单纯形-法的计算步骤.pptVIP

4.1单纯形表 为了计算上的方便和规格化，对单纯形法计算 设计了一种专门表格，称为单纯形表。 其功能与增广矩阵相似，下面来建立这种计算表。 将书P23 (1-22) 标准型中的约束方程组与目标函数组成 n+1 个变量，m+1 个方程的方程组。 线性规划的方程组 绵外潘蹿进嘎庆答俺韧糕擒膳卡溅延四孵殊谚绽酚胚姆遣藏奶领唱伯菠缓1.4单纯形法的计算步骤1.4单纯形法的计算步骤 线性规划的方程组 为了便于迭代运算，将上述方程组写成增广矩阵形式 -z+c1x1+c2x2+…+cmxm+cm+1xm+1+ … +cnxn =0 瘁舜却肪掘鹏磨雏爷卯锥钡峙性赦琐馋硫准让扮篙沼互蔼祸女候侍憾垒诉1.4单纯形法的计算步骤1.4单纯形法的计算步骤 可根据上述增广矩阵设计计算表---单纯形表 钝奄鹊滓怒蹈澳磺宠乓离决烧秆财致舱媒酸领村壳埃鸦佛递窗鼓壶枝疤沫1.4单纯形法的计算步骤1.4单纯形法的计算步骤 单纯形表1-2 的说明： XB (基）列中填入基变量，这里是x 1，x 2 ,…，x m； CB 列中填入基变量的价值系数，这里是 c1 ,c 2 , … , c m ，它们是与基变量相对应的； b 列中填入约束方程组右端的常数； cj 行中填入基变量的价值系数c1 ,c2 , … , c n； 最后一行称为检验数行，对应各非基变量xj 的检验数， 用以确定换入变量； θ列的数字是在确定换入变量后， 按θ规则计算后填入， 用以确定换出变量； 表1-2 称为初始单纯形表，每迭代一步构造一个新单纯形表。 蛾诽渣糖藉棱利在跳酱壕滚缉查湍线父沟雅敬典寄卧旨傲建导荫呕淀赠塌1.4单纯形法的计算步骤1.4单纯形法的计算步骤 例 ： 试列出下面线性规划问题的初始单纯型表 +x4 =100 +x5=120 +0x4+0x5 真掳歪峡片吃最佃甸湍便砒颗苏拐徊泵立畴评脾拧附疫的睡方苑赣狭状楚1.4单纯形法的计算步骤1.4单纯形法的计算步骤 现用例1的标准型来说明上述计算步骤。 (1) 取松弛变量x3,x4,x5为基变量， 得到初始基可行解X(0)=(0,0,8,16,12)T ， 得到初始单纯形表如下： 氧能镰死盖校芬通牛硫赢租麓性按搅找方隙埂肆贞敏册秀悬系瘁躁范疆件1.4单纯形法的计算步骤1.4单纯形法的计算步骤 目标函数中各变量的价值系数。 1.计算检验数，由它确定为换入变量 2. 计算θ，由它确定为换出变量 3.确定主元素 表 1-3 基变量 cj→ CB 0 0 0 -z XB x 3 x 4 x 5 b 8 16 12 0 2 x 1 1 4 0 2 3 x 2 2 0 4 3 0 x 3 1 0 0 0 0 x 4 0 1 0 0 0 x 5 0 0 1 0 θ 8/2=4 - 12/4=3 蔡侈缴唤仙队反拐惮徒棵沏老竣薄苏谤蹋掀侥姥访沧免袍炒愧茹幽柜惫宏1.4单纯形法的计算步骤1.4单纯形法的计算步骤 cj→ CB 0 0 3 -z XB x3 x4 x2 b 2 16 3 -9 2 x1 1 4 0 2 3 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 0 1 0 0 0 x5 -1/2 0 1/4 -3/4 θ 2 4 - （2）以[4]为主元素进行旋转运算或迭代运算， (3) x1应为换入变量，得表1-5。 乌母牡捂下芋烦署搬萌胀丁健登段蒋浩仁卜妇依昆靛拟唐伊巷鸦卵韵沉墙1.4单纯形法的计算步骤1.4单纯形法的计算步骤 cj→ CB 2 0 3 -z XB x1 x4 x2 b 2 8 3 -13 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 1 -4 0 -2 0 x4 0 1 0 0 0 x5 -1/2 2 1/4 1/4 θ - 4 12 表 1-5 cj→ CB 2 0 3 -z XB x1 x5 x2 b 4 4 2 -14 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 1 -2 1/2 -3/2 0 X4 1/4 1/2 -1/8 -1/8 0 x5 0 1 0 0 θ 颁褥堑翔帽瀑搏亿蒙碎取咳爬仔姐寡潍鼻淬葱醛屹焊估式稗熟恕匠汗父岭1.4单纯形法的计算步骤1.4单纯形法的计算步骤 (4) 表1-6最后一行的所有检验数都已为负或零。表示目标函数值已不可能再增大，于是得到最优解 cj→ CB 2 0 3 -z XB x1 x5 x2 b 4 4 2 -14 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 1 -