1

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

T5-08/05/2015: Algoritmo Simplex.

Introdução

Uma pratica inicial em um problema de otimização indistintamente de sua aplicação na vida real é procurar uma solução básica factível, caso de este estúdioestudo. A, a partir dela é possível um trabalho computacional mais ótimo otimizado para obter os resultados desejados.

Metodologia

O programa de otimização Simplex foi feito na plataforma “MATLAB”, sendo nosso este caso um exemplo de maximização para o problema proposto na página 35 da unidade 3 dos apontes da aula, referente ao método simplex, ; em neste caso particular, temos como restrições as mencionadas nas equações 1, 2 e 3.

2ᵡ1 + ᵡ2 + ᵡ3 ≤2 eq. [1]

2ᵡ1 + ᵡ2 + ᵡ3 ≤2 eq. [2]

2ᵡ1 + ᵡ2 + ᵡ3 ≤2 eq. [3]

Para maximizar o problema expressado na equação 4.

3ᵡ1 + ᵡ2 + 3ᵡ3 = Z eq. [4]

O trabalho esDeve-se obter o máximo valor das variáveis ᵡ1 ᵡ2 ᵡ3 para que a

expressão da equação [4], seja a maior, sendo as variáveis de analises sempre positivas, assim da seguinte forma.

x1≥ 0 , x2≥ 0 , x3 ≥ 0 ,

O processo para o algoritmo foi feito seguindo o expressado descrito nos passos para programação de Algoritmo Simplex na página 33 dos apontesmencionados.

Maio de 2015

2

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

Paso 0: O usuário tem que declarar os valores das matrizes requeridas para o a analisesanálises, as quais são chamadas “a”, “b” e “z”.

A matriz “a”, tem que ser quadrada e seus valores todos positivos sendo de caraterísticas expressadas matematicamente como:

“a” € Rmxm

A matriz “b” que tem os valores de:

“b” € Rmx1

A matriz “z” que tem os valores de:

“z” € R1xm

A partir delas se procede a criar a matriz canônica, a qual terá a dimensão de Rm+1x2m+1 a qual, que é a base para o a analise análise de maximização.

Passo 1: Como se trata de um problema de maximização, o primeiro aspecto para o a analise análise é são os valores da equação de otimização. Sendo, sim todos eles são negativos, já se concluí concluía-se que já que é uma solução ótima y e no precisa de nenhum cálculo matricial.

Passo 2: A seguir é requeridorequer-se determinar o valor a ser considerado como pivô dentro do algoritmo simplex. Determina , determine-se o termo menor inferior a “0” na linha “m+1” da matriz canônica. Em seguida, , depois na coluna onde fica o número mencionado, calculecalcula-se a razão aritmética dos termos da última coluna com a coluna selecionada anteriormente, mantendo a mesma linha para o cálculo. O, o resultado obtido vai serserá armazenado no vetor “div”, o qual, por meio através da função “min( )”, gera a posição do menor valor positivo do vetor analisado; assim foi obtidoobtêm-se os valores de “p” e “q”, indispensáveis para o seguinte passo do da programação.

Passo 3: Determinado a o endereço do pivô, procede-se ao cálculo de cadaum a um os termos da nova matriz, a qual tem como objetivo determinar um valor de maximização para uma das variáveis expressadas na equação de otimização [4], sendo a base para a iteração o expressado nas equações [5] e [6] que vão em coincidência dos sub índices “i” e “p”.

Maio de 2015

3

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

Y ij' =Y ij−

Y pj

Y pq

Y iq i ≠ p [5]

Y ij' =

Y pj

Y pq

i=p [6]

Depois de finalizar com todos os termos da matriz canônica, é indispensável determinar sim se entre os valores da última linha existe um valor negativo, para iniciar novamente o cálculo com o novo pivô, e, de este modo, procurar uma nova coluna até chegar a uma solução básica fatível.

Já no exemplo prático, é necessário mencionar que configure-se uma função no MATLAB, a qual apresenta as caraterísticas básicas requeridas.

[C,B,Z]=otimsimplex(a,b,z) (1)

A linha descrita na expressão (1) é o texto da função que tem que ser digitada no MATLAB e, arroja lança como resultado as matrizes C,B,Z que são a resposta do algoritmo de otimização. Sendo:

C: a matriz canônica gerada y resultante depois do pivotação do termo selecionado.

B: a matriz resposta que contém os valores para os termos de x1 até x2m-1.

Z: é a resposta obtida para a equação de maximização depois de substituir os termos de “x” na expressão objeto do analises.

Resultados

[i)] Exemplo pag. 35: Após da execução da função (1), para as matrizes que se detalham em (2), obteveobtiveram-se os resultados expressados em (3).

a=[2 1 11 2 32 2 1]b=[256 ] z=[ 3 1 3 ] (2)

Maio de 2015

4

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

C=[115

035

−15

015

035

1−15

25

085

0 1 0 −1 0 1 4

075

065

35

0275

] (3)

B=[ 15

085

0 0 4]Z=[−27

5 ]O resultado obtido pode ser contrastado com a resposta da página 37 dos apontes de aula, e pode-se expressar dizer que eles convergem nos mesmos valores.

[ii)] Exemplo planteado: considere-se a o seguinte enunciado.

Um escritório de serviços complementários de limpeza, tem três contratos ao mês sendo, x1, x2 e x3; assim um máximo valor a faturar é de $ 30.000 por mês; a primeira preocupação é que o custo da mão de obra respectivamente tem que obedecer a um percentual de 35%, 25%, e 45%, respectivamente, sabendo que um máximo da variável é $ 18000; outra função é os materiais utilizados, a qual obedece a um 5%, 8% e 19%, o máximo por esta variável é $ 2500; finalmente deve-se considerar os custos administrativos que fazem referência a um 10%, 9% e 13%, sendo o máximo de inversão em esteneste item o valor de $ 3000. Maximize os valores de cada contrato que gerarem a maior utilidade.

Analises: O primer primeiro ponto é a obtenção das matrizes “a”, “b” e “z”, que descrevem o problema planteado indicado, expressasas quais estão expressadas em (4).

a=[10500 7500 135001500 2400 57003000 2700 3900 ]

(4)b=[ 18000 2500 3000 ]

z=[ 1 1 1 ]

Maio de 2015

5

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

Após isto, requere-se apenas apenas é requerido a execução da função expressada em (1). E fForam obtidas as respostas expressadas em (5).

C=[0 0 6814,286 1 1,8571 −4,428 9357,1420 1 3,571 0 0,0009 −0,0004 0,9521 0 −1,914 0 −0,0008 0,0007 0,1420 0 0,657 0 9,523 0,0002 1,095

] B=[ 0,142 0,952 0 9357,142 0 0 ] (3)

Z=[−1,095 ]

Análises dos resultadosComo se pode observar, a função desarrolhada em MATLAB, satisfaze os requerimentos do da analisesanálise., os Os valores obtidos são um resumo, pois, no segundo cálculo, é possível expressar mais posições decimais.

As matrizes de resposta são uma solução básica fatível para cada caso, sendo importante mencionar que é requerido um analisesrequer-se uma análise adicional para expressar uma solução ótima de oo problema de maximização planteaoindicado.

As descrições das linhas de programa estão expressadas no anexo 1, onde se descrevi descreve brevemente cada um de osdos aspectos importantes dentro do processo de programação.

Conclusão

A análise dos valores obtidos aponta como conclusão que o processo de cálculo de uma solução básica fatível é facilmente desenhado bajo em plataformas de programação disponíveis e fornecem uma eficiência y garantiacom eficiência e garantia bastante confiávelconfiáveis.

Uma análise dos dados gerados para o exemplo (ii), foi feito feita para um caso real de analises análise pessoalparticular, que forneci-oao qual se obteve uma conclusão muito interessante, pois não teve houve até agora uma ferramenta para vincular vários contratos que não têm nexo entre eles e, procurar uma relação matemática que procure obter uma utilidade maior, que é o ponto onde eles se vinculam-se.

Maio de 2015

6

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

Maio de 2015

7

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

ANEXO 1

function [ canonic,Z,ZT ] = otimsimplex( a,b,z ) %otimsimplex% % Avalua um problema de otimização para obter% uma solução básica factível.% % Sintaxes% [A,B,ZT]=Otimsimplex(a,b,z)% % Descrição % % [A,B,ZT]=Otimsimplex(a,b,z) %otimiza uma equação z para a sujeito a Ax=b e x >= 0 % % Observações% As características das matrizes têm que ser % A € Rnxn >= 0 e B € Rnx1 e Z € R1xn div=0;i=0;canonic=cat(2,a,eye(size(a)),b);z=-z;z=cat(2,z,zeros(1,length(canonic)-length(z)));canonic=cat(1,canonic,z);columna=-1;[r,t]=size(canonic);X=zeros(1,t);Z=zeros(1,t-1);if find(b>0)~=0while columna <0 vectorz=canonic(r,:); [~,q]=min(vectorz); for p=1:r-1; div(p,1)=canonic(p,t)/canonic(p,q);end [y1,y2,y3]=find(div>0); for i=1:y1 div1(y1)=div(y1);end [~,p]=min(div1);

Maio de 2015

Construção da matriz canônica a partir das matrizes “a” “b” e “c”, e obtenção dos valores “p” e “q” que são as direções do elemento pivô.

8

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

for i=1:r if i==p; for j=1:t canonic1(p,j)=canonic(p,j)/canonic(p,q); end end if i~=p; for j=1:t canonic1(i,j)=canonic(i,j)-(canonic(p,j)*canonic(i,q)/canonic(p,q)); end endend

canonic=canonic1;vectorz=canonic(r,:); [columna,q]=min(vectorz);end for j=1:t-1 for i=1:r X(j)=X(j)+abs(canonic(i,j)); end if X(j)==1 vectorj=canonic(:,j); [~,s]=max(vectorj); Z(j)=canonic(s,t); endendendZT=-canonic(r,t);end

Maio de 2015

Cálculo dos novos termos Yij para a nova matriz canônica de dimensões (r,t).

Seleção dos dados para presentação das matrizes de saída “canonic”, “Z” e “ZT” .

9

Mestrado em Engenharia Elétrica JUAN PABLO OCHOA AVILES

Bibliografia

CHAPMAN, S. J. (2011). programaçao em MATLAB para engenheiros.SAO PAULO: CENAGE LEARNING.

Jalón, J. G. (2009). Aprenda Matlab 7.0. MADRID: Universidad Politécnica de Madrid.

Pelas normas da ABNT, o certo seria que isto viesse após a conclusão, antes dos anexos, da seguinte forma:

Referências Bibliográficas:

CHAPMAN, S. J. Programação em MATLAB para engenheiros. São Paulo: Cenage Learning, 2011.

JALÓN, J.g. Aprenda Matlab 7.0. Madrid: Universidad Politécnica de Madrid, 2009.

Maio de 2015