Ogłoszenie

SESJA :D

#1 2007-11-16 18:53:20

mate

Administrator

Zarejestrowany: 2007-02-06
Posty: 236
Punktów :   

ściąga znalazlem takie coś

Kryterium wejścia i wyjścia w algorytmie transportowym
Elementy zerowej macierzy równoważnej są  odpowiednikami wskaźników optymalności w zadaniu PL. Oznacza to, że wartość ujemna wskaźnika  Cbij mówi nam o ile zmniejszy się wartość funkcji celu jeżeli zmieni się  w rozkładzie bazowym wartości zmiennej niezależnej o jednostkę. Jeżeli więc dane BRD nie jest optymalne, to należy znaleźć lepsze rozwiązanie . wprowadzamy do niego węzeł dla którego element macierzy zerowej równoważnej jest najmniejszy np. dla macierzy CB.
Aby znaleźć nowe rozwiązanie bazowe oraz zmienne które należy zwiększyć i zmniejszyć (usunąć z rozwiązania bazowego). Należy znaleźć cykl gamma zawierający węzeł, któremu odpowiada najmniejsza wartość w macierzy CB.
Znajdujemy element min {xijB}i w następnym rozwiązaniu bazowym zmieniamy węzły macierzy XB należące do cyklu gamma, o tę wartość ze znakiem + lub –. W ten sposób usuwamy z rozwiązani bazowego węzeł - kryterium wyjścia.

Kryterium optymalności w algorytmie transportowym
Algorytm transportowy jest szczególnym przypadkiem programu liniowego. Jego idea jest taka sama jak w przypadku metody SIMPLEX – polega na znalezieniu rozwiązania optymalnego spośród bazowych rozwiązań dopuszczalnych – ma jednak nieco odmienną konstrukcję.
Do badanie czy wyznaczone jest rozwiązanie bazowe jest rozwiązaniem optymalnym, wykorzystuje się zerową macierz równoważną, czyli macierz potencjałów CB.
Dla danego zbioru bazowego B i macierzy kosztów jednostkowych C wyznaczamy potencjały u1, u2, u3...un i v1, v2, v3...vn takie, że Cij + Ui + Vj = 0;  (i,j) € B, i = 1,2,3 ... m, j = 1,2,3...n. Przykładowo dla macierzy kosztów....
Ponieważ mamy układ np. czterech równań z pięcioma niewiadomymi, więc rozwiązań jest nieskończeni wiele, można jedno z niewiadomych przyjąć za zero, np. u1 = 0
Zerowa macierz równoważna ma wtedy postać ...a jej elementy są równe  cijB = cij + ui + vj
Macierz ta służy stwierdzeniu optymalności zadania transportowego.
TWIERDZENIE
Jeżeli macierz XB jest bazowym rozwiązaniem dopuszczalnym zadania transportowego odpowiadającym zbiorowi  bazowemu B, a odpowiadająca B zerowa macierz równoważna CB ma wszystkie elementy nieujemne, to XB jest rozwiązaniem optymalnym tego zadania. Dodatkowo jeśli cijB > 0 dla każdego ij {nie należącego} do B to XB jest jedynym rozwiązaniem optymalnym tego zadania.

Rozwiązania bazowe i ich znaczenie w metodzie SIMPLEX
Bazowym rozwiązaniem układu równań liniowych nazywamy rozwiązanie, które otrzymujemy w następujący sposób:
(1)    Przypisujemy wartości zerowe S – r zmiennym spośród zmiennych x1, .... , xS takim jednak, aby macierz B współczynników aij przy takich xj, którym nie przypisaliśmy wartości zerowych, była macierz nieosobliwa (tzn. aby jej wyznacznik był różny od zera)
(2)    Wartości pozostałych r zmiennych wyliczamy z powstałego w wyniku tej operacji układu r równań z r niewiadomymi. Macierz B nazywa się baza rozwiązania. Pojęcie bazy i rozwiązania bazowego objaśniamy na przykładzie.
Nieujemne bazowe rozwiązanie układu równań nazywać będziemy rozwiązaniem bazowym programu PKL. Przy założeniach (Z1) i (Z2) istnieje przynajmniej jedno rozwiązanie bazowe tego programu. Rozwiązania bazowe dlatego nas szczególnie interesują, że zachodzi następujące –
TW. Jeżeli optymalne rozwiązanie programu PKL istnieje, to przynajmniej jedno rozwiązanie bazowe tego programu jest rozwiązaniem optymalnym.
Z definicji rozwiązania bazowego układu równań liniowych wynika, że bazowych rozwiązań programu PKL jest skończenie wiele (nie więcej niż {sr}). Żeby więc znaleźć optymalne rozwiązanie tego programu, wystarczy znaleźć jego rozwiązanie bazowe i wybrać to, które daje największą wartość funkcji celu. Istotne dla rozwiązania programów liniowych jest również
TW. Jeżeli wektory x1, .... , xN są optymalnymi rozwiązaniami programu liniowego, to dowolny wektor  ................

Jest również rozwiązaniem optymalnym.
Wprowadzamy jeszcze jedno pojęcie. Rozwiązanie bazowe programu PKL nazywamy rozwiązaniem zdegenerowanym jeżeli liczba zmiennych przyjmujących w tym rozwiązaniu wartości zerowe jest większa niż s – r (tym samym liczba zmiennych przyjmujących wartości dodane – mniejsza niż r). Pojęcie rozwiązania zdegenerowanego jest ważne dlatego, że pojawienie się rozwiązań zdegenerowanych wywołuje przy rozwiązaniu programów liniowych pewne trudności, o których będzie mowa później.

Równanie równowagi przepływów międzywydziałowych.
Sprawdzeniem zgodności programu produkcji w ujęciu wartościowym jest równanie

∑ xij + xj = ∑ xij + ∑ vrj + zj + xoj
Równanie to nosi nazwę równania równowagi przepływów i oznacza, że suma przepływów z i – tego wydziału do pozostałych + produkcja finalna tego wydziału = jest sumie przepływów z pozostałych wydziałów do tego wydziału + suma dostaw z zewnątrz + zysk tego wydziału + wartość siły roboczej zatrudnionej w tym wydziale.

Metoda kąta północno – zachodniego a metoda potencjałów
Otrzymywanie rozwiązania optymalizacji algorytmu transportowego. Metoda potencjału Domtziga – macierzą równoważną do macierzy kosztów jednostkowych C jest  macierz C” , której elementy spełniają równość:
C”ij = cij + ui + vj  (ui i vj potencjały dowolne stałe).
TW. Rozwiązanie dopuszczalne X = [xij] zagadnienie transportowe minimalizuje f z(Z)
Z(X) = ∑∑C”ijXij
Zerową macierzą równoważną jest macierz CB, w której cijB = 0 dla xij należących do rozwiązania bazowego. Zerową macierzą równoważną macierzy C względem zbioru bazowego B jest taka macierz
CB = [cijB] = [cij + uij + vij] w której elementy spełniają układ równań dla
Cij + ui + vj = 0
Ponieważ jest to zawsze m + n – 1 równań (ilość zmiennych bazowych z n + m niewiadomymi (ilość ui i vj) to jedną niewiadomą (potencjał) można wyznaczyć dowolnie).
Każdy element tej macierzy mówi o ile zmieni się wartość funkcji celu po wprowadzeniu jednej dostawy (tony, sztuki), jeśli (m + n – 1) = liczba zer – rozwiązanie optymalne.

Metoda kąta północno – zachodniego a metoda potencjałów.
Proces gospodarowania zmusza decydentów do układania planów działania. Decydent jednak działa w określonych warunkach ograniczających, które powodują, że nie każdy plan działania może być zrealizowany powstaje zatem zbiór planów możliwych do realizacji – są to tzw. decyzje dopuszczalne.
Z tego zbioru można wyróżnić decyzje lepsze lub gorsze. Decydentowi zależy oczywiście na wyborze decyzji najlepszej tzw. decyzji optymalnej. Aby ten wybór był możliwy należy skonstruować kryterium wyboru tzw. funkcję celu tak powstaje model decyzyjny, który należy zapisać matematycznie. Warunki ograniczające zatem zapisujemy w postaci nierówności, które będą zawierać dwa rodzaje zmiennych: zmienne decyzyjne – wielkości te należy wyznaczyć w zdaniu od nich zależy decyzja, parametry – wielkości niezależne od decydenta,  w modelu deterministycznym są one znane i stałe w określonym czasie.
Jeżeli funkcja celu ma postać liniową to model taki nazwiemy liniowym. Funkcja celu wiąże wszystkie zmienne decyzyjne. Ponadto występują w niej  wagi zmiennych decyzyjnych.
Decyzja dopuszczalna jest decyzją optymalną gdy wartość funkcji celu dla zmiennych tej decyzji przyjmuje wartość ekstremalną.
Przykłady zastosowań
-    zagadnienie diety
-    ustalenie planu działania (plan produkcji)
-    zagadnienie pośrednika (plan zakupu, przewozu i sprzedaży towaru, tak aby dochód był maksymalny)
-    optymalizacja działalności rolnika

Zapis macierzowy
Z (X) = CTX     AX = b      X => 0
Postać standardowa
Max Z(X) = CTX              min Z(X) = CTX
AX <= b              AX => b
X => 0               X => 0

Związki między programem dualnym i pierwotnym.
1.    w zadaniu dualnym jest tyle zmiennych ile nierówności w zadaniu pierwotnym
2.    w zadaniu dualnym jest tyle warunków ile zmiennych w zadaniu pierwotnym
3.    wagi funkcji celu zadania pierwotnego są wyrazami wolnymi w zadaniu dualnym
4.    wyrazy wolne zadania pierwotnego są wagami funkcji celu w zadaniu dualnym
5.    macierz współ czynników zadania dualnego jest transpozycją macierzy współczynników zadania pierwotnego
6.    jeżeli zadanie pierwotne jest na maksimum, to dualne jest na minimum i odwrotnie
   
    Zastosowanie liniowych modeli dynamicznych.
7.    wybór asortymentu produkcji
8.    problem mieszanek
9.    wybór procesu technologicznego
   
    Decyzje dopuszczalne – decyzje uwzględniające warunki ograniczające
    Zmienne decyzyjne – w warunkach ograniczających opisanych za pomocą równań lub nierówności występują wielkości znane (warunki nieznane, które występują w równaniach opisujących warunki ograniczające)
    Zmienna swobodna- wprowadzana jest w celu likwidacji nierówności  i ma interpretację ekonomiczną
    Zmienna sztuczna – wprowadzana gdy w macierzy A warunków ograniczających nie ma macierzy jednostkowych o wymiarach m, nie ma interpretacji ekonomicznej
    Zmienna bazowa – to zmienna przy wektorach tworzących bazę i jest ich m
   
    Rozwiązanie optymalne a rozwiązanie dopuszczalne.
    Jest to punkt ze zbioru decyzji dopuszczalnych dla których funkcja przyjmuje wartość max / min
   
    Rozwiązania bazowe i ich znaczenie w metodzie simpleks.
    Rozwiązanie bazowe związane jest z postacią kanoniczną. W metodzie simplex stosujemy przegląd ukierunkowany zbioru rozwiązań bazowych. Przechodzimy od jednego dopuszczalnego rozwiązania bazowego do drugiego, o którym wiemy, że jest nie gorsze od poprzedniego.  Pomijamy więc rozwiązania bazowe niedopuszczalne oraz te, które są gorsze od aktualnie rozpatrywanego.
10.    rozwiązania optymalnego wystarczy szukać wśród rozwiązań bazowych, których liczba jest skończona
11.    można znaleźć rozwiązanie optymalne dokonując przeglądu zupełnego zbioru wszystkich rozwiązań bazowych
   
    Kryterium simpleks i jego znaczenie w metodzie simplex.
    Cj – Zb – wyraża zmianę w wartości funkcji celu Z(x) względem dotychczasowej  Z(xb) wywołaną wprowadzeniem zmiennej niebazowej xj w ilości 1 – wielkość tą nazywamy kryterium simplex (optymalności)
    Za pomocą kryterium simplex możemy ocenić:
12.    czy dane rozwiązanie bazowe jest optymalne
    rozwiązanie bazowe jest optymalne gdy wskaźniki kryterium simplex dla zmiennych niebazowych są
13.    nieujemne jeżeli funkcja celu dąży do minimum cj – zj >= 0
14.    niedodatnie jeżeli funkcja celu dąży do maximum cj – zj <= 0
    Wskazuję, którą zmienną niebazową wprowadzić do rozwiązania bazowego. Wprowadzamy tę zmienną niebazową, dla której wskaźnik kryterium simplex
    Cj – Zj = minimum gdy funkcja celu dąży do minimum
    Cj – Zj = maximum gdy funkcja celu dąży do maximum
   
    Kryterium wejścia i wyjścia w metodzie simplex.
   
    Kryterium wejścia – informuje, którą zmienną niebazową należy wprowadzić do następnego rozwiązania bazowego. Wprowadzany tę zmienną dla której Cj – Zj jest największe dla funkcji celu Z(x) – max lub zmienną dla której Cj – Zj jest najmniejsze dla funkcji celu Z(x) – minimum.
   
    Kryterium wyjścia – zasada wg której usuwamy z rozwiązania bazowego jedną ze zmiennych bazowych aby zrobić miejsce dla wprowadzonej zmiennej dotąd niebazowej. Zmienną usuwaną jest Xr dla której Bi/Aik = min Aik >0
    Wybór innej zmiennej powoduje uzyskanie nowego rozwiązania bazowego, które będzie niedopuszczalne. Brak w k – tej kolumnie tablicy simplexowej elementu dodatniego oznacza, że zadanie nie ma rozwiązania optymalnego i obliczenia należy przerwać
   
    KRYTERIA DECYZYJNE W WARUNKACH NIEPEWNOŚCI I RYZYKA
   
    Sytuacja pewności występuje wtedy gdy wynik decyzji jest znany zawczasu. W warunkach pewności jest tylko jeden możliwy wynik, jaki przyniesie pojedyncze działanie czy decyzja
    Sytuacja ryzyka jest definiowana jako taka w której na skutek działania lub decyzji może wystąpić każdy z dwóch lub więcej przypadków. Wszystkie z tych  wyników oraz prawdopodobieństwa wystąpienia każdego z nich są znane podejmującemu decyzję.
    Sytuacja niepewności ma miejsce wówczas, gdy w rezultacie działania może zaistnieć jeden lub więcej wyników. W odróżnieniu od sytuacji ryzyka, nie ,może być ściśle określone zaistnienie tych wyników oraz nie mogą być obiektywnie wyznaczone prawdopodobieństwa  ich wystąpienia. W sytuacji niepewności to szacowanie prawdopodobieństw opiera się na subiektywnych przesłankach, a nie na obiektywnych podstawach.
   
    Procedura podejmowania decyzji w warunkach niepewności i/ lub ryzyka może przedstawiać się następująco
•    identyfikacja sposobów działania, które są możliwe
•    rozpoznanie możliwych wyników każdego działania
•    wyznaczenie prawdopodobieństw wszystkich wyników
•    zastosowanie wybranego kryterium decyzyjnego

Reguły decyzyjne w warunkach niepewności
1.    Kryterium minimaksowe (Savage’a)
2.    Kryterium maksyminowe (Walda)
3.    Kryterium Hurowicza
4.    Kryterium wartości średniej
Zakres informacji dostępnej przy podejmowaniu decyzji opisany jest za pomocą trzech stanów: pewności, ryzyka, niepewności.
Stan pewności – w momencie podejmowania decyzji znamy stan świata zewnętrznego, zadanie wówczas polega na wyborze takiej decyzji której jest przyporządkowana największa korzyść.
Stan ryzyka – na skutek decyzji może wystąpić każdy z 2 lub więcej wyników, przy czym wszystkie wyniki te jak i prawdopodobieństwo wystąpienia ich jest znane pod. Podejmującym decyzje. (np. gry hazardowe)
Sytuacja niepewności – gdy w rezultacie działania może zaistnieć 1 lub więcej wyników przy czym nie znamy wyników i prawdopodobieństwa ich wystąpienia.

1.  Kryterium minimaksowych skutków błędnych decyzji, nie ocenia się wyników podjętych decyzji lecz skutki (straty) wynikające z niepodjęcia decyzji, która przy danym stanie natury byłaby najlepsza. Budujemy macierz strat Ui j będących różnicami między max do osiągnięcia wynikiem, a wynikiem uzyskanym w razie podjęcia decyzji o wyborze wariantu Di.
Vi j = max (kr j) – ki j             r - największa wartość
Następnie każdemu wariantowi przyporządkowuje się max względną stratę jaką można ponieść wybierając ten wariant.
Ui = max ( ui j ).  Podejmujemy dec. O takim wyborze przed. Dk , która zapewnia najmniejszą z max strat.

2. Wybieramy wartość min w każdym wierszu a następnie wybieramy największą z nich.
K i j =max min (k)         Jest to b. Ostrożna reguła. Podmiot podejmujący decyzje jest pesymistą.

3.  Wprowadzamy tzw. Współczynnik ostrożności  „a” i  a(0;1)
di = a min ki j + (1 – a ) max kij
Spośród możliwych wariantów wybieramy decyzje Dk = max di
Jeżeli „a” jest bliskie: 1  kryt. Jest regułą ostrożną
            0  kryt. Jest regułą hazardową
4. Najlepsza jest strategia która daje największą przeciętną wygraną.
Dla każdej decyzji wart. Średniej wyników
wybiera się taką decyzje Dk=max di
Taka reg. gdy wszystkie stany natury są jednakowo prawdopodobne.

Offline

 

#2 2007-11-16 19:01:43

bartek

Weteran

Zarejestrowany: 2007-02-25
Posty: 79
Punktów :   

Re: ściąga znalazlem takie coś

nic z tego nie wiem

Offline

 

#3 2007-11-16 22:44:38

Elcia

Aktywny

Skąd: Rzeszów
Zarejestrowany: 2007-02-23
Posty: 41
Punktów :   

Re: ściąga znalazlem takie coś

hehehe dobre jak dostane conajmniej 4 to podziękuję heehe

Offline

 

#4 2007-11-21 21:16:25

mate

Administrator

Zarejestrowany: 2007-02-06
Posty: 236
Punktów :   

Re: ściąga znalazlem takie coś

Offline

 

Stopka forum

RSS
Powered by PunBB
© Copyright 2002–2008 PunBB
Polityka cookies - Wersja Lo-Fi


Darmowe Forum | Ciekawe Fora | Darmowe Fora
Alloggio Giamaica sala na szkolenie kraków krowodrza