线性规划问题举例
　
　　作为上述线性规划问题的数学模型的应用，下面将对三个问题建立线性规划模
型．这些问题以及其他线性规划问题的更详细的讨论，在本书的第三部分给出．
　
运输问题
　
　　一个制造厂希望把若干单位的产品从几个仓库发送到若干个零售点．每个零售
点都需要一定数量的产品，而每个仓库也能供应一定数量的产品．这里作如下规定
：
　　 m=仓库的数目．
　　 n=零售点的数目．
　　 ai=第i个仓库能供应产品的总量．
　　 bj=第j个零售点所需产品的总量．
　　
　　 xij=从仓库i运到零售点j的产品数量．
　　这里xij是待定的未知量．如作...点击查看全部>> 出表格(当m=2，n=3)

　　则可以看出从仓库1运出产品的总量能用线性方程表示为
x11＋x12＋x13=a1． (2．1)
　　对于仓库2有
x21＋x22＋x23=a2． (2．2)
　　也要考虑三个零售点所需产品的总量，用下列方程表示：

　　制造厂知道从仓库i运到零售点j一个单位产品的费用为cij．我们还假定费用
关系是线性的，即运送xij单位的费用为cijxij．
　　制造厂希望确定，从每个仓库到每个零售点，要运送多少数量的产品，才能使
全部运输费用为极小．使费用为极小的目标，可通过极小化线性费用函数
c11x11＋c12x12＋c13x13＋c13x13＋c21x21＋c22x22＋c23x23
　　 (2．4)
　　来实现．因为一个非负的xij表示从仓库i到零售点j的运输量，所以我们要求
全部变量xij≥0．
　　把等式(2．1)至(2．3)，目标函数(2．4)和变量非负的条件联合起来，则m=2
，n=3的运输问题就可以表示成下列线性规划问题：

　　作为运输问题的一个数值例子，让我们考虑两个仓库三个零售点的问题，其中
可

　　把这个问题写成线性规划问题如下：

　　我们注意上述方程可代表一组会计上的帐目，它们记录了仓库与零售点之间货
物流通量．类似地，许多线性规划问题的方程只不过是会计步骤的数学表达．
　　下表给出一个平凡解

　　即x11=0，x12=5，x13=0，x21=8，x22=0，x28=2．相应的目标函数值是
2x12＋3x21＋x23=2·5＋3·8＋1·2=36．
　　第二组解(许多组解中的一组)是

　　其目标函数值为26．由第十章的方法可以证明，这个解是极小解．(对于此例
，读者应能验证，任何其他解所得到的运输费用都大于26．)
　
活动性分析问题
　
　　某公司掌握了几种数量固定的资源(如原材料，劳动力和设备)，合起来能生产
若干不同产品中的一种或这些产品的某种组合．已知公司每生产一个单位的j种产
品所需要的i种资源的数量，同时也已知每生产一个单位的j种产品所能获得利润的
数量．公司希望生产的产品组合能使其获得的总利润为最大．对此问题可以作如下
定义：
　　 m=资源的种类数．
　　 n=产品的种类数．
　　 aij=生产一个单位的j种产品所需i种资源的数量．
　　 bi=i种资源的最大可用量．
　　 cj=生产单位j种产品的利润数．
　　 xj=j种产品的活动水平(或产量)．
　　有时称aij为投入－产出系数或技术系数．
　　使用i种资源的总量可表示为线性函数
ai1x1＋ai2x2＋…＋ainxn．
　　因为上述使用i种资源的总量必须小于或等于i种资源的最大可用量，所以对i
种资源有下列线性不等式：
ai1x1＋ai2x2＋…＋ainxn≤bi．
　　由于负的xj没有实际意义，所以我们要求所有xj≥0．生产xj单位的j种产品所
获得的利润为cjxj．上述极大化利润函数问题的数学表达如下：

　　如第二章将讨论的那样，一个不等式可等价于非负变量的一个等式，所以上述
问题是一般线性规划问题的另一种提法．
　　为了说明上述模型，我们考虑在Gass[172]中所给出的例子．一个生产家具的
公司计划生产两种产品——椅子和桌子，其可用资源包括400板英尺①的红木板和450
个工时．已知生产每把椅子需用红木板5板英尺，10个工时，其利润为45美元，而
生产每张桌子需用红木板20板英尺和15个工时，其利润为80美元．问题是要确定，
在资源约束范围内，公司生产多少把椅子和多少张桌子，其总利润最大．生产一把
椅子需消耗5板英尺的木板和10个工时，而生产一张桌子需消耗20板英尺木板和15
个工时．令x1为椅子的生产量，x2为桌子的生产量．上述活动性分析问题，用线性
规划的形式可写成下述极大化利润函数的问题：

　　当然，对于上述约束条件，具有很多组可能的解．例如，仅生产椅子的解为x
>>收起