Zmniejszony koszt
W programowaniu liniowym koszt zredukowany lub koszt alternatywny to ilość, o jaką współczynnik funkcji celu musiałby się poprawić (a więc zwiększyć w przypadku problemu maksymalizacji, zmniejszyć w przypadku problemu minimalizacji), zanim odpowiednia zmienna będzie mogła przyjąć wartość dodatnią w optymalnym rozwiązaniu. Jest to koszt zwiększenia zmiennej o niewielką wartość, czyli pierwszą pochodną z pewnego punktu wielościanu to ogranicza problem. Kiedy punktem jest wierzchołek wielościanu, zmienną o najbardziej ekstremalnym koszcie, ujemnie w przypadku minimalizacji i dodatniej maksymalizacji, czasami nazywa się najbardziej stromą krawędzią .
system minimalizacji, z zastrzeżeniem , wektor kosztów obniżonych można obliczyć jako do , gdzie podwójnych kosztów.
Wynika z tego bezpośrednio, że w przypadku problemu minimalizacji wszelkie zmienne niepodstawowe w ich dolnych granicach ze ściśle ujemnymi kosztami obniżonymi mogą zostać wprowadzone do tej podstawy, podczas gdy wszelkie zmienne podstawowe muszą mieć zredukowany koszt równy dokładnie 0. W przypadku problemu maksymalizacji zmienne niepodstawowe w swoich dolnych granicach, które kwalifikują się do wprowadzenia do podstawy, mają ściśle dodatni koszt obniżony.
Interpretacja
W przypadku, gdy x i y są optymalne, obniżone koszty mogą pomóc wyjaśnić, dlaczego zmienne osiągają taką wartość, jaką osiągają. Dla każdej zmiennej odpowiednia suma tych elementów daje pokaz obniżonych kosztów, które ograniczenia wymuszają zmianę wartości zmiennej w górę i w dół. W przypadku zmiennych niepodstawowych odległość do zera daje minimalną zmianę współczynnika obiektu powodującą zmianę wektora rozwiązania x.
W strategii obrotowej
W zasadzie dobrą strategią przestawną byłoby wybranie tej zmiennej, która ma najbardziej obniżony koszt. Jednak najbardziej stroma krawędź może ostatecznie nie być najbardziej atrakcyjna, ponieważ może być bardzo krótka, co zapewnia jedynie niewielką poprawę wartości funkcji obiektu. Z obliczeniowego punktu widzenia innym problemem jest to, że aby obliczyć najbardziej stromą krawędź, należy obliczyć iloczyn wewnętrzny dla każdej zmiennej w systemie, co w wielu przypadkach powoduje, że koszt obliczeń jest zbyt wysoki. Algorytm Devex próbuje przezwyciężyć ten ostatni problem, szacując obniżone koszty, zamiast obliczać je na każdym etapie obrotu, wykorzystując fakt, że krok obrotu może nie zmienić radykalnie obniżonych kosztów wszystkich zmiennych.
W programowaniu liniowym
UWAGA: To jest bezpośredni cytat z witryny internetowej, do której link znajduje się poniżej: „Z każdą zmienną wiąże się obniżona wartość kosztu. Jednak obniżona wartość kosztu jest niezerowa tylko wtedy, gdy optymalna wartość zmiennej wynosi zero. Dość intuicyjny sposób myślenie o zmiennej kosztu obniżonego oznacza myślenie o niej jako o wskazaniu, o ile koszt działania reprezentowanego przez zmienną musi zostać obniżony, zanim jakakolwiek czynność zostanie wykonana.
... obniżona wartość kosztu wskazuje, o ile należy poprawić współczynnik funkcji celu odpowiedniej zmiennej, aby wartość zmiennej w rozwiązaniu optymalnym była dodatnia.
W przypadku problemu minimalizacji „poprawiony” oznacza „zmniejszony”. Zatem w przypadku problemu minimalizacji kosztów, gdzie współczynniki funkcji celu reprezentują koszt jednostkowy działań reprezentowanych przez zmienne, współczynniki „kosztu obniżonego” wskazują, o ile każdy współczynnik kosztu musiałby zostać obniżony, zanim działanie reprezentowane przez odpowiednią zmienną byłoby opłacalne. W przypadku problemu maksymalizacji „poprawiony” oznacza „zwiększony”. W tym przypadku, gdzie na przykład współczynnik funkcji celu może reprezentować zysk netto na jednostkę działalności. Wartość kosztu obniżonego wskazuje, o ile należałoby zwiększyć rentowność działania, aby działanie mogło nastąpić w rozwiązaniu optymalnym. Jednostki wartości kosztów obniżonych są takie same, jak jednostki odpowiednich współczynników funkcji celu.
Jeśli optymalna wartość zmiennej jest dodatnia (nie zerowa), wówczas koszt obniżony wynosi zawsze zero. Jeśli optymalna wartość zmiennej wynosi zero, a koszt obniżony odpowiadający tej zmiennej również wynosi zero, to istnieje co najmniej jeden inny narożnik, który również znajduje się w rozwiązaniu optymalnym. Wartość tej zmiennej będzie dodatnia w jednym z pozostałych optymalnych narożników.