第一章 线性规划及单纯形法
1、 一般线性规划问题的数学模型
问题的提出
在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。任何资源，如劳动力、原材料、设备或资金等都是有限的。因此，必须进行合理的配置，寻求最佳的利用方式。
由此可以把有限资源的合理配置归纳为两类问题：一类是如何合理地使用有限的资源，使生产经营的效益达到最大；另一类是在生产或经营的任务确定的条件下如何合理地组织生产，安排经营活动，使所消耗的资源数最少。这是最常见的两类规划问题。
与规划问题有关的数学模型由两部分组成：一部分是约束条件，反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务，另一部分是目标函数，反映生产经营在有限资源条件下希望达到的生产或经营的目标。
例1 常山机器厂生产甲、乙两种产品。这两种产品都要分别在A、B、C三种不同设备上加工。按工艺材料规定，生产每件产品甲需占用各设备分别为2小时、4小时、0小时，生产每件产品乙需占用各设备分别为2小时、0小时、5小时。已知各设备计划期内用于生产这两种产品的能力分别为12小时、16小时、15小时，又知每生产一件甲产品企业能获得2元利润，每生产一件乙产品企业能获得3元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？
解：为更加直观理解题意，把上述问题转化为如下表格
A设备 B设备 C设备 利润
假定用x1和x2分别表示甲、乙两种产品在计划期内的产量。因设备A在计划期内的可用时间为12小时，不允许超过，于是有2x1+2x2≤12。对设备B、C也可列出类似的不等式：4x1≤16，5x2≤15。企业的目标实在各种设备能力允许的条件下，使总的利润收入z=2x1+3x2为最大。所以可归结为：约束于
甲产品 2 4 0 2 乙产品 2 0 5 3 资源限量 12 16 15 ?2x1?2x2?12?4x?16?1s.t.? ?5x2?15??x1,x2?0使 z=2x1+3x2?max
这是一个将生产安排问题抽象为在满足一组约束条件的限制下，寻求变量xl和x2的决策值，使目标函数达到最大值的数学规划问题。
钙 蛋白质 粗纤维 每千克成本（元） 骨粉 0.18 0.03 0.00 25.80 谷物 0.01 0.09 0.02 3.60 大豆粉 0.02 0.25 0.02 7.50 常写成如下数学表达式
max z=2x1+3x2
?2x1?2x2?12?4x?16?1s.t.? ?5x2?15??x1,x2?0
例2：某养鸡场每天需要的混合饲料的批量是100千克，这些饲料必须包含：
（1） 至少0.8%但不超过1.2%的钙； （2） 至少15%的蛋白质； （3） 最多5%的粗纤维
假定主要的配料包括骨粉、谷物和大豆粉，这些配料的营养成分及每千克成本汇总如下表，问如何配置可使总成本最小。
解：设x1,x2,x3是100千克混合饲料中所用的骨粉、谷物和大豆粉的含量，于是数学模型为：
minz?25.8x1?3.6x2x?7.5x3
?x1?x2?x3?100?0.18x?0.01x?0.02x?0.008?100123???0.18x1?0.01x2?0.02x3?0.012?100s.t. ?
0.03x?0.09x?0.25x?0.15?100123??0.02x2?0.02x3?0.05?100???x1,x2,x3?0
例3：某公司有一笔30万元的资金，考虑今后3年内用于下列项目的投资：
（1） 三年内每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一
年的投资。
（2） 只允许第一年年初投入，于第二年末收回，本利合计为投资额的150%，但此
类投资限额不超过15万元。
（3） 允许于第二年年初投入，于第三年末收回，本利合计为投资额的160%，但投
资限额20万元。
（4） 允许于第三年年初投入，年末收回，可获利40%，但投资限额10万元。 试为该公司确定一个使第三年末本利和为最大的投资组合方案。
【解】 为便于理解，投资方式见图
用xij表示第i年初投放到j项目的资金数 第一年年初 投资方式 x11+x12=30 第二年年初，可投资金额 1.2x11， 投资方式x21+x23，满足x21+x23=1.2x11 第三年年初，可投资金额 1.2x21+1.5x12， 投资方式x31+x34，满足x31+x34=1.2x21+1.5x12 第三年年底可回收资金 1.2 x31+1.4x34+1.6 x23 线性规划模型为
max z=1.2 x31+1.4x34+1.6 x23
?x11?x12?30??x21?x23?1.2x11?x31?x34?1.2x21?1.5x12? s.t. ?x12?15
?x?20?23?x34?10??xij?0
一般线性规划问题的数学模型
