Zadania transportowe - samouczek PDF

Preview

Summary

Sposób wykonywania zadań transportowych...

Description

TEORIA GRAFÓW - PORADNIK WYKONYWANIA ZADAŃ 1. METODA SIMPLEX Zad1. Str.5 Zadanie 1 (KK, Zadanie 12, str. 31) Przedsiębiorstwo może produkować cztery wyroby: A, B, C i D. Ograniczeniem w procesie produkcji są zasoby dwóch surowców: S1 i S2. Niezbędne dane zawiera poniższa tabela:

Surowce

S1 S2

Zużycie surowca na jednostkę wyrobu (w Zapas surowca (w kg) kg) A B C D 0,5

0,4

0,4

0,2

2000

0,4

0,2

0

0,5

2800

Ceny wyrobów wynoszą odpowiednio 10, 14, 8 i 11 zł. Należy ustalić wielkości produkcji tych wyrobów gwarantujące przy istniejących zasobach surowców maksymalny przychód z ich sprzedaży.

Rozwiązanie: Krok 1. Tworzenie tabeli Na początek musimy zbudować sobie tabelkę w Excelu. Widzimy, że w treści zadania mamy 4 produkty, do których wyprodukowania potrzebujemy 2 rodzaje surowca. Każdy surowiec, ma swój zapas (ograniczenie) – czyli mamy 2 ograniczenia. Dlatego budujemy tabelkę 2x6. 2 – ponieważ mamy dwa surowce które są ograniczone zapasami 6 – bo mamy 4 produkty + dwa miejsca na zmienne bilansujące, które odpowiadają liczbie ograniczeń

Tak skonstruowana tabelka jest gotowa, żeby zacząć ją wypełniać. Krok 2. Wypełnienie tabeli Zaczynamy od wypełnienia tabeli danymi, które posiadamy z treści zadania, aby w kolejnym kroku zająć się konstruowaniem formuł. Legenda:

cb – tabelka zmiennych którą będziemy uzupełniać w dalszych tablicach. W pierwszej tablicy, musi być w każdej kratce 0, cj – wiersz, w którym należy wpisać ceny wyrobów, x1,x2,x3,x4 – w te kolumny wpisujemy wartości z tabeli z treści zadania, odnoszące się odpowiednio do A,B,C i D, Rozwiązanie (bi) – w tą kolumnę wpisujemy ograniczenia, w tym wypadku zapas surowca S1 i S2, Zmienne bazowe – tak jak wcześniej wspomniałem, mamy dwie zmienne bilansujące (odpowiadające liczbie ograniczeń). W tabeli zmienne bazowe, wpisujemy x5 oraz x6. x5, x6 – w tej kolumnie, cyfrę „1” wpisujemy w ten wiersz, który odpowiada tej zmiennej w zmiennych bazowych, a w kolejnym wierszu wpisujemy „0”.

Tak wygląda prawidłowo wypełniona pierwsza tabela, od której zaczynamy kolejne kroki. Teraz należy, wpisać odpowiednie formuły, które obliczą nam kolejne miejsca w tabeli. Krok 3. Formuły Interesują nas teraz dwa wiersze, które mają ogromny wpływ na dalszą część zadania. zj – jest to wiersz, który na samym końcu obliczy nam wynik funkcji celu, czyli jednej ze składowych odpowiedzi końcowej do zadania. W pierwszej kratce tego wiersza musimy zastosować funkcję =SUMA.ILOCZYNÓW Korzystając z tej funkcji, będziemy mnożyć kolumny iksów z kolumną cb.

W pierwszej komórce zj, korzystając z funkcji sumy iloczynów, musimy zablokować tabelę cb poprzez naciśnięcie przycisku F4. Blokowanie jest obowiązkowe, bo będziemy funkcję przesuwać po kolumnach w prawo i bez blokowania mnożyło by nam z każdą kolejną kolumną, a chcemy tylko żeby mnożyło razy kolumnę cb.

cj-zj – tak jak nazwa wiersza, musimy w pierwszej komórce zastosować odejmowanie i następnie przeciągnąć je do końca tabeli.

Wypełniliśmy do końca tabelę, więc można teraz wyciągnąć z niej ważne informacje. Żeby przejść do następnej tabeli, musimy znaleźć największą wartość w wierszu cj-zj. Zgodnie z powyższą tabelą, największa wartość to 14 i jest w kolumnie x2. Musimy teraz stworzyć kolejną kolumnę, w której podzielimy kolumnę bi z wartościami kolumny x2.

W pierwszej komórce bi/x2 mamy proste dzielenie: Dzięki tej ostatniej operacji wiemy, że do bazy wejdzie nam x2 w miejsce x5. Dlaczego w miejsce x5? Ponieważ po podzieleniu bi/x2 przy x5 otrzymaliśmy 5000 a przy x6 otrzymaliśmy 14000. Zastępujemy tą zmienną, której wynik po dzieleniu jest mniejszy. Krok 4. Tworzenie tabeli nr 2 Po wykonaniu wszystkich powyższych czynności przechodzimy do tworzenia drugiej tabeli. Jest ona tych samych rozmiarów, jednakże musimy w niej zaktualizować dane.

W zmiennych bazowych, zamiast x5 wstawiamy x2, ponieważ tak nam wyszło w poprzedniej tabeli. W tym samym wierszu, do kolumny cb wpisujemy cenę (wartość z cj odpowiadającą produktowi x2), w tym przypadku 14. Zostawiamy formułę w wierszu zj oraz w wierszu cj-zj. Wnętrze tabeli czyścimy i będzie ona wyglądać tak jak powyżej.

Krok 5. Tabelka pomocnicza Do wypełnienia tabeli głównej, potrzebujemy skorzystać z kilku formuł i wykonać kilka obliczeń. Niezbędna będzie do tego tabelka pomocnicza, którą stworzymy sami. Jako, że będziemy korzystać z formuły macierzy odwrotnej, stworzymy sobie dwie tabelki 2x2.

Do tabelki BI kopiujemy wartości z pierwszej tablicy, znajdujące się pod x2 oraz x6. Dlaczego przy nich? Bo zgodnie z tym co jest w tabelce, one są w naszej „bazie”, czyli są to zmienne bazowe i do nich się odwołujemy. W pierwszej kratce, musimy skorzystać z formuły „macierz odwrotna”, ponieważ chcemy wyliczyć macierz odwrotną tabelki BI. W komórce wpisujemy formułę

, zaznaczając tabelę BI.

W pierwszej kratce w tym wypadku pojawi się wynik 2,5. Teraz, należy na tą kratkę najechać, zaznaczyć całą tabelkę (2,5 oraz trzy puste kratki) i wcisnąć F2 (wyświetli się formuła oraz znów na niebiesko zaznaczy się tabela wyżej), a następnie jednocześnie wcisnąć Ctrl, Shift i Enter.

Tabelka zostanie automatycznie wypełniona pozostałymi wartościami obliczonymi przez Excela.

Krok 6. Macierz iloczyn tabela główna Teraz możemy przejść do wypełnienia tabeli głównej. Oczywiście za pomocą formuły. Przechodzimy do komórki znajdującej się pod x1 i będziemy używać formuły „macierz iloczyn”.

Wpisujemy =MACIERZ.ILOCZYN po czym zaznaczamy tabelkę pomocniczą BI-1. Jako, że iloczyn to mnożenie, musimy tą tabelkę z czymś pomnożyć. Będziemy ją mnożyć z tabelą główną nr1, czyli tą z początku zadania. Dodajemy średnik (;) i przechodzimy do pierwszej tabeli aby zaznaczyć cały obszar od x1 aż do kolumny bi, tak jak poniżej widać.

Zamykamy nawias i klikamy enter. W naszej pierwszej komórce pojawi się wynik 1,25. Teraz musimy zaznaczyć ten sam obszar (od x1 aż do kolumny bi) w naszej tabeli nr2. Po zaznaczeniu tego obszaru, klikamy F2, a następnie jednocześnie trzeba kliknąć Ctrl, Shift i Enter.

Po wciśnięciu tych klawiszy, tabelka cała się wypełni, ze względu na fakt, że mamy już wcześniej wpisane formuły w komórkach zj oraz cj-zj. W ten sposób mamy już uzupełnioną tabelę nr2. Należy z niej wyciągnąć wnioski i sprawdzić, czy musimy robić tabelę nr3. Patrzymy na wiersz cj-zj i szukamy najwyższej wartości. Widzimy, że jest to wartość 4 w kolumnie x4. Pozostałe wartości albo są zerowe albo ujemne. Oznacza to, że „zerowe” kolumny nie poprawią nam wyniku rozwiązania zadania, a te ujemne go pogorszą. Dlatego szukamy dodatniej najwyższej wartości, która wskazuje nam, że możemy poprawić wynik rozwiązania zadania. Po tej analizie widać, że musimy zrobić tabelę nr3. Co dalej? Robimy kolumnę pomocniczą bi/x4, aby dowiedzieć się, którą zmienną zastąpi x4.

W zasadzie było to logiczne, że będzie to zmienna x6, jednakże warto zawsze to sprawdzić. Teraz wiemy, że w tabeli nr 3, x4 zastąpi x6 i możemy przejść do tworzenia tabeli nr3. Krok 7. Tworzenie tabeli nr3 Tworzymy tabelę nr3, analogicznie do tego, jak tworzyliśmy tabelę nr2. W zmiennych bazowych, zamiast x6 wstawiamy x4. W kolumnie cb, pod liczbą14 umieszczamy liczbę 11 (cenę znajdującą się nad x4). Zostawiamy formuły w wierszach zj oraz cj-zj. Tak powinna wyglądać prawidłowo stworzona tabela nr3:

Krok 8. Tabelka pomocnicza Nie obejdzie się bez stworzenia kolejnej tabeli pomocniczej. Tym razem interesują nas wartości przy x2 oraz x4, ponieważ te zmienne są w naszej „bazie”. Wartości kopiujemy z pierwszej tabeli (początkowej nr1).

Tak prawidłowo stworzona tabelka pomocnicza, pozwala nam przejść ponownie do obliczenia macierzy odwrotnej. Tak jak wcześniej, klikamy na pierwszą komórkę tabeli BI-1 i stosujemy formułę =MACIERZ.ODW zaznaczając tabelę BI, której macierz chcemy obliczyć.

Dostajemy wynik 3,125 i czas zaznaczyć tą komórkę z pozostałymi trzema kratkami. Znów aby wypełniła się tabelka, musimy wcisnąć F2, a następnie jednocześnie wcisnąć Ctrl, Shift i Enter.

Tabelka się wypełni, a my możemy przejść do wypełnienia tabeli głównej.

Krok 9. Macierz iloczyn tabela główna nr 3 Sytuacja jest dokładnie taka sama jak w przypadku poprzedniej tabeli (nr2). Klikamy na komórkę znajdującą się pod komórką x1 i będziemy używać formuły „macierz iloczyn”.

Wpisujemy =MACIERZ.ILOCZYN po czym zaznaczamy tabelkę pomocniczą BI-1. Jako, że iloczyn to mnożenie, musimy tą tabelkę z czymś pomnożyć. Będziemy ją mnożyć z tabelą główną nr1, czyli tą z początku zadania. Dodajemy średnik (;) i przechodzimy do pierwszej tabeli aby zaznaczyć cały obszar od x1 aż do kolumny bi, tak jak poniżej widać.

Zamykamy nawias i klikamy enter. W naszej pierwszej komórce pojawi się wynik 1,0625. Teraz musimy zaznaczyć ten sam obszar (od x1 aż do kolumny bi) w naszej tabeli nr2. Po zaznaczeniu tego obszaru, klikamy F2, a następnie jednocześnie trzeba kliknąć Ctrl, Shift i Enter.

Po wciśnięciu tych klawiszy, tabelka cała się wypełni, ze względu na fakt, że mamy już wcześniej wpisane formuły w komórkach zj oraz cj-zj. W ten sposób mamy już uzupełnioną tabelę nr3. Należy z niej wyciągnąć wnioski i sprawdzić, czy musimy robić tabelę nr4. Krok 10. Wnioski i rozwiązanie Patrzymy na tabelę, na wiersz cj-zj i szukamy najwyższej dodatniej wartości. Okazuje się, że są albo wartości „zerowe” albo ujemne. Oznacza to, że żadna inna zmienna nie jest w stanie poprawić już naszych wyników, czyli nie ma sensu robienia kolejnych tabel, ponieważ nic one nie zmienią. Widząc, że zadanie jest zakończone, musimy jeszcze dostarczyć odpowiedź na zadanie. Musimy podać jakie jest x1,x2,x3,x4 oraz jaka jest funkcja celu. To wszystko, odczytamy z tabeli.

ROZWIĄZANIE: X1=0 X2=2750 X3=0 X4=4500 FUNKCJA CELU=88000 Dlaczego X1 oraz X3 są równe zero? Ponieważ nie ma ich w naszej „bazie”. W naszej bazie znajdują się tylko X2 oraz X4, co oznacza, że aby zdobyć największy przychód ze sprzedaży, nie będziemy produkować wyrobów X1 oraz X3, dlatego ich wynik jest równy zero. Czyli aby mieć jak największy zysk ze sprzedaży, powinniśmy wyprodukować 2750 produktów X2 oraz 4500 produktów X4, dzięki czemu zarobimy 88000.

2. ZADANIA TRANSPORTOWE – METODA SOLVER Zad2. Str 7. Trzy magazyny: M1, M2 i M 3 zaopatrują w mąkę cztery piekarnie: P 1, P2, P3 i P4. Jednostkowe koszty transportu (w zł za tonę), miesięczne wielkości dostaw Ai, (w tonach) oraz miesięczne zapotrzebowania piekarni Bj (w tonach) podaje tablica:

Piekarnie

Magazyny

Ai

M1 M2

P1 50 40

P2 40 80

P3 50 70

P4 20 30

100 50

M3

60

40

70

80

80

Bj

40

60

50

50

Jednostkowe koszty magazynowania wynoszą w magazynie: M1 — 5 zł, (c15 = 5), M2 — 5 zł (c25 = 5), M3 — 6 zł (c 35= 6) za tonę. Opracować plan przewozu i magazynowania nadwyżki mąki minimalizujący całkowite koszty transportu i magazynowania.

Rozwiązanie: Zadanie polega na tym, że chcemy zaopatrzyć wszystkie piekarnie, korzystając z zapasów ze wszystkich magazynów i jak najmniej za to zapłacić. Czyli będziemy szukać minimum funkcji. Ai – jest to ilość mąki jaka jest w magazynie Bj – to zapotrzebowanie piekarni na mąkę Krok 1. Tabelka Zaczynamy od stworzenia w excelu tabeli podobnej do tej z treści zadania, tylko że dodamy kolumnę kosztów magazynowania.

Skąd wiadomo, że Bj dotyczące kosztów magazynowania wynosi 30? Widzimy, że ilość mąki w magazynach to 230 ton (100+50+80), a zapotrzebowanie wszystkich piekarni to 200 ton (40+60+50+50). To oznacza, że trzeba będzie przechować 30 ton mąki w magazynach, za co będziemy musieli zapłacić.

Krok 2. Tabela obliczeniowa Żeby użyć solvera i móc obliczyć całe zadanie, musimy stworzyć kolejną tabelę, w której solver dokona obliczeń. Będzie to taka sama tabela jak ta powyżej, tylko że na początku szare, różowe i niebieskie pola wypełnimy zerami. Dodatkowo stworzymy sobie komórkę „Funkcja celu”, w której obliczymy minimalny koszt. Żeby solver mógł zadziałać, w szare i niebieskie pola będziemy musieli wpisać odpowiednie formuły, ale o tym zaraz.

Krok 3. Formuły w komórkach Solver będzie zmieniał wartości w kolorowych polach, ale nie zrobi tego jeśli nie będziemy mieli założeń i formuł. W szarych polach chcemy, żeby dodał w kolumnie wartości z pól różowych – czyli chcemy żeby każda piekarnia w sumie dostała całe miesięczne zapotrzebowanie (nieważne czy z jednego czy z trzech magazynów, w sumie z trzech ma być zapotrzebowanie zapełnione). Dlatego w komórkach szarych będziemy sumować wartości w kolumnie.

Przykład dla szarej komórki dla piekarni P1 W niebieskich komórkach chcemy, żeby z każdego magazynu wyszła całą mąka. Nieważne czy do jednej piekarni pójdzie wszystko czy zostanie to rozdane po trochu do każdej z nich, ponieważ chcemy żeby w sumie magazyny zostały opróżnione. Dlatego w niebieskich komórkach będziemy sumować komórki w wierszu.

Przykład dla niebieskiej komórki magazynu M1

Zostaje nam jeszcze komórka funkcji celu, czyli obliczenie kosztu całej operacji, której celem jest minimum (aby koszt był jak najniższy). Będziemy korzystać z funkcji „suma iloczynów”, w której będziemy mnożyć różowe pola z obu tabel.

Krok 4. Ustawienia solvera 1. Teraz musimy użyć solvera, który za nas dokona obliczeń na podstawie założeń, które mu damy. Musimy zacząć od ustawienia celu, którym jest komórka „Funkcja celu”.

2. Ustawiamy „Min”, ponieważ chcemy obliczyć minimum tej funkcji. Zmieniane komórki, w których chcemy wyniki, to różowe pola w drugiej tabeli. Dlatego pole „Przez zmienianie komórek zmiennych”, ustawimy właśnie te różowe komórki z drugiej tabeli

3. Musimy dodać ograniczenia. Pierwszym ograniczeniem jest to, aby wartości szarych komórek w drugiej kolumnie, były równe wartościom szarych komórek w pierwszej tabeli. Ponieważ, tak jak wcześniej założyliśmy, chcemy aby wszystkie piekarnie dostały tyle mąki ile potrzebują.

4. Drugim ograniczeniem jest to, aby wartości niebieskich komórek w drugiej tabeli, były równe wartościom niebieskich komórek w pierwszej tabeli. Ponieważ, tak jak wcześniej założyliśmy, chcemy wykorzystać całą mąkę ze wszystkich magazynów.

5. Po ustawieniu ograniczeń, zostaje nam sprawdzenie czy mamy zaznaczone aby nie było w rozwiązaniu wartości ujemnych oraz czy na pewno korzystamy z metody LP simpleks.

Krok 5. Rozwiąż Teraz zostaje nam tylko uruchomienie w solverze funkcji „Rozwiąż”. Solver rozwiąże to zadanie za nas, dzięki ustawieniom które wcześniej mu zadaliśmy. Poprawny rozwiązanie wygląda tak:

Co wyszło? Wyszło, że:   

całkowite najniższe koszty magazynowania i transportu to 7670 (zł), wszystkie piekarnie zostaną w pełni zaopatrzone w magazynach M2 i M3 zostanie analogicznie 10t i 20t mąki, za które będziemy musieli zapłacić...