单纯形法例题

单纯形法例题1、例1、目标函数maxz=2𝒙𝟏+3𝒙𝟐约束条件：{𝒙𝟏+𝟐𝒙𝟐≤𝟖𝟒𝒙𝟏≤𝟏𝟔𝟒𝒙𝟐≤𝟏𝟐𝒙𝟏，𝒙𝟏≥𝟎}解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量，𝑥3，𝑥4，𝑥5，并且它们都大于等于0.得到的标准形式为：maxz=2𝑥1+3𝑥2+0𝑥3+0𝑥4+0𝑥5{𝑥1+2𝑥2+𝑥3＝84𝑥1+𝑥4=164𝑥2+𝑥5＝12𝑥1，𝑥2，𝑥3，𝑥4，𝑥5≥0}然后要将其初始的单纯形表画出来：𝑐𝑗23000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥50𝑥381210040𝑥41640010-0𝑥5120[4]0013𝑐𝑗−𝑧𝑗23000由初始单纯形表可以看出，𝑥2为换入变量，而𝑥5为换出变量；然后根据：𝑎𝑖𝑗={𝑎𝑖𝑗−𝑎𝑙𝑗𝑎𝑙𝑘∗𝑎𝑖𝑘(𝑖≠𝑙)𝑎𝑙𝑗𝑎𝑙𝑘(𝑖=𝑙)}𝑏𝑖={𝑏𝑖−𝑎𝑖𝑘𝑎𝑙𝑘∗𝑏𝑙(𝑖≠𝑙)𝑏𝑙𝑎𝑙𝑘(𝑖=𝑙)}(也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值，否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2,故填入值应该为2。而𝜃𝑖则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该换入变量所在的列的所有值，得到𝜃𝑖列的值。𝑐𝑗23000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥50𝑥32[1]010-1/220𝑥4164001043𝑥2301001/4-𝑐𝑗−𝑧𝑗2000-3/4由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为𝑥1，换出变量为𝑥3，故得到的单纯形表如下：𝑐𝑗23000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥52𝑥121010-1/2-0𝑥4800-41[2]43𝑥2301001/412𝑐𝑗−𝑧𝑗00-201/4由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变量为𝑥5，换出变量为𝑥4：得到单纯形表如下：𝑐𝑗23000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥52𝑥141001/400𝑥5400-21/213𝑥22011/2-1/80𝑐𝑗−𝑧𝑗00-3/2-1/80此时可以发现检验数中没有大于0的数，表明已经得到了最优解，所以最优解是：（4,2,0,0,4），故目标函数值z=2*4+2*3=142、合理利用线材问题，现在要做100套钢架，每套用长为2.9m，2.1m，和1.5m的钢各一根，已知原料长7.4m，问应如何下料，使用的原材料最省；解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要2.9m长的钢100根，2.1m的钢100根，1.5m的钢100根。而一份原料长度是7.4m，它的截取的方法有多少种，我们可以用表格列举出来：长度/m下料根数截取方案123452.91122.12121.53132所用长度7.47.17.36.67.2剩余长度00.30.10.80.2求解的问题是关于如何去进行下料，使得原材料最省，也就是说如何搭配使用这些方案，使得剩余的总长度最少。由此，我们可以将目标函数和约束条件表述出来：目标函数：minz=0.3𝑥2+0.1𝑥3+0.8𝑥4+0.2𝑥5约束条件{𝑥1+𝑥2+2𝑥3=1002𝑥2+𝑥4+2𝑥5=1003𝑥1+𝑥3+3𝑥4+2𝑥5=100𝑥1，𝑥2，𝑥3，𝑥4，𝑥5≥0}首先可以写出线性方程组的矩阵形式：[112000201230132]发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：𝑥6，𝑥7，𝑥8，那么线性方程组可以表示为：{𝑥1+𝑥2+2𝑥3+𝑥6=1002𝑥2+𝑥4+2𝑥5+𝑥7=1003𝑥1+𝑥3+3𝑥4+2𝑥5+𝑥8=100𝑥1，𝑥2，𝑥3，𝑥4，𝑥5，𝑥6，𝑥7，𝑥8≥0}，目标函数可以表示为：minz=0𝑥1+0.3𝑥2+0.1𝑥3+0.8𝑥4+0.2𝑥5+M𝑥6+𝑀𝑥7+𝑀𝑥8转换为求目标最大化maxZ=−0𝑥1−0.3𝑥2−0.1𝑥3−0.8𝑥4−0.2𝑥5−M𝑥6−𝑀𝑥7−𝑀𝑥8然后列出初始单纯形表：(注意，加入人工变量之后，它所对应的系数为-M，而非0)𝑐𝑗0-0.3-0.1-0.8-0.2-M-M-M𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7𝑥8-M𝑥610011200100100-M𝑥710002012010--𝑥810[3]0132001100/M03𝑐𝑗−𝑧𝑗4M-0.3+3M-0.1+3M-0.8+4M-0.2+4M000换入变量为𝑥1，换出变量为𝑥8，得到单纯形表为：𝑐𝑗0-0.3-0.1-0.8-0.2-M-M-M𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7𝑥8-M𝑥6200/3015/3-1-2/310-1/3200/3-M𝑥71000[2]012010100/20𝑥1100/3101/312/3001/3-𝑐𝑗−𝑧𝑗0-0.3+3M-0.1+5/3M-0.8-0.2+4/3M00-4/3M换入变量为𝑥2，换出变量为𝑥7，得到的单纯形表为：𝑐𝑗0-0.3-0.1-0.8-0.2-M-M-M𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7𝑥8-M𝑥650/3005/3-3/2-5/31-1/2-1/310-0.3𝑥2500101/2101/20-0𝑥1100/3101/312/3001/3-100𝑐𝑗−𝑧𝑗00-0.1+5/3M-0.65-3/2M0.1-5/3M00.15-3/2M-4/3M换入变量为𝑥3，换出变量为𝑥6，得到的单纯形表为：𝑐𝑗0-0.3-0.1-0.8-0.2-M-M-M𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7𝑥8-0.1𝑥310001-9/10-13/5-3/10-1/5-0.3𝑥2500101/2101/200𝑥13010013/101-1/51/102/5𝑐𝑗−𝑧𝑗000-0.740-M+0.06-M+0.12-M-0.02所以，最优解为：（30,50,10，0,0,0,0,0）。也就是说最优的下料方案为：按照第一个方案下料30根，第二种方案下料50根，按照第三种方案下料10根。即需要90根原材料可以制造出100套钢架。3、某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下表：班次时间所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八个小时，问该公交线路至少配备多少名司机和乘务人员，列出这个问题的线性规划模型。解：目标函数：minz=𝑥1+𝑥2+𝑥3+𝑥4+𝑥5+𝑥6约束条件:{𝑥1+𝑥6≥60𝑥1+𝑥2≥70𝑥2+𝑥3≥60𝑥3+𝑥4≥50𝑥4+𝑥5≥20𝑥5+𝑥6≥30𝑥1，𝑥2，𝑥3，𝑥4，𝑥5，𝑥6≥0}4、利用单纯形算法求解线性规划问题目标函数为：MaxZ=4𝒙𝟏+3𝒙𝟐约束条件为：{𝟐𝒙𝟏+𝟐𝒙𝟐≤𝟏𝟔𝟎𝟎𝟓𝒙𝟏+𝟐.𝟓𝒙𝟐≤𝟐𝟓𝟎𝟎𝒙𝟏≤𝟒𝟎𝟎𝒙𝟏,𝒙𝟐≥𝟎}解：首先将线性方程组化为标准形式：添加松弛变量：𝑥3，𝑥4，𝑥5，得到的方程式为：目标函数：MaxZ=4𝑥1+3𝑥2+0𝑥3+0𝑥4+0𝑥5约束条件为：{2𝑥1+2𝑥2+𝑥3=16005𝑥1+2.5𝑥2+𝑥4=2500𝑥1+𝑥5=400𝑥1,𝑥2,𝑥3,𝑥4,𝑥5≥0}接着将初始单纯形表列出：𝑐𝑗43000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥50𝑥31600221008000𝑥4250052.50105000𝑥5400[1]0001400𝑐𝑗−𝑧𝑗43000由上表可以看出，𝑥1为换入变量，而𝑥5为换出变量。然后根据变换公式可以得到变换之后的单纯形表如下：𝑐𝑗43000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥50𝑥38000210-24000𝑥45000[2.5]01-52004𝑥1400100010𝑐𝑗−𝑧𝑗0300-4由上表可以看出，换入变量为𝑥2，换出变量为𝑥4，单纯形表如下：𝑐𝑗43000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥50𝑥3400001-4/5[2]2003𝑥22000102/5-2-4𝑥140010001400𝑐𝑗−𝑧𝑗000-6/52由上表可以看出，换入变量为𝑥5，换出变量为𝑥3得到的单纯形表如下：𝑐𝑗43000𝜃𝑖𝑪𝑩𝑿𝑩b𝑥1𝑥2𝑥3𝑥4𝑥50𝑥5200001/2-2/513𝑥2600011-2/504𝑥12001002/50𝑐𝑗−𝑧𝑗00-3-2/50由于，检验数均为非负，所以得到了最优解，且最优解为(200,600,0,0,200);故目标函数的最大值为：Z=2600