CCF03252008005

2.6

Metoda simpleks

Metoda simpleks jest podstawową metodą znajdowania optymalnych rozwiązań zadań programowania liniowego. Jest to metoda ogólna, pozwalająca rozwiązać każde zadanie PL. Polega ona na sekwencyjnym, ściśle określonym przeglądzie rozwiązań bazowych.

2.6.1

Rozwiązanie bazowe zadania PL

Rozwiązanie bazowe związane jest z postacią kanoniczną. Załóżmy więc, że dane jest zadanie PL o postaci kanonicznej:

(2.43)

gdzie:

A — macierz współczynników o wymiarach (m x n), x — 11-wymiarowy wektor zmiennych, b — m-wymiarowy wektor wyrazów wolnych, c — n-wymiarowy wektor wag funkcji celu.

Niech B oznacza macierz kwadratową m-tego stopnia, składającą się z m liniowo niezależnych kolumn macierzy A. Wyznacznik tej macierzy jest oczywiście różny od zera:

det (B) + 0. '

Macierz B nazywać będziemy bazą, jej kolumny — kolumnami bazowymi, a pozostałe kolumny macierzy A — kolumnami niebazowymi. Zmienne związane z kolumnami bazowymi nazywamy zmiennymi bazowymi, a pozostałe zmienne — zmiennymi niebazowymi.

Z każdą bazą B układu Ax = b związane jest rozwiązanie bazowe. Jeżeli układ Ax = b jest niesprzeczny oraz n > m, to układ ten ma nieskończenie wiele rozwiązań, ale skończoną liczbę rozwiązań bazowych. Układ m

rownan z n zmiennymi ma co najwyżej

zowych.

Rozwiązania bazowe układu Ax = b można uzyskać np. w następujący sposób:

1)    wybieramy m liniowo niezależnych kolumn macierzy A, czyli bazę B,

2)    zmienne niebazowe przyjmują wartości zerowe (x_N = 0),

3) wartości zmiennych bazowych ustalamy rozwiązując układ m równań z m niewiadomymi: Bx„ = b.

Jeżeli każda zmienna bazowa jest różna od zera, to takie rozwiązanie bazowe jest niezdegenerowane. Jeżeli natomiast chociaż jedna zmienna bazowa jest zerowa, to takie rozwiązanie bazowe jest zdegenerowane. Dla zadań PL prawdziwe jest następujące twierdzenie.

TWIERDZENIE &

Jeżeli zadanie PL ma rozwiązanie optymalne, to ma także rozwiązanie optymalne bazowe.

WNIOSEK fi

Rozwiązania optymalnego wystarczy szukać wśród rozwiązań bazowych, których liczba jest skończona.

WNIOSEK 2

Można znaleźć rozwiązanie optymalne dokonując przeglądu zupełnego zbioru wszystkich rozwiązań bazowych.

PRZYKŁAD 2.10

Mamy zadanie PL o postaci standardowej:

r

3Xj + x₂ -> max,

< 2x, + 3x₂ < 12, J.

2x, ^ 6, x_lt x₂ ^ 0.

Wprowadzając zmienne swobodne uzyskujemy równoważną postać kanoniczną:

2.45)

4!

2! (4-2)1

wych. Możemy je wyznaczyć przyjmując jako zmienne niebazowe kolejno: x_lt x₂; x_v x₃; x_v x₄; x₂, x₃; x₂, x₄; x₃,x₄. Ponieważ dla trzeciego wariantu zmiennych niebazowych wektory:

ostatecznie mamy 5 następujących rozwiązań bazowych:

35

Wyszukiwarka

Podobne podstrony:
zestaw01 6 Matematyka. Poziom podstaw owy ZADANIA OTWARTE Rozwiązania zadań o numerach od 26, do 3
Programowanie liniowe - metoda simplex Algorytm simplex jest algorytmem pozwalającym znaleźć maksimu
P1220663 Edukacja zdrowotna jest podstawową metodą walki z chorobami. Dotyczy to również stomatologi
Przykłady nowotworów, w których chirurgia jest podstawową metodą leczenia • rak płuca rak piersi rak
DSC65 (2) Metoda simpleks Metoda simpleks polega na rozpatrzeniu ciągu sąsiednich rozwiązań bazowyc
Progowanie jasności Segmentacja obrazu przez progowanie jasności jest podstawową metodą segmentacji
odpowiedzi na kolosa page 034 47. Metoda mało.sygnałowaMetoda małosygnałowa •    Meto
DSC
26 Edukacja zdrowotna jest podstawową metodą walki z chorobami. Dotyczy to również stomatologii
str14 (47) Przykład 2. Metoda biegunowa jest podstawowym sposobem pomiaru szczegółów terenowych Jak
Istota metody Simpley Metoda uniwersalna do rozwiązań liniowych Założenia: l,n>m 2. rząd macierzy
skanuj0035 KLASYFIKACJA JAK w każdej nauce, klasyfikacja jest podstawową metodą 1) por2ądkowania mat
Wyciskanie jest podstawowa metodą wytwarzania rur. prętów i kształtowników oraz części maszyn ze sta

więcej podobnych podstron