资源描述：
《运筹学课件第1章 线性规划及单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、「线性规划」带来巨额财富与其他传统数学学科相比较,线性规划算是非常「年轻」却非常「实用」的一门应用数学。根据二十世纪八十年代的一项调查,在美国「财富」杂志(Fortune)名列前五百名的大公司中,百分八十五均曾应用线性规划的方法来协助公司的营运。由此可见线性规划应用面的宽广与普及。第1章线性规划及单纯形法§1一般线性规划问题的数学模型§2图解法§3单纯形法原理§4单纯形法的计算步骤§5单纯形法的进一步讨论§6数据包络分析主要内容§1一般线性规划问题的数学模型问题的提出线性规划问题的数学模型线性规划问题的标准
2、形式线性规划问题的解常山机器厂生产I、II两种产品，这两种产品都要分别在A、B、C三种不同设备上加工。生产两种产品，已知的条件如下表所示，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。生产每件产品占用设备时间(h)产品I产品II计划期内用于生产的能力设备A2212设备B4016设备C0515单位产品的利润（元）23例1.1生产计划问题1-1问题的提出问题分析占用设备时间(h)产品I产品II可用的能力设备A2212设备B4016设备C0515利润（元）23可控因素(决策变量):设在计划期内生产I、
3、II两种产品的数量分别为目标：达到最大.使得总利润最大，即利润函数：受制条件：计划期内设备的使用量不超过可用量：设备B：设备C：设备A：模型s.t.1-2线性规划问题的数学模型(1)规划问题的数学模型的3个组成要素：决策变量、目标函数、约束条件(2)线性规划问题的数学模型：决策变量为可控的连续变量、目标函数和约束条件关于决策变量都是线性目标函数约束条件(3)一般线性规划问题的数学模型的表示形式：以上模型的简写形式为待定的决策变量价值系数矩阵为系数矩阵(或约束矩阵)。向量表示形式其中矩阵表示形式价值向量右端向
4、量(2)化为标准形式的方法1-3线性规划问题的标准形式取极大bi≥0,等式约束非负约束(1)标准形式①②松弛变量③剩余变量说明：松弛变量和剩余变量在实际问题中分别表示未被利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。例1.2把问题转化为标准形式1-4线性规划问题的解线性规划问题满足约束条件(2)、(3)的解可行解(或可行点)可行域全部可行解的集合最优解使目标函数(1)达到最大值的可行解最优解集合最优值最优解的全体最优解的目标函数值基设Am×n为约束方程组(2)的
5、系数矩阵(设n＞m),R(A)=mB是矩阵A的m×m阶的满秩子矩阵，基向量基变量非基变量基解不失一般性，设基B的每一个列向量Pj(j=1,…,m)与基向量Pj对应的变量xj线性规划中除基变量以外的其他变量在约束方程组(2)中,令非基变量xm+1=…=xn=0,可解出m个基变量的惟一解XB=(x1,…,xm),X=(x1,…,xm,0,…0)T,基解总数基可行解满足变量非负约束条件(3)的基解可行基对应于基可行解的基例1.3列出下述线性规划问题的全部基、基解、基可行解、最优解解：系数矩阵R(A)=2基基解是基
6、可行解？目标函数值x1x2x3x4-45.500×√√√×√×√2/5011/50-1/30011/601/2200-1/2020011P1P2P1P3P1P4P2P3P2P4P3P443/555§2图解法优点：直观性强、计算方便缺点：只适用问题中有两个变量的情况步骤：建立坐标系，将约束条件在图上表示；确立满足约束条件的范围；绘制出目标函数的图形；确定最优解s.t.例2.1用图解法解线性规划x1x2oB(0,6)A(6,0)2x1+2x2=125x2=154x1=16z=9z=15z=12Q1Q2Q3Q4唯
7、一最优解线性规划问题解的情况：无可行解(可行域是空集)无界解或无最优解(可行域无界)最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一(无穷多最优解)，一定存在顶点是最优解(1)无可行解s.t.x1x2o2x1+2x2=12x1+2x2=14(2)无界解s.t.(3)无穷多最优解x1x2o4x1=16s.t.x2oQ1Q2Q3Q4x1图解法的启示(1)求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解；(2)若线性规划问题的可行域存在，则可行域是一个凸集；(3)若线性规划问题的最
8、优解存在，则最优解或最优解之一(如果有无穷多的话)一定能够在可行域的某个顶点找到；(4)解题思路：先找出凸集的任一顶点，计算在顶点处的目标函数值，比较周围相邻顶点的目标函数值是否比这个值更优，若为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更优的另一顶点重复上述过程，一直到找出使目标函数值达到最优的顶点为止。内容小结基本概念线性规划、可行解、可行域、最优解、最优值、基向量、(非)基变量
