Solucione o problema de otimização linear a seguir pelo método descrito abaixo:
(i) Liste todos os pontos extremos do conjunto dos pontos factíveis.
(ii) Calcule o valor da função objetivo em cada um dos pontos factíveis.
(iii) Determine o ponto extremo que otimize a função objetivo e apresente os valores ótimos das variáveis de decisão, da função objetivo e o conjunto de índices associados à base ótima.
Além disso, diga se cada ponto extremo é ou não uma solução básica factível, apresentando os respectivos índices do conjunto de índices das variáveis básicas e do conjunto de índices das varáveis não-básicas. Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada. Caso seja múltipla ou ilimitada, mostre o formato geral da solução, tanto para as variáveis de decisão quanto para a função objetivo.
(a) \max \quad z=4 x_{1}+3 x_{2}
suj a x_{1}+3 x_{2} \leq 7
2 x_{1}+2 x_{2} \leq 8
x_{1}+x_{2} \leq 3
x_{2} \leq 2
x_{1} \geq 0
x_{2} \geq 0

Passo 1

O que o enunciado pede e quais informações nos dá\n
  • Pede que localizemos todos os pontos extremos (vértices) do conjunto factível e que calculemos o valor da função objetivo em cada um deles.\n
  • Pede que determinemos qual ponto extremo otimiza a função objetivo e apresentemos os valores ótimos das variáveis de decisão, o valor ótimo da função objetivo e o conjunto de índices da base ótima.\n
  • Pede, adicionalmente, para cada ponto extremo dizer se ele é uma solução básica factível, apresentando um conjunto de índices das variáveis básicas e das não-básicas, e indicar se a solução é única, múltipla ou ilimitada (se aplicável).\n
    Dados do problema:\n
\begin{aligned} \max\quad & z = 4x_{1}+3x_{2}\\\ \text{s.a.}\quad & x_{1}+3x_{2}\le 7\\\ & 2x_{1}+2x_{2}\le 8\\\ & x_{1}+x_{2}\le 3\\\ & x_{2}\le 2\\\ & x_{1}\ge 0,\; x_{2}\ge 0. \end{aligned}

Passo 2

Colocando as restrições em forma mais explícita e criando variáveis de folga (slacks) para explicar a ideia de base\n
  • Introduzo quatro variáveis de folga s_{1},s_{2},s_{3},s_{4} (todas \ge 0) para transformar as desigualdades em igualdades:
\begin{aligned} x_{1}+3x_{2}+s_{1} &= 7\\\\ 2x_{1}+2x_{2}+s_{2} &= 8\\\ x_{1}+x_{2}+s_{3} &= 3\\\ x_{2}+s_{4} &= 2. \end{aligned}
  • Índices que vou usar para listar variáveis: x_{1} índice 1, x_{2} índice 2, s_{1} índice 3, s_{2} índice 4, s_{3} índice 5, s_{4} índice 6.\n
    Breve explicação conceitual (rápida, prática):\n
  • Um ponto extremo do conjunto factível em \mathbb{R}^{2} aparece quando duas restrições (ou uma restrição e um eixo) ficam ativas simultaneamente (viram igualdades) e a solução resultante é viável.\n
  • Uma solução básica factível (SBF) corresponde a escolher um conjunto de m variáveis (aqui m=4 restrições) que formam a base; na prática, para cada vértice escolhemos 4 variáveis como básicas (algumas podem valer zero se houver degenerescência). Vou identificar uma base possível para cada vértice.

Passo 3

Observação sobre redundância de restrições e redução do trabalho\n
  • A restrição 2x_{1}+2x_{2}\le 8 equivale a x_{1}+x_{2}\le 4. Como existe a restrição x_{1}+x_{2}\le 3, esta última é mais restrita e torna a restrição x_{1}+x_{2}\le 4 redundante no conjunto factível. Portanto posso ignorá-la ao procurar vértices (ela não contribuirá para formar vértices da região factível).\n
  • Logo as desigualdades relevantes para formar vértices são:
x_{1}+3x_{2}\le 7,\quad x_{1}+x_{2}\le 3,\quad x_{2}\le 2,\quad x_{1}\ge0,\;x_{2}\ge0.

Passo 4

Encontrando todos os pontos extremos (intersecções relevantes) passo a passo\n
Vou verificar interseções entre as fronteiras das restrições (incluindo os eixos x_{1}=0 e x_{2}=0). Cada interseção será testada quanto à factibilidade (satisfaça todas as desigualdades).\n
  1. Interseção dos eixos: x_{1}=0 e x_{2}=0 \Rightarrow ponto \,(0,0). Verificação: todas as desigualdades são satisfeitas. Logo (0,0) é factível.\n
  2. Interseção x_{1}=0 com x_{2}=2 (fronteira de x_{2}\le 2) \Rightarrow (0,2). Verificação: x_{1}+3x_{2}=0+6=6\le7 e x_{1}+x_{2}=2\le3. Factível. Logo (0,2) é vértice.\n
  3. Interseção x_{2}=0 com x_{1}+x_{2}=3 \Rightarrow x_{1}=3 então (3,0). Verificação: 3+0\le7,\;3+0\le3 (igualdade na terceira). Factível. Logo (3,0) é vértice.\n
  4. Interseção x_{2}=2 com x_{1}+3x_{2}=7: inserir x_{2}=2 x_{1}+6=7\Rightarrow x_{1}=1. Ponto (1,2). Verificação: 1+2=3\le3 (igualdade na terceira). Factível. Logo (1,2) é vértice.\n
  5. Outros candidatos de interseção (por exemplo x_{1}=0 com x_{1}+x_{2}=3 (0,3), mas isto viola x_{2}\le2, logo não factível). Interseções com a restrição redundante x_{1}+x_{2}=4 geram pontos fora da região (ex.: (4,0) não satisfaz x_{1}+x_{2}\le3). Então já listamos todos os vértices factíveis.\n
    Conclusão: os vértices factíveis são os quatro pontos
(0,0),\quad (0,2),\quad (1,2),\quad (3,0).

Passo 5

Calcular z=4x_{1}+3x_{2} em cada ponto extremo (contas mostrando passo a passo)\n
  • Em (0,0): z=4\cdot 0 + 3\cdot 0 = 0.\n
  • Em (0,2): z=4\cdot 0 + 3\cdot 2 = 6.\n
  • Em (1,2): z=4\cdot 1 + 3\cdot 2 = 4 + 6 = 10.\n
  • Em (3,0): z=4\cdot 3 + 3\cdot 0 = 12.

Passo 6

Determinar o ponto extremo que otimiza a função objetivo e analisar unicidade/ilimitado\n
  • Comparando os valores calculados, o maior valor é z=12 no ponto (3,0). Portanto o ótimo é (x_{1},x_{2})=(3,0) com z_{\max}=12.\n
  • A região factível é limitada (há restrições tanto em x_{1} quanto em x_{2}); não existe direção que torne z indefinidamente grande sem violar restrições. Logo a solução ótima não é ilimitada.\n
  • Verificando se há soluções ótimas múltiplas: se houvesse múltiplas ótimas, a reta de nível 4x_{1}+3x_{2}=\text{const} com valor máximo deveria coincidir com uma aresta inteira do polígono factível. Os outros vértices têm valores 0,6,10 distintos de 12; portanto o ótimo 12 ocorre apenas em (3,0). Logo o ótimo é único (solução ótima única).\n
  • Base ótima (uma escolha de variáveis básicas) para (3,0): calculo os folgas no ponto (3,0):
\begin{aligned} s_{1} &= 7-(3+0)=4,\\\ s_{2} &= 8-(2\cdot 3 + 2\cdot 0)=8-6=2,\\\ s_{3} &= 3-(3+0)=0,\\\ s_{4} &= 2-(0)=2. \end{aligned}
Uma base natural e não-degenerada é escolher as variáveis básicas \{x_{1},s_{1},s_{2},s_{4}\} (índices \{1,3,4,6\}), com valores (3,4,2,2). As não-básicas ficam \{x_{2},s_{3}\} (índices \{2,5\}), com valores (0,0).\n
  • Observação sobre degenerescência e multiplicidade de base: o ponto ótimo é uma solução única do problema primal, e a base escolhida acima dá representação básica não-degenerada (todas as básicas positivas), portanto é uma base ótima única nessa representação; não há múltiplas soluções ótimas e o problema não é ilimitado.

Passo 7

Para cada ponto extremo: é SBF? quais índices básicos e não-básicos escolher (uma possível escolha), e se a representação é degenerada (múltiplas bases) ou não\n
Vou usar a indexação: 1\!\leftrightarrow\!x_{1}, 2\!\leftrightarrow\!x_{2}, 3\!\leftrightarrow\!s_{1}, 4\!\leftrightarrow\!s_{2}, 5\!\leftrightarrow\!s_{3}, 6\!\leftrightarrow\!s_{4}.\n
  • Ponto (0,0): valores (x_{1},x_{2},s_{1},s_{2},s_{3},s_{4})=(0,0,7,8,3,2).\n
    • É solução básica factível? Sim. Uma base natural é \{3,4,5,6\} (as quatro folgas) e não-básicas \{1,2\}. Todas as básicas são positivas, não há degenerescência (base única nesta representação).\n
  • Ponto (0,2): valores (0,2,1,4,1,0).\n
    • É SBF? Sim. Uma base possível é \{2,3,4,5\} (variáveis x_{2},s_{1},s_{2},s_{3}) com não-básicas \{1,6\}. Todas as básicas indicadas são positivas (exceto nenhuma), portanto não-degenerada para essa escolha de base.\n
  • Ponto (1,2): valores (1,2,0,2,0,0).\n
    • É SBF? Sim. Há degenerescência porque várias folgas valem zero. Uma base possível é \{1,2,4,6\} (índices \{1,2,4,6\}) com não-básicas \{3,5\}; nesta escolha s_{4}=0 é básica e igual a zero (degenerescência). Portanto a representação básica é degenerada — existem múltiplas bases que representam o mesmo ponto (mas o ponto em si é único). Esta degenerescência não implica múltiplas soluções ótimas do problema (a não ser que o valor objetivo fosse o mesmo em uma aresta inteira, o que não ocorre aqui).\n
  • Ponto (3,0): valores (3,0,4,2,0,2).\n
    • É SBF? Sim. Uma base conveniente e não-degenerada é \{1,3,4,6\} (índices \{1,3,4,6\}) com não-básicas \{2,5\}. Todas as básicas têm valor estritamente positivo aqui, logo essa base não é degenerada.\n
      Resumo sobre unicidade / ilimitado: nenhuma das SBFs corresponde a solução ilimitada; o ótimo global é único e ocorre em (3,0). Não há solução ótima múltipla.

Resposta

Pontos extremos factíveis: (0,0),\; (0,2),\; (1,2),\; (3,0).\n
Valores da função objetivo z=4x_{1}+3x_{2} em cada ponto, respectivamente: 0,\;6,\;10,\;12.\n
Ponto que otimiza (máximo): (x_{1},x_{2})=(3,0) com z_{\max}=12.\n
Conjunto de índices associado à base ótima (uma escolha não-degenerada): \{1,3,4,6\} (ou seja, x_{1},s_{1},s_{2},s_{4} básicos). Não-básicas: \{2,5\} (ou seja, x_{2},s_{3}).\n
Para cada ponto: (0,0) é SBF com base \{3,4,5,6\} e não-básicas \{1,2\} (não-degenerada);\n
(0,2) é SBF com base \{2,3,4,5\} e não-básicas \{1,6\} (não-degenerada);\n
(1,2) é SBF com base possível \{1,2,4,6\} e não-básicas \{3,5\} (degenerada — múltiplas bases representam o mesmo ponto);\n
(3,0) é SBF com base \{1,3,4,6\} e não-básicas \{2,5\} (não-degenerada).\n
A solução ótima é única (não há soluções múltiplas ótimas) e o problema não é ilimitado.

Exercícios relacionados