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

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

相关文章

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

linux解压缩 xxx.jar文件进行内部操作过程

《linux解压缩xxx.jar文件进行内部操作过程》:本文主要介绍linux解压缩xxx.jar文件进行内部操作,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、解压文件二、压缩文件总结一、解压文件1、把 xxx.jar 文件放在服务器上,并进入当前目录#

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

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.