[数学]线性规划与单纯形法

《[数学]线性规划与单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划与单纯形法.生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划论要解决的问题。规划论作为运筹学的一大分支，常分成线性规划、非线性规划和动态规划三个部分。线性规划是运筹学创立初期人们重点研究的内容，是生产、科研和企业管理中一种有效的优化技术，其理论完善，方法简便，应用广泛，成为规划问题乃至运筹学最基本的内容。第一节线性规划的基本概念一、线性规划的数学模型线性规划问题通常有两大类型：一类是在一定的资源条件限制下，如何组织安排生产获得最大的经济效益（如产量最多或利润最大等）；另一类是当任务或目标确定后，如

2、何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工或时间等）去完成给定的任务或目标。现各举一例如下：例1.1产计划问题常山机器厂生产I、II两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如表1-1所示：表1-1单位产品消耗设备工时III设备工时限量（小时）设备A2212设备B4016设备C0515单位利润（元）23如何安排生产才能使总的利润最大？解设计划期内两种产品的产量分别为x1和x2，由于设备A在计划期内的有效时间为12h，不允许超过，于是有2x1+2x2≤

3、12。对于B、C设备也可列出类似的不等式：4x1≤16；5x2≤15。该厂的目标是在各种设备允许的情况下，使总的利润收入z=2x1+3x2为最大。因此例1可以归结为如下的数学模型例1.2配料问题一饲养场饲养某种动物用于出售，该动物每天至少需要700克蛋白质，30克矿物质，100毫克维生素。现有四种饲料可供选用，各种饲料每千克营养成分含量及单价如表1-2所示：表1-2每千克饲料中各营养成分的含量IIIIIIIV需要量蛋白质（克）3215700矿物质（克）10.50.2230维生素（毫克）0.510.32.5100单价（元/千克）0.81.20.62四种饲料各采购多

4、少，才能使总费用最小？解设四种饲料分别采购x1,x2,x3,x4千克.根据该动物每天对蛋白质的需求，有。同理得到类似的不等式；。该饲料厂的目标是在满足动物生长需求的情况下，使总的费用为最小。因此例2可以归结为如下的数学模型从上面的例子可以看出，所谓规划问题，就是求规划目标在若干限制条件下的极值问题。规划问题的数学模型包含三个组成要素：（1）决策变量或变量，即决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。通常用x1，x2，…，xn表示；（2）目标函数，即问题要达到的目标要求，表示为决策变量的函数。通常用z=f(x1，x2，…，xn)表示，按优化目标

5、分别在这个函数前面加上max或min；（3）约束条件，即决策变量取值时受到各种可用资源的限制，通常表示为含决策变量的等式或不等式。若在规划问题的数学模型中，决策变量是可控的连续变量，目标函数和约束条件都是线性的，则此类模型称为线性规划问题或线性规划（LinearProgramming）。实际问题中线性的含义：一是严格的比例性，如生产某产品可获取的利润和产品的数量严格成比例；二是可叠加性，如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和。一般地，假设线性规划数学模型有n个决策变量，分别用xj（j=1,2…,n）表示。目标函数中变量系数用cj表示

6、,通常cj称为价值系数。有m个约束条件，第i个约束条件中变量xj的系数用aij表示，aij常称为工艺系数或技术系数。约束条件右端的常数用bi表示，通常bi称为资源限量或资源拥有量。于是线性规划数学模型的一般表达式可写成(1.1)一个线性规划问题有解，是指能找出一组xj(j＝1,...,n)的值既满足(1.1)中的约束条件，又满足决策变量的取值要求，此时称X=(x1,x2,...,xn)T为该问题的可行解。全部可行解的集合称为可行域．特别的，能使目标函数达到最优的可行解称为最优解。研究线性规划的根本目的在于求出它的最优解，这个过程称为求解线性规划问题。式(1.1)

7、也可简写为(1.2)若各个约束条件左右两端的连接符号都相同（都是“≤”，或都是“=”，或都是“≥”），则可利用向量把线性规划问题写成(1.3)在式(1.3)中式(1.3)还可用矩阵形式表示为(1.4)式(1.4)中A称为约束条件中变量的系数矩阵，或简称为约束变量的系数矩阵。注意在实际意义中决策变量的取值一般为非负实数。在单纯数学意义下也可以有决策变量取非正实数。另外若某个决策变量xj表示第j种产品本期产量相对于前期产量的变化量，则xj的取值范围可以是全体实数。一、图解法对于仅含有两个决策变量的线性规划问题有一种简单直观的几何方法——图解法。图解法的步骤是：先在平

8、面直角坐标系中画出约束条