线性规划及单纯形.ppt

线性方程组的增广矩阵表示谢谢大家！它的初始可行基初始基本可行解初始基变量是松弛变量。初始可行解（只要满足非负条件）初始基本可行解（非基变量取值为零时）目标函数与最优性检验第一次迭代受资源的约束，400所对应的资源最紧张对目标函数贡献大（价值系数高）确定入基变量，应当是（Why），它的系数是4。确定出基变量，方法如下，得(Why)确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解01目标函数02第二次迭代添加标题确定换入基变量：确定换出基变量：添加标题不考虑零与负值0102确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解01目标函数02第三次迭代添加标题确定入基变量：确定出基变量：添加标题不考虑零与负值0102确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数这是最优解。最大目标函数值为2600。三、关于解的最优性检验设线性规划模型为AnnualWorkSummaryReport令基为B，并作相应的矩阵分割，从约束条件得代入目标函数得令则目标函数可写成可用σ（sigma）判断是否最优解，它叫做检验数。四、表格形式的单纯形法表的格式在表上的计算方法表上计算的原理表格单纯形法的实例：初始单纯形表430000001600250040025122.5010001000180050040043000logo单纯形表法求解430000001600250040025122.50100010001800500400043000第一次换基迭代3＝3－0×2－0×2.5－4×01600＝0×800+0×500+4×4004300000480050040000122.50100010-2-514002000不算16000300-4logo第二次换基迭代43000034400200400001010100-0.80.402-21200负值不算4002200000-1.22第三次换基迭代：最优解430000342006002000010100.51-0.5-0.4-0.40.4100260000-1-0.404.决策变量有上下界的转换例1.1的标准型t例1.2的标准型t1.2线性规划问题的图解法添加标题图解法添加标题单纯形法的思路添加标题可行解及可行解集的特性添加标题线性规划问题解的特点1.2线性规划问题的图解法图解法就是利用坐标图来求解线性规划问题，以例1.1的线性规划模型为例来介绍具体的求法。≤12≤8s.t.≤16≤12≥0O12345613245678412345613256O7854R1234561326O784QR12345613256O78PSPQRS123456132456O78PQRS123456132456O78PQRS123456132456O78(4,2)图解法求解线性规划问题的一般步骤建立直角坐标系找出所有约束条件所构成的公共区域，即可行域；改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。O12345613245678建立直角坐标系PQRS123456132456O78找出所有约束条件所构成的公共区域，即可行域；可行域PQRS123456132456O78(4,2)改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。可行域思考：当目标函数