os valores precisam ser inteiros!Uma maneira de chegar a esse resultado e quebrando o problema em dois. Se a sua solucao tem um valor fracionario, como 17.13, entao voce roda o Simplex mais duas vezes: na primeira adicionando a inequacao M17, e na segunda, M18. Se o resultado tiver so variaveis inteiras, beleza, esta resolvido. Senao, voce pega a variavel fracionaria e quebra em dois de novo. Esse metodo na literatura e a Programacao Inteira Mista (ou apenas MIP).Opa! Perai! Os metodos de programacao linear eram polinomiais, e abrindo uma arvore em cada variavel nos transformamos o metodo em exponencial. E uma perda de performance inaceitavel!Pois e, mas nao tem jeito. Embora a programacao linear seja polinomial, a programacao inteira e NP-hard. Se voce achar um metodo polinomial para resolver esse problema, entao voce tambem provou que P=NP.Nem tudo esta perdido, entretanto. Existem varios metodos para otimizar a busca, de modo que voce nao precise visitar todos os nos da arvore. Por exemplo, voce pode usar branch and bound, branch and cut, Gomory cuts, e mais inumeros truques que deixam o numero de nos baixos o suficiente para o metodo ser viavel na pratica.Implementar esses metodos pode ser bem dificil. A boa noticia e que voce nao precisa faze-lo! Existem inumeras bibliotecas prontas que implementam tudo isso para voce, em quase todas as linguagens do mercado. A minha preferida e a SCIP, que e open source e bastante competitiva com as solucoes comerciais. O unico problema dela e que o publico-alvo sao os pesquisadores da area, entao a API e bem complexa e intimidadora para quem esta comecando agora. Se voce quer comecar agora a brincar com MIP, eu tenho uma alternativa melhor.Usando EasySCIPJa que a SCIP e boa, mas e dificil de usar, meu primeiro instinto foi escrever uma abstracao sobre ela que torne a programacao mais simples. E assim surgiu o EasySCIP, um binding em C++ que e facil de usar. Para mostrar como e simples, vamos implementar o problema da dieta em EasySCIP.Primeiro voce cria uma instancia do EasySCIP:MIPSolver solver;Depois, cria as variaveis, uma para cada tipo de alimento. Na criacao da variavel, voce especifica os limites onde ela pode variar (digamos, de 0 a 1000). Alem disso, voce passa o coeficiente dessa variavel na funcao que vai ser minimizada (no nosso caso, e o preco de cada item):Variable corn = solver.integer_variable(0, 1000, 0.08);Variable milk = solver.integer_variable(0, 1000, 0.23);Variable bread = solver.integer_variable(0, 1000, 0.05);Agora voce adiciona as inequacoes (constraints). Para cada inequacao, voce passa o coeficiente da variavel, e os limites inferiores e superiores. No nosso caso, so nos importam os limites inferiores, entao eu chutei um valor alto para o superior. A primeira inequacao fica assim:Constraint calories = solver.constraint();calories.add_variable(corn, 72);calories.add_variable(milk, 121);calories.add_variable(bread, 65);calories.commit(2000, 200000);Na segunda inequacao voce nem precisa adicionar a variavel do pao, porque ele nao tem nenhuma vitamina A.Constraint vitamin_a = solver.constraint();vitamin_a.add_variable(corn, 107);vitamin_a.add_variable(milk, 500);vitamin_a.commit(5000, 500000);Agora e so resolver e ler os valores finais:Solution sol = solver.solve();cout << "Corn: " << sol.value(corn) << "\n";cout << "Milk: " << sol.value(milk) << "\n";cout << "Bread: " << sol.value(bread) << "\n";O