利用单纯形法进行线性规划求解

2024-01-24 22:12

本文主要是介绍利用单纯形法进行线性规划求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 作业要求

例16.5:

  • 理论推导

本作业题的目的分别利用两阶段修正单纯形法与两阶段仿射尺度法对线性规划问题进行求解。

两阶段修正单纯形法是一种求解线性规划问题的方法,它主要用于处理约束系数矩阵不包含单位矩阵(没有明显的基本可行解)的情况,也就是无法直接得到初始基可行解的情况。它分为两个阶段:

第一阶段:引入人工变量,构造一个只含有人工变量的目标函数,并求其最小值。如果最小值为零,则说明原问题有基可行解,可以进入第二阶段;如果最小值不为零,则说明原问题无可行解,算法终止。

第二阶段:去掉人工变量,恢复原目标函数,用单纯形法求解原问题的最优解。

两阶段仿射尺度法的基本原理同两阶段修正单纯形法,只不过将单纯形法计算的模块替换为仿射尺度的计算模块。

修正单纯形法是一种改进的单纯形法,它可以避免对大部分非基变量的计算,从而提高求解线性规划问题的效率。修正单纯形法的基本思想是,给定一个初始的可行基矩阵和其逆矩阵,通过不断地修正旧的可行基矩阵的逆矩阵,获得新的可行基矩阵的逆矩阵,进而完成单纯形法所需要的其他运算。修正单纯形法的主要步骤如下:

S1.针对初始基本可行解构造修正的单纯形表

S2.计算当前检验数,如果对所有非基变量都有检验数大于等于零,则停止运算,当前基本可行解即是最优解;否则进入下一步

S3.从小于零的检验数中选择一个检验数作为进基变量

S4.如果不存在正的约束系数,则停止运算,问题有无界解;否则计算出基变量和步长

S5.更新基本可行解和修正的单纯形表

S6.回到第二步继续迭代

最为基础的单纯形法的基本思想是从一个初始的基本可行解出发,通过不断地改进基本可行解,使目标函数值不断增大或减小,直到找到最优解为止。单纯形法的基本步骤如下:

S1.将线性规划问题化为标准形式,即目标函数为最大化,约束条件为等式,变量非负。

S2.找到一个初始的基本可行解,即满足约束条件和非负性的一组解,可以通过引入松弛变量或人工变量来构造。

S3.计算检验数,即目标函数中非基变量的系数减去基变量对应列的线性组合。检验数反映了非基变量对目标函数值的影响。

S4.判断是否达到最优解。如果所有检验数都小于等于零(最大化问题)或大于等于零(最小化问题),则当前基本可行解是最优解,算法停止;否则进入下一步。

S5.选择一个进基变量和一个出基变量。进基变量是检验数为正(最大化问题)或负(最小化问题)的非基变量中的一个,可以按照最大系数法、最小下标法等规则来选取。出基变量是当前基变量中的一个,可以按照最小比率法来选取,即使得进基变量增加后不会导致其他基变量为负。

S6.进行枢轴运算,即用高斯消元法将出基变量所在行的主元(即进基变量所在列的元素)化为1,然后用该行消去其他行中该列的元素,使得进基变量成为新的基变量,而出基变量成为新的非基变量。

S7.回到第三步继续迭代,直到达到最优解或发现问题无界或无可行解。

  • 实验结果

图1,图2分别展示了两题中迭代过程中值的变化情况。

图1 第一题的迭代过程

图2 第二题的迭代结果

附录

作业一

%main1.mA=[1 1 1 0; 5 3 0 -1];b=[4;8];c=[-3;-5;0;0];options(1)=1;format rat;tprevsimp(c,A,b,options);% revsimp.mfunction [x,v,Binv]=revsimp(c,A,b,v,Binv,options)if nargin ~= 6options = [];if nargin ~= 5disp('Wrong number of arguments.');return;endendformat compact;%format short e;options = foptions(options);print = options(1);n=length(c);m=length(b);cB=c(v(:));y0 = Binv*b;lambdaT=cB'*Binv;r = c'-lambdaT*A; %row vector of relative cost coefficientsif printdisp(' ');disp('Initial revised tableau [v B^(-1) y0]:');disp([v Binv y0]);disp('Relative cost coefficients:');disp(r);end %ifwhile ones(1,n)*(r' >= zeros(n,1)) ~= nif options(5) == 0;[r_q,q] = min(r);else%Bland’s ruleq=1;while r(q) >= 0q=q+1;endend %ifyq = Binv*A(:,q);min_ratio = inf;p=0;for i=1:m,if yq(i)>0if y0(i)/yq(i) < min_ratiomin_ratio = y0(i)/yq(i);p = i;end %ifend %ifend %forif p == 0disp('Problem unbounded');break;end %ifif print,disp('Augmented revised tableau [v B^(-1) y0 yq]:')disp([v Binv y0 yq]);disp('(p,q):');disp([p,q]);endaugrevtabl=pivot([Binv y0 yq],p,m+2);Binv=augrevtabl(:,1:m);y0=augrevtabl(:,m+1);v(p) = q;cB=c(v(:));lambdaT=cB'*Binv;r = c'-lambdaT*A; %row vector of relative cost coefficientsif print,disp('New revised tableau [v B^(-1) y0]:');disp([v Binv y0]);disp('Relative cost coefficients:');disp(r);end %ifend %whilex=zeros(n,1);x(v(:))=y0;%tprevsimpfunction [x,v]=tprevsimp(c,A,b,options)if nargin ~= 4options = [];if nargin ~= 3disp('Wrong number of arguments.');return;endendclc;format compact;%format short e;options = foptions(options);print = options(1);n=length(c);m=length(b);%Phase Iif printdisp(' ');disp('Phase I');disp('-------');endv=n*ones(m,1);for i=1:mv(i)=v(i)+i;end[x,v,Binv]=revsimp([zeros(n,1);ones(m,1)],[A eye(m)],b,v,eye(m),options);%Phase IIif printdisp(' ');disp('Phase II');disp('--------');end[x,v,Binv]=revsimp(c,A,b,v,Binv,options);if printdisp(' ');disp('Final solution:');disp(x');end

作业二

% main2.mA=[1 1 1 0; 5 3 0 -1];b=[4;8];c=[-3;-5;0;0];options(1)=0;tpaffscale(c,A,b,options);% tpaffscale.mfunction [x,N]=tpaffscale(c,A,b,options)if nargin ~= 4options = [];if nargin ~= 3disp('Wrong number of arguments.');return;Endend%clc;format compact;format short e;options = foptions(options);print = options(1);n=length(c);m=length(b);%Phase Iif print,disp(' ');disp('Phase I');disp('-------');endu = rand(n,1);v = b-A*u;if v ~= zeros(m,1),u = affscale([zeros(1,n),1]',[A v],b,[u' 1]',options);u(n+1) = [0];endif printdisp('')disp('Initial condition for Phase II:')disp(u)endif u(n+1) < options(2),%Phase IIu(n+1) = [];if printdisp(' ');disp('Phase II');disp('--------');disp('Initial condition for Phase II:');disp(u);end[x,N]=affscale(c,A,b,u,options);if nargout == 0disp('Final point =');disp(x');disp('Number of iterations =');disp(N);end %ifelsedisp('Terminating: problem has no feasible solution.');end% affscale.mfunction [x,N] = affscale(c,A,b,u,options);if nargin ~= 5options = [];if nargin ~= 4disp('Wrong number of arguments.');return;endendxnew=u;if length(options) >= 14if options(14)==0options(14)=1000*length(xnew);endelseoptions(14)=1000*length(xnew);end%if length(options) < 18options(18)=0.99; %optional step size%end%clc;format compact;format short e;options = foptions(options);print = options(1);epsilon_x = options(2);epsilon_f = options(3);max_iter=options(14);alpha=options(18);n=length(c);m=length(b);for k = 1:max_iter,xcurr=xnew;D = diag(xcurr);Abar = A*D;Pbar = eye(n) - Abar'*inv(Abar*Abar')*Abar;d = -D*Pbar*D*c;if d ~= zeros(n,1),nonzd = find(d<0);r = min(-xcurr(nonzd)./d(nonzd));elsedisp('Terminating: d = 0');break;endxnew = xcurr+alpha*r*d;if print,disp('Iteration number k =')disp(k); %print iteration index kdisp('alpha_k =');disp(alpha*r); %print alpha_kdisp('New point =');disp(xnew'); %print new pointend %ifif norm(xnew-xcurr) <= epsilon_x*norm(xcurr)disp('Terminating: Relative difference between iterates <');disp(epsilon_x);break;end %ifif abs(c'*(xnew-xcurr)) < epsilon_f*abs(c'*xcurr),disp('Terminating: Relative change in objective function <' );disp(epsilon_f);break;end %ifif k == max_iterdisp('Terminating with maximum number of iterations');end %ifend %forif nargout >= 1x=xnew;if nargout == 2N=k;endelsedisp('Final point =');disp(xnew');disp('Number of iterations =');disp(k);end %if

这篇关于利用单纯形法进行线性规划求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

使用Python进行GRPC和Dubbo协议的高级测试

《使用Python进行GRPC和Dubbo协议的高级测试》GRPC(GoogleRemoteProcedureCall)是一种高性能、开源的远程过程调用(RPC)框架,Dubbo是一种高性能的分布式服... 目录01 GRPC测试安装gRPC编写.proto文件实现服务02 Dubbo测试1. 安装Dubb

Linux使用scp进行远程目录文件复制的详细步骤和示例

《Linux使用scp进行远程目录文件复制的详细步骤和示例》在Linux系统中,scp(安全复制协议)是一个使用SSH(安全外壳协议)进行文件和目录安全传输的命令,它允许在远程主机之间复制文件和目录,... 目录1. 什么是scp?2. 语法3. 示例示例 1: 复制本地目录到远程主机示例 2: 复制远程主

windows系统上如何进行maven安装和配置方式

《windows系统上如何进行maven安装和配置方式》:本文主要介绍windows系统上如何进行maven安装和配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. Maven 简介2. maven的下载与安装2.1 下载 Maven2.2 Maven安装2.

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y

Go语言中使用JWT进行身份验证的几种方式

《Go语言中使用JWT进行身份验证的几种方式》本文主要介绍了Go语言中使用JWT进行身份验证的几种方式,包括dgrijalva/jwt-go、golang-jwt/jwt、lestrrat-go/jw... 目录简介1. github.com/dgrijalva/jwt-go安装:使用示例:解释:2. gi

SpringBoot如何对密码等敏感信息进行脱敏处理

《SpringBoot如何对密码等敏感信息进行脱敏处理》这篇文章主要为大家详细介绍了SpringBoot对密码等敏感信息进行脱敏处理的几个常用方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录​1. 配置文件敏感信息脱敏​​2. 日志脱敏​​3. API响应脱敏​​4. 其他注意事项​​总结

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

Python对PDF书签进行添加,修改提取和删除操作

《Python对PDF书签进行添加,修改提取和删除操作》PDF书签是PDF文件中的导航工具,通常包含一个标题和一个跳转位置,本教程将详细介绍如何使用Python对PDF文件中的书签进行操作... 目录简介使用工具python 向 PDF 添加书签添加书签添加嵌套书签Python 修改 PDF 书签Pytho

Java进行日期解析与格式化的实现代码

《Java进行日期解析与格式化的实现代码》使用Java搭配ApacheCommonsLang3和Natty库,可以实现灵活高效的日期解析与格式化,本文将通过相关示例为大家讲讲具体的实践操作,需要的可以... 目录一、背景二、依赖介绍1. Apache Commons Lang32. Natty三、核心实现代