6.1. Rozwiązanie optymalne i bazowe

Tw: Jeżeli zadanie programowania liniowego ma rozwiązanie optymalne to ma także rozwiązanie optymalne - bazowe

Wniosek: rozwiązania optymalnego należy szukać wśród rozwiązań bazowych, których liczba jest skończona.

Definicja: Rozwiązanie bazowe - nazywa się dowolne rozwiązanie uzyskane przez podstawienie (przyjęcie) za n-m zmiennych 0 i rozwiązanie układu równań ze względu na pozostałe m-zmiennych.

Rozwiązań bazowych jest skończona liczba.

Rozwiązań jest tyle, ile jest kombinacji

, np. n=5, m=3

6.2

6.4. Interpretacja ekonomiczna zagadnienia dualnego

Jeżeli zadanie pierwotne jest modelem pierwotnego problemu decyzyjnego i ma określoną interpretacje ekonomiczną, to również odpowiednią interpretację ma zbudowane w odniesieniu do niego zadanie dualne.

Jeżeli zdanie pierwotne opisuje problem maxymalizacji zysku, a ograniczenia dotyczą zużycia środków produkcji, które nie może przekroczyć poziomu posiadanych zasobów to zmienną dualną y_i można interpretować jako cenę jednostkową i-tego środka produkcji.

Optymalna wartość zmienniej y_i określa o ile wzrośnie przychód (zysk) jeśli zwiększy się zasób i-tego środka produkcji o jednostkę.

Ten wniosek jest prawdziwy gdy zmiany mieszczą się w dopuszczalnych granicach i dotyczą tylko jednego środka produkcji.

Zmienną dualną określa się więc jako krańcową produktywność jednostki i-tego środka.

6.5. Modele programowania liniowego w postaci standardowej i kanonicznej

Jeżeli w modelu warunki ograniczające mają charakter nierówności to taki model liniowy ma postać standardową. Natomiast jeśli mają postać równań to model ma postać Kanoniczną.

Każdą postać standardową można sprowadzić do postaci kanonicznej poprzez wprowadzenie do modelu postaci standardowej dodatkowych zmiennych (swobodnych, bilansowych)

n - liczba zmiennych w modelu; m - liczba równań ; n>m

Postać standardowa 9x1+6x2max

Postać kanoniczna 9x1+6x2max

---