a który to chcemy nieco zmodyfikować w taki sposób, aby uzyskać pewien nowy układ równań, posiadający pewne dokładne (jednoznaczne, w pewnym sensie) rozwiązanie – przy czym naszym najistotniejszym celem, jest uzyskanie jak najbardziej rzadkiego rozwiązania, w sensie normy .
Niniejsza wersja problemu poszukiwania reprezentacji bazowej, jak też i wiele innych, analogicznych – w pewien sposób – do niniejszej postaci tego problemu; może zostać zapisanych jako pewne problemy programowania liniowego o czasie wielomianowym (i vice versa); co oznacza jednocześnie, że te dwa typy problemów, są względem siebie wielomianowo równoważne (ang. polynomially equivalent).
Zastosowanie do programowania liniowego Problem poszukiwania reprezentacji bazowej można przetłumaczyć na język programowania liniowego, w pierwszej kolejności zauważając, że mamy – w istocie:
przy czym . Powyższa konstrukcja bierze się z położenia (kładziemy): ; przy czym sens tej „zmiany oznaczeń” jest taki, że wartość wyrażenia powinna mieścić się odpowiednio pod oznaczeniem , bądź oznaczeniem , w zależności od tego, czy samo jest większe, czy też mniejsze, od zera.
Przypisy
Kategoria:Programowanie liniowe Kategoria:Metody numeryczne Kategoria:Metody optymalizacji