《工程数学》教学课件02线性规划.pptxVIP

第2章线性规划;;;;;;§2.1线性规划问题的数学模型;;;建立数学模型时所设的变量，称为决策变量；需要满足的限制条件，称为约束条件；用决策变量表示出来的目标要求，称为目标函数.特别地，当约束条件和目标函数均为决策变量的线性函数的数学模型时，称为线性规划模型. 决策变量、约束条件及目标函数称为线性规划模型的三要素.;由上面的分析不难得到线性规划模型的一般形式为;一般来说，建立线性规划模型时的条件、数据比较繁乱，分析概括不易，但大致可按下列三步来进行. （1）根据问题的讨论因素，设出决策变量. （2）由决策变量所决定要达到的目的，确定目标函数. （3）由决策变量所受的限制，确定要满足的约束条件.;;;;;例题;例题;例题;;;习题2-1;习题2-1;习题2-1;习题2-1;习题2-1;§2.2线性规划模型的求解;满足约束条件的决策变量取值，称为规划问题的可行解；全体可行解的集合称为可行域；满足目标函数的可行解称为最优解；由最优解确定的目标函数值叫作规划问题的最优值.;当一个线性规划问题的决策变量只有两个时，最优解可以通过作图的直观方式求出（如果决策变量多于两个，因为多元函数没有直观的几何图示，所以此方法不适用）.;;;;当线性规划模型中的决策变量较多时，可行域没有直观意义，那么怎么求决策变量多于两个时的线性规划模型的最优解呢？丹齐格在1947年提出了著名的求解线性规划问题的方法——单纯形法. 一般来说，线性规划模型形式多样，目标函数值有求最大、最小两种情况，约束不等式有“≤”“≥”“＝”等形式，给讨论带来不便.为此，我们先规范和统一模型的形式，然后再进行单纯形法的讨论.;?;?;?;例题;例题;一般地，对于线性规划模型的标准型;在约束方程组中约束方程的个数多于决策变量的个数（mn）的情况下，根据高斯消元法可知，约束方程组要么有多余方程，要么有矛盾方程.当出现多余方程时，可以删掉；当出现矛盾方程时，无可行解就不必再讨论.为方便研究问题，以下讨论总假定m≤n，且约束方程组的系数矩阵的秩为m；并假设线性规划模型有可行解.;?;?;?;?;注：因为一般规划模型的约束方程系数矩阵不进行列的对调，所以典式约束方程组的系数矩阵的前若干列系数并不一定是单位矩阵的形式；但每个基变量的系数列必是单位矩阵的某一列；典式目标函数中的基变量的系数必须全为零.这两点在下面的讨论中要时刻明确. 以上求??过程可以利用表格或矩阵的形式来完成，这就是单纯形法的思路.下面通过具体的例子来说明.;;;;;;;;;;;;?;（3）换基迭代.若检验数中存在负数，先要将其中绝对值最大者对应的变量选进基变量，比值检验寻求主元素，将主元素利用初等行变换化为1，将主元素列其他数化为0，再将与新主元素列相同的原主元素列对应的原基变量剔除出基变量，向目标函数进行再迭代. （4）最优判断.不断重复上述检验—换基—迭代过程，当常数列各元素保持非负，最终检验数也全部非负时，令非基变量为零，得到的基可行解为最优解；当常数列各元素保持非负，而检验数不可能全部化为正数时，模型无最优解. 线性规划问题模型的形式、决策变量要求多种多样，故而求解的方法、手段也有很多，但单纯形法是基础解法.在此，我们仅要求能列出线性规划模型，对决策变量与约束方程较少的线性规划模型能够利用单纯形法求得最优解即可.在后面学习完LINGO软件的使用方法后，利用它将能非常容易地求解各种线性规划模型.;习题2-1;习题2-1;习题2-1;§2.3指派问题模型的建立与求解;如果线性规划问题中的所有变量都要求取整数值，则称之为纯整数线性规划；若只限定部分变量取整数值，则称之为混合整数线性规划.整数线性规划的求解比起线性规划问题要困难得多：当变量较少时，相应线性规划的可行域内含有的整数点较少，可以用穷举法求解；但是对于变量较多的问题，由于可行的整数解组合数量庞大，穷举法就不可取了.目前求解整数线性规划问题的方法主要有割平面法和分支定界法两种.然而这两种方法都比较烦琐、不易理解，因此本书不做介绍. 这里介绍一种整数线性规划的特殊情形——指派问题模型.;思考;思考;思考;?;2.3.1 指派问题模型的建立;2.3.1 指派问题模型的建立;;;;;指派问题模型是一种特殊的线性规划模型，可以用单纯形法来求解.但是，单纯形法不能充分利用指派问题的特殊性质来有效地减少运算量.匈牙利解法是由库恩（W.W.Kuhn）于1955年提出的，该法因应用了匈牙利数学家康尼格的一个定理而得名，其简单直观地给出了指派问题模型的求解方法.下面仅介绍匈牙利解法的操作过程，对其理论依据不做介绍. 指派问题总可以化为一一指派分配，所以数据表构成一个方阵.数据的含义有两种：效率和消耗率. ??牙利解法的操作过程如下.;（1）列消耗阵.当数据表中的数据表示消耗