线性规划模型：高职应用数学的关键章节

6.3.2.1 概述

线性规划是高等数学运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.

当你打算用数学建模方法来处理一个优化问题的时候，首先要确定优化的目标是什么，寻求的决策是什么，决策受到哪些条件的限制（如果有限制的话），然后用数学工具（变量、常数、函数等）表示它们.当然，在这个过程中要对实际问题作若干合理的简化假设.

6.3.2.2 线性规划模型简介

建模是解决线性规划问题极为重要的环节，一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际内容，要明确目标函数和约束条件，通过表格的形式把问题中的已知条件和各种数据进行整理分析，从而找出约束条件和目标函数.

从实际问题中建立数学模型一般有以下三个步骤；

（1）根据影响所要达到目的的因素找到决策变量，用X表示决策变量；

（2）由决策变量和所在达到目的之间的函数关系确定目标函数，f（x）表示目标函数；

（3）由决策变量所受的限制条件确定决策变量所要满足的约束条件，实际问题一般对决策变量X的取值范围有限制.

决策变量、约束条件、目标函数是线性规划的三要素.实际中的优化问题通常有多个决策变量，n维向量X=（x1，x2，x3，…，xn）表示，目标函数f（x）是多元函数，可行域Ω比较复杂，常用一组不等式（也可以由等式）gi（x）≤0（i=1，2，3，…，m）来界定.称为约束条件.一般地，这类模型可表示述成下形式

minz=f(x),

s.t.gi(x)≤0(i=1,2,3,…,m).

注意 线性规划模型的特征如下：

比例性：每个决策变量对目标函数的“贡献”，与该决策变量的取值成正比.

可加性：各个决策变量对目标函数的“贡献”，与其他决策变量的取值无关.

连续性：连续性每个决策变量的取值是连续的.

案例1 奶制品的生产与销售

一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在甲类设备上用12h加工成3kgA1，或者在乙类设备上用8h加工成4kgA2，根据市场需求，生产的A1，A2全部能售出，且每千克A1获利24元，每千克A2获利16元，现在加工厂每天能得到50桶牛奶的供应，每天工人总劳动时间为480h，并且甲类设备每天至多能加工100kgA1，乙类设备的加工能力没有限制，试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：

若用35元可以买到1桶牛奶，应否做这项投资？若投资，每天最多购买多少桶牛奶？

若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？

由于市场需求变化，每千克A1的获利增加到30元，应否改变生产计划？

6.3.2.3 模型假设

1.A1，A2两种奶制品每千克的获利是与它们各自产量无关的常数，每桶牛奶加工出A1，A2的数量和所需的时间是与它们各自的产量无关的常数.

2.A1，A2每千克的获利是与它们相互间产量无关的常数，每桶牛奶加工出A1，A2的数量和所需的时间是与它们相互间产量无关的常数.

3.加工A1，A2的牛奶的桶数可以是任意实数.

决策变量 设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2.

目标函数 设每天获利为z元，x1桶牛奶可生产3x1千克A1，获利24×3x1，x2桶牛奶可生产4x2kgA2，获利16×4x2，故

z=72x1+64x2.

约束条件

原料供应生产A1，A2的原料（牛奶）总量不得超过每天的供应，即x1+x2≤50.

劳动时间生产A1，A2的总加工时间不得超过每天正式工人总的劳动时间，即12x1+8x2≤480.

设备能力A1的产量不得超过甲类设备每天的加工能力，即3x1≤100.

非负约束x1，

x2均不能为负值，即x1≥0，

x2≥0.

综上可得

maxz=72x1+64x2,

s.t.x1+x2≤50,

12x1+8x2≤480,

3x1≤100,

x1≥0,x2≥0.

求解以上线性规划问题，在LINGO下新建一个模型文件，直接输入：

将文件存储并命名后，选择菜单“LINGO|Solve”执行，即可得到如下输出：

结果分析

上面结果的前3行告诉我们，LINGO求出了模型的全局最优解，最优值为3360（即最大利润为3360元），迭代次数为2次.接下来的3行告诉我们，这个线性规划的最优解为x1=20，x2=30（即用20桶牛奶生产A1，30桶牛奶生产A2）.

“LP OPTIMUM FOUND AT STEP2”表示单纯形法在两次迭代（旋转）后得到最优解.

“OBJECTIVE FUNCTION VALUE 1 3 360.000”表示最优目标值为3360.000（LINDO中将目标函数自动看作第1行，从第二行开始才是真正的约束条件）.

“VALUE”给出最优解中各变量（VARIABLE）的值：

“REDUCED COST”的含义是（对MAX型问题）：基变量的REDUCED COST值为0，对于非基变量，相应的REDUCED COST值表示当非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量.本例中两个变量都是基变量.

“SLACKOR SURPLUS”给出松弛（或剩余）变量的值，表示约束是否取等式约束；第2、第3行松弛变量均为0，说明对于最优解而言，两个约束均取等式约束；第4行松弛变量为40.000000，说明对于最优解而言，这个约束取不等式约束.

“DUAL PRICES”给出约束的影子价格（也称为对偶价格）的值：第2、第3、第4行（约束）对应的影子价格分别48.000000，2.000000，0.000000.即牛奶的影子价格为48.000000，工人的影子价格为2.000000，若用35元购买牛奶，35≤48，则值得投资，付给工人的工资最多为2.(www.xing528.com)

敏感性分析：选择“LINGO|Options”菜单，在弹出的选项卡中选择“Generai Solver”，然后找到选项“Duai computations”在下拉框中选中“Prices&Ranges”，应用或保存设置.重新运行”LINGO|Solve“，然后选择“LINGO|Ranges”菜单，得到如下输出：

“GURRENT COEF”（敏感性分析）的“ALLOWABLE INCREASE”（允许的增加量）和“ALLOWABLE DECREASE”（允许的减少量）给出了最优解不变条件下目标函数系数的允许变化范围：

x1的系数为（72-8，72+24）即（64，96）.并且，x1系数的允许范围需要x2的系数保持64不变.A1获利增加到30元，则30×3=90∈（64，96），则不改变生产计划.

x2的系数为（64-16，64+8）即（48，72）.同理，x2系数的允许范围需要x1的系数保持72不变.

“CURRENT RHS”则是对“影子价格”的进一步约束.

牛奶的需求量满足（50-6，50+10）即（44，60）.并且，牛奶的允许范围需要劳动时间保持480h不变.

6.3.2.4 自来水输送问题

某市有甲，乙，丙，丁四个居民区，自来水有A，B，C三个水库供应.四个区每天必须得到保证的基本生活用水量分别是30，70，10，10kt，但由于水源紧张，三个水库每天最多只能分别供应50，60，50kt自来水.由于地理位置的差别，自来水公司从各水库向各区送水所需付出的引水管理费不同（表6-15），其中C水库与丁区之间没有输水管道），其他管理费用都是450元/kt.根据公司规定，各区用户按照统一标准900元/kt收费.此外，四个区都向公司申请了额外用水量，分别为每天50，70，20，40kt.该公司应如何分配供水量，才能获利最多？

表6-15 从水库向各区送水的引水管理费

问题分析 分配供水量就是安排从三个水库向四个区送水的方案，目标是获利最多.而从题目给出的数据看，A，B，C三个水库的供水量160kt，不超过四个区的基本生活用水量与额外用水量之和300kt，因而总能全部卖出并获利，于是自来水公司每天的总收入是900×（50+60+50）=144000元，与送水方案无关.同样，公司每天的其他管理费用450×（50+60+50）=72000元也与送水方案无关.故只需使引水管理费最小即可.此外，送水方案自然要受三个水库的供应量和四个区的需求量的限制.

决策变量为A，B，C三个水库（i=1，2，3）分别向甲，乙，丙，丁四个区（j=1，2，3，4）的供水量.设水库i向j区的日供水量为xij.由于C水库与丁区之间没有输水管道，即x34=0，因此只有11个决策变量.

目标函数 引水管理费最少，即

MinZ=160x11+130x12+220x13+170x14+140x21+130x22+190x23+150x24+190x31+200x32+230x33.

约束条件

由于供水量总能卖出并获利，水库的供应量限制可以表示为

x11+x12+x13+x14=50,

x21+x22+x23+x24=60,

x31+x32+x33=50.

考虑到各区的基本生活用水量与额外用水量，需求量限制可以表示为

30≤x11+x21+x31≤80,

70≤x12+x22+x32≤140,

10≤x13+x23+x33≤30,

10≤x14+x24≤50.

求解以上线性规划问题，在LINGO下新建一个模型文件，直接输入：

运行程序后，得结果如下图（图6-9）

图6-9 运行结果

综上，送水方案为：A水库向乙区供水50kt，B水库向乙、丁区分别供水50，10 kt，C水库向甲、丙分别供水40，10kt.引水管理费为24400元，利润为144000-72000-24400=47600元.

课后提升

1.现某物流公司准备运输7种规格的包装箱，需要装到两辆车上，包装箱的宽和高是一样的，但厚度tcm和质量wkg是不同的.见表6-16，给出了每种包装箱的厚度、质量以及数量.每辆车有10.2m的地方可以用来包装箱，载重为40t.由于地区货运限制，对C5，C6，C7类包装箱的总数有一个特别的限制：这三类包装箱所占的空间（厚度）不能超过302.7cm.

问题要求：设计一种方案，使得剩余空间最小.

表6-16 包装类型箱厚度

2.某驾货机有三个货舱：前舱、中舱、后舱，三个货舱所能装载的货物的最大质量和体积都有限制，见表6-17.并且为了保持飞机的平衡，三个货舱中实际装载货物的质量必须与其最大容许质量成比例.

表6-17 机舱容积质量

现有四类货物供该货机本次飞行装运，其有关信息见表6-18，最后一列指装运后所获得的利润.

表6-18 货物质量体积利润

应该如何安排装运，使该货机本次飞行获利最大？

3.某公司饲养实验用的动物以出售给动物研究所，已知这些动物的生长对饲料中3种营养成分（蛋白质、矿物质和维生素）特别敏感，每个动物每周至少需要蛋白质60g，矿物质3g，维生素8mg，该公司买到5种不同的饲料，每种饲料1kg所含各种营养成分和成本见表6-19，如果每个小动物每周食用饲料不超过52kg，才能满足动物生长需要.

表6-19 营养需求

问题：（1）求使得总成本最低的饲料配方？

（2）如果另一个动物研究对蛋白质的营养要求变为59g，但是要求动物的价格比现在的价格要便宜0.3元，问该养殖所值不值得接受？

（3）由于市场因素的影响，A2的价格为0.6元/kg，问是否要改变饲料配方？

答案

1.第一辆车剩余空间0.1cm，第二辆车剩余空间0.5cm.

2.飞行获利最大为121515.8元.

3.略.