Microsoft Excel 2000
- 212 -
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:
)
,...,
,
(
2
1
n
x
x
x
f
,
gdzie: x
1
, x
2
,.....,x
n
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”.
Microsoft Excel 2000
- 213 -
Okno dialogowe Solver-Parametry zawiera te
ż listę
warunków ograniczaj
ących zakresy zmiennych x
k
, 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
Microsoft Excel 2000
- 214 -
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.
Microsoft Excel 2000
- 215 -
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
Microsoft Excel 2000
- 216 -
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.
Microsoft Excel 2000
- 217 -
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
3 8
9
2
5
7
4 6
4
5
1
3
P
ra
cow
ni
cy
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.
Microsoft Excel 2000
- 218 -
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.
Microsoft Excel 2000
- 219 -
Zadanie 63.
Turysta ma do wyboru 10 przedmiotów o wagach i warto
ściach
okre
ślonych w poniższej tabelce.
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.
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