线性规划及其基本理论课件

1、运筹学，1，学习与交流PPT，线性规划及其基本理论，线性规划概述线性规划数学模型一般模型标准模型线性规划解概念可行解，最优解矩阵，基本解，基本可行解线性规划的基本性质，2，学习与交流PPT，线性规划概述，线性规划是运筹学线性规划及其一般解-单纯形法一般认为是由美国学者G .丹齐格在1947年研究美国空军军事规划时提出的。苏联学者坎特罗维奇在1939年解决工业生产组织和计划问题时提出了类似线性规划的模型和解法；坎特罗维奇的工作在当时没有受到重视，但直到1960年坎特罗维奇再次出版了最优资源利用的经济计算一书才受到重视。一些常用的电子表格软件，如电子表格、Lotus1-2-3等。具有内置线性编程功

2、能。优化问题解决软件，如Lindo、Lingo、Matlab等。3。学习交换PPT，线性规划问题被提出，在生产管理和经营活动中，这样一种问题经常被提出：如何利用有限的人力、物力、财力等资源达到最佳效果。例如：积载问题-运输工具，运输不同体积和重量的几种材料，如何组装，以及运输最多的材料？材料切割问题：当圆钢用于制造不同长度的机器轴时，如何切割材料，剩余材料最少？生产计划问题企业生产两种电气产品，甲和乙。这两种产品的市场需求是可以确定的，所有产品都可以按现行价格销售。一个企业能够提供的两种原材料的数量和劳动时间是有限的。产品甲和产品乙应该生产多少才能使企业的总利润最大化？4、学习交流PPT，提出

3、线性规划问题，这些问题有以下共同特点：问题解决必须满足一定条件，称为约束条件；符合条件的问题有多种解决方案；问题解决有明确的目标要求，不同的目标值对应不同的方案，可以表示为目标函数。5，学习交流PPT，什么是线性规划问题，优化问题我们称之为以下一般问题：“在一定的约束条件下，寻求目标函数的最大值或最小值”是一个优化问题，而用数学模型描述的优化问题称为数学规划问题。线性规划问题在最优化问题中，如果约束条件和目标函数都是线性的，我们称之为线性规划问题。学会沟通PPT，线性规划问题的三要素，以及决策变量的待定值的决策问题称为决策变量。决策变量的值有时需要非负的。约束任何问题都是在一定条件下解决的，各

4、种约束都表示为一组等式或不等式，这就是所谓的约束。约束是决策方案可行性的保证。线性规划的约束都是决策变量的线性函数。目标函数是衡量决策方案优劣的标准，如最短时间、最大利润和最低成本。目标函数是决策变量的线性函数。有些目标非常需要实现，而另一些则要求很少。7.学习交换PPT，线性规划数学模型，例如，生产计划问题A工厂生产两种产品，A和B，它们的零件分别在A车间和B车间生产，最后它们都需要在c车间组装。相关数据见表：询问如何安排产品A和B的产量以实现利润最大化。3 5，单位产品利润，8 12 36，1 2 3 2 3 4，A B C，生产能力，工时消耗A B，产品车间，8，学会交换PPT，线性规划

5、数学模型，并建立数学模型步骤：步骤1分析实际问题；第二步，确定决策变量；找出约束条件；步骤4，确定目标函数；组织并写出数学模型。9，学习和交流PPT，例1.1一个城市将在此建造大量房屋，线性规划问题示例，10，学习交流PPT，示例1.2最优生产计划问题。一个企业计划在规划期内生产三种产品：甲、乙、丙。这些产品需要分别在设备甲和设备乙上加工，材料丙和材料丁需要消耗。根据技术数据，单个产品在不同设备上的加工情况及所需资源见表1.1。据了解，规划期内设备加工能力为200台时，可用材料分别为360公斤和300公斤；假设无限的市场需求，对于甲、乙、丙三种产品，企业可以分别获得40元、30元和50元的利润

6、。企业决策者应该如何安排生产计划，使企业在计划期内的总利润和总收入最大化？线性规划问题示例，产品资源消耗表，11，学习与交流PPT，示例1.3一家商场决定销售人员在每周连续工作五天后，应连续休假两天，并轮流休息。据统计，商场每天需要的销售人员如表1.2所示。表1.2销售人员要求统计表。商场人力资源部应该如何安排每天上班的人数，以减少商场的总销售人员？线性规划问题示例，12，学习交流PPT，示例1.4合理使用材料。一辆汽车需要使用一个轴的甲，乙和丙，其规格分别为1.5，1和0.7米。这些车轴需要用同样的圆钢制成，长度为4米。现在，要制造1000辆汽车，至少需要用多少圆钢来生产这些车轴？例如，线性

7、规划问题，13，学习交流PPT，解决方案这是一个带切割问题，让切口宽度为零。如果圆钢被切割成三个轴：y 1、y2和y3，那么切割方法可以用不等式1.5y1 y2 0.7y34表示，并且可以得到关于y1、y2和y3的该不等式的非负整数解。像这样的非负整数解有10组，即有10种消隐模式，如表1.3所示。表13下料方案，表14，学习交流PPT，设xj(j=1，2，10)为第j次下料方案中使用的圆钢数量。那么最小材料消耗的数学模型是：注：(1)计算下料方案时，应注意余料不能超过最短的下料长度；()最好按降序排列坯料长度，即先切割最长的坯料，然后切割第二长的坯料，最后切割最短的坯料，这样就不会遗漏该方案

8、。()如果有很多方案，用计算机编程来安排方案，去掉有长剩余材料的方案进行初选。15，学会交流PPT，示例1.5配料。钢铁公司生产的合金要求成分规格：锡不低于28%，锌不超过15%，铅正好是10%，镍在35U之间，不允许有其他成分。钢铁公司计划冶炼五种不同等级的矿石，每种矿石的成分含量和价格见表1.4。矿石杂质在精炼过程中被丢弃，现在需要每吨合金成本最低的矿石量。假设矿石的合金含量在熔炼过程中没有变化。表1.4，矿石的金属含量，线性规划示例，16，学习交换PPT，求解：让xj(j=1，2，5)为第一类矿石的数量，并得到以下线性规划模型，注意矿石的金属含量在实际冶炼过程中会发生变化，这可能是一个非

9、线性关系。配料问题，也称为配方问题、营养问题或混合问题，可在许多行业中遇到。17，学会沟通PPT，示例1.6投资问题。一家投资公司第一年的资本为200万元。每年可考虑采用以下投资方案：“如果第一年投入一笔资金，第二年继续投入50%，第一年投入的资金可在第三年收回”。投资公司决定最好的投资策略，这样它在第六年就有最多的资金。线性规划问题，例如，18，学习沟通PPT，示例1.7平衡支持生产问题。一个产品由两个零件甲和三个零件乙组装而成。两种零件必须在设备甲和设备乙上加工为了维持两种设备的均衡负荷生产，要求一种设备每天的总加工时间不超过另一种设备一小时的总加工时间。如何安排设备的加工时间，使每天的产

10、品产量最大化。线性规划问题示例，19，学习交流PPT，线性规划数学模型的一般形式，并假设线性规划问题有n个决策变量和m个约束。一般来说，线性规划问题的数学模型可以用以下形式表示：20。学习和交流PPT，线性规划数学模型的标准形式，线性规划问题的数学模型有多种形式，如目标函数的最大化和最小化；有三种约束：“”、“和”；决策变量通常有非负要求，而其他变量没有。为了方便地解决这个问题，规定了线性规划的标准形式，非标准形式可以转化为标准形式。标准形式是：目标函数最大化，约束条件为等式，右常数项为bi0，决策变量为非负。21，学会交流PPT，线性规划数学模型标准表格，22，学会交流PPT，线性规划数学模

11、型标准表格，23，学会交流PPT，线性规划数学模型标准表格，24，学会交流PPT，如何转换线性规划标准表格，26，示例1.8min z=x1 2x 2-3x 3 x12x 2-x3 52x 1 3 x2-x3 6-x1 x2x 3-2x 1 2x 0，x3 0，27，学会交流PPT，示例1.9如何改变学习交换PPT，如何改变线性规划标准形式，29，学习交换PPT当一个约束是一个绝对值不等式时，绝对值不等式转化为两个不等式，然后转化为一个等式。 例如，一个约束被转换成两个不等式，然后一个松弛变量被添加到等式中。如何改变线性规划的标准形式，30，学习PPT，线性规划解的概念，其中可行解和可行域满足约束条件(AX=b，X0)，X称为线性规划问题的可行解，而所有可行解的集合称为可行域，而D=X| AX=b，X0。最优解使目标函数值最大的可行