运筹学OperationsResearch1.1数学模型MathematicalModel1.1线性规划的数学模型MathematicalModelofLP【例1-1】生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定，每件产品甲需要消耗材料A2公斤，消耗材料B1公斤，每件产品乙需要消耗材料A1公斤，消耗材料B1.5公斤。已知在计划期内可供材料分别为40、30公斤；每生产一件甲、乙两产品，企业可获得利润分别为40、30元，如表1－1所示。假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大。【解】设x1、x2分别为甲、乙产品的产量，数学模型为：线性规划的数学模型由【例1-2】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1-2所示。【解】设xj(j=1，2，…，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为1【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？设xj(j=1,2…,10)为第j种下料方案所用圆钢的根数。则用料最少数学模型为:1【例1-4】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%~55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1-4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。解:设xj（j=1,2，…，5）是第j种矿石数量，得到下列线性规划模型11.1线性规划的数学模型MathematicalModelofLP1.1线性规划的数学模型MathematicalModelofLP整理后得到线性规划模型1.1.2线性规划的一般模型一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2…,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成在实际中一般xj≥0,但有时xj≤0或xj无符号限制。1.什么是线性规划，掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。1.2图解法GraphicalMethod图解法的步骤：x1222x1由以上例题可知，线性规划的解有4种形式：1.通过图解法了解线性规划有几种解的形式2.作图的关键有三点(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动1.3线性规划的标准型StandardformofLP在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。max(或min)Z=c1x1+c2x2+…+cnxn或写成下列形式：通常X记为：称Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。【例1-12】将下列线性规划化为标准型(3)第二个约束条件是≥号，在≥号左端减去剩余变量(Surplusvariable)x5，x5≥0。也称松驰变量综合起来得到下列标准型当某个变量xj≤0时,令x/j=－xj。当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束【例1-13】将下例线性规划化为标准型得到线性规划的标准形式1.如何化标准形式？1.4线性规划的有关概念BasicConceptsofLP设线性规划的标准型maxZ=CX（1.1）AX=b（1.2）X≥0（1.3）式中A是m×n矩阵，m≤n并且r（A）=m，显然A中至少有一个m×m子矩阵B，使得r（B）=m。【例1-14】线性规划由线性代数知，基矩阵B必为非奇异矩阵并且|B|≠0。当矩阵B的行列式等式零即|B|=0时就不是基可行解(feasiblesolution)满足式（1.2）及（1.3）的解X=（x1,x2…，xn)T称为可行解。显然，只要基本解中的基变量的解满足式（1.３）的非负要求，那么这个基本解就是基本可行解。由于是基本解，从而它是基本可行解，在中x1<0,因此不是可行解，也就不是基本可行解。可行基基可行解对应的基称为可行基；最优基基本最优解对应的基称为最优基；如上述B3就是最优基，最优基也是可行基。基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：凸集(Convexset