运筹学ABC-2线性规划建模课

线性规划在经济管理中的应用——线性规划建模应用1：生产计划问题问题1试列出下述产品规划问题的线性规划模型：某工厂生产A、B、C三种产品，每吨利润分别为2000元、3000元、1000元；生产单位产品所需的工时及原材料如表所示。若供应的原材料每天不超过3吨，所能利用的劳动力日总工时是固定的，问如何制定日生产计划，使三种产品总利润最大？生产每吨产品所需资源产品ABC劳动力所需工时占总工时比例1/31/31/3所需原材料（吨）1/34/37/3解：第一步——确定决策变量为产品A的日产量为产品B的日产量为产品C的日产量第二步——明确约束条件劳动力的约束条件为：原材料的约束条件为：第三步——明确目标总利润为：此产品规划问题的线性规划模型为：问题2

某工厂在计划期内要安排生产I、II两种产品。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问I、II两种产品的产量各为多少时，使该工厂获取最大利润？产品I产品II

设备128台时原材料A4016kg原材料B0412kg约束条件

x1＋2x2≤84x1≤164x2≤12x1，x2≥0该生产计划问题可用数学模型表示为：目标函数

maxz＝2x1＋3x2问题3某制造企业有A、B、C、D四种主要产品，所有产品均需四道工序生产：第一阶段是冲压，第二阶段是成型，第三阶段是装配，第四阶段是喷漆。根据工艺要求及成本核算，单位产品所需的加工时间、利润以及可供使用的总工时如下表所示。这四种产品每天要各生产多少件才能使获得的利润最大？请就这一问题，以利润最大为目标，建立求解的线性规划模型。工序每件产品加工时间每天加工能力（分钟）ABCD冲压1111480成型48252400装配42552000喷漆64843000单位利润（元）96118解答：

maxZ=9x1+6x2+11x3+8x4

约束条件：

x1+x2+x3+x4≤4804x1+8x2+2x3+5x4≤24004x1+2x2+5x3+5x4≤20006x1+4x2+8x3+4x4≤3000x1≥0，x2≥0，x3≥0，x4≥0应用2：配料问题

某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：

假设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，才能使新产品的原材料成本最小。问题

1解：设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4公斤，根据条件，可建立相应的线性规划模型如下：

这是一个典型的成本最小化的问题。这个线性规划问题的最优解是：

x1=26.58，x2=31.57，x3=41.84，x4=0（公斤）最低成本为： z=9549.87（元）

min

z=

115x1

+97x2

+82x3

+76x4

s.t.

0.0321x1

+0.0453x2+0.0219x3

+0.0176x4

≥3.20

0.0204x1

+0.0112x2

+0.0357x3

+0.0433x4

≥2.10

0.0582x1

+0.0306x2

+0.0427x3

+0.0273x4

≥4.30

x1

+x2

+x3

+x4

=100

x1,

x2,

x3,

x4

≥0

问题2某养猪场的猪每天至少需要700g蛋白质，30g矿物质，100mg维生素。现有五种饲料可选，每种饲料每kg营养成分含量及单价如表所示。要求确定既满足动物生长应用需要，又使费用最省的选用饲料方案。饲料蛋白质（g）矿物质（g）维生素（mg）价格（元/kg）1234532161810.50.220.50.51.00.220.80.20.70.40.30.8设xi为第i种饲料的数量（公斤），则Minz=0.2x1+0.7x2+0.4x3+0.3x4+0.8x5St.3x1+2x2+1X3+6X4+18X5>=7001x1+0.5x2+0.2X3+2X4+0.5X5>=300.5x1+1x2+0.2X3+2X4+0.8X5>=100应用3：背包及配送问题

一个物料箱最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：

问：要在物料箱中装入这三种物品各多少件，使箱中的物品价值最高？问题1：物料装箱

这个问题的最优解是：x1=1(件),x2=0(件),x3=2(件),最高价值为：z=87（元）解：设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此物料箱问题的线性规划模型是一个整数规划问题：Maxz=17x1+41x2+35x3

s.t10x1+41x2+20x3<=50

xi≥0(i=1,2,3)且为整数问题2

设某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运价如下表所示。

问如何安排运输计划，从而使总运费最小？

设xij为从供应地Ai运往需求地Bj的物资数量（i=1,2；j=1,2,3），z为总运费，则总运费最小的线性规划模型为：xij≥0

以上约束条件（1）、（2）称为供应地约束，（3）、（4）、（5）称为需求地约束。这个问题的最优解为：x11=0， x12=30，x13=5（吨）；x21=10, x22=0, x23=15（吨）

最小运费为：z=275元。应用4：优化下料问题问题1线材优化

现要做100套钢架，每套用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。

方案下料数长度IIIIIIIVV2.92.11.510321221213合计料头7.407.30.17.20.27.10.36.60.8

为了得到100套钢架，需要混合使用各种下料方案。设第i种方案下料的原材料根数为xi

，（i＝1，2，3，4，5）得数学模型为：

minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5

x1+2x2+x4

＝100x2+2x3+2x4+x5＝1003x1+x2+2x3+3x5＝100

xi≥0(i=1,2,3,4,5)且为整数问题2板材优化

要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：规格类型第一种钢板第二种钢板A规格B规格C规格212131

今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。解：设需截第一种钢板x张，第一种钢板y张，则2x+y≥15,x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*目标函数为

minz=x+y应用5：值班调度问题问题1

某个中型的百货商场对售货人员的需求经过统计分析如下表所示，为了保证销售人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既能满足工作需要，又使配备的售货人员的人数最少？问题2某医院护士值班班次、每班工作时间及各班所需护士数如下表所示。每班护士值班开始时向病房报到，试决定：若护士上班后连续工作8h，该医院最少需多少名护士，以满足轮班需要？解：在本例中，每一时段上班的工作人员，既包括本时段开始上班的人，又包括上一个时段开始上班的人。因此，设xi为第i个时段开始上班的人员数，得到数学模型为：Minz=x1+x2+x3+x4+x5+x6x6+x1>=60X1+x2>=70X2+x3>=60

x3+x4>=50X4+x5>=20X5+x6>=30Xj>=0,j=1,2,…6应用6：投资组合问题问题1宏银公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年—100万，2004年—150万，2005年—120万，2006年—110万元。以上贷款资金均需于2002年底前筹集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目（1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元；（2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，且限购90万元；（3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元；（4）于每年初将任意数额的资金存放于银行，年息4%，于每年底取出。问宏银公司应如何运用好这笔筹集到的资金，使2002年底需筹集到的资金数额最少？解：设x为2002年底宏银公司需筹集到的资金额，y1，y2，