第一章 线性规划与单纯形法11

第一章 线性规划与单纯形法

经营管理中如何有效地利用现有人力、物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力、物力去实现目标。这类统筹规划的问题用数学语言表达，先根据问题要达到的目标选取适当的变量，问题的目标通过变量的函数形式表示（成为目标函数），对问题的限制条件用有关变量的等式或不等式表达（成为约束条件）。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。有关线性规划问题的建模，求解和应用的研究构成了运筹学中的线性规划分支。用线性规划求解的典型问题有运输问题、生产计划问题、下料问题、混合配料问题等。有些线性规划问题的目标函数是非线性的，但往往可以采用分段线性化邓手法，转化为线性规划问题。

第一节 线性规划问题及其数学模型

一、问题的提出及数学模型

例一：美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时，调试时间，调试工序每天可用于这两种家电的能力。各售出一件的获利情况，如表1－1所示。问该公司应制造两种家电各多少件，使获得的利润为最大。

表1－1

Ⅰ Ⅱ 每天可用能力 设备A（h） 设备B（h） 调试工序(h) 利润（元） 0 6 1 2 5 2 1 1 15 24 5 设该公司应制造Ⅰ家电x1件，Ⅱ家电x2件，该公司每天可获得的利润为（z?2x1?x2）元，因问题中要求获得的利润为最大，即maxz。又z是该公司能获得的利润的目标函值，它是变量x1、x2的函数，成为目标函数。x1、x2的取值受到设备A、B和调试工序的限制，用于描述限制条件的数学表达式成为约束条件。数学模型为：

目标函数maxz?2x1?x2 约束条件（S.T.）

表示家电的制造件数受设备A的能力限制?5x2?15?设备B的能力限制?6x1?2x2?24表示家电的制造件数受?表示家电的制造件数受调试工序的能力限制?x1?x2?5?x　、x?0成为变量的非负约束。表明家电的制造件数不可能为负 2?1例2：捷运公司拟在下一年度的1－4月份的4个月需租用仓库堆放物资。已知各月份所需仓库面积数列于表1－2。仓库租用费随合同期而定，期限越长，折扣越大。具体数字见表1－3。租界仓库的合同每月初都可办理，每份合同的具体规定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租界合同。每次办理时可签一份，也可签若干份租用面积和租界期限不同的合同，试确定该公司签订的租界合同的最优决策，目的是所付租界费用最小。

表1－2

月份 1 2 10 3 20 4 12 所需仓库面积15 （100m） 表1－3 合同租界期限 1个月 22个月 4500 3个月 6000 4个月 7300 2合同期内的租金（元/100m） 2800 解：若用变量xij表示捷运公司在第i(i?1,2,3,4)个月初签定的租借期为

j(j?1,2,3,4)个月的仓库面积的合同（单位为100m2）。因5月份起该公司不需

要租界仓库，故x24x33x34x42x43x44均为零。该公司希望总的租界费用为最

小，故有如下的数学模型：

minz?2800(x11?x21?x31?x41)?4500(x12?x22?x32)?目标函数：

6000(x13?x23)?7300x14

?x11?x12?x13?x14?15??x12?x13?14＋21＋22＋23?10??x13?x14?x22?x23?x31?x32?20?x?x?x?x?12233241?14?x?0(i?1~4,j?1~4)约束条件?ij

这个模型中的约束条件分别表示当月初签订的租界合同的面积数加上该月前签订的未到期的合同的租界面积数总和，应不少于该月所需的仓库面积数。

例3：某公司经营某种产品，该产品由3个生产点A1,A2,A3生产，日产量为

A1?60ton,A2?40ton,A3?60ton，分别销往4个销售点B1,B2,B3,B4,各销地的日销售量分别为：B1?30ton,B2?50ton,B3?40ton,B4?40ton。已知每吨产品从各产点到各销售地 的运价如表1－3所示，问如何调运，保证产销平衡且总运费最小？

表1－3 （单位：百元/吨） B1 5 4 4 30 A1 6 1 2 50 B3 10 9 3 40 B4 3 7 8 40 产量 60ton 40ton 60ton 160ton A1 A2 A3 销量 解：这是一个产销平衡的运输问题，即各产地的产量之和等于各销地的销量的总量。设xij表示从生产点Ai到销售点Bj的调运量(i?1,2,3;j?1,2,3,4)。数学模型为：

目标函数为：

minz?5x11?6x12?10x13?3x14?4x21?x22?9x23?7x24?4x31?2x32?3x33?8x34?x11?x12?x13?x14?60?x?x?x?x?40222324?21?x31?x32?x33?x34?60??x11?x21?x31?30S.T.??x12?x22?x32?50?x13?x23?x33?40??x14?x24?x34?40?x?0(i?1,2,3;j?1,2,3,4)?ij

下面从数学的角度来归纳上述三个例子的共同点：

（1）、每一个问题都有一组变量—称为决策变量，一般记为x1,x2,?,xn。对决策变量的每一组值：

(0)(0)T(x1(0),x2,?,xn)代表了一种决策方案。通常要求

决策变量取值非负，即xj(j?1,2,?,n)。

（2）、每一个问题中都有决策变量需要满足的一组约束条件—线性的等式或不等式。

（3）、都有一个关于决策变量的线性函数—称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。

将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划问题（linear programming）有时简称为LP问题。

一般数学模型为

max(min)z?c1x1?c2x2??cnxn

?a11x1?a12x2??a1nxn?(或?，＝)b1??a21x1?a22x2??a2nxn?(或?，＝)b2?????ax?ax??ax?(或?，＝)bm22mnnn?m11?x,x,?xn?0s.t.?12(1)(2)（m）(m?1)

其中x1,x2,?xn为变量（决策变量）

max(min)z?c1x1?c2x2??cnxn是目标函数，或实现最大化，或实现最小化。s.t.是subject to的英文缩写，它表示“以?为条件”，“假定”，“满足”之意。（1）—（m）称为约束条件，称为约束条件，它可以?或?的不等式，也可以是严格的等式。(m+1)称为非负约束条件。