运筹学线性规划1

运筹学（线性规划）模式识别与智能系统研究所韩延彬Email:HYB309@复习前述内容:1、运筹学的基本概念和发展简史2、运筹学研究的基本特征与基本方法3、运筹学主要分支4、运筹学与管理科学特别强调的内容是考试的重点。写出运筹学的基本概念运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科.其研究的基本特征和方法系统的整体观念，多学科的综合，应用模型技术.分析和表述问题,建立模型,求解模型和优化方案,对模型和由模型导出的解进行检验,对解的有效控制,方案的实施主要分支线性规划,非线性规划,动态规划,图与网络分析,存储论,排队论,对策论,决策论1.线性规划的定义当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。目标函数：问题的目标通过用变量的函数形式表示约束条件：对问题的限制条件用有关的等式或不等式的表示。其典型问题为：运输问题，生产计划问题，下料问题，混合配料问题，许多非线性的问题往往采用某些问题转化成为线性问题。本章主要内容线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论应用举例这一章的内容都非常的重要，所以要注意！原理，计算1.线性规划问题及其数学模型怎样根据现实问题搭建线性规划的数学模型线性规划的标准模型是什么怎样将一般的线性规划模型转化为标准模型1.线性规划问题及其数学模型问题：在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优。例1：公司S计划制造Ⅰ,Ⅱ两种产品，已知制造一件所占用的A，B两台设备的台时，调试时间，调试工序，每天可制造的能力，以及每种产品的利润如下：

ⅠⅡ每天的可用能力设备A设备B调试工序06152115245利润21

问题分析可控因素：每天生产两种产品的数量，分别设为x1,x2,目标：每天的生产利润最大利润函数maxz=2x1+x2（1）受制条件：每天原料的需求量不超过可用量：设备A：5x2≤15（2）

设备B：6x1+2x2≤24（3）

工序：x1+x2≤5（4）蕴含约束：产量为非负数x1,x2≥0（5）

其中（1）为目标函数，（2）～（5）约束条件例2：某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量公斤/日原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354问题分析规划问题的三个要素变量（决策变量）：问题中要确定的未知量，用以明确规划中的用数量表示方案，措施，可有决策者制定和控制目标函数：决策变量的函数，按优化目标分别为max和min约束条件：决策变量收到各种资源条件的限制，通常为等式和不等式。线性规划的一般模型假定线性规划问题中含有n个变量，分别用xj（j=1,...,n）表示，在目标函数当中xj的系数为cj（价值系数），xj的取值受到m项资源的限制，用bi（I=1,...,m）表示第i中资源的数量，ai,j为技术系数或工艺系数。则上述线性问题的数学模型可以表示为：max(min)z=c1x1+c2x2+...+cnxna11x1+a12x2+...+a1nxn

≤（＝，≥）b1a21x1+a22x2+...+a2nxn

≤（＝，≥）b2...am1x1+am2x2+...+amnxn

≤（＝，≥）bmx1,x2,...,xn≥0线性规划的一般模型(其他形式)向量模式矩阵模式Max(min)z=CXAX≤(=,≥)BX≥0线性规划的一般模型(其他形式)线性规划问题的标准形式对于非标准形式，我们可以通过一下的形式进行标准化：(1)(2)图1(3)约束条件(4)无约束条件x没有约束，可以转化为x＝x1－x2(5)对于x≤0的情况x`=-x图解法了解图解法的一些基本概念会用图解法求解简单题目了解图解法解的情况对模型中只含2个变量的线性规划问题，可以通过在平面上作图的方法求解。一个线性规划问题有解，是指能找出一组xj(j＝1,...,n)，满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域．可行域中使目标函数值达到最优的可行解称为最优解。对不存在可行解的线性规划问题，称该问题无解。图解法求解的目：一、判别线性规划问题的求解结果，二、在存在最优解的条件下，把问题的最优解找出来。理论上讲，图解法是不存在变量限制的，但是在实际情况中，我们最多能描述的是空间模型，所以图解法要求变量的个数≤3，一般是两个变量。可行域（该区域中的任何一个解即为可行解）最优解区域（该区域中的任何一个解，都是最优解）最优解，也是可行解线性规划的图解（步骤）例3：max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2图解法的步骤（1）以变量x1为横坐标轴，x2为纵坐标轴画出直角平面坐标系，并适当选取单位坐标长度。（2）图示约束条件，找出可行域（根据约束条件）。（3）图示目标函数，由于目标函数值逐渐增大，这样得到一组平行的直线。（4）最后解的确定，找到使得目标函数值最大的点或者是点集。线性规划问题求解的几种情况惟一解图解线性规划问题求解的几种情况无穷解图解平行目标函数同某一约束条件平行图解无界解，缺少约束条件无界解线性规划问题求解的几种情况无解无解，没有可行解区域线性规划问题求解的几种情况由图解法得到的启示

1．求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解、无可行解。

2．若线性规划问题的可行域存在，则可行域是一个凸集。

3．若线性规划问题的最