Autor: Maksymilian Grab

Spośród wszystkich metod matematyki stosowanej metody optymalizacji są jedną z najczęściej wykorzystywanych w innych dyscyplinach ludzkiej działalności. Od zarządzania łańcuchami dostaw poprzez dobór portfolio instrumentów finansowych aż do treningu modeli sztucznej inteligencji metody optymalizacji są z powodzeniem używane do wsparcia w procesach decyzyjnych. Spośród wszystkich metod optymalizacji natomiast metody optymalizacji liniowej wyróżniają się prostotą sformułowania problemu. Jednocześnie pomimo tej prostoty rozwój algorytmów optymalizacji liniowej wciąż stanowi aktywny obszar badań naukowych (o czym Czytelnik przekonać się może przeglądając daty niektórych publikacji artykułów cytowanych na końcu niniejszego opracowania).
Narzędzia oparte na metodach optymalizacji są również wykorzystywane od lat w energetyce (klasycznych przykładów w elektroenergetyce dostarczają prace [17], [8], [1]). Projekt Nauka dla Społeczeństwa korzysta z tej bogatej spuścizny dostarczając narzędzie ZefirLib dla Samorządów, którego funkcjonalności umożliwiają wsparcie zaspokajania potrzeb energetycznych Jednostek Samorządu Terytorialnego w horyzoncie długoterminowym [5].
Celem niniejszego opracowania jest przystępne przedstawienie problemu optymalizacji liniowej i krótki przegląd metod służących jego rozwiązywaniu. Pierwsza część skupia się na wyjaśnieniu pojęć oraz na odniesieniu ich do wybranych elementów problemu optymalizacji stosowanego w narzędziu ZefirLib dla Samorządów. W drugiej części znajduje się panoramiczny przegląd istniejących metod.

1    Programowanie liniowe

1.1    Terminologia
Centralne zagadnienie w dziedzinie optymalizacji liniowej można w ogólności sformułować w następu-jący sposób:
Problem programowania liniowego (albo po prostu problem liniowy). Dane są parametry

będące liczbami rzeczywistymi. Należy znaleźć liczby rzeczywiste x1, . . . , xn spełniające warunki:

 
dla których wyrażenie:
 

przyjmuje wartość najmniejszą.
 

Niektórzy formułują problem programowania liniowego jako problem maksymalizacji wyrażenia (3). Zauważmy jednak, że zastępując w powyższym wyrażeniu wszystkie parametry c_i przez −c_i, otrzymujemy zadanie równoważne maksymalizacji wyrażenia (3). Oznaczmy to wyrażenie poprzez L(x). Funkcję, która argumentowi x przypisuje wartość L(x) nazywa się funkcją celu (a czasem - w przypadku problemu minimalizacji - funkcją kosztu) dla danego problemu programowania liniowego. Innymi słowy, rozwiązanie problemu programowania liniowego polega na minimalizacji funkcji celu (minimalizacji kosztu), przy warunkach zadanych równaniami i nierównościami (1)-(2). Warunki takie nazywa się ograniczeniami (w przypadku problemu liniowego - ograniczeniami liniowymi) zaś zbiór zestawów wartości xi spełniających te warunki - rozwiązaniami dopuszczalnymi problemu liniowego.

Optymalizacja liniowa dostarcza metod rozwiązywania tak rozumianych problemów programowania liniowego. Odnotujmy, że w ogólności istnieją również inne gałęzie dziedziny jaką jest optymalizacja. Gałęzie te mają analogicznie sformułowane problemy programowania matematycznego, które przyjmują bardziej konkretne nazwy w zależności od klasy funkcji matematycznych użytych przy formułowaniu funkcji celu i ograniczeń a także w zależności od dopuszczalnych rozwiązań. I tak mówi się np. o optymalizacji wypukłej czy programowaniu kwadratowym albo całkowitym. Do końca niniejszego opracowaniu koncentrujemy się na optymalizacji liniowej.

Ze względu na to, że w praktyce optymalizację liniową stosuje się do rozwiązywania zagadnień świata „prawdziwego" - pozamatematycznego - problem programowania liniowego nazywa się czasem również modelem liniowym, aby podkreślić, że stanowi on matematyczną reprezentację pewnego zagadnienia z rzeczywistości. Sam proces doboru odpowiednich parametrów a_ij, b_j, a′, b′ , c_k reprezentujących to zagadnienie „prawdziwego", pozamatematycznego świata, które chcielibyśmy rozwiązać przy użyciu matematycznych metod optymalizacji liniowej można więc (i często tak się robi) nazwać procesem modelowania. Zauważmy przy tym, że nie jest to jedyne znaczenie sformułowania modelowanie matematyczne, jakie funkcjonuje w języku polskim. W ogólności istnieją wszak również inne stosowane gałęzie matematyki, które również definiują pojęcie modelu w zupełnie inny, nie równoważny, lecz również potencjalnie pożyteczny dla innego zakresu zagadnień sposób (np. statystyka matematyczna). W tym opracowaniu jak zostało już powiedziane skupiamy się na modelowaniu w tym węższym sensie metod optymalizacji liniowej.
 

1.2    Przykład

Skoro już określiliśmy czym modelowanie jest, zaangażujmy się w tę praktykę, aby zrozumieć ją lepiej na przykładzie. Konkretniej, nawiązując do [5] zastanówmy się od czego można zacząć formułowanie problemu programowania liniowego użytecznego na potrzeby wsparcia zaspokajania potrzeb energetycznych Jednostek Samorządu Terytorialnego w horyzoncie długoterminowym.

Zastrzegamy na wstępie, że z konieczności ujęcie zagadnienia w tym rozdziale będzie znacznie uproszczoną wersją modelu faktycznie stosowanego w [5]. Mamy jednak nadzieję, że uproszczenia te pozwolą ułatwić Czytelnikowi odbiór ilustrowanego przykładowego procesu modelowania. Z ekspertami dziedzinowymi natomiast łączymy się w ubolewaniu, że formuła krótkiego artykułu popularyzatorskiego nie pozwala na ujęcie tematu w sposób oddający pełnię jego głębi.

Przy tych ważnych zastrzeżeniach postawmy sobie za zadanie zaplanowanie inwestycji i punktów pracy wybudowanych urządzeń tak aby zapewnić mieszkańcom bezpieczeństwo dostaw energii cieplnej (c.o. i ciepła woda użytkowa) po możliwie najniższych kosztach w pewnym horyzoncie czasowym.

Funkcja celu będzie dla nas (zgodnie ze swoją alternatywną nazwą) przedstawiała całkowity koszt jaki poniesiemy w naszym przedsięwzięciu zapewnienia ciepła mieszkańcom. Koszt ten możemy zapisać jako sumę:

gdzie:
•    indeks u reprezentuje poszczególne urządzenia/instalacje u biorące udział w wytwarzaniu ciepła (np. ciepłownie, pompy ciepła),
•    indeks t reprezentuje poszczególne jednostki czasu t (np. godziny) w całym horyzoncie czasowym naszego modelu
•    CAPEX(u, t) = C_u,t · BW_u,t oznacza koszt jednostkowy rozbudowy jednostki/magazynu u w czasie t pomnożony przez budowany wymiar jednostki/magazynu u w czasie t,
•    OPEX(u, t) = O_u,t · IW_u,t oznacza jednostkowy koszt operacyjny stały utrzymania urządzenia u
w czasie t pomnożony przez istniejący wymiar urządzenia u w czasie t,
•    VarCost(u, t) = V_u,t · PP_u,t oznacza koszt jednostkowy pracy przez urządzenie u w czasie t pomnożony przez punkt pracy jednostki u w czasie t.

W tym przypadku wartości BW_u,t, IW_u,t, PP_u,t stanowią odpowiedniki wartości x_i ze sformułowania w poprzednim podrozdziale. Są to argumenty funkcji celu - niewiadome, które będziemy chcieli wyznaczyć w taki sposób by zminimalizować wartość funkcji celu (czyli koszt przedsięwzięcia), przy jednoczesnym zachowaniu dodatkowych warunków. Warunki te musimy w następnym kroku naszego procesu modelowania określić tłumacząc wymogi świata rzeczywistego na język matematyki.

Zauważmy, że obrana przez nas funkcja celu faktycznie ma postać taką jak w ogólnym sformułowaniu problemu liniowego w poprzednim rozdziale - jest to suma znanych parametrów (w tym wypadku kosztów jednostkowych) przemnożonych przez szukane wartości zmiennych.

Idąc dalej w naszym procesie modelowania powinniśmy uwzględnić zadanie jakie sobie postawiliśmy, polega ono na zaspokojeniu potrzeb energetycznych mieszkańców samorządu. Spróbujmy sformułować stosowne ograniczenie, które będzie odpowiadało spełnieniu tego zadania:

gdzie:
•    Z_c,t to całkowite zapotrzebowanie na ciepło w jednostce czasu t,
•      to całkowita produkcja ciepła przez nasze urządzenia. Wyraża się ona jako suma współczynników efektywności (uwzględniających sprawności urządzeń i straty na przesyle energii do odbiorców) przemnożonych przez punkty pracy poszczególnych urządzeń u.

Ograniczenie (5) nazywamy równaniem bilansu. Poza zaspokajaniem zapotrzebowania na ciepło nasz model powinien również uwzględniać możliwości techniczne naszego parku wytwórczego. Najbardziej oczywistym ograniczeniem tego rodzaju jest tutaj uwzględnienie możliwości produkcyjnych poprzez ograniczenia na punkty pracy:

gdzie MZ_u,t oznacza tutaj moc zainstalowaną urządzenia u w czasie t.

W ramach samodzielnej eksploracji rozpoczętego wspólnie procesu modelowania proponujemy Czytelnikowi wyzwanie w postaci pytania - w jaki sposób wyglądałyby ograniczenia pozwalające uwzględnić w naszym modelu pracę magazynów ciepła?
 

2    Metody rozwiązywania problemów programowania liniowego
 

W tym rozdziale prezentujemy krótki przegląd istniejących praktycznych metod wraz z odnośnikami do literatury. Czytelnikowi zainteresowanemu praktycznymi aspektami rozwiązywania trudnych problemów programowania liniowego polecamy artykuł [12]. Wyczerpującego (i tak współczesnego jak to możliwe przy obecnym szybkim rozwoju nowych metod pierwszego rzędu) wprowadzenia do tematu optymalizacji (nie tylko liniowej) dostarcza [14].

Metoda sympleks. Najstarsza, lecz wciąż często stosowaną i zaskakująco skuteczna metodą rozwiązywania problemów liniowych to metoda sympleks z ok. 1947 roku [6]. Metoda ta jest upodobana przez wykładowców uniwersyteckich kursów algebry liniowej nie tylko dlatego, że pozwala zastosować teoretyczny materiał wykładu, ale również ze względu na swoją elegancką interpretację geometryczną. Okazuje się bowiem, że zbiór rozwiązań dopuszczalnych stanowi pewien wielowymiarowy wielościan (może on być nieograniczony). Ze względu na to, że funkcja celu jest liniowa dowodzi się, że jeśli wartość minimalna istnieje, to jest ona przyjmowana w wierzchołku takiego wielościanu. Ponieważ wielościan (niezależnie od tego czy jest ograniczony czy nie) ma jedynie skończenie wiele wierzchołków, to narzuca się następująca procedura:

1.    Wyznaczamy jeden wierzchołek.
2.    Sprawdzamy czy wartość funkcji celu w jakimś sąsiadującym wierzchołku jest mniejsza.
3.    Jeśli tak, to idziemy do takiego sąsiedniego wierzchołka i wracamy do poprzedniego punktu.
4.    Jeśli nie, to jesteśmy w minimum funkcji celu w naszym wielościanie - rozwiązaliśmy nasz problem liniowy.

Współcześnie implementowana w solverach komputerowych metoda sympleks jest nieco bardziej zniuansowana (np. poprzez uwzględnienie tzw. problemu dualnego), niemniej powyższa procedura oddaje jej ogólny sens. Czytelnika zainteresowanego współczesnymi wariantami metody sympleks odsyłamy do rozdziału 4 książki [14]

Pewną wadą metody sympleks jest wykładnicza złożoność w przypadku pesymistycznym - liczba wierzchołków wielościanu w przestrzeni n-wymiarowej rośnie bardzo szybko z n i liczbą ograniczeń. Faktycznie w wykazano, że istnieją problemy liniowe dla których metoda sympleks musi odwiedzić wszystkie wierzchołki wielościanu zanim znajdzie ten minimalizujący funkcję celu [11]. Praktyka jednak pokazuje, że w wielu przypadkach metoda sympleks jest bardzo skuteczna, co ma również pewne podstawy teoretyczne [18].

Inną trudnością związaną z metodą sympleks jest fakt, że wędrówka po wierzchołkach wielościanu ma fundamentalnie (nomen omen) liniowy charakter, do którego nie stosują się metody obliczeń równo-ległych, co nie pozwala w pełnie wykorzystywać mocy dzisiejszych wielordzeniowych procesorów CPU czy wielotysięczno-rdzeniowych procesorów graficznych GPU.

Metoda punktu wewnętrznego. Metoda wykorzystywana w większości współczesnych solverów, o niższej złożoności pesymistycznej niż metoda sympleks i pozwalająca w ograniczonym stopniu na zrównoleglenie obliczeń. Pierwszy wariant tej metody został opublikowany w [10]. Od tego czasu powstało wiele kolejnych wersji, praca [9] i rozdział 5 książki [14] zawierają współczesny przegląd tematyki. Motywem przewodnim jest tu przewrotne wprowadzenie nieliniowego składnika (tzw. bariery logarytmicznej) do funkcji celu a następnie zastosowanie metod optymalizacji nieliniowej (twierdzenie Lagrange'a) i sukcesywne zmniejszanie wkładu tego składnika po obliczeniu przybliżonego rozwiązania zmodyfikowanego nieliniowego problemu. Geometryczna interpretacja: podróż od wnętrza wielościanu rozwiązań dopuszczalnych (stąd nazwa metody) w kierunku położonego na brzegu rozwiązania. Poglądowego spojrzenia na metodę punktu wewnętrznego dostarcza [15]. Przykładowe stosowane warianty opublikowano m.in. w [16] i [19].

Metody pierwszego rzędu. Ze względu na „złotą erę" sztucznej inteligencji i wykorzystania procesorów graficznych do wysokowydajnych obliczeń naukowych również optymalizacja liniowa doczekała się metod pozwalających wykorzystać jednostki GPU [13]. Metody te starają się zaangażować potencjał procesorów graficznych do obliczania dużej liczby równoległych operacji iloczynu macierzy przez wektor. Metody te nazywane zbiorczo metodami pierwszego rzędu, stanowią bardzo aktywny obszar badań. Wyróżniającym się algorytmem stopniowo wdrażanym w solverach komercyjnych i tych o otwartym kodzie źródłowym jest rozwijany w Google algorytm PDLP [3], [2]. Metoda ta jest szczególnie polecana w przypadkach, gdy szybkość rozwiązania dużego problemu liniowego ma większe znaczenie niż dokładność (rozwiązania przybliżone w czasie rzeczywistym).

Metody dekompozycji. To rodzina metod, w których rozwiązujący stara się wykorzystać szczególną, blokową postać ograniczeń problemu liniowego. Dekompozycja polega na zastąpieniu jednego problemu kilkoma prostszymi, powiązanymi ze sobą i rozwiązywanymi po kolei w sposób iteracyjny przybliżając się do rozwiązania oryginalnego problemu. Współcześnie metody te stosuje się głównie w przypadku problemów, których wielkość uniemożliwia zastosowanie bezpośrednio innych metod (np. ze względu na ograniczenia dostępnej pamięci). W innym wypadku metody sympleks i punktu wewnętrznego zaimplementowane w najnowszych wersjach solverów gwarantują konkurencyjne czasy rozwiązań przy mniejszym nakładzie czasu poświęconym na implementację dekompozycji przysposobioną pod szczególną postać problemu. Najbardziej znane metody dekompozycji to dekompozycja Dantzig-Wolfe [7] i dekompozycja Bendersa [4].

Bibliografia
[1]    Dennis Anderson. „Models for Determining Least-Cost Investments in Electricity Supply". W: The Bell Journal of Economics and Management Science 3.1 (1972), s. 267-299. (Term. wiz. 31. 03. 2026).
[2]    David Applegate i in. „PDLP: A Practical First-Order Method for Large-Scale Linear Program-ming". W: 2025. URL: https://api.semanticscholar.org/CorpusID:275471116.
[3]    David Applegate i in. „Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient". W: Advances in Neural Information Processing Systems. Red. M. Ranzato i in. T. 34. Curran Associates, Inc., 2021, s. 20243-20257. URL: https://proceedings.neurips.cc/paper_ files/paper/2021/file/a8fbbd3b11424ce032ba813493d95ad7-Paper.pdf.
[4]    J. F. Benders. „Partitioning procedures for solving mixed variables programming problems". W: Numerische Mathematik 3.4 (1962).
[5]    T. Chmiel i in. „Narzędzie "ZefirLib dla Samorządów"we wsparciu transformacji energetycznej samorządów". W: (2026). W przygotowaniu.
[6]    George B. Dantzig. „Origins of the simplex method". W: A Bistory of Scientific Computing. New York, NY, USA: Association for Computing Machinery, 1990, s. 141-151. ISBN: 0201508141. URL: https://doi.org/10.1145/87252.88081.
[7]    George B. Dantzig i Philip Wolfe. „Decomposition Principle for Linear Programs". W: Operations Research 8.1 (1960), s. 101-111.
[8]    Hermann W. Dommel i William F. Tinney. „Optimal Power Flow Solutions". W: IEEE Trans-actions on Power Apparatus and Systems PAS-87.10 (1968), s. 1866-1876.
[9]    Jacek Gondzio. „Interior point methods 25 years later". W: European Journal of Operational Research 218.3 (2012), s. 587-601.
[10]    N. Karmarkar. „A new polynomial-time algorithm for linear programming". W: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing. STOC '84. Association for Computing Machinery, 1984, s. 302-311.
[11]    Victor Klee i George J. Minty. „HOW GOOD IS THE SIMPLEX ALGORITHM". W: 1970. URL:
https://api.semanticscholar.org/CorpusID:117965841.
[12]    Ed Klotz i Alexandra M. Newman. „Practical guidelines for solving difficult linear programs". W: Surveys in Operations Research and Management Science 18.1 (2013), s. 1-17.
[13]    Haihao Lu i Jinwen Yang. „An Overview of GPU-based First-Order Methods for Linear Pro-gramming and Extensions". W: (czer. 2025). DOI: 10.48550/arXiv.2506.02174.
[14]    David G. Luenberger i Yinyu Ye. Linear and Nonlinear Programming. 5th ed. 2021. International Series in Operations Research & Management Science 228. Springer International Publishing, 2021.
[15]    Roy Marsten i in. „Interior Point Methods for Linear Programming: Just Call Newton, Lagrange, and Fiacco and McCormick!" W: Interfaces 20.4 (1990), s. 105-116.
[16]    Sanjay Mehrotra. „On the Implementation of a Primal-Dual Interior Point Method". W: SIAM Journal on Optimization 2.4 (1992), s. 575-601.
[17]    John A. Muckstadt i Richard C Wilson. „An Application of Mixed-Integer Programming Duality to Scheduling Thermal Generating Systems". W: IEEE Transactions on Power Apparatus and Systems PAS-87.12 (1968), s. 1968-1978.
[18]    Daniel Spielman i Shang-Hua Teng. „Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time". W: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. STOC '01. Hersonissos, Greece: Association for Computing Machinery, 2001, s. 296-305. ISBN: 1581133499. DOI: 10.1145/380752.380813. URL: https://doi.org/10.1145/380752.380813.
[19]    Filippo Zanetti i Jacek Gondzio. „A factorisation-based regularised interior point method using the augmented system". W: 2025. URL: https : / / api . semanticscholar . org / CorpusID : 280537020.
 

Publikacja dofinansowana ze środków budżetu państwa w ramach programu Ministra Nauki i Szkolnictwa Wyższego pod nazwą „Nauka dla Społeczeństwa II” nr projektu NdS-II/SN/0073/2023/01 kwota dofinansowania 1 500 000 zł całkowita wartość projektu 1 500 000 zł.