Combinação positiva

[vasco16]

Boas pessoal,

Estou a desenvolver uma aplicação mas bloqueie na elaboração do algoritmo.

Se alguém me puder dar um empurrão agradecia.

Então é assim:

Dado 3 valores reais positivos superior a 1, que ficarão numa linha.

Depois mais 3 valores reais positivos superiores a 0,5 que ficarão noutra linha.

Agora com estas 2 linhas vou gerar 3 outros numeros (x,y,x):

O processo de calculo desde 3 numeros é:

x = (ao primeiro numero da segunda linha) * o primeiro numero da primeira linha

y = (ao segundo numero da segunda linha) * o segundo numero da primeira linha

z = (ao terceiro numero da segunda linha) * o terceiro numero da primeira linha

Por fim vou calcular o resultado final que é (a,b,c):

a = x - (Soma dos 3 valores da segunda linha)

b = y - (Soma dos 3 valores da segunda linha)

c = z - (Soma dos 3 valores da segunda linha)

Nota:

O valores da 2 linha podem (ou devem ser alterados) até um máximo de 10,00

Objectivo:

Os três ultimos numeros (a,b,c) têm de ser positivos (incluindo 0)

[mogers]

Isto é um problema de programação linear (a versão inglesa é muito mais completa).

Podes ver alguns slides que falam disto aqui.

Eu não tenho nenhuma implementação de um "solver" destes problemas. Mas acho que existem bibliotecas online (caso não pretendas implementar um algoritmo de resolução).

PS: Como só tens 3 variáveis (x2,y2,z2), se calhar arranjas forma mais simples de resolver o problema.

[vasco16]

Isto é um problema de programação linear (a versão inglesa é muito mais completa).

Podes ver alguns slides que falam disto aqui.

Eu não tenho nenhuma implementação de um "solver" destes problemas. Mas acho que existem bibliotecas online (caso não pretendas implementar um algoritmo de resolução).

PS: Como só tens 3 variáveis (x2,y2,z2), se calhar arranjas forma mais simples de resolver o problema.

Onde que sites posso encontrar essas bibliotecas?

Em relação a isto ser um problema de programação linear esses problemas não devolvem só o maximo ou o minimo?

Em relação ao teu "PS" podes dar mais umas luzes de como simplificar?

[mogers]

Onde que sites posso encontrar essas bibliotecas?

Se soubesse tinha colocado o link :x  Acho que pesquisando no google deves encontrar.

Na disciplina onde falamos disto, usamos programas (e não bibliotecas) para resolver este tipo de problemas.

Em relação a isto ser um problema de programação linear esses problemas não devolvem só o maximo ou o minimo?

Sim, minimizar ou maximizar uma função objectivo. Neste caso queres apenas uma solução, pelo que podes escolher uma coisa qualquer (implementando a primeira fase do método simplex a 2 fases ficas logo com uma solução admissível).

Em relação ao teu "PS" podes dar mais umas luzes de como simplificar?

Foi só um palpite, à espera de saber se alguém teria outra ideia porque usar bibliotecas optimizadas para a resolução de problemas com milhares de variáveis e restrições parece um bocado "overkill" para este problema com apenas 3 variáveis e 5 restrições.

[Warrior]

Eu não consegui perceber qual o problema, ou seja, quais as incógnitas.

Se tens os 6 números das linhas e queres calcular (a, b, c), podes simplesmente calcular (x, y, z) e depois (a, b, c).

Agora, isto é básico e evidente, portanto tenho que ter percebido mal qual é o teu input.

[vasco16]

Eu não consegui perceber qual o problema, ou seja, quais as incógnitas.

Se tens os 6 números das linhas e queres calcular (a, b, c), podes simplesmente calcular (x, y, z) e depois (a, b, c).

Agora, isto é básico e evidente, portanto tenho que ter percebido mal qual é o teu input.

Introduzo na primeira linha os numeros:

5 , 4 e 6

depois na segunda meto

0,6 ; 0,75; 0,5

ao fazer os calculos

faço 0,6*5 = 3 ; 0,75*4 =3; 0,5*6=3;

a soma da segunda linha é 0,6 + 0,75 + 0,5 = 1.85

agora com o calculo que fiz á pouco (faço 0,6*5 = 3 ; 0,75*4 =3; 0,5*6=3) vou obter os novos numeros para isso faço 3-1,85 = positivo; 3-1,85 = positivo; 3-1,85 = positivo

Agora se usares outros valores sem sempre dá positivo..

[mogers]

Eu não consegui perceber qual o problema, ou seja, quais as incógnitas.

Se tens os 6 números das linhas e queres calcular (a, b, c), podes simplesmente calcular (x, y, z) e depois (a, b, c).

Agora, isto é básico e evidente, portanto tenho que ter percebido mal qual é o teu input.

Ele não explicou bem o input. Também tive dificuldades em perceber.

Depois mais 3 valores reais positivos superiores a 0,5 que ficarão noutra linha.

Estes valores da 2ª linha não são dados, acho que estas é que são as incognitas.

[vasco16]

Ele não explicou bem o input. Também tive dificuldades em perceber.

Estes valores da 2ª linha não são dados, acho que estas é que são as incognitas.

Exacto os valores da segunda linha são as incógnitas e o meu objectivo é um input dessas incógnitas calculadas com resultado positivo.

[Warrior]

Ah, era difícil perceber isso olhando para o post inicial..

Anyway, este problema em particular não me parece necessitar de programação linear, visto as equações não serem completas.

Acho que esta pode ser uma possível resolução:

Chamemos aos valores da primeira linha respectivamente a1, a2 e a3.

Os da segunda linha, as nossas incógnitas, x1, x2 e x3.

O teu (x, y, z) do post inicial serão então, respectivamente, a1.x1, a2.x2 e a3.x3.

A soma dos valores da segunda linha, x1+x2+x3.

Queres que ak.xk-(x1+x2+x3) <=> ak.xk - x1 - x2 - x3 sejam positivos, mas podemos mudar o problema para ele ser igual a 0.

Ou seja, se resolveres o sistema:

(a1-1).x1 - x2 - x3 = 0

-x1 + (a2-1).x2 - x3 = 0

-x1 - x2 - (a3-1).x3 = 0

Terás os valores das variáveis x1, x2 e x3 que colocam (a, b, c) a 0.

O problema deles serem positivos pode ser resolvido substituindo este sistema de equações por um sistema de inequações.

Julgo que isto seja possível, se for, podes resolver o sistema por eliminação gaussiana por exemplo.

[mogers]

[offtopic]

Warrior, passei-te agora no SPOJ. Toca a treinar!!!  :knuppel2:

[/offtopic]

[Warrior]

[offtopic]

Quarta à tarde já vou reservar uma ou duas horas para ti!

[/offtopic]

[vasco16]

quando faço:

(4,3-1) · x-y-z>0

-x+(2,3-1) · y-z>0

-x-y-(2,4-1) · z>0

Obtenho:

x>(Y/42) + (Z/42) and x<22y-z

Que faço com isto? vou escolhendo valores aleatórios ? :S

[mogers]

A solução do Warrior não funciona porque não garante que as variaveis têm um valor superior a 0.5

[vasco16]

A solução do Warrior não funciona porque não garante que as variaveis têm um valor superior a 0.5

Por outro lado, acho que não se pode usar eliminação gaussiana (pelo menos normal) para resolver um sistema de inequações (e.g. multiplicar uma linha por um valor negativo modificava a inequação de > pa < ou vice-versa). Mas eu não sou grande coisa a algebra.

Será que existe algum um outro metodo? ou o exercicio é simplesmente estupido?

[mogers]

Como disse, aplicando programação linear funciona. Ex:

Variáveis de decisão: 

X, Y, Z : valores da "2ª linha"

Parâmetros:

x1, y1, z1 : valores dados da 1ª linha

Sujeito a:

x1 * X >= X+Y+Z

y1 * Y >= X+Y+Z

z1 * Z >= X+Y+Z

X,Y,Z > 0.5

X,Y,Z <= 10.0

Função objectivo: qualquer. Ex:

min(X+Y+Z)

[Warrior]

A solução do Warrior não funciona porque não garante que as variaveis têm um valor superior a 0.5

Não me lembrei dessa restrição.

Sendo assim, tem-se que usar mesmo programação linear.

Já agora, provavelmente vais querer aplicar este algoritmo (ou encontrar o seu código na net)

http://en.wikipedia.org/wiki/Simplex_algorithm

[vasco16]

Como disse, aplicando programação linear funciona. Ex:

Variáveis de decisão: 

X, Y, Z : valores da "2ª linha"

Parâmetros:

x1, y1, z1 : valores dados da 1ª linha

Sujeito a:

x1 * X >= X+Y+Z

y1 * Y >= X+Y+Z

z1 * Z >= X+Y+Z

X,Y,Z > 0.5

X,Y,Z <= 10.0

Função objectivo: qualquer. Ex:

min(X+Y+Z)

Será que é sempre fiavel? é que nos valores que meto nao encontro intersecção

[mogers]

Eu acho que o problema nem sempre tem solução.

[vasco16]

Eu acho que o problema nem sempre tem solução.

pois eu tambem começo a achar isso.

[mogers]

Mas isso é normal em problemas deste género.