Programação Inteira: Introdução - Variáveis Inteiras e Binárias, Otimização Linear Discreta

a programação inteira a gente tem né diversas classificações aí então um problema de programação inteira ele pode ser uma fronteira pura tá quando todas as variáveis aí de problema Elas têm que assumir valores em por exemplo aqui ó veja o que é bem parecido com problema de programação linear A única diferença para os problemas de programação linear que a gente viu até o momento Essa exigência aqui todos os pontos tem que pertence ao conjunto dos inteiros maiores ou iguais a zero demais aqui veja aqui continua sendo né Minimizar uma função linear e sujeito a restrições

lineares na do tipo menor igual ou maior igualdade tudo de anterior se mantém Ei exceto pelo domínio de X aqui ele tem que ser inteira agora ele não pode ser dois. Nova ele não pode ser 3.7 e tem que ser 1230 qualquer valor Inter e aqui ele está considerando a programação linear inteira aí eu meti o linear aqui o nosso curso já é um curso de otimização linear tá então a gente tá sumido ainda EA constante multiplicando variável tanto na função de tio quanto nas inscrições não tem variável no ano variável continua sendo otimização linear

só que agora amortização linear discreto o domínio pode ser também o programação inteira mista Como assim programação inteira mista tenho dois tipos de variáveis chamei aqui de X eu chamei de o domínio de X continua sendo continua como lá em programação linear a diferença agora é o domínio do Y A Y é uma uma variável agora inteira muitas vezes o pessoal falar tem um ipe tá que tem um militar em que sentido de programa então é a tradução disso pro inglês mas é muito comum e antiga muito comum né Você vai no Congresso pessoa falar

você tem um meio para isso a resolveu e o pessoal tem muita gente que usa até o meio qual o verbo eu vi pisei isso né você já transformei num para nós ficar massa inteira e resolvi mas pode ser também binário O que que é uma programação inteira binária binária quando as variáveis são inteiras Mas você pode assumir o valor o Zé ou não é permitido a se assumir dois três nada disso São só dois valores né E somente esses 20 ou isso daí também é muito usado muito interessante quando você tem né decisões do

tipo sim ou não vai não vai aceitar não seita verdadeiro ou falso esse tipo de decisões são muito importantes que tem um veículo para o veículo visita gente olha uma visita ou ele cruza né um arco Lá Da sua rede ele não uso não tem como metade do veículo por um lado e metade para o outro até tem mas não deveria né um caderno não deveria sugerir isso e amplamente ó tudo isso daí se você misturar tudo você volta por causa da programação inteira mista então missa que eu só coloquei a continua inteira mas pode

ter binária pode ser todas as combinações possíveis aí uma vez que você tem mais um tipo junto aí é programação inteiramente umas incrível aí né rapidinho só para gente ir entender aí para quem ainda não está familiarizado com programação inteira frente voltar lá para mim das ligas metálicas para variar um pouco lembram que lá eu tô em qualquer quantidade de liga agora imagina Mudou as barras não podem ser fracionados Ou seja a gente vai vender melhor a cada uma dessas ligas em Barras é uma que a gente vende em toneladas o cara Ligar Flávio eu

quero 4,6 toneladas né da legal falar e vem agora eu posso vender em barra então eu vendo uma barra de uma tonelada ou duas barras de um lado três barras de lado e assim por diante então eu modifiquei um pouco lembra a gente ver que agora ela é discreta eu não posso vender meia/isso não permite ou vendo uma barra ou Duas Barras ou três barras está ali e se eu só posso vender dessa forma cada só quer produzir dessa forma que mudaria isso do modelo ó quase nada eu continuo tendo a mesma função dos objetivos

as mesmas restrições a antes né para garantir lá eu não vou esse deu o quanto eu tenho estoque mas a multa modificação a única modificação que eu tenho é aqui eu peço que x 1 x 2 sejam na parte da modelagem essa simplesmente fala olha a variável agora inteira tá E aí o sofre aquilo e para fazer esse negócio inteiro e a luta aqui é pesado tá por aqui ó a gente foi lá no ele pessoa por exemplo só como exemplo aqui de um fato que a gente já viu exatamente como a gente fazia antes

a única diferença é eu pedi aqui ó que as variáveis x 1 x 2 seja inteiras Então veja que essa é a única coisa que eu preciso fazer para resolver esse modelo então a dificuldade né o ponto de vista de quem tá usando é muito simples Qual foi a solução que eu consegui aqui X1 = 6 X2 = 0 veja o que é diferente da que eu consegui antes só quem tem a memória boa vai a X1 = 4,62 né Mais ou menos x 2 aproximadamente 2,3 com uma f lá né Desse x ac =

18,40 e seis alguma coisa assim por causa continuo tá eu em caso em que x 1 x 2 memória igual a zero agora que eu pedi por causa inteiro vejo que mudou agora X1 = 6 completamente diferente X2 = 0 a produzir Seis Barras a liga um e nem na barra da liga 2 e qual que é o meu valor ótimo agora do inteiro tava por uma barrinha aqui também de falar isso que eu inteiro agora o valor ótimo é 18 mudou piorou mas obviamente que piorou porque eu tô exigindo mais eu tô restringindo mais

o meu problema agora é produz aí não viu no meu estoque e garante que as quantidades produzidas em termos na cor não ficou mais restrita ou mais apertado eu fiquei mais chato mas exigente e ele consegue uma solução um pouco pior que conseguir antes ela maximizando eu chegava no 18 460l nas de milhar aqui agora eu chego só no 18 mil mas tudo bem ele satisfez a minha exigência que era quantidades interesses não vou poder seis bases liga um nenhuma da liga 2 Se fosse no Excel também é tranquilo a parte da da integralidade entra

de fato como uma restrição eu tenho que colocar aqui eu clico no adicionar quando aparecer essa caixinha eu coloco aqui a célula que estão as minhas variáveis que eu quero que sejam inteiros se ele falar é melhor não nada disso não é uma restrição desse tipo é simplesmente mais estão de domínio quero que ela seja inteiro feito isso ele mesmo já completa aqui no mundo inteiro você dá ok e acabou a ele vai conseguir a solução inteira para você essa é a melhor solução possível para esse problema exigindo variáveis inteiras está exigindo um domínio aí

diz que quer vamos modelar um problema aqui rapidinho só para gente né praticar um pouco é a parte de modelagem de programação inteira e ficar um pouco mais familiarizado aí o empresário está fazendo adiamento dos próximos três anos tá então ele tá fazendo aí né um planejamento no que investir nesse Horizonte aí ele tem disponível 25 milhões para investir ano aumente e cinco projetos a estão sob consideração são esses aqui olha o orçamento de 25 milhões anualmente isso para gestão aqui tabela abaixo apresenta os retornos esperados para cada projeto ao final do terceiro ano e

os em bolsos anuais ele quer determinar quais projetos eles o modo a maximizar seu vetor então se ele optar pelo projeto um é um contrato tá ele já vai deve tar lá da conta dele tem que pagar cinco milhões no ano ou 1 Milhão no ano dois e oito milhões no ano três ele vai ter de retorno e se ele fizer isso tá uma estimativa aí 20 milhões para esse projeto Então esse projeto é um projeto que rende aí 20 milhões desde que ele faz essa fortes aí né esses investimentos anã da veja que aqui

ele tem cinco projetinhos né cara pode ter 520 e não ano 1 ano 2 anos ele pode ter as semanas meses né Ele quer saber né como escolher os melhores projetos Eos melhores investimentos ele não vai poder investir 025 um projeto ou ela investe ou ele não investe no projeto Não tem só eu vou investir só metade kkk não centro de cara nesse projeto ou não talvez é uma decisão 01 precisamos binária Vamos pensar um pouquinho Olha esse problema quais seriam os variáveis de e não e restrições aqui perto vou dar 5 minutinhos para vocês

quebrarem a cabeça é um pouquinho e aí a gente vai fazendo junto eu tenho que decidir ou não né se eu investir no projeto empresário né na verdade investe no projeto como é que a gente pode definir uma variável para ir só uns 15 que queria te dizer uma variável bem lá que ela é um né se o empresário deve investir no projeto ii0 se ele não deve investir se ele foi escolhido lá para o investidor ele é um se ele não foi escolhido ele é zero Stay para cada um dos meus investimentos e é

feito isso agora vamos a gente vai fazer inscrições Eu tenho 25 milhões por ano se você quiser investir em todos os projetos seria excelente se conseguiriam né todos esses retornos aqui não é isso que eu posso né Eu só tenho 25 milhões eu sou mato daqui né aí só esses daqui ó no ano três já deu 28 tem que 31 eu não dá cá um dos anos ou seja no ano no ano dois no ano três eu só vou ter 25 tão tudo que você investir em cada um desses anos Menor igual a 25 anos

um menor igual a 25 anos dois menor igual a 25 no ano então isso daí seria a minha restrição boa num por exemplo quanto que eu em visto lá né se eu tiver escolhido projeto quando que eu vou ter que desenbolsar aí como que eu vou investir nesse projeto mando um pouco melhor no projeto 24 milhões assim por diante então tudo que investir no ano vai ter que ser menor igual do meu orçamento que os meus 25 milhões tenho seu decide a né eu vou investir no projeto um ele desenvolve sim aí eu vou investir

no projeto Dois eu desembolso mais quatro e assim por diante assim eu não eu não invisto no dois e se quiser se você não quiser tá eu não vou gastar a investir num Ah tá bom então você vai gastar 5 e assim por dia a mesma ideia aí a 12 o que eu em visto lá né Em cada um dos meus projetinhos na no ano dois não pode ceder O que eu tenho um ano dois e no ano para eles a mesma e aí a nossa função objetivo eu quero maximizar O Retorno Total o retorno

do projeto é vim milhões retorno do projeto Dois 40 milhões e assim por diante serviço no projeto um e tem esse retorno ele vai ser um aqui serviço no projeto Dois vai virar um eu tenho retorno de 40 a não existe zero eu não tenho retorno referente a Scar E aí contra Olhar todos os retornos para cada um projeto Somos Todos eles e o maximizo isso tô maximizando o meu retorno foi como que fica meu modelinho ou só objetivo linear restrições lineares como sempre e agora X1 X2 X3 X4 X5 binário está pertencentes a ia01

se fosse lá na ele pessoa depois né até legal vocês fazerem esse exercício e lá no ali pessoa tá e vejam que eu teria que colocar só isso vim x 1 x 2 3 4 5 aí coloco que todas as minhas variáveis binárias tá a gente vê lá se fosse inteligente aí assim por diante coloco mais uma linha se tiver como é que ficou essa solução aí eu vou investir em todos os projetos e certo os cinco então o resultado aqui ó A melhor solução que ele encontrou seja solução ótima é 95 aí de valor

ótimo e a investir em todos os projetos exceto no período agora vamos só pensar o seguinte pensa Vou colocar aqui algumas situações independente para gente modelar ela nesse problema usando aí um pouco da programação inteira variáveis binárias daquele está usando aqui imagina aqui né Aparecida seguinte situação o cara não pode investir mais de três projetos ele não consegue ele é muito difícil gente ser mais do que três ele se pede não dá e falaram três projetos o máximo que eu consigo como é que a gente fazia uma restrição para isso agora uma outra exigência independente

dessa não esquece a vão pra Oi gente três deve ser selecionados CO2 portão e seja se você seja no dois tem que ser Nacional três o preço três não pode ser tracionado se quatro também independente da esquece de pega o modelo lá e Agora pensa na ser cada uma dessas aí de família perder mais uma o projeto cinco deve ser selecionado se o 1 ou o 3 foi e o projeto cinco deve ser selecionado se o projeto um e o 3 foi comer que a gente pode fazer restrições aí para colocar naquele modelo original para

garantir cada uma dessas não são todos juntos tá então vou dar aí mais uns minutinhos para vocês a pensar então né Pensa narrar que você teria que colocar lá no modelo para garantir fez isso vai para ver esquece a né faz a ver depois você cada um garoto de forma independente Então peça um pouquinho aí também como fazer cada uma dessas daí né na forma de reflexão tem que ser restrição linear e quando de programação linear inteira tá e não linear usando tá as variáveis que a gente já tem no problema precisa criar variável nova

lá vamos fazer o primeiro aqui então não se pode selecionar mais do que três projeto se a gente tem nessa Celesc que é selecionar ou não projeto é a variável do projeto seu então seu olhar todos os projetos aqui né e tomar essas decisões Artes ou uma x 2 nos determinantes 45 essa soma tem que ser menor igual a três Porque se é a escolha o projeto dois três e quatro como tava lá naquela solução ótimo essa soma daria quatro seja 493 não eu não posso selecionar quatro a Então essa solução já não vai ser

mais a morte fala já in fact Então seja se eu selecionar o projeto é um e essa posta né selecionar três essa soma das variáveis tem que ser no máximo três Então esse daí seria a resposta dá pra colocar no software lá simplesmente a seleção é mais x 1 Manchester não está apenas cinco menor ou igual a três quando eu resolver esse isso falar mesmo são agora é só escolhi o 2 o 3 e os 5 veja que foi uma solução diferente antes não escolheu cinco não era um dois três e quatro agora que eu

exigência de ter né no máximo três os cinco já ficou interessante agora a solução ótima foi dois três e cinco selecionados um retorno aí de 90 tá diminuiu foi de 95 a 97 and Mas o problema fiquei mais chato mas exigente ele não consegue tão longe lá né na direção do Gradiente com mais restrito meu problema EA solução né O valor vai ficar igual ou menor caso aqui mesmo o projeto três deve ser selecionado se o projeto Dois projeto três horas X3 projeto Dois é o x 2 como é que o relacionam essas duas né

decisões aqui que ele tá falando cio projeto Dois for Cuidado para implicação aqui né o 3 o CO2 foi então sio2 por né o três é tão CO2 for ou se ele x 2 é um tem que ser com estes 3 ou também esses dois por 0 x 2 não foram acontece com os três tanto faz ele pode ser como ele também pode ser um porque se esse for esse tem que ser se ele não for não tá falando nada aqui para cuidar de quantificação eu só confunde bastante veja aqui ó u tá sempre né

Se eu tiver um aqui eu implico se eu tiver zero tanto faz tá pode ser sério pode ser um qualquer um dos valores aqui qual que é a relação que eu tô conseguindo ver aqui nitidamente entre essas duas o x 2 tá sempre menor igual que estes 3 como se o sol estivesse empurrando aqui os três então se ele for um ele Force empurra aqui de alguma família fora X três a ser um também então essa decisão né é forte se ela for Ela implica com essa sejam se ela fizer Aos três está livre o

projeto 3 e pode ser selecionado se o projeto quatro for tá agora mudou ele não pode ser selecionados e quatro então assim a gente pensar de novo né eu tenho aqui nos três e tenho aqui um X4 É sempre bom dar esses valores para ajudar a gente a pensar e evitar e que a gente né se engane ela vai fazer restrição se os três não for selecionado o que acontece com os quatro ele pode ser selecionado pode tá então se ele não poderia ser se esse então aqui ó se esse aqui foi selecionado aqui tem

que ser zero esse esse aqui não for selecionar tem alguma implicação no três não esse Pode ser ou pode ser a única explicação né que ele fala é essa primeira aqui mesmo tá Se esse for e se não pode Qual que é a relação aqui vejo que agora a gente já não tem mais um menor igual ou maior igual aqui tão nítido né você fala que você ser menor igual que esses quatro viola aqui e contrário viola por aqui que que eu posso fazer aqui eu vou ter que ir né garantir que seu seleciono né

os e não é possível então x 3 + 4 veja aqui ó a soma aqui ó ela vai dar um nesse caso um nesse caso 10 Então essas uma tem que ser sempre menor igual a Então esse aqui falou esse aqui tem que ser zero não tem outra forma que você não viu a restrição em 60 deixa de três vezes para ele se ele quiser os cinco deve ser selecionado se um ou o 3 foi tá então agora a gente tem uma relação do cinco do projeto né variável lá do projeto cinco com a 1

com a três é um ou aqui se esse tipo selecionado Esse é esse aqui pode se zero pode ser tá agora se esse daqui né for selecionado já está incluído aqui né mas só para ficar separadinho esse aqui pode ser zero pode ser o que for né ele vai ser esse daqui for zero e esse zero esse aqui pode fizeram tem problema tá ele não tá falando que os cinco só pode ser selecionado ser muito senão ele deve ser se ou esse e esse aqui podem selecionar é esse caso aqui como é que a gente

pode garantir essa relação à redação vai ficando um pouco mais diffusa acorda tá então quando tem ou em geral a gente separa Como assim ó uma delas é suficiente para isso acontecer a cox-1 e já foram ele já garanti a restrição Então se utilizam já foram ele já vai implicar que os cinco tem que ser tão a gente só precisa exigir que o X1 não é importante Sim esse estes vão fazer as aqui podes fizeram olhando para o X1 aonde que vem então a parte do UOL o 3 também tem força sobre cinco agora sim

se esfumam ele vai obrigar que estejam Independente de se quiser ele foi vieram É esse aqui pode fizeram se os dois forem 0 X1 X3 X5 continua ali Então nesse caso a gente tem duas restrições aí para garantir essa exigência muito confo X1 mais três menor igual que 25 e esses daqui Se pelo menos um desse Forum né E se nós pegasse aqui seja zero eu vou ter um lado um eu vou ter o lado esquerdo um aqui esse cinco ele tem que ser um porque senão você viu a Maria né seria um menor Guazzelli

não dá então de fato e se os dois forem ainda continua válido porque se soma aqui essa parte da dois duas vezes 5 né vai dar dois ele não pode ser zero Então essa aqui também funciona você consegue fazer uma inscrição só tá para garantir legal e a próxima então ó um projeto cinco deve ser selecionado se o projeto um e o 3 ou em então agora tem que relacionar X1 X3 e este sim se esse daqui foram e esse daqui foram esse tem que ser um Ah mas isso e se for zero e se

for a isso aqui pode ser qualquer coisa pode usar pode ser um Esse aqui foi 10 pode ser qualquer coisa os dois eram pode ser qualquer coisa mas se e esse caso que aconteceu os 21 isso aqui tem que acontecer e detalhe se ele não acontecer você não pode proibir o X1 e assume nenhum valor tem que continuar Ali vai começar esse só pudesse ser válido Quando os dois são quando eles não são aí né o X5 continua ali se eu sou mar esses 2 x 1 + 3 e que vai acontecer né se essas

duas aqui forem um não tem saída para os cinco ele tem que ser um tá porque a soma deu dois a única forma do lado direito Aqui também tá dois é ele sendo um tá ah mas os dois aqui são zero ou pelo menos um é um tudo bem esse unzinho falar para absorver isso e deixar os cinco livros tá então de fatos esse aqui por exemplo a X1 e 03 e 05 pode Cesarão quiser É melhor igual a só x15 pode se quiser veja que isso não seria garantido aqui por isso que eu falei

para vocês essa não dá porque se um aqui já é um você importa o que seja um não pode um só sendo um né esse 160 você tem que deixar o X5 livre e aqui você deixa os cinco livros porque o Joãozinho aqui tá absorvendo aí né esse uma mais um