Resolva
Maxz
s.a
Maxz
s.a
Passo 1
O enunciado pede: maximizar a função objetivo
sujeita às restrições
Informações relevantes que temos:
e
são variáveis inteiras não-negativas; as duas primeiras inequações definem a região viável; queremos o valor máximo de
e os valores de
que o atingem.
Passo 2
Estratégia que vou usar (explicada como se eu estivesse te orientando na prova): primeiro resolvemos a versão relaxada (ou seja, sem a exigência de integridade — as variáveis podem ser reais) para identificar o máximo contínuo e os vértices da região viável. Isso é útil porque, para problemas lineares, o ótimo relaxado ocorre em um vértice da região poligonal. Depois, como as variáveis devem ser inteiras, fazemos uma busca discreta simples restrita aos possíveis valores inteiros (a região é pequena), comparando os valores de
. Essa abordagem é rápida em prova quando as variáveis têm limites baixos. Vou explicar cada etapa com calma.
A região viável (relaxada) é o polígono definido por
,
e
. Os vértices possíveis vêm das interseções dessas retas/semirretas. Calculamos os vértices relevantes:
Interseção entre
e
. Substituímos
em
:
Desenvolvendo,
Então
Logo um vértice é
.
Interseções com eixos (avaliando quais são factíveis):
- Com
: as restrições dão e . Então o ponto extremo na abscissa é (o não é viável porque viola ). - Com
: as restrições dão e . Então o extremo na ordenada é .
Os vértices relevantes da região viável são, portanto:
Calculamos
nesses vértices:
Assim, o ótimo relaxado (variáveis reais) é
em
. Como queremos variáveis inteiras, esse ponto não é admissível; precisamos procurar a melhor solução inteira na vizinhança viável.
Passo 3
Agora tratamos a versão inteira. Observação prática:
não pode exceder
porque
. Além disso
. Então
é um inteiro entre
e
. Para cada inteiro
calculamos o máximo inteiro possível de
compatível com ambas as restrições:
o limite real para é
; o maior inteiro admissível é a parte inteira (floor) desse mínimo. Vou calcular para cada
:
o limite real para
- Para
: . Então dá . - Para
: . dá . - Para
: . dá . - Para
: . dá . - Para
: . Como é inteiro, . Então dá . - Para
: . Então dá .
Compilando os melhores valores inteiros por
:
. O maior é
, obtido em
.
Passo 4
Comentário didático e rápido motivo: o ponto relaxado ótimo
dá
, mas não é inteiro. O ponto inteiro mais próximo em termos de componentes,
, seria atraente pois
, porém verifica-se que
viola a restrição
porque
. Assim o melhor possível entre os inteiros viáveis é
com
. Dica de prova: quando as variáveis têm limites pequenos, esta enumeração controlada por
(ou
) é rápida e segura.