Questão 2:
(a) Seja a tabela final SIMPLEX dada abaixo:
Table 1: Tableau 2\captionsetup{labelformat=empty}
Basic
variables
Current
values
1
1
1
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.
-
.
(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)
Table 1: Tableau 2
\captionsetup{labelformat=empty}
|
|
|
|
|
|
|
|
||||
|
|
|
1 |
|
|
|
||||||
|
|
|
|
|
|
1 | ||||||
|
|
|
1 |
|
|
|
||||||
|
|
|
|
|
|
(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 com valor atual
).
(b) Gerar um Corte de Gomory a partir da segunda linha do tableau corrente (a segunda linha corresponde à variável básica com valor atual
).
(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).
(a) Gerar um Corte de Gomory a partir da primeira linha do tableau ótimo (a primeira linha corresponde à variável básica
(b) Gerar um Corte de Gomory a partir da segunda linha do tableau corrente (a segunda linha corresponde à variável básica
(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
): - valor atual (RHS)
. - coeficientes nas colunas
são respectivamente . (Em particular, os coeficientes relevantes para o corte são os que multiplicam .)
- valor atual (RHS)
- Linha 2 (basic
): - valor atual (RHS)
. - coeficientes nas colunas
são . (Coeficientes relevantes: .)
- valor atual (RHS)
Lembrete da forma algébrica do Corte de Gomory usada aqui (fornecida no enunciado): para uma linha escrita na forma
o Corte é
ou seja, usa-se a parte fracionária de cada coeficiente
e da RHS
.
Passo 2
Construção do Corte a partir da primeira linha (basic
) — passo a passo e explicando cada operação.
- Reescrever a equação da linha na forma
. A linha dada corresponde a:
Portanto os
relevantes são
,
,
e
.
- Calcular a parte fracionária de
:
A parte fracionária de
é
.
- Calcular a parte fracionária de cada
usando :
- Para
: , então - Para
: , então - Para
: , então
- Aplicar a fórmula do corte:
- (Prática: normalmente multiplicamos por um denominador comum inteiro para obter coeficientes inteiros.) O denominador comum aqui é
. Multiplicando ambos os lados por obtemos a forma inteira equivalente:
Portanto o Corte gerado pela primeira linha é, em forma fracionária,
ou, multiplicando por
, a forma inteira
Passo 3
Construção do Corte a partir da segunda linha (basic
) — passo a passo.
- Reescrever a equação da linha:
Logo
,
,
e
.
- Parte fracionária de
:
- Partes fracionárias dos coeficientes:
-
. Temos (porque ), então -
já calculado antes dá parte fracionária . -
tem , logo parte fracionária .
- Aplicar a fórmula do corte:
- Multiplicando por
para inteiros:
Portanto o Corte gerado pela segunda linha é
ou, em forma inteira,
Passo 4
Responder (c): a tabela resultante da adição dos cortes gerados continua ótima? Justificação passo a passo.
- Interpretar: a tabela atual tem básicas
e, portanto, na solução atual os não-básicos valem zero. Então, na solução básica corrente,
- Avaliar cada corte na solução atual:
- Para o corte da primeira linha (forma inteira)
: substituindo dá , o que é falso — isto é, o corte é violado pela solução atual. - Para o corte da segunda linha
: com dá , também falso — também violado.
- 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
) viola ambos os cortes (
e
).
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.
-
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.
-
Demonstração algébrica curta (clara e direta). Partimos da linha
onde o corte é
Se
é uma solução inteira (isto é, todas as
e
são inteiros), então considere a quantidade
Reescrevendo:
Pela equação da linha,
, que é inteiro; e
é também um inteiro, logo a diferença é um inteiro. Além disso, a diferença está estritamente maior que
(porque as partes fracionárias envolvidas ficam em
), então o único inteiro possível é um inteiro maior ou igual a
. Portanto
ou seja, toda solução inteira satisfaz o corte.
- 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)
\quad (forma inteira equivalente:
).
(b) \quad (forma inteira equivalente:
).
(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).
(b)
(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).