线性规划问题和MATLAB函数linprog的使用

2024-05-13 03:32

本文主要是介绍线性规划问题和MATLAB函数linprog的使用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转自:http://blog.csdn.net/jbb0523/article/details/50596555

题目:线性规划问题和MATLAB函数linprog的使用

        线性规划(Linear Programming, LP)问题的一般形式为:


其中。矩阵向量形式为


其中

       

       线线规划的几个基本性质:【文献[1]第46页】

       (1)线性规划问题的可行域如果非空,则是一个凸集-凸多面体;

       (2)如果线性规划问题有最优解,那么最优解可在可行域的顶点中确定;

       (3)如果可行域有界,且可行域只有有限个顶点,则问题的最优解必存在,并在这有限个顶点中确定;

       (4)最优解可由最优顶点处的有效约束形成的方程组的解确定。

       常用的线性规划求解方法有单纯形法和内点法。

1、单纯形法(simplex method)

       单纯形法是由G.B. Dantzig在1947年提出来的,这是20世纪数学界最重大的成果之一。单纯形法是一种迭代法,它根据线性规划问题的特点在问题可行域的顶点中逐步确定问题的最优解。在每一个是基本可行解的迭代点(即顶点),如果它不是最优的,单纯形法从与该顶点相连结的边中确定一个使目标函数值下降的边,沿该边移动可以确定一个与该顶点相邻且目标函数又优于该顶点的新顶点(新的基本可行解)。由于可行域的顶点数是有限的,如果每一次的移动都能使目标函数值下降,则经过有限次的移动方法必终止于问题的一个最优顶点。【文献[1]第57页】

       单纯形法要求线性规划具有标准形式,即

即约束函数都是等式约束,且决策变量均是非负的。

       任何线性规划问题使用单纯形法时都需要通过变换转换为线性规划的标准形。转换方法参见文献[1]第51页例2.1.6。

2、从单纯形法到内点法

       由于单纯形法的有效性,几十年来得到了广泛的应用。近年来,对于大规模的线性规划问题,尽管单纯形法受到了内点法的挑战,但单纯形法还是受到广大用户的青睐。

       一个算法如果其求得问题的解所用的运算工作量是问题的参数m和n的多项式,则称这一算法的复杂多项式时间算法;如果所需运算工作量的阶数是以m或n为幂的指数2m或2n,则称复杂性是指数时间的算法。

       单纯形算法的平均运算工作量是多项式时间的,但对于一个具体的问题其算法的复杂性并不一定是多项式的。1972年,Klee和Minty给出了一个复杂性为指数时间的例子。那么对线性规划问题是否存在时间复杂性是多项式的算法呢?如果存在多项式时间算法,如何设计这样的算法?

       1979年,前苏联数学家Khachiyan回答了第1个问题,他提出了一个椭球算法求不等式问题的解,并证明了算法的时间复杂性是多项式的。利用对偶理论,线性规划问题可以转换成不等式问题,这就明确回答了对线性规划存在多项式时间算法。但是计算的实际表明,椭球算法的效果要比单纯形方法差得多,并不是一个有实际应用价值的算法。

       1984年,在美国贝尔实验室工作的印度数学家Karmarkar回答了第2个问题,它对线性规划的求解提出了一个具有多项式时间复杂性的内点算法。

3、内点法(interior point method)

       求线性规划问题的单纯形方法在问题的基本可行解中确定最优解,在几何上,每次迭代它是沿着可行域的边界从一个顶点向另一个更好的顶点移动来实现的。内点算法则完全不同,它是从可行域的一个严格内点开始,产生一个使目标函数值逐步改善的严格内点序列,并最终收敛于问题的最优解。通过下图可以清晰的看出单纯形法与内点法的区别。

单纯形法与内战法轨迹(文献[1]图2.4.4)

       经过近20年的研究与发展,如今已有大量求解线性规划问题的内点算法,它们可以分成三类:路径跟踪算法,仿射调比算法,和原始对偶内点算法(primal-dual interior point method)。

4、线性规划问题的MATLAB求解

       在MATLAB中求解线性规划问题的函数是linprog,该函数集中了几种求线性规划的算法,如内点法和单纯形法,根据问题的规模或用户指定的算法进行求解。具体使用方法可查询帮助文件。

例:求如下线性规划问题。

输入以下代码:(代码是直接在Command Window中一行一行录入的,所以每行前面有符号“>>”)

[plain]  view plain copy
在CODE上查看代码片 派生到我的代码片
  1. >> f = [-5; -4; -6];  
  2. >> A = [1 -1  1;3  2  4;3  2  0];  
  3. >> b = [20; 42; 30];  
  4. >> lb = [0; 0; 0];  
  5. >> [x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)  

输出以下结果:

[plain]  view plain copy
在CODE上查看代码片 派生到我的代码片
  1. x =  
  2.     0.0000  
  3.    15.0000  
  4.     3.0000  
  5.   
  6. fval =  
  7.   -78.0000  
  8.   
  9. exitflag =  
  10.   
  11.      1  
  12.   
  13. output =   
  14.          iterations: 6  
  15.           algorithm: 'large-scale: interior point'  
  16.        cgiterations: 0  
  17.             message: 'Optimization terminated.'  
  18.     constrviolation: 0  
  19.   
  20. lambda =   
  21.     ineqlin: [3x1 double]  
  22.       eqlin: [0x1 double]  
  23.       upper: [3x1 double]  
  24.       lower: [3x1 double]  
参考文献:

【1】孙文瑜, 徐成贤, 朱德通.最优化方法(第二版)[M]. 北京:高等教育出版社, 2010.

【2】龚纯,王正林. 精通MATLAB最优化计算[M].北京: 电子工业出版社,2009.

这篇关于线性规划问题和MATLAB函数linprog的使用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/984562

相关文章

vue使用docxtemplater导出word

《vue使用docxtemplater导出word》docxtemplater是一种邮件合并工具,以编程方式使用并处理条件、循环,并且可以扩展以插入任何内容,下面我们来看看如何使用docxtempl... 目录docxtemplatervue使用docxtemplater导出word安装常用语法 封装导出方

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面