运筹学_线性规划.ppt

2016-10-61?1. 线性规划问题及其数学模型?2. 线性规划的图解法?3. 线性规划问题的标准形式?4. 线性规划的解集特征?5. 线性规划的单纯形法?6. 单纯形法的进一步讨论2016-10-62线性规划问题及其数学模型?资源合理利用问题:第5页例2-1?质量检验问题:第6页例2-2?线性规划数学模型的一般形式2016-10-63资源合理利用问题:第5页例2-1 1. 决策变量:x1和x2 2. 目标函数:max (2 x1+3 x2) 3. 约束条件:10x1+20 x2 ? 80 4 x1 ? 16 6 x2 ? 18x1,x2 ? 02016-10-64质量检验问题:第6页例2-2 :x1和x2 :min(40x1+36 x2):5x1+3 x2? 45x1? 8 x2? 10x1,x2 ? 02016-10-65线性规划数学模型的一般形式 1. 决策变量是非负变量;2. 目标函数是线性函数;3. 约束条件是线性等式或不等式组。一般形式为:max(min)(c1x1+ c2x2 +…+cn xn)a11x1+ a12x2 +…+ a1n xn?(=,?) b1a21x1+ a22x2 +…+ a2nxn?(=,?) b2……am1x1+ am2x2 +…+ amn xn?(=,?) bmx1 ,x2 ,…,xn? 02016-10-66线性规划的图解法?:只能求解具有两个变量的线性规划问题。?:图解法只能求解具有两个决策变量的线性规划问题,其应用具有很大的局限性,因此学习图解法的目的并非是要掌握一种线性规划问题的求解方法,而是要通过图解法揭示线性规划问题的内在规律,为学习线性规划问题的一般算法(单纯形法)奠定基础。???-10-67线性规划有关解的几个概念 1. 可行解:满足约束条件的一组决策变量的取值;2. 可行域:可行解所构成的集合;3. 最优解:使目标函数达到极值的可行解;4. 最优值:与最优解相对应的目标函数的取值。2016-10-68图解法的基本步骤 ;,用标号和箭线表明约束条件的顺序和不等号的方向;;。:第7页例2-3:用图解法求解例2-1 :第8页例2-4:用图解法求解例2-22016-10-69用图解法求解例2-1x1x2432101 2 3 4 5 6 7 82016-10-610用图解法求解例2-1x1x2432101 2 3 4 5 6 7 8