POLITECHNIKA

Ś

L

Ą

SKA

WYDZIAŁ TRANSPORTU

KATEDRA SYSTEMÓW INFORMATYCZNYCH TRANSPORTU

ROK AKADEMICKI 2010/2011

LABORATORIUM Z ORGANIZACJA I ZARZ

Ą

DZANIE

SPRAWOZDANIE Z

Ć

WICZENIA LAB.NR 4

TEMAT: Zagadnienia plecakowe.

Data wykonania

ć

wiczenia lab. 14.04.2011

GRUPA DZIEKA

Ń

SKA T21 B

1. MICHAŁ KUDELA

2. JAROMIR BRACKI

KATOWICE ,DNIA 25.04.2011

1. Wst

ę

p teoretyczny

W procesie zarz

ą

dzania firm

ą

, a szczególnie w trakcie planowania jej rozwoju z reguły

rozpatrywane s

ą

ró

ż

ne warianty. Niektóre z nich wzajemnie si

ę

wykluczaj

ą

, a niektóre

mog

ą

by

ć

realizowane równolegle. Nawet, gdy od strony technicznej nic nie stoi na

przeszkodzie w jednoczesnej realizacji kilku projektów nale

ż

y mie

ć

na uwadze

ograniczone mo

ż

liwo

ś

ci finansowania tych inwestycji. Mo

ż

e zdarzy

ć

si

ę

tak,

ż

e trzeba

dokona

ć

wyboru pewnego podzbioru spo

ś

ród wszystkich mo

ż

liwych do realizacji

projektów, tak aby nie przekroczy

ć

przeznaczonych na nie funduszy. Przy wyborze

nale

ż

y kierowa

ć

si

ę

jak najlepszym wykorzystaniem tych funduszy oraz ewentualnie

spodziewanym w wyniku ich realizacji zyskiem. Od strony matematycznej problemy te s

ą

opisane przez zagadnienie plecakowe i problem złodzieja.

Zagadnienie plecakowe
Mamy n przedmiotów, których ci

ęż

ary wynosz

ą

w

1

, w

2

, ..., w

n

. W plecaku mo

ż

na

zmie

ś

ci

ć

przedmioty o sumarycznej wadze nie przekraczaj

ą

cej W. Jakie wybra

ć

przedmioty do zapakowania, aby nie przekraczaj

ą

c maksymalnej wagi plecaka zmie

ś

ci

ć

w nim jak najwi

ę

kszy ci

ęż

ar? Przedmioty musz

ą

by

ć

zapakowane w cało

ś

ci - nie mo

ż

na

wybra

ć

ułamka przedmiotu.

Problem złodzieja
Złodziej ma worek, w którym da si

ę

umie

ś

ci

ć

przedmioty o sumarycznym ci

ęż

arze nie

przekraczaj

ą

cym W. Jakie przedmioty ma zapakowa

ć

do swojego worka, je

ś

li do wyboru

ma n łupów o wagach w

1

, w

2

, ..., w

n

i warto

ś

ciach

c

1

, c

2

, ..., c

n

, tak aby wartość skradzionych dóbr była jak największa? Złodziej nie może

wybrać ułamka przedmiotu.

2. Rozwi

ą

zanie zadania

Przykład I

1) Pewna firma przeznaczyła 40 000 zł na inwestycje. Rozpatrywane są

różne

projekty, które wymagają

zróżnicowanych nakładów (nakłady przedstawiono w

tabeli poniżej). Należy dokonać

takiego wyboru projektów, aby jak najlepiej

wykorzystać

przeznaczone na inwestycje fundusze, jednocześnie nie przekraczając

ich.

Projekty Nakład
Projekt 1

20000

Projekt 2

50000

Projekt 3

80000

Projekt 4

100000

Projekt 5

120000

Projekt 6

60000

Projekt 7

70000

Projekt 8

40000

Projekt 9

30000

Projekt
10

10000

Projekt
11

90000

Projekt
12

110000

Do rozwiązania problemu będzie użyty SOLVER – poszukiwane zmienne będą mogły

przyjmować wartości stałe (0 – projekt odrzucony; 1 – projekt zaakceptowany).

Maksymalizowana jest suma inwestycji, lecz nie może przekroczyć funduszu firmy.

W kolumnie D znajdują się iloczyny nakładu projektu ze stała 1 (projekt zaakceptowany)

lub 0 (projekt odrzucony),która została wyznaczona za pomocą programu SOLVER .

Wyrażenie „suma” określa sumę wszystkich kosztów wybranych projektów nie

mogących przekroczyć dostępnych funduszy.

„=B2*D2”

„=SUMA(F2:F13)”

SOLVER został uzupełniony następującymi formułami:

Przykład II

Pewna firma przeznaczyła 40 000 zł na inwestycje. Rozpatrywane są rożne projekty, które

wymagają zróżnicowanych nakładów finansowych i szacuje się, przyniosą różne zyski.

Należy dokonać takiego wyboru projektów, aby spodziewany zysk był jak największy,

jednocześnie nie przekraczając funduszu przeznaczonego na inwestycje.

Projekty Nakład

Zysk

Projekt 1

20000

60000

Projekt 2

50000

60000

Projekt 3

80000

90000

Projekt 4

100000

150000

Projekt 5

120000

200000

Projekt 6

60000

70000

Projekt 7

70000

80000

Projekt 8

40000

41000

Projekt 9

30000

33000

Projekt
10

10000

47000

Projekt
11

90000

110000

Projekt
12

110000

170000

Do rozwiązania problemu będzie użyty SOLVER – poszukiwane zmienne będą mogły

przyjmować wartości stałe (0 – projekt odrzucony; 1 – projekt zaakceptowany).

Maksymalizowana jest suma zysków z projektów, przy czym suma ich wartości nie może

przekroczyć przeznaczonych funduszy na inwestycje.

W kolumnie „koszt” znajdują się iloczyny nakładu projektu ze stała 1 (projekt

zaakceptowany) lub 0 (projekt odrzucony), która została wyznaczona przez SOLVER.

Wyrażenie „suma” określa sumę wszystkich kosztów wybranych projektów nie

mogących przekroczyć dostępnych funduszy, obok jest suma zysków odniesioną z

wybranych projektów, którą maksymalizujemy w SOLVERZE.

„=C2*E2”

„=B2*E2”

„=SUMA(G2:G13)”

„ „=SUMA(H2:H13)”

3. Wnioski

W obu przypadkach były rozpatrywane potrzeby wykorzystania maksymalnych
funduszy przeznaczonych na inwestycje w projekty. W przykładzie pierwszym
wybierali

ś

my sum

ę

jako komórk

ę

celu,

ż

eby móc rozdysponowa

ć

jak najwi

ę

cej

dost

ę

pnych funduszy. W przykładzie drugim istniała dodatkowa kolumna mówi

ą

ca nam o

spodziewanych zyskach z konkretnych projektów, wi

ę

c z przykładzie tym to sum

ę

spodziewanych zysków wybrali

ś

my za komórk

ę

celu aby były one jak najwi

ę

ksze.