2012年软考系统分析师经典教程：数学基础知识

　　1.9.4 线性规划

　　线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。线性规划所研究的问题是：在线性约束条件下，使线性目标函数达到最优。为了解决实际问题，首先需要把它归结为数学问题，即建立数学模型。线性规划问题的数学模型是描述实际问题的抽象的数学形式。

　　线性规划问题的数学模型是指求一组满足一个线性方程组(或线性不等式组，或线性方程与线性不等式混合组)的非负变量，使这组变量的一个线性函数达到最大值或最小值的数学表达式。

　　建立数学模型的一般步骤：

　　1. 确定决策变量(有非负约束);

　　2. 写出目标函数(求最大值或最小值);

　　3. 写出约束条件(由等式或不等式组成)。

　　标准形式及其特点

　　为便于今后求解，我们把线性规划问题的数学模型规定统一的形式，称之为标准形式，简称标准型。线性规划问题的标准形式也是单纯形方法的基础。

　　线性规划问题的标准形式有以下特点：

　　1.目标函数求最小值;

　　2.约束条件中除决策变量外，其余条件均为等式;

　　3.每个约束方程右边的常数都是非负数，即.；

　　线性规划问题数学模型的标准形式：

　　求

　　其中 均为常数。

　　化标准形式

　　(1)如果目标函数求最大值，即。

　　只须令 ，便可将目标函数求最大值转化为求最小值，即求

　　(2)引进松弛变量，将约束条件中的不等式化为等式(决策变量非负约束除外)。

　　(3)在约束条件为等式的前提下，如果某个方程右边的常数是负数，则只须在方程两边乘以-1.

　　线性规划问题的一些重要概念

　　(1)基、基变量、非基变量

　　如果矩阵B是约束方程系数矩阵A中的 阶非奇异矩阵

，则称方阵B为线性规划问题的一个基矩阵，简称为基。

　　矩阵B中的每一列所对应的m个变量称为基变量，除基变量以外的n-m个变量，我们称为非基变量。

　　(2)基础解、基础可行解、基础最优解

　　在约束方程组中，如果令各非基变量等于零，所得的解，称为线性规划问题的基础解。

　　如果基础解满足非负限制，则称它为基础可行解。

　　使目标函数取得最小值的基础可行解，称为基础最优解。

　　(3)可行基、最优基

　　对应于基础可行解的基，称为可行基。

　　对应于基础最优解的基，称为最优基。

　　通过例题让大家理解这几个概念及基础最优解求出的过程。

　　线性规划的解法一般有图形法和单纯形法。

　　2.重点和难点：

　　1) 存储器部分：特别是cache和虚拟存储器是重点的复习方面

　　2) 计算机系统结构：计算机的安全和可靠性方面计算题目

　　3) 体系结构其他知识：RISC和并行处理的技术

　　4) 数学部分

　　相关推荐：

　　2012年软考系统分析师考试60天完美复习计划

　　2012年软件水平考试网络工程师章节笔记讲义汇总

　　2012年上半年软件水平考试成绩查询汇总