第1章-线性规划模型-宋

第一章 线性规划模型第一章 线性规划模型线性规划（Linear Programming）是数学规划的一个重要组成部分，是最优化与运筹学理论中的一个重要分支和常用的方法，是最优化理论的基础性内容。第一节 线性规划问题及其数学模型一、问题的提出 在生产管理和经营活动中经常提出一类问题，即如何利用有限的人力、物力、财力等资源，以便得到最好的经济效果。例1 生产计划问题某工厂在计划期内要安排生产、的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23解：设分别表示在计划期内生产产品、的产量。由于资源的限制，所以有：机器设备的限制条件: 原材料A的限制条件： （称为资源约束条件）原材料B的限制条件： 同时，产品、的产量不能是负数，所以有（称为变量的非负约束）。显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量以得到最大的利润，即使目标函数的值达到最大。综上所述，该生产计划安排问题可用以下数学模型表示：例2 运输问题 某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保证产销平衡的条件下，如何调运可使总运费最少？销地单位运价 产地B1B2B3B4产量A15610360A2419740A3423860销量30504040解:（1）决策变量：设为从产地运到销地的运量 （2）目标函数：总运费最小（3）约束条件： 产量约束销量约束非负约束模型为：二、线性规划问题的模型上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有以下共同的特征。（1）每个问题都可用一组决策变量表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划（LP）问题的数学模型，其一般形式为：或矩阵形式或向量形式（或）其中，称为价值系数向量；称为技术系数矩阵(也称消耗系数矩阵)；称为资源限制向量；称为决策变量向量。三、建立线性规划模型的一般步骤：（1）确定决策变量；（2）确定目标函数；（3）确定约束条件。例3 投资计划问题某公司经调研分析知，在今后三年内有四种投资机会。第种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？解：问题分析.该问题的实际投资背景如下表所示：年份一二三四（1）决策变量：设表示第i年对第j个方案的投资额，（2）目标函数：第三年年未的本利和为（3）约束条件：每一年的投资额应等于当年公司拥有的资金数：; ; 每个方案投资额的限制：; ; 非负约束：。例4 混合配料问题某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲，乙，丙。已知各种牌号糖果中A，B，C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果各多少时，使该厂获利最大。试建立这个问题的线性规划模型。甲乙丙原料成本(元/kg)第每月限制量(kg)A60%30%2.002000B1.502500C20%50%60%1.001200加工费(元/kg)0.500.400.30售价(元/kg)3.402.852.25解：(1)设决策变量表示生产第种糖果(表示甲，乙，丙三种糖果)耗用的第种原料(表示A,B,C三种原料)的kg数(2)目标函数：该厂的获利为三种牌号糖果的售价减去相应的加工费和原料成本。(3)约束条件：四、LP问题的标准形1. 标准型为了讨论LP问题解的概念和解的性质以及对LP问题求解方便，必须把LP问题的一般形式化为下面统一的标准型：或或标准型的特点：（1）目标函数是最大化类型（2）约束条件均由等式组成（3）决策变量均为非负 （4）2.化一般形式为标准型目标函数：若约束为“”型左边+“松驰变量”；若约束为“”型左边“剩余变量”若变量；若变量无限制令若右边常数等式两边同乘以。例5 化下述问题为标准型解：（1）首先考察变量：令，其中；（2）在第一个约束不等式的左端加入松弛变量；（3）对第二个约束不等式两边同时乘以并减去剩余变量；（4）令，则原问题化为如下标准型：第二节 LP问题解的概念和性质一、几个概念1.可行解、最优解、基、基变量、基础解、基础可行解、退化解、基础最优解设线性规划问题 (1-1) (1-2)我们称满足约束条件(1-2)的为可行解。所有可行解构成可行解集，即可行域。使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。设为矩阵，是中的阶非奇异子矩阵（即），则称是LP问题的一个基。若是LP问题的一个基，则由m个线性无关的列向量组成，即，其中，()称为基向量。与基向量相对应的变量称为基变量，其它变量称为非基变量。显然，对应于每个基总有个基变量，个非基变量。设是LP问题的一个基，令其个非基变量均为零，所得方程的解称为该LP问题的一个基础解。显然，基与基础解是一一对应的，基础解的个数。在基础解中，称满足非负条件的基础解为基础可行解，对应的基称为可行基。如果基础解中非零分量的个数小于，则称此基础解为退化的，否则是非退化的。如果对应于基的基础可行解是LP问题的最优解，则称为LP问题的最优基，相应的解又称基础最优解。LP问题解之间的关系如图所示：可行解基解最优解基最优解2.凸集若连接维点集中任意两点的线段仍在内，则称为凸集。即，都有，则称为凸集。例如，矩形、三角形、圆、四面体等都是凸集。圆环、空心球等都不是凸集。3.极点若凸集中的点不能成为任何线段的内点，则称为的极点。即，都有则称为的极点。例如，矩形、三角形、四面体的顶点，圆周上的点等都是极点。二、线性规划问题解的性质定理1 线性规划问题的可行域是凸集。定理2 可行域中的点是极点的充分必要条件是为基础可行解。定理3 LP问题最优解若存在，则必可在可行域的极点上达到。第三节 LP问题的解法一、两个变量LP问题的图解法LP问题图解法的步骤： （1）画出直角坐标系；（2）依次做每条约束直线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线）,根据目标函数（最大或最小）类型，移该直线即将离开可行域处，则与目标函数线接触的最终点即表示最优解。例1：用图解法求解如下线性规划问题Q2(6,4)Q1(26/3,0)Q3(0,8)A(12,0)B(0,13)最优解为 最优值为 解的几种情况：（1）此例有唯一解Q2，即，（2）有无穷多最优解（多重解），若将目标函数改为，则线段Q2，Q3上的点均为最优解。（3）无界解(4)无可行解图解法只适用于两个变量（最多含三个变量）的LP问题。二、单纯形法 虽然线性规划问题的可行域（凸集）的顶点数目是有限的（），在理论上，可以通过枚举法找出所有的基可行解，然后一一进行比较，最终找出最优解，但在实际上，当和的值较大时，这种方法是行不通的，需要用更有效、更简便的、适合于在计算机上用通用软件求解的方法来确定最优解。单纯形法是一种既简便又有效，也适合用计算机通用软件求解线性规划问题最优解的方法。1. 单纯形法的基本思路：LP问题的标准形求出一个初始基可行解Y停判别此基可行解是否最 优 解 换基迭代N求出使目标函数值得到改善的基可行解2. 单纯形法的计算步骤（表格形式）（1）建立初始单纯形表，假定设 将目标函数改写为：把上述方程组和目标函数方程构成个变量，个方程的方程组，并写成增广矩阵的形式：以非基变量表示基变量，.代入中的基变量,有令 于是因此，上述的增广矩阵就可写成：再令则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B）检验数行上述初始单纯形表可确定初始可行基和初始基可行解：，从初始单纯形表建立的过程可以看到以下事实： 凡LP模型中约束条件为“”型，在化为标准型后必有，如果，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数则以相反数填入检验数行各相应位置。 在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。 （2）判别最优解 在T(B)中，若所有的检验数 ()则为最优基，相应的基可行解为最优解，停止计算。 在T(B)中，若有，且的系数列向量，则该问题无界，停止计算。否则转入（3）。（3）换基迭代（基变换） 先确定进基变量，根据来确定或，即选择最小检验数或行从左至右选择第一个负检验数所对应的变量进基。 按最小比值原则确定出基变量：。 以为主元，进行初等行变换（又称旋转变换），即将列向量变换为单位列向量：返回（2）。换基迭代的关键在于将换入变量对应的列向量用初等行变换方法变换成单位列向量。其中主元变成。即第L个分量。如果在最终表中有非基变量的检验数为，则该问题有多重最优解。例2 求解下列线性规划问题解：引进松驰变量，化为标准形得：从标准形中可看出存在可行基，基变量为；非基变量为。建立初始单纯形表得： 由于的检验数均为负，且的检验数绝对值最大，选取为进基变量；再按最小比值，因此选取为出基变量，进行换基迭代。 1 1 表中最后一行的所有检验数均为非负数，表明目标函数已达到最大值，上述表为最终表。从表中可得到最优解为，最优值为。三、单纯形法的进一步讨论用人工变量法求初始基可行解1、人工变量法若对LP模型标准化后，不具有时，如何办？此时可采用人工变量法得到初始基可行解。所谓人工变量法是在原问题不含有初始可行基的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有的另一个LP问题后求解。当增加的人工变量全部取值为时，才与原问题等价。这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，即人工变量全部出基，则得到原问题的一个基可行解。在最终表中若人工变量不能全部被换出，则说明原问题无可行解。因此，该法的关键在于将人工变量全部换出。2、大M法（通过下例简略介绍其方法与步骤） 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此当目标函数要实现最大时，假定人工变量的系数为，当目标函数要实现最小时，假定人工变量的系数为（其中为任意大的正数）。例3 用大法求解解：其中为剩余变量，为人工变量，为任意大的正数。注意到：分别在约束条件中增加人工变量是为了构成“人工基” 对于Min的目标函数采用，而对于Max的目标函数则采用作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由基变量转为非基变量，使之恢复原问题，或与原问题等价。 对于判别最优性准则应是。 大法适合于计算机计算，不适用于手工求解。所以本题求解过程略。3、两阶段法第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：s.t.然后用单纯形法求解上述模型。若，则原问题无可行解，停止计算。若，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换为原问题的目标函数作为第二阶段计算的初始表。例4 将上例用两阶段法求解。 解：原问题： 辅助问题： 用单纯形法求解的迭代表如下： 01111/3 1 -1/3 0 1/3 02/3 0 1/3 -1 -1/3 112/3 0 1/3 -1 -4/3 0 1/23/2 0 1 -1/2 1/2 1/2 -1/2 1 0 1/2 -3/2 -1/2 3/200 0 0 0 -1 -1上述表中目标函数值，且人工变量已全部出基，得到原问题的一个可行基和一个基可行解。去掉人工变量列，并将目标函数行换为原目标函数行得： 上表中最后一行所有检验数均非正（因为是求极小化问题），所以上述表已是原问题的最优表。从表中可知原问题的最优解为，最优目标函数值为。注意：第二阶