Zagadnienie pośrednika

Pośrednik nabywa towar od m dostawców, przewozi go i sprzedaje n odbiorcom.

Dane:

a_i – maksymalna ilość towaru jaką dysponuje i-ty dostawca.

b_j – maksymalna ilość towaru jaką można sprzedać j-temu odbiorcy

k_i­ – jednostkowa cena zakupu i i-tego dostawcy

p_j – jednostkowa cena sprzedaży j-temu odbiorcy

c_ij – koszty jednostkowe transportu na trasie (i,j)

Zmienne decyzyjne:

x_ij – wielkość transportu na trasie (i,j)

d_ij – dochód (przychód) pośrednika (jednostkowy) na trasie (i,j)

Oczywiście d_ij = p_j –k_i-c_ij (zakładamy, że dochód pośrednika jest równy jego przychodowi)

Funkcja celu:

$$\sum_{i = 1}^{m}{\sum_{j = 1}^{n}{d_{\text{ij}}x_{\text{ij}} \rightarrow max}}$$

Ograniczenia:

$$\sum_{j = 1}^{n}{x_{\text{ij}} \leq a_{i}\ \ \ \ \ \ \ \ i = 1\ldots m}$$

$$\sum_{i = 1}^{m}{x_{\text{ij}} \leq b_{j}\ \ \ \ \ \ \ \ j = 1\ldots n}$$

x_ij ≥ 0,   x_ij∈ℤ

∖n

Pośrednik kupuje towar od 2 dostawców i sprzedaje go 3 odbiorcom. Podaż dostawcy, popyt odbiorcy, jednostkowy koszt transportu, ceny zbytu i zakupu przedstawione są w tabeli.

	Popyt	15	12	18	Cena zakupu
Podaż		Odbiorca 1	Odbiorca 2	Odbiorca 3
20	Dostawca 1	5	3	8	6
30	Dostawca 2	9	2	4	9
Cena sprzedaży	15	14	16

Ustalić plan zakupu i sprzedaży, aby dochód był maksymalny.

Rozwiązując powyższy przykład skorzystamy ze schematu sprowadzania Zadania Pośrednika (ZP) do Zbilansowanego Zadania Transportowego (ZZT).

1. Wprowadzamy

   1. Fikcyjnego dostawcę z podażą

$$a_{m + 1} = \sum_{j = 1}^{n}b_{j}$$

1. Fikcyjnego odbiorcę z popytem

$$b_{n + 1} = \sum_{i = 1}^{m}a_{i}$$

1. Zerowe dochody jednostkowe na trasach od fikcyjnego dostawcy i na trasach do fikcyjnego odbiorcy.

Wówczas ograniczenia przyjmują postać:

$$\sum_{j = 1}^{n + 1}{x_{\text{ij}} = a_{i}\ \ \ \ \ \ \ \ i = 1\ldots m + 1}$$

$$\sum_{i = 1}^{m + 1}{x_{\text{ij}} = b_{j}\ \ \ \ \ \ \ \ j = 1\ldots n + 1}$$

1. Znajdujemy dopuszczalne rozwiązanie początkowe metodą największego elementu macierzy dla D = [a_ij]

2. Analogicznie jak w ZZT obliczamy wskaźniki optymalności _ij = d_ij − u_i − v_j.

Rozwiązanie jest optymalne, gdy _ij ≤ 0 dla wszystkich tras (i,j).

1. Jeżeli rozwiązanie nie jest optymalne, to znajdujemy trasę wchodzącą do bazy – jest to ta trasa dla której _ij jest największe.

2. Dla nowej trasy bazowej wyznaczamy cykl korygujący i poprawiamy rozwiązanie w taki sam sposób jak w ZZT.

3. Wracamy do III.

Rozwiązanie przykładu na podstawie wyżej opisanego algorytmu.

	O1	O2	O3	O4
D1	4	5	2	0	20
D2	-3	3	3	0	30
D3	0	0	0	0	45 = $\sum_{}^{}\mathbf{b}_{\mathbf{j}}$
	15	12	18	50 = $\sum_{}^{}\mathbf{a}_{\mathbf{i}}$

8^+	12^-	0	0	20
0	0^+	18	12^-	30
7^-	0	0	38^+	45
15	12	18	50

	V1	V2	V3	V4
U1	4	5			0
U2			3	0	-4
U3	0			0	-4
	4	5	7	4

15	5	0	0	20
0	7	18	5	30
0	0	0	45	45
15	12	18	50

	V1	V2	V3	V4
U1	4	5			0
U2		3	3	0	-2
U3				0	-2
	4	5	5	2

Wyliczenie wartości funkcji celu przedstawia poniżej równanie:

15 × 4 + 5 × 5 + 7 × 3 + 18 × 3 = 60 + 25 + 21 + 52 = 160

Pokażemy teraz jak całościowo wygląda nasz problem zapisany w języku GAMS po czym omówimy jego wyniki wyjściowe.

$title Zagadnienie pośrednika

Sets

j odbiorcy /O1,O2,O3/

i dostawcy /D1,D2/;

Parameters

b(j) popyt odbiorców

/O1 15

O2 12

O3 18/

a(i) podaż dostawców

/D1 20

D2 30/

k(i) ceny zakupu

/D1 6

D2 9/

p(j) ceny sprzedaży

/O1 15

O2 14

O3 16/;

Table

c(i,j) koszt transportu

O1 O2 O3

D1 5 3 8

D2 9 2 4 ;

Parameter

d(i,j) dochód pośrednika na trasie (i j);

d(i,j) = p(j)-k(i)-c(i,j);

Variables

fc funkcja celu

x(i,j) wielkość transportu na trasie (i j);

Integer variable x;

Equations

dochod

podaz(i)

popyt(j);

dochod .. fc =e= sum((i,j),d(i,j)*x(i,j));

podaz(i) .. sum(j,x(i,j)) =l= a(i);

popyt(j) .. sum(i, x(i,j)) =l= b(j);

Model Zagadnienie_pośrednika /all/;

Solve Zagadnienie_pośrednika using MIP maximizing fc;

Display x.l, x.m;

Rezultatem działania program GAMS są następujące części: Echo Print, Equation Listing, Column Listing, Model Statistics, Solution Report, REPORT SUMMARY oraz rezultat instrukcji DISPLAY.

Sprawdzenie czy solver nie miał żadnych problemów z rozwiązaniem zadania (solver status), jaki typ rozwiązania został znaleziony (model status) oraz ile wynosi maksymalna wartość funkcji cel (objective value).

S O L V E S U M M A R Y

MODEL posrednik OBJECTIVE cel

TYPE MIP DIRECTION MAXIMIZE

SOLVER CPLEX FROM LINE 53

**** SOLVER STATUS 1 Normal Completion

**** MODEL STATUS 1 Optimal

**** OBJECTIVE VALUE 160.0000

Następną częścią jest odczytanie wartości z instrukcji display.

E x e c u t i o n

---- 54 VARIABLE x.L wielkość transportu na trasie (i j)

O1 O2 O3

D1 15.000 5.000

D2 7.000 18.000

---- 54 VARIABLE x.M wielkość transportu na trasie (i j)

O1 O2 O3

D1 4.000 5.000 2.000

D2 -3.000 3.000 3.000

Pierwsza tabela przedstawia ilość towaru zakupionego u i-tego dostawcy, przewiezionego i sprzedanego j-temu odbiorcy. Oczywiście ważne jest by spełnione były warunki ograniczające.

Druga tabela zawiera dochód jednostkowy, który uzyska pośrednik na trasach (i,j).