Badania operacyjne - wykład 3

[ Pobierz całość w formacie PDF ]
//-->2013-12-07Badaniaoperacyjnew logistyceWykład 3:Zagadnienia transportoweizabela.dziaduch@pwr.wroc.plEkonomiczne sformułowanie problemutransportowegoIstnieje pewna liczba punktów nadania i punktów odbiorujednorodnego towaru.Należy tak powiązać ze sobą miejsca dostaw z miejscami odbioru,aby łączne koszty (czas) transportu były jak najmniejsze(y).Wymagana jest znajomość następujących wielkości:Limity dostaw dostawców,Zapotrzebowanie odbiorców,Jednostkowe(y)relacjach.koszty(czas)transportuwewszystkichID,2013/201412013-12-07Matematyczne sformułowanie zagadnieniatransportowego (1)∑a≥∑bi=1ij=1mnjF(x)=∑ ∑cijxij→mini=1j=1mnOznaczenia:xij— wielkość przewozu towaru odi-tego dostawcy doj-tegoodbiorcy,cij— jednostkowy koszt przewozutowaru odi-tegodostawcy doj-tegoodbiorcy,ai— limit dostawi-tegodostawcy,bj— zapotrzebowaniej-tegoodbiorcy,m— liczba dostawców,n— liczba odbiorców.ID,2013/2014∑xj=1nij≤ai,i=1,2,K,mj=1,2,K,n∑xi=1mij=(≤)bj,xij≥Matematyczne sformułowanie zagadnieniatransportowego (2)Tablica transportowaji12…mbj1x11x21…xm1b12x12x22…xm2b2………………nx1nx2n…xmnbnaia1a2…amWymiary tablicy transportowejm×n.ID,2013/201422013-12-07Matematyczne sformułowanie zagadnieniatransportowego (3)Macierz (bezpośrednia)jednostkowych kosztówtransportu (cij)c11c12cc2221cij=MMcm1cm2Lc1nLc2nO MLcmnID,2013/2014Rodzaje zadań transportowych (1)1.Zamknięte zagadnienie transportowe (ZZT)∑a=∑bi=1ij=1mnj(podaż = popyt)Każda podaż zostanie rozdysponowana, każdy popyt zostanie zaspokojony -zagadnienie zbilansowane;Model matematyczny:zmienne decyzyjne:xij– ilość towaru przewożona odi-tegodostawcy doj-tegoodbiorcywarunki ograniczające dla dostawcówn∑xij=ai(i=1,2,...,m)j=1warunki ograniczające dla odbiorcówm∑xij=bj(j=1,2,...,n)i=1warunki brzegowefunkcja celu∑∑ci=1j=1mxij≥nijxij→MINID,2013/201432013-12-07Rodzaje zadań transportowych (2)2.Otwarte zagadnienie transportowe (OZT)2.1.ma>nb∑i=1i∑j=1j(podaż > popyt)Nie każda podaż zostanie rozdysponowana - zagadnienie niezbilansowane;Model matematyczny:zmienne decyzyjne:xij– ilość towaru przewożona odi-tegodostawcy doj-tegoodbiorcywarunki ograniczające dla dostawców∑∑mnj=1xij≤aiwarunki ograniczające dla odbiorcówwarunki brzegowexij≥funkcja celum ni=1xij=bj∑∑ci=1j=1ijxij→MINID,2013/2014Rodzaje zadań transportowych (3)2.Otwarte zagadnienie transportowe (OZT)mn2.2.a<b(podaż < popyt)∑i=1i∑j=1jNie każdy popyt zostanie zaspokojony - zagadnienie niezbilansowane;Model matematyczny:zmienne decyzyjne:xij– ilość towaru przewożona odi-tegodostawcy doj-tegoodbiorcywarunki ograniczające dla dostawców∑xj=1mnij=ai≤bjwarunki ograniczające dla odbiorców∑xi=1ijwarunki brzegowexij≥funkcja celu∑∑cijxij→MINi=1j=1mnID,2013/201442013-12-07Rozwiązywanie zadań transportowych– algorytm transportowyAlgorytm transportowyto zmodyfikowana metoda simplekssłużąca do rozwiązywania zadań transportowych.Podstawowytransportowegozbilansowane.warunekzastosowania-zadanie transportowealgorytmumusi być∑a=∑bi=1ij=1mnjID,2013/2014Bilansowanie OZT (1)1)∑ai=1mi>∑bj=1njwprowadzamy fikcyjnegon+1odbiorcę o zapotrzebowaniu:bn+1=∑ai−∑bji=1j=1mndo macierzy kosztów wprowadzamy dodatkową kolumnę zerowąci,n+1= ... ID,2013/20145 [ Pobierz całość w formacie PDF ]