Student

Funcao em Matlab para pivoteamento

function [I,l] = PIVOT(I,c,A,x)

% Input
% I ...Indice vetor base
% c ...Vetor da funcao objetivo
% A ...Matriz das restriçoes
% x ...Vetor Base

% Output
% I ...Indice novo vetor base
% l ...-1, se prob. ilimitado
% 0, se min. presente
% 1, se ainda nao chegou no minimo

l = 1;

% Forma o indice J
J = [1:size(A,2)];
J(I) = zeros(size(I));
J = find(J);

% Calcula o u u = c(J) - A(:,J)'*inv(A(:,I)')*c(I);

% verifica se y já eh sol. otima basica if min(u)>=0; l = 0 ; return; end

% encontra o u_r com indice minimo j = find(um); [nd,md] = size(d); if l == -1 return; else if nd ~= 0 if l == 0 l = -1; end else l = 0; end end end Especificacoes...

Número de soluções básicas pode ser estimado usanado n! m!(n−m), ou seja, exponencialmente falando.

Soluções Básicas e Pontos Extremos

Teorema a ser considerado:

Seja o conjunto S = {x ∈ Rn : Ax = b,x ≥ 0}. Então, x é um ponto extremo desse conjunto
S se e somente se x é uma solução básica factível.

Seja x uma solução básica factível, então podemos assumir por contradição

x = αy + (1 − α)z, y,z ∈ S − {x} e α ∈ (0,1).

max 8x1 + 9x2 + 5x3
s.t. x1 + x2 + 2x3 + x4 = 2
2x1 + 3x2 + 4x3 +x5 = 3
6x1 + 6x2 + 2x3 +x6 = 8 x1; x2; x3; x4; x5; x6  0

Como exemplo. Podemos montar vetores matrizes:

A = [1 1 2 1 0 0;2 3 4 0 1 0;6 6 2 0 0 1];

b = [2;3;8];

c = [8;9;5;0;0;0];

Assim podemos contruir os vetores para a funcao PIVOT: I ...Indice vetor base c ...Vetor da funcao objetivo
A ...Matriz das restriçoes x ...Vetor Base

Output
I ...Indice novo vetor base l ...-1, se prob. ilimitado ou 0, se min. presente, ou 1, se ainda nao chegou no minimo

Funcao em Matlab para pivoteamento

function [I,l] = PIVOT(I,c,A,x)

% Input
% I ...Indice vetor base
% c ...Vetor da funcao