Microsoft Excel 2000
Zagadnienia optymalizacyjne
Zagadnienia
optymalizacyjne
dotyczą
efektywnego
wykorzystania zasobów lub optymalnego rozmieszczenia posiadanych
środków, tak aby były spełnione określone wymagania.
Zagadnienia te mają na ogół więcej niż jedno rozwiązanie
spełniające podstawowe stawiane im warunki. Wybór jednego spośród
tych rozwiązań zależy od celu jaki chcemy osiągnąć i wymagań
zawartych w sformułowaniu problemu.
Ogólne
sformułowanie
matematyczne
zagadnienia
optymalizacyjnego może być przedstawione następująco.
Zoptymalizować
(tzn
zmaksymalizować,
zminimalizować,
spowodować aby przyjęła określoną wartość) funkcję celu postaci:
f ( x , x ,..., x ) ,
1
2
n
gdzie: x1, x2,.....,xn są zmiennymi decyzyjnymi, których wartości w
wyniku procesu optymalizacyjnego zostaną ustalone na takie, które
powodują realizację założonego celu. Początkowe wartości tych
zmiennych są umieszczone w tych komórkach arkusza, które
wskazane zostaną w oknie dialogowym Solver-Parametry w polu
edycyjnym o nazwie Komórki zmieniane.
Formuła odpowiadająca funkcji celu jest umieszczana w
komórce arkusza zwanej Komórką celu (odwołanie do niej podajemy
we wspomnianym wyżej oknie dialogowym w polu edycyjnym o
nazwie Komórka celu). Związek określony funkcją celu może być
związkiem liniowym lub nie. W przypadku liniowym mamy do
czynienia z „zagadnieniem programowania liniowego”.
- 212 -
Microsoft Excel 2000
Okno dialogowe Solver-Parametry zawiera też listę
warunków ograniczają cych zakresy zmiennych xk, lub warunków nakładanych na zależności funkcyjne wiążące te zmienne.
Narzędzie Solver w programie Excel służy do rozwiązywania
wszelkich dobrze sformułowanych zagadnień optymalizacyjnych, nie
tylko zagadnień programowania liniowego.
Wśród praktycznych zagadnień, które można rozwiązywać z
zastosowaniem narzędzia Solver możemy wymienić:
• analizę działalności gospodarczej (maksymalizacja zysku w
procesie produkcji; minimalizacja kosztu wytwarzania,
transportu; optymalne rozmieszczenie pracowników itd.),
• zagadnienie optymalnego składu diety,
• zagadnienia transportowe,
• zagadnienie podróżującego kupca.
W przykładach z rozwiązaniem podanych niżej oraz w kilku
zadaniach do samodzielnego rozwiązania czytelnik znajdzie
praktyczne wskazówki jak wykorzystywać narzędzie Solver do
rozwiązywania zagadnień optymalizacyjnych
Uwaga!
W przypadku trudności ze znalezieniem rozwiązania można próbować
zmieniać opcje Solvera dostępne po kliknięciu w przycisk Opcje w
oknie Solver -Parametry. Daje on dostęp do ustaleń dotyczących
sposobu realizacji procesu iteracyjnego poszukiwania rozwiązania.
Maksymalny czas w sekundach (do 32767), liczba iteracji (jak wyżej),
dokładność, tolerancja (wartość procentowa informująca na ile
wartość w komórce celu rozwiązania zadania z może odbiegać od
wartości optymalnej, aby można ją uznać za możliwą do
zaakceptowania), zbieżność (kiedy względna zmiana wartości w
komórce celu dla pięciu ostatnich iteracji jest mniejsza niż liczba
- 213 -
Microsoft Excel 2000
podana w polu Zbieżność, przerywane jest poszukiwanie rozwiązania.
Zbieżność odnosi się tylko do zadań nieliniowych i musi być
określona przez liczbę ułamkową z przedziału pomiędzy 0 i 1). Okno
opcji zawiera jeszcze dalsze opcje, których pobieżne omówienie
znajduje się w systemie Pomocy .
Zadanie 60.
Fabryka produkuje cztery typy samochodów: Hatch, Sedan, Jeep,
Wagon. Ze względu na ograniczony popyt produkcja wszystkich
modeli łącznie nie powinna przekroczyć 1000 sztuk. Czas pracy,
Zasoby materiału (stal) oraz zysk dla poszczególnych modeli
przedstawia poniższa tabelka.
Hatch
Sedan
Jeep
Wagon
Czas
80
130
110
140
Stal
0,76
1
0,72
1,5
Zysk/szt
625
825
600
1200
Ze względu na to by nie musieć zwalniać pracowników wymagane
jest wyprodukowanie każdego z modeli w ilości większej niż 100
sztuk i mniejszej niż 700 sztuk. Łączne zasoby czasu pracy wynoszą
125000 jednostek, a materiałów 900 jednostek. Zbudować model,
który pozwoli określić jaką ilość każdego z modeli należy
wyprodukować, aby zysk fabryki był jak największy.
- 214 -
Microsoft Excel 2000
Rozwiązanie.
Przygotowujemy arkusz kalkulacyjny jak na poniższym rysunku
Kolumna G zawiera ograniczenia na pracochłonność, ilość łączną
oraz zużycie materiału wynikające z treści zadania. W komórkach H5
oraz H7 wpisujemy formuły obliczające zużycie czasu pracy oraz stali
jako iloczyny skalarne odpowiednich zakresów arkusza. Funkcja celu
obliczająca łączy zysk umieszczona jest w komórce B15 i widać ją w
pasku formuły.
Przystępując do rozwiązania zadania wybieramy z menu Narzędzia
opcję Solver... ,co powoduje wyświetlenie okienka dialogowego
- 215 -
Microsoft Excel 2000
Solver - Parametry. Wskazujemy w nim komórkę celu, zaznaczamy,
że chodzi o maksimum i podajemy zakres komórek zmienianych,
którymi
są
wysokości
produkcji
poszczególnych
modeli.
Wykorzystując klawisz Dodaj należy wprowadzić warunki
ograniczają ce. Po zaakceptowaniu następuje uruchomienie procesu iteracyjnego wyszukiwania rozwiązania.
Na rysunku widać ilości samochodów poszczególnych modeli jakie
należy wyprodukować aby zmaksymalizować zysk łączny. Można też
zauważyć, że zasoby stali zostaną wykorzystane w całości,
wyprodukuje się 1000 sztuk ale są rezerwy w czasie pracy.
Wykorzystując klawisz Zapisz scenariusz można zapamiętać
znalezione rozwiązanie w celu późniejszej prezentacji (Narzędzia |
Scenariusze... ). Możliwe jest też wygenerowanie raportów wyników,
wrażliwości i granic. W przypadku poszukiwania rozwiązań w
liczbach całkowitych sens ma tylko raport wyników.
- 216 -
Microsoft Excel 2000
Zadanie 61.
Wykorzystując poprzedni model znaleźć taką ilość materiału (stali),
która pozwoliłaby osiągnąć zysk łączny w wysokości 1 000 000
jednostek przy zachowaniu pozostałych ograniczeń bez zmiany.
Zadanie 62.
W firmie jest pięć wolnych stanowisk pracy i jest też pięciu
pracowników, których wartość na poszczególnych stanowiskach
pokazuje poniższa tabelka.
Stanowiska
1
2
3
4
5
1 5
4
7
6
3
2 6
7
3
4
5
cy 3 8
9
2
5
7
ni
4 6
4
5
1
3
racowP 5 3
5
6
8
4
Dobrać tak przyporządkowanie pracowników do stanowisk, aby
korzyść firmy była maksymalna.
Rozwiązanie.
Przygotowujemy
arkusz
zawierający tabelkę z wartościami
pracowników na stanowiskach oraz drugą zawierającą podsumowania
wierszy i kolumn, a w obszarze odpowiadającym wartościom w
pierwszej tabeli wstawiamy same zera, jak na niżej zamieszczonym
rysunku.
- 217 -
Microsoft Excel 2000
Komórką aktywną jest H18, więc widoczna w linii edycji formuła
znajduje się właśnie w tej komórce. Komórki H15 do H17 zawierają
analogiczne formuły (suma wiersza). Komórki C19 do G19 zawierają
podobne formuły sumujące kolumny. Po wybraniu opcji Solver... z
menu Narzędzia zostaje wyświetlone okno dialogowe Solver –
Parametry, gdzie podobnie jak poprzednio dodajemy warunki
ograniczające. Pierwsze trzy warunki gwarantują, że znalezione
rozwiązanie będzie składało się z licz 0 lub 1. Ostatnie dwa warunki
gwarantują obsadę każdego stanowiska przez dokładnie jednego
pracownika. Komórka celu ($C$23) zawiera iloczyn skalarny
zakresów C5:G9 oraz C14:G18. W wyniku uruchomienia procesu
iteracyjnego znajdujemy maksymalną wartość komórki celu równą 35.
- 218 -
Microsoft Excel 2000
Zadanie 63.
Turysta ma do wyboru 10 przedmiotów o wagach i wartościach
określonych w poniższej tabelce.
1
2
3
4
5
6
7
8
9
10
Waga
3
6
2
7
4
3
5
6
1
3
Warto
1
2
1
3
2
1
3
2
1
1
Zakładając, że turysta może wziąć co najwyżej jedną sztukę każdego
przedmiotu znaleźć taką zawartość plecaka aby jego wartość była
maksymalna, a waga nie przekraczała 32 kilogramów.
Zadanie 64.
Istnieją cztery bazy lotnicze i trzy miejsca odbioru towarów. Każda
baza może wykonać nie więcej niż 150 lotów dziennie. Każdy punkt
odbioru towarów powinien przyjąć nie mniej niż 200 lotów dziennie.
Ilość ton towarów dostarczonych w jednym locie z bazy do punktu
odbioru przedstawia tabelka.
Miejsca odbioru
Bazy
1
2
3
1
8
6
5
2
6
6
6
3
10
8
4
4
8
6
4
Znaleźć rozkład lotów z każdej bazy do każdego punktu odbioru,
który maksymalizuje całkowitą ilość przetransportowanych towarów.
- 219 -