Tcc programação linear

UNIVERSIDADE FEDERAL DE ALAGOAS ´ INSTITUTO DE MATEMATICA

O Problema de Programa¸˜o Linear ca

Autor: Jos´ Lucyan Mendon¸a de Almeida e c Orientador: Prof. Dimas Mart´ ınez Morera

Programa¸˜o Linear ca

Jos´ Lucyan Mendon¸a de Almeida e c

Trabalho de Conclus˜o de Curso a submetido ao Colegiado do Curso de Gradua¸ao em Matem´tica da Universidade c˜ a Federal de Alagoas, como requisito parcial para obten¸ao do t´ c˜ ıtulo de Licenciado em Matem´tica. a

Banca Examinadora:

Prof. Dimas Mart´ ınez Morera

Prof. Ad´n Jos´ Corcho Fern´ndez a e a

Profa . Luana Giarola Contiero

Agradecimentos
` A minha m˜e, pelo apoio incondicional em todos os momentos da minha vida. a ` As minhas irm˜s Luciana Mayara e Lucilayne Mendon¸a, pelos incentivos e momentos a c de alegrias. Ao professor Dimas, pela disposi¸ao, amizade, compreens˜o e paciˆncia durante o c˜ a e per´ ıodo de orienta¸ao. c˜ Aos meus amigos de gradua¸ao, pela convivˆncia ao longo desses quatro anos. c˜ e A todos que, de alguma forma, contribu´ ıram para minha forma¸ao acadˆmica. c˜ e

3

Sum´rio a
1 Introdu¸˜o ca 1.1 O Problema de Programa¸˜o Linear . . . ca 1.2 Problemas Cl´ssicos . . . . . . . . . . . a 1.2.1 O Problema do Caixeiro Viajante 1.2.2 O Problema da Dieta . . . . . . 2 Modelagem 2.1 Modelo de Programa¸˜o Linear . ca 2.2 Formula¸ao . . . . . . . . . . . . c˜ 2.3 Exemplos . . . . . . . . . . . . . 2.3.1 O Problema da Dieta . . . 2.3.2 O Problema do Fazendeiro 2.3.3 O Problema do Hospital . 3 O M´todo Gr´fico e a 3.1 Interpreta¸˜o Geom´trica no R2 : . ca e 3.2 Poss´ ıveis Regi˜es Compat´ o ıveis . . 3.3 Exemplo . . . . . . . . . . . . . . 3.3.1 O Problema do Fazendeiro 5 6 6 6 7 8 8 9 10 10 10 12 15 15 19 22 22 27 27 34 43 44

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . .

. . . . . .

. . . . . .

. . . .