§2线性规划问题及其数学模型 线性规划作为运筹学的一人重要分支，是研究较早，理论较完善，应用最广泛的一门科学。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低限度和成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有条件下进行组织和安排，以完成更多的工作。因此，线性规划就是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。

Presentation on theme: "§2线性规划问题及其数学模型 线性规划作为运筹学的一人重要分支，是研究较早，理论较完善，应用最广泛的一门科学。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低限度和成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有条件下进行组织和安排，以完成更多的工作。因此，线性规划就是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。"— Presentation transcript:

1 §2线性规划问题及其数学模型 线性规划作为运筹学的一人重要分支，是研究较早，理论较完善，应用最广泛的一门科学。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低限度和成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有条件下进行组织和安排，以完成更多的工作。因此，线性规划就是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。 一、运输问题 例1　设有A1，A2两个香蕉基地，产量分别为60吨和80吨，联合供应B1，B2，B3三个销地的销售量经预测分别为50吨、50吨和40吨。两个产地到三个销地的单位运价如下表所示： 　　　　表13――1运价表（单位：元/吨）　　 B1 B2 B3 A1 600 300 400 A2 700 销地 单位动价 产地

2 问每个产地向每个销地各发货多少，才能使总的运费最少？
解（1）在该问题中，所要确定的量是各产地运往各销地的香蕉数量，即决策变量是运输量。设Xij(i=1,2; j =1,2,3)分别表示由产地Ai运往销地Bi的数量。 （2）在解决问题的过程中，要受到如下条件限制，即约束条件： ①各产地运出的数量应等于其产量，即 …………….. ②各销地运进的数量应等于其当地预测的销售量，即 ………………. ③从各产地运往各销地的数量不能为负值，即 (3) 该问题的目的是运价最低，所以运价是目标函数，即 因此，该问题的数学模型为： 上一页 8 下一页

3 结束条件　　 例1的一般形式是：设某种物资有m个产地 产量分别为 有n个销地 ,销量分别为 如果由产地 运往销地 的单位运价为 （元/吨），在产销平衡的情况下，应如何调运才能使运费最省？ 解… 设 表示由产地 运往销地 的数是(i=1,……，m；j=1,2,……，n) 则该问题数学模型为： 求变量 的一组值，使它们满足 并使目标函数 的值最小。

4 二、生产组织与计划问题 例2 设某用 种原料，生产 种产品，其中 种产品每单位需要原粉分别为 ；而该厂现有原料 ；的数量分别为 各种产品每单位可是利润分别为 。在该厂产品全部能销售情况下，应如何组织生产，才能使该企业获得最大？ 解 设生产产 中数量为 ，则此问题的数学模型为： 求一组变量 的值，使满足 ………….. 结束条件 并使目标函数 的值最大。 三、配料问题 例 设有 种原料，配制含有几种成分 的产品，要求产品中各种成分的含量不低于 ；不高于 ； 种成分在 种原料中的单位含量为，

5 四﹑线性规划问题数学模型的一般形式和标准形式
各种原料的单位价格依次为 问如何调配原料，才能使产品符合要求，又使成本最低？ 解 设 表示每单位产品中原料 的使用量(即决策变量)， 则 数学模型为：求一组变量的值，使其满足 …….. 约束条件 并使目标函数 最小。 四﹑线性规划问题数学模型的一般形式和标准形式 上面我们建立了经济领域中常见的实际问题的数学模型，尽管这些实际问题本身是多种多样的，但是它们的数学模型却具有相同的特征：要确定某些变量(决策变量)的一组值，使得在确定的确定的约束条件下，目标函数是取得最大值或最小值。其中，约束条件是决策变量的线性方程或线性不等式。目标函数是决策变量的线性函数。因此，我们把这种规划问题称为线性规划问题。同时，我们可以得到对于一个线性规划问题，其数学模型应具有如下形式：

6 求 我们称这种形式的线性规划模型为一般形式。其中， 为目标函数系数约束方程系数； 为约束方程常数项；(i=1,……,m;j=1,……,n). 由此可见，一个线性规划问题问题的数学模型，必须含有三个要素：决策变量、约束条件和目标函数。 由上面的例子可知，线性规划问题的数学模型的一般形式很多。目标函数有求最大值和最小值；约束条件有“≤”，“≤”，“＝”三种情况。这种多样性给问题的讨论带来很大的不便。为此，我们介绍线性规划问题的一种统一形式—标准形式。规定线性规划问题的数学模型的标准形式为：

7 S.t 线性规划问题的标准（13.1）也可写成矩阵形式 s.t 其中 ， X＝ A＝ B＝ ， ，

8 对于线性规划问题的一般形式，可以按如下方法化成标准形：
（1）如果线性规划问题是求目标函数的最大值，即求 ，只要令 ，即可化为求目标函数的最小值，即求 （2）如果某个约束条件为线性不等式，则可将其化为线性议程式的形式。 设第k个约束条件为： 则加入一个新变量，将其约束条件改为： 这个所加的变量称为松弛变量。 令 若第 个约束条件为： 则加入一个新变量，将上述约束条件变为： （3）若对某变量没有非负限制，则引进两个非负变量 　　令 代入约束条件和目标函数，可化为全部变量都有非负限制。 例4 将下列线性规划模型化为标准形

9 解 引入松驰变量 ，令 且　 　 即可得标准形式如下　　　　 S.t