matlab——线性规划
2024-08-23 14:25:08
@
前言
线性规划是数学规划中的一个重要分支,常用于解决如何利用现有资源来安排生产,以取得最大经济效益的问题。本文将粗略地介绍线性规划,matlab实现和常见变形。
一、基本概念
一般线性规划问题地(数学)标准型为
\[max\quad z=\sum\limits_{j=1}^nc_jx_j, \\s.t \quad
y=
\begin{cases}
\sum\limits_{j=1}^na_{ij}x_j=b_i,i=1,2,...,m\\
x_j\geq0,j=1,2,...,n
\end{cases}
\tag{1}
\]
y=
\begin{cases}
\sum\limits_{j=1}^na_{ij}x_j=b_i,i=1,2,...,m\\
x_j\geq0,j=1,2,...,n
\end{cases}
\tag{1}
\]
可行解:满足约束条件的解\(x=[x_1,...,x_n]^T\)
最优解:使目标函数达到最大值的可行解
二、matlab实现
1.常用函数
matlab中规定线性规划的标准形式为:
\[\underset {x}{min}\ \pmb f^T\pmb x,\\s.t\quad
\begin{cases}
\pmb{A\cdot x}\leq \pmb b,\\
Aeq \cdot \pmb x=beq\\
lb\leq x\leq ub
\end{cases}
\]
\begin{cases}
\pmb{A\cdot x}\leq \pmb b,\\
Aeq \cdot \pmb x=beq\\
lb\leq x\leq ub
\end{cases}
\]
其中\(\pmb{f,x,b},beq,lb,ub\)为列向量, \(\pmb f\)称为价值向量,\(\pmb b\)称为资源向量;\(\pmb A,Aeq\)为矩阵。
matlab求线性规划的函数为
[x,fval]=linprog(f,A,b);
[x,fval]=linprog(f,A,b,Aeq,beq);
[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub);//如果Aeq,beq不存在用[]代替
注意:
(1)如果是求\(\underset {x}{max}\ \pmb f^T\pmb x\),则需转化为\(\underset {x}{min}\ \pmb {-f}^T\pmb x\),答案为函数求出来的值的相反数。
(2)在得到矩阵\(\pmb {A,b}\)前,要将所有不等式转化为\(\pmb {Ax}\leq \pmb b\)的形式。
2.常见变形
\[min\quad |x_1|+|x_2|+...+|x_n|,\\ s.t\quad \pmb {Ax\leq b}.
\]
\]
这看起来不是线性规划,但可以通过变换转化成线性规划问题。
注意到对任意\(x_i\),存在\(u_i,v_i\geq 0\)满足
\[x_i=u_i-v_i,|x_i|=u_i+v_i\\u_i=\frac{x_i+|x_i|}{2},v_i=\frac{|x_i|-x_i}{2}
\]
\]
记\(\pmb u=[u_1,...,u_n]^T,\pmb v=[v_1,...,v_n]^T\),于是上述问题转化为
\[min\quad \sum\limits_{i=1}^{n}(u_i+v_i),\\s.t\
\begin{cases}
\pmb{A\cdot (u-v)}\leq \pmb b,\\
\pmb {u,v}\geq 0.\\
\end{cases}
\]
\begin{cases}
\pmb{A\cdot (u-v)}\leq \pmb b,\\
\pmb {u,v}\geq 0.\\
\end{cases}
\]
改写成matlab形式
\[min\quad ,\left[ \begin{matrix} 1\\1\end{matrix}\right]^T\left[ \begin{matrix} \pmb u\\\pmb v\end{matrix}\right]\\s.t\
\begin{cases}
[A,-A]\cdot \left[ \begin{matrix} \pmb u\\\pmb v\end{matrix}\right],\\
\pmb {u,v}\geq 0.\\
\end{cases}
\]
\begin{cases}
[A,-A]\cdot \left[ \begin{matrix} \pmb u\\\pmb v\end{matrix}\right],\\
\pmb {u,v}\geq 0.\\
\end{cases}
\]
code:
//z=|x1|+2|x2|+3|x3|+4|x4|
f=1:4;
f=[f,f]';
A=[1,-1,-1,1;1,-1,1,-3;1,-1,-2,3];
A=[A,-A];
b=[-2;-1;-0.5];
[y,z]=linprog(f,A,b,[],[],zeros(8,1));
x=y(1:4)-y(5:end)
z
参考书目
《数学建模算法与应用》
最新文章
- Android Studio 多个编译环境配置 多渠道打包 APK输出配置
- javascript的类型、值和变量
- pull 解析XML 文件
- SlickUpload Upload to disk
- Xiph基金会成员:Timothy B. Terriberry
- asp自动解析网页中的图片地址,并将其保存到本地服务器
- CentOS 7 之Shell学习笔记
- 工程启动加载.properties/.xml配置文件
- C# ListBox 每行显示颜色设置
- ORACLE数据库SQL优化 not in 与not exits
- STS搭建SpringBoot项目
- SQL 一列数据整合为一条数据
- node.js跨域
- go mysql insert变量到数据库
- js中怎么使点击按钮后文本框获得焦点
- 剑指Offer 15. 反转链表 (链表)
- 欢迎访问新博客(pfzheng.tech)
- c语言:复合文字
- npm 设置地址
- SSH-CLIENT : gSTM
热门文章
- CVPR2019论文解读:单眼提升2D检测到6D姿势和度量形状
- AlexeyAB DarkNet YOLOv3框架解析与应用实践(一)
- 剑指 Offer 04. 二维数组中的查找
- Django基础之模板层
- 消息队列面试题、RabbitMQ面试题、Kafka面试题、RocketMQ面试题 (史上最全、持续更新、吐血推荐)
- 【题解】localmaxima 数论
- DOS命令行(2)——Windows磁盘维护与管理
- JavaScript 实现:输出斐波那契数列
- 解决“与 Microsoft Exchange 的连接不可用,Outlook 必须联机或已连接才能完成此操作”
- Java中对象初始化过程