Zagadnienie pośrednika.docx

Zagadnienie pośrednika

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

Dane:

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

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

ki­ – jednostkowa cena zakupu i i-tego dostawcy

pj – jednostkowa cena sprzedaży j-temu odbiorcy

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

Zmienne decyzyjne:

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

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

Oczywiście dij = pj –ki-cij (zakładamy, że dochód pośrednika jest równy jego przychodowi)

Funkcja celu:

i=1mj=1ndijxij→max

Ograniczenia:

j=1nxij≤ai        i=1…m

i=1mxij≤bj        j=1…n

xij≥0,  xij∈Z

Przykład

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.

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).

I.        Wprowadzamy

i)       Fikcyjnego dostawcę z podażą

am+1=j=1nbj

ii)     Fikcyjnego odbiorcę z popytem

bn+1=i=1mai

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

Wówczas ograniczenia przyjmują postać:

j=1n+1xij=ai        i=1…m+1

i=1m+1xij=bj        j=1…n+1

II.     Znajdujemy dopuszczalne rozwiązanie początkowe metodą największego elementu macierzy dla D=aij

III.  Analogicznie jak w ZZT obliczamy wskaźniki optymalności ∆ij=dij-ui-vj.

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

IV.  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.

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

VI.  Wracamy do III.

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

...