线性规划基本模型

线性规划的基本的内容和线性规划数学模型

定义：

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。

数学模型

(1)列出约束条件及目标函数 线性规划步骤

(2)画出约束条件所表示的可行域

(3)在可行域内求目标函数的最优解及最优值

解法求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。

对于一般线性规划问题： 图解法解线性规划问题

Min z=CX

S.T.

AX =b

X>=0

其中A为一个m*n矩阵。

若A行满秩

则可以找到基矩阵B，并寻找初始基解。

用N表示对应于B的非基矩阵。则规划问题1可化为：

规划问题2：

Min z=CB XB+CNXN

S.T. 线性规划法解题

B XB+N XN = b (1)

XB >= 0, XN >= 0 (2)

(1)两边同乘于B-1，得

XB + B-1 N XN = B-1 b

同时，由上式得XB = B-1 b - B-1 N XN，也代入目标函数，问题可以继续化为：

规划问题3：

Min z=CB B-1 b + ( CN - CB B-1 N ) XN

1 第一章 线性规划模型

一、 线性规划模型的建立

例1某工厂A有生产甲，乙二种产品的能力，且生产一吨甲产品需要3个工日和0.35吨小麦。生产一吨乙产品需要4个工日和0.25吨小麦。该厂仅有工人12人，一个月只能出300个工日，小麦一个月只能进21吨，并且还知生产一吨甲产品可盈利80（百元），生产一吨乙产品可盈利90（百元）。那么，工厂A在一月中应如何安排这两种产品的生产，使之获得最大的利润？

由以上条件可列表如下：

产品

资源 甲 乙 总和

工日 3 4 300

小麦 0.35 0.25 21

盈利 80 90

问题一的数学模型:

设1x,2x分别表示一月中生产甲，乙二种产品的数量，称之为决策变量。所得利润为z，问题一的目标是使得总利润函数219080xxz有最大值。

工日的约束为：3004321xx

原料小麦的约束为：2125035021x.x.

于是问题一可归结为求目标函数在约束条件下的最大值问题，显然目标函数和约束条件都是决策变量的线性函数，即可建立以下线性规划模型

02125035030043908021212121x,xx.x.xx.t.sxxzmax (1.1)

2 1.1 线性规划模型的一般形式

n,,jxm,,ib,xa.t.sxczminmaxjinjjijniii2102111 （m个约束） (1.2)

矩阵形式

0Xb,AX.t.sXczminmaxT (1.3)

其中Tnx,x,xX21为决策向量，Tncccc,,21为目标函数的系数向量，Tmb,b,bb21为常数向量，nmijaA为系数矩阵。

1.2 线性规划模型的标准形

赛区评阅编号（由赛区组委会填写）：

2016年高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参

赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网

上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或

资料（包括网上资料），必须按照规定的参考文献的表述方式列出，并在正文引用处予

以标注。在网上交流和下载他人的论文是严重违规违纪行为。

我们以中国大学生名誉和诚信郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞

赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展

示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号（从A/B/C/D中选择一项填写）：

我们的报名参赛队号（12位数字全国统一编号）：

参赛学校（完整的学校全称，不含院系名）：

参赛队员(打印并签名)：1.2.3.

指导教师或指导教师组负责人(打印并签名)：

（指导教师签名意味着对参赛队的行为和论文的真实性负责）日期：年月日

（请勿改动此页内容和格式。此承诺书打印签名后作为纸质论文的封面，注意电子版论

文中不得出现此页。以上内容请仔细核对，如填写错误，论文可能被取消评奖资格。）

1物资调运问题

摘要：随着社会不断发展，物资调运的重要性不断凸显。为此，本文引入某地区三家物

资生产厂与八个存储仓库的物资调运问题作为范例进行研究，以求解决类似的物资调运

问题。

首先，本文确定了物资生产厂与存储仓库的供求平衡关系，引入SNA-社会关系网络

的相关理论规划出成本最低的运输路线。然后，设定相关必要的约束条件，建立线性规

1、问题的提出

1.1基本情况

小米手机公司现生产m3、m2S、m2A，3种类型手机。已知生产单位产品的利润与所需的劳动力时间、设备台时及单位产品的资金投入，公司的资金拥有量和工作时间拥有量如表1-1所示：

表1-1

项目 配件种类 资源限制

m3 m2S m2A

资金（百元） 12 10 8 400

劳动力/工时 4 3 3 360

设备台时（小时） 3 2 3 210

产品利润(百元/件) 8 11 6

1.2提出问题

1、假设每种配件的市场都是供不应求，不用考虑市场及原材料的供应问题那么在现有的条件下应该如何分配者三种配件的生产才能获得最大利润。

2、模型的建立

2.1确定决策变量

因为获得最大利润的核心目标，要确定各种配件的生产数量从而去求得所能获得的最大利润。因此可以设321,,xxx来表示m3，m2S，m2A的产量。

2.2确定目标函数

该问题归结为求效益最大化的问题。这里所追求的利润S应是最大（简写为max）

Maxs=8X1+11X2+6X3

2.3确定约束条件

考虑到资金限制和劳动力总工时以及设备台时的要求，会有一定的约束条件用不等式表示参考表1-1数值有

12X1+10X2+8X3≤400

4X1+3X2+3X3≤360

3X1+2X2+3X3≤210

2.4建立模型

综合前述各步及变量非负的条件建立起线性规划模型如下。求变量)3,2,1(ixi使得目标函数：

Maxs=8X1+11X2+6X3

取得最大值，并满足如下的约束条件的要求：

s.t. 12X1+10X2+8X3≤400

4X1+3X2+3X3≤360

3X1+2X2+3X3≤210

3、模型的求解分析

上述线性规划模型是非标准的线性规划模型，用常规方法将其变为标准型的线性规划模型，然后利用单纯形法进行求解。

3.1模型转化

给约束条件加入松弛变量654,,xxx将模型变为标准型的线性规划模型如下：

Maxs=8X1+11X2+6X3