单纯形法例题

1、单纯形法例题时间:2021.03.01创作：欧阳语2、例 1、目标函数 maxz=2xi+3x2fXt + 2X2 w 8、4xi W 164x2 W 12约束条件：X, Xi M 0解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量,X3 X4X5.并且它们都大于等于0.得到的标准形式为:maxz=2xi+3X2+0x3+0x4+0xs然后要将其初始的单纯形表画出来:ci23000qCb&bX1x2x3x4x50x38120040X41640010-0X512000132L±00由初始单纯形表可以看出2为换入变量，而勺为换出变量；然后根据:（也就是如果与主

2、元素同行”则用现在的值除以主元素 即可得到即将要填入的值，否则，就用现在的值减去 与主元素构成矩形的边角上的值的乘积再除以主元素 之后的值。例如：上面的第一行所对应的b值为 8(12*2)/4二2,故填入值应该为2。而则是由我们根据 非基变量的检验数的大小，挑选出最大的那个，作为 换入变量，然后用b的值除以该换入变量所在的列的 所有值,得到咧的值。ci23000%CBXBbX1x2x3X4x50x32KB010-1/220x4164001043x2301001/4-Cj-Zj2000-3/4由于在检验数中仍然存在大于等于0的数，而且P1 ,P5的坐标中有正分量存在,所以需要继续进行迭代运通过观

3、察可以看出主元素为1,换入变量为勺，换出变量为勺，故得到的单纯形表如下:ci23000CbXbbXx2x3X4x52X121010-1/2-0X48004m43X2301001/41200201/4由于检验数中存在正数，且P5和P3中有正分量存在,所以需要继续迭代(换入变量为勺，换出变量为":得到单纯形表如下：ci230000、CbXbbXx2x3X4x52X11001/40040021/213X22011/2-1/80ci_zi003/2-1/80此时可以发现检验数中没有大于0的数，表明已经得到了最优解,所以最优解是:(420Q4 ),故目标函数值 z=2*4+2*3二 143、合

4、理利用线材问题,现在要做100套钢架,每套用长 为2.9m , 2.1m ,和1.5m的钢各一根，已知原料长 7.4m z问应如何下料，使用的原材料最省；解：首先我们必须要清楚该问题的需要设立的变量是 什么。我们分析一下问题,做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求解的问题是关于如何去进行下料,使得原材料最省, 也就是说如

5、何搭配使用这些方案，使得剩余的总长度 最少。由此，我们可以将目标函数和约束条件表述出 来：目标函数：minz=0.3x2+0.1x3+0.8x4+0.2x5X + X2 + 2X3 = 100约束条件2x2 + X4 + 2x5 = 10° 3xi + X3 + 3x4 + 2x5 = 100 x2. x3, x4> X5 M 0首先可以写出线性方程组的矩阵形式:现不存在单位矩阵”所以要采用人造基的方式”也就是要添加人工变量:X® X7. X8 z那么线性方程组可以表示为,目标函数可以表示X + X2 + 2X3 + X6 二 1002x2 + X4 + 2x5 +

6、X7 二 1003X1 + X3 + 3X4 + 2X5 + X8 二 100xb x2, X3, X4. x5, x6, x7. X8 M 0为:minz=°xi+0.3x2+0.1x3+0.8x4+0.2x5+Mx6+ Mx8转换为求目标最大化maxZ= " Oxi 03%2 - 0.1x3 * 0.8x4 ° 0.2x5 Mx6 Mx7- Mxs然后列出初始单纯形表：（注意，加入人工变量之后,它所对应的系数为而非0）q0-0.3-0.1-0.8-0.2MMMCBXbbXx2x3X4X5x6X7X8MX610011200100100MX710002012010

7、-Mx8罗R0132001100/3Cjp4M-0.3+3-0.1+3M-0.8+4M-0.2+4M000换入变量为勺，换出变量为七，得到单纯形表为：ci0-0.3-0.108-0.2-M-M-MqCbXbbX1x2x3x4x5x6x?x8Mx6200/3015/3-1-2/310/3200/3MX71000012010100/20X1100/3101/312/3001/3-CjZj0-0.3+3M-0.1+5/3M0.8-0.2 +4/3M004/3M换入变量为迄，换出变量为><7 ,得到的单纯形表为：换入变量为勺，换出变量为心z得到的单纯形表为：ci0-0.3-0.1-0.8-

8、0.2-MCbXbbX1x2x3x4x5x6x?x80.1x310001-9/103/5-3/10J/50.3x2500101/2101/200X13010013/101-1/51/102/5CjT000-0.740-M +0.06-M +0.12-M-0.02所以，最优解为：（30,50,10,0Q0Q0 也就是说最 优的下料方案为：按照第一个方案下料30根，第二种 方案下料50根，按照第三种方案下料10根。即需要 90根原材料可以制造出100套钢架。4、某昼夜服务的公交线路每天各时间区段内所需司机和欧阳语创编乘务人员数如下表:班次时间所需人数16:00-10:0060210:00-14:0

9、070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030设司机和乘务人员分别在各时间区段一开始时上班， 并连续工作八个小时，问该公交线路至少配备多少名 司机和乘务人员，列出这个问题的线性规划模型。解：目标函数:minz=x1 + x2 + x3 + x4 + x5 + x6X + X6 M 60Xi +X2 三 70X2 + X3 M 60x3 + x450x4 + x520X5+X6 M 30约束条件:x2. x3. x4. x5. x6 A 05、利用单纯形算法求解线性规划问题目标函数为：MaxZ=4xi+3x22x1 + 2x2 W

10、 16005xt + 2.5x2 W 2500Xi w 400约束条件为：xvx2 > 0解：首先将线性方程组化为标准形式:添加松弛变量:X3 , X. X5 ,得到的方程式为：目标函数：Max Z=4xi+3x2+0x3+0x4+0x52xt + 2x? + X3 = 16005X + 2.5x2 + x4 = 2500约束条件为:Xj + x5 = 400xvx2,x3, x4,x5 > 0接看将初始单纯形表列出:Cj43C0c0、CbXbbX1x2X3X4X50X31600221008000X4250052.50105000X5400I1J000140043000由上表可以看出，"为换入变量，而><5为换出变量。然 后根据变换公式可以得到变换之后的单纯形表如下：43C00CbXbbX1x2X3X4X50X38000210-24000X4500012501-52004X1400100010ci_zj03004由上表可以看出，换入变量为边，换出变量为"，单纯 形表如下：Cj4300cCBXbbX1X2;<50x3400001-4/52003x22000102/52-4X140010001400000-6/5箜由上表可以看出，换入变量为§ ,换出