411 2

411

10.1. Sformułowanie zadania, definicje i postać normalna

Wiele innych ważnych zmian woźna wyrazić w postaci normalnej; np. zadanie minimali-gićji wyrażenia /=c₁.T₁-tc₂jr, + ... ^ c_rx_nz warunkami (10.1.2) i <10.1.3) jest równoważne pianiu maksymalizacji wyrażenia —f

jeśli niektóre ograniczenia są nierównościami

A|lJf I + <*12*2 + • - • + 0,„X_n < b,,

•o można wprowadzić zmienne wolne” tak, aby miały być spełnione równania j nierówności x_n+i ^0.

Przykład 10.1.2. Kontynuacja przykładu 10.1.1. Nierówności (10.1.1) można doprowadzić do postaci normalnej za pomocą trzech zmiennych wolnych x₂, x_A, x_s. Otrzymujemy

5xj+ x₂+x₃    =60,

(10.1.4)    3xj+4x₂    + x₄    =60,

4xj +3x₂    -fx₅=60,

(10.1.5)    x&0    (1*1,2,...,5).

Trzy równania (10.1.4) określają podprzestrzeó dwuwymiarowy (płaszczyznę z rys. 10.1.1)

przestrzeni pi ęciowymiarowej punktów (x,. x₂.....x_t), gdyż 5—3 = 2. Dwie współrzędne -

- np. x,, x₂ — określają jednoznacznie pozostałe. Każdy bok pięciokąta OABCD ma równanie postaci x_{-=0 (J= I, 2,.... 5). Wierzchołek jesi punktem przecięcia dwóch boków; dlatego w wierzchołku dwie współrzędne są zerami, a inne nie mogą być ujemne. (Istnieje leź pięć punktów przecięcia przedłużeń boków pięciokąta. W tych punktach jednak niektóre x_£ są ujemne, wobec czego tych punktów przecięcia nie uważa się za wierzchołki).

Intuicje geometryczne zastosowane w* poprzednim przykładzie przydają się i w ogólnym przypadku; m równań (10.1.2) wyznacza (n—/»)-wy miarową podprzestrzeń w n-wymiarowej przestrzeni punktów (x_lt x₂,.... x„). Można wybrać n—m współrzędnych i nadać im dowolne wartości; wtedy układ równań określa jednoznacznie pozostałe współrzędne. Punkt spełniający ograniczenia (10.1.2) i (10.1.3) nazywa się punktem (lub wektorem) dopuszczał-mw. Punkty dopuszczalne tworzą wieiościan w przestrzeni (n—m)-wymiarowej. Wektory dopuszczalne mogą w ogóle nie istnieć. Jest też możliwe, że wspomniany wiełościan nie jest ni mezony w pewnych kierunkach. Założymy jednak, że wektory dopuszczalne istnieją f ma skończone maksimum (dzięki czemu ewentualna nieograniczoność wielościanu nie Wnidnia w praktyce obliczeń). Te założenia w' są praktyce zazwyczaj spełnione w poprawnie sformułowanych zadaniach.

Przez bazowy wektor (łub punkt) dopuszczalny rozumiemy wektor (punkt) dopuszczalny, # którym co najmniej n—m z n współrzędnych x_{ jest równych 0. Może się zdarzyć, że •' Punkcie dopuszczalnym zeruje się więcej niż n—m współrzędnych — zobacz np. wierz-ostrosłupa z rys. 10.2.J. W takim przypadku mówimy o zdegeńerowanym wektorze

F⁵*szczalnym.