Este é o comando lrsbuffer que pode ser executado no provedor de hospedagem gratuita OnWorks usando uma de nossas várias estações de trabalho online gratuitas, como Ubuntu Online, Fedora Online, emulador online do Windows ou emulador online do MAC OS
PROGRAMA:
NOME
lrslib - Converter entre representações de poliedros convexos.
SINOPSE
lrs entrada.ine
lrs entrada.ine | lrsbuffer
lrsfourier arquivo.ine [saída de arquivo]
redundante entrada.ine
DESCRIÇÃO
Um poliedro pode ser descrito por uma lista de desigualdades (Representação H) ou como por uma lista
de seus vértices e raios extremos (Representação V). lrs é um programa C que converte um
Representação H de um poliedro para sua representação V e vice-versa. Estes problemas
são conhecidos respectivamente no vértice enumeração e convexo casco problemas.
Fukuda's Perguntas frequentes página[1] contém uma introdução mais detalhada do problema, junto com
muitas dicas úteis para o novo usuário.
lrsbuffer pode remover alguma saída duplicada. redundante encontra desigualdades redundantes no
entrada.
ARQUIVO FORMATOS
Os formatos de arquivo foram desenvolvidos em conjunto com Komei Fukuda e são compatíveis com cdd[2].
A entrada para lrs é uma representação H- ou V- de um politopo.
nome
{linha de representação}
{opções}
{linearidades[3]}
começar
mn racional
{matriz de entrada}
final
{opções}
nome é um nome fornecido pelo usuário para o politopo. Os comentários podem aparecer antes do início ou
após o final, e para evitar a interpretação como uma opção, deve começar com um especial
caractere como "*" ou "#".
nome é um nome fornecido pelo usuário para o politopo. representação linha é também
"Representação H" ou "representação V". Se for omitido, a representação H é assumida. o
os coeficientes de entrada são lidos em formato livre e não são verificados quanto ao tipo. Coeficientes são
separados por espaço em branco. m é o número de linhas eno número de colunas da entrada
matriz.
Representação H
O inteiro m é o número de desigualdades, e o inteiro n é a dimensão do
entrada +1. Uma lista de desigualdades contém os coeficientes de desigualdades do formulário
a0 + a1x1 + ... + an-1 xn-1> = 0.
Esta desigualdade é inserida como a linha
a0 a1 ... an-1
Os coeficientes podem ser inseridos como inteiros ou racionais no formato x / y.
Representação em V
O inteiro m é o número de vértices e raios, e o inteiro n é a dimensão de
a entrada +1. Cada vértice é dado na forma
1 v0 v 1 ... vn-1
Cada raio é dado na forma
0 r0 r 1 ... rn-1
onde r0 r 1 ... rn-1 é um ponto no raio.
Deve haver pelo menos um vértice em cada arquivo. Para poliedros delimitados, não haverá
raios entraram. Os coeficientes podem ser inseridos como inteiros ou racionais no formato x / y.
Note para cdd usuários: lrs usa essencialmente o mesmo formato de arquivo que cdd. Arquivos preparados para
cdd deve funcionar com pouca ou nenhuma modificação. Observe que a representação em V
corresponde à opção "casco" em cdd. Opções específicas para cdd pode ser deixado na entrada
arquivos e serão ignorados por lrs. Observe os arquivos de entrada para lrs são lidos em formato livre,
depois da linha m n racional, lrs iráprocurar exatamente m * n racionais ou inteiros separados
por espaço em branco (em branco, retorno de carro, guia etc.). lrs não vai "descartar" colunas extras de
entrada se n for menor que o número de colunas fornecidas.
Basico Opções
Quase todas as opções são colocadas depois de a declaração final, mantendo a compatibilidade com cdd.
Quando este não for o caso, será mencionado explicitamente.
todas as bases Esta opção instrui lrs para listar cada vértice (ou faceta) para cada uma de suas bases.
saída Duplicação[4].[5] Esta opção é freqüentemente combinada com printcobasis.
obrigado x Use com representação H - para lrs ou nash Maximize ou minimize
opção deve ser selecionada. x é um número inteiro ou racional. Para maximização (resp.
minimização) a árvore de pesquisa reversa é truncada sempre que o valor do objetivo atual
é menos (resp. mais) do que x.
esconderijo nlrs armazena os últimos n dicionários na árvore de pesquisa reversa. Isso acelera
a etapa de retrocesso, mas requer mais memória.
depurar base de partida terminando a baseImprima rastreamento enigmático, mas detalhado, dicionários etc.
começando em # B = base inicial e terminando em # B = base final. depurar 0 0 dá um completo
vestígio.
dígitos n colocado antes que o começar afirmação n é o número máximo de dígitos decimais a serem
usado. Se for excedido, o programa termina com uma mensagem (geralmente pode ser
reiniciado). O padrão é definido para cerca de 100 dígitos. No final de uma corrida, uma mensagem é
fornecido informando ao usuário o tamanho inteiro máximo encontrado. Isso pode ser usado para
otimizar o uso de memória e velocidade em execuções subsequentes (se estiver fazendo estimativas, por exemplo).
perturbação dupla Se lrs for executado com a opção de maximizar ou minimizar, a pesquisa reversa
árvore está enraizada em um vértice ótimo para esta função.
vértices, a saída geralmente não será concluída. Esta opção dá uma pequena perturbação para
o objetivo de evitar isso. Uma mensagem de aviso é dada se o dicionário inicial for dual
degenerar.
estimativas k Estime o tamanho da saída. Usado em conjunto com maxdepth - consulte
Estimativa.[6]
geométrico // Representação H ou opção voronoi apenas // Com esta opção, cada raio é
impresso junto com o vértice com o qual é incidente. Para mais informações, veja
Raios geométricos em Dicas e Comentários[5].
incidênciaEsta opção liga automaticamente printcobase , então veja abaixo um
descrição desta opção primeiro. Pode ser usado com printcobasis n. (Ver 4.2b) .PP para
entrada representação H, índices de todas as desigualdades de entrada que contêm o vértice / raio que
está prestes a ser produzido. Para simplificar, não há saída nova, uma vez que esses índices
já estão listados. Caso contrário, as desigualdades restritas adicionais são listadas após dois pontos.
.PP Para a representação V de entrada, índices de todos os vértices / raios de entrada que se encontram na faceta
que está prestes a ser produzido. Um índice com estrela indica que este vértice também está no
cobasis, mas não está contido na faceta. Surge devido à operação de elevação utilizada
com representações V de entrada.
#incidênciaO mesmo que printcobasis. Incluído para compatibilidade com cd.
linearidade k i1i2 i ... ikA entrada contém k linearidades em linhas i1i2i ... ikda
arquivo de entrada são equações. Ver Linearidades.[3]
profundidade máxima k A pesquisa será truncada na profundidade k. Todas as bases com profundidade menor que ou
igual a k será calculado. k é um número inteiro não negativo, e esta opção é usada para
estimativas - veja Estimativa.[6]Note: Para representações H, os raios na profundidade k não serão
relatado. Para representações em V, as facetas na profundidade k não serão relatadas.
maximizar a0 a1 ... um-1 // apenas representação H //
minimizar a0 a1 ... um-1 // apenas representação H //
Se usado com lrs, o vértice inicial maximiza (ou minimiza) a função a0 + a1x1 + ...
+ an-1 xn-1. A opção dualperturb pode ser necessária para evitar degenerescência dupla. Ver Nash
Equilíbrio e Linear Programação[7]
saída máxima n Limita o número de linhas de saída produzidas (vértices + raios ou facetas) para n
profundidade mínima k O retrocesso será encerrado na profundidade k, para ka inteiro não negativo. Esse
pode ser usado para executar a pesquisa reversa em subárvores como processos separados, por exemplo, em um
ambiente de computação distribuída.
não negativo // Esta opção deve vir antes da instrução begin // // apenas representação H
// Bug: Só pode ser usado se a origem for um vértice do poliedro Para problemas onde
a entrada é uma representação H da forma b + Ax> = 0, x> = 0 (ou seja, todas as variáveis
não negativo, todas as restrições de desigualdades), não é necessário dar o não negativo
restrições explicitamente se a opção não negativa for usada. Esta opção não pode ser usada para
V-representações, ou com a opção de linearidade (neste caso as linearidades serão
tratados como desigualdades). Esta opção pode ser usada com redundância, mas o implícito
as restrições de não-negatividade não são testadas para redundância. Para testar tudo isso
é necessário inserir as restrições de não-negatividade explicitamente no arquivo de entrada. (Em Ver
4.1, a origem deve ser um vértice).
printcobase k;Modificado em lrs 4.0. Cada k'th cobasis é impressa. Se k for omitido, o
cobasis é impresso para cada vértice / raio / faceta que é produzido. Para um longo prazo, é útil
para imprimir o cobasis ocasionalmente para que o programa possa ser reiniciado se necessário.
Representação H: Se a entrada for uma representação H, a cobase é uma lista dos índices de
as desigualdades do arquivo de entrada que definem o vértice ou raio atual. Veja a opção
incidência acima para obter mais informações. Para os raios, uma cobase também é impressa. Nesse caso
a cobase é a cobase do vértice de onde o raio emana. Um dos índices
está marcado com estrela, isso indica a desigualdade a ser eliminada da cobase para definir o
raio. Alternativamente, se o todas as basesopção for usada, todos os cobases serão impressos.
Representação em V: Se a entrada for uma representação em V, o cobasis é uma lista da entrada
vértices / raios que definem a faceta atual. Veja a opção incidência acima para mais
em formação. Iniciar lrs desta faceta, todos os 4 índices devem ser dados nesta ordem
(omita o *).
falta de impressão Novo na versão 4.2; // Use com representação H // lrs imprime uma lista dos
índices das desigualdades de entrada que são satisfeitas estritamente para o vértice atual, ou seja,
a variável de folga correspondente é positiva. Se não negativo for definido, a lista também
incluem índices n + i para cada variável de decisão xi que é positiva. projeto Usado por
lrsfourier[8] apenas.
restart V# R# B# profundidade {faceta #s or vértice / raio #s} Modificado em lrs4.0 lrs pode ser
reiniciado a partir de qualquer cobase conhecida. O cálculo prosseguirá para o encerramento normal. Tudo
das informações estão contidas na saída de um printcobase opção. O ordem of
que o índices is muito importante, insira-os exatamente como aparecem na saída do
execução abortada anteriormente.
começando a cobase i1i2i ... em-1 Isso permite que o usuário especifique uma cobase conhecida para
começando a busca reversa. i1i2i ... em-1 é uma lista das desigualdades (para
Representação H) ou vértices / raios (para representação em V) que definem uma cobase. Se for
inválido ou esta opção não foi especificada, lrs encontrará seu próprio cobasis inicial. o
a árvore de pesquisa reversa é truncada (podada) sempre que um novo vértice é encontrado. Nota: este
nota necessariamente produz o conjunto de todos os vértices adjacentes ao vértice ideal em
o poliedro, mas apenas um subconjunto deles.
detalhadoImprima informações um pouco mais detalhadas sobre a execução.
volume // Apenas representação em V // Computa o volume - consulte a seção Volume Computação.[9]
Voronoi // Apenas representação V - coloque imediatamente após a instrução final // Compute
Diagrama de Voronoi - consulte a seção Voronoi Diagramas.[10]
NOTAS
1. Página de FAQ
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html
2. CD
http://www.cs.mcgill.ca/% 7Efukuda / soft / cdd_home / cdd.html
3. linearidades
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linearities
4. Duplicação de saída
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Output% 20Duplication
5.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Hints% 20and% 20Comments
6. Estimativa.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Estimation
7. Programação Linear
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Linear% 20Programming
8. lrsfourier
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # fourier
9. Computação de volume.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Volume% 20Computation
10. Diagramas de Voronoi.
http://cgm.cs.mcgill.ca/% 7Eavis / C / lrslib / USERGUIDE.html # Voronoi% 20Diagrams
Use lrsbuffer online usando serviços onworks.net