Pesquisa Operacional I – Aula 5 – Ferramentas computaci… — Transcript

[Música] Olá, sejam bem-vindos à segunda semana da disciplina de Pesquisa Operacional. Meu nome é José Roberto. Nós vamos continuar então com a aula C, ferramentas computacionais, SVE Excel e o Lindo. Como objetivo nessa aula, a gente tem entender e implementar os modelos de programação linear e obter a solução ótima nessas ferramentas computacionais, o Lindo. Nossa primeira ferramenta, ela é uma ideia para desenvolvimento e resolução de problemas, entre eles, né, de programação linear, quadrática e inteira. Essa, essa, essa é a interface dele no Windows. Ah, é uma ferramenta que você pode baixar e fazer o uso dela numa versão demo, com uma quantidade razoável de variáveis e restrições no problema, ou senão adquirir a versão completa da empresa. Ah, alguns detalhes que são importantes desse ambiente de programação é que os principais comandos são Max e Min, que se referem à função objetiva do problema. Então, Max quando é de maximização, Min de minimização, e o uso do End ao final, quando você completa o modelo e você quer determinar melhor o domínio de cada uma das variáveis. Então, após o End é feita essa, esse, essa determinação. Ah, os operadores que são utilizados: menor, maior, menor ou igual e maior ou igual. E aqui nós temos, resgatando lá na aula 3S, o problema um, que é a determinação do mix de produção. Lembrem que nós tínhamos lá três modelos de produto, produto A, modelo A, o modelo B e o modelo C. Ah, tínhamos um valor de venda, um valor de lucro, né, que era obtido com a venda desses itens, e eles estavam sujeitos a duas restrições, uma de material e outra quantidade de horas-homem, né, hora-máquina disponível na empresa. Ah, e também as restrições de non negatividade. Bom, como que a gente passa, implementa, né, esse modelo no ambiente do Lindo? O Lindo tem essa facilidade, modelos simples como esse são facilmente implementados. Ah, basta essa parte que eu destaquei em amarelo ser trocada. Então, o Z igual a, a gente despreza ele no Lindo, o sujeito a, como o ambiente foi escrito na linguagem inglesa, então trocamos para Subj. Também poderia se fazer o uso apenas de S, abreviando nas restrições. Notem que aqui a gente usa um único símbolo de maior ou igual, desculpa, de menor ou igual, né, mas poderia ser o de maior ou igual. E quando vamos pro Lindo, nós precisamos fazer o uso do menor e do igual, tá? E as restrições de non negatividade aqui eu não coloquei, há um motivo pelo qual no Lindo é por padrão já são definidos, já é definida a não negatividade, então todas as variáveis são positivas. Dado que já foi implementado, né, já escrevemos o modelo no Lindo, então nós vamos fazer a execução dele. Posso clicar nesse botão ou senão ir até o menu Solve e escolher a opção Solve novamente para execução dele. Então, logo que ele termine a execução, ele vai trazer uma primeira tela com um resumo, pequeno resumo do que aconteceu. Ah, nesse resumo nós temos lá o número de iterações que foram utilizadas para sua resolução de um algoritmo chamado Simplex, que vocês vão começar a ver ele na aula sete. Ah, e também temos aqui o valor da função objetivo, ou seja, o valor de Z, né, ah, qual o valor que nós estávamos otimizando, procurando o melhor lucro, né, o maior lucro para aquela empresa. Então, o maior lucro possível com aqueles parâmetros de entrada seria 100. Fechando essa tela, então o Lindo vai abrir uma outra tela com uma melhor descrição dos resultados, maiores detalhes. Eu fiz um resumo daquela tela, trouxe para cá, e lá nós temos que então, novamente, que a solução ótima foi encontrada com duas iterações, que o valor da função objetivo foi 100, e o valor das variáveis XA e XC, esses dois modelos não haverá produção, havendo produção apenas do produto, do modelo, né, do produto que é XB, que foi de 50 unidades. Esses outros detalhes vocês vão aprender durante as disciplinas, nós vamos ter conteúdos, aulas específicas sobre cada um deles. No problema 2, que também era da aula 3, nós tínhamos lá a seleção de mídia para a propaganda, já era um problema maior, um pouquinho mais complexo, né? E aí a gente vai ver se ele realmente é mais difícil de se resolver ou se às vezes mudando a complexidade do problema em termos de tamanho não altera na sua resolução. Então, vamos ver as principais diferenças. Eu já transportei diretamente para o Lindo o modelo, tá? Então, já fiz a, já já eliminei o Z igual, coloquei Sub 2, né, e notem que até o momento eu não coloquei o End, não fiz o uso do End, não determinei qual o domínio das variáveis. Então, por enquanto, elas são positivas e contínuas, né, porém não negativas por padrão. Ao executar aqui, um outro resumo, né? Então, foi obtida a solução no passo zero. Passo zero significa que, dada a solução inicial, ele já encontrou a solução ótima pro problema. Ok? E o valor da função objetiva. Ah, só que nós temos um problema. Olhando pro valor das variáveis, nós temos lá que X1 era a quantidade de propagandas que seriam realizadas, veiculadas, né, na TV normal, X2 na TV em horário nobre, X3 e X4 em revistas e rádio. Ah, tudo bem com X1, X3 e X4, mas em X2 tá dizendo lá que nós vamos veicular 3.0, uma dízima periódica, né, com seis vezes a propaganda na TV nobre. E aí é um problema, né? Nós precisamos daqui como número inteiro. A questão é, bom, já que temos lá 3, 3.06 me 7, né, por que não arredondar para simplesmente três? Aqui mantemos 10, 10 e 3, né? Bom, antes disso, então vamos, vamos ver se realmente seria só arredondar se esse ainda manteríamos a solução ótima. Vamos tomar alguns cuidados com a sintaxe, já que a gente vai partir para um problema inteiro, né? As variáveis assumem valores inteiros, então algumas restrições com relação ao domínio vão aparecer, como eu já havia comentado, depois da palavra reservada End, que vem ao final do modelo. Então, lá nós podemos colocar Int e o nome da variável, se o domínio for de números inteiros binários, 0 ou 1, se forem, se for um número inteiro, mas inteiro positivo, né, então a gente coloca o Gin de General Integer. E se quisermos que eles possam assumir valores negativos, né, então fazemos uso do Free, que vai permitir então que as variáveis sejam livres, né, possam assumir valor negativo ou positivo. E aí a implementação muda quase nada, na verdade. A gente manteve a mesma implementação até a linha X4 menor ou igual a 10, né, que era todo o modelo. Foi colocada então a palavra reservada End e, após ela, Gin 4. Notem que no slide anterior eu coloco Gin e o nome da variável, mas aqui eu coloquei Gin 4. Então, eu poderia ter colocado Gin X1, depois na linha de baixo Gin X2, Gin X3 e Gin X4. Então, tenho quatro variáveis, coloquei Gin 4, ele vai entender, Lindo vai ser capaz de entender que são as quatro variáveis que eu tenho no problema que devem ser do tipo General Integer. Ok? Bom, pedindo para resolver aqui, vai dado, é dado um resumo. Notem que na solução anterior, com as variáveis relaxadas, nós encontramos na solução dada inicialmente já a solução ótima, né? Encontramos a solução ótima já na solução dada, na solução inicial. E agora, somente na iteração de número 35 é que conseguimos encontrar a solução ótima do problema. E notem como a solução ótima mudou, né? Tudo bem, mantemos para X3 e X4 10 veiculações em cada uma dessas mídias, porém em X1, que era o número de veiculações na TV normal de três, aumentou para quatro. Em X2, que é no horário nobre, de 3.0666, né, caiu para apenas duas. Então, o problema inteiro, a diferença dele pro relaxado é que a gente não pode simplesmente considerar que um arredondamento vai manter você com a solução ótima. Uma forma de perceber isso também é olhando pro valor da função objetivo. Aqui a gente tem o 108, na outra solução nós tínhamos 100, 96. Então, quer dizer, da solução relaxada pra solução inteira também houve uma diferença no valor da função objetiva. O que é importante perceber também nesse momento, quando você sai de uma solução relaxada e vai para uma solução com domínio das variáveis sendo inteiro, é que você nunca vai melhorar o valor da função objetivo. Por quê? Nessa solução, as restrições, elas vão ser, pelo menos uma das restrições, ela vai ser aproveitada ao máximo, ou seja, todo o recurso que eu tenho do lado direi...

modelos de programação linear e obter a solução ótima nessas ferramentas computacionais o lindo nossa primeira ferramenta ela é uma ideia para desenvolvimento e resolução de problemas entre eles né de programação linear quadrática e inteira essa essa essa é a a interface

dele no Windows Ah é uma ferramenta que você pode baixar e fazer o uso dela numa versão demo eh com uma quantidade razoável de variáveis e restrições no problema ou sen não adquirir a versão completa da empresa ah alguns detalhes que importantes dessa

desse ambiente de programação é que os principais comandos são Maxim min que se refere à função objetiva do problema então Max quando é de maximização min de minimização e o uso do end ao final quando você completa o modelo

eh e você quer determinar melhor o domínio de cada uma das variáveis então após o end é feita essa esse essa determinação ah os operadores que são utilizados menor maior menor ou igual e maior ou igual e Aqui nós temos resgatando lá na aula

3S o problema um que é a determinação do mix de produção lembrem Que nós tínhamos lá três modelos de produto produto a modelo a o modelo b e o modelo C ah tínhamos um valor de venda um valor

de lucro né que era obtido com a venda desses itens e eles estavam sujeitos a duas restrições uma de material e outra quantidade de horas homem né hora máquina disponível na empresa ah e também as restrições de non

negatividade bom como que a gente passa implementa né Esse modelo no no ambiente do lindo o Lindo tem essa facilidade modelos simples como esse são facilmente implementados ah basta essa parte que eu destaquei em amarelo ser trocado então o z igual a

gente despreza ele no lindo o sujeito a como o ambiente foi escrito na linguagem inglesa então trocamos para subc também poderia se fazer o uso apenas de S abreviando nas restrições notem que aqui a gente usa um único símbolo de maior ou

igual desculpa de menor ou igual né mas poderia ser o de maior ou igual e quando vamos pro lindo nós precisamos fazer o uso do menor e do igual tá e as restrições de non negatividade aqui eu não coloquei há um motivo pelo

qual no lindo é por padrão já são definidos já é definida a não negatividade então todas as variáveis são positivas dado que já foi implementado né já escrevemos o modelo no lindo então nós vamos fazer a execução dele posso

clicar nesse botão ou senão ir até o menu solve e escolher a opção solve novamente PR execução dele então logo ele termine a execução ele vai trazer uma primeira tela com um resumo pequeno resumo do que aconteceu Ah nesse resumo

nós temos lá o número de iterações que foram utilizadas para sua resolução de um algoritmo chamado Simplex que vocês vão começar a ver ele na aula sete Ah E também temos aqui o valor da função objetivo ou seja o valor de Z né ah qual

o qual o valor que nós estávamos otimizando procurando o melhor lucro né o maior lucro para aquela empresa então o maior lucro possível com aqueles parâmetros de entrada seria 100 fechando essa tela então o lindo vai abrir uma outra tela com uma melhor

descrição dos resultados maiores detalhes eu fiz um resumo daquela tela trouxe para cá e lá nós temos que então novamente que a solução ótima foi encontrada com duas iterações que o valor da função objetivo foi 100 e o valor das variáveis xa e

XC esses dois modelos não haverá produção havendo produção apenas do produto do modelo né do produto que é XB que foi de 50 unidades esses outros detalhes vocês vão aprender durante as disciplinas nós vamos ter conteúdos aulas específicas

sobre cada um deles no problema 2 que também era da aula 3 nós tínhamos lá a seleção de mídia para a propaganda já era um problema maior um pouquinho mais complexo né E aí a gente vai ver se ele realmente é mais difícil

de se resolver ou se às vezes mudando a complexidade do problema em termos de tamanho não altera na sua resolução Então vamos ver as principais diferenças eu já transportei diretamente ente pro lindo o modelo tá então já fiz a já já

eliminei o z igual coloquei sub 2 né e notem que até o momento eu não coloquei o end não fiz o uso do end não determinei Qual o domínio das variáveis Então por enquanto elas são positivas e contínuas

né porém não negativas por padrão ao executar aqui um outro resumo né em então ele foi obtida a solução no Passo zero passo zer zero significa que dada a solução Inicial ele já encontrou a solução ótima pro problema Ok e o

valor da função objetiva Ah só que nós temos um problema olhando pro valor das variáveis nós temos lá que X1 era a quantidade de propagandas que seriam realizadas veiculadas né na TV normal X2 na TV em horário nobre X3 e X4 er em

revistas e rádio Ah tudo bem com X1 X3 e X4 mas em X2 tá dizendo lá que nós vamos veicular 3.0 uma dízima periódica né com seis eh vezes a propaganda na TV Nobre E aí é um problema né Nós precisamos daqui como

número inteiro a questão é bom já que temos lá 3 3.06 me 7 né Por que não arredondar para simplesmente TR aqui mantemos 10 10 e 3 né bom antes disso então vamos vamos ver se realmente seria só arredondar se esse

ainda manteríamos a solução ótima Vamos tomar alguns cuidados com a sintaxe já que a gente vai partir para um problema inteiro né as variáveis assumem valores inteiros então algumas restrições com relação ao domínio vão aparecer como eu já havia comentado

depois da palavra reservada end que vem ao final do modelo então lá nós podemos colocar int e o nome da variável se o domínio for de números inteiros binários 0 ou 1 se forem se for um número inteiro

mas inteiro positivo né então a gente coloca o Gin de general integer e Se quisermos que eles possam assumir valores negativos né então fazemos uso do free que vai permitir então que as variáveis sejam Livres né possam assumir

valor negativo ou positivo e aí implementação muda quase nada na verdade a gente Manteve a mesma implementação até a linha X4 menor ou igual a 10 né que era todo o modelo foi colocada então a palavra reservada a end e após ela Gin

4 notem que a no slide anterior eu coloco Gin e o nome da variável mas aqui eu coloquei Jin 4 então eu poderia ter colocado Gin X1 depois na linha de baixo Gin X2 Gin X3 e Gin X4 então tenho quatro variáveis coloquei

Gin 4 ele vai entender lindo vai ser capaz de entender que são as quatro variáveis que eu tenho no problema que devem ser do tipo General integer Ok bom pedindo para resolver aqui vai dado é dado um resumo notem que na solução anterior com

as variáveis relaxadas nós encontramos na solução dada inicialmente já a solução ótima né encontramos a solução ótima já na solução dada na solução Inicial e agora somente no Passo na iteração de número 35 é que conseguimos encontrar a solução

ótima do problema e notem como a solução ótima mudou né tudo bem mantemos para X3 e X4 10 veiculações em cada uma dessas mídias porém e X1 que era o número de veiculações na TV normal de três aumentou para CCO em

X2 que é no horário nobre de 3 3.0 666 né caiu para apenas duas então o problema inteiro eh a diferença dele pro relaxado é a gente não pode simplesmente considerar que um arredondamento vai manter você com a solução ótima uma forma de

perceber isso também é olhando pro valor da função objetivo aqui a gente tem o 108 na outra solução nós tínhamos 1000 né 96 então quer dizer eh da solução relaxada pra solução inteira também houve um uma diferença no

valor da função objetiva o que que é importante perceber também nesse momento quando você sai de uma solução relaxada e vai para uma solução com Domínio das variáveis send inteiro e você nunca vai melhorar o valor da função objetivo por

quê nessa solução as restrições elas vão ser pelo menos uma das restrições ela vai ser aproveitada ao máximo ou seja todo o recurso que eu tenho do lado direito ele vai ser aproveitado em pelo menos uma das restrições tá porque eu posso

relaxar as variáveis de forma tal que essa soma aqui seja exatamente igual a esta Tá ok já quando as variáveis são inteiras eu não tenho garantia disso acontecer em nenhuma das restrições né porque eu tenho uma multiplicação depois

eu vou fazer a soma e pode ser que não encaixe exatamente Então pode sobrar algum recurso em todas as restrições do problema tá então eu não consigo alcançar o mesmo valor de solução ótima de uma solução relaxada né Se eu estiver

na inteira não consigo melhor o máxximo que a gente pode conseguir é uma solução tão boa quanto bom ainda alguns cuidados com a sintaxe o lindo como eu comentei ele é bastante simples de trabalhar quando você está trabalhando com modelos

bastante simples a partir do momento que você tem um modelo um pouco maior ele começa a ficar um pouco mais complexo vai ficando um pouco mais difícil de trabalhar por exemplo não é possível fazer o uso dos parênteses para fazer um

indicador de preferência na hora de fazer a resolução matemática Então você sempre vai trabalhar eh colocando resolvendo da esquerda para a direita né então é preciso manipular a função no lado direito das restrições utilizam-se apenas constantes ou seja

valores numéricos né Eh no lado esquerdo das restrições somente variáveis e o coeficiente da variável tá você não vai poder usar uma constante livre tem que ser sempre um valor multiplicando uma variável ah lá no problema lá na aula 4ro nós

tínhamos um problema de treinamento né E esse problema de Treinamento também precisaria de uma solução inteira ã Esse era o modelo que nós resolvemos né resolvendo o exercício chegamos nesse modelo então lembrem lá que nesse problema era questão da empresa fazer um

treinamento né de profissionais entravam trinis seus seus funcionários davam treinamento para esses treis de A cada 10 treis sete eram aproveitados pro próximo mês que viravam trabalhadores na empresa então começava lá em janeiro fevereiro março e Abril eu fiz uma inclusão de uma nova variável

uma X7 aqui que seria a quantidade de funcionários ociosos ao final do último mês que é Abril tá isso só para demonstrar melhor como ficaria a implementação no lindo E aí qual a diferença de custo envolvida né então

pro lindo mantém-se praticamente a mesma coisa a mesma implementação porém esses 315.000 que era o quanto estava custando os funcionários que estavam trabalhando em máquina ao longo dos 4 meses nós vamos tirar no lindo tá simples esse valor ele é fixado ele é

conhecido já foi determinado na sua entrada não há necessidade de nós fazermos a inclusão dele ou o cálculo dele na função objetiva lembrem que o número de interações ele pode ser pequeno ou muito grande a gente viu lá

um problema sendo resolvido com com zero com duas ou com 35 iterações Mas dependendo da complexidade do problema isso aumenta muito vai para muito mais do que 1000 iterações imagina então cada iteração dessa você ter que fazer essa soma n vezes né

desnecessário então você pode economizar tira ela daqui e ao final depois da execução é um valor fixo você soma no valor de Z Tá ok então no lindo você não conseguiria também colocar esse 315.000 dessa forma tá ela sempre estaria

precisa multiplicar uma variável então a função objetiva tem essa exigência sempre você associa um valor do o coeficiente da variável né a variável não pode deixar ele isolada Ok bom então sujeito às mesmas restrições com a inclusão lembrando lá do X7 né Ah e eu

fiz apenas algumas modificações essas essas duas linhas elas não existiam lá na nos slides da aula 4 então eu só completei elas elas já estavam começadas né então Esso daqui é o nosso entendimento de como o modelo deve ficar

mas na hora da implementação no lindo eu preciso fazer uma transformação Agora usando solw Excel né o Solare é um complemento do Microsoft Excel então na sua no seu na sua máquina você tem uma Microsoft Office tendo o

Excel você pode começar a fazer a resolver os nossos problemas de pesquisa operacional por meio do solver né pode-se maximizar Minimizar ou definir um valor alvo a ser atingido tá nós vamos ter uma aula só para comentar sobre esse tipo de estratégia que seria

a programação por metas né por ser um suplemento é preciso carregá-lo no Excel então só lá em arquivo né suplementos suplementos do Excel clique em ir e seleciona S dá um ok né E aí ele vai aparecer lá na abinha de

dados na guia análise bom como lançar os dados na planilha a forma como você vai colocar o layout na tela isso diferente né algum dependendo do autor vai fazer de uma maneira diferente de outro né Mas o que

importa é colocar as funções e as restrições corretamente então voltando no modelo nós temos lá função objetivo que é Minimizar Z 4700 X1 até né mais 3000 315.000 mas não vamos utilizar o 315.000 então aqui no s colocamos

novamente a função né e na célula E aí Vamos definir as restrições as restrições a gente tem lá janeiro fevereiro março e Abril né as variáveis de X1 até X7 né e o lado B que é qual o valor que máximo né valor teto

que deve ser alcançado então nós temos lá na primeira restrição 1 X1 + 1 X2 né Igual a 30 em fevereiro 7 X1 - X3 - X4 né Igual 20 e assim por diante eu preciso determinar essas restrições dentro do solver né então em

cada uma dessas células eu vou representar o que são exatamente essas restrições que eu coloquei aqui para visualizar então o conteúdo da célula k12 por exemplo né que é da primeira restrição em janeiro C1 + C2 que são os

números das células então aqui eu tenho todas as variáveis de X1 até 7 e aqui os valores que as variáveis assumem então C1 valor da variável X1 Tá ok então representa aquelas restrições nas variáveis k12 a nas células de k12 a

k15 vou clicar lá em solver vai abrir essa tela para mim na nessa nesse Campo definir objetivo a ao clicar eu posso selecionar a função a célula B9 né que é da função objetivo vou determinar que ela é de

minimização e aqui alterando as células variáveis eu cli nesse botão e seleciono desde C1 até C7 que são os valores das variáveis que vão ser apresentados aqui ao final da execução dele e aí eu preciso incluir as restrições Então como que eu vou fazer

essa tela esse quadro primeiro aparece em branco né não há nenhuma restrição lá clico em adicionar E aí eu seleciono cada uma dessas células né E nessa uma uma por vez Então eu vou incluindo as restrições no problema

e notem que precisamos colocar uma restrição de número inteiro então todas as variáveis devem ser inteiras então ao clicar em adicionar aparece essa tela toda vez né então a referência de células eu seleciono de C1 até C7 até C7 e a restrição é que são de

números inteiros ah após vai aparecer essa tela dizendo se o modelo foi resolvido ou não Então nesse caso foi resolvido dentro de todas as restrições Vamos só selecionar manter a solução do solver e pedir para gerar um relatório

de resposta né parecido com o que o lindo fez clico em Ok então essa tela é atualizada e notem lá que como resultado nós temos que X1 vai valer 4 X2 26 X3 7 X4 1 X5 7 X6 é 0 e X7 6 tá valor da

função objetivo 101.100 e então clicamos no relatório de resposta e Aqui nós temos um resumo da resolução do problema é isso pessoal obrigado pela assistir a nossa quinta aula aguardo vocês na sexta aula até mais [Música] [Música]