第一章线性规划jssk运筹学.ppt

运 筹 学 教 程 第一章 线性规划的数学模型与单纯形法 1.1 线性规划问题及其数学模型 1.2 线性规划问题的图解法及几何意义 1.3 线性规划问题的单纯形解法 1.4 单纯形算法的进一步讨论 1.5 应用举例 1.1 线性规划问题及其数学模型 1、线性规划问题 在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。 1.1 线性规划问题及其数学模型 例1.1 （计划安排问题） 某工厂在计划期内安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所占用设备A、B的台时、原材料的消耗如表1.1所示： 问：应如何组织生产才能使工厂利润最大？ 1.1 线性规划问题及其数学模型 在本例中： 决策变量： Ⅰ、Ⅱ两种产量的计划产量，设为x1 、x2 目标函数：总获利，记为Z，为体现对其追求极大化，在的前面冠以极大号Max 约束条件：分别来自资源设备、原材料限量的约束，和产量非负的约束 1.1 线性规划问题及其数学模型 数学模型： 解：设Ⅰ、Ⅱ两种产量的计划产 量x1 、x2 ，总获利记为Z 1.1 线性规划问题及其数学模型 例1.2 （成本问题） 某炼油厂每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A、B两处运回原油提炼，已知两处的原油成分含量见表1.2；又已知从A处采购的原油价格（包括运费）为每吨200元，B处采购的原油价格（包括运费）为每吨290元，问：该炼油厂该如何从A、B两处采购原油，在满足供应合同的条件下，使购买成本最小。 1.1 线性规划问题及其数学模型 1.1 线性规划问题及其数学模型 1.1 线性规划问题及其数学模型 线性规划的模型结构: 从以上两个例子中可以归纳出线性规划问题的一般形式：对于一组决策变量x1,x2,?xn，取 1.1 线性规划问题及其数学模型 在线性规划模型中，Z为目标函数； xj(j=1,2,?,n)：为决策变量； cj(j=1,2,?,n)：为目标函数系数或价值系数或费用系数； bi(i=1,2,?,m)：为函数约束右端常数或简称右端值，也称资源常数； aij(i=1,2,?,m;j=1,2,?,n)为约束系数或技术系数或工艺系数。 这里，cj，bi，aij均为常数。 1.1 线性规划问题及其数学模型 线性规划模型三要素的意义 （1）决策变量是问题中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。 （2）目标函数是指对问题所追求的目标的数学描述。例如利润最大、成本最小等。 （3）约束条件是指实现问题目标的限制因素。如原材料供应量、生产能力、市场需求等，它们限制了目标值所能到达的程度。 1.1 线性规划问题及其数学模型 本章讨论的问题均为线性规划问题。所谓“线性”规划，是指如果目标函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的规划问题就称为线性规划问题。 如果模型中出现 非线性表达式，就不属于线性规划 标准型 例1.1的标准型 例1.4 将如下线性规划问题化为标准型 1.2图解法（导言） 1.2 线性规划问题的图解法 及几何意义 图解法 是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。 图解法（总结三个特点） ◆唯一解：线性规划问题具有唯一解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。 ◆无穷多解：线性规划问题具有无穷多解是指该规划问题有无穷多个既在可行域内、又使得目标值达到最优的解。 无可行解：当线性规划问题中的约束条件不能同时满足时，无可行域的情况将会出现，这时不存在可行解，即该线性规划问题无解。 无有限最优解（可行域无界，目标值不收敛）：线性规划问题的可行域无界，是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。 用图解法求解例1.1： 1.4 线性规划问题解的概念 例：判断是否为可行解 1.4 线性规划问题解的概念 1.4 线性规划问题解的概念 1.4 线性规划问题解的概念 1.4 线性规划问题解的概念 在上例中，求相应于B1和B2的基解，它们是否是基可行解？ 单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格提出。 尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。 一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数