Questão 2:

(a) Seja a tabela final SIMPLEX dada abaixo:
Table 1: Tableau 2
\captionsetup{labelformat=empty}
Basic
variables
Current
values
x_{1} x_{2} x_{3} x_{4} x_{5} x_{6}
x_{2} 4 \frac{2}{7} 1 -\frac{2}{7} -\frac{1}{7} \frac{3}{35}
x_{6} 1 \frac{4}{7} -\frac{11}{7} -\frac{2}{7} \frac{1}{14} 1
x_{1} 6 \frac{3}{7} 1 \frac{11}{7} \frac{2}{7} -\frac{1}{14}
(-z) -51 \frac{3}{7} -\frac{4}{7} -\frac{11}{14} -\frac{1}{35}
Lembrando da forma algébrica padrão dos Cortes Fracionários de Gomory*, gere uma desigualdade válida (Plano Cortante, ou mais simplesmente, um Corte) a partir da primeira linha do Tableau ótimo.
  • \left(a_{1}-\left\lfloor a_{1}\right\rfloor\right) x_{1}+\left(a_{2}-\left\lfloor a_{2}\right\rfloor\right) x_{2}+\cdots+\left(a_{n}-\left\lfloor a_{n}\right\rfloor\right) x_{n} \geq b-\lfloor b\rfloor.
    (b) Idem para a segunda linha do tableau corrente.
    (c) Responda: A tabela resultante da adição dos cortes gerados continua ótima?
    (Justifique)
    (d) Qual é o único tipo de solução-básica-viável que um Corte-de-Gomory (tal qual na forma algérbica dada acima) não conseguiria cortar? (Justifique)

Passo 1

O enunciado pede quatro coisas:
(a) Gerar um Corte de Gomory a partir da primeira linha do tableau ótimo (a primeira linha corresponde à variável básica x_{2} com valor atual 4\frac{2}{7}).
(b) Gerar um Corte de Gomory a partir da segunda linha do tableau corrente (a segunda linha corresponde à variável básica x_{6} com valor atual 1\frac{4}{7}).
(c) Dizer se a tabela resultante da adição desses cortes continua ótima (justificar).
(d) Dizer qual é o único tipo de solução-básica-viável que um Corte-de-Gomory, na forma algébrica dada, não conseguiria cortar (justificar).
Dados relevantes extraídos da tabela (peguei os números da tabela enviada):
  • Linha 1 (basic x_{2}):
    • valor atual (RHS) b = 4\frac{2}{7} = \dfrac{30}{7}.
    • coeficientes nas colunas x_{1},x_{2},x_{3},x_{4},x_{5},x_{6} são respectivamente 0,\;1,\;-\dfrac{2}{7},\;-\dfrac{1}{7},\;\dfrac{3}{35},\;0. (Em particular, os coeficientes relevantes para o corte são os que multiplicam x_{3},x_{4},x_{5}.)
  • Linha 2 (basic x_{6}):
    • valor atual (RHS) b = 1\frac{4}{7} = \dfrac{11}{7}.
    • coeficientes nas colunas x_{1},x_{2},x_{3},x_{4},x_{5},x_{6} são 0,\;0,\;-\dfrac{11}{7},\;-\dfrac{2}{7},\;\dfrac{1}{14},\;1. (Coeficientes relevantes: x_{3},x_{4},x_{5}.)
Lembrete da forma algébrica do Corte de Gomory usada aqui (fornecida no enunciado): para uma linha escrita na forma
x_B + \sum_j a_j x_j = b,
o Corte é
\sum_j \bigl(a_j - \lfloor a_j\rfloor\bigr) x_j \ge b - \lfloor b\rfloor,
ou seja, usa-se a parte fracionária de cada coeficiente a_j e da RHS b.

Passo 2

Construção do Corte a partir da primeira linha (basic x_{2}) — passo a passo e explicando cada operação.
  1. Reescrever a equação da linha na forma x_{2} + \sum_j a_j x_j = b. A linha dada corresponde a:
x_{2} + \left(-\tfrac{2}{7}\right)x_{3} + \left(-\tfrac{1}{7}\right)x_{4} + \left(\tfrac{3}{35}\right)x_{5} = \tfrac{30}{7}.
Portanto os a_j relevantes são a_3=-\tfrac{2}{7}, a_4=-\tfrac{1}{7}, a_5=\tfrac{3}{35} e b=\tfrac{30}{7}.
  1. Calcular a parte fracionária de b:
\left\lfloor \tfrac{30}{7}\right\rfloor = 4,\qquad b-\lfloor b\rfloor = \tfrac{30}{7}-4=\tfrac{2}{7}.
A parte fracionária de b é \dfrac{2}{7}.
  1. Calcular a parte fracionária de cada a_j usando a_j-\lfloor a_j\rfloor:
  • Para a_3=-\dfrac{2}{7}: \lfloor -\tfrac{2}{7}\rfloor = -1, então a_3-\lfloor a_3\rfloor = -\tfrac{2}{7}-(-1)=1-\tfrac{2}{7}=\tfrac{5}{7}.
  • Para a_4=-\dfrac{1}{7}: \lfloor -\tfrac{1}{7}\rfloor=-1, então a_4-\lfloor a_4\rfloor = -\tfrac{1}{7}-(-1)=1-\tfrac{1}{7}=\tfrac{6}{7}.
  • Para a_5=\dfrac{3}{35}: \lfloor \tfrac{3}{35}\rfloor=0, então a_5-\lfloor a_5\rfloor = \tfrac{3}{35}-0=\tfrac{3}{35}.
  1. Aplicar a fórmula do corte:
\frac{5}{7}x_{3}+\frac{6}{7}x_{4}+\frac{3}{35}x_{5}\ge \frac{2}{7}.
  1. (Prática: normalmente multiplicamos por um denominador comum inteiro para obter coeficientes inteiros.) O denominador comum aqui é 35. Multiplicando ambos os lados por 35 obtemos a forma inteira equivalente:
25x_{3}+30x_{4}+3x_{5}\ge 10.
Portanto o Corte gerado pela primeira linha é, em forma fracionária,
\frac{5}{7}x_{3}+\frac{6}{7}x_{4}+\frac{3}{35}x_{5}\ge \frac{2}{7},
ou, multiplicando por 35, a forma inteira
25x_{3}+30x_{4}+3x_{5}\ge 10.

Passo 3

Construção do Corte a partir da segunda linha (basic x_{6}) — passo a passo.
  1. Reescrever a equação da linha:
x_{6} + \left(-\tfrac{11}{7}\right)x_{3} + \left(-\tfrac{2}{7}\right)x_{4} + \left(\tfrac{1}{14}\right)x_{5} = \tfrac{11}{7}.
Logo a_3=-\tfrac{11}{7}, a_4=-\tfrac{2}{7}, a_5=\tfrac{1}{14} e b=\tfrac{11}{7}.
  1. Parte fracionária de b:
\left\lfloor \tfrac{11}{7}\right\rfloor = 1,\qquad b-\lfloor b\rfloor = \tfrac{11}{7}-1=\tfrac{4}{7}.
  1. Partes fracionárias dos coeficientes:
  • a_3=-\tfrac{11}{7}. Temos \lfloor -\tfrac{11}{7}\rfloor=-2 (porque -\tfrac{11}{7}\approx-1{,}5714), então a_3-\lfloor a_3\rfloor = -\tfrac{11}{7}-(-2)=2-\tfrac{11}{7}=\tfrac{3}{7}.
  • a_4=-\tfrac{2}{7} já calculado antes dá parte fracionária \tfrac{5}{7}.
  • a_5=\tfrac{1}{14} tem \lfloor\tfrac{1}{14}\rfloor=0, logo parte fracionária \tfrac{1}{14}.
  1. Aplicar a fórmula do corte:
\frac{3}{7}x_{3}+\frac{5}{7}x_{4}+\frac{1}{14}x_{5}\ge \frac{4}{7}.
  1. Multiplicando por 14 para inteiros:
6x_{3}+10x_{4}+x_{5}\ge 8.
Portanto o Corte gerado pela segunda linha é
\frac{3}{7}x_{3}+\frac{5}{7}x_{4}+\frac{1}{14}x_{5}\ge \frac{4}{7},
ou, em forma inteira,
6x_{3}+10x_{4}+x_{5}\ge 8.

Passo 4

Responder (c): a tabela resultante da adição dos cortes gerados continua ótima? Justificação passo a passo.
  1. Interpretar: a tabela atual tem básicas x_{1},x_{2},x_{6} e, portanto, na solução atual os não-básicos x_{3},x_{4},x_{5} valem zero. Então, na solução básica corrente,
x_{3}=x_{4}=x_{5}=0.
  1. Avaliar cada corte na solução atual:
  • Para o corte da primeira linha (forma inteira) 25x_{3}+30x_{4}+3x_{5}\ge 10: substituindo x_{3}=x_{4}=x_{5}=0 0\ge 10, o que é falso — isto é, o corte é violado pela solução atual.
  • Para o corte da segunda linha 6x_{3}+10x_{4}+x_{5}\ge 8: com x_{3}=x_{4}=x_{5}=0 0\ge 8, também falso — também violado.
  1. Conclusão lógica: a solução atual não satisfaz (violou) os cortes adicionados, logo a solução atual deixa de ser viável para o programa linear que inclui esses cortes. Se a solução atual não é viável, a tabela corrente não pode permanecer como uma tabela ótima da nova relaxação (pois ótima implica viável). Portanto, após adicionar os cortes, a tabela NÃO permanece ótima — é necessário refazer a fatoração/re-otimização (normalmente introduzindo variáveis de folga/sobra e pivotando) para encontrar a nova solução ótima da relaxação aumentada.
Resposta curta para (c): Não — porque a solução atual (com x_{3}=x_{4}=x_{5}=0) viola ambos os cortes ( 0<10 e 0<8 ).

Passo 5

Responder (d): qual é o único tipo de solução-básica-viável que um Corte-de-Gomory na forma dada não conseguiria cortar? Justificação.
  1. Intuição: cortes de Gomory são formulados para separar soluções fracionárias da envelopagem inteira; eles são válidos para todo ponto inteiro factível. Em particular, um corte de Gomory não pode excluir nenhuma solução inteira factível (ou seja, nenhuma solução onde todas as variáveis inteiras da formulação original têm valor inteiro), porque a construção garante validade para todas as soluções inteiras.
  2. Demonstração algébrica curta (clara e direta). Partimos da linha
x_B + \sum_j a_j x_j = b,
onde o corte é
\sum_j \bigl(a_j-\lfloor a_j\rfloor\bigr) x_j \ge b-\lfloor b\rfloor.
Se x é uma solução inteira (isto é, todas as x_j e x_B são inteiros), então considere a quantidade
\sum_j \bigl(a_j-\lfloor a_j\rfloor\bigr) x_j - \bigl(b-\lfloor b\rfloor\bigr).
Reescrevendo:
\sum_j a_j x_j - b \;-\;\Bigl(\sum_j \lfloor a_j\rfloor x_j - \lfloor b\rfloor\Bigr).
Pela equação da linha, \sum_j a_j x_j - b = -x_B, que é inteiro; e \sum_j \lfloor a_j\rfloor x_j - \lfloor b\rfloor é também um inteiro, logo a diferença é um inteiro. Além disso, a diferença está estritamente maior que -1 (porque as partes fracionárias envolvidas ficam em [0,1)), então o único inteiro possível é um inteiro maior ou igual a 0. Portanto
\sum_j \bigl(a_j-\lfloor a_j\rfloor\bigr) x_j - \bigl(b-\lfloor b\rfloor\bigr)\ge 0,
ou seja, toda solução inteira satisfaz o corte.
  1. Conclusão: o Corte-de-Gomory não consegue cortar (ou seja, não exclui) nenhuma solução-básica-viável inteira. Em palavras concisas: o único tipo de solução-básica-viável que o corte não consegue cortar é uma solução-básica-viável inteira (todas as variáveis inteiras assumem valores inteiros) — pois o corte é válido para todas as soluções inteiras.

Resposta

(a) \dfrac{5}{7}x_{3}+\dfrac{6}{7}x_{4}+\dfrac{3}{35}x_{5}\ge \dfrac{2}{7} \quad (forma inteira equivalente: 25x_{3}+30x_{4}+3x_{5}\ge 10).
(b) \dfrac{3}{7}x_{3}+\dfrac{5}{7}x_{4}+\dfrac{1}{14}x_{5}\ge \dfrac{4}{7} \quad (forma inteira equivalente: 6x_{3}+10x_{4}+x_{5}\ge 8).
(c) Não.
(d) Qualquer solução-básica-viável inteira (ou seja, uma solução em que todas as variáveis inteiras assumem valores inteiros).

Exercícios relacionados