第1章线性规划及单纯形法(完成).ppt

运 筹 学 大连交通大学管理学院 王岩 第一章 线性规划及单纯形法 第一节 一般线性规划问题的数学模型 本节内容： 一、线性规划问题简介 二、线性规划问题的数学模型 三、线性规划问题的标准形式 四、线形规划模型的标准形式的转化 一、线性规划问题简介 线性规划能解决哪类问题？ 有限资源的最佳分配问题：资源分配问题；成本收益平衡问题；网络配送问题 线性规划的广泛应用是计算机时代的产物。 1902年，Julius Farkas 发表论文，阐述有关线性规划问题。 1938年，英国人康德进行较详细研究。 1947年，美国学者George Dantzig（丹茨格）发明了求解线性规划的单纯形法（1951年发表），从而为线性规划的推广奠定了基础。有人认为，求解线性规划的单纯形算法可与求解线性方程组的高斯消元法相媲美。 二、线性规划问题建模举例 资源分配问题：教材第6页例2 企业计划生产I，II两种产品，它们分别在A，B，C，D四种不同设备上加工，具体生产时间及各设备加工能力如下表： 求：企业如何安排两种产品的产量，使得总利润最大 二、线性规划问题建模举例 解：根据题意，选择决策变量为x1，x2，分别代表I，II两种产品在计划期内的产量。 设利润为Z，则 maxZ=2x1+3x2 （1） 此为企业追求的目标，故称为目标函数。 根据题意，两种产品在计划期内的产量应该满足各设备的生产时间限制，则有： （2） 以上的不等式左端均为决策变量x1，x2的函数，因此称为函数约束 两种产品的产量应为非负，即应满足以下限制条件： （3） 上面的称为非负性约束。 （2）（3）统称为约束条件。 二、线性规划问题建模举例 因此，该问题的数学模型可以归结为：在约束条件（2）（3）下，确定变量x1，x2，的数值，使目标函数（1）式的函数值Z达到最大，上述数学模型可简记为： maxZ=2x1+3x2 其中，max是maximize的缩写，s.t.是subject to（受约束于）的缩写 三、线性规划问题的数学模型 1.三个组成要素： 决策变量：问题中的未知量，一般由研究者的决策部门加以确定，故称决策变量。 目标函数：决策目标，为决策变量的函数。 约束条件：可用资源的限制。 三、线性规划问题的数学模型 小结1：建模的基本步骤 设置决策变量，它们体现解决问题的方案。 确定目标函数，它是决策变量的函数。 确定约束条件，它们是含有决策变量的不等式或等式。 确定决策变量的取值范围，给出优化方向。 其中，前两条称为可行条件，最后一条称为优化条件。符合这三个条件的数学模型通常称为线性规划的一般型（general）。 三、线性规划问题的数学模型 小结2：数学模型的共同结构 存在一组决策变量，对它们可有非负要求； 存在一个以决策变量为自变量的目标函数，且它为线性函数； 存在一组约束条件，且每个条件都是由决策变量构成的线性不等式或等式； 结构要求出这样的变量组，或者说决策向量，在满足约束条件和非负约束的同时，使相应的目标函数值达到最大或者最小。简言之，在一定条件下使目标函数优化。 三、线性规划问题的数学模型 2. 线性规划问题的数学模型： 以上模型的简写形式为： 三、线性规划问题的数学模型 其向量形式为： 其中， 其中，C常常被称为价值向量，其每个分量价值系数 三、线性规划问题的数学模型 模型的矩阵形式为： 其中， ，A称为约束方程组变量的 系数矩阵，或简称约束变量的系数矩阵 三、线性规划问题的数学模型 课堂练习： 1.一食品厂生产饼干：生产两种饼干A，B，需经过三道工序及相应的设备：搅拌机、成型机、烘箱。生产每吨A、B产品各需要在三种设备上时间如表所示。单位利润：A：500元/吨，B：400元/吨。问：如何安排生产，使总利润最大？ 1.解：设总利润为z，生产饼干A、B各为x1、x