单纯形法原理及例题

1、5.4 单纯形法一. 问题概述当m和n很大时, 顶点数目会很大, 例 n=100, m=50时, 顶点数目可达1029.问题: 从一个容易找到的顶点出发, 能否经过有限的几步, 最快找到最优解对应的顶点?回顾前例的产品生产问题.约束条件: 原料限制: 工时限制: 非负条件: x1, x2 , x3, x40令 得p5可用pi (i=1,4) 的线性组合表示. xi视为系数, 存在无穷组xi可使上式成立. 现在的目标是为找到使目标函数有最优值的最优组xi.因p5是二维向量, 可用两个线性无关的向量的线性组合表示, 则系数xi是唯一确定的, 对应于基本解 (注: 基本解和基本可行解的关系).例:

2、得 这里 定义为基变量, 定义为基向量.单纯形法的基本原理: 不断地更换基变量和基向量(对应于不断地更换顶点). 这种变换是在对应于可行区域顶点的各组基本可行解中找出最优解. 寻找起始点:做为基向量, 基本矩阵为易得 以及 对应于a点, 目标值 z/=-z=-6x1-4x2=0 (即两种产品均未安排生产).目标是通过选xi (i=1,4) 使z增长(或使-z减少)最快. x1增加一个单位, 使-z减少6个单位, x2增加一个单位, 使-z减少4个单位, 所以选择x1, 使其从0增大(即使x1进基).x1的增大受到限制, 因为当x2=0, x1=100/2=50时, 使 x3=0 (原料剩余量,

3、 用完).当x2=0, x1=120/4=30时, 使 x4=0 (工时剩余量, 用完).所以, x1=30时, 已使x4=0, x1进基增长, x4离基减少.由约束条件, 得 (1)回顾: (2)消去x1, 得 (3)目标函数 z/+6x1+4x2=0 (注z/=-z) (4) (4)中消去x1, 得 z/+ x2- x4= -180 (5)即当x1=30, x2=0, z/=-180 (即 z=180) 注: 现从a点移至d点. 问题: 能否进一步减少z/?由(5)式得知, 因为x2的系数为正, 则x2由0增大, 会使z/ 进一步减少. 由(3)式和(1)式可得x2增大受到限制,当x2=4

4、0/2=20时, 使x3=0, (注x4已经为零 )当x2=30/(1/2)=60时, 使x1=0, 所以x2只能增大到20.由(3)式得, (6)考虑 (1)式, 消去x2, 得 (7)由(5)式减去(6)式可得, (8)由(7)式, 基变量, 非基变量, z/=-200.由于(8)式中x的系数均为负, z/无法再减少, 所以z/=-200, 即z=200. 单纯形法的主要思路:1) 先找出初始基本可行解, 通常选个决策变量为零, 而松弛变量等于约束方程右边值作为初始解. 2) 改进目标值进行换基. 选择目标方程中系数为正而且绝对值最大的那一项对应的变量x作为基变量. 再计算当它增加时, 将原来的首先减为零的变量做为离基变量. 然后将方程进行交换, 使进基变量在这一方程中的系数为1, 在其余方程(包括目标方程)中的系数为零(以利于迅速求得基变量值). 这是目标值将得到改善. 3) 然后进一步查看目标值能否再减少. 若目标方程中变量x的系数仍有正数, 则选最大的一项进行换基, 直到所有系数为负, 目标值无法再进一步改进为止. 使用单纯形表法进行系数演算:一般情况:设线性规划问题已化为下列形式:将