Programação linear

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar
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 . O ótimo da função de custo linear é onde a linha vermelha cruza o polígono. A linha vermelha é um conjunto de níveis da função de custo e a seta indica a direção na qual estamos otimizando.
Uma região factível fechada de um problema com três variáveis ​​é um poliedro convexo . As superfícies que dão 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 esteja no plano com o maior valor possível.

A programação linear ( PL , também chamada de otimização linear ) é um método para alcançar o melhor resultado (como lucro máximo ou menor custo) 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 a restrições de igualdade linear e desigualdade linear . Sua região viável é um politopo convexo , que é um conjunto definido como a interseção de um número finito de meios espaços , cada um dos quais é definido por uma desigualdade linear. Sua função objetivo é uma função afim (linear) de valor real 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 de forma canônica como

Aqui os componentes de x são as variáveis ​​a serem determinadas, c e b são vetores dados (comindicando que os coeficientes de c são usados ​​como uma matriz de linha única com a finalidade 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 . As desigualdades A x  ≤  b e x0 são as restrições que especificam um politopo convexo sobre o qual a função objetivo deve ser otimizada. Nesse contexto, dois vetores são comparáveis ​​quando possuem as mesmas dimensões. Se cada entrada no primeiro for menor ou igual à entrada correspondente no segundo, 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. As indústrias que usam modelos de programação linear incluem transporte, energia, telecomunicações e manufatura. Ele provou ser útil na modelagem de diversos tipos de problemas em planejamento , roteamento , agendamento , 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ê-las, [1] e que deu nome ao método de eliminação de Fourier-Motzkin .

Em 1939, uma formulação de programação linear de um problema que é 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. [2] É uma forma que ele desenvolveu, durante a Segunda Guerra Mundial , para planejar gastos e retornos a fim de reduzir custos do exército e aumentar as perdas impostas ao inimigo. [ carece de fontes ] O trabalho de Kantorovich foi inicialmente negligenciado na URSS . [3] Na mesma época que Kantorovich, o economista holandês-americano TC Koopmans formularam problemas econômicos clássicos como programas lineares. Kantorovich e Koopmans mais tarde dividiram o prêmio Nobel de economia de 1975 . [1] 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 . [2] 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 EUA. [4] Em 1947, Dantzig também inventou o método simplex que, pela primeira vez, abordou eficientemente o problema de programação linear na maioria dos casos. [4] Quando Dantzig marcou uma reunião com John von Neumann para discutir seu método simplex, Neumann imediatamente conjeturou a teoria da dualidade ao perceber que o problema que ele estava trabalhando na teoria dos jogos era equivalente. [4] Dantzig forneceu prova formal em um relatório não publicado "Um Teorema sobre Desigualdades Lineares" em 5 de janeiro de 1948.[3] 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 atribuição de 70 pessoas para 70 empregos. O poder computacional 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, colocando 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, [5] 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 programação linear. problemas. [6]

Usa

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. [3] Certos casos especiais de programação linear, como problemas de fluxo de rede e problemas de fluxo multicommodity são considerados importantes o suficiente para gerar muitas pesquisas sobre algoritmos especializados para sua solução. Vários algoritmos para outros tipos de problemas de otimização funcionam resolvendo problemas de PL 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 das empresas, como planejamento, produção, transporte, tecnologia e outras questões. Embora as questões de gestão moderna 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 vídeos do YouTube. [7] Portanto, muitos problemas podem ser caracterizados como problemas de programação linear.

Formulário padrão

A forma padrão é a forma usual e mais intuitiva de descrever um problema de programação linear. É composto pelas 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 agricultor tenha um pedaço de terra, 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, quilogramas F , e pesticida, quilogramas P. 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 2seja o preço de venda da cevada. Se denotarmos a área de terra plantada com trigo e cevada por x 1 e x 2 respectivamente, então o lucro pode ser maximizado escolhendo valores ótimos 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 (o total de vendas de trigo mais o total de vendas de cevada) - receita é a "função objetivo")
Sujeito a: (limite na área total)
(limite de fertilizantes)
(limite de pesticidas)
(não pode plantar uma área negativa).

Na forma matricial isso se torna:

maximizar
sujeito a

Formulário aumentado (formulário slack)

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

Maximizar:

Ondesã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)

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

Na forma matricial isso se torna:

Maximizar:

Dualidade

Todo problema de programação linear, conhecido como problema primal , pode ser convertido em um problema dual , que fornece um limite superior para o valor ótimo do problema primal. Na forma matricial, podemos expressar o problema primal 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.

Há duas ideias 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, então o primal deve ser inviável. No entanto, é possível que tanto o dual quanto o primal sejam inviáveis. Veja programa linear duplo para detalhes e vários outros exemplos.

Variações

Dualidades de cobertura/empacotamento

Um LP de cobertura é um programa linear da forma:

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

tal que a matriz A e os vetores b e c são não negativos.

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

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

tal que a matriz A e os vetores b e c são não negativos.

Exemplos

PLs de cobertura e empacotamento geralmente surgem como um relaxamento de programação linear de um problema combinatório e são importantes no estudo de algoritmos de aproximação . [8] Por exemplo, as relaxações LP do problema de empacotamento de conjuntos , o problema de conjuntos independentes e o problema de emparelhamento são LPs de empacotamento. As relaxações LP do problema de cobertura de conjuntos , o problema de cobertura de vértices e o problema de conjunto dominante também cobrem PLs.

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

Folga 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 factível primal e que y  = ( y 1y 2 , ... ,  y m ) seja factível dual. Sejam ( w 1w 2 , ...,  w m ) as variáveis ​​de folga primárias correspondentes, e sejam ( z 1z 2 , ... ,  z n ) as variáveis ​​de folga duplas correspondentes. Então x e ysão ótimas 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 for zero, então a i -ésima variável do dual será igual a zero. Da mesma forma, se a j -th variável de folga do dual não for zero, então a j -th variável do primal será 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, há "sobras"), então quantidades adicionais desse recurso não devem ter valor. Da mesma forma, se houver folga no requisito de restrição de não negatividade de preço duplo (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 factí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 .

Uma solução ótima não precisa existir, por duas razões. Primeiro, se as restrições são inconsistentes, então não existe solução viável: Por exemplo, as restrições x  ≥ 2 ex  ≤ 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 ótimo é alcançado porque é sempre possível fazer melhor do que qualquer valor finito da função objetivo.

Vértices ótimos (e raios) de poliedros

Caso contrário, se existe uma solução viável e se o conjunto de restrições é limitado, então o valor ótimo é sempre obtido na fronteira 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), uma vez que as funções lineares 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 que assume 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 toda combinação convexa das soluções é uma solução.

Os vértices do politopo também são chamados de soluções viáveis ​​básicas . A razão para esta escolha de nome é a seguinte. Seja d o número de variáveis. Então o teorema fundamental das desigualdades lineares implica (para problemas factíveis) que para cada vértice x * da região factível do 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 única solução é x * . Assim, podemos estudar esses vértices olhando para certos subconjuntos do conjunto de todas as restrições (um conjunto discreto), em vez do contínuo de soluções PL. Este princípio fundamenta aalgoritmo 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, esta 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 PL construindo uma solução viável em um vértice do politopo e então percorrendo um caminho nas arestas do politopo até vértices com valores não decrescentes da função objetivo até que um o ideal é alcançado com certeza. Em muitos problemas práticos, ocorre " stalling ": muitos pivôs são feitos sem aumento na função objetivo. [9] [10] Em problemas práticos raros, as versões usuais do algoritmo simplex podem realmente "ciclo". [10] Para evitar ciclos, os pesquisadores desenvolveram novas regras de pivô. [11] [12] [9] [10] [13][14]

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

No entanto, o algoritmo simplex tem um comportamento ruim no pior caso: Klee e Minty construíram uma família de problemas de programação linear para os quais o método simplex leva um número de etapas exponenciais no tamanho do problema. [9] [12] [13] De fato, durante algum tempo não se sabia se o problema de programação linear era solucionável em tempo polinomial , ou seja, de 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 2D de um cubo (perturbado) na dimensão  D , o cubo de Klee–Minty , no pior caso . [14] [17]

Ponto interior

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

Algoritmo 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, este algoritmo é executado emTempo. [5] Leonid Khachiyan resolveu este 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 (de 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 solubilidade em tempo polinomial de programas lineares. O algoritmo não foi um avanço computacional, pois o método simplex é mais eficiente para todos, exceto famílias especialmente construídas de programas lineares.

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 [6] melhorou o limite polinomial de pior caso de Khachiyan [5] (dando). Karmarkar afirmou que seu algoritmo era muito mais rápido em PL prático do que o método simplex, uma afirmação que criou grande interesse em métodos de pontos interiores. [18] 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 roda emTempo. [19]

Algoritmo 89 de Vaidya

Em 1989, Vaidya desenvolveu um algoritmo que roda emTempo. [20] Formalmente falando, o algoritmo levaoperaçõ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 esparsidade de entrada

Em 2015, Lee e Sidford mostraram que isso pode ser resolvido emtempo, [21] onderepresenta o número de elementos diferentes de zero, e permanece tomandona pior das hipóteses.

Algoritmo de tempo de multiplicação da matriz atual

Em 2019, Cohen, Lee e Song melhoraram o tempo de execução paraTempo,é o expoente da multiplicação de matrizes eé o expoente dual da multiplicação de matrizes . [22] é (aproximadamente) definido como o maior número tal que se pode multiplicar ummatriz por ummatriz emTempo. Em um trabalho de acompanhamento de Lee, Song e Zhang, eles reproduzem o mesmo resultado por meio de um método diferente. [23] Esses dois algoritmos permanecemquandoe. O resultado devido a Jiang, Song, Weinstein e Zhang melhoroupara. [24]

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 rotineiras de programação linear. No entanto, para tipos específicos de problemas de PL, pode ser que um tipo de solucionador seja melhor 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. [25]

Problemas em aberto e trabalho recente

Problema não resolvido em 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, cuja solução representaria avanços fundamentais na matemática e avanços potencialmente importantes em nossa capacidade de resolver programas lineares de grande escala.

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

Este conjunto de problemas intimamente relacionados 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 programação linear em tempo polinomial fraco, como os métodos elipsóides e técnicas de pontos interiores , ainda não foram encontrados algoritmos que permitam 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 possibilitasse ganhos práticos na resolução de grandes PLs também.

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 grafos politópicos têm diâmetro limitado polinomialmente?

Essas questões estão relacionadas à 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 executadas 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 a PL pode ser resolvida em tempo fortemente polinomial.

O algoritmo simplex e suas variantes se enquadram na família de algoritmos de acompanhamento de arestas, assim chamados porque resolvem problemas de programação linear movendo-se de vértice para vértice 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 conhecer o diâmetro máximo teórico de grafos de grafos politopais. Foi provado que todos os politopos têm diâmetro subexponencial. A recente refutação da conjectura de Hirsch é o primeiro passo para provar se qualquer politopo tem diâmetro superpolinomial. Se tais politopos existirem, nenhuma variante de acompanhamento de borda poderá ser executada em tempo polinomial. 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 primal viável, dual factível ou primal-e-dual inviável em qualquer ordem. Métodos de pivô desse tipo têm sido estudados desde a década de 1970. [ citação necessária ] Essencialmente, esses métodos tentam encontrar o caminho pivô mais curto no politopo de arranjo sob o problema de programação linear. Em contraste com os grafos politopais, os grafos de politopos de arranjo são conhecidos por terem diâmetro pequeno, permitindo a possibilidade de algoritmos de pivô cruzado em tempo polinomial sem resolver questões sobre o diâmetro de politopos gerais. [14]

Inteiros desconhecidos

Se todas as variáveis ​​desconhecidas precisam ser inteiras, então o problema é chamado de problema de programação inteira (IP) ou programação linear inteira (ILP). Em contraste com a programação linear, que pode ser resolvida eficientemente 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 . Programação inteira 0–1 ou programação inteira binária (BIP) é o caso especial de programação inteira onde as variáveis ​​devem ser 0 ou 1 (em vez de inteiros arbitrários). Este problema também é classificado como NP-difícil, e de fato a versão de decisão foi um dos 21 problemas NP-completos de Karp .

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

Existem no entanto algumas subclasses importantes de problemas IP e MIP que são solucionáveis ​​de forma eficiente, mais notavelmente problemas onde a matriz de restrições é totalmente unimodular e os lados direitos das restrições são inteiros ou – mais geral – onde o sistema tem a integralidade dual total (TDI).

Algoritmos avançados para resolver programas lineares inteiros incluem:

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

Programas lineares integrais

Um programa linear em variáveis ​​reais é dito integral se tiver pelo menos uma solução ótima que seja integral. Da mesma forma, um poliedroé dito integral se para todas as funções objetivo viáveis ​​limitadas c , o programa lineartem um ótimocom 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 número inteiro.

Programas lineares integrais são de importância central no aspecto poliédrico da otimização combinatória , pois fornecem uma caracterização alternativa de um problema. Especificamente, para qualquer problema, o casco convexo das soluções é um poliedro integral; se este poliedro tiver uma descrição agradável/compacta, então podemos encontrar eficientemente a solução viável ótima sob qualquer objetivo linear. Por outro lado, se pudermos provar que uma relaxação de programação linear é integral, então é a descrição desejada da casca convexa 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çadas a serem inteiras, e esse problema é NP-difícil em geral,
  • em um programa linear integral, descrito nesta seção, as variáveis ​​não são restritas a serem inteiras, mas sim provou-se de alguma forma que o problema contínuo sempre tem um valor ótimo integral (assumindo que c é integral), e esse valor ótimo pode ser encontrado de forma eficiente, pois todos os programas lineares de tamanho polinomial podem ser resolvidos em tempo polinomial.

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

Solvers e linguagens de script (programação)

Licenças permissivas :

Nome Licença Informações breves
Gekko Licença MIT Biblioteca de código aberto para resolver otimização de LP, QP , QCQP , NLP e MIP em larga escala
GLOP Apache v2 O 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, inteira mista e não linear em larga escala
Suan Shu 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ções breves
Solucionador de restrições de casuar LGPL um kit de ferramentas de solução de restrição incremental que resolve com eficiência sistemas de igualdades e desigualdades lineares
CLP CPL um solucionador de LP da 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 . Agrupa o tradutor e a linguagem de modelagem GNU MathProg do tipo AMPL .
Qoca GPL uma biblioteca para resolver incrementalmente 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 branch and bound) tem código fonte publicamente disponível [26], mas não é open source.

Licenças proprietárias :

Nome Informações breves
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. Algoritmos, na forma de heurísticas ou métodos exatos, como Branch-and-Cut ou Column Generation, também podem ser implementados. A ferramenta chama um solucionador apropriado, como CPLEX 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, inteira mista e não linear em larga escala com uma versão gratuita limitada para estudantes disponível (500 variáveis ​​e 500 restrições).
Monitor de APM API para MATLAB e Python. Resolva exemplos de problemas de programação linear (LP) por meio de MATLAB, Python ou uma interface da web.
CPLEX Solver popular com uma API para várias linguagens de programação, e também possui uma linguagem de modelagem e funciona com AIMMS, AMPL, GAMS , MPL, OpenOpt, OPL Development Studio e TOMLAB . Gratuito para uso acadêmico.
Função do Solucionador do Excel Um solucionador não linear ajustado a planilhas nas quais as avaliações de funções são baseadas nas células de recálculo. Versão básica disponível como complemento padrão para Excel.
FortMPName
JOGOS
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 irrestritas, com restrições lineares e não lineares e algoritmos de programação linear.
LINDO Solver com uma 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 soluções globalmente ótimas garantidas 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 a modelagem 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 propósito geral e orientada a matrizes para computação numérica. A programação linear no MATLAB requer o Optimization Toolbox além do produto MATLAB base; as rotinas disponíveis incluem INTLINPROG e LINPROG
Mathcad Um editor de matemática WYSIWYG. Possui 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.
MOSEQUE Um solver para otimização em larga escala com API para diversas 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 lineares esparsas e não esparsas, juntamente com rotinas para a otimização de somas quadráticas, não lineares, de quadrados de funções lineares ou não lineares com restrições não lineares, limitadas ou não . A Biblioteca NAG possui 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. [27] [28]
SAS /OU Um conjunto de solucionadores para Otimização Linear, Inteiro, Não-linear, Livre de Derivadas, Rede, Combinatória e de Restrições; a linguagem de modelagem algébrica OPTMODEL; e uma variedade de soluções verticais voltadas para problemas/mercados específicos, todas totalmente integradas ao Sistema SAS .
SCIP Um solucionador de programação inteira de restrições de uso geral com ênfase em MIP. Compatível com a linguagem de modelagem Ziimpl. 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 inteiros mistos. Possui API para diversas linguagens de programação, também possui linguagem de modelagem Mosel e trabalha com AMPL, GAMS . Gratuito para uso acadêmico.
VisSim Uma linguagem visual de diagrama de blocos para simulação de sistemas dinâmicos .

Veja também

Notas

  1. ^ a b Gerard Sierksma; Yori Zwols (2015). Otimização Linear e Inteira: Teoria e Prática (3ª ed.). Imprensa CRC. pág. 1. ISBN 978-1498710169.
  2. ^ a b Alexander Schrijver (1998). Teoria da Programação Linear e Inteira . John Wiley & Filhos. págs. 221-222. ISBN 978-0-471-98232-6.
  3. ^ a b c George B. Dantzig (abril de 1982). "Reminiscências sobre as origens da programação linear" . Cartas de Pesquisa Operacional . 1 (2): 43–48. doi : 10.1016/0167-6377(82)90043-8 .
  4. ^ a b c Dantzig, George B.; Thapa, Mukund Narain (1997). Programação linear . Nova York: Springer. pág. xxvii. ISBN 0387948333. OCLC  35318475 .
  5. ^ a b c Leonid Khachiyan (1979). "Um algoritmo polinomial para programação linear". Doklady Akademii Nauk SSSR . 224 (5): 1093-1096.
  6. ^ a b Narendra Karmarkar (1984). "Um novo algoritmo de tempo polinomial para programação linear". Combinatória . 4 (4): 373–395. doi : 10.1007/BF02579150 . S2CID 7257867 . 
  7. ^ (PDF) https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf . {{cite web}}: ausente ou vazio |title=( ajuda )
  8. ^ Vazirani (2001 , p. 112)
  9. ^ a b c d Dantzig & Thapa (2003)
  10. ^ a b c Padberg (1999)
  11. ^ Bland (1977)
  12. ^ a b Murty (1983)
  13. ^ a b Papadimitriou & Steiglitz
  14. ^ a b c Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (ed.). "Métodos cruzados: uma nova visão sobre algoritmos de pivô". Programação Matemática, Série B . 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . doi : 10.1007/BF02614325 . MR 1464775 . S2CID 2794181 .   
  15. ^ Borgwardt (1987)
  16. ^ Todd (2002)
  17. ^ Roos, C. (1990). "Um exemplo exponencial para a regra pivotante de Terlaky para o método cross-cross simplex". Programação Matemática . Série A. 46 (1): 79–84. doi : 10.1007/BF01585729 . MR 1045573 . S2CID 33463483 .  
  18. ^ Strang, Gilbert (1 de junho de 1987). "Algoritmo de Karmarkar e seu lugar na matemática aplicada". O Inteligente Matemático . 9 (2): 4–10. doi : 10.1007/BF03025891 . ISSN 0343-6993 . MR 0883185 . S2CID 123541868 .   
  19. ^ Vaidya, Pravin M. (1987). Um algoritmo para programação linear que requeroperações aritméticas . 28º Simpósio Anual do IEEE sobre Fundamentos da Ciência da Computação. FOCS.
  20. ^ Vaidya, Pravin M. (1989). Acelerando a programação linear usando a multiplicação de matrizes rápida . 30º Simpósio Anual de Fundamentos da Ciência da Computação. FOCS. doi : 10.1109/SFCS.1989.63499 .
  21. ^ Lee, Yin-Tat; Sidford, Aaron (2015). Manutenção inversa eficiente e algoritmos mais rápidos para programação linear . FOCS '15 Fundamentos da Ciência da Computação. arXiv : 1503.01752 .
  22. ^ Cohen, Michael B.; Lee, Yin-Tat; Canção, Zhao (2018). Resolvendo Programas Lineares no Tempo de Multiplicação da Matriz Atual . 51º Simpósio Anual da ACM sobre Teoria da Computação. STOC'19. arXiv : 1810.07896 .
  23. ^ Lee, Yin-Tat; Canção, Zhao; Zhang, Qiuyi (2019). Resolvendo a minimização do risco empírico no tempo de multiplicação da matriz atual . Conferência sobre Teoria da Aprendizagem. COLT'19. arXiv : 1905.04447 .
  24. ^ Jiang, Shunhua; Canção, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). Faster Dynamic Matrix Inverse para LPs mais rápidos . arXiv : 2004.07470 .
  25. ^ Illes, Tibor; Terlaky, Tamás (2002). "Pivot versus métodos de ponto interior: prós e contras" . Revista Europeia de Pesquisa Operacional . 140 (2): 170. CiteSeerX 10.1.1.646.3539 . doi : 10.1016/S0377-2217(02)00061-9 . 
  26. ^ "COR@L – Pesquisa de Otimização Computacional em Lehigh" . lehigh.edu .
  27. ^ http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ usado em um modelo de otimização para linhas de montagem de modelo misto, Universidade de Münster
  28. ^ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 OptimJ usado em uma técnica de computação de equilíbrio perfeito de subjogo aproximado para jogos repetidos

Referências

Leitura adicional

Links externos