SHUFE 第一节线性规划一般模型 三、线性规划的一般模型 用一组非负决策变量表示一个决策问题, 存在一定的等式或不等式的线性约束条件, 有一个希望达到的目标,可表示成决策变量的线性 函数。可能是最大化,也可能是最小化。 线性规划一般模型的代数式为: max(minz=cu +Cxc2+.+cr a1x1+a1x2+…+a1rxn≤C,=)b1 22 x2+…,+a2rxn≤C,=)b2 mx1+anm2x2+…,+umxn≤C2,=)bm xpx2…,xn≥(≤)0 11海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 11 第一节 线性规划一般模型 • 用一组非负决策变量表示一个决策问题， • 存在一定的等式或不等式的线性约束条件， • 有一个希望达到的目标，可表示成决策变量的线性 函数。可能是最大化，也可能是最小化。 • 线性规划一般模型的代数式 为： 三、线性规划的一般模型 max(min)Z=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn ≤(≥,＝)b1 a21x1+a22x2+…+a2nxn ≤(≥,＝)b2 … … … … … am1x1+am2x2+…+amnxn≤(≥,＝)bm x1 ,x2 ,…,xn ≥(≤)0
SHUFE 第二节线性规划的图解法 、图解法的基本步骤 图解法即是用图示的方法来求解线性规划问题。 个二维的线性规划问题,可以在平面图上求解, 维的线性规划则要在立体图上求解,这就比较麻 烦,而维数再高以后就不能图示了。 12上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 12 第二节 线性规划的图解法 • 图解法即是用图示的方法来求解线性规划问题。 • 一个二维的线性规划问题，可以在平面图上求解， 三维的线性规划则要在立体图上求解，这就比较麻 烦，而维数再高以后就不能图示了。 一、图解法的基本步骤
SHUFE 第二节线性规划的图解法 1.可行域的确定 满足所有约束条件的解的集合,称之为可行域。即所有约束 条件共同围城的区域 例1的数学模型为 x1=8 marz=3x, +5 x2 C(4,6) 2x,=12 <8 2x2≤12 S t B 3x1+4x2≤36 x1≥0,x2≥0 0 A 12 3x1+4x2=36 五边形 OABCD内(含边界)的任意一点(x1,x2)都是满足所有 约束条件的一个解,称之可行解 13上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 13 第二节 线性规划的图解法 1. 可行域的确定 • 例1的数学模型为 maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 S.t. x1 =8 2x2 =12 3x1 +4 x2 =36 x1 x2 4 8 12 3 6 9 0 A B D C(4,6) • 五边形OABCD内(含边界)的任意一点(x1，x2 ) 都是满足所有 约束条件的一个解，称之可行解。 • 满足所有约束条件的解的集合，称之为可行域。即所有约束 条件共同围城的区域
SHUFE 第二节线性规划的图解法 2.最优解的确定 目标函数z=3x1+5x2代表以z为参数的一族平行线。 x1=8 C(4,6) 2x2=12 B Z=42 z15 A 2 3x1+4x2=36 等值线:位于同一直线上的点的目标函数值相同 ·最优解:可行解中使目标函数最优(极大或极小)的解 14上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 14 第二节 线性规划的图解法 2. 最优解的确定 Z=30 Z=42 Z=15 • 目标函数 Z= 3x1 +5 x2 代表以Z为参数的一族平行线。 x1 =8 2x2 =12 3x1 +4 x2 =36 x1 x2 4 8 12 3 6 9 0 A B D C(4,6) • 等值线：位于同一直线上的点的目标函数值相同。 • 最优解：可行解中使目标函数最优(极大或极小)的解
SHUFE 第二节线性规划的图解法 几点说明 由线性不等式组成的可行域是凸集(凸集的定义是 集合内部任意两点连线上的点都属于这个集合)。 可行域有有限个顶点。设规划问题有n个变量,m个 约束,则顶点的个数不多于Cm个。 目标函数最优值一定在可行域的边界达到,而不可 能在其内部。 15上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 15 第二节 线性规划的图解法 • 由线性不等式组成的可行域是凸集(凸集的定义是： 集合内部任意两点连线上的点都属于这个集合)。 • 可行域有有限个顶点。设规划问题有n个变量，m个 约束，则顶点的个数不多于Cn m个。 • 目标函数最优值一定在可行域的边界达到，而不可 能在其内部。 二、几点说明