Tópicos Complementares_ Múltiplos objetivos, Programação dinâmica e Não linear

Prévia do material em texto

Tópicos Complementares: Múltiplos 
objetivos, Programação dinâmica e Não 
linear
APRESENTAÇÃO
Uma etapa fundamental na formulação de um modelo de pesquisa operacional (PO) é a 
construção da função objetivo. É nesse sentido que o responsável pelas decisões desenvolve 
uma medida quantitativa de desempenho para cada um dos objetivos finais, que são 
identificados durante a definição do problema.
Nesta Unidade de Aprendizagem, você vai conhecer os conceitos básicos de problemas com 
múltiplos objetivos e as características principais das programações dinâmica e não linear. 
Bons estudos.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Definir solução de problemas considerando múltiplos objetivos.•
Descrever as características e os problemas de uma programação dinâmica.•
Identificar problemas de uma programação não linear.•
DESAFIO
Você tem um restaurante e foi contratado por uma empresa para entregar o almoço de 30 
funcionários, de segunda a sexta, em outra cidade. O almoço deve chegar ainda quente até as 
12h. A rede apresenta as possíveis rotas entre a cidade de origem no nó 1 e a cidade de destino 
no nó 7. As rotas passam por cidades intermediárias, dos nós 2 ao 6.
Com o objetivo de economizar combustível, você deve definir três estágios e a rota mais curta 
entre as cidades 1 e 7, conforme a rede mostrada na imagem a seguir.
INFOGRÁFICO
A definição de programação dinâmica (PD) é um tanto quanto abstrata, necessitando muitas 
vezes de um exemplo prático para a sua melhor compreensão. Entretanto, algumas 
características são importantes na aplicação desse método e auxiliarão na resolução de 
problemas. Veja no infográfico a sequência dessas características.
Conteúdo interativo disponível na plataforma de ensino!
 
CONTEÚDO DO LIVRO
No capítulo Tópicos Complementares, do livro "Pesquisa Operacional", você verá os conceitos 
básicos de problemas com múltiplos objetivos e as características principais das programações 
dinâmica e não linear.
Boa leitura!
PESQUISA
OPERACIONAL
Organizador: 
Rodrigo Rodrigues
Tópicos complementares: 
múltiplos objetivos, 
programação dinâmica 
e não linear
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Definir solução de problemas considerando múltiplos objetivos.
 � Descrever as características e os problemas de uma programação
dinâmica.
 � Identificar problemas de uma programação não linear.
Introdução
Uma etapa fundamental na formulação de um modelo de pesquisa 
operacional (PO) é a construção da função objetivo. É nesse sentido que 
o responsável pelas decisões desenvolve uma medida quantitativa de
desempenho para cada um dos objetivos finais, que são identificados
durante a definição do problema.
Neste texto, você vai conhecer os conceitos básicos de problemas 
com múltiplos objetivos e as características principais das programações 
dinâmica e não linear. 
Solução de problemas considerando 
múltiplos objetivos
A maioria dos modelos estudados é baseada na otimização de uma única função 
objetivo. Há situações em que múltiplos objetivos (conflitantes) podem ser 
mais adequados. Por exemplo, políticos prometem reduzir a dívida nacional 
e, ao mesmo tempo, oferecem redução da carga tributária. Em tais situações, 
é impossível achar uma solução única que otimize essas duas metas confli-
tantes. A programação de metas é o meio pelo qual se busca uma solução de 
compromisso baseada na importância relativa de cada objetivo.
Como podemos otimizar um modelo multiobjetivos com metas possivel-
mente conflitantes? Dois métodos foram desenvolvidos para essa finalidade: 
o método de pesos e o método hierárquico. Ambos os métodos são baseados 
na conversão de múltiplos objetivos em uma única função.
O método de pesos forma uma única função objetivo que consista na soma 
ponderada das metas. Já o método hierárquico otimiza as metas uma por 
vez, começando com a meta de prioridade mais alta e terminando com a de 
prioridade mais baixa, sem nunca degradar a qualidade da meta de prioridade 
mais alta. A solução dada pelo método de pesos nada mais é do que uma 
programação linear comum. O método hierárquico acarreta em considerações 
“adicionais” em relação ao algoritmo que se enquadram muito bem no domínio 
do método simplex (TAHA, 2008).
Programação dinâmica
A programação dinâmica (PD) é um método matemático útil para uma sequên-
cia de tomadas de decisão inter-relacionadas. Ela apresenta um procedimento 
sistemático para determinar a combinação de decisões ótimas. Diferentemente 
da programação linear, não há uma formulação matemática padrão para um 
problema de programação dinâmica. Pelo contrário, a programação dinâmica 
é um tipo genérico de metodologia para a resolução de problemas e, para cada 
situação, são desenvolvidas equações particulares. Por isso, segundo Hillier 
e Liebermann (2013), é necessário certo grau de engenhosidade e de insight 
na estrutura geral dos problemas de programação dinâmica para reconhecer 
quando e como um problema pode ser resolvido pelos procedimentos dessa 
mesma programação. 
A PD é utilizada como método para realizar uma sequência de decisões 
inter-relacionadas. Ela exige a formulação de uma relação recursiva apropriada 
para cada problema individual. Contudo, ela resulta em grandes economias 
em termos de processamento em comparação com o emprego de enumeração 
exaustiva para encontrar a melhor combinação de decisões, principalmente 
para problemas de grande porte. Como exemplo, supomos que um problema 
possui 10 estágios, com 10 estados e 10 decisões possíveis a cada estágio, então, 
a enumeração exaustiva deve considerar até 10 bilhões de combinações, ao 
passo que a programação dinâmica precisaria fazer não mais que um milhar 
Pesquisa operacional108
de cálculos (10 para cada estado a cada estágio). Consideramos apenas a 
programação dinâmica com um número finito de estágios. 
Essa programação determina a solução ótima de um problema de multiva-
riáveis decompondo-o em estágios, sendo que cada estágio compreende um 
subproblema com uma única variável. A vantagem da decomposição é que o 
processo de otimização em cada estágio envolve uma só variável, uma tarefa 
mais simples com relação ao cálculo do que lidar com todas as variáveis ao 
mesmo tempo. Um modelo de PD é basicamente uma equação recursiva que une 
os diferentes estágios do problema de modo que garanta que a solução ótima 
viável de cada estágio também seja ótima e viável para o problema inteiro.
Segundo Taha (2008), os cálculos em PD são feitos recursivamente, de 
modo que a solução ótima de um subproblema é usada como dado de entrada 
para o subproblema seguinte. Quando o último subproblema é resolvido, a 
solução ótima para o problema inteiro está à mão. A maneira como os cálculos 
recursivos são executados depende de como o problema original é decom-
posto. Particularmente, os subproblemas em geral estão ligados por restrições 
em comum. À medida que passamos de um subproblema para o seguinte, a 
viabilidade dessas restrições em comum deve ser mantida.
Programação não linear
Em pesquisa operacional (PO), o papel fundamental da programação linear é 
refletido de forma aprimorada. Uma suposição central da programação linear 
é que todas as suas funções (função objetivo e funções de restrição) sejam 
lineares. Mesmo que essa hipótese seja válida para vários problemas práticos, 
com frequência ela não se verifica. Então, muitas vezes é necessário lidar 
diretamente com problemas de programação não linear. 
De um modo geral, o problema de programação não linear é encontrar x 
= (x1, x2, . . . , xn) de modo a:
maximizar f(x),
sujeito a: 
gi(x)≤ bi, para i = 1, 2, ..., m, 
e
x ≥ 0,
em que f (x) e os gi (x) sejam funções dadas das n variáveis de decisão. 
109Tópicos complementares: múltiplos objetivos, programação dinâmica e não linear
Existem diversos tipos de problemas de programação não linear, deacordo 
com as características das funções f(x) e gi(x). São usados diferentes algorit-
mos para os diversos tipos. Para determinados tipos em que as funções têm 
formas simples, os problemas podem ser resolvidos de modo relativamente 
eficiente. Para outros, porém, até mesmo a resolução de problemas pequenos 
é um verdadeiro desafio (HILLIER; LIEBERMANN, 2013). 
Devido à existência de muitos tipos e de muitos algoritmos, a programação não linear é 
um assunto particularmente extenso, contudo, abordaremos de forma reduzida. Desse 
modo, é importante um estudo complementar. Veja as indicações no final deste texto. 
Tipos de problema de programação não linear 
Existem diferentes formas e formatos de problemas de programação não 
linear. Ao contrário do método simplex para programação linear, não há um 
algoritmo único capaz de resolver todos esses tipos variados de problemas. 
Ao contrário disso, foram desenvolvidos algoritmos para várias classes (tipos 
especiais) individuais de problemas de programação não linear. As classes 
mais importantes são apresentadas brevemente neste texto. Para simplificar, 
partiremos do pressuposto de que os problemas foram formulados (ou refor-
mulados) na forma genérica da qual já falamos. 
Otimização irrestrita
Os problemas de otimização irrestrita são aqueles que não apresentam restri-
ções, de modo que o objetivo seja simplesmente 
maximizar f(x)
ao longo de todos os valores de x = (x1, x2, . . . , xn). 
Pesquisa operacional110
A condição necessária para que determinada solução x = x* seja ótima 
quando f(x) for uma função diferenciável é que 
A condição de f(x) ser uma função côncava, também é suficiente, de modo 
que encontrar a solução para x* limita-se a resolver o sistema de n equações 
obtidas configurando-se as n derivadas parciais iguais a zero. Infelizmente, 
para funções f(x) não lineares, essas equações muitas vezes também serão 
não lineares. Nesse caso, dificilmente você será capaz de encontrar analiti-
camente sua solução simultânea. Muitos algoritmos para problemas restritos 
são modelados de forma que sejam capazes de se concentrar em uma versão 
irrestrita do problema durante parte de cada iteração. Quando uma variável xj 
não apresentar uma restrição de não negatividade xj = 0, a condição precedente 
necessária e (quem sabe) suficiente muda rapidamente para 
∂
∂
≤ =
= =



f
xj
em x x se xj
em x x se xj
 0 *, * = 0
0 *, * > 0
para cada j deste. Essa condição é ilustrada na Figura 1, em que a solução 
ótima para um problema com uma única variável encontra-se em x = 0, embora 
a derivada ali seja negativa em vez de zero. Como esse exemplo tem uma função 
côncava a ser maximizada, sujeita a uma restrição de não negatividade, ter a 
derivada menor ou igual a 0 em x = 0 é uma condição tanto necessária quanto 
suficiente para x = 0 ser ótima. 
A Figura 1 é um exemplo que ilustra como uma solução ótima pode estar 
em um ponto em que uma derivada é negativa em vez de zero, pois esse ponto 
recai sobre o contorno de uma restrição de não negatividade.
111Tópicos complementares: múltiplos objetivos, programação dinâmica e não linear
Figura 1. Condição de f (x) sendo uma função côncava, com uma ótima solução e em 
derivada negativa.
Fonte: Hillier e Liebermann (2013).
A próxima classe de problemas é dedicada aos problemas que têm algumas 
restrições de não negatividade, mas nenhuma restrição funcional. São um 
caso especial (m = 0). 
Otimização linearmente restrita 
De acordo com Hillier e Liebermann (2013), as características de problemas de 
otimização linearmente restrita são restrições que se ajustam completamente 
à programação linear, de modo que todas as funções de restrição gi(x) sejam 
lineares, mas com a função objetivo f(x) não linear. O problema é conside-
ravelmente simplificado tendo apenas uma função não linear para levar em 
conta, junto com uma região de soluções viáveis de programação linear. Foi 
desenvolvida uma série de algoritmos especiais com base na extensão do 
método simplex para considerar a função objetivo não linear. 
Pesquisa operacional112
Programação quadrática 
A programação quadrática é um importante caso especial. Os problemas de 
programação quadrática também possuem restrições lineares, porém, agora 
a função objetivo f(x) deve ser quadrática. Com isso, a única diferença entre 
um problema desses e um problema de programação linear é que alguns dos 
termos na função objetivo envolvem o quadrado de uma variável básica ou o 
produto de duas variáveis. 
Foram desenvolvidos diversos algoritmos para esse caso sob a hipótese 
adicional de que f(x) seja uma função côncava.
 A programação quadrática é muito importante, devido a essas formulações 
que surgem naturalmente em diversas aplicações e porque uma metodologia 
comum para solucionar problemas de otimização genéricos linearmente res-
tritos é resolver uma sequência de aproximações de programação quadrática. 
Programação convexa 
A programação convexa abrange uma ampla gama de problemas que, na 
realidade, engloba como casos especiais todos os tipos precedentes quando 
f(x) é uma função côncava a ser maximizada. Continuando a supor a forma 
de problema genérico (inclusive a maximização) apresentado no início do 
texto, as hipóteses são de que: 
1. f(x) seja uma função côncava;
2. cada gi(x) seja a função convexa.
Essas hipóteses são suficientes para garantir que um máximo local seja 
um máximo global. Caso o objetivo fosse minimizar f(x), sujeito a gi(x) ≤ bi, 
ou então - gi(x)≤bi para i = 1, 2, . . . , m, a primeira hipótese seria fazer uma 
alteração para que f(x) fosse uma função convexa, visto que isso é o neces-
sário para garantir que um mínimo local seja um mínimo global (HILLIER; 
LIEBERMANN, 2013).
Há ainda a programação separável, que é um caso especial de programação 
convexa, em que a única hipótese adicional é: 
3. Todas as funções f(x) e gi(x) sejam funções separáveis. 
113Tópicos complementares: múltiplos objetivos, programação dinâmica e não linear
Uma função separável é uma função na qual cada termo envolve apenas 
uma única variável, assim, a função torna-se separável em uma soma de 
funções de variáveis individuais. Se f(x) for uma função separável, ela pode 
ser expressa, por exemplo:
Em que cada função fj(xj) inclui apenas os termos que envolvem apenas xj. 
Na terminologia da programação linear, problemas de programação separável 
atendem à hipótese da aditividade, mas, quando qualquer uma das funções 
fj(xj) for não linear, violam a hipótese da proporcionalidade. 
É uma função separável, pois ela pode ser expressa como:
f(x1, x2) = f1 (x1) + f2 (x2)
Na qual f1(x1) = 126x1 - 9x
2
2 e f2(x2) = 182x2 - 13x
2
2 são cada uma delas uma 
função de uma única variável - x1 e x2, respectivamente. 
É importante distinguir problemas de programação separável de outros de 
programação convexa, pois qualquer um desses problemas pode ser aproximado 
por um problema de programação linear de modo que o eficiente método 
simplex possa ser utilizado. 
Programação não convexa 
A programação não convexa engloba todos os problemas de programação não 
linear que não atendem às hipóteses da programação convexa. Então, mesmo 
que você consiga encontrar um máximo local, não há nenhuma garantia de que 
ele também seja um máximo global. Portanto, não existe um algoritmo que 
encontrará uma solução ótima para todos esses tipos de problema. Entretanto, 
não existe um algoritmo que seja relativamente adequado para explorar várias 
partes da região de soluções viáveis e, talvez, encontrar um máximo global 
no processo. 
Pesquisa operacional114
Certos tipos específicos de problemas de programação não convexa podem 
ser resolvidos sem grandes dificuldades por métodos especiais. Dois desses 
tipos particularmente importantes são discutidos a seguir de forma breve.
Programação geométrica 
Ao aplicar a programação não linear a problemas de desenvolvimento de 
engenharia, bem como a certos problemas econômicos e de estatística,a 
função objetivo e as funções de restrição assumem frequentemente essa forma:
Nesses casos, ci e aij representam tradicionalmente constantes físicas e xj 
são variáveis de projeto. Essas funções geralmente não são convexas nem 
côncavas e, por isso, as técnicas de programação convexa não podem ser 
aplicadas diretamente para esses problemas de programação geométrica. 
Contudo, há um caso importante no qual o problema pode ser transformado 
em um problema de programação convexa equivalente, como nos casos em 
que todos os coeficientes ci em cada função são estritamente positivos, de 
modo que as funções sejam polinômios positivos generalizados (posinomiais) 
e que a função objetivo seja minimizada. O problema de programação convexa 
equivalente com variáveis de decisão y1, y2,..., yn é então obtido configurando-se:
Ao longo do modelo original, de modo que agora um algoritmo de programa-
ção convexa possa ser aplicado. Também foram desenvolvidos procedimentos 
de resolução alternativos para resolver esses problemas de programação posi-
nomial, bem como para problemas de programação geométrica de outros tipos.
115Tópicos complementares: múltiplos objetivos, programação dinâmica e não linear
Programação fracionária 
Supomos que a função objetivo encontre-se na forma de uma fração, ou seja, 
a razão de duas funções:
Os problemas de programação fracionária surgem, por exemplo, quando 
se está maximizando a razão entre produção e horas de mão de obra gastas 
(produtividade) ou entre lucro e capital investido (taxa de retorno) ou, ainda, 
entre valor esperado e desvio padrão de alguma medida de desempenho para 
uma carteira de investimentos (retorno/risco). Foram desenvolvidos alguns 
procedimentos especiais para certas formas de f1(x) e f2(x). 
A mais simples e direta metodologia para solucionar um problema de 
programação fracionária, quando é possível realizá-la, é transformá-lo em 
um problema equivalente de tipo padrão para o qual já haja procedimentos de 
resolução eficientes. Por exemplo, suponha que f(x) seja da forma programação 
fracionária linear
em que c e d são vetores-linha, x é um vetor-coluna e c0 e d0 são escalares. 
Suponha também que as funções de restrição gi(x) sejam lineares, de modo 
que as restrições na forma matricial serão Ax ≤ b e x ≥ 0. 
Sob outras hipóteses amenas adicionais, podemos transformar o problema 
em um problema de programação linear equivalente fazendo que:
de modo que x =y/t. Esse resultado leva a
maximizar z = cy + c0t,
sujeito a
Ay – bt ≤ 0,
Pesquisa operacional116
Dy + d0t = 1,
e
y ≥ 0, t ≥ 0,
que podem ser resolvidos pelo método simplex. De modo genérico, o 
mesmo tipo de transformação pode ser usado para converter um problema 
de programação fracionária com f1(x) côncava, f2(x) convexa e gi(x) convexa 
em um problema de programação convexa equivalente.
Problema da complementaridade 
O problema da complementaridade busca encontrar uma solução viável para 
o conjunto de restrições
W = f (z), w ≥ 0, z ≥ 0
que também satisfaçam a restrição de complementaridade
wtz = 0.
 Aqui, w e z são vetores-coluna, f é determinada função avaliada por vetores 
e o t sobrescrito representa a transposição. O problema não possui nenhuma 
função objetivo e, portanto, tecnicamente não é um problema de programação 
não linear totalmente desenvolvido. Chama-se problema da complementaridade 
em virtude das relações de complementaridade que
Wi = 0 ou zi = 0 (ou, então, ambos) para cada i = 1,2,...,p.
Um caso especial importante é aquele do problema de complementaridade 
linear, em que
F (z) = q + Mz,
em que q é um vetor-coluna dado e M é uma matriz p x p dada. Foram 
desenvolvidos algoritmos eficientes para solucionar esse problema sob diversas 
hipóteses sobre as propriedades da matriz M. Um tipo envolve pivotar a partir 
117Tópicos complementares: múltiplos objetivos, programação dinâmica e não linear
de uma solução básica viável (BV) para a próxima, de modo muito parecido com 
o método simplex para programação linear (HILLIER; LIEBERMANN, 2013). 
Além de ter aplicações em programação não linear, os problemas de comple-
mentaridade possuem aplicações na teoria dos jogos, problemas de equilíbrio 
econômico, bem como problemas de equilíbrio de engenharia.
Há grande ênfase nos últimos anos no desenvolvimento de pacotes de software 
confiáveis e de alta qualidade para uso geral na aplicação dos melhores desses algo-
ritmos. Por exemplo, diversos pacotes de software poderosos, como o Minos, foram 
desenvolvidos no Laboratório de Otimização de Sistemas da Universidade de Stanford.
Problemas práticos de otimização frequentemente envolvem comporta-
mento não linear que deve ser levado em consideração. Algumas vezes, é 
possível reformular essas não linearidades para se adequar ao formato da 
programação linear, como pode ser feito, por exemplo, no caso de problemas 
de programação separável. Entretanto, com frequência é necessário usar uma 
formulação de programação não linear. 
Ao contrário do método simplex para programação linear, não há um 
algoritmo eficiente de propósito genérico que possa ser utilizado para resolver 
todos os problemas de programação não linear. Na verdade, nenhum método 
pode resolver de maneira bem satisfatória alguns desses problemas. Contudo, 
está se obtendo progresso considerável para algumas classes importantes de 
problemas, entre elas programação quadrática, programação convexa e certos 
tipos especiais de programação não convexa. Existe uma série de algoritmos 
disponíveis que, frequentemente, têm bom desempenho para esses casos. 
Alguns desses algoritmos incorporam procedimentos altamente eficientes 
para otimização irrestrita para uma parte de cada iteração, e outros usam uma 
sucessão de aproximações quadráticas ou lineares para o problema original. 
Pesquisa operacional118
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre: 
AMGH, 2013. E-book. 
TAHA, H. A. Pesquisa operacional: uma visão geral. São Paulo: Pearson Prentice Hall, 2008.
Leituras recomendadas
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. São Paulo: Pearson 
Prentice Hall, 2009.
WAGNER, H.M. Pesquisa operacional. 2. ed. Rio de Janeiro: Prentice-Hall do Brasil, 1996.
119Tópicos complementares: múltiplos objetivos, programação dinâmica e não linear
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra. 
Conteúdo:
DICA DO PROFESSOR
Nesse vídeo, você vai ver como são os métodos utilizados para obtermos o algoritmo de 
problemas com múltiplos objetivos e como devem ser organizadas as metas para a sua solução.
Conteúdo interativo disponível na plataforma de ensino!
EXERCÍCIOS
1) A solução de problemas considerando múltiplos objetivos apresenta características 
particulares. Marque a alternativa que apresenta uma afirmativa correta: 
A) As situações com decisões sempre envolvem um único objetivo.
B) Há apenas um método que pode otimizar um modelo de multiobjetivos: o método de 
pesos.
C) O método de pesos otimiza as metas uma por vez começando com a meta de prioridade 
mais alta e terminando com a de prioridade mais baixa, sem nunca degradar a qualidade da 
meta de prioridade mais alta.
D) O método hierárquico forma uma única função objetivo que consista na soma ponderada 
das metas.
E) Políticos prometem reduzir a dívida nacional e, ao mesmo tempo, oferecem redução da 
carga tributária. Esse é um exemplo de problema com múltiplos objetivos.
2) Com relação à programação dinâmica, marque a alternativa que apresenta uma 
afirmativa correta: 
A programação dinâmica é um método matemático pouco útil para uma sequência de A) 
tomadas de decisão não relacionadas.
B) Semelhante à programação linear, há uma formulação matemática padrão para um 
problema de programação dinâmica.
C) A programação dinâmica é muito útil como método para realizar uma sequência de 
decisõesinter-relacionadas.
D) A programação dinâmica determina a solução ótima de um problema de uma variável 
formado por um único estágio.
E) Um modelo de programação dinêmica não envolve equações recursivas e é formado por 
um único estágio do problema.
3) Sobre as características gerais de programação não linear, marque a alternativa que 
apresenta uma afirmativa correta: 
A) Em pesquisa operacional, raras vezes é necessário lidar diretamente com problemas de 
programação não linear.
B) Poucos são os tipos de problemas de programação não linear, de acordo com as 
características das funções f(x) e gi(x).
C) Devido à existência de poucos tipos de problemas de programação não linear, esse é um 
assunto particularmente curto.
D) Existem diferentes formas e formatos de problemas de programação não linear.
E) Não foram desenvolvidos pacotes de software confiáveis e de alta qualidade para uso geral 
na aplicação dos melhores desses algoritmos.
4) Com relação aos tipos de problema de programação não linear, marque a alternativa 
correta: 
A) Os problemas de otimização irrestrita são aqueles que apresentam restrições, de modo que 
o objetivo seja simplesmente maximizar f(x).
B) Os algoritmos para problemas restritos não podem ser modelados para que sejam capazes 
de se concentrar em uma versão irrestrita do problema durante parte de cada iteração.
C) As características de problemas de otimização linearmente restrita são restrições que se 
ajustam completamente à programação linear, de modo que todas as funções de restrição 
gi (x) sejam lineares, mas com a função objetivo f(x) não linear.
D) O problema de otimização linearmente restrita é complexo de modo considerável.
E) Distinto do método simplex, não foi desenvolvido nenhum algoritmo especial para 
considerar a função objetivo não linear.
5) Há diversas particularidades que diferenciam os tipos de programação não linear. 
Marque a alternativa que representa corretamente uma característica de um desses 
tipos. 
A) Os problemas de programação convexa também possuem restrições lineares, porém, agora 
a função objetivo f(x) deve ser quadrática.
B) A programação quadrática abrange uma ampla gama de problemas que, na realidade, 
engloba como casos especiais todos os tipos precedentes quando f(x) é uma função 
côncava a ser maximizada.
Na terminologia da programação não linear, problemas de programação separável atendem 
à hipótese da aditividade, mas, quando qualquer uma das funções fj(xj) for linear, violam a 
C) 
hipótese da proporcionalidade.
D) A programação convexa engloba todos os problemas de programação não linear que não 
atendem às hipóteses da programação linear.
E) Os problemas de programação fracionária surgem, por exemplo, quando se está 
minimizando a razão entre produção e horas de mão de obra gastas (produtividade).
NA PRÁTICA
A programação dinâmica (PD) determina a solução ótima de um problema de multivariáveis 
decompondo-o em estágios, sendo que cada estágio compreende um subproblema com uma 
única variável. Vejo como isso pode ser feito na prática.
Conteúdo interativo disponível na plataforma de ensino!
 
SAIBA MAIS
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Controle Ótimo de Sistemas Não Lineares com Aplicação no Cultivo do Milho.
Conteúdo interativo disponível na plataforma de ensino!
Programação Linear com objetivos múltiplos - Um instrumento para a tomada de decisão.
Conteúdo interativo disponível na plataforma de ensino!
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto 
Alegre: AMGH, 2012. 1028p.