第一章运筹学中的几个数学问题及模型数学预备知识：矩阵的基本概念及初等运算参考文献1.《运筹学》教材编写组编，《运筹学》，清华大学出版社，2005年6月第3版2.田丰、马仲番编著，图与网络流理论，科学出版社，1987年3.刘振宏、蔡茂城(译)，《组合最优化：算法和复杂性》，清华大学出版社,1988年第1版4.C.H.PapadimitriouandK.Steiglitz,CombinatorialOptimization:AlgorithmsandComplexity,Printice-Hall,1982运筹学的性质和特点定义2：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。特点2：该定义表明运筹学具有多学科交叉的特点，如综合应用经济学、心理学、物理学和化学中的一些方法。特点3：由系统的观点研究功能关系。综上所述，运筹学的定义可以提炼为：定义3：运筹学就是利用计划的方法和多学科专家组成的队伍，把复杂的功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量依据。运筹学与计算机运筹学的工作步骤1.线性规划问题及其数学模型问题表1—1解：假设x1、x2分别表示在计划期内生产产品I、II的数量，则该计划问题可用如下数学模型表示为：目标函数MaxZ=2x1+3x2约束条件其最优解为x1=4,x2=2,最优值为z=14。例2:（营养问题）某养鸡场所用的混合饲料是由n种配料组成。要求这种混合饲料必须含有m种不同的营养成份，而且要求每单位混合饲料中第i种营养成份的含量不能低于bi(i=1,2,…,m）。已知第i种营养成份在每单位的第j种配料中的含量为aij,j=1,2,…,n，每单位的第j种配料的价格为cj。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小。以上两个例子，从数学上来讲,它们的共同特征是:(1)每个问题都用一组决策变量(x1,x2,···,xn)表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2)存在一定的限制条件(称为约束条件)，这些条件都可以用关于决策变量的一组线性等式或不等式来表示。(3)都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为(1.1)和(1.2)形式。在该模型中，方程(1.1)称为目标函数，(1.2)称为约束条件。线性规划问题的解法例3.求解线性规划minz=x1+2x2+x3-x4s.t.2x1+4x2+x3+x4=62x1+x4+x5=3x1-x2+x5=1x1,x2,x3,x4,x5≥0解：对原问题进行初等变换，得到minz=x1+2x2+x3-x4s.t.x1+3x2+x3=4x1+x2+x4=2x1-x2+x5=1x1,x2,x3,x4,x5≥0即minz=2+x1s.t.x1+3x2≤4x1+x2≤2x1-x2≤1x1,x2≥0然后用图解法求解。求出x1，x2最优解后，再求出x3,x4,x5，就得到了原问题的最优解。线性规划问题的标准型其中：c=(c1,c2,···,cn)T，X=(x1,x2,···,xn)T，b=(b1,b2,···,bm)T,A=(P1,P2,···,Pn)，Pj=(a1j,a2j,···,amj)T，0=(0,0,···,0)T,(j=1,2,···,n)。我们称A为约束方程组的系数矩阵(m×n阶),一般情况下m<n,m和n为正整数,分别表示约束条件的个数和决策变量的个数,C为价值向量,X为决策向量,通常aij,bi,cj为已知常数，这里i=1,2,···,m,j=1,2,···,n。对偶问题的提出我们将简单叙述对偶线性规划。这里的对偶是指对同以事物（或问题）从不同的角度观察，有两种不同的表述。例如：“平面中矩形的面积与周长的关系”有下面两种表述周长一定时，面积最大的矩形式正方形；面积一定时，周长最小的矩形式正方形。在前面例1中，我们讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题。假设该工厂的决策者决定不生产产品I、II，而将其所有资源出租或出售。这时，工厂的决策者就要考虑给每种资源进行定价的问题。设用y1、y2、y3分别表示出租单位设备台时的租金和出让单位原材料A、B的附加费。作决策时，需要如下的比较：若一个单位设备台时和四个单位原材料A可以生产一件产品I，可获利2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入应