Obecna postać podręcznika powstała jako wynik wieloletniego doświadczenia dydaktycznego autora w prowadzeniu przedmiotu Podstawy optymalizacji na Wydziale Elektroniki Technik Informacyjnych Politechniki Warszawskiej. Istnieje wiele bardzo dobrych książek w języku polskim i angielskim do tego przedmiotu, które będą cytowane w miarę potrzeby, ale odczuwa się jednak brak zawartego ujęcia (szczególnie w języku polskim). Zmienia się też sposób prowadzenia wykładu. Jest bardzo mało prawdopodobne, by obecni studenci zetknęli się z koniecznością pisania oprogramowania implementującego algorytmy optymalizacji. Obecnie istnieje wiele dostępnych pakietów komercyjnych i darmowych oraz środowisk i języków modelowania współpracujących z nimi, które mogą być z powodzeniem wykorzystane. Odpowiednie informacje o dostępnym oprogramowaniu zostały zamieszczone na końcu każdego rozdziału. Efektywne ich użycie wymaga jednak zrozumienia podstawowych idei metod optymalizacyjnych oraz znajomości warunków koniecznych i dostatecznych optymalności. Tym zagadnieniom poświęcono najwięcej uwagi w obecnej wersji książki.

Podręcznik „Wprowadzenie do optymalizacji” jest przeznaczony dla studentów V semestru Wydziału Elektroniki i Technik Informacyjnych i jest dostosowany do programu wykładu i ćwiczeń laboratoryjnych z przedmiotu Podstawy optymalizacji.

Wydaje się, że może być również użyteczny dla studentów innych uczelni w Polsce. Zasadniczym celem jest wprowadzenie czytelnika w zagadnienia optymalizacji w sposób możliwie najbardziej przystępnym, z minimalnym zastosowaniem zaawansowanego aparatu matematycznego. Podręcznik składa się z części wstępnej poświęconej zastosowaniom oraz trzech zasadniczych rozdziałów omawiających: programowanie liniowe, optymalizację bez ograniczeń, optymalizację nieliniową (albo programowanie nieliniowe) z ograniczeniami. Prezentowane zagadnienia są ilustrowane szeregiem rysunków, przykładów i zadań w celu ułatwienia studentom zrozumienia omawianych problemów. Pierwowzorem podręcznika „Wprowadzenie do optymalizacji” były „Podstawy optymalizacji” (patrz Stachurski i Wierzbicki 76). Obecna wersja znacznie różni się od swojego poprzednika mimo podobnego układu. Znacznie większy nacisk położono na warunki konieczne i dostateczne optymalności oraz rolę wypukłości. Zwiększyła się również liczba przykładów, ilustrujących omawiane zagadnienia, do zestawów zadań na końcu każdego rozdziału zostały wprowadzone nowe, przeprowadzono również selekcję poprzednich. Informacje na temat oprogramowania dostępnego w internecie zostały zweryfikowane i uzupełnione.

Rozdział poświęcony zastosowaniom zawiera opisy przykładowych zagadnień rozwiązywanych metodą sformułowania modelu optymalizacyjnego i jego rozwiązania za pomocą metod obliczeniowych optymalizacji. Przykłady są wprowadzane kolejno, rozpoczynając od najprostszych zadań programowania liniowego, aż po zadania wielokrotnej optymalizacji dynamicznej.

W rozdziale drugim omawiane są zagadnienia programowania liniowego, klasyczna jedno- i dwufazowa metoda sympleks, teoria dualności w zagadnieniach programowania liniowego, dualna metoda sympleks oraz metoda punktu wewnętrznego Karmarkara. Rozdział został gruntownie przeredagowany. Zmianie uległ sposób prezentacji metody sympleks, położono większy nacisk na pojęcie rozwiązania bazowego (dopuszczalnego i niedopuszczalnego). Teoria dualności Lagrange’a w programowaniu liniowym jest prezentowana dla ogólnej postaci ograniczeń, co w naturalny sposób pozwoliło wprowadzić dualną metode sympleks. Ostatni podrozdział wprowadza czytelnika w świat internetu - zawiera zaktualizowany, wyczerpujący przegląd dostępnego oprogramowania (darmowego i komercyjnego) oraz stron www poświęconych zagadnieniom programowania liniowego.

Trzeci rozdział rozpoczyna omówienie zastosowań optymalizacji nieliniowej bez ograniczeń. Jako główne dziedziny zastosowań wskazano w nim rozwiązywanie układów równań nieliniowych i problemy identyfikacji nieznanych parametrów modeli (przy wykorzystaniu metody najmniejszych kwadratów) oraz zadania optymalizacji z ograniczeniami. Istotnie rozszerzono informacje na temat zagadnień na temat optymalizacji wypukłej. Pokazano związki prezentowanych warunków koniecznych i dostatecznych optymalności z lokalna wypukłością funkcji celu. Przedstawiono pojęcie jednostajnych kierunków poprawy, testy stopu w niedokładnej minimalizacji kierunkowej. Omówiono typowe metody gradientowe: najszybszego spadku, Newtona, quasi-newtonowskie, metody kierunków sprężonych i gradientów sprężonych, bezgradientową metodę sympleksu Neldera-Meada. Przedstawiono przykłady gradienowych metod minimalizacji kierunkowej oraz złotego podziału niewykorzystującą pochodnych. Rozdział uzupełniono krótkim zestawieniem oprogramowania dostępnego w internecie, które nie występowało w „Podstawach optymaliacji”.

W rozdziale czwartym istotnie rozszerzono zagadnienia warunków koniecznych i dostatecznych optymalności dla różniczkowalnych zadań z ograniczeniami, w szczególności dodano warunki drugiego rzędu. Prezentacja wyników jest bardziej jednorodna. W dowodach twierdzeń precyzujących warunki optymalności wykorzystano funkcje kary i odpowiednie wyniki dotyczące zadań bez ograniczeń. W podrozdziałach poświęconych funkcjom kary dodano twierdzenia o ich zbieżności, wskazano związki miedzy minimami zadania z ograniczeniami i odpowiedniego zadania z karą. Do opisu metody zbiorów ograniczeń aktywnych do rozwiązywania zadań kwadratowych z ograniczeniami nierównościowymi, włączono uzasadnienie, ze generowane kierunki są dopuszczalnymi kierunkami spadku. Omówiono również teorię dualności Lagrange’a oraz algorytmy wielomianowe oparte na wykorzystaniu barierowej funkcji kary do rozwiązywania zadań programowania liniowego. Ta ostatnia jest prezentowana w tym miejscu, ponieważ jej zrozumienie wymaga znajomości teorii dualności, metody Newtona oraz barierowej funkcji kary. Rozdział zamyka omówienie aktualnego stanu oprogramowania oraz stron www dostępnych w internecie.

Spis treści

Rozdział 1. Wprowadzenie

• Problem optymalizacji
• Przykłady praktycznych zadań optymalizacyjnych
• Optymalne planowanie produkcji
• Sieć rezystorów
• Sieci elektryczne
• Przykłady budowy autostrady
• Wystrzelenia rakiety
• Model wzrostu lasu

• Wstęp
• Postać standardowa zadania programowania liniowego
• Metoda sympleks
• Rozwiązania bazowe zadania programowania liniowego
• Wybór zmiennej wprowadzanej do bazy oraz kryterium
• optymalności bazowego rozwiązywania dopuszczalnego
• Wybór zmiennej wyprowadzanej z bazy oraz wykrywanie
• nieograniczoności zadania programowania liniowego
• Algorytm metody sympleks- zapis algebraiczny
• Różne sposoby organizacji obliczeń w metodzie sympleks
• Znajdowanie początkowego punktu dopuszczalnego
• Metoda minimalizacji sumy zmiennych sztucznych
• Technika zmiennych znaków zaproponowana przez Wolfe’a
• Metoda jednofazowa (wielkiego M)
• Przykłady zadań rozwiązywanych dwufazową metodą
• sympleks w wersji tablicowej
• Dualne zadanie Lagrange’a do zadania programowania liniowego
• Przykłady wzajemnie dualnych zadań LP
• Związki między zadaniami prymalnym i dualnym
• programowania liniowego
• Interpretacja ekonomiczna dualności
• Dualna metoda sympleks
• Przebieg k-tej iteracji dualnej metody sympleks
• Analiza i uzasadnienie poszczególnych kroków dualnej
• metodzie sympleks
• Przykłady znajdowania rozwiązań za pomocą dualnej
• metody sympleks
• Zadania transportowe
• Programowanie liniowe – algorytmy o wielomianowym nakładzie
• obliczeń
• Oprogramowanie do rozwiązywania zadań programowania liniowego
• Pakiety powszechnie dostępne
• Pakiety komercyjne i system modelowania
• Zadania z programowania liniowego
• Rozwiązania

• Zastosowania optymalizacji nieliniowej bez ograniczeń
• Zadania identyfikacji
• Układy równań nieliniowych
• Ciągi pomocniczych zadań bez ograniczeń w metodach optymalizacji z ograniczeniami
• Pojęcie rozwiązania optymalnego
• Zadania optymalizacji wypukłej
• Zbiór wypukły
• Funkcje wypukłe
• Własności zadań optymalizacji wypukłej
• Warunki optymalności dla zadań optymalizacji bez ograniczeń
• Warunki konieczne dla funkcji różniczkowalnych
• Warunki dostateczne
• Pojęcie ścisłej dodatniej określoności
• Punkty stacjonarne
• Gradientowe metody kierunków poprawy
• Kierunki poprawy
• Metoda najszybszego spadku
• Metoda Newtona
• Metody newtonowskie z aproksymacją różnicową
• Metody quasi-newtonowskie
• Metody kierunków sprężonych
• Analiza zbieżności
• Testy zatrzymania algorytmu
• Modele kwadratowe
• Lokalna szybkość zbieżności
• Minimalizacja w kierunku
• Metody korzystające z pochodnych
• Algorytm kwadratowych interpolacji i ekstrapolacji
• Bezgradientowe metody minimalizacji w kierunku
• Metoda sympleksu Neldera-Meada jako przykład metody poszukiwań prostych
• Oprogramowanie do rozwiązania układów równań nieliniowych i zadań optymalizacji bez ograniczeń
• Optymalizacja bez ograniczeń
• Estymacja parametrów funkcji nieliniowej metodą najmniejszych kwadratów
• Układy równań nieliniowych
• Zadania z optymalizacji nieliniowej bez ograniczeń
• Rozwiązania

• Warunki optymalności dla zadań optymalizacji nieliniowej z ograniczeniami
• Warunki konieczne optymalności w przypadku zadania z ograniczeniami równościowymi
• Warunki dostateczne optymalności w przypadku zadania
• z ograniczeniami równościowymi
• Warunki konieczne optymalności w przypadku zadania z ograniczeniami równościowymi i nierównościowymi
• Warunki dostateczne optymalności w przypadku zadań z ograniczeniami równościowymi i nierównościowymi
• Warunki regularności
• Dualne zadanie Lagrange’a
• Przykłady zadań wzajemnie dualnych
• Twierdza o dualności
• Dualne zadanie Wolfe’a
• Programowanie kwadratowe
• Zadanie programowania kwadratowego z ograniczeniami równościowymi
• Zadania programowania kwadratowego z ograniczeniami nierównościowymi (metoda zbioru ograniczeń aktywnych)
• Zewnętrzna funkcja kary
• Algorytm metody zewnętrznej funkcji kary
• Typowe przykłady funkcji kary
• Zmienne sprzężone w punkcie optymalnym
• Wewnętrzna funkcja kary
• Mnożnikowe (przesuwanie) funkcje kary
• Ograniczenia równościowe
• Rozszerzona funkcja Lagrange’a dokłądne funkcje kary
• Ograniczenia nierównościowe
• Dokładna funkcja kary typu 
• Algorytm punktu wewnętrznego do rozwiązywania zadań LP
• Oprogramowanie do rozwiązywania zadań optymalizacji nieliniowej
• Zadania z optymalizacji nieliniowej z ograniczeniami
• Rozwiązania
• Bibliografia
• Indeks

które będą cytowane w miarę potrzeby, ale odczuwa się jednak brak zawartego ujęcia (szczególnie w języku polskim). Zmienia się też sposób prowadzenia wykładu. Jest bardzo mało prawdopodobne, by obecni studenci zetknęli się z koniecznością pisania oprogramowania implementującego algorytmy optymalizacji. Obecnie istnieje wiele dostępnych pakietów komercyjnych i darmowych oraz środowisk i języków modelowania współpracujących z nimi, które mogą być z powodzeniem wykorzystane. Odpowiednie informacje o dostępnym oprogramowaniu zostały zamieszczone na końcu każdego rozdziału. Efektywne ich użycie wymaga jednak zrozumienia podstawowych idei metod optymalizacyjnych oraz znajomości warunków koniecznych i dostatecznych optymalności. Tym zagadnieniom poświęcono najwięcej uwagi w obecnej wersji książki.

Podręcznik „Wprowadzenie do optymalizacji” jest przeznaczony dla studentów V semestru Wydziału Elektroniki i Technik Informacyjnych i jest dostosowany do programu wykładu i ćwiczeń laboratoryjnych z przedmiotu Podstawy optymalizacji.

Wydaje się, że może być również użyteczny dla studentów innych uczelni w Polsce. Zasadniczym celem jest wprowadzenie czytelnika w zagadnienia optymalizacji w sposób możliwie najbardziej przystępnym, z minimalnym zastosowaniem zaawansowanego aparatu matematycznego. Podręcznik składa się z części wstępnej poświęconej zastosowaniom oraz trzech zasadniczych rozdziałów omawiających: programowanie liniowe, optymalizację bez ograniczeń, optymalizację nieliniową (albo programowanie nieliniowe) z ograniczeniami. Prezentowane zagadnienia są ilustrowane szeregiem rysunków, przykładów i zadań w celu ułatwienia studentom zrozumienia omawianych problemów. Pierwowzorem podręcznika „Wprowadzenie do optymalizacji” były „Podstawy optymalizacji” (patrz Stachurski i Wierzbicki 76). Obecna wersja znacznie różni się od swojego poprzednika mimo podobnego układu. Znacznie większy nacisk położono na warunki konieczne i dostateczne optymalności oraz rolę wypukłości. Zwiększyła się również liczba przykładów, ilustrujących omawiane zagadnienia, do zestawów zadań na końcu każdego rozdziału zostały wprowadzone nowe, przeprowadzono również selekcję poprzednich. Informacje na temat oprogramowania dostępnego w internecie zostały zweryfikowane i uzupełnione.

Rozdział poświęcony zastosowaniom zawiera opisy przykładowych zagadnień rozwiązywanych metodą sformułowania modelu optymalizacyjnego i jego rozwiązania za pomocą metod obliczeniowych optymalizacji. Przykłady są wprowadzane kolejno, rozpoczynając od najprostszych zadań programowania liniowego, aż po zadania wielokrotnej optymalizacji dynamicznej.

W rozdziale drugim omawiane są zagadnienia programowania liniowego, klasyczna jedno- i dwufazowa metoda sympleks, teoria dualności w zagadnieniach programowania liniowego, dualna metoda sympleks oraz metoda punktu wewnętrznego Karmarkara. Rozdział został gruntownie przeredagowany. Zmianie uległ sposób prezentacji metody sympleks, położono większy nacisk na pojęcie rozwiązania bazowego (dopuszczalnego i niedopuszczalnego). Teoria dualności Lagrange’a w programowaniu liniowym jest prezentowana dla ogólnej postaci ograniczeń, co w naturalny sposób pozwoliło wprowadzić dualną metode sympleks. Ostatni podrozdział wprowadza czytelnika w świat internetu - zawiera zaktualizowany, wyczerpujący przegląd dostępnego oprogramowania (darmowego i komercyjnego) oraz stron www poświęconych zagadnieniom programowania liniowego.

Trzeci rozdział rozpoczyna omówienie zastosowań optymalizacji nieliniowej bez ograniczeń. Jako główne dziedziny zastosowań wskazano w nim rozwiązywanie układów równań nieliniowych i problemy identyfikacji nieznanych parametrów modeli (przy wykorzystaniu metody najmniejszych kwadratów) oraz zadania optymalizacji z ograniczeniami. Istotnie rozszerzono informacje na temat zagadnień na temat optymalizacji wypukłej. Pokazano związki prezentowanych warunków koniecznych i dostatecznych optymalności z lokalna wypukłością funkcji celu. Przedstawiono pojęcie jednostajnych kierunków poprawy, testy stopu w niedokładnej minimalizacji kierunkowej. Omówiono typowe metody gradientowe: najszybszego spadku, Newtona, quasi-newtonowskie, metody kierunków sprężonych i gradientów sprężonych, bezgradientową metodę sympleksu Neldera-Meada. Przedstawiono przykłady gradienowych metod minimalizacji kierunkowej oraz złotego podziału niewykorzystującą pochodnych. Rozdział uzupełniono krótkim zestawieniem oprogramowania dostępnego w internecie, które nie występowało w „Podstawach optymaliacji”.

W rozdziale czwartym istotnie rozszerzono zagadnienia warunków koniecznych i dostatecznych optymalności dla różniczkowalnych zadań z ograniczeniami, w szczególności dodano warunki drugiego rzędu. Prezentacja wyników jest bardziej jednorodna. W dowodach twierdzeń precyzujących warunki optymalności wykorzystano funkcje kary i odpowiednie wyniki dotyczące zadań bez ograniczeń. W podrozdziałach poświęconych funkcjom kary dodano twierdzenia o ich zbieżności, wskazano związki miedzy minimami zadania z ograniczeniami i odpowiedniego zadania z karą. Do opisu metody zbiorów ograniczeń aktywnych do rozwiązywania zadań kwadratowych z ograniczeniami nierównościowymi, włączono uzasadnienie, ze generowane kierunki są dopuszczalnymi kierunkami spadku. Omówiono również teorię dualności Lagrange’a oraz algorytmy wielomianowe oparte na wykorzystaniu barierowej funkcji kary do rozwiązywania zadań programowania liniowego. Ta ostatnia jest prezentowana w tym miejscu, ponieważ jej zrozumienie wymaga znajomości teorii dualności, metody Newtona oraz barierowej funkcji kary. Rozdział zamyka omówienie aktualnego stanu oprogramowania oraz stron www dostępnych w internecie.

Spis treści

Rozdział 1. Wprowadzenie

• Problem optymalizacji
• Przykłady praktycznych zadań optymalizacyjnych
• Optymalne planowanie produkcji
• Sieć rezystorów
• Sieci elektryczne
• Przykłady budowy autostrady
• Wystrzelenia rakiety
• Model wzrostu lasu

• Wstęp
• Postać standardowa zadania programowania liniowego
• Metoda sympleks
• Rozwiązania bazowe zadania programowania liniowego
• Wybór zmiennej wprowadzanej do bazy oraz kryterium
• optymalności bazowego rozwiązywania dopuszczalnego
• Wybór zmiennej wyprowadzanej z bazy oraz wykrywanie
• nieograniczoności zadania programowania liniowego
• Algorytm metody sympleks- zapis algebraiczny
• Różne sposoby organizacji obliczeń w metodzie sympleks
• Znajdowanie początkowego punktu dopuszczalnego
• Metoda minimalizacji sumy zmiennych sztucznych
• Technika zmiennych znaków zaproponowana przez Wolfe’a
• Metoda jednofazowa (wielkiego M)
• Przykłady zadań rozwiązywanych dwufazową metodą
• sympleks w wersji tablicowej
• Dualne zadanie Lagrange’a do zadania programowania liniowego
• Przykłady wzajemnie dualnych zadań LP
• Związki między zadaniami prymalnym i dualnym
• programowania liniowego
• Interpretacja ekonomiczna dualności
• Dualna metoda sympleks
• Przebieg k-tej iteracji dualnej metody sympleks
• Analiza i uzasadnienie poszczególnych kroków dualnej
• metodzie sympleks
• Przykłady znajdowania rozwiązań za pomocą dualnej
• metody sympleks
• Zadania transportowe
• Programowanie liniowe – algorytmy o wielomianowym nakładzie
• obliczeń
• Oprogramowanie do rozwiązywania zadań programowania liniowego
• Pakiety powszechnie dostępne
• Pakiety komercyjne i system modelowania
• Zadania z programowania liniowego
• Rozwiązania

• Zastosowania optymalizacji nieliniowej bez ograniczeń
• Zadania identyfikacji
• Układy równań nieliniowych
• Ciągi pomocniczych zadań bez ograniczeń w metodach optymalizacji z ograniczeniami
• Pojęcie rozwiązania optymalnego
• Zadania optymalizacji wypukłej
• Zbiór wypukły
• Funkcje wypukłe
• Własności zadań optymalizacji wypukłej
• Warunki optymalności dla zadań optymalizacji bez ograniczeń
• Warunki konieczne dla funkcji różniczkowalnych
• Warunki dostateczne
• Pojęcie ścisłej dodatniej określoności
• Punkty stacjonarne
• Gradientowe metody kierunków poprawy
• Kierunki poprawy
• Metoda najszybszego spadku
• Metoda Newtona
• Metody newtonowskie z aproksymacją różnicową
• Metody quasi-newtonowskie
• Metody kierunków sprężonych
• Analiza zbieżności
• Testy zatrzymania algorytmu
• Modele kwadratowe
• Lokalna szybkość zbieżności
• Minimalizacja w kierunku
• Metody korzystające z pochodnych
• Algorytm kwadratowych interpolacji i ekstrapolacji
• Bezgradientowe metody minimalizacji w kierunku
• Metoda sympleksu Neldera-Meada jako przykład metody poszukiwań prostych
• Oprogramowanie do rozwiązania układów równań nieliniowych i zadań optymalizacji bez ograniczeń
• Optymalizacja bez ograniczeń
• Estymacja parametrów funkcji nieliniowej metodą najmniejszych kwadratów
• Układy równań nieliniowych
• Zadania z optymalizacji nieliniowej bez ograniczeń
• Rozwiązania

• Warunki optymalności dla zadań optymalizacji nieliniowej z ograniczeniami
• Warunki konieczne optymalności w przypadku zadania z ograniczeniami równościowymi
• Warunki dostateczne optymalności w przypadku zadania
• z ograniczeniami równościowymi
• Warunki konieczne optymalności w przypadku zadania z ograniczeniami równościowymi i nierównościowymi
• Warunki dostateczne optymalności w przypadku zadań z ograniczeniami równościowymi i nierównościowymi
• Warunki regularności
• Dualne zadanie Lagrange’a
• Przykłady zadań wzajemnie dualnych
• Twierdza o dualności
• Dualne zadanie Wolfe’a
• Programowanie kwadratowe
• Zadanie programowania kwadratowego z ograniczeniami równościowymi
• Zadania programowania kwadratowego z ograniczeniami nierównościowymi (metoda zbioru ograniczeń aktywnych)
• Zewnętrzna funkcja kary
• Algorytm metody zewnętrznej funkcji kary
• Typowe przykłady funkcji kary
• Zmienne sprzężone w punkcie optymalnym
• Wewnętrzna funkcja kary
• Mnożnikowe (przesuwanie) funkcje kary
• Ograniczenia równościowe
• Rozszerzona funkcja Lagrange’a dokłądne funkcje kary
• Ograniczenia nierównościowe
• Dokładna funkcja kary typu 
• Algorytm punktu wewnętrznego do rozwiązywania zadań LP
• Oprogramowanie do rozwiązywania zadań optymalizacji nieliniowej
• Zadania z optymalizacji nieliniowej z ograniczeniami
• Rozwiązania
• Bibliografia
• Indeks