论文总字数:14231字
摘 要
本文在介绍线性规划的模型与解的基础上,结合实例介绍了线性规划问题的具体求解方法,如图解法、单纯形法、大M法、两阶段法、MATLAB软件法与LINGO软件法.关键词: 线性规划,图解法,单纯形法,软件法
Abstract: In this paper, the author described the method of solving linear programming problem on the basis of introducing the model and solutions of linear programming, such as graph method, simplex method, large M method, two-stage method, MATLAB software method and LINGO software method.
Keywords: linear programming, graph method, simplex method, software method https://www.baidu.com/javascript:;
目 录
1 引言………………………………………………………………………… 3
2 线性规划问题的模型与求解……………………………………………… 3
2.1 模型介绍………………………………………………………………… 3
2.2 标准形式………………………………………………………………… 4
2.3 模型求解………………………………………………………………… 5
3 求解方法…………………………………………………………………… 6
3.1 图解法…………………………………………………………………… 6
3.2 单纯形法………………………………………………………………… 8
3.3 人工变量法……………………………………………………………… 11
3.3.1 大M法………………………………………………………………… 11
3.3.2 两阶段法……………………………………………………………… 14
3.4 软件法…………………………………………………………………… 16
3.4.1 MATLAB软件法………………………………………………………… 16
3.4.2 LINGO软件法………………………………………………………… 19
结束语………………………………………………………………………… 22
参考文献……………………………………………………………………… 23
致谢…………………………………………………………………………… 24
1 引言
在现实经济活动中,我们不断碰到诸如此类的问题:什么是最好的决策或者最佳的方案.例如企业在外在条件不变的情况下,如何通过合理安排,改进生产计划人、物、资源,使得成本最低.这些问题就是所谓的线性规划问题.下面让我们通过一个实际问题来认识线性规划的建模技巧和实际应用[1].
某农场每天至少使用800kg混合饲料.这种混合饲料是由玉米和大豆粉混合而成.每千克玉米含蛋白质90g,含纤维20g,费用为3元;每千克大豆粉含蛋白质600g,含纤维60g,费用为9元.混合饲料的营养要求是至少30%的蛋白质和至多5%的纤维.该农场希望确定每天饲料最少的饲料混合.
对于上面提出的问题,假定用分别表示混合饲料中玉米和大豆粉的千克数.因农场每天至少使用800kg混合饲料,于是有.对于蛋白质的营养需求约束,含在kg玉米和kg大豆粉中的蛋白质总量为kg.这个量至少应等于混合饲料总量的30%,即同样,纤维的需求至多为5%,构造的约束为农场的目标是使得这种混合饲料每天的总成本达到最小,因此有将上面方程化简约束,问题可归结为:
上述问题是求极值问题,问题中变量的取值是受一系列的限制,求解这类带附加限制条件的极值问题就是我们线性规划研究的内容.
2 线性规划问题的模型与求解
2.1 模型介绍
规划问题的数学模型包含三个组成要素,即
决策变量,指决策者为实现规划目标采取的方案、措施,是问题中所要确定的未知的
量.
目标函数,指问题要达到的目的要求,表示为决策变量的函数.
约束条件,指决策变量取值时受到的各种可用资源的限制,表示为含决策变量的等式或不等式.
如果在规划问题的数学模型中,决策变量为可控制的连续变量,目标函数和约束条件都是线性的,这类模型称作为线性规划问题的数学模型.
线性规划问题的数学模型的一般形式为
(1)
以上模型的简写形式为
(2)
2.2 标准形式
由于目标函数和约束条件内容和形式上的差别,线性规划问题可以有多种多样.为了便于讨论,规定线性规划的标准形式如下:
(3)
标准形式的线性规划模型中,目标函数为求极大值(有些地方规定是求极小值),约束条件全为等式,约束条件右端常数项全为非负值,变量的取值为非负.对不符合标准形式的线性规划问题,可以通过下列方法化为标准形式.
目标函数为极小值,即为
(4)
因为求min z等价于求max (-z),另,即化为
(5)
约束条件为不等式.当约束条件为“”时,如,可令
得,显然.当约束条件为“”时,如,可令,得,.和是新加上去的变量,取值均为非负,加到原约束条件中去的目的是使不等式转化为等式,其中称为松弛变量,一般称为剩余变量,其实质与相同,故也有统称为松弛变量的.松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超用的资源数,均未转化为价值和利润,所以引进模型后它们在目标函数中的系数均为0.
取值无约束的变量.如果变量x代表某产品当年计划数与上一年计划数之差,显然x的取值可能是正也可能是负,这时可令,其中,,将其代入线性规划模型即可.
变量.可令,显然[2].
剩余内容已隐藏,请支付后下载全文,论文总字数:14231字
该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;