Zadanie ograniczone

W wielu praktycznych zagadnieniach obok ograniczeń

$$\sum_{j=1}^n a_{ij}x_j \leq b_i \ \ \ (i=1,...,m)$$

występują indywidualne ograniczenia od góry na zmienne (wszystkie lub niektóre postaci

$$x_j \leq g_j \ \ \ \ (j=1,...,n)$$

Zadanie PL z tak określonymi ograniczeniami jest wtedy oczywiście zadaniem w postaci standardowej

$$\sum_{j=1}^n a_{ij}x_j \leq b_i \ \ \ (i=1,...,m)$$

$$x_j \leq g_j \ \ \ \ (j=1,...,n)$$

$$x_j \geq 0 \ \ \ \ (j=1,...,n)$$

Jednak po dołączeniu zmiennych sztucznych otrzymujemy wtedy macierz ograniczeń o rozmiarze $(m+2n)\times (m+2n)$. Jeśli liczba zmiennych (a więc liczba $n$) jest duża, wielkość problemu który należało będzie rozwiązać może być kłopotliwa. Stąd istotna może się okazać metoda zasugerowana po raz pierwszy przez Dantziga w [5].
Problem postawimy jeszcze ogólniej niż wspomniano wyżej, mianowicie będziemy zakładać ograniczenia nie tylko górne ale i dolne i to na wszystkie zmienne, czyli

$$d_j \leq x_j \leq g_j \ \ \ \ (j=1,...,n)$$

przy czym dopuszczać będziemy $-\infty$ dla dolnego i $+\infty$ dla górnego ograniczenia (co oczywiście oznacza, że odpowiednich ograniczeń nie ma) ^6.1 Będziemy też zakładali równości $\sum_{j=1}^n a_{ij}x_j = b_i, \ (i=1,...,m)$, czyli sytuację którą mamy po wprowadzeniu zmiennych sztucznych. Problem nasz będzie więc postaci

$$% latex2html id marker 6882 \begin{array}{lrclcrrr} \mbox... ...,m)\\ &&&d_j \leq x_j \leq g_j& && (j=1,...,n) \end{array}$$

lub w formie macierzowej

$$% latex2html id marker 6402\left\{ \begin{array}{lrcrcrr}... ... & {\bf d} &\leq {\bf x} \leq & {\bf g} \end{array} \right.$$ (6.1)

gdzie ${\bf A} \in {\bf R}^{n \times n}, \ {\bf b},{\bf d},{\bf g},{\bf x} \in {\bf R}^{n\times 1}, {\bf c} \in {\bf R}^{1 \times n}$.