UNIVERSIDADE DE CAMPINAS - UNICAMP INSTITUTO DE COMPUTAC¸A˜O - IC Introduc¸a˜o a Programac¸a˜o Linear e Inteira Fla´vio Keidi Miyazawa Campinas,2002-2016 Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 1/182 Introduc¸a˜o Programac¸a˜o Linear Programac¸a˜o linear (cid:73) da´ a resoluc¸a˜o exata para muitos problemas (cid:73) da´ a resoluc¸a˜o aproximada para muitos problemas (cid:73) faz parte dos principais me´todos para obter soluc¸o˜es o´timas (cid:73) fazpartedosprincipaisme´todosparaobtersoluc¸o˜esaproximadas (cid:73) da´ excelentes delimitantes para soluc¸o˜es o´timas (cid:73) pode ser executada muito rapidamente (cid:73) ha´ diversos programas livres e comerciais Obs.: Algumas teorias sobre a estrutura dos programas lineares sera˜o apresentadas para se entender os resultados das reduc¸o˜es, mas o foco da aula sera´ nas reduc¸o˜es para Programas Lineares. Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 2/182 Introduc¸a˜o Programac¸a˜o Linear Problema PL: Dados matriz A = (a ) ∈ Qn×m, vetores c = (c) ∈ Qn e ij i b = (b) ∈ Qm, encontrar vetor x = (x) ∈ Qm (se existir) que i i minimize c x +c x +···+c x 1 1 2 2 m m  a x +a x +···+a x ≤ b  11 1 12 2 1m n 1   a21x1+a22x2+···+a2mxn ≥ b2  . . . sujeitoa .. .. ..   an1x1+an2x2+···+anmxn = bn   x ∈ Q i Teorema: PL pode ser resolvido em tempo polinomial. Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 3/182 Introduc¸a˜o Exemplo gra´fico x2 x1+x2≤5 6 x1≤4 5 2x +3x ≤12 1 2 4 3 2 P 1 x ≥0 2 0 1 2 3 4 5 6 x1 −2x −x =−9 1 2 x ≥0 1 −2x −x =−4 minimize −2x −x 1 2  1 2 −2x1−x2=0 x +x ≤ 5  1 2   2x1 +3x2 ≤ 12 Sol. o´tima: x1 = 4 e x2 = 1 sujeitoa x ≤ 4 Valor da sol. o´tima = −9 1  x ≥ 0  1   x ≥ 0 2 Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 4/182 Introduc¸a˜o Teorema: Uma soluc¸a˜o que e´ ve´rtice do PL pode ser encontrada em tempo polinomial. Algoritmos polinomiais para resolver PL: (cid:73) Algoritmo dos elipso´ides (Khachiyan’79) e (cid:73) Me´todo dos pontos interiores (Karmarkar’84). Algoritmos exponenciais para resolver PL: (cid:73) Me´todo simplex (Dantzig’47) (tempo me´dio polinomial). Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 5/182 Introduc¸a˜o Nem sempre encontramos uma soluc¸a˜o o´tima (cid:73) Sistema ilimitado y P x (cid:73) Sistema invia´vel y x+y≥5 −y−x≥−2 x Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 6/182 ResolvedoresdeProgramac¸a˜oLinear Resolvedores de Sistemas Lineares Programas comerciais (cid:73) CPLEX / IBM: www.ilog.com/products/cplex/ (cid:73) XPRESS: www.dashoptimization.com/ (cid:73) GUROBI:: http://www.gurobi.com/ Programas livres (cid:73) SCIP: http://scip.zib.de/ (cid:73) COIN-CLP: www.coin-or.org/Clp/ (cid:73) SoPlex / Zib: www.zib.de/Optimization/Software/Soplex (cid:73) GLPK / Gnu: www.gnu.org/software/glpk/glpk.html (cid:73) LEMON / Coin-OR: http://www.coin-or.org/ Biblioteca de grafos usando solver GLPK ou COIN-CLP Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 7/182 ResolvedoresdeProgramac¸a˜oLinear Trecho de implementac¸a˜o usando LEMON #include <lemon/lp.h> // g++ ex_lp1.cpp -lemon -lglpk -o ex_lp1 using namespace lemon; using namespace std; int main() { Lp lp; / Declarando/criando um LP (inicialmente vazio) Lp::Col x1 = lp.addCol(); // Adicionando duas vari´aveis Lp::Col x2 = lp.addCol(); lp.addRow( x1 + x2 <= 5 ); // Adicionando restric¸˜oes lp.addRow( 2*x1 + 3*x2 <= 12); // Definindo os limitantes superior e inferior de cada vari´avel lp.colLowerBound( x1, 0 ); lp.colUpperBound( x1, 4 ); lp.colLowerBound( x2, 0 ); // Definindo a func¸˜ao objetivo e se de minimizac¸˜ao ou maximizac¸˜ao lp.obj( -2*x1 - x2 ); lp.min(); lp.solve(); // Resolvendo o sistema if (lp.primalType() == Lp::OPTIMAL) {// Imprimindo valor das vari´aveis cout << "Valor da funcao objetivo: " << lp.primal() << endl; cout << "x1 = " << lp.primal(x1) << endl; cout << "x2 = " << lp.primal(x2) << endl; } else {cout << "Nao encontrou solucao otima." << endl;} return 0;} Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 8/182 Exemplos ProblemadaDieta Problema da Dieta Sa˜o dados: (cid:73) m alimentos: ali ,...,ali 1 m (cid:73) n nutrientes: nut ,...,nut 1 n (cid:73) prec¸o p de cada alimento ali j j (cid:73) recomendac¸o˜es dia´rias r de cada nutriente nut , para uma dieta i i balanceada (cid:73) quantidade q do nutriente nut no alimento ali , ij i j Objetivo: Encontrar uma dieta mais barata respeitando as recomendac¸o˜es nutricionais Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 9/182 Exemplos ProblemadaDieta Exemplo: Dieta I Nutrientes, com recomendac¸o˜es dia´rias m´ınima e ma´xima Nutriente m´ınimo ma´xima nut = ca´lcio 800 1200 1 nut = ferro 10 18 2 Alimentos, com prec¸o e composic¸a˜o nutricional: Alimento prec¸o ca´lcio ferro ali = carne de boi (kg) 20.0 110.00 29.00 1 ali = feija˜o cozido (kg) 6.0 170.00 15.00 2 ali = leite desnatado (lt) 2.0 1150.00 0.00 3 Fla´vioKeidiMiyazawa (Unicamp) Introduc¸a˜oaProgramac¸a˜oLineareInteira 10/182