1.1问题的提出 上述两个问题具有的共同特征: 每一个线性规划问题都用一组决策变量(x1,x2…x,) 表示某一方案,这组决策变量的值代表一个具体方案 一般这些变量的取值是非负且连续的; ●都有关于各种资源和资源使用情况的技术数据,创造新 价值的数据; an,c1(i=1…m;j=1,…n) 存在可以量化的约束条件,这些约束条件可以用一组线 性等式或线性不等式来表示; 都有一个达到某一目标的要求,可用决策变量的线性函 数(称为目标函数)来表示。按问题的要求不同,要求目 标函数实现最大化或最小化
1.1 问题的提出 ⚫ 每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。 一般这些变量的取值是非负且连续的； ⚫ 都有关于各种资源和资源使用情况的技术数据，创造新 价值的数据； ⚫ 存在可以量化的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示; ⚫ 都有一个达到某一目标的要求，可用决策变量的线性函 数(称为目标函数)来表示。按问题的要求不同，要求目 标函数实现最大化或最小化。 ( ) n x ,x , x 1 2 a ;c (i , m; j , n ) i j j = 1 = 1 上述两个问题具有的共同特征：
11问题的提出 决策变量及各类系数之间的对应关系 决策变量 资源 xX1 X n 11 12 b 活 2 21 a 22 a, b 2n 动 mI a m2 价值系数 2
1.1 问题的提出 n m m m n m n n n c c b b b a a a a a a a a a m x x x 1 2 2 1 1 2 2 1 2 2 2 1 1 1 2 1 1 2 c 2 1 价值系数 动 活 资 源 决策变量 决策变量及各类系数之间的对应关系
11问题的提出 线性规划模型的一般形式 目标涵数 max(min)2=C,+C,x2+.+Cmn(1.1) 约束条件 a1x1+a12x2+…+a1nxn≤(=,≥)b 21x1+a2)x2+…+a2nxn≤(=,2≥)b2 anm1x1+an2x2+……+amxn≤(=,>)b x …,xn≥0 1.3)
1.1 问题的提出 x ,x , , x ( . ) a x a x a x ( , )b ( . ) a x a x a x ( , )b a x a x a x ( , )b max(min) z c x c x c x ( . ) n m m m n m n n n n n n 0 1 3 1 2 1 1 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 + + + = + + + = + + + = = + + + 约束条件 目标函数 线性规划模型的一般形式
1.2图解法 12图解法 例1是一个二维线性规划问题,因而可用作图法直观地进行求 解。 22 max 2=2x,+3x 4x1=16 x1+2x2≤2 4x2=12 16 4x2≤12 x1,x2≥0 Q1 0
1.2 图解法 1.2 图解法 例1是一个二维线性规划问题，因而可用作图法直观地进行求 解。 + = + 0 4 12 4 16 2 2 2 3 1 2 2 1 1 2 1 2 x ,x x x x x max z x x
1.2图解法 max z=2 x, +3 2 x1+ 33 表示一簇平行线 Q2(4,2) 目标值在(4,2)点,达到最大值14
1.2 图解法 表示一簇平行线 3 3 2 2 1 z x = − x + 2 1 3 2 max z = x + x 目标值在（4，2）点，达到最大值14