ZARZĄDZANIE PRZEDSIĘWZIĘCIAMI BUDOWLANYMI.
Opracowanie: Anna Zielińska, Michał Gomoła
Metoda SIMPLEKSOWA
1. Metoda simpleksowa – skąd wiadomo, że wyznaczone w danej iteracji rozwiązanie jest optymalne? Podać odpowiedź dla dwóch zagadnień.
Rozwiązanie optymalne to rozwiązanie zagadnienia w taki sposób, że uzyskuje się ekstremalną wartość funkcji celu (minimalną lub maksymalną). Czyli takie, które generuje największy zysk (maksymalizacja) lub najmniejszy koszt (minimalizacja).
O tym, że rozwiązanie jest optymalne decydują współczynniki optymalności .
Rozwiązanie jest optymalne, gdy:
− Dla maksymalizacji 0
− Dla minimalizacji 0
2. Kiedy należy wprowadzić „sztuczne” zmienne? W Jaki sposób tego dokonujemy? Jak zmienia się funkcja celu?
Sztuczne zmienne stosujemy w metodzie „sztucznej bazy”. Wprowadzamy je wtedy, gdy na wstępie (jeszcze przed znalezieniem rozwiązania dopuszczalnego) nie możemy określić bazy – do równań, które nie posiadają zmiennej bazowej należy dodać sztuczną zmienną bazową z kolejnym indeksem. Zmienną sztuczną wprowadzamy także
do FUNKCJI CELU z najbardziej niekorzystnym współczynnikiem „”kosztów:
− „ ” dla maksymalizacji, gdzie 0
− „ ” dla minimalizacji, gdzie 0
3. Co decyduje o istnieniu rozwiązania alternatywnego? Czy to rozwiązanie jest również optymalne? Co o tym świadczy?
O tym czy istnieje rozwiązanie alternatywne decyduje wartość wskaźnika optymalności dla zmiennych swobodnych (niebędących bazowymi). Rozwiązanie alternatywne istnieje, gdy w tabeli simpleksowej, wskaźnik optymalności
0, dla którejkolwiek zmiennej swobodnej. Jest to również rozwiązanie optymalne, ponieważ wartość
funkcji celu ‘’ jest jednakowa, dla rozwiązań alternatywnych.
4. Jakie jest kryterium wyboru kolumny głównej w metodzie simpleksowej?
O tym, którą kolumnę wybierzemy, jako kolumnę główną decyduje wartość wskaźnika optymalności w danej
kolumnie.
Wybieramy tę, której wskaźnik optymalności jest najmniejszy z ujemnych (maksymalizacja) lub największy
z dodatnich (minimalizacja).
5. Jak zmienić nierówności istniejące w warunkach ograniczających na równania? Jak interpretować wprowadzone symbole?
Jeżeli chcemy zamienić nierówności w warunkach ograniczających na równania musimy, w przypadku:
− Znaku większości - odjąć zmienną niedoboru – określa ilość danego środka jakiej zabraknie w procesie
produkcji
− Znaku mniejszości - dodać zmienną nadmiaru – określa ilość danego środka jaki nie zostanie
wykorzystany w procesie produkcji
Są to tzw. zmienne bilansujące. Do funkcji celu wprowadzamy je ze współczynnikiem 0.
6. Skąd wiadomo, że wyznaczone rozwiązanie bazowe w danej iteracji metody simpleksowej nie jest optymalne? Rozpatrzyć dwa przypadki.
O tym, że rozwiązanie NIE jest optymalne decydują współczynniki optymalności .
Rozwiązanie NIE jest optymalne, gdy:
− Dla maksymalizacji 0
− Dla minimalizacji 0
7. Jakie jest kryterium wyboru wiersza głównego w metodzie simpleksowej?
Wybieramy ten wiersz, dla którego stosunek
jest najmniejszy, gdzie:
/
- wyrazy wolne w tablicy
simpleksowej, - wyrazy kolumny głównej.
Przy czym bierzemy pod uwagę tylko wartości dodatnie wyrazów wolnych.
1 | S t r o n a
ZARZĄDZANIE PRZEDSIĘWZIĘCIAMI BUDOWLANYMI.
Opracowanie: Anna Zielińska, Michał Gomoła
8. Jakie są znane główne zagadnienia optymalizacji? Czym się różnią od siebie?
Wyróżniamy dwa główne zagadnienia optymalizacji:
− Minimalizacja - np. kosztów produkcji danych wyrobów
− Maksymalizacja – np. zysków ze sprzedaży danych wyrobów
W przypadku minimalizacji chcemy, aby funkcja celu osiągnęła wartość minimalną, tzn., aby koszt przy danym planie produkcji był najmniejszy. Wtedy rozwiązanie będzie optymalne - wskaźniki optymalności muszą być NIEDODATNIE 0.
W przypadku maksymalizacji chodzi o to, aby funkcja celu osiągnęła wartość maksymalną, tzn., aby zysk przy danym planie produkcji był największy. Wtedy rozwiązanie będzie optymalne - wskaźniki optymalności muszą być
NIEUJEMNE 0.
9. Co to jest rozwiązanie alternatywne?
Rozwiązanie alternatywne to kolejne rozwiązanie optymalne, którego wartość funkcji celu jest taka sama
(najmniejsza dla minimalizacji i największa dla maksymalizacji), ale plan produkcji jest inny. Z rozwiązaniem alternatywnym mamy do czynienia, gdy po uzyskaniu rozwiązania optymalnego, w tabeli simpleksowej, chociaż jeden wskaźnik optymalności dla zmiennej SWOBODNEJ będzie równy zero 0.
10. Czym jest wskaźnik optymalności w metodzie simpleksowej? W jaki sposób go wyznaczyć i interpretować (2
przypadki).
Wskaźnik optymalności jest to różnica
,
gdzie
- współczynnik kosztu
- ilość wyprodukowanego produktu
współczynnik kosztu przy zmiennych w funkcji celu
-
Służy do oceny optymalności rozwiązania. Rozwiązanie jest optymalne, gdy:
− Dla maksymalizacji 0
− Dla minimalizacji 0
11. Czym jest kolumna i wiersz główny, co się z nimi dzieje w kolejnej iteracji?
Kolumna główna jest to kolumna, w której wskaźnik optymalności jest najmniejszy z ujemnych (maksymalizacja) lub największy z dodatnich (minimalizacja). Kolumna główna mówi nam to tym, która zmienna wejdzie do bazy w następnej iteracji –zacznie być zmienna bazową.
Wiersz główny to wiersz, dla którego stosunek
jest najmniejszy, gdzie:
/
- wyrazy wolne w tablicy
simpleksowej, - wyrazy kolumny głównej. Przy czym bierzemy pod uwagę tylko wartości dodatnie
wyrazów
wolnych. Wiersz główny określa, która zmienna wyjdzie z dotychczasowej bazy w następnej iteracji – przestanie być zmienną bazową.
12. Kiedy zmienna występująca w zagadnieniu jest bazowa?
Zmienna występująca w zagadnieniu będzie zmienną bazową, jeżeli występuje tylko w jednym z równań układu równań ograniczających. Jest ona częścią macierzy jednostkowej – rozwiązania bazowego.
13. Czy wartości sztucznej zmiennej bazowej jest istotna?
Tak, wartość sztucznej zmiennej bazowej jest istotna, ponieważ wprowadzamy ją do funkcji celu – wpływa na zysk lub koszt w danym rozwiązaniu. Jest ona wprowadzana z najbardziej niekorzystnym współczynnikiem. Dla
maksymalizacji przyjmuje ona wartość „ ”, a dla minimalizacji „ ”, gdzie 0.
14. Po co stosujemy sztuczne zmienne bazowe?
Stosujemy je po to by uzyskać dodatkową zmienną bazową, aby móc określić bazę. Wprowadzamy je wtedy,
gdy na wstępie (jeszcze przed znalezieniem rozwiązania dopuszczalnego) nie możemy określić bazy – do równań, które nie posiadają zmiennej bazowej należy dodać sztuczną zmienną bazową z kolejnym indeksem.
15. Jaki warunek muszę spełniać zmienne, aby osiągnąć dopuszczalne rozwiązanie bazowe?
Aby osiągać dopuszczalne rozwiązanie bazowe zmienne muszą przyjmować wartości nieujemne (WARUNEK
BRZEGOWY) – musimy mieć 0. Gdy na wstępie chociażby w jednym równaniu z układu równań występuje
0, to należy całe równanie pomnożyć przez (-1). Dodatkowo zmienne muszą spełniać warunki ograniczające -
być rozwiązaniem układu równań.
2 | S t r o n a
ZARZĄDZANIE PRZEDSIĘWZIĘCIAMI BUDOWLANYMI.
Opracowanie: Anna Zielińska, Michał Gomoła
16. Co to oznacza, że rozwiązanie jest optymalne? (Można wyjaśnić na przykładzie). Rozpatrzyć dwa przypadki.
Po wyznaczeniu rozwiązania bazowego (dopuszczalnego) wyznaczamy rozwiązanie optymalne. Rozwiązanie bazowe będzie optymalne, gdy:
− W przypadku minimalizacji funkcja celu osiągnie wartość minimalną, tzn. koszt przy danym planie produkcji będzie najmniejszy. Aby rozwiązanie było optymalne wskaźniki optymalności muszą być NIEDODATNIE
0.
− W przypadku maksymalizacji chodzi o to, aby funkcja celu osiągnęła wartość maksymalną, tzn., aby zysk przy danym planie produkcji był największy. Wtedy rozwiązanie będzie optymalne - wskaźniki optymalności muszą być NIEUJEMNE 0.
Co to znaczy
? To znaczy, że liczymy poszczególny zysk dla danej zmiennej
, od tego odejmujemy
- czyli wartość danej zmiennej z funkcji celu, uzyskujemy
, i na podstawie tego określamy optymalność
rozwiązania.
17. Jaki związek z rozwiązaniem bazowym ma macierz jednostkowa?
Macierz jednostkowa jest rozwiązaniem bazowym. Składa się z jednostkowych wektorów bazowych, w skład,
których wchodzą zmienne bazowe. Czyli takie, które występują tylko w jednym równaniu.
18. Czym jest zmienna bazowa?
Zmienna bazowa jest to zmienna będąca częścią bazy. Taka zmienna, która występuje tylko w jednym z równań układu współrzędnych. Wchodzi w skład macierzy jednostkowej, zbudowanej z wektorów bazowych. W każdej
kolejnej iteracji zmieniają się zmienne bazowe wchodzące do bazy. Określane są przez kolumny i wiersze główne macierzy simpleksowej.
19. Czym jest zmienna swobodna?
Zmienna swobodna jest to zmienna niewchodząca do bazy. Występuje w kilku równaniach ograniczających.
W kolejnych iteracjach może stać się zmienną bazową – wyznaczoną przez kolumnę i wiersz główny.
Wejdzie do bazy, gdy dla maksymalizacji wartość wskaźnika optymalności dla danej kolumny będzie
najmniejsza z ujemnych (lub największa z dodatnich przy minimalizacji).
20. Czym jest funkcja celu?
W danym zagadnieniu rozwiązywanym metodą simpleks mamy do czynienia z funkcją celu, Z, której wartości
ekstremalnej poszukujemy. Należy tak dobrać rozwiązanie danego problemu, w którym funkcja celu przyjmuje wartość minimum w przypadku minimalizacji kosztów lub maksimum w przypadku maksymalizacji zysku.
Funkcja celu wyraża się wzorem:
gdzie:
– zmienne decyzyjne;
- koszt (przy minimalizacji) lub zysk (przy maksymalizacji).
3 | S t r o n a
ZARZĄDZANIE PRZEDSIĘWZIĘCIAMI BUDOWLANYMI.
Opracowanie: Anna Zielińska, Michał Gomoła
Zagadnienia TRANSPORTOWE
21. Co to znaczy, że zagadnienie transportowe jest zbilansowane?
Zagadnienie transportowe zbilansowane występuje wtedy, gdy ilość towaru dostarczanego przez dostawców równa jest ilości towaru odbieranego przed odbiorców. Czyli zapotrzebowanie odbiorców jest równe zasobom dostawców.
22. Co zrobić, kiedy trasa (pomiędzy dostawcą z a odbiorcą y) została zamknięta z powodu remontu, a dowóz od dostawcy do odbiorcy okrężną drogą jest bardzo kosztowny?
W takim wypadku należy daną trasę zablokować, jako trasę zupełnie nieopłacalną. Żeby to zrobić dla trasy, którą chcemy wykluczyć nakładamy bardzo duży koszt przewozu ௬௫ , gdzie 0.
Takie zagadnienie możemy rozwiązać na dwa sposoby: znaleźć rozwiązanie optymalne dla normalnych kosztów, a potem inne optymalne dla trasy zablokowanej, lub zacząć rozwiązywać zadanie od razu z kosztem ௬௫ .
23. Co to są potencjały w zagadnieniu transportowym?
Potencjały oraz są to wielkości służące do oceny optymalności zagadnienia transportowego.
Wyznaczenie potencjałów jest potrzebne do obliczenia OCENY OPTYMALNOŚCI
,
! "
gdzie – koszt jednostkowy trasy.
Wartości potencjałów wyznacza się wg następujących zasad:
− Przyjmujemy 0
− Obliczamy potencjał bazując na wypełnionych klatkach i wiedząc, że oceny są dla tych klatek równe zero
− Po wyznaczeniu potencjałów obliczamy oceny dla klatek pustych
− Rozwiązanie jest optymalne, jeśli WSZYSTKIE oceny są NIEUJEMNE, 0.
24. Co zrobić w przypadku, kiedy ilość towaru, który jest oferowany przez wszystkich dostawców jest mniejsza od zapotrzebowania odbiorów?
W tym przypadku mamy do czynienia z zagadnieniem transportowym niezbilansowanym. Sumaryczna ilość towaru u dostawców jest mniejsza od łącznego zapotrzebowania odbiorców $ %. W tym przypadku należy prowadzić FIKCYJNEGO DOSTAWCĘ, któremu przydzielamy zapas równy niedoborowi towaru. Koszt przewozów towarów
od fikcyjnego dostawcy jest równy 0, ponieważ w rzeczywistości transakcje te się nie odbędą.
25. Jakie znasz metody wyznaczenia wstępnego rozwiązania bazowego w zagadnieniu transportowym?
1. Metoda kąta północno-zachodniego
2. Metoda minimalnego elementu w wierszu
3. Metoda minimalnego elementu w kolumnie
4. Metoda minimalnego elementu w macierzy
26. Co zrobić, gdy ilość towaru dostawców jest większa niż potrzeby odbiorów?
W tym przypadku mamy do czynienia z zagadnieniem transportowym niezbilansowanym. Sumaryczna ilość towaru u dostawców jest większa od łącznego zapotrzebowania odbiorców $ %. W tym przypadku należy prowadzić
FIKCYJNEGO ODBIORCĘ, któremu przydzielamy zapotrzebowanie równe nadmiarowi towaru. Koszt przewozów
towarów do fikcyjnego odbiorcy jest równy 0, ponieważ w rzeczywistości transakcje te się nie odbędą.
27. Jak sprawdzić, czy wstępne rozwiązanie bazowe wyznaczone jedną z metod jest optymalne?
Po wyznaczeniu wstępnego rozwiązania bazowego (dopuszczalnego), – czyli takiego, w którym dostawcy pozbędą się całego towaru, a odbiorcy otrzymają potrzebną im ilość towaru, ale nie koniecznie będzie to rozwiązanie najtańsze. Należy sprawdzić optymalność rozwiązania. W tym celu należy wyznaczyć potencjały oraz a na ich podstawie OCENY OPTYMALNOŚCI
, gdzie
! "
– koszt jednostkowy trasy.
Rozwiązanie bazowe będzie optymalne, jeśli WSZYSTKIE oceny będą NIEUJEMNE, 0.
28. Czym różni się metoda minimalnego elementu w kolumnie od metody minimalnego elementu w macierzy?
Obie metody służą do wyznaczenia wstępnego rozwiązania bazowego w zagadnieniu transportowym. Metoda
minimalnego elementu w kolumnie polega na rozpoczęciu wypełniania tabelki od kratki o najmniejszym koszcie transportu w danej kolumnie, po wypełnieniu konkretnej kolumny, szukamy najmniejszego kosztu w następnej kolumnie. W metodzie najmniejszego elementu w macierzy wybieramy koszt najmniejszy ze wszystkich kosztów w macierzy, bez różnicy, w której z kolumn czy wierszy.
4 | S t r o n a
ZARZĄDZANIE PRZEDSIĘWZIĘCIAMI BUDOWLANYMI.
Opracowanie: Anna Zielińska, Michał Gomoła
29. Czy metoda minimalnego elementu w kolumnie i metoda minimalnego elementu w wierszu to jedna i ta sama metoda? Jeżeli nie to, czym się różnią?
Nie jest to jedna i ta sama metoda, aczkolwiek są do siebie bardzo podobne. Obie metody służą do wyznaczenia wstępnego rozwiązania bazowego w zagadnieniu transportowym. Metoda minimalnego elementu w kolumnie
polega na rozpoczęciu wypełniania tabelki od kratki o najmniejszym koszcie transportu w danej kolumnie
(najczęściej pierwszej od lewej), po wypełnieniu konkretnej kolumny, szukamy najmniejszego kosztu w następnej kolumnie. Natomiast metoda minimalnego elementu w wierszu polega na wypełnieniu tabelki rozpoczynając od najmniejszego elementu w wierszu (najczęściej pierwszym).
30. Kiedy rozwiązanie jest optymalne w zagadnieniu transportowym?
Rozwiązanie optymalne to rozwiązanie dopuszczalne, (czyli takie, w którym dostawcy pozbędą się całego towaru, a odbiorcy otrzymają potrzebną im ilość towaru), które jednocześnie jest rozwiązaniem najtańszym – o
najmniejszym koszcie transportu towarów od dostawców do odbiorców, to, które generuje najmniejszy koszt.
Rozwiązanie bazowe będzie optymalne, jeśli WSZYSTKIE oceny optymalności będą NIEUJEMNE, 0.
Oceny optymalności wyznaczamy na podstawie potencjałów oraz . Obliczamy w następujący sposób:
, gdzie
! "
– koszt jednostkowy trasy.
31. Wymienić metody wyznaczania wstępnego rozwiązania bazowego w zagadnieniu transportowym.
5. Metoda kąta północno-zachodniego
6. Metoda minimalnego elementu w wierszu
7. Metoda minimalnego elementu w kolumnie
8. Metoda minimalnego elementu w macierzy
9. Metoda VAM – nie była omawiana na zajęciach
32. Co to jest rozwiązanie alternatywne w zagadnieniu transportowym?
Rozwiązanie alternatywne to inne rozwiązanie optymalne, generujące jednakowy koszt transportu, ale w inny sposób kształtujące powiązania pomiędzy odbiorcami a dostawcami. Z rozwiązaniem alternatywnym mamy
do czynienia, gdy w tabeli, chociaż jedna ocena optymalności dla zmiennej swobodnej jest równa zero - 0.
33. Na czym polega metoda kąta północno-zachodniego?
Metoda kąta północno-zachodniego jest metodą wyznaczania wstępnego rozwiązania bazowego w zagadnieniu
transportowym. Polega ona na tym, że zaczynamy wypełniać tabelę od kratki położonej najbardziej na górze i po lewej stronie, bez względu na to czy akurat w tej kratce koszt połączenia jest minimalny.
*Jeżeli wykreślamy na raz kolumnę i wiersz należy wpisać „zero bazowe” w kratce o najmniejszym koszcie, najbardziej na lewo lub najwyżej.
34. Na czym polega metoda minimalnego elementu w macierzy?
Metoda minimalnego elementu w macierzy jest metodą wyznaczania wstępnego rozwiązania bazowego
w zagadnieniu transportowym. Polega ona na tym, że zaczynamy wypełniać tabelę od kratki o najmniejszym koszcie w CAŁEJ TABLICY. Po jej wypełnieniu następną, którą wypełniamy jest kolejna kratka o minimalnym koszcie ze wszystkich kratek macierzy, które nie są jeszcze wypełnione.
35. Ile klatek/tras musimy wypełnić w zagadnieniu transportowym, aby otrzymać wstępne rozwiązanie bazowe?
Aby otrzymać wstępne rozwiązanie bazowe należy wypełnić następującą liczbę klatek:
& ' ( 1
gdzie: m - liczba dostawców
n - liczba odbiorców
36. Kiedy istnieje rozwiązanie alternatywne w zagadnieniu transportowym?
Z rozwiązaniem alternatywnym mamy do czynienia, gdy w tabeli, chociaż jedna ocena optymalności dla zmiennych swobodnych jest równa zero - 0. Rozwiązanie alternatywne to inne rozwiązanie optymalne, generujące
jednakowy koszt transportu, ale w inny sposób kształtujące powiązania pomiędzy odbiorcami a dostawcami.
5 | S t r o n a
ZARZĄDZANIE PRZEDSIĘWZIĘCIAMI BUDOWLANYMI.
Opracowanie: Anna Zielińska, Michał Gomoła
37. Kiedy mówimy, że zagadnienie transportowe jest niezbilansowane?
Zagadnienie transportowe niezbilansowane występuje wtedy, gdy ilość towaru dostarczanego przez dostawców NIE JEST równa ilości towaru odbieranego przed odbiorców. Czyli zapotrzebowanie odbiorców NIE jest równe zasobom dostawców.
Mamy do czynienia z 2 przypadkami zagadnienia niezbilansowanego:
− Sumaryczna ilość towaru u dostawców jest większa od łącznego zapotrzebowania odbiorców $ %
− Sumaryczna ilość towaru u dostawców jest mniejsza od łącznego zapotrzebowania odbiorców $ %
38. Kim jest i kiedy występuje fikcyjny dostawca?
Występowanie fikcyjnego dostawcy ma miejsce w zagadnieniach transportowych niezbilansowanych.
Występuje, gdy sumaryczna ilość towaru u dostawców jest mniejsza od łącznego zapotrzebowania odbiorców
$ %. FIKCYJNY DOSTAWCA to taki, któremu przydzielamy zapas równy niedoborowi towaru. Koszt przewozów
towarów od fikcyjnego dostawcy jest równy 0, ponieważ w rzeczywistości transakcje te się nie odbędą.
39. Kim jest i kiedy występuje fikcyjny odbiorca?
Występowanie fikcyjnego odbiorcy ma miejsce w zagadnieniach transportowych niezbilansowanych.
Występuje, gdy sumaryczna ilość towaru u dostawców jest większa od łącznego zapotrzebowania odbiorców $
%. FIKCYJNY ODBIORCA to taki, któremu przydzielamy zapotrzebowanie równe nadmiarowi towaru. Koszt
przewozów towarów do fikcyjnego odbiorcy jest równy 0, ponieważ w rzeczywistości transakcje te się nie odbędą.
40. Jak nazywamy zmienne występujące w klatkach „zajętych” a jak w klatkach „pustych”?
Zmienne w klatkach „zajętych” – to zmienne bazowe, są to zmienne , występujące w miejscach, gdzie występują
rzeczywiste połączenia między dostawcą „i” a odbiorcą „j”.
Zmienne w klatkach „pustych” – to zmienne swobodne, są to zmienne odpowiadająca za nieistniejące
połączenia między dostawcą a odbiorcą.
6 | S t r o n a