GNU Linear Programming Kit, GLPK
[ Pobierz całość w formacie PDF ]
Narzędzia programistyczne
GNU Linear Programming Kit
Narzędzie do rozwiązywania
zagadnień programowania liniowego
Zagadnienie programowania liniowego oraz metoda simplex umożliwiająca
jego rozwiązanie były tajnym orężem podczas drugiej wojny światowej.
Pozwalały na maksymalizację zysków lub minimalizację strat przy zadanych
ograniczeniach. W poniższym artykule wprowadzamy czytelnika w arkana
programowania liniowego oraz narzędzie GLPK.
Dowiesz się:
• Czym jest zagadnienie programowania linio-
wego.
• Jakie problemy można dzięki niemu rozwiązać.
• W jaki sposób sformułować problemy w na-
rzędziu GLPK.
• Jak interpretować otrzymane rezultaty.
• Gdzie znaleźć dodatkowe informacje.
Powinieneś wiedzieć:
• Co to jest funkcja liniowa.
• Co to jest układ równości lub nierówności.
• Przy pomocy ciężarówek można prze-
wieźć maksymalnie 1500 ton kruszywa
miesięcznie.
• Zakładamy, że nie można wozić betonu
ciężarówkami, ani kruszywa betoniarka-
mi.
• Przewiezienie tony betonu kosztuje 17
PLN, a tony kruszywa 4 PLN; całkowity
budżet na ten cel wynosi 25000 PLN.
• Czas potrzebny na przewiezienie tony be-
tonu wynosi 8 godzin, a tony kruszywa
6 godzin; całkowity czas dostępny przez
pracodawcę wynosi 15000 godzin.
• Firma zarabia 22 PLN na przewiezieniu
tony betonu, a 20 PLN na przewiezieniu
tony kruszywa.
• Należy uzyskać jak największy zysk na
przewożeniu betonu oraz kruszywa.
Poziom trudności
nych wyrobów. Spektrum zastosowań ograni-
czone jest jedynie wyobraźnią. Zanim zosta-
nie formalnie zdefiniowanie zagadnienie pro-
gramowania liniowego, spróbujmy prześledzić
prosty problem.
P
rogramowanie liniowe jest dziedziną ba-
Pierwszy przykład
Firma transportowa ma do dyspozycji beto-
niarki do przewozu betonu oraz ciężarówki
do transportu kruszywa. Za pomocą betonia-
rek może przewieźć 1400 ton betonu miesięcz-
nie, a za pomocą ciężarówek 1500 ton. Aby zre-
alizować kontrakt, musi najpierw sama wyło-
żyć środki. Przewiezienie z bazy na budowę to-
ny betonu kosztuje firmę 17 PLN, a tony kru-
szywa 4 PLN. Firma może maksymalnie wyło-
żyć 25000 PLN na ten cel. Dodatkowo uśred-
niony czas przewiezienia tony betonu wynosi 8
godzin, a tony kruszywa 6 godzin. Pracodawca
dysponuje miesięcznie 15000 godzinami, jakie
może przeznaczyć na przewóz. Firma zarabia
22 PLN na przewiezieniu tony betonu oraz 20
PLN na przewiezieniu tony kruszywa. Oblicz,
w jaki sposób zrealizować kontrakt (to jest, ile
przewieźć betonu i kruszywa na budowę), aby
osiągnąć największy zysk.
Aby rozwiązać ten problem, prześledźmy
najważniejsze informacje:
dań operacyjnych, które skupiają się na
opracowywaniu metod pozwalających
na podjęcie optymalnej decyzji. Zagadnienie
programowania liniowego [1][2] umożliwia
sformułowanie i rozwiązanie problemów, któ-
rych celem jest maksymalizacja (lub minima-
lizacja) pewnej funkcji przy zadanych ograni-
czeniach.
Dzięki pakietowi GLPK [3] możliwe jest
rozwiązanie problemów programowania li-
niowego oraz całkowitoliczbowego. W jego
skład wchodzą biblioteka w języku C oraz
so-
lver
, który z niej korzysta. Poprzez język pro-
gramowania GNU MathProg
solver
pozwa-
la na formułowanie problemów oraz ich roz-
wiązanie za pomocą wspomnianej biblioteki
programowej. Możliwe jest również korzysta-
nie z samej biblioteki w programach pisanych
w języku C.
Na potrzeby niniejszego artykułu zosta-
ły wybrane przykłady, w których powracają-
cym motywem jest firma transportowa. Oczy-
wiście metoda ta może być użyta do rozwią-
zywania innych zagadnień. Przykładami mo-
gą być problemy z opracowywaniem optymal-
nych diet, grafików pracy czy składów chemicz-
Po syntezie informacji dochodzimy do wnio-
sku, iż zysk firmy zależy od dwóch zmien-
nych:
b –
ilości przewiezionych ton betonu
oraz
k
– ilości przewiezionych ton kruszywa.
Co więcej, zysk ten można wyrazić przy po-
Listing 1.
Model problemu z transportem
betonu i kruszywa
# Transport betonu i kruszywa
/* Zmienne */
var
b
>=
0
;
/* beton */
var
k
>=
0
;
/* kruszywo */
/* Funkcja celu */
maximize
zysk
:
22
*
b
+
20
*
k
;
/* Ograniczenia */
s
.
t
.
c1
:
17
*
b
+
4
*
k
<=
25000
;
s
.
t
.
c2
:
8
*
b
+
6
*
k
<=
15000
;
s
.
t
.
c3
:
b
<=
1400
;
s
.
t
.
c4
:
k
<=
1500
;
end
;
• Firma przewozi beton oraz kruszywo.
• Przy pomocy betoniarek można prze-
wieźć maksymalnie 1400 ton betonu
miesięcznie.
52
1/2009
GNU Linear Programming Kit
mocy prostego równania z =
22 * b + 20 * k
.
Jak łatwo zauważyć, równanie to jest liniowe.
Zmienne te będą zmieniały wartość w trakcie
poszukiwania optymalnego rozwiązania przez
algorytm simplex.
Na pierwszy rzut oka można odnieść wra-
żenie, iż zysk dałoby się zwiększać w nieskoń-
czoność poprzez zwiększanie zmiennych
b
oraz
k
. Niestety nie jest to możliwe, gdyż ist-
nieją dodatkowe ograniczenia. Pierwsze z nich
dotyczy konieczności przeznaczenia pewnych
środków na realizację zadania. Środki te ro-
sną wraz z ilością przewiezionych materiałów.
Ograniczenie możemy wyrazić przy pomocy
nierówności
17 * b + 4 * k <= 25000.
Drugim
ograniczeniem jest liczba godzin, jakie mogą
być przeznaczone na zrealizowanie zlecenia.
Ich liczba również zależy od liczby przewie-
zionych materiałów. Bez trudu możemy dojść
do nierówności
8 * b + 6 * k <= 15000
. Ostat-
nimi ograniczeniami będą te najprostsze, któ-
re zostały już explicite zaznaczone w najważ-
niejszych informacjach. Ilość przewiezione-
go betonu nie może być większa niż 1400
ton, a ilość przewiezionego kruszywa więk-
sza od 1500 ton. Daje to dwie nierówności:
b <= 1400
oraz
k <= 1500
. Ostatnie nierów-
ności nie zostały opisane wcześniej, ale wy-
nikają implicite z rozważanego zagadnienia.
Ilość przewiezionych materiałów nie może
być ujemna. Stąd otrzymujemy nierówności:
b >= 0
oraz
k >= 0
.
Podsumowując, otrzymaliśmy następujące
równania oraz nierówności:
Aby rozwiązać tak stworzony model, posłu-
gujemy się narzędziem
glpsol
.
macje o czasie i pamięci użytej do znalezienia
rozwiązania.
Najistotniejszymi informacjami są te, iż po-
wiodło się wygenerowanie modelu oraz uzyska-
nie optymalnego rozwiązania. Oznacza to, że
znaleziono takie wartości zmiennych, dla któ-
rych funkcja celu przyjmuje wartość najwięk-
szą. W szczególnym przypadku takich miejsc
może być nieskończenie wiele. Możliwe są
jeszcze dwa przypadki rozwiązania problemu
programowania liniowego. Pierwszym z nich
jest nieskończona wartość funkcji celu. Drugi
przypadek to brak rozwiązania ze względu na
sprzeczność ograniczeń.
Przeanalizujmy zawartość wygenerowane-
go pliku z rozwiązaniem problemu (Listing
3.). Składa się on z czterech części. Pierw-
glpsol -m betonkruszywo.mod -o
betonkruszywo.sol
Jego wywołanie składa się z dwóch parame-
trów. Pierwszy z nich określa nazwę pliku, z
którego ma być wczytany model. Drugi z nich
wskazuje na plik, do którego ma być zapisane
rozwiązanie.
Po uruchomieniu
solvera
zostaną wypisane
informacje o przebiegu jego działania. Na Li-
stingu 2. widzimy, że został poprawnie utwo-
rzony model, uruchomiona metoda simplex,
oraz że udało się znaleźć rozwiązanie opty-
malne. Na końcu raportu podawane są infor-
• Funkcja celu, która podlega maksymaliza-
cji:
z = 22 * b + 20 * k.
• 1-wsze ograniczenie:
17 * b + 4 * k <= 25000.
• 2-gie:
8 * b + 6 * k <= 15000.
• 3-cie ograniczenie:
b <= 1400.
• 4-te ograniczenie:
k <= 1500.
• 5-te ograniczenie na zmienne:
b >= 0
,
k >= 0.
Rysunek 1.
Graiczna interpretacja problemu dwuwymiarowego
W celu rozwiązania opisanego problemu po-
służmy się pakietem GLPK. W pierwszym
kroku zdefiniujemy model systemu. Został on
przedstawiony na Listingu 1.
Komentarze zaczynają się od znaku
#
lub
są zawarte pomiędzy
/* */
. W następnych li-
niach następuje deklaracja zmiennych
b
oraz
k
wraz z ograniczeniem ich co do znaku. Na-
zwy zmiennych mogą składać się z więcej niż
jednej litery. Funkcję celu, którą mamy maksy-
malizować, przedstawiono w linii rozpoczyna-
jącej się od słowa kluczowego
maximize
. Moż-
liwa jest również minimalizacja funkcji celu.
W takim przypadku funkcję poprzedza się sło-
wem kluczowym
minimize
. Ostanie linie defi-
niują ograniczenia, jakie muszą być zastosowa-
ne przy naszym problemie. Deklarację ograni-
czenia możemy rozpocząć od jednego ze słów
kluczowych
subject to
,
subj to
,
s.t.
, lub po-
minąć w ogóle.
Listing 2.
Informacja o działaniu solvera
Reading
model
section
from
betonkruszywo
.
mod
...
19
lines
were
read
Generating
zysk
...
Generating
c1
...
Generating
c2
...
Generating
c3
...
Generating
c4
...
Model
has
been
successfully
generated
lpx_simplex
:
original
LP
has
5
rows
,
2
columns
,
8
non
-
zeros
lpx_simplex
:
presolved
LP
has
2
rows
,
2
columns
,
4
non
-
zeros
lpx_adv_basis
:
size
of
triangular
part
=
2
*
0
:
objval
=
0.000000000e+00
infeas
=
0.000000000e+00
(
0
)
*
2
:
objval
=
4.650000000e+04
infeas
=
0.000000000e+00
(
0
)
OPTIMAL
SOLUTION
FOUND
Time
used
:
0.0
secs
Memory
used
:
0.
1
M
(
151406
bytes
)
lpx_print_sol
:
writing
LP
problem
solution
to
`
betonkruszywo
.
sol
'...
www.sdjournal.org
53
Narzędzia programistyczne
sza z nich przedstawia informację o proble-
mie oraz o optymalnym rozwiązaniu. Druga
część prezentuje funkcję celu oraz ogranicze-
nia. Kolejna dotyczy optymalnych wartości
zmiennych decyzyjnych. Wreszcie ostatnia
część umożliwia prześledzenie błędów nu-
merycznych, jakie mogły pojawić się w trak-
cie rozwiązania.
Najprostszą interpretacją jest stwierdzenie,
iż funkcja celu przyjmuje największą wartość
46500 dla wartości zmiennych
b = 750
oraz
k =
1500
. Dla naszego przykładu oznacza to, że fir-
ma transportowa osiągnie największy zysk, gdy
przetransportuje 750 ton betonu oraz 1500
ton kruszywa. W ten sposób osiągnie zysk o
wartości 46500 PLN.
Co jeszcze można wyczytać z przedstawio-
nego listingu? W kolumnie
St
pojawiają się
dwa oznaczenia
B
oraz
NU
. Za każdym razem,
gdy ograniczenie sięga swojej dolnej lub górnej
granicy, jest ono odpowiednio zwane dolnym
lub górnym. Ograniczenie takie uniemożliwia
osiągnięcie przez funkcję celu lepszej wartości.
Przez s
olver
oznaczane jest ono jako
NL
(dla dol-
nego ograniczenia) oraz
NU
(dla górnego). W ko-
lumnie
Marginal
pojawia się dodatkowa liczba
oznaczająca, o ile zmieni się funkcja celu, gdy
dane ograniczenie zostanie poluzowane o jed-
ną jednostkę. W naszym przykładzie dla ogra-
niczenia
c2
dotyczącego ilości godzin przezna-
czonych na wykonanie zadania, funkcja celu
zwiększy się o 2.75, a dla ograniczenia
c4
doty-
czącego limitu na ilość przewożonego kruszy-
wa o 3.5 PLN. Proszę sprawdzić, czy rzeczywi-
ście funkcja celu wzrośnie o odpowiednią war-
tość. Dla ograniczeń oznaczonych przez
B
nie
zostały osiągnięte limity. Zmiana dla takich
przypadków nie będzie miała wpływu na war-
tość funkcji celu.
formie graficznej może ono zostać wyobra-
żone jako poszukiwanie maksymalnej warto-
ści funkcji wewnątrz dopuszczalnego obsza-
ru. Obszar ten jest definiowany poprzez zada-
ne ograniczenia. Na Rysunku 1. przedstawia-
my obszar zdefiniowany przez kryteria zawar-
te w przykładzie z betoniarkami oraz ciężarów-
kami. Co ciekawe, najlepsze rozwiązanie le-
ży na obwiedni dopuszczalnego obszaru. Stąd
też nazwa metody simplex, gdzie simplex sta-
nowi granicę takiego obszaru. Dzięki poszuki-
waniu optymalnego rozwiązania na obwiedni
obszaru, udało się opracować algorytmy, które
działają w czasie liniowym w zależności od roz-
miaru problemu. Jest to jedno z największych
osiągnięć w badaniach nad rozwiązywaniem
zagadnienia programowania liniowego. Proszę
wskazać miejsce, dla którego funkcja celu osią-
ga wartość największą. Jest ono jednym z prze-
cięć funkcji ograniczających dopuszczalny ob-
szar (Rysunek 1).
Teoria w pigułce
Mam nadzieję, że zainteresowałem Cię drogi
Czytelniku zagadnieniem programowania li-
niowego. Wprowadźmy teraz trochę formali-
zmów oraz przedstawmy graficznie, na czym
polega rozwiązanie problemu programowa-
nia liniowego dla przypadku dwuwymiaro-
wego. W formie macierzowej ma ono postać:
�����
�
�
���������
Zadanie polega na maksymalizacji funkcji li-
niowej przy narzuconych ograniczeniach. W
Przykład z modelem oraz danymi
Kolejny przykład ma pokazać, w jaki sposób
zdefiniować model dla danego problemu oraz
wprowadzić dla niego konkretne dane. Model
jest ogólnym przedstawieniem rozważanego za-
dania. Dzięki niemu możliwe jest podstawianie
konkretnych danych i analizowanie dla nich ko-
lejnych rozwiązań, na przykład w celu rozstrzy-
gnięcia pomiędzy kilkoma alternatywami.
So-
lver
umożliwia wprowadzenie modelu oraz da-
nych z kilku plików. Dla uproszczenia w zapre-
zentowanym przykładzie model oraz dane bę-
dą w jednym pliku.
Model zawiera kilka parametrów, ze wzglę-
du na które będzie rozważany. Parametry te
są definiowane przy pomocy słowa kluczowe-
go
param
. Konieczne jest również zdefinio-
wanie zmiennych, które będą zmieniały się
w trakcie działania algorytmu. Zmienne te
definiuje się przy pomocy słowa kluczowego
var
. To one wyznaczą optymalne rozwiąza-
nie. Parametry będą mogły być zmieniane po-
przez różne dane. W ten sposób otrzymamy
kilka różnych zadań do rozwiązania. Zmien-
ne z kolei stanowią rozwiązanie dla konkret-
nego problemu.
Zanim przedstawimy zadanie, musimy jesz-
cze trochę skomplikować opis, aby w rezultacie
ułatwić zapis modelu. Niejednokrotnie w trak-
cie definicji modelu będziemy musieli wyliczać
kilka parametrów oraz zmiennych, które będą
indeksowane przy pomocy pewnego zbioru ele-
mentów. Na przykład zmienne
k_1
,
k_2
, ...,
k_n
.
Zamiast jednak stosować taki zapis, można
Listing 3.
Rozwiązanie problemu z transportem betonu i kruszywa
Problem
:
betonkruszywo
Rows
:
5
Columns
:
2
Non
-
zeros
:
8
Status
:
OPTIMAL
Objective
:
zysk
=
46500
(
MAXimum
)
No
.
Row
name
St
Activity
Lower
bound
Upper
bound
Marginal
------
------------
--
-------------
-------------
-------------
-------------
1
zysk
B
46500
2
c1
B
18750
25000
3
c2
NU
15000
15000
2.75
4
c3
B
750
1400
5
c4
NU
1500
1500
3.5
No
.
Column
name
St
Activity
Lower
bound
Upper
bound
Marginal
------
------------
--
-------------
-------------
-------------
-------------
1
b
B
750
0
2
k
B
1500
0
Karush
-
Kuhn
-
Tucker
optimality
conditions
:
KKT
.
PE
:
max
.
abs
.
err
.
=
0.00e+00
on
row
0
max
.
rel
.
err
.
=
0.00e+00
on
row
0
High
quality
KKT
.
PB
:
max
.
abs
.
err
.
=
0.00e+00
on
row
0
max
.
rel
.
err
.
=
0.00e+00
on
row
0
High
quality
KKT
.
DE
:
max
.
abs
.
err
.
=
1.78e-15
on
column
2
max
.
rel
.
err
.
=
8.46e-17
on
column
2
High
quality
KKT
.
DB
:
max
.
abs
.
err
.
=
0.00e+00
on
row
0
max
.
rel
.
err
.
=
0.00e+00
on
row
0
High
quality
End
of
output
Tabela 1.
Koszt przejazdu pomiędzy fabrykami a
magazynami
X Y Z
A
30 25 15
B
15 20 10
C
20 35 15
54
1/2009
GNU Linear Programming Kit
zdefiniować je jako
k_i
, gdzie
i
należy do zbioru
Z =
{1, 2,..., n}
.
Solver
oferuje taką możliwość
poprzez definiowanie zbioru indeksów. Na ta-
kim zbiorze możemy również wykonywać ope-
racje. Zamiast pisać
k_1 + k_2 +...+ k_n
, wystar-
czy napisać
sum{i in Z} k_i
.
Jeśli jest to jeszcze niezrozumiałe, mam nadzie-
ję, że przykład doskonale wyjaśni, o co chodzi.
Firma spedycyjna ma do przewiezienia 2000
paczek przy pomocy małych i dużych aut. Każ-
de małe auto może pomieścić 60 paczek, w du-
żym aucie mieści się ich 150. Koszt przejazdu
małego auta wynosi 15 PLN, a koszt przejazdu
dużego auta to 25 PLN. Dodatkowo, cały prze-
wóz ma zmieścić się w kwocie 400 PLN, a licz-
ba dużych aut nie może przekraczać liczby ma-
łych aut użytych do transportu. Ile dużych i
małych samochodów należy użyć do wykona-
nia zadania, aby spełnić powyższe ograniczenia
i zminimalizować koszt?.
Listing 4. przedstawia zdefiniowany model
oraz konkretne dane dla zadania z małymi i du-
żymi autami. Zawiera on kilka elementów, któ-
re postaram się przybliżyć. Definicja modelu
znajduje się na początku pliku (do słowa klu-
czowego
data
). W dalszej części zaczyna się de-
finicja konkretnych danych. Zajmijmy się jed-
nak najpierw modelem.
Z treści zadania wynika, iż firma posiada ma-
łe i duże samochody. Pojawiają się również in-
formacje o ich pojemności oraz koszcie trans-
portu. Możemy więc przypuszczać, iż w mo-
delu będą występowały parametry dla takich
aut. Zamiast pisać
koszt_Małe
,
koszt_Duze
,
pojemność_Małe
,
pojemność_Duze
, zadeklaruj-
my zbiór rodzajów aut, ze względu na które te
parametry będą określane. Co więcej, rozwiąza-
nie będzie polegało na określeniu liczby obu ro-
dzajów aut w taki sposób, aby koszt był jak naj-
mniejszy. Będziemy więc potrzebowali dwóch
zmiennych:
auta_Małe
oraz
auta_Duze
. I tu-
taj przyda nam się wspomniany zbiór rodza-
jów aut.
Zadeklarujmy więc ów zbiór, którego ele-
menty będą służyły jako indeksy dla parame-
trów oraz zmiennych modelu. Jego deklaracja
to
set Auta;
. Wyszczególnienie, iż mamy do
czynienia z małymi i dużymi autami znajdzie
się w sekcji z danymi modelu. Kolejne linie de-
klarują wspomniane parametry i zmienne. Dla
przykładu,
param koszt{a in Auta};
, ozna-
cza deklarację parametrów
koszt
z indeksami
w zbiorze
Auta
. Dla konkretnych danych
Auta
:= Male, Duze;
, możemy sobie wyobrażać, że
będą to parametry
koszt_Male
,
koszt_Duze
.
Przejdźmy teraz do omówienia funkcji celu
oraz ograniczeń. W ich deklaracji również za-
stosowano wyliczenia odnoszące się do zbio-
ru indeksów. Aby łatwiej zrozumieć zapis
funkcji celu
z : sum{a in Auta} auta[a] *
koszt[a]
, rozwińmy ją do naszego przypadku z
małymi i dużymi autami. Będzie ona miała po-
stać
auta_Male * koszt_Male + auta_Duze *
koszt_Duze
. Widzimy więc, że jest ona wyrażo-
na za pomocą bardziej zwartego zapisu. Stano-
wi też cel, jaki chcemy osiągnąć – zminimalizo-
wać koszt związany z użyciem szukanej liczby
dużych i małych samochodów.
Teraz wyjaśnienie sformułowania ograni-
czeń nie powinno być już problemem. Ogra-
niczenie
c1
i
c2
są matematycznym przedsta-
wieniem informacji z tekstu zadania. Z kolei
ograniczenie
c3
dotyczy obostrzeń dotyczących
liczby dużych i małych aut. Tak naprawdę dla
naszego przykładu będą to cztery ogranicze-
nia! Dzięki wyliczeniom elementów zbioru po-
wstaną ograniczenia o nazwach
c3_Male_Male
,
c3_Male_Duze
,
c3_Duze_Male
i
c3_Duze_Duze
.
Listing 4.
Model problemu z małymi i dużymi autami
set
Auta
;
param
koszt
{
a
in
Auta
}
;
param
pojemnosc
{
a
in
Auta
}
;
/* Zmienna pomocnicza do ostatniego ograniczenia */
param
transport
{
m
in
Auta
,
d
in
Auta
}
;
/* Zmienna decyzyjna, liczba aut */
var
auta
{
a
in
Auta
}
>=
0
,
integer
;
/* Funkcja celu */
minimize
z
:
sum
{
a
in
Auta
}
auta
[
a
]
*
koszt
[
a
];
/* Ograniczenia */
s
.
t
.
c1
:
sum
{
a
in
Auta
}
auta
[
a
]
*
koszt
[
a
]
<=
400
;
s
.
t
.
c2
:
sum
{
a
in
Auta
}
auta
[
a
]
*
pojemnosc
[
a
]
>=
2000
;
s
.
t
.
c3
{
m
in
Auta
,
d
in
Auta
}
:
auta
[
d
]
*
transport
[
m
,
d
]
<=
auta
[
m
]
*
transport
[
m
,
d
];
data
;
set
Auta
:=
Male
,
Duze
;
param
koszt
:=
Male
15
Duze
25
;
param
pojemnosc
:=
Male
60
Duze
150
;
param
transport
:
Male
Duze
:=
Male
0
1
Duze
0
0
;
end
;
Listing 5.
Rozwiązanie problemu z małymi i dużymi autami
Problem
:
duzemaleauta
Rows
:
7
Columns
:
2
(
2
integer
,
0
binary
)
Non
-
zeros
:
8
Status
:
INTEGER
OPTIMAL
Objective
:
z
=
390
(
MINimum
)
380.952381
(
LP
)
No
.
Row
name
Activity
Lower
bound
Upper
bound
------
------------
-------------
-------------
-------------
1
z
390
2
c1
390
400
3
c2
2010
2000
4
c3
[
Male
,
Male
]
0
-
0
5
c3
[
Male
,
Duze
]
-
2
-
0
6
c3
[
Duze
,
Male
]
0
-
0
7
c3
[
Duze
,
Duze
]
0
-
0
No
.
Column
name
Activity
Lower
bound
Upper
bound
------
------------
-------------
-------------
-------------
1
auta
[
Male
]
*
11
0
2
auta
[
Duze
]
*
9
0
End
of
output
www.sdjournal.org
55
Narzędzia programistyczne
Dla konkretnych danych będziemy mogli zde-
finiować, że ma ono być uwzględniane tylko w
przypadku małych i dużych aut. Zrozumienie
tego ograniczenia może zająć trochę więcej cza-
su, ale nie stanowi istoty omawianego tutaj za-
dania. Ma raczej pokazać, iż wyliczenie elemen-
tów zbioru, może być użyte do deklaracji kilku
ograniczeń.
Omówienie fragmentu z danymi nie jest już
takie skomplikowane. Pierwsza linia w tej sek-
cji deklaruje zbiór typów aut. Będziemy mieć
do czynienia z małymi i dużymi pojazdami.
Następnie zadeklarowane są wartości parame-
trów. Parametry
koszt
oraz
pojemność
są jed-
nowymiarowe. Na przykład koszt dla małego
auta wynosi 15, a pojemność dla dużego 150.
Parametr
transport
jest macierzą dwuwymia-
rową. Jej deklaracja jest podobna do deklara-
cji zwykłej macierzy: w poziomie zapisane są
wiersze, a w pionie jej kolumny. Na przykład
wartość
transport[Male, Duze]
wynosi 1.
Uff, dobrnęliśmy do końca omawiania tego
dość skomplikowanego przykładu. Zostały po-
kazane tutaj najważniejsze konstrukcje języka
GNU MathProg. Wydaje mi się, iż powinieneś
sobie, drogi Czytelniku, poradzić samodzielnie
z innymi przykładami. Gratuluję cierpliwości i
dociekliwości.
Po uruchomieniu możemy zobaczyć intere-
sujący nas wynik. Jednak tutaj czeka nas niespo-
dzianka. Uważni czytelnicy z pewnością zauwa-
żą, iż w linii deklarującej zmienne decyzyjne poja-
wiło się słowo kluczowe
integer
. Oznacza ono, iż
poszukiwane rozwiązanie musi zostać ograniczo-
ne do wartości całkowitych. Niemożliwe jest prze-
cież użycie do transportu tylko kawałka auta. Szu-
kaną odpowiedzią jest 11 i 9. Oznacza to, iż naj-
lepszy efekt osiągniemy, gdy do przewozu użyje-
my 11 małych i 9 dużych aut. Dzięki tej prostej
modyfikacji do wyznaczenia rozwiązania został
użyty algorytm całkowitoliczbowy.
Model zawierał explicite podane wartości
dotyczące ilości paczek do przewiezienia oraz
całkowitego kosztu, jaki może być poniesiony
w związku z tym kontraktem. Ustalenie tych
wartości jako parametrów zadania, nie powin-
no stanowić żadnego kłopotu.
Listing 6.
Model problemu transportowego
set
Fabryki
;
set
Magazyny
;
param
produkcja
{
f
in
Fabryki
}
;
param
zapotrzebowanie
{
m
in
Magazyny
}
;
param
koszt
{
f
in
Fabryki
,
m
in
Magazyny
}
;
var
wysylka
{
f
in
Fabryki
,
m
in
Magazyny
}
>=
0
,
integer
;
minimize
budzet
:
sum
{
f
in
Fabryki
,
m
in
Magazyny
}
wysylka
[
f
,
m
]
*
koszt
[
f
,
m
];
s
.
t
.
podaz
{
f
in
Fabryki
}
:
sum
{
m
in
Magazyny
}
wysylka
[
f
,
m
]
<=
produkcja
[
f
];
s
.
t
.
popyt
{
m
in
Magazyny
}
:
sum
{
f
in
Fabryki
}
wysylka
[
f
,
m
]
=
zapotrzebowanie
[
m
];
data
;
set
Fabryki
:=
A
B
C
;
set
Magazyny
:=
X
Y
Z
;
param
produkcja
:=
A
9
B
5
C
2
;
param
zapotrzebowanie
:=
X
6
Y
3
Z
3
;
param
koszt
:
X
Y
Z
:=
A
30
25
15
B
15
20
10
C
20
35
15
;
end
;
Listing 7.
Rozwiązanie problemu transportowego
Problem
:
transport
Rows
:
7
Columns
:
9
(
9
integer
,
0
binary
)
Non
-
zeros
:
27
Status
:
INTEGER
OPTIMAL
Objective
:
budzet
=
215
(
MINimum
)
215
(
LP
)
No
.
Row
name
Activity
Lower
bound
Upper
bound
------
------------
-------------
-------------
-------------
1
budzet
215
2
podaz
[
A
]
5
9
3
podaz
[
B
]
5
5
4
podaz
[
C
]
2
2
5
popyt
[
X
]
6
6
=
6
popyt
[
Y
]
3
3
=
7
popyt
[
Z
]
3
3
=
Zagadnienie transportowe
Zaprezentowany w tej sekcji przykład korzy-
sta z konstrukcji poznanych w poprzednim za-
daniu. Podobnie do poprzedniego, jest ono cał-
kowitoliczbowe. Oto nasz problem do rozwią-
zania.
W fabrykach A, B, C znajduje się odpowied-
nio 9, 5 i 2 maszyny, które mają zostać prze-
transportowane do magazynów X, Y, Z. W każ-
dym z magazynów mają znaleźć się odpowied-
nio 6, 3 i 3 maszyny. Koszt transportu pomię-
dzy miejscami podano w Tabeli 1. Należy za-
planować transport maszyn w taki sposób, aby
zminimalizować jego całkowity koszt (budżet
przedsięwzięcia).
Z treści zadania wynika, iż należy uwzględ-
nić kilka parametrów ze względu na fabryki oraz
magazyny. Parametry te będą dotyczyły ilości
maszyn dostępnych w fabryce, zapotrzebowa-
nia w danym magazynie oraz kosztu transpor-
No
.
Column
name
Activity
Lower
bound
Upper
bound
------
------------
-------------
-------------
-------------
1
wysylka
[
A
,
X
]
*
0
0
2
wysylka
[
A
,
Y
]
*
3
0
3
wysylka
[
A
,
Z
]
*
2
0
4
wysylka
[
B
,
X
]
*
4
0
5
wysylka
[
B
,
Y
]
*
0
0
6
wysylka
[
B
,
Z
]
*
1
0
7
wysylka
[
C
,
X
]
*
2
0
8
wysylka
[
C
,
Y
]
*
0
0
9
wysylka
[
C
,
Z
]
*
0
0
56
1/2009
[ Pobierz całość w formacie PDF ]