Programação linear - Linear programming

Uma representação pictórica de um programa linear simples com duas variáveis ​​e seis desigualdades. O conjunto de soluções viáveis ​​é representado em amarelo e forma um polígono , um politopo bidimensional . A função de custo linear é representada pela linha vermelha e a seta: A linha vermelha é um conjunto de nível da função de custo e a seta indica a direção na qual estamos otimizando.
Uma região fechada viável de um problema com três variáveis ​​é um poliedro convexo . As superfícies que fornecem um valor fixo da função objetivo são planos (não mostrados). O problema de programação linear é encontrar um ponto no poliedro que está no plano com o maior valor possível.

A programação linear ( LP , também chamada de otimização linear ) é um método para obter o melhor resultado (como lucro máximo ou custo mais baixo) em um modelo matemático cujos requisitos são representados por relações lineares . A programação linear é um caso especial de programação matemática (também conhecida como otimização matemática ).

Mais formalmente, a programação linear é uma técnica para a otimização de uma função objetivo linear , sujeita à igualdade linear e restrições de desigualdade linear . Sua região viável é um politopo convexo , que é um conjunto definido como a interseção de muitos meios espaços finitos , cada um dos quais definido por uma desigualdade linear. Sua função objetivo é uma função afim de valor real (linear) definida neste poliedro. Um algoritmo de programação linear encontra um ponto no politopo onde esta função tem o menor (ou maior) valor se tal ponto existir.

Programas lineares são problemas que podem ser expressos na forma canônica como

Aqui, os componentes de x são as variáveis ​​a serem determinadas, c e b recebem vetores ( indicando que os coeficientes de c são usados ​​como uma matriz de linha única para o propósito de formar o produto da matriz), e A é uma matriz dada . A função cujo valor deve ser maximizado ou minimizado ( neste caso) é chamada de função objetivo . O desigualdades Um x  ≤  b e x0 são as limitações que especificam um poliepítopo convexa sobre a qual a função de objectivo é de ser optimizados. Nesse contexto, dois vetores são comparáveis quando têm as mesmas dimensões. Se cada entrada na primeira for menor ou igual à entrada correspondente na segunda, então pode-se dizer que o primeiro vetor é menor ou igual ao segundo vetor.

A programação linear pode ser aplicada a vários campos de estudo. É amplamente utilizado em matemática e, em menor grau, em negócios, economia e para alguns problemas de engenharia. Indústrias que usam modelos de programação linear incluem transporte, energia, telecomunicações e manufatura. Ele tem se mostrado útil na modelagem de diversos tipos de problemas de planejamento , roteamento , programação , atribuição e design.

História

O problema de resolver um sistema de desigualdades lineares remonta pelo menos até Fourier , que em 1827 publicou um método para resolvê-los, e após o qual o método de eliminação de Fourier-Motzkin é nomeado.

Em 1939, uma formulação de programação linear de um problema equivalente ao problema geral de programação linear foi dada pelo matemático e economista soviético Leonid Kantorovich , que também propôs um método para resolvê-lo. É uma forma que desenvolveu, durante a Segunda Guerra Mundial , para planejar gastos e retornos a fim de reduzir os custos do exército e aumentar as perdas impostas ao inimigo. O trabalho de Kantorovich foi inicialmente negligenciado na URSS . Quase ao mesmo tempo que Kantorovich, o economista holandês-americano TC Koopmans formulou problemas econômicos clássicos como programas lineares. Kantorovich e Koopmans mais tarde dividiram o prêmio Nobel de economia de 1975 . Em 1941, Frank Lauren Hitchcock também formulou problemas de transporte como programas lineares e deu uma solução muito semelhante ao método simplex posterior . Hitchcock morreu em 1957 e o prêmio Nobel não é concedido postumamente.

Durante 1946-1947, George B. Dantzig desenvolveu independentemente uma formulação de programação linear geral para usar em problemas de planejamento na Força Aérea dos Estados Unidos. Em 1947, Dantzig também inventou o método simplex que, pela primeira vez, abordou com eficiência o problema de programação linear na maioria dos casos. Quando Dantzig marcou um encontro com John von Neumann para discutir seu método simplex, Neumann imediatamente conjeturou a teoria da dualidade ao perceber que o problema que ele vinha trabalhando na teoria dos jogos era equivalente. Dantzig forneceu prova formal em um relatório não publicado "Um Teorema sobre Desigualdades Lineares" em 5 de janeiro de 1948. O trabalho de Dantzig foi disponibilizado ao público em 1951. Nos anos do pós-guerra, muitas indústrias o aplicaram em seu planejamento diário.

O exemplo original de Dantzig foi encontrar a melhor designação de 70 pessoas para 70 empregos. O poder de computação necessário para testar todas as permutações para selecionar a melhor atribuição é vasto; o número de configurações possíveis excede o número de partículas no universo observável . No entanto, leva apenas um momento para encontrar a solução ótima, apresentando o problema como um programa linear e aplicando o algoritmo simplex . A teoria por trás da programação linear reduz drasticamente o número de soluções possíveis que devem ser verificadas.

O problema de programação linear foi mostrado pela primeira vez como solucionável em tempo polinomial por Leonid Khachiyan em 1979, mas um grande avanço teórico e prático no campo veio em 1984, quando Narendra Karmarkar introduziu um novo método de ponto interior para resolver problemas de programação linear.

Usos

A programação linear é um campo de otimização amplamente utilizado por vários motivos. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linear. Certos casos especiais de programação linear, como problemas de fluxo de rede e problemas de fluxo de multicommodidades , são considerados importantes o suficiente para ter gerado muitas pesquisas sobre algoritmos especializados para sua solução. Vários algoritmos para outros tipos de problemas de otimização funcionam resolvendo problemas LP como subproblemas. Historicamente, as ideias da programação linear inspiraram muitos dos conceitos centrais da teoria da otimização, como dualidade, decomposição e a importância da convexidade e suas generalizações. Da mesma forma, a programação linear foi muito utilizada na formação inicial da microeconomia e atualmente é utilizada na gestão de empresas, como planejamento, produção, transporte, tecnologia e outras questões. Embora as questões de gerenciamento moderno estejam em constante mudança, a maioria das empresas gostaria de maximizar os lucros e minimizar os custos com recursos limitados. O Google usa programação linear para estabilizar os vídeos do YouTube. Portanto, muitos problemas podem ser caracterizados como problemas de programação linear.

Forma padrão

A forma padrão é a forma usual e mais intuitiva de descrever um problema de programação linear. Consiste nas seguintes três partes:

  • Uma função linear a ser maximizada
por exemplo
  • Restrições do problema da seguinte forma
por exemplo
  • Variáveis ​​não negativas
por exemplo

O problema geralmente é expresso em forma de matriz e então se torna:

Outras formas, como problemas de minimização, problemas com restrições em formas alternativas, bem como problemas envolvendo variáveis negativas , podem sempre ser reescritos em um problema equivalente na forma padrão.

Exemplo

Suponha que um fazendeiro tenha um pedaço de terra agrícola, digamos L km 2 , para ser plantado com trigo ou cevada ou alguma combinação dos dois. O agricultor tem uma quantidade limitada de fertilizante, F quilogramas, e pesticida, P quilogramas. Cada quilômetro quadrado de trigo requer F 1 quilograma de fertilizante e P 1 quilograma de pesticida, enquanto cada quilômetro quadrado de cevada requer F 2 quilogramas de fertilizante e P 2 quilogramas de pesticida. Seja S 1 o preço de venda do trigo por quilômetro quadrado e S 2 o preço de venda da cevada. Se representarmos a área de terra plantada com trigo e cevada por x 1 e x 2 , respectivamente, em seguida, o lucro pode ser maximizado escolhendo valores ideais para x 1 e x 2 . Este problema pode ser expresso com o seguinte problema de programação linear na forma padrão:

Maximizar: (maximizar a receita - a receita é a "função objetivo")
Sujeito a: (limite na área total)
(limite de fertilizante)
(limite de pesticida)
(não pode plantar uma área negativa).

Na forma de matriz, isso se torna:

maximizar
sujeito a

Forma aumentada (forma flexível)

Problemas de programação linear podem ser convertidos em uma forma aumentada para aplicar a forma comum do algoritmo simplex . Este formulário apresenta variáveis ​​de folga não negativas para substituir desigualdades por igualdades nas restrições. Os problemas podem ser escritos na seguinte forma de matriz de bloco :

Maximize :

onde estão as variáveis ​​de folga recém-introduzidas, são as variáveis ​​de decisão e é a variável a ser maximizada.

Exemplo

O exemplo acima é convertido na seguinte forma aumentada:

Maximizar: (função objetiva)
sujeito a: (restrição aumentada)
(restrição aumentada)
(restrição aumentada)

onde estão as variáveis ​​de folga (não negativas), representando neste exemplo a área não utilizada, a quantidade de fertilizante não utilizado e a quantidade de pesticida não utilizado.

Na forma de matriz, isso se torna:

Maximize :

Dualidade

Todo problema de programação linear, conhecido como problema primário , pode ser convertido em um problema dual , que fornece um limite superior para o valor ótimo do problema primário. Na forma de matriz, podemos expressar o problema primordial como:

Maximize c T x sujeito a A xb , x ≥ 0;
com o problema dual simétrico correspondente ,
Minimize b T y sujeito a A T yc , y ≥ 0.

Uma formulação primária alternativa é:

Maximize c T x sujeito a A xb ;
com o problema dual assimétrico correspondente ,
Minimize b T y sujeito a A T y = c , y ≥ 0.

Existem duas idéias fundamentais para a teoria da dualidade. Um é o fato de que (para o dual simétrico) o dual de um programa linear dual é o programa linear primal original. Além disso, toda solução viável para um programa linear fornece um limite para o valor ótimo da função objetivo de seu dual. O teorema da dualidade fraca afirma que o valor da função objetivo do dual em qualquer solução viável é sempre maior ou igual ao valor da função objetivo do primal em qualquer solução viável. O teorema da dualidade forte afirma que se o primal tem uma solução ótima, x * , então o dual também tem uma solução ótima, y * e c T x * = b T y * .

Um programa linear também pode ser ilimitado ou inviável. A teoria da dualidade nos diz que se o primal é ilimitado, então o dual é inviável pelo teorema da dualidade fraca. Da mesma forma, se o dual é ilimitado, o primal deve ser inviável. No entanto, é possível que tanto o dual quanto o primordial sejam inviáveis. Consulte o programa linear duplo para obter detalhes e vários outros exemplos.

Variações

Dualidades de cobertura / embalagem

Um LP de cobertura é um programa linear da forma:

Minimize: b T y ,
sujeito a: A T yc , y ≥ 0 ,

de forma que a matriz A e os vetores b e c não sejam negativos.

O dual de um LP de cobertura é um LP de embalagem , um programa linear da forma:

Maximize: c T x ,
sujeito a: A xb , x ≥ 0 ,

de forma que a matriz A e os vetores b e c não sejam negativos.

Exemplos

Cobrir e empacotar LPs comumente surge como um relaxamento de programação linear de um problema combinatório e é importante no estudo de algoritmos de aproximação . Por exemplo, os relaxamentos LP do problema de empacotamento de conjuntos , o problema de conjuntos independentes e o problema de correspondência são LPs de empacotamento. Os relaxamentos LP do problema da cobertura do conjunto , o problema da cobertura do vértice e o problema do conjunto dominante também estão cobrindo os LPs.

Encontrar uma coloração fracionária de um gráfico é outro exemplo de LP de cobertura. Nesse caso, há uma restrição para cada vértice do gráfico e uma variável para cada conjunto independente do gráfico.

Frouxidão complementar

É possível obter uma solução ótima para o dual quando apenas uma solução ótima para o primal é conhecida usando o teorema da folga complementar. O teorema afirma:

Suponha que x  = ( x 1x 2 , ...,  x n ) seja viável primal e que y  = ( y 1y 2 , ...,  y m ) seja dual viável. Deixe ( w 1w 2 , ...,  w m ) denotar as variáveis ​​de folga primárias correspondentes e ( z 1z 2 , ...,  z n ) denotar as variáveis ​​de folga duais correspondentes. Em seguida, x e y são ideais para seus respectivos problemas se e somente se

  • x j z j  = 0, para j  = 1, 2, ...,  n e
  • w i y i  = 0, para i  = 1, 2, ...,  m .

Portanto, se a i- ésima variável de folga do primal não é zero, então a i- ésima variável do dual é igual a zero. Da mesma forma, se a j -ésima variável de folga do dual não for zero, então a j -ésima variável do primal é igual a zero.

Essa condição necessária para a otimização transmite um princípio econômico bastante simples. Na forma padrão (ao maximizar), se houver folga em um recurso primário restrito (ou seja, houver "sobras"), então as quantidades adicionais desse recurso não devem ter valor. Da mesma forma, se houver folga no requisito de restrição de não negatividade do preço dual (sombra), ou seja, o preço não é zero, então deve haver oferta escassa (sem "sobras").

Teoria

Existência de soluções ótimas

Geometricamente, as restrições lineares definem a região viável , que é um poliedro convexo . Uma função linear é uma função convexa , o que implica que todo mínimo local é um mínimo global ; da mesma forma, uma função linear é uma função côncava , o que implica que todo máximo local é um máximo global .

Não é necessário que haja uma solução ótima por dois motivos. Primeiro, se as restrições são inconsistentes, então não existe uma solução viável: por exemplo, as restrições x  ≥ 2 e x  ≤ 1 não podem ser satisfeitas conjuntamente; neste caso, dizemos que o LP é inviável . Em segundo lugar, quando o politopo é ilimitado na direção do gradiente da função objetivo (onde o gradiente da função objetivo é o vetor dos coeficientes da função objetivo), então nenhum valor ideal é alcançado porque é sempre possível fazer melhor do que qualquer valor finito da função objetivo.

Vértices (e raios) ótimos de poliedros

Caso contrário, se existe uma solução viável e se o conjunto de restrições é limitado, o valor ótimo é sempre alcançado no limite do conjunto de restrições, pelo princípio do máximo para funções convexas (alternativamente, pelo princípio do mínimo para funções côncavas ) desde linear as funções são convexas e côncavas. No entanto, alguns problemas têm soluções ótimas distintas; por exemplo, o problema de encontrar uma solução viável para um sistema de desigualdades lineares é um problema de programação linear em que a função objetivo é a função zero (ou seja, a função constante tomando o valor zero em todos os lugares). Para este problema de viabilidade com a função zero para sua função objetivo, se houver duas soluções distintas, então cada combinação convexa das soluções é uma solução.

Os vértices do politopo também são chamados de soluções básicas viáveis . A razão para esta escolha de nome é a seguinte. Deixe d denotar o número de variáveis. Em seguida, o teorema fundamental das desigualdades lineares implica (para problemas viáveis) que para cada vértice x * da região viável LP, existe um conjunto de d (ou menos) restrições de desigualdade do LP tal que, quando tratamos essas d restrições como igualdades, a solução única é x * . Assim, podemos estudar esses vértices por meio da observação de certos subconjuntos do conjunto de todas as restrições (um conjunto discreto), ao invés do contínuo de soluções LP. Este princípio está na base do algoritmo simplex para resolver programas lineares.

Algoritmos

Em um problema de programação linear, uma série de restrições lineares produz uma região convexa viável de valores possíveis para essas variáveis. No caso de duas variáveis, essa região tem a forma de um polígono simples convexo .

Algoritmos de troca de base

Algoritmo Simplex de Dantzig

O algoritmo simplex , desenvolvido por George Dantzig em 1947, resolve problemas de LP construindo uma solução viável em um vértice do politopo e, em seguida, caminhando ao longo de um caminho nas bordas do politopo para vértices com valores não decrescentes da função objetivo até um o ideal é alcançado com certeza. Em muitos problemas práticos, ocorre " estagnação ": muitos pivôs são feitos sem aumento na função objetivo. Em raros problemas práticos, as versões usuais do algoritmo simplex podem realmente "circular". Para evitar ciclos, os pesquisadores desenvolveram novas regras de pivotamento.

Na prática, o algoritmo simplex é bastante eficiente e pode ser garantido que encontrará o ótimo global se forem tomadas certas precauções contra o ciclismo . O algoritmo simplex provou resolver problemas "aleatórios" de forma eficiente, ou seja, em um número cúbico de etapas, o que é semelhante ao seu comportamento em problemas práticos.

No entanto, o algoritmo simplex tem um comportamento de pior caso pobre: ​​Klee e Minty construíram uma família de problemas de programação linear para a qual o método simplex executa um número de etapas exponenciais no tamanho do problema. Na verdade, há algum tempo não se sabia se o problema de programação linear foi solucionáveis em tempo polinomial , ou seja, da classe de complexidade P .

Algoritmo cruzado

Como o algoritmo simplex de Dantzig, o algoritmo cruzado é um algoritmo de troca de bases que gira entre as bases. No entanto, o algoritmo cruzado não precisa manter a viabilidade, mas pode girar de uma base viável para uma base inviável. O algoritmo cruzado não possui complexidade de tempo polinomial para programação linear. Ambos os algoritmos visitam todos os cantos 2 D de um cubo (perturbado) na dimensão  D , o cubo Klee-Minty , no pior caso .

Ponto Interior

Em contraste com o algoritmo simplex, que encontra uma solução ótima ao percorrer as arestas entre os vértices em um conjunto poliédrico, os métodos de ponto interno se movem pelo interior da região viável.

Algoritmo de elipsóide, seguindo Khachiyan

Este é o primeiro algoritmo de tempo polinomial de pior caso já encontrado para programação linear. Para resolver um problema que tem n variáveis ​​e pode ser codificado em L bits de entrada, esse algoritmo é executado no tempo. Leonid Khachiyan resolveu esse problema de complexidade de longa data em 1979 com a introdução do método elipsóide . A análise de convergência tem predecessores (números reais), notadamente os métodos iterativos desenvolvidos por Naum Z. Shor e os algoritmos de aproximação de Arkadi Nemirovski e D. Yudin.

Algoritmo projetivo de Karmarkar

O algoritmo de Khachiyan foi de grande importância para estabelecer a solvabilidade em tempo polinomial de programas lineares. O algoritmo não foi um avanço computacional, pois o método simplex é mais eficiente para todas as famílias de programas lineares, exceto as especialmente construídas.

No entanto, o algoritmo de Khachiyan inspirou novas linhas de pesquisa em programação linear. Em 1984, N. Karmarkar propôs um método projetivo para programação linear. O algoritmo de Karmarkar melhorou o limite polinomial de pior caso de Khachiyan (dando ). Karmarkar afirmou que seu algoritmo era muito mais rápido na prática LP do que o método simplex, uma afirmação que criou grande interesse em métodos de pontos interiores. Desde a descoberta de Karmarkar, muitos métodos de pontos interiores foram propostos e analisados.

Algoritmo 87 de Vaidya

Em 1987, Vaidya propôs um algoritmo que funciona no tempo.

Algoritmo 89 de Vaidya

Em 1989, Vaidya desenvolveu um algoritmo que funciona no tempo. Falando formalmente, o algoritmo realiza operações aritméticas no pior caso, onde é o número de restrições, é o número de variáveis ​​e é o número de bits.

Algoritmos de tempo de dispersão de entrada

Em 2015, Lee e Sidford mostraram que, pode ser resolvido no tempo, onde representa o número de elementos diferentes de zero, e continua levando no pior caso.

Algoritmo de tempo de multiplicação da matriz atual

Em 2019, Cohen, Lee e Song melhoraram a execução de tempos em tempos, é o expoente da multiplicação da matriz e é o expoente dual da multiplicação da matriz . é (aproximadamente) definido como o maior número tal que se pode multiplicar uma matriz por uma matriz no tempo. Em um trabalho subsequente de Lee, Song e Zhang, eles reproduzem o mesmo resultado por meio de um método diferente. Esses dois algoritmos permanecem quando e . O resultado devido a Jiang, Song, Weinstein e Zhang melhorou para .

Comparação de métodos de pontos interiores e algoritmos simplex

A opinião atual é que as eficiências de boas implementações de métodos baseados em simplex e métodos de pontos interiores são semelhantes para aplicações de rotina de programação linear. No entanto, para tipos específicos de problemas LP, pode ser que um tipo de solucionador seja melhor do que outro (às vezes muito melhor), e que a estrutura das soluções geradas por métodos de pontos interiores versus métodos baseados em simplex sejam significativamente diferentes com o suporte conjunto de variáveis ​​ativas sendo tipicamente menor para o último.

Problemas abertos e trabalhos recentes

Problema não resolvido na ciência da computação :

A programação linear admite um algoritmo de tempo fortemente polinomial?

Existem vários problemas em aberto na teoria da programação linear, a solução dos quais representaria avanços fundamentais na matemática e avanços potencialmente importantes em nossa capacidade de resolver programas lineares em grande escala.

  • LP admite um algoritmo de tempo fortemente polinomial ?
  • LP admite um algoritmo de tempo fortemente polinomial para encontrar uma solução estritamente complementar?
  • LP admite um algoritmo de tempo polinomial no modelo de computação de número real (custo unitário)?

Este conjunto de problemas intimamente relacionado foi citado por Stephen Smale como um dos 18 maiores problemas não resolvidos do século XXI. Nas palavras de Smale, a terceira versão do problema "é o principal problema não resolvido da teoria da programação linear". Embora existam algoritmos para resolver a programação linear em tempo polinomial fraco, como os métodos elipsóide e técnicas de ponto interior , nenhum algoritmo foi encontrado ainda que permita desempenho em tempo polinomial forte no número de restrições e no número de variáveis. O desenvolvimento de tais algoritmos seria de grande interesse teórico e talvez também permitisse ganhos práticos na resolução de LPs grandes.

Embora a conjectura de Hirsch tenha sido recentemente refutada para dimensões superiores, ela ainda deixa as seguintes questões em aberto.

  • Existem regras de pivô que levam a variantes simplex em tempo polinomial?
  • Todos os gráficos politópicos têm diâmetro polinomialmente limitado?

Essas questões se relacionam à análise de desempenho e ao desenvolvimento de métodos do tipo simplex. A imensa eficiência do algoritmo simplex na prática, apesar de seu desempenho teórico em tempo exponencial, sugere que pode haver variações de simplex que são executados em tempo polinomial ou mesmo fortemente polinomial. Seria de grande importância prática e teórica saber se tais variantes existem, particularmente como uma abordagem para decidir se LP pode ser resolvido em um tempo fortemente polinomial.

O algoritmo simplex e suas variantes se enquadram na família de algoritmos de seguimento de arestas, assim chamados porque resolvem problemas de programação linear movendo-se de um vértice para outro ao longo das arestas de um politopo. Isso significa que seu desempenho teórico é limitado pelo número máximo de arestas entre quaisquer dois vértices no politopo LP. Como resultado, estamos interessados ​​em saber o diâmetro teórico-gráfico máximo de gráficos politopais . Está provado que todos os politopos têm diâmetro subexponencial. A recente refutação da conjectura de Hirsch é o primeiro passo para provar se algum politopo tem diâmetro superpolinomial. Se qualquer um desses politopos existir, nenhuma variante de seguimento de borda poderá ser executada em tempo polinomial. As questões sobre o diâmetro do politopo são de interesse matemático independente.

Os métodos de pivô simplex preservam a viabilidade primária (ou dupla). Por outro lado, os métodos de pivô cruzado não preservam a viabilidade (primal ou dual) - eles podem visitar bases viáveis ​​primárias, viáveis ​​duplas ou inviáveis ​​inviáveis ​​primárias e duais em qualquer ordem. Os métodos de pivô desse tipo têm sido estudados desde a década de 1970. Essencialmente, esses métodos tentam encontrar o caminho de pivô mais curto no politopo de arranjo sob o problema de programação linear. Em contraste com os gráficos de politopos, os gráficos de politopos de arranjo são conhecidos por terem diâmetro pequeno, permitindo a possibilidade de um algoritmo de pivô cruzado de tempo fortemente polinomial sem resolver questões sobre o diâmetro dos politopos gerais.

Inconhecidos inteiros

Se todas as variáveis ​​desconhecidas devem ser inteiros, então o problema é chamado de programação inteira (IP) ou programação linear inteira (ILP). Em contraste com a programação linear, que pode ser resolvida com eficiência no pior caso, os problemas de programação inteira são em muitas situações práticas (aquelas com variáveis ​​limitadas) NP-difíceis . A programação inteira 0-1 ou programação inteira binária (BIP) é o caso especial da programação inteira onde as variáveis ​​devem ser 0 ou 1 (em vez de números inteiros arbitrários). Esse problema também é classificado como NP-difícil e, de fato, a versão de decisão era um dos 21 problemas NP-completos de Karp .

Se apenas algumas das variáveis ​​desconhecidas precisam ser inteiros, então o problema é chamado de problema de programação inteira mista (MIP). Geralmente, também são NP-difíceis porque são ainda mais gerais do que os programas ILP.

No entanto, existem algumas subclasses importantes de problemas de IP e MIP que podem ser resolvidos de forma eficiente, principalmente problemas em que a matriz de restrição é totalmente unimodular e os lados direitos das restrições são inteiros ou - mais geral - onde o sistema tem a integralidade dual total (TDI) propriedade.

Os algoritmos avançados para resolver programas lineares inteiros incluem:

Esses algoritmos de programação inteira são discutidos por Padberg e em Beasley.

Programas lineares integrais

Um programa linear em variáveis ​​reais é considerado integral se tiver pelo menos uma solução ótima que é integral. Da mesma forma, um poliedro é considerado integral se, para todas as funções objetivo viáveis ​​limitadas c , o programa linear tiver um ótimo com coordenadas inteiras. Conforme observado por Edmonds e Giles em 1977, pode-se dizer equivalentemente que o poliedro é integral se para cada função objetivo integral viável limitada c , o valor ótimo do programa linear é um inteiro.

Os programas lineares integrais são de importância central no aspecto poliédrico da otimização combinatória, uma vez que fornecem uma caracterização alternativa de um problema. Especificamente, para qualquer problema, o casco convexo das soluções é um poliedro integral; se este poliedro tem uma descrição bonita / compacta, então podemos encontrar com eficiência a solução viável ótima sob qualquer objetivo linear. Por outro lado, se podemos provar que uma relaxação de programação linear é integral, então é a descrição desejada do casco convexo de soluções viáveis ​​(integrais).

A terminologia não é consistente em toda a literatura, portanto, deve-se ter o cuidado de distinguir os dois conceitos a seguir,

  • em um programa linear inteiro, descrito na seção anterior, as variáveis ​​são forçosamente restritas a números inteiros, e este problema é NP-difícil em geral,
  • em um programa linear integral, descrito nesta seção, as variáveis ​​não são restritas a inteiros, mas sim provou-se de alguma forma que o problema contínuo sempre tem um valor ótimo integral (assumindo que c é integral), e este valor ótimo pode ser encontrado de forma eficiente, uma vez que todos os programas lineares de tamanho polinomial podem ser resolvidos em tempo polinomial.

Uma forma comum de provar que um poliedro é integral é mostrar que ele é totalmente unimodular . Existem outros métodos gerais, incluindo a propriedade de decomposição de inteiro e integralidade dual total . Outros LPs integrais bem conhecidos específicos incluem o politopo correspondente, poliedros reticulados, poliedros de fluxo submodular e a interseção de dois polimatroides / g- polimatroides generalizados - por exemplo, ver Schrijver 2003.

Solucionadores e linguagens de script (programação)

Licenças permissivas :

Nome Licença Informação resumida
GLOP Apache v2 Solucionador de programação linear de código aberto do Google
Pyomo BSD Uma linguagem de modelagem de código aberto para otimização linear em grande escala, inteira mista e não linear
SuanShu Apache v2 um conjunto de algoritmos de otimização de código aberto para resolver LP, QP , SOCP , SDP , SQP em Java

Licenças Copyleft (recíprocas) :

Nome Licença Informação resumida
Solucionador de restrição de casuar LGPL um kit de ferramentas de resolução de restrição incremental que resolve com eficiência sistemas de igualdades e desigualdades lineares
CLP CPL um solucionador LP de COIN-OR
glpk GPL GNU Linear Programming Kit, um solucionador LP / MILP com uma API C nativa e vários (15) wrappers de terceiros para outras linguagens. Suporte especializado para redes de fluxo . Inclui o tradutor e a linguagem de modelagem GNU MathProg semelhante a AMPL .
Qoca GPL uma biblioteca para resolver de forma incremental sistemas de equações lineares com várias funções de objetivo
Projeto R GPL uma linguagem de programação e ambiente de software para computação estatística e gráficos

MINTO (Mixed Integer Optimizer, um solucionador de programação inteira que usa algoritmo de ramificação e limite) possui código-fonte disponível publicamente, mas não é de código aberto.

Licenças proprietárias :

Nome Informação resumida
AIMMS Uma linguagem de modelagem que permite modelar modelos de otimização lineares, inteiros mistos e não lineares. Ele também oferece uma ferramenta para programação de restrições. Algoritmo, na forma de heurísticas ou métodos exatos, como Branch-and-Cut ou Column Generation, também pode ser implementado. A ferramenta chama um solucionador apropriado, como CPLEX, Gurobi ou similar, para resolver o problema de otimização em questão. As licenças acadêmicas são gratuitas.
AMPL Uma linguagem de modelagem popular para otimização linear em grande escala, inteira mista e não linear com uma versão limitada gratuita do aluno disponível (500 variáveis ​​e 500 restrições).
APMonitor API para MATLAB e Python. Resolva problemas de programação linear (LP) de exemplo por meio de MATLAB, Python ou uma interface da web.
CPLEX Solver popular com API para várias linguagens de programação, e também possui linguagem de modelagem e funciona com AIMMS, AMPL, GAMS , MPL, OpenOpt, OPL Development Studio e TOMLAB . Gratuito para uso acadêmico.
Função Excel Solver Um solucionador não linear ajustado para planilhas nas quais as avaliações das funções são baseadas nas células recalculadas. Versão básica disponível como complemento padrão para Excel.
FortMP
GAMS
Gurobi Solver com algoritmos paralelos para programas lineares de grande escala, programas quadráticos e programas de número inteiro misto. Gratuito para uso acadêmico.
Bibliotecas Numéricas IMSL Coleções de algoritmos matemáticos e estatísticos disponíveis em C / C ++, Fortran, Java e C # /. NET. As rotinas de otimização nas Bibliotecas IMSL incluem minimizações ilimitadas, linearmente e não linearmente restritas e algoritmos de programação linear.
LINDO Solver com API para otimização em larga escala de programas lineares, inteiros, quadráticos, cônicos e não lineares gerais com extensões de programação estocástica. Ele oferece um procedimento de otimização global para encontrar uma solução globalmente ótima garantida para programas não lineares gerais com variáveis ​​contínuas e discretas. Ele também possui uma API de amostragem estatística para integrar simulações de Monte-Carlo em uma estrutura de otimização. Possui uma linguagem de modelagem algébrica ( LINGO ) e permite modelar dentro de uma planilha ( What'sBest ).
Bordo Uma linguagem de programação de uso geral para computação simbólica e numérica.
MATLAB Uma linguagem de programação de uso geral e orientada a matrizes para computação numérica. A programação linear no MATLAB requer a Caixa de Ferramentas de Otimização além do produto MATLAB base; as rotinas disponíveis incluem INTLINPROG e LINPROG
Mathcad Um editor de matemática WYSIWYG. Ele tem funções para resolver problemas de otimização linear e não linear.
Mathematica Uma linguagem de programação de propósito geral para matemática, incluindo recursos simbólicos e numéricos.
MOSEK Um solucionador para otimização em grande escala com API para várias linguagens (C ++, java, .net, Matlab e python).
Biblioteca Numérica NAG Uma coleção de rotinas matemáticas e estatísticas desenvolvidas pelo Numerical Algorithms Group para múltiplas linguagens de programação (C, C ++, Fortran, Visual Basic, Java e C #) e pacotes (MATLAB, Excel, R, LabVIEW). O capítulo Otimização da Biblioteca NAG inclui rotinas para problemas de programação linear com matrizes de restrição linear esparsas e não esparsas, juntamente com rotinas para a otimização de quadráticas, não lineares, somas de quadrados de funções lineares ou não lineares com não lineares, limitadas ou sem restrições . A biblioteca NAG tem rotinas para otimização local e global e para problemas contínuos ou inteiros.
OptimJ Uma linguagem de modelagem baseada em Java para otimização com uma versão gratuita disponível.
SAS / OR Um conjunto de solucionadores para otimização linear, inteira, não linear, livre de derivativos, rede, combinatória e de restrição; a linguagem de modelagem algébrica OPTMODEL ; e uma variedade de soluções verticais dirigidas a problemas / mercados específicos, todas totalmente integradas com o Sistema SAS .
SCIP Um solucionador de programação inteira de restrição de propósito geral com ênfase em MIP. Compatível com a linguagem de modelagem Zimpl . Gratuito para uso acadêmico e disponível em código-fonte.
XPRESS Solver para programas lineares de grande escala, programas quadráticos, programas gerais não lineares e de inteiros mistos. Possui API para diversas linguagens de programação, possui também uma linguagem de modelagem Mosel e trabalha com AMPL, GAMS . Gratuito para uso acadêmico.
VisSim Uma linguagem de diagrama de bloco visual para simulação de sistemas dinâmicos .

Veja também

Notas

Referências

Leitura adicional

links externos