056 057 2

56 Programowanie liniowe

Analiza sytuacji, które mogą wystąpić przy rozwiązywaniu zadań programowania liniowego pozwala na uzupełnienie wstępnego opisu metody simpleks, podanego w podrozdziale 1.3.2. Poniżej sformułowane zostały reguły postępowania, uwzględniające również omówione uprzednio szczególne przypadki.

1.    Uzyskanie pierwszego rozwiązania bazowego

Rozwiązanie to uzyskujemy często poprzez przekształcenie zadania wyjściowego do postaci standardowej i wprowadzenie zmiennych bilansujących. Jeżeli okaże się to niewystarczające, wprowadzamy zmienne sztuczne.

2.    Ocena optymalności rozwiązania

Służy do tego kryterium optymalności, wykorzystywane na początku i każdej iteracji.

3.    Badanie niesprzeczności zadania

Jeżeli do zadania wyjściowego wprowadzona została zmienna sztuczna, ! wtedy sprawdzamy, czy w otrzymanym na końcu postępowania roz- \ wiązaniu optymalnym wśród zmiennych bazowych znajduje się niezerowa | zmienna sztuczna. Gdyby tak było, oznacza to, że wyjściowe zadanie jest j sprzeczne.

4.    Identyfikacja rozwiązań alternatywnych

Rozwiązania alternatywne istnieją wtedy, gdy przynajmniej jeden współczynnik optymalności dla zmiennej niebazowej przyjmuje wartość zero. Możemy zidentyfikować wszystkie rozwiązania alternatywne, wprowadzając kolejno te zmienne do bazy i przechodząc do kolejnych rozwiązań bazowych zgodnie z regułami opisanymi w dalszych krokach.

5.    Wybór zmiennej wprowadzanej do bazy Służy do tego kryterium wejścia.

6.    Badanie nieograniczoności funkcji celu i istnienia krawędzi sprawnej

Sprawdzamy, czy w kolumnie, odpowiadającej wybranej zmiennej, którą

zamierzamy wprowadzić do bazy, jest przynajmniej jedna liczba dodatnia. Jeżeli współczynnik optymalności odpowiadający tej zmiennej jest różny od zera oraz w rozpatrywanej kolumnie nie ma liczby dodatniej, oznacza to, że funkcja celu jest nieograniczona. Gdy współczynnik optymalności jest równy zeru oraz w rozpatrywanej kolumnie nie ma liczby dodatniej, oznacza to, że rozpatrywany wierzchołek jest początkiem nieograniczonej krawędzi optymalnej.

7. Wybór zmiennej usuwanej z bazy Służy do tego kryterium wyjścia.

H. Sprowadzenie warunków ograniczających do postaci bazowej wzglądem nowej bazy

Wykorzystujemy w tym celu przekształcenia elementarne.

1.5. Analiza wrażliwości

Mając rozwiązane zadanie programowania liniowego, możemy zastanawiać się nad tym, na ile jest ono wrażliwe na zmiany parametrów (wartości składowych wektora funkcji celu, wektora warunków ograniczających oraz macierzy współczynników). Chodzi o to, aby określić zakres zmian wymienionych parametrów, które nic powodują konieczności zmiany wyznaczonego uprzednio rozwiązania optymalnego (lub bazy optymalnej). Rozpatrzymy dalej dwa przypadki:

1)    gdy zmianie ulegają składowe wektora funkcji celu,

2)    gdy mamy do czynienia ze zmianami wartości wektora wyrazów wolnych.

1.5.1. Współczynniki funkcji celu

Rozpoczniemy od analizy wrażliwości współczynników funkcji celu, rozpatrując najpierw każdy z nich osobno. Z kolei zajmiemy się analizą łącznych zmian tych współczynników.

Przykład 1.8

Rozpatrzymy ponownie problem programowania produkcji, opisany w przykładzie 1.1. Zysk z wytworzenia jednostki P, wynosi obecnie cW jakim przedziale powinna się znajdować wartość c,, aby rozwiązanie bazowe =4, x₂ = 2, *3 = 2, .*4 = 0, jc₅ = 0, które otrzymaliśmy dla c,=2, pozostało dla każdej wartości z tego zbioru optymalne?

Przypomnimy ostatnią tablicę simpleksową dla przykładu 1.1, traktując zysk jednostkowy c, jako parametr. Otrzymujemy (tablica 1.20):

Wyszukiwarka

Podobne podstrony:
058 059 2 58 Programowanie liniowe Tablica 1.20 cx
056 057 56 Eliza Mytych, Ludwik Kumański Charakterystyka logarytmiczna amplitudowa Lm(co) przedstawi
056 057 56 Eliza Mytych, Ludwik Kumański Charakterystyka logarytmiczna amplitudowa Lm{a>) przeds
056 (16) 56 3PKAWCZDANTE i. Opisnć ukłaoy pomiarowe- ?. Stosując oscowujdni program. komputerowy wyz
056 (16) 56 3PKAWCZDANTE i. Opisnć ukłaoy pomiarowe- ?. Stosując oscowujdni program. komputerowy wyz
056 (16) 56 3PKAWCZDANTE i. Opisnć ukłaoy pomiarowe- ?. Stosując oscowujdni program. komputerowy wyz
042 043 2 42 U Programowanie liniowe 42 U Programowanie liniowe Tablica
050 051 2 50 Programowanie liniowe Pierwsza tablica simpleksowa ma postać (tablica 1.14): Tablica 1.
str 6 057 56 TRANSAKCYJA WOJNY CHOC1MSKIEJ Niebieski indygenat za takie prezenty, Że sławy, która i
IMG6 057 (2) 56 4. Interpretacja wykresów układów równowagi natomiast przeliczenie procentów atomow
str 6 057 56 TRANSAKCYJA WOJNY CHOC1MSKIEJ Niebieski indygenat za takie prezenty, Że sławy, która i
056 pcx 56 Bezprzewodowe sieci komputeroweOcena efektywności protokołów Istnieje wiele miar efektywn
IMG6 057 (2) 56 4. Interpretacja wykresów układów równowagi natomiast przeliczenie procentów atomow
Image149 Charakterystyka rejestrów liniowych    Tablica 4.7 Długoić logiczna rejest
Program Srijeda 9. 5. 2018. 19.00    Izlożbeni prostor CZK Ćakovec otvorenje

więcej podobnych podstron