第二节线性规划问题的图解法一、线性规划问题的几个基本概念1.可行解：满足所有约束条件的解，称为线性规划问题的可行解。2．最优解：满足目标函数式的可行解，称为线性规划问题的最优解。3.最优值：对应于最优解的目标函数之值：称为最优值。二、图解法「例41仍以前面的例1为例，它可以用下面的数学模型来表示：max Z =30x,+25x,[2xj +4x, ≤40①②s.t33x +2x, ≤30,5≥016
16
二、图解法·步骤：一建立平面直角坐标系，取x为横轴，x为纵轴一求满足约束条件的可行解区域·可行域：满足所有约束条件的解的公共部分所构成的可行解的集合·凸集：如果在形体内任意取两点连接一根直线，若线段上所有的点都在这个形体中一作目标函数的等值线簇，确定目标函数值增加方向一求出最优解17
17
二、图解法从图2-1可以看出·可行域：四边形OABC·最有解是如下两条直线的交点：2x +4x2= 40[3x) +2x2=30解此方程组得到B点的值为（5，7.5），即当x=5，x=7.5时，目标函数取得最大值Z-337.5二、图解法[例51用图解法解下面线性规划问题min Z =2x, +3x2[x +x, ≥350 ①s.t.②≥1252x+≤600③,x≥018
18
二、图解法三、线性规划问题解的形式与特点一唯一最优解一多重最优解：如果一个线性规划问题存在多重最优解，那么它至少有两个相邻的角顶可行解所对应的目标函数值相等，且达到最大值（或最小值）一无最优解·可行域为空·可行域是一个无限空间19
19
第三节?单纯形法一、单纯形法的基本原理（一）典型方程组2a,, -b, i-1, ,. mi+dim+1Xm+1+dim+2xm+2 +...+dinx, =bxix2+a2m+1xm+1+a2m+2xm+2+...+a2nx,=bXm+amm+1m++amm+2*m+2+..+amm*h=bm式中x,x，,x,是重新排序后的变量b,b2,,b"为非负常数、单纯形法的基本原理（二）基本变量：如果变量x在某一方程中系数为1，而在其它一切方程中的系数为零，则称x为该方程中的基本变量。否则为非基本变量。（三）基本解：在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解（四）基本可行解：基本变量为非负的一组基本解称为基本可行解。20
20