第1章线性规划及单纯形法 9 法。 1.1.1线性规划问题的提出 线性规划是指求解一组决策变量，该组决策变量在满足一些线性约束条件的基础上， 使得某个线性函数的值达到最大或最小。下面通过两个例子加以说明。 么模型引入1.1（生产安排问题）某工厂生产甲、乙两种产品，而生产这两种产品需要 用到原材料A和原材料B。该厂可以利用的原材料A有16kg,原材料B有12kg。生产 一个单位甲产品需要消耗2kg原材料A和4g原材料B,生产一个单位乙产品需要消耗 3kg原材料A和1kg原材料B。经过测算，一个单位的甲产品可以获得6元的利润，一 个单位的乙产品可以获得7元的利润。问：该厂应如何安排生产才能获得最大利润？ 解这个问题问的是如何安排生产才能获得最大利润。什么叫安排生产呢？在这个 简化的题目中，所谓安排生产当然指的是生产甲、乙两种产品各多少个单位。所以，这是 我们要回答的不知道的量。设生产甲、乙两种产品各为x1和x2个单位，于是按照题目 的假设，该厂此时可以获利z=61+7红2。生产不能是随意的，在这里，生产所耗费的原 料当然不能超过该厂的拥有量。于是，生产必须在如下约束下进行： 2x1+3x2≤16（原料A的限制） 4x1+x2≤12（原料B的限制） 此外，x1,x2是甲、乙产品的计划生产量，所以有x1≥0，x2≥0。用max表示maximize(即 最大)，用subject to或such that表示受约束（其缩写为s.t.),于是可以将上面的分析表 示为： max z=6x1+7x2 s.t. 2x1+3x2≤16 (1-1-1) 4红1+x2≤12 D1,x2≥0 这就是该问题的数学模型。它将原问题用数学的语言完全表达出来了。 么模型引入1.2（最佳下料问题）某汽车制造过程中需要用到1.5m、1m、0.7m的钢轴 各一根。用于制造这些钢轴的原料是4m长的圆钢。现在要制造1000辆汽车，问最少需 要多少根圆钢。 解由于3种规格的钢轴长度之和为3.2m,一个自然的做法是在一根圆钢上截取 就可以完成该项任务。但是，这样做将会出现0.8m的料头。制造1000辆汽车将会出现 800m的料头，如果这些料头不能作其他用途，则相当于浪费了200根原材料。那么，有 没有什么办法能减少浪费呢？仔细阅读题目不难发现，需要的是1.5m、1m、0.7m的钢轴 各一根，并没有要求这些钢轴来自于同一根圆钢。也就是说，只要获得1.5m、1m、0.7m第 1 章 线性规划及单纯形法 9 法。 1.1.1 线性规划问题的提出 线性规划是指求解一组决策变量，该组决策变量在满足一些线性约束条件的基础上， 使得某个线性函数的值达到最大或最小。下面通过两个例子加以说明。  模型引入 1.1 (生产安排问题) 某工厂生产甲、乙两种产品，而生产这两种产品需要 用到原材料 A 和原材料 B。该厂可以利用的原材料 A 有 16kg，原材料 B 有 12kg。生产 一个单位甲产品需要消耗 2kg 原材料 A 和 4kg 原材料 B，生产一个单位乙产品需要消耗 3kg 原材料 A 和 1kg 原材料 B。经过测算，一个单位的甲产品可以获得 6 元的利润，一 个单位的乙产品可以获得 7 元的利润。问：该厂应如何安排生产才能获得最大利润？ 解 这个问题问的是如何安排生产才能获得最大利润。什么叫安排生产呢？在这个 简化的题目中，所谓安排生产当然指的是生产甲、乙两种产品各多少个单位。所以，这是 我们要回答的不知道的量。设生产甲、乙两种产品各为 x1 和 x2 个单位，于是按照题目 的假设，该厂此时可以获利 z = 6x1 + 7x2。生产不能是随意的，在这里，生产所耗费的原 料当然不能超过该厂的拥有量。于是，生产必须在如下约束下进行： 2x1 + 3x2 616 (原料 A 的限制) 4x1 + x2 612 (原料 B 的限制) 此外，x1, x2 是甲、乙产品的计划生产量，所以有 x1 > 0, x2 > 0。用 max 表示 maximize(即 最大)，用 subject to 或 such that 表示受约束 (其缩写为 s.t.)，于是可以将上面的分析表 示为： max z = 6x1 + 7x2 s.t.    2x1 + 3x2 6 16 4x1 + x2 6 12 x1, x2 > 0 (1-1-1) 这就是该问题的数学模型。它将原问题用数学的语言完全表达出来了。  模型引入 1.2 (最佳下料问题) 某汽车制造过程中需要用到 1.5m、1m、0.7m 的钢轴 各一根。用于制造这些钢轴的原料是 4m 长的圆钢。现在要制造 1000 辆汽车，问最少需 要多少根圆钢。 解 由于 3 种规格的钢轴长度之和为 3.2m，一个自然的做法是在一根圆钢上截取 就可以完成该项任务。但是，这样做将会出现 0.8m 的料头。制造 1000 辆汽车将会出现 800m 的料头，如果这些料头不能作其他用途，则相当于浪费了 200 根原材料。那么，有 没有什么办法能减少浪费呢？仔细阅读题目不难发现，需要的是 1.5m、1m、0.7m 的钢轴 各一根，并没有要求这些钢轴来自于同一根圆钢。也就是说，只要获得 1.5m、1m、0.7m