大学论文：线性规划问题

线性规划 毕业论文

聊 城 大 学

LIAOCHENG UNIVERSITY

线性规划问题在实际生活中的应用

线性规划 毕业论文

线性规划(LP)问题的求解

摘要：生活中的很多问题涉及线性规划问题，如组合投资、运输问题、生产组织问题等。本文中通过将线性规划问题的数学模型的一般形式转变为标准形式，从而应用单纯形法求解。但单纯形法的运算量较大，应用excel、matlab等软件求解既快又准。 关键词：线性规划、单纯形法、matlab\excel求解

Linear programming (LP) problems’ solving

Abstract:Many problems refer to the linear programming problems in our life,such as portfolio investment、transportation problem、organization of production problems,and so on. In this paper through transforming the general form of the mathematical model of linear programming problem into standard forms to use the application of the simplex method to solve LP problems. But the simplex method needs larger computation,so we can use the software of excel and matlab which are fast and accurate to solve the problems.

Keywords: Linear programming、Simplex method、Matlab \ excel to solve

1.线性规划问题的在实际应用中的作用

资源是有限的，如何通过分配有限的资源获得人们所期望的效果；在工农业生产、交通运输、资本增值等各项经济活动中，如何提高经济效益，做到耗费较少的人力物力财力，创造出较多的经济价值；

线性规划 毕业论文

这些问题涉及分配，而线性规划为最优分配提供了工具。

线性规划研究的问题主要有两类：一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们，使得完成任务最多。常见的线性规划问题如：运输问题，生产的组织与计划问题，合力下料问题，配料问题、布局问题、分派问题等。 2.线性规划问题对应的数学模型

对于给定的实际问题，首先是要建立线性规划问题的数学模型，其次是求问题的最优解.

线性规划问题数学模型的一般形式，是求一组变量x1,x2, ,xn，使其满足：

a11x1 a12x2 a1nxn b1 或 b1，或 b1

a21x1 a22x2 a2nxn b2 或 b2，或 b2

约束条件

ax ax ax b 或 b，或 b m22mnnmmm m11

xj 0(j 1,2, ,n)

并使目标函数s c1x1 c2x2 cnxn达到最小（或最大）。其中使目标函数取最小值的可行解就称为最优解。

通过引入松弛变量xn k,xn r，及maxs mins'(s' s),将一般形式转变为标准形式：

mins c1x1 c2x2 cnxn

a11x1 a12x2 a1nxn b1

a21x1 a22x2 a2nxn b2

约束条件

ax ax ax b

m22mnnm

m11

x 0(j 1,2, ,n) j

线性规划 毕业论文

考虑约束条件中的非齐次线性方程组，设A为系数矩阵，B为增广矩阵。

线性方程组的解（即可行解）一般有三种情况：无解、唯一解、无穷解。对于上面的非其次线性方程组，当 m<n时，若有解，一定有无穷解；下面考虑无解的情况，如何判断呢，线性代数中的方法是将原方程组经过初等变换后得到阶梯形方程组，通过判断阶梯形方程组中是否出现“0=d（d 0）”，若出现，则原方程组无解；否则，有解。当m≥n时，若有解，如果rank(B)=n，则有唯一解；如果rank(B)<n，则有无穷解；无解时的判断与m<n时相同。

同时，对于LP问题可能有几种结局：有唯一的最优解、有无穷多个最优解、无界解、无解。其中无解的情况即LP问题的约束条件对应的线性方程组无解。

特别的对于二元LP问题，也可以应用图解法，在二维直角坐标平面上作图表示线性规划问题的有关概念，判断有无解，并求解。 3.单纯性法

单纯形法的理论基础：

定理一 若LP问题可行域存在，则可行域是个凸集。 定理二 LP问题的基可行解与可行域的顶点一一对应。

定理三 若LP问题存在最优解，则一定存在一个基可行解是最优解。

若LP问题的最优解存在，则它一定可在其可行域R的一个极点处达到，所以单纯形法的基本思想就是从一个初始极点出发，按照一种简单的规则，自动实现从一个极点转移到另一个极点，同时使目标函

线性规划 毕业论文

数值减少（或增大），若现行解（极点）为最优解，则计算结束；否则继续这种极点之间的转移。 下面举例说明如何构造单纯形表 例1 设有线性规划问题

mins x1 2x2 x3 2x1 x2 x3 4

x 2x 6 12

x 0(i 1,2,3) i

试选择一个基，并构造单纯形表。 解 先将线性规划问题标准化，得

mins x1 2x2 x3 0x4 2x1 x2 x3 x4 4

x1 2x2 0x3 0x4 6 x 0(i 1,2,3,4) i

2 11 1 4

b x x,x,x,x本例中，A ,,,c 1,2,1,01234。构 6 1200

造单纯形表实际上是要计算cBB 1b,cBB 1A c,B 1b和B 1A。 (1). 确定基B P1,P3 或B P2,P4

21 2 1 B P,P （当然也可以选取12 12

10

1 1

等等。事实上，只要选择系数矩阵A的m 2个线

20

性无关的列向量组成B，使B为非奇异矩阵即可）。并由此得到

01

B x x,xx x,xcB c1,c3 1,1 ，cN c2,c4 2,0 。，， 13N24， B

1 2

1

(2).计算目标值b00 s cBB 1b 1,1 (3). 计算检验数

01 4

22

1 2 6

线性规划 毕业论文

b01,b02, ,b0n cBB 1A c

01 2 110

1,1 1,2,1,0

1 2 1200

0, 5,0, 1

(4). 计算基础解xB B 1b

1

01 4 6

1 2 6 16

01 2 11 1 1200

(5). 计算矩阵BA 1200 0 51 1 1 2

(6). 合成单纯形表如下表

由此来看，构造单纯形表并不困难，只是计算量较大、较麻烦。需要说明的是，在第一行和第一列分别标明各变量的目的是为今后的换基迭代做准备。

选择一个基，并构造单纯形表。 单纯形方法的求解过程

(1).将一般形式华为标准形式； (2).建立初始单纯性表

(3).计算检验数，判断线性解是否为最优解； (4).确定进基向量； (5).确定主元素和离基向量；

(6).以主元素进行换基计算，求得一个新的基本可行解，然后返回第三步。

线性规划 毕业论文

例2.某厂生产A,B两种产品，生产A产品1kg,需煤9t，电力4000kWh，劳动量4人日，生产B产品1kg，需用煤5t，电力5000kWh,劳动量10人日。现该厂有煤350t，电力20万kWh,劳动量300人日，A产品每kg可获利润1000元，B产品每kg可获利润1500元，问应如何安排生产才能使该厂所获利润最大？ 解 （1）建立数学模型

设该厂生产A产品x1kg,B产品x2kg，所获利润为w元，则可建立如下的LP模型：

maxw 1000x1 1500x2

s.t.9x1 5x2 350 4 4000x1 5000x2 20 10

4x1 10x2 300 x,x 0 12

（2）用单纯性法求解问题

引入松弛变量x3,x4,x5，将上式化简后化为标准形式：

minz (1000x1 1500x2)

9x1 5x2 x3 350 4x 5x x 200 124

2x1 5x2 x5 150

xi 0(i 1,2,3,4,5)

a4 0 1 0 0

a5 ↑ 0 0 1 0

b 350 200 150 0

用单纯性法求解问题的计算过程如下表：

基向量 a3 a4 ←a5 rj

a1 9 4 2 -1000

a2 5 5 ⑤ -1500

a3 1 0 0 0

a3 ←a4

7↓ ②

0 0

1 0

0↑ 1

-1 -1

200 50

线性规划 毕业论文

a2 rj

0.4 -400

1 0

0 0

0 0

0.2 300

30 45000

a3 a1 a2 rj

0 1 0 0

0 0 1 0

1 0 0 0

-3.5 0.5 -0.2 200

2.5 -0.5 0.4 100

25 25 20 55000

T

x* 25,20,25,0,0所以该问题的最优解为。由此即可得到原问题的最优T

25,20解为，也就是说产品A应生产25kg，B应生产20kg，该厂可获

得利润w* 55000元。

该题的matlab实现方法为：使用linprog函数求解一般的线性规划、最优解问题。 f=[-1000,-1500]; A=[9,5;4000,5000;4,10]; b=[350,200000,300]; xm=[0,0];

[x,z]=linprog(f,A,b,[],[],xm) 运算结果为：x = 25.0000 20.0000 z=

-5.5000e+004

4.excel在线性规划中的应用

例3.某厂用A1，A2两台机床，加工B1，B2，B3三种不同零件。已知在一个生产周期内A1只能工作80机时，A2只能工作100机时。一个

线性规划 毕业论文

生产周期计划加工70个零件B1，50个B2，20个B3。两台机床加工每个零件的时间和每个零件的成本，分别如表2和表3,问如何安排加工任务，才能使加工成本最低？

解：设A1生产B1、B2、B3的数量分别为：x11 ，x12 ，x13 ，A2生产B1、

B2、B3的数量分别为：x21 ， x22 ， x23 。

则该问题的数学模型为：

目标函数：mins 2x11 3x12 5x13 3x21 4x22 6x23 约束条件：

x11 x12 x13 80 x 2x 3x 100

2223 21

x11 x21 70

x12 2x22 50 x13 3x23 20

xij 0且为整数（i 1,2；j 1,2,3）

Excel求解方法：使用SUMPRODUCT函数及加载宏中的规划求解选项

线性规划 毕业论文

线性规划 毕业论文

5．小结

由于将线性规划问题化为标准形式之后的约束条件是一个非齐次线性方程组，故当考虑LP问题的解时，首先可以考虑非齐次线性方程组的解，然后再考虑目标函数的解最大最小值问题。

单纯形法是求解LP问题的一种常用方法，但单纯形法的运算量比较大，当约束条件中的约束变量比较多时，效费比就比较低，因此借助计算机软件的强大运算功能，既节约时间又提高了运算的准确性。对于一般的线性规划问题，应用excel、MTALAB都可以轻松解决，但MATLAB的整数线性规划运算功能欠缺，此时可以应用lingo、excel软件解决这类问题。随着计算机的大量应用，掌握一些基本的数学软件，将对以后的学习、工作大有裨益。 参考文献：

（1）.陈志杰.《高等代数与解析几何》，高等教育出版社，2006 （2）.唐文换.《数学模型》，高等教育出版社，2008 （3）. 百度文库：/

本文来源：https://www.bwwdw.com/article/9hx4.html