第一章线性规划.

《第一章线性规划.》由会员分享，可在线阅读，更多相关《第一章线性规划.（125页珍藏版）》请在金锄头文库上搜索。

1、第1章 线性规划,制作：数理学院 赵建强,1.4 初始基本可行解的确定,4,1.1线性规划问题及其数学模型,1,1.2 线性规划问题的解,2,1.3 单纯形法,3,本章的教学目的和要求：,1、掌握线性规划数学模型的基本特征和标准形式，以及线性规划问题数学模 型的建立方法，学会用图解法求解简单的线性规划问题。 2、理解线性规划问题的解的概念，了解线性规划的基本理论。 3、了解单纯形表的构成，熟练掌握运用单纯形法求解线性规划问题。 4、掌握人工变量法（包括大法和两阶段法）的计算步骤。 5、本章将安排4学时的上机实验，练习如何建立线性规划模型解决相关的实际问题，并会用相关的数学软件求解该线性规划模型

2、。 教学重点：线性规划的标准形式、图解法、单纯形法。 教学难点：单纯形法、人工变量法。,1.1线性规划问题及其数学模型,教学目的和要求：使学生了解常见的几种线性规划实例；掌握线性规划的一般形式、标准形式、向量形式、矩阵形式等；会将线性规划的一般形式标准化。 教学重点：线性规划的一般形式、标准形式；线性规划的标准化。 教学难点：线性规划的标准化。 教学过程：,在经济活动及工程技术中会遇到各种各样的实际问题，描述实际问题共性的抽象的数学形式称为该问题的数学模型通常建立线性规划问题数学模型要遵循以下步骤： (1) 明确问题中有待确定的未知量(称为决策变量)，并用数学符号表示； (2) 明确问题中所有

3、的限制条件(称为约束条件)，并用决策变量的一组线性方程或线性不等式表示； (3) 明确问题的目标，并用决策变量的一个线性函数(称为目标函数)表示，按问题的不同取最大值或最小值,1.1.1 线性规划问题的几个实例,下面结合几个实际例子来介绍线性规划问题的特点，并按上面给出的三个步骤来建立它们的数学模型. 例 1.1-1 生产计划问题 假设某厂计划生产甲、乙两种产品，这两种产品都要分别在A，B，C三种不同设备上加工按工艺资料规定：生产每件甲产品需占用设备的小时数分别为2，l，4；生产每件乙产品需占用设备的小时数分别为2，2，0. 已知各设备计划期内用于生产这两种产品的能力(小时数)分别为12，8，

4、16；又知每生产一件甲产品，该厂会获得利润2元，每生产一件乙产品，该厂能获利润3元，问该厂应安排生产两种产品各多少件才能使总的利润收入为最大? 解 (1)明确决策变量 工厂需要确定的是甲、乙两种产品的计划生产量，设x1, x2分别为甲、乙两种产品的计划生产量，总的利润为z (2)明确约束条件 因设备A在计划期内有效时间为12小时，不允许超过,故有,对设备B，C也可列出类似的不等式,此外产品的产量,只能取非负值，即,0,0,这种限制称为变量的非负约束条件,(3)明确目标 工厂的目标是在各种设备能力允许的条件下，使总利润收入,为最大,综合起来，该问题的数学模型为：求一组变量,的值在满足约束条件,的

5、情况下，,为最大,使利润,例 1.1-2 运输问题,设有三个地方,生产某种物资,简称为产地),(,四个地方,需要该种物资,（ 简称为销地),产地的产量和销地的销量以及,产地到销地的单位运价表见表1.11，问如何组织物资,的运输，才能在满足供需的条件下使总的运费最少,表1.11 产销运输表,例 1.1-3 合理下料问题 某工厂生产某一种型号的机床，每台机床上需要2.9m，2.1m,1.5m的轴分别为一根、二根、一根，这些轴需用同一种圆钢制作，圆钢的长度为7.4m，如果要生产100台机床，问应如何安排下料，才能使用料最省?,1.1.2 线性规划问题的数学模型 一、线性规划模型的一般形式 上述各例具

6、有下列共同特征：,1、存在一组变量,，称为决策变量，通常要求,这些变量的取值是非负的,2、存在若干个约束条件，可以用一组线性等式或线性不等式 来描述,3、存在一个目标函数，它是决策变量的线性函数，按实际 问题求最大值或最小值,根据以上特征，可以将线性规划问题抽象为一般的数学表达式，,即线性规划问题数学模型（简称线性规划模型）的一般形式为：,式中max表示求最大值，min表示求最小值，,是由实际问题所确定的常数.,为利润系数,或成本系数；,称为限定系数或常数项；,称为结构系数或消耗系数；,为决策变量；每一个约束条件只有,一种符号,二、线性规划模型的标准形式,线性规划模型的具体形式是多种多样的为了

7、讨论和计算方便，,我们要在这众多的形式中规定一种形式，将其称为,线性规划模型的标准形式,通常线性规划模型的标准形式为,上述形式的特点是：,线性规划模型的标准形式可以写成简缩形式：,线性规划模型的标准形式有时用矩阵或向量描述往往更为方便,用向量表示线性规划模型的标准形式为,其中,向量,是变量,对应的约束条件中的系数列向量.,用矩阵表示线性规划的标准形式为,其中,其它同前我们称A为约束方程的系数矩阵（mn），,一般mn，m、n为正整数,三、 线性规划模型的标准化,我们对线性规划问题的研究是基于标准形式进行的， 因此对于给定的非标准形式线性规划问题的数学模型， 则需要将其化为标准形式一般地，对于不同

8、形式的 线性规划模型，可以采用以下一些方法将其化为标准形式,对于目标函数是求最小值的线性规划问题，只要将 目标函数的系数反号，即可化为等价的最大值问题,2约束条件为“”（“”）类型的线性规划问题，,可在不等式左边加上（或减去）一个非负的新变量，,即可化为等式这个新增的非负变量称为松弛变量 （或剩余变量），也可统称为松弛变量在目标函数中,一般认为新增的松弛变量的系数为零,3如果在一个线性规划问题中，决策变量,的符号没有限制，我们可用两个非负的新变量,和,之差来代替，即将变量,写成,且有,通常将这样的,称为自由变量如果Xk=0,则令Xk/=-Xk,4当常数项,为负值时，可在该约束条件的两边,分别乘

9、以-1,例1.1-4 将下列线性规划模型化成标准形式,解 通过以下四个步骤：,（1） 目标函数两边乘上-1化为求最大值；,（2） 以,代入目标函数和所有的约束条件中，,其中,（3） 在第一个约束条件的左边加上松弛变量,（4） 在第二个约束条件的左边减去剩余变量,于是得到该线性规划模型的标准形式：,练习：化标准型p36 1.3(4),(5),1.9(3) 作业：p34 1.1（1）（4）（5）、1.2,1.2 线性规划问题的解,教学目的和要求：掌握线性规划问题的基本概念； 掌握线性规划图解法； 了解线性规划问题的解的特殊情况； 掌握线性规划解的基本性质。 教学重点：线性规划问题的基本概念、基本性

10、质、图解法。 教学难点：线性规划的基本性质。 教学过程：,1.线性规划问题的基本概念,设有线性规划问题,一、可行解,满足线性规划约束条件（1.2-2）和(1.2-3)的解,称为线性规划问题的可行解,所有可行解的集合称为可行域,或可行解集,二、最优解,使线性规划的目标函数（1.2-1）式达到最大的可行解称 为线性规划的最优解,三、基本解,设A是约束方程组(1.2-2)的（mn）阶的系数矩阵（mn）,其,秩为m，则A中任意m个线性无关的列向量构成的mm阶子矩阵,称为线性规划的一个基矩阵或简称为一个基，记为B显然，,B为非奇异矩阵，即|B|0,基矩阵的m个列向量称为基向量，其余n-m个向量称为非基

11、向量；与m个基向量相对应的m个变量称为基变量，其余的 n-m个变量则称为非基变量显然，基变量随着基的变化而 变化，当基被确定以后，基变量和非基变量也随之确定了,若令约束方程组(1.2-2)中的n-m个非基变量为零，再对余下 的m个基变量求解，所得到的约束方程组的解称为基本解 基本解的个数总是小于,等于,的,如设,为线性规划的一个基，于是,为基变量，,就为非基变量,现令非基变量,，方程组(1.2-2)就变为,此时方程组有m个方程，m个未知数，,可唯一地解出,则向量,就是对应于基B的基本解,四、基本可行解,满足非负条件（1.2-3）的基本解称为基本可行解；对应于 基本可行解的基称为可行基,显然，基

12、本可行解既是基本解，又是可行解一般，基本 可行解的数目要少于基本解的数目，最多两者相等当基本 可行解的非零分量个数恰为m时，称此解是非退化的解； 如果有的基变量也取零值，即基本可行解的非零分量个数小于 m时，称此解是退化解,例1.2-1 求下列线性规划问题的所有基本解，并指出哪些是 基本可行解,解 将已知模型化为标准形式,系数矩阵,则易知,均为线性规划问题的基矩阵,对应基,，基变量为,，非基变量为,令,得,.从而,为线性规划问题的一个基本解,因,均大于零，故,为线性规划问题的一个基本可行解,对应于其他基,的基本解列表见表1.2-1,表1.2-1对应于其他基的基本解,2.线性规划的图解法,线性规

13、划的图解法(解的几何表示)： 对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。 图解法求解线性规划问题的步骤如下：,2.线性规划的图解法,(1)建立直角坐标系： 分别取决策变量x1 ,x2 为坐标向量。,2.线性规划的图解法,（2）绘制可行域： 对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。,2.线性规划的图解法,（3）绘制目标函数等值线，并移动求解： 目标函数随着

14、取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）； 然后，确定该直线平移使函数值增加的方向； 最后，依照目标的要求平移此直线。,2.线性规划的图解法,结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。,2.线性规划的图解法,Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 65 (A) 2x1+ x2 40 (B) 3x2 75 (C) x1 , x2 0

15、(D, E),2.线性规划的图解法 例题作图（1）,按照图解法的步骤： （1）以决策变量x1 ，x2 为坐标向量作平面直角坐标系；,2.线性规划的图解法,（2）对每个约束（包括非负约束）条件作出直线（A、B、C、D、E），并通过判断确定不等式所决定的半平面。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示。,2.线性规划的图解法 例题作图（2）,第2步图示(1) 分别作出各约束半平面,X2 0,x1 0,3x2 75,3x1+ 2x2 65,2x1+ x2 40,2.线性规划的图解法 例题作图（3）,第2步图示(2) 各约束半平面的交可行域,2.线性规划的图解法,（3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点 (5,25)T ，即最优解。此目标函数的值为70000。,2.线性规划的图解法 例题作图（4）,第3步图示 作出目标函数等值线,函数值增大,2.线性规划的图解法 例题作图（5）,第3步图示(2) 求出最优解,1,2.线性规划的图解法,根据上面的过程 我们得到这个线性规划的 最优解 x1=5、x2=25， 最优值 z = 70000 即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元