第一章线性规划。
1 线性规划。
在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(linear programming 简记lp)则是数学规划的一个重要分支。自从2023年g.
b. dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。
1.1 线性规划的实例与定义。
例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？
上述问题的数学模型：设该厂生产台甲机床和乙机床时总利润最大，则应满足。
目标函数1)
约束条件2）
这里变量称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为即subject to)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。
总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。
在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。
1.2 线性规划的matlab标准形式。
线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，matlab中规定线性规划的标准形式为。
其中和为维列向量，、为适当维数的矩阵，、为适当维数的列向量。
例如线性规划。
的matlab标准型为。
1.3 线性规划问题的解的概念。
一般线性规划问题的标准型为。
可行解满足约束条件（4）的解，称为线性规划问题的可行解，而使目标函数（3）达到最小值的可行解叫最优解。
可行域所有可行解构成的集合称为问题的可行域，记为。
1.4 线性规划的**法。
**法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用**法来求解例1。对于每一固定的值，使目标函数值等于的点构成的直线称为目标函数等位线，当变动时，我们得到一族平行直线。
对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为，最优目标值。
从上面的**过程可以看出并不难证明以下断言：
1）可行域可能会出现多种情况。可能是空集也可能是非空集合，当非空时，它必定是若干个半平面的交集（除非遇到空间维数的退化）。既可能是有界区域，也可能是无界区域。
2）在非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。
3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域的“顶点”。
上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的维空间中，满足一线性等式的点集被称为一个超平面，而满足一线性不等式（或）的点集被称为一个半空间（其中为一维行向量，为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。
易见，线性规划的可行域必为多胞形（为统一起见，空集也被视为多胞形）。
在一般维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。
定义1 称维空间中的区域为一凸集，若及，有。
定义2 设为维空间中的一个凸集，中的点被称为的一个极点，若不存在及，使得。
定义1 说明凸集中任意两点的连线必在此凸集中；而定义2 说明，若是凸集的一个极点，则不能位于中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域的顶点均为的极点（也没有其它的极点）。
1.5 求解线性规划的matlab解法。
单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的matlab解法。
matlab中线性规划的标准型为。
基本函数形式为linprog(c,a,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在 matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：
x,fval]=linprog(c,a,b,aeq,beq,lb,ub,x0,options)
这里fval返回目标函数的值，lb和ub分别是变量的下界和上界，是的初始值，options是控制参数。
例2 求解下列线性规划问题。
解 （）编写m文件。
c=[2;3;-5];
a=[-2,5,-1]; b=-10;
aeq=[1,1,1];
beq=7;
x=linprog(-c,a,b,aeq,beq,zeros(3,1))
value=c'*x
）将m文件存盘，并命名为。
）在matlab指令窗运行example1即可得所求结果。
例3 求解线性规划问题。
解编写matlab程序如下：
c=[2;3;1];
a=[1,4,2;3,2,0];
b=[8;6];
x,y]=linprog(c,-a,-b,zeros(3,1))
1.6 可以转化为线性规划的问题。
很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如：
例4 规划问题为。
其中，和为相应维数的矩阵和向量。
要把上面的问题变换成线性规划问题，只要注意到事实：对任意的，存在满足，
事实上，我们只要取，就可以满足上面的条件。
这样，记，，从而我们可以把上面的问题变成。
例5 其中。
对于这个问题，如果我们取，这样，上面的问题就变换成。
此即我们通常的线性规划问题。
2 运输问题(产销平衡)
例6 某商品有个产地、个销地，各产地的产量分别为，各销地的需求量分别为。若该商品由产地运到销地的单位运价为，问应该如何调运才能使总运费最省？
解：引入变量，其取值为由产地运往销地的该商品数量，数学模型为。
显然是一个线性规划问题，当然可以用单纯形法求解。
对产销平衡的运输问题，由于有以下关系式存在：
其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。
3 指派问题。
3.1 指派问题的数学模型。
例7 拟分配人去干项工作，每人干且仅干一项工作，若分配第人去干第项工作，需花费单位时间，问应如何分配工作才能使工人花费的总时间最少？
容易看出，要给出一个指派问题的实例，只需给出矩阵，被称为指派问题的系数矩阵。
引入变量，若分配干工作，则取，否则取。上述指派问题的数学模型为。
5)的可行解既可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用中的一个置换表示。
5)的变量只能取0或1，从而是一个0-1规划问题。一般的0-1规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为），其非负可行解的分量只能取0或1，故约束可改写为而不改变其解。
此时，指派问题被转化为一个特殊的运输问题，其中，。
3.2 求解指派问题的匈牙利算法。
由于指派问题的特殊性，又存在着由匈牙利数学家konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵，则以或为系数矩阵的指派问题具有相同的最优指派。
例8 求解指派问题，其系数矩阵为。
解将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得。
再将第3列元素各减去1，得。
以为系数矩阵的指派问题有最优指派。
由等价性，它也是例7的最优指派。
有时问题会稍复杂一些。
例9 求解系数矩阵的指派问题。
解：先作等价变换如下。
容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：
1) 对未选出0元素的行打；
2) 对行中0元素所在列打；
3) 对列中选中的0元素所在行打；
重复（2）、（3）直到无法再打为止。
可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得。
现在已可看出，最优指派为。
4 对偶理论与灵敏度分析。
4.1 原始问题和对偶问题。
考虑下列一对线性规划模型：
和。称（p）为原始问题，（d）为它的对偶问题。
数学建模 线性规划
这家公司希望广告费用不超过800 千元 还要求 1 至少要有两百万妇女收看广告 2 电视广告费用不超过500 千元 3 电视广告白天至少播出3次，最佳时间至少播出2次 4 通过广播 杂志做的广告要重复5到10次。5.2解 设电视 白天，最佳时间 无线电广播 杂志，的广告播出分别为 x x x alt...
数学建模线性规划
x11 x12 x13 x14 50 x21 x22 x23 x24 60 x31 x32 x33 50 x11 x21 x31 30 x11 x21 x31 80 x12 x22 x32 70 x12 x22 x32 140 x13 x23 x33 10 x13 x23 x33 30 x14 x2...
数学建模线性规划
题目。根据调查我省对哪几种纸的需求量最大 每种纸的耗费原料量 原料供需 纸的造价 原料造价 环境资源等，求一家纸品生产公司怎样安排每种纸的生产量才能满足成本最小？1.造纸业的定义。造纸业是制造和使用浆状植物性纤维原料各种工艺过程的概述，从纸浆到纸，进而到种类繁多的纸品构成了纸业的各个生产环节和子部门...