Menu



Exportar registro bibliográfico

Tese

Alguns aspectos de dualidade em programação matemática (1972)

  • Authors:
  • Autor USP: HUMES JUNIOR, CARLOS - EP
  • Unidade: EP
  • Sigla do Departamento: PEL
  • Assunto: PROGRAMAÇÃO MATEMÁTICA
  • Language: Português
  • Abstract: Dualidade em problemas de otimização tem sido estudada desde as origens da programação linear e não linear. Muito tem sido discutido e escrito sobre o assunto, principalmente nos últimos anos. Deste modo tem surgido um extenso corpo de conhecimento, corpo este ainda não totalmente unificado. Este aspecto de falta de unificação torna-se claro durante este trabalho, pois são apresentados aqui duas diferentes formulações de problema dual (formulações de Wolfe e de Rockafellar). Um outro enfoque que poderia ser dados, não apresentado neste trabalho, é o enfoque de desigualdades duais (ver Duffin (4)). Porém, mesmo dentro da formulação de Rockafellar, um único problema de minimização pode ser dualizado de diferentes formas. Esta aparente imprecisão em dualidade é, na realidade, um dos campos de pesquisa que parece ser dos mais frutíferos, pois, utilizando as propriedades das funções em jogo em um dados problema, é possível que possamos construir um problema dual mais facilmente estudável ou solúvel. Esta ideia, de vários duais possíveis, já foi explorada em programação linear, e atualmente tem adquirido importância em programação geométrica. No campo de programação linear encontramos os maiores usos, implícitos ou explícitos , de dualidade. O princípio de decomposição de Dantzig-Wolfe, aplicado a sistemas de controle de vários níveis pode ser visto como uma decomposição baseada em dualidade. Esta ideia pode ser generalizada para certos problemas não lineares (p. ex., Lasdon (17). Tipicamente, em programação linear, obtemos a solução do problema dual como subproduto da solução do problema primal. Este subproduto é obtido em vários algoritmos (mesmo para casos não lineares, e um estudo de dualidade revela o significado de tais grandezas, (ver, p. ex., Gale (7)), que podem ser utilizadas para, por exemplo, estudo desensibilidade. Muitas vezes, é possível substituir um dado problema (ou, subproblema) por um problema dual, de solução mais simples ou então, passível de solução por método conhecido. Este é o caso de sistemas de grande porte, onde o problema inicial é decomposto em vários subproblemas. Estes subproblemas não são, normalmente, obedientes aos moldes clássicos de programação matemática, uma vez que a função objetivo e o conjunto de pontos só pode ser descrito indiretamente, em termos de outros subproblemas. Este tipo de problema, em certos casos, é passível de tratamento através de dualidade, devido aos vários desenvolvimentos de caráter abstrato, obtidos nos últimos anos. Dentro desta linha, especula-se da aplicação de dualidade a problemas originados de controle ótimo. Uma aplicação menos geral, porém de imenso valor, é a de determinação de aproximação de valor ótimo. Isto é, muitas vezes, a presença de um problema dual permite determinar um limite inferior para o valor ótimo do problema que desejamos resolver. Normalmente, dentro de um processo computacional, tal limite inferior é refinado ao longo da computação e nos dá um bom critério de terminação. Este tipo de procedimento é, por exemplo, a base da programação geométrica. Apesar de todas estas considerações e do uso de dualidade para algoritmos de otimização, nossa opinião é a mesma que a de Rockafellar: “Dualidade é útil e válida fundamentalmente como uma ferramenta conceitual para entender problemas de otimização e descobrir suas propriedade maisprofundas". (referência26). Esta consideração expressa a razão pela qual nos dedicamos a este trabalho. De certa forma, a ambiciosa pergunta que originou este estudo foi “qual o papel que convexidade desempenha nos problemas de otimização?”. A hipótese de convexidade é utilizada para caracterizar soluções ótimas globais dos problemas de minimização, e, quase sempre esta caracterização também pode ser feita utilizando dualidade. Dentro deste espírito, procuramos desenvolver um trabalho onde evitássemos, o mais possível, as hipóteses de convexidade, sendo os resultados sob estas hipóteses obtidos como casos particulares. Por outro lado, procuramos apresentar o campo de dualidade em programação matemática, obedecendo a um compromisso de extensão e de um mínimo de didática, e cobrindo um amplo subcampo dos resultados mais importantes encontrados na literatura.
  • Imprenta:
  • Data da defesa: 07.08.1972
    • How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      HUMES JÚNIOR, Carlos. Alguns aspectos de dualidade em programação matemática. 1972. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1972. . Acesso em: 27 set. 2024.

    • APA

      Humes Júnior, C. (1972). Alguns aspectos de dualidade em programação matemática (Dissertação (Mestrado). Universidade de São Paulo, São Paulo.

    • NLM

      Humes Júnior C. Alguns aspectos de dualidade em programação matemática. 1972 ;[citado 2024 set. 27 ]

    • Vancouver

      Humes Júnior C. Alguns aspectos de dualidade em programação matemática. 1972 ;[citado 2024 set. 27 ]

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2024