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