Duality in linear programming

Optimization in mathematics consist of finding the extreme value of the function with subject to restrictions and conditions, which solution must fulfill. Most often because of its simplicity linear functions are considered. This paper is based on finding optimal (minimum or maximum) solutions in linear functions. This process is called linear programming. Each of primal linear problem has corresponding dual problem. The function values for optimal solutions to these problems are finite and equal.This paper contains basic definitions and theorems of linear programming and the most popular method of solving these kinds of problems - the simplex method. Additionally, others variations of the simplex method, which use properities of dual problems: the dual simplex method and the primal-dual algorithm. For each method will be presented a simplex table that illustrates and facilitates understanding operation of each of the above algorithms.

Optymalizacja w matematyce polega na wyznaczeniu ekstremum danej funkcji, często mając na uwadze pewne ograniczenia i warunki, które rozwiązanie musi spełniać. Najczęściej ze względu na swoja prostotę rozważane są funkcje liniowe. Praca ta opiera się na znajdowaniu rozwiązań optymalnych (minimalnych lub maksymalnych) problemów w postaci liniowej, czyli tak zwanym programowaniu liniowym. Każdy problem programowania liniowego posiada analogiczny problem dualny. Wartości funkcji dla rozwiązań optymalnych tych problemów są skończone i równe. Praca ta zawiera podstawowe definicje i twierdzenia programowania liniowego oraz najpopularniejsza metodę rozwiązań tego rodzaju problemów - metodę sympleks. Oprócz tego inne wariacje tej metody, które wykorzystują postać i własności problemów dualnych, czyli metodę dualną oraz dualno-pierwotną. Do każdej metody zostanie przedstawiona tablica sympleksowa, która ilustruje i ułatwia zrozumienie działania każdego z powyższych algorytmów. Przedstawiony zostanie również przykład obliczeń prostych problemów liniowych zgodnie z dana metodą.