matlab初始化矩阵_代码 | 求解LP问题基本(可行)解的Matlab代码

介绍求解LP问题基本(可行)解的Matlab代码。

Contents

• 基本原理

• Matlab代码

  • 初始化代码环境

  • 初始化系数矩阵A和b

  • 找到所有的基本(可行)解

基本原理

基本(可行)解是线性规划问题的一个重要概念。它在几何上对应于LP问题的顶点。

考虑线性规划问题的标准型：

在线性规划中，基、基向量、基变量、基本解、基本可行解的概念定义如下：

换句话说，假定A是m*n阶矩阵，并且A的秩r(A)=m。那么，求解该基本(可行)解的步骤：

1. 从A中找到一个m*m阶的非奇异方阵B，也就是B的行列式det(B) ~=0；

2. 确定基变量XB和非基变量XN；

3. 代入方程AX=b,展开BXB+NXN=b；

4. 令XN = 0，代入,BXB+NXN=b，得到XB=B^(-1)b

尽管基本(可行)解的概念和步骤比较简单和清晰，但是手算会涉及到大量的矩阵运算，比较费时费力，接下来给出求解基本(可行)解的Matlab实现，供感兴趣的朋友参考使用。

Matlab代码

初始化代码环境

clc %清屏
clear all % 清除变量
close all % 关掉图像窗口
format RAT % 显示分数形式

初始化系数矩阵A和b

m = 2; %矩阵A的行数
n =4; %矩阵A的列数% 随机生成一个m*n行满秩矩阵A
flag = 0;
NumMax = 10; % 矩阵A的最大元素

% 随机生成秩为m的系数矩阵Awhile flag==0
A = randi(NumMax,m,n);if rank(A) == m
flag=1;endend
b = randi(NumMax,m,1); % 随机生成右端系数向量b

% 展示A,b,AX=bdisp('系数矩阵A是：')
disp(A)
disp('列向量b是：')
disp(b)
disp('约束组AX=b是：')
str = [repmat('%dx%d+',1,n-1) '%dx%d=%d.n'];for i = 1:m
v =[];for j =1:n
v =[v, A(i,j),j];end
fprintf(str,[v,b(i)])end

系数矩阵A是：
1 9 5 3
6 2 6 3
列向量b是：
5
6
约束组AX=b是：
1x1+9x2+5x3+3x4=5.
6x1+2x2+6x3+3x4=6.

找到所有的基本(可行)解

idxs = nchoosek(1:n,m); %所有可能的基阵的下标组合
count = size(idxs,1); %所有可能的基阵个数for k = 1:1:count% 按顺序从A中挑出m列组成B
idx = idxs(k,:);
B = A(:,idx);% 判断B是否构成基阵
str = [repmat('P%d,',m-1,1) 'P%d'];if det(B) == 0
fprintf(['n1.列向量' str '不能构成基阵.n'],idx); % B是奇异矩阵，不能构成基阵else
fprintf(['n1. 列向量' str '能构成基阵.n'],idx); % B不是奇异矩阵，能构成基阵% 令XN=0，解方程BXB+NXN=b,计算基本解为XB=B^(-1)b,XN=0;
X = zeros(1,n);
XB = inv(B)*b; % 基本解的基变量XB
XN = 0; % 基本解的非基变量XN为0
X(idx)=XB;
fprintf('2. 该基阵对应的基本解：X= [%s].n',rats(X));% 判断是否为基本可行解if sum(XB<0) == 0
fprintf('3. 该基本解也是基本可行解.n'); % XB分量>=0,是基本可行解；else
fprintf('3. 该基本解不是基本可行解.n'); % XB分量有小于0,不是基本可行解；endendend

1. 列向量P1,P2能构成基阵.
2. 该基阵对应的基本解：
X= [ 3/7 12/7 0 0 ].
3. 该基本解也是基本可行解.
1. 列向量P1,P3能构成基阵.
2. 该基阵对应的基本解：
X= [ -3 0 6 0 ].
3. 该基本解不是基本可行解.
1. 列向量P1,P4能构成基阵.
2. 该基阵对应的基本解：
X= [ 1/25 0 0 28/25 ].
3. 该基本解也是基本可行解.
1. 列向量P2,P3能构成基阵.
2. 该基阵对应的基本解：
X= [ 0 3/2 3/4 0 ].
3. 该基本解也是基本可行解.
1. 列向量P2,P4能构成基阵.
2. 该基阵对应的基本解：
X= [ 0 -3/17 0 21/17 ].
3. 该基本解不是基本可行解.
1. 列向量P3,P4能构成基阵.
2. 该基阵对应的基本解：
X= [ 0 0 3/38 21/19 ].
3. 该基本解也是基本可行解.

Published with MATLAB® R2015b