第10章资源分配模型与线性规划线性规划是运筹学中研究的比较早，理论上已趋向成熟并且应用广泛是解决最优化问题非常有效地工具。
早在20世纪30年代末，前苏联数学家康托洛维奇首先提出了资源分配模型的线性规划，于1947年由美国人丹茨格提出了线性规划的单纯算法，较好的解决了线性规划的求解问题，从而奠定了线性规划作为一门学科的基石。
线性规划研究的对象大体可分为两大类：（1）在现有的人、财、物等资源的条件下，研究如何合理的计划、安排，可使得某一目标达到最大，如产量、利润目标等。
（2）在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使生产成本、费用自小等。
（3）线性规划中研究的问题要求目标与约束条件函数均是线性的，并且只有一个目标函数。
在经济管理问题中，大量的问题是线性的，有的可以转化为现行的，从而线性规划有着极大地应用价值。
§10.1 线性规划问题在经济管理中，经常遇到一类如何合理的使用有限的劳动力、设备、资金等资源，异化的最大的效益的问题。
例 1 某工厂生产甲、乙两种产品，生产这两种产品要消耗某种原料。
生产每吨产品所需要的原料量及所占设备时间，见表10-1.该厂每周所能得到的原料为16吨，每周设备能多开15个台班，且根据市场需要，甲种产品每周产量不应超过4吨。
已知该厂生产每吨甲、乙两种产品的利润分别为15万元及6万元。
问：该厂应如何安排两种产品才能是每周获得的利*最大？简历数学模型社该厂每周安排生产甲种产品的产量为x1吨，乙种产品为x2吨，则每周所能获得的利润总额为z=15x1+6x2（万元）。
但生产量的大小要受到原料量技术倍的限制及市场最大需求量的制约，即x1，x2要满足一下一组不等式条件：3x1+2x2≤16，5x2+x2≤15，（10—1）x≤4，此外，产品x1，x2还应是非负的数：x1≥0，x2≥0. （10—2）因此从数学角度看，x1，x2应在满足资源约束（10-1）及非负约束（10-2）条件下，使利润z取最大值：Max z=15x1+6x2. （10—3）经过以上分析，可将一个生产安排问题抽象为满足一组约束条件下，寻求变量x1，x2，使目标函数达到最大值得一个线性规划。
同样，在经济生活中为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使消耗为最少，一下给出一个求目标函数最小化的线性规划问题。
例2某公司需要生产某产品，需要Ⅰ，Ⅱ两种原料至少35吨，其中原料Ⅰ至少购进10吨。
但由于Ⅰ，Ⅱ两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨原料Ⅰ需要2个小时，加工每吨原料Ⅱ需要1小时，而公司总共有60个加工小时。
又知道每吨原料Ⅰ的价格为4万吨，每吨原料Ⅱ的价格为6万元，试问：在满足生产需要的前提下，在公司加工能力的范围内，如何购买Ⅰ，Ⅱ两种原料，是的购进成本最低？解设x1为购进原料Ⅰ的吨数，x2为购进原料Ⅱ的吨数。
则得到了次线性规划的数学模型如下：目标函数：Min z=2x1+3x2；（10—4）约束条件：x1+x2≥35，(10—5)x1 ≥10，（10—6）2x1+x2≤60，（10—7）x1≥0，x2≥0. （10—8）由于上述两个数学模型的目标函数为变量的线性函数，同时约束条件也为变量的线性等式或不等式，因此这两个模型成为线性规划。
一般线性规划的建模过程：首先，要明确在什么条件下要达到什么目标。
每一个问题都定义一组决策变量，一般记为（x1，x2,……,xn），表示某一方案；这组决策变量的值就代表一个具体方案，通常这些变量取之是非负的。
用决策变量的线性函数形式表示出所要寻找的目标，称之为目标函数；按问题的不同，要求目标函数在满足约束条件下实现最大化或最小化。
用一组决策变量的等式或不等式来表示在解决问题过程上所必须遵循的约束条件。
§10.2 图解法对于只包含两个决策变量的线性规划问题，可以使用图解法来求解。
图解法简单直观，有助于了解线性规划问题求解的基本原理，在以x1.x2为坐标轴的直角坐标系里，图上任意一点的坐标即表示决策变量x1，x2的一组值，也就代表了一个具体的决策方案。
例2以例1为例说明图解法的主要步骤，例1的数学模型如下：Max z=15x1+6x2；（10—9）s．t．3x1+2x2≤16，5x2+x2≤15 (10—10)x1≤4x1≥0，x2≥0. (10—11)首先作一个以x1，x2为坐标轴的直角坐标系（见图10—1）约束条件（10—10）中有单个不等式。
暂且将第一个不等式3x1+2x2≤16变为等式3x1+2x2=16，他在坐标系中应是一条直线，记L1，显然L1上的点的坐标（x1，x2）都满足3x2+2x2=16，则坐标（x1，x2）满足3x1+2x2 ＜16的点都在直线L1的左下方（显然坐标满足3x1+2x2＞16的点都在直线L1的右上方）。
即直线L1将平面Ox1x2上的点分为两半。
因次我们通常也称不等式3x1+2x2≤16为半平面（含直线L 1）,见图10—1，同理设直线5x1+x2=15为直线L2，则5x1+x2≤15为L2左下半平面，满足x1≤14得点位于直线L3，x1=14的左半平面，满足非负约束条件x1≥0及x2≥0的点分别为坐标平面的上半平面及右半平面。
因此，满足约束条件（10—10）及（10—11）的点应是上述5个平面的交集，即图10—1中的四边形OABC区域（含边界），该区域称之为可行域。
满足约束条件及非负条件的解（x1，x2）称之为可行解。
本题即变为要在可行域OABC中找到一个点（解）x*=（x1*，x2*），它的目标函数（10—9）中z的值在所有可行解中达到最大。
目标函数z=15x1+6x2在坐标平面Ox1x2中，可视为以x1，x2为变量、z为参数的一族直线。
如5x1+2x2=5，即为图10—1中直线l1：5x1+2x2=10，即为l2….。
因此5x1+2x2=z是以z为参数的一族互相平行的直线。
在同一直线5x1+2x2=z0上的点（x1，x2），他们的目标函数值都相等。
因此称为等值线族。
在这族等值线中z取得最大且又要在可行域内（或说也可行域相切）的直线l*便是我们要寻找的。
其与可行域的交点就是最优解x*。
具体做法是，首先求出z=15x1+6x2的斜率为－6/15.计斜率为－6/15的垂直方向为t，在坐标平面上画出t。
然后将任意一根等值线如l1，沿t方向（即z增加的方向）推进平行线，直到该平行线将离开而还未离开可行域时的一根等值线即为l*，在图10—1中即为过点B的等值线。
点B即为最优解。
容易计算，点B的坐标为（2，5）。
因此本题的最优解x*=（2，5）。
最优值为z*=15 ×6 ×5=60.即该厂每周安排生产量为2吨，乙种为5吨。
每周可获最大利润为60万元。
假若数学模型中对目标函数z试求极小值，显然等值线应按斜率垂直的负方向推进平行线，从而求得l*即最优解x*。
对此问题做经济解释与分析，可知生产甲、乙两种产品分别是2吨、5吨，则原料总量为3×2+2×5=16（吨），正好达到约束条件的最高限制。
同样，对设备来说，5×2+5=15（台班），也恰好达到设备约束的最多限额。
而甲产品只有2吨，还有剩余量。
同样对于大于等于的约束条件变为等式约束条件中，可以增加一些代表最低限约束的超过量，称之为剩余变量，把大于等于的约束条件变为等式约束条件，假如松弛变量与剩余变量后例2的数学模型为目标函数：Min z=4x1+6x2+0s1+0s2+0s3；约束条件：x1+x2－x1=35，x1－x2=10，2x1+x2+s3=60，x1，x2，s1，s2，s3≥0.从约束条件中可以知道s1，s2为剩余变量，s3为松弛变量（s是松弛和剩余slack和surplus的第一个字母）。
上式中所有的约束条件也都为等式，故这也是线性规划问题的标准形式，在线性规划单纯形法中是很重要的。
从图解法作图结果来分析，线性规划问题应有以下几种可能出现的结果：（1）有唯一最优解，如例1和例3；（2）有无穷多个最优解。
例 4 若在例1中，其他都不变，而甲种利润从15万元改为5万元，则线性规划模型为Max z=9x1+6x2；（10—12）S．t1`21211,23216,515,4,,0.x xx xxx x+≤⎧⎪+≤⎪⎨≤⎪⎪≥⎩（10—13）解有约束条件（10—13）做出可行域D(见图10—3)为多边形OABC。
对目标函数z=9x1+6x2，做等值线l1：9x1+6x2=5.将l1沿斜率为－6/12的垂直方向推进平行线，平行线将离开可行域D而尚未离开时，与D相切与边BC。
因此l*记为边BC,而线段BC上任一点的目标函数值均等，因此线段BC上任一点都是最优解。
故本例有无穷多个最优解：如点B（2，5），点C(0，8)，点A（3，0）等。
最大值为z*=9×2+6×5=48.有的软件要求变量的非负约束，若x k为无约束的变量，则令x k=xk’+xk’’,其中x k’,x k’’ 0.定理若线性规划有有限的最优解，则它必在可行域D的某个极点达到。
对于一般的变量多于两个的情形，用图解法求解时比较困难的。
但是很多数学软件。
如MA TLAB 和LINDO都提供了很简便的阶线性规划问题的命令或语句。
§10.3 竞赛题举例例5某厂拟生产甲、乙两种适销产品，每件销售收入分别为3千元/件、2千元/件。
甲、乙产品都需要在A,B两种设备上加工，所需工时甲为：在A,B两种设备上分别为1台时/件、2台时/件，乙在A,B 两种设备上分别为2台时/件、1台时/件。
A,B设备每月有效可使用台数分别为400，500.市场初期预测反映乙产品的销售最多不能超过150件。
1）工厂如何依据初期预测安排生产，使产品销售总收入量最大？2）工厂依据上述预测确定甲、乙两种产品的最有生产规模后，市场销售收入发生变化，乙产品的销售收入每件仍为2千元/件，而甲产品的销售收入将变化，因改变生产规模需要很高的代价，使计算甲产品的销售收入变化的最小、最大限度。
上述生产规模不改变，仍使产品销售总收入最大。
解设甲、乙两种产品的产量分别为x1，x2件，由此，A,B设备每月有效可使用台时必须满足约束，同时，乙产品应满足消耗资源不能超过150吨的约束，则数学模型为Max z=3x1+2x2；s.t. x1+2x2≤400,2x1+x2≤500,x2≤500,x1,x2≥0.使用图解法，见图10—2，得点A（0，150），B（100，150），C（200，100），D（250，0）。
使用图解法可得最优解为（200，100），即生产甲产品200件、乙产品100件，总产值为800千元。