2375运筹学基础复习资料5

第五章线性规划P670
概述（领会）P67
线性：描述在两个或多个变量之间的关系是直接成正比例的，规划：使用某种数学方法使有限的运用达到最优化，线性规划：是一种合理的利用资源，合理调配资源的应用数学方法
线性规划的模型结构P68
一、 线性规划的模型结构（领会）P68
变量、目标函数、约束条件、线性规划的变量应为正值
二、 线性规划建模的步骤（简单应用）P68
四步骤：明确问题，确定目标，列出约束因素；收集资料，确立模型；模型求解与检验；优化分析
线性规划的图解法（简单应用）P70（可参见大专笔记P85）
线性规划的基本解法有图解法和单纯形法两种
一、 求最大值问题P70
图解法分两步：求出满足约束条件的可行解区（可行域），从中求得目标函数的最优解
1．求出满足约束条件的可行解区（可行解：又称凸集，或者叫可行域，形状取决 于约束条件的数目和约束条件的系数）
可建立数学模型——变量：为非负，即≥0
                 约束条件：等号
                 目标函数：为最大值
根据条件，在直角坐标的平面图上作出图
2．从可行解区内，找满足目标函数的最优解
最优的可行解必在可行解区边缘折线的凸交点上
具体方法：通过各个极点作与目标函数直线斜率相同的平行直线，离原点距离最远的极点即是最优
二、 求极小值问题P73
可建立数学模型——变量：为非负，即≥0
                 约束条件：等号
                 目标函数：为最小值
根据条件，在直角坐标的平面图上作出图
作与目标函数直线斜率相同的平行直线，离原点距离最远的极点即是最优
解线性规划问题的单纯形法（领会）P74
它是通过一种数学的迭代过程，逐步求得最优解的方法，基本步骤：求可行解；换基迭代，得到最优解（求最优解可以分为求最大值和最小值两类）
一、 一般最大值问题的求解法P74——（可参见大专笔记P88）
步骤如下：
1．建立初始方案，列出初始单纯形表
第一步：引入辅助变量，将模型转换成标准形式
引入辅助变量，把约束条件由不等式变为等式（当不等号左边是小于时为增加，是大于时为减去），把约束方程等号右边的常数变为正数，在等号两边乘 -1即可
标准型 （公式）
第二步，列出初始单纯性表，如下：
基变量：在本方程中系数为1，在其它方程中系数为0，叫…
                     1．目标函数系数
  CJ基变量 X1 X2 K1 K2 K3     所求的极大值
             2． 全部变量（基变量和非基变量数）  
  基       K1
  变
  量       K2                    约束条件的系数                  常数
  系
  数       K3
ZJ -2． 经迭代后，对目标函数进行的调整，在初始表中无反应
CJ - ZJ -1．经调整后，目标函数的系数
注：非基变量数=变量个数-约束方程的个数
   满足约束方程组和变量非负的要求，则是可行解。
2．进行第一次迭代
①在方程中，选系数最大的正非基变量转为基变量，此非基变量所在列称为主列，然后求（常数列/主列对应的值），在所得结果中选最小值所在的行作为主行，主行与主列相交，得到主元素。将主元素所在列和行的变量进行迭代（即列中的非基变量转为基变量，而行中的基变量转为非基变量）
作为基变量，那么它所在的这一列中，除了主无素位置上的值是1，其它的值为0
值是1：可通过整行除以主元素的倒数求得整行的值，可通过在求得1的基础上，进行乘和加求得整行值
① ZJ行：所有已迭代的基变量的系数  *  本行每列的对应值（之和）
②  CJ -ZJ行：第1行（即目标函数系数这一行）  -  ZJ行
3．第二次迭代：将CJ -ZJ这一行中，系数非负的作为基变量，查找（常数/系数）值最小的作为非基变量，进行第二次迭代
3．迭代至所有的检验数都 非正，则当前的基可行解是最优解。
二、 一般最小值问题的求解法P82
有时需在建立初始方案时加入人工变量，此变量在最后的结果中都变为0，从而对规划问题无影响，所以在目标函数中，给它们配上一个数值很大的系数，此系数取正数。
1．列出初始单纯表
2．在方程中，选系数最小的作为主列，比值小的作为换出行
3．第二次迭代：将CJ -ZJ这行中最小的作为主行，比值小的作为主列，当此行为正数或0时，最优
线性规划应用示例（简单应用）P84
一、 原料投入的混料问题P85
二、 生产计划中产品搭配问题P88？？？
三、 季节产品修匀的应用P90