DSC03228

1.1. Programowanie liniowe

Zagadnienie programowania liniowego (w skrócie LP, od angielskiej nazwy łinear progmmming) polega na znalezieniu zbioru nieujemnych wartości zmiennych, minimali-zujących liniową funkcję celu i spełniających pewien zbiór ograniczeń liniowych. Standardowa postać programu liniowego jest następująca:

Znaleźć minimum

(1.1)    * as c^T* przy warunkach

(1.2)    A* <6,

(1.3)    »>0,

gdzie A jest daną macierzą o wymiarach m x n, m < n, c jest n-elementowym wektorem kosztów, 6 jest wektorem o m składowych, a z jest wektorem niewiadomych

0    n składowych Górny wskaźnik T oznacza transpozycję wektora.

Wiele praktycznych zagadnień w ekonomii, badaniach operacyjnych, teorii decyzji

1    technice może być sformułowanych jako modele LP. To właśnie sprawia, że programowanie liniowe jest niezmiernie popularne i że w ostatnich trzydziestu latach dokonał się tak fenomenalny jego rozwój. Do tego rozwoju przyczyniły się także trzy inne czynniki: (1) elegancka matematyka oparta na teorii nierówności i równań algebraicznych; (2) szybki rozwój komputerów, które stały się koniecznym narzędziem w stosowaniu programowania liniowego; (3) przybliżenia za pomocą programowania liniowego, których się używa w roi wiązywaniu niemal wszystkich zagadnień programowania matematycznego.

George Dantzig, Leonid Kantorowicz, John von Neumann i Allan Tucker należą do tych wielkich matematyków, którzy rozwinęli teorię, metody obliczeniowe i zastosowania programowania liniowego. Dantzig [1963], w rozdziale 3 swojej obszernej książki o LP i jego uogólnieniach, przedstawia interesujący opis początków i wpływów programowania liniowego. Od końca lat csterdsiestych zostały napisane setki książek i tysiące prac o teorii i zastosowaniach l.P. Czytelnik nie powinien mieć większych trudności w znalezieniu źródeł informacji rosssersąjących naszą zwartą prezentację programowania liniowego.

Zanim zajmiemy się LP w jego postaci standardowej (1.1) —(1.3), wskażemy, w jaki sposób różne inne postacie LP inogą być sprowadzone do postaci standardowej.

Nierówność a_uZ| + a_tax₃ + ... + a_lnar„ < b_x może być sprowadzona do równości poprze* wprowadzenie zmiennej uzupełniającej (sztucznej) z_n+1 > 0 jak następuje:

^an*» + °»a*a + - - • + <*!„*« + *_n+i = V

Jeśli nierówność ma przeciwny zwrot, zmienną z_nłl należy oójąć.