Dodatkowe ograniczenia problemu transportowego. Opisana powyżej metoda rozwiązania problemu transportowego ma prostszy logiczny schemat obliczeń niż metoda potencjalna

Zadanie transportowe

Kiedy znajdziesz rozwiązanie problemu transportu metoda renty różnicowe po pierwsze, część ładunku jest rozdzielana w najlepszy możliwy sposób pomiędzy miejscami docelowymi (tzw. warunkowo optymalna dystrybucja) i w kolejnych iteracjach stopniowo zmniejszać całkowitą ilość nieprzydzielonych dostaw. Opcja początkowego rozkładu obciążenia jest określana w następujący sposób. W każdej kolumnie tabeli danych zadania transportowego znajduje się najniższa taryfa. Znalezione liczby są otoczone kółkami, a komórki zawierające wskazane liczby są wypełniane. Zapisane są w nich maksymalne możliwe liczby. W rezultacie uzyskuje się określony rozkład dostaw ładunków do miejsc docelowych. Rozkład ten generalnie nie spełnia ograniczeń pierwotnego problemu transportowego. Dlatego kolejnym krokiem powinno być stopniowe ograniczanie dostaw ładunków nieprzydzielonych, tak aby całkowity koszt transportu pozostał minimalny. W tym celu określane są nadmiarowe i niewystarczające wiersze.

Linie odpowiadające dostawcom, których zapasy są w pełni przydzielone i których miejsca docelowe powiązane z tymi klientami nie są zaspokajane przez zaplanowanych dostawców, uważa się za niewystarczające. Linie te są czasami nazywane także liniami ujemnymi. Linie, które nie są całkowicie wyczerpane, uważa się za nadwyżkowe. Czasami nazywane są również pozytywnymi.

Po ustaleniu wierszy nadmiarowych i niedostatecznych dla każdej z kolumn wyznaczane są różnice pomiędzy liczbą w kółku a najbliższą taryfą wpisaną w wierszu nadmiarowym. Jeśli liczba w okręgu znajduje się na linii dodatniej, różnica nie jest określana. Wśród uzyskanych liczb znajdź najmniejszą. Liczba ta nazywana jest rentą pośrednią. Po ustaleniu renty pośredniej przechodzą do nowej tabeli. Tabelę tę uzyskuje się z poprzedniej tabeli poprzez dodanie czynszu pośredniego do odpowiednich taryf w wierszach ujemnych. Pozostałe elementy pozostają takie same. W takim przypadku wszystkie komórki nowej tabeli są uważane za wolne. Po zbudowaniu nowej tabeli jej komórki zaczynają się wypełniać. Teraz liczba wypełnionych komórek jest o jedną większa niż na poprzednim etapie. Ta dodatkowa komórka znajduje się w kolumnie, w której zarejestrowano rentę pośrednią. Wszystkie pozostałe komórki znajdują się po jednej w każdej z kolumn i są najmniejsze tej kolumny liczby ujęte w kółka. W kółkach znajdują się dwie identyczne liczby w kolumnie, w której w poprzedniej tabeli zapisano rentę pośrednią.

Ponieważ w nowej tabeli liczba komórek do wypełnienia jest większa niż liczba kolumn, przy wypełnianiu komórek należy zastosować specjalną regułę, która wygląda następująco. Wybierz określoną kolumnę (wiersz), w której znajduje się jedna komórka z zaznaczonym kółkiem. Ta komórka jest wypełniona, a ta kolumna (wiersz) jest wyłączona z analizy. Następnie weź określony wiersz (kolumnę), w którym znajduje się jedna komórka z umieszczonym w niej okręgiem. Ta komórka jest wypełniona i wykluczona z analizy. ta linia(kolumna). Kontynuując w ten sposób, po skończonej liczbie kroków, wszystkie komórki, w których znajdują się kółka z zawartymi w nich liczbami, zostaną wypełnione. Jeżeli dodatkowo możliwa jest dystrybucja całego dostępnego w punktach wyjścia ładunku pomiędzy punktami przeznaczenia, wówczas uzyskuje się optymalny plan zadania transportowego. Jeśli nie zostanie uzyskany optymalny plan, przechodzą do nowego stołu. Aby to zrobić, znajdź linie nadmiarowe i niewystarczające, czynsz pośredni i zbuduj na tej podstawie nowy stół. W takim przypadku mogą pojawić się pewne trudności w określeniu znaku ciągu, gdy takowy jest nieprzydzielone saldo równy zeru. W takim przypadku wiersz uważa się za dodatni pod warunkiem, że druga wypełniona komórka, znajdująca się w kolumnie powiązanej z tym wierszem przez inną wypełnioną komórkę, znajduje się w wierszu dodatnim.

Jeżeli przy ustalaniu optymalnego planu problemu transportowego metodą potencjalną, niektóre z jego planie referencyjnym, a następnie był on konsekwentnie udoskonalany, to przy rozwiązywaniu problemu transportowego metodą rent różniczkowych część ładunku jest najpierw rozdzielana pomiędzy miejscami docelowymi w najlepszy możliwy sposób (tzw. warunkowo optymalny rozkład) i w kolejnych iteracjach stopniowo zmniejszać całkowitą ilość nieprzydzielonych dostaw. Opcja początkowego rozkładu obciążenia jest określana w następujący sposób. W każdej z kolumn tabeli danych zadania przewozowego znajduje się stawka minimalna. Znalezione liczby są otoczone kółkami, a komórki zawierające wskazane liczby są wypełniane. Zapisane są w nich maksymalne możliwe liczby. W rezultacie uzyskuje się określony rozkład dostaw ładunków do miejsc docelowych. Rozkład ten generalnie nie spełnia ograniczeń pierwotnego problemu transportowego. Dlatego kolejnym krokiem powinno być stopniowe ograniczanie dostaw ładunków nieprzydzielonych, tak aby całkowity koszt transportu pozostał minimalny. Aby to zrobić, najpierw określ nadmiarowe i niewystarczające wiersze.

Linie odpowiadające dostawcom, których zapasy są w pełni przydzielone i których popyt z miejsc docelowych powiązanych z planowanymi wysyłkami tych klientów nie jest spełniony, uznaje się za niewystarczające. Linie te są czasami nazywane także liniami ujemnymi. Linie, które nie są całkowicie wyczerpane, uważa się za nadwyżkowe. Czasami nazywane są również pozytywnymi.

Po ustaleniu wierszy nadmiarowych i niedostatecznych dla każdej z kolumn wyznaczane są różnice pomiędzy liczbą w kółku a najbliższą taryfą wpisaną w wierszu nadmiarowym. Jeśli liczba w okręgu znajduje się na linii dodatniej, różnica nie jest określana. Wśród uzyskanych liczb znajdź najmniejszą. Ten numer się nazywa czynsz pośredni. Po ustaleniu renty pośredniej przechodzą do nowej tabeli. Tabelę tę uzyskuje się z poprzedniej tabeli poprzez dodanie czynszu pośredniego do odpowiednich taryf w wierszach ujemnych. Pozostałe elementy pozostają takie same. W takim przypadku wszystkie komórki nowej tabeli są uważane za wolne. Po zbudowaniu nowej tabeli jej komórki zaczynają się wypełniać. Teraz liczba wypełnionych komórek jest o jedną większa niż na poprzednim etapie. Ta dodatkowa komórka znajduje się w kolumnie, w której zarejestrowano rentę pośrednią. Wszystkie pozostałe komórki znajdują się po jednej w każdej z kolumn i zawierają najmniejsze liczby dla danej kolumny, ujęte w kółka. W kółkach znajdują się dwie identyczne liczby w kolumnie, w której w poprzedniej tabeli zapisano rentę pośrednią.

Ponieważ w nowej tabeli liczba komórek do wypełnienia jest większa niż liczba kolumn, przy wypełnianiu komórek należy zastosować specjalną regułę, która wygląda następująco. Wybierz określoną kolumnę (wiersz), w której znajduje się jedna komórka z umieszczonym w niej okręgiem. Ta komórka jest wypełniona, a ta kolumna (wiersz) jest wyłączona z analizy. Następnie weź określony wiersz (kolumnę), w którym znajduje się jedna komórka z umieszczonym w niej okręgiem. Ta komórka jest wypełniona, a ten wiersz (kolumna) jest wyłączony z analizy. Kontynuując w ten sposób, po skończonej liczbie kroków, wszystkie komórki, w których znajdują się kółka z zawartymi w nich liczbami, zostaną wypełnione. Jeżeli dodatkowo możliwa jest dystrybucja całego dostępnego w punktach wyjścia ładunku pomiędzy punktami przeznaczenia, wówczas uzyskuje się optymalny plan zadania transportowego. Jeśli nie zostanie uzyskany optymalny plan, przechodzą do nowego stołu. Aby to zrobić, znajdź zbędne i niewystarczające wiersze, czynsz pośredni i na tej podstawie zbuduj nową tabelę. W takim przypadku mogą pojawić się pewne trudności w określeniu znaku ciągu, gdy jego nieprzydzielona reszta wynosi zero. W takim przypadku wiersz uważa się za dodatni pod warunkiem, że druga wypełniona komórka, znajdująca się w kolumnie powiązanej z tym wierszem przez inną wypełnioną komórkę, znajduje się w wierszu dodatnim.

Po skończonej liczbie iteracji opisanych powyżej nieprzydzielona reszta staje się równy zeru. W efekcie uzyskuje się optymalny plan danego zadania transportowego.

Opisana powyżej metoda rozwiązania problemu transportu jest prostsza obwód logiczny obliczeń niż potencjalna metoda omówiona powyżej. Dlatego w większości przypadków, aby znaleźć rozwiązanie konkretnych problemów transportowych za pomocą komputera, stosuje się metodę czynszów różnicowych.

5.6 Wyznaczenie planu optymalnego dla problemów transportowych, które mają pewne komplikacje w sformułowaniu.

Szukając rozwiązania szeregu specyficznych problemów transportowych, często konieczne jest uwzględnienie dodatkowych ograniczeń, które nie zostały napotkane powyżej przy rozważaniu proste opcje te zadania. Rozważmy bardziej szczegółowo niektóre możliwe komplikacje w formułowaniu problemów transportowych.

1. W pewnych rzeczywistych warunkach transportu ładunku z określonego punktu wyjścia , do miejsca docelowego , nie może zostać wdrożony. Aby określić optymalne plany dla takich problemów, przyjmuje się, że stawka za przewóz jednostki ładunku z punktu do punktu , jest dowolnie duży M, i pod tym warunkiem znane metody znaleźć rozwiązanie nowego problemu transportowego. Przy takim założeniu w ramach optymalnego planu zadania transportowego wykluczona jest możliwość transportu ładunku z punktu do punktu. . Takie podejście do znalezienia rozwiązania problemu transportowego nazywa się zakaz transportu Lub bloking odpowiednią komórkę w tabeli danych zadania.

2. Przy niektórych zadaniach transportowych dodatkowym warunkiem jest zapewnienie przewozu odpowiednimi trasami pewna ilośćładunek Niech np. z punktu wyjścia do miejsca przeznaczenia konieczne będzie przemieszczenie jednostek ładunku. Następnie określony numer jest zapisywany w komórce tabeli danych zadania transportowego, znajdującej się na przecięciu wiersza i kolumny, a w przyszłości komórka ta jest uważana za wolną z dowolnie dużą taryfą transportową M. Dla otrzymanego w ten sposób nowego problemu transportowego wyznaczany jest plan optymalny, który wyznacza plan optymalny oryginalny problem.

3. Czasami konieczne jest znalezienie rozwiązania problemu transportowego, w którym należy dostarczyć przynajmniej określoną ilość ładunku z miejsca wyjazdu do miejsca przeznaczenia. Aby określić optymalny plan rozwiązania takiego problemu, uważa się, że rezerwy przedmiotu i potrzeby tego przedmiotu są mniejsze niż rzeczywiste w jednostkach. Następnie ustalany jest optymalny plan nowego problemu transportowego, na podstawie którego określane jest rozwiązanie pierwotnego problemu.

4. W przypadku niektórych problemów transportowych konieczne jest znalezienie optymalnego planu transportu pod warunkiem, że od miejsca wyjazdu do miejsca przeznaczenia, tj. przewiezionych zostanie nie więcej niż jednostka ładunku.

Sformułowany problem można rozwiązać w następujący sposób. W tabeli danych zadania początkowego dla każdego ograniczenia (1) podawana jest dodatkowa kolumna, czyli wpisywany jest dodatkowy cel. W tej kolumnie zapisywane są te same taryfy, co w kolumnie, z wyjątkiem taryfy znajdującej się w wierszu th. W dodatkowej kolumnie w tym wierszu taryfę uważa się za równą pewnej dowolnie dużej liczbie. W tym przypadku potrzeby punktu uznaje się za równe i za równe uznaje się potrzeby nowo wprowadzonej destynacji. Rozwiązanie powstałego problemu transportowego można znaleźć metodą potencjałów, a tym samym ustalić optymalny plan lub ustalić nierozwiązywalność pierwotnego problemu. Należy pamiętać, że pierwotny problem transportowy można rozwiązać tylko wtedy, gdy istnieje dla niego co najmniej jeden plan odniesienia.

Powyższy problem można rozwiązać w ten sposób. Uwzględniając ograniczenie (1), plan odniesienia budowany jest z wykorzystaniem zasady minimalnego elementu. Co więcej, jeśli wartość zarejestrowana w dniu ten krok do odpowiedniej komórki liczba jest określona tylko przez ograniczenie (1), wówczas z analizy wyłączana jest później tylko wypełniona komórka. W innych sprawach z rozważania wykluczają wiersz lub kolumnę (jedną lub drugą).

Jeżeli w wyniku sporządzenia planu zaopatrzenia rozdystrybuowane zostaną wszystkie dostępne zapasy punktów odjazdu i zaspokojone zostaną potrzeby w punktach docelowych, wówczas uzyskuje się podstawowy plan zadania przewozowego.

Jeżeli w jakimś wierszu (a zatem w kolumnie) znajduje się nieprzydzielone saldo równe , następnie wprowadza się dodatkowe miejsce docelowe i dodatkowy punkt wyjścia z równymi wymaganiami i dostawami . W komórce znajdującej się na przecięciu kolumny dodatkowy punkt miejsca docelowego a linią dodatkowego punktu odjazdu, taryfę uznaje się za równą zeru. We wszystkich pozostałych komórkach danego wiersza i kolumny przyjmuje się, że stawki są równe jakiejś dowolnie dużej liczbie M. Powstały problem transportu rozwiązuje się metodą potencjalną. Po skończonej liczbie kroków ustala się, że pierwotny problem nie ma planu odniesienia, lub zostaje znaleziony jego plan optymalny. W której – optymalny plan pierwotnego problemu, jeśli

Część teoretyczna

Zadania ekonomiczne sprowadzone do modelu transportowego

Model transportu służy do stworzenia najbardziej ekonomicznego planu transportu jednego rodzaju produktu z kilku punktów (na przykład fabryk) do punktów dostawy (na przykład magazynów). Model transportu można zastosować, rozważając szereg praktycznych sytuacji związanych z zarządzaniem zapasami, planowaniem zmian, przydzielaniem pracowników do stanowisk, obrotem dostępnym kapitałem, regulacją przepływu wody w zbiornikach i wieloma innymi. Dodatkowo model można modyfikować w celu umożliwienia transportu wielu rodzajów produktów.

Problem transportu jest zadaniem Programowanie liniowe, jednakże jej specyficzna konstrukcja pozwala na modyfikację metody sympleksowej w taki sposób, aby procedury obliczeniowe stały się wydajniejsze. Przy opracowywaniu metody rozwiązania problemu transportowego znaczącą rolę odgrywa teoria dualności.

Klasyczny problem transportu dotyczy transportu (bezpośredniego lub z punktami pośrednimi) jednego lub większej liczby rodzajów produktów z miejsca pochodzenia do miejsca przeznaczenia. Problem ten można zmodyfikować, aby uwzględnić górne ograniczenia dotyczące wydajność komunikacja transportowa. Za problemy można uznać problem przypisania i problem zarządzania zapasami rodzaj transportu. Istnieje kilka rodzajów problemów ekonomicznych, które można sprowadzić do modelu transportu:

– optymalne rozmieszczenie sprzętu;

– kształtowanie optymalnej kadry firmy;

- zadanie planowanie produkcja;

– optymalne badania rynek;

– optymalne wykorzystanie agenci pracujący;

– problem lokalizacji produkcji;

– problem z przydziałem.

Problem kształtowania optymalnej kadry przedsiębiorstwa w ogólna perspektywa formułuje się następująco.

Firma prowadzi rekrutację pracowników. Ma n grup o różnych pozycjach z bj wolnych jednostek w każdej grupie, j = 1,…,n. Kandydaci na stanowiska poddawani są testowi, według wyniku którego dzieleni są na m grup po ai kandydatów w każdej grupie, i = 1,...,m. Dla każdego kandydata z i-tej grupy wymagane są określone koszty szkolenia Cij, aby zająć j-te stanowisko, i=1,…,m; j=1,…,n. (W szczególności pewne Cij = 0, czyli kandydat w pełni odpowiada stanowisku, lub Cij = ∞ (Cij = M), czyli kandydat w ogóle nie może zajmować tego stanowiska.) Wymagane jest rozdysponowanie kandydatów na stanowiska, wydając minimalne środków na ich szkolenie. Udawajmy, że Łączna kandydatów odpowiada liczbie wolnych stanowisk. Następnie to zadanie odpowiada modelowi transportu. Grupy kandydatów pełnią rolę dostawców, a grupy stanowisk pełnią rolę konsumentów. Koszty przekwalifikowania traktowane są jako stawki za transport. Model matematyczny zapisuje się jako:

Metoda czynszów różnicowych do rozwiązania problemu transportowego

Aby rozwiązać problemy transportowe, stosuje się kilka metod. Rozważmy rozwiązanie wykorzystując metodę rent różniczkowych.

Szukając rozwiązania problemu transportowego metodą rent różniczkowych, w pierwszej kolejności część ładunku jest najlepiej rozdzielana pomiędzy miejsca przeznaczenia (tzw. dystrybucja warunkowo optymalna), a w kolejnych iteracjach stopniowo zmniejsza się łączna wielkość dostaw nierozdystrybuowanych. Opcja początkowego rozkładu obciążenia jest określana w następujący sposób. W każdej z kolumn tabeli danych zlecenia transportowego znajduje się stawka minimalna. Znalezione liczby są otoczone kółkami, a komórki zawierające wskazane liczby są wypełniane. Zapisane są w nich maksymalne możliwe liczby. W rezultacie uzyskuje się określony rozkład dostaw ładunków do miejsc docelowych. Rozkład ten generalnie nie spełnia ograniczeń pierwotnego problemu transportowego. Dlatego w wyniku kolejnych kroków należy stopniowo ograniczać dostawy ładunków niealokowanych, tak aby całkowity koszt transportu pozostał minimalny. Aby to zrobić, najpierw określ nadmiarowe i niewystarczające wiersze.

Po ustaleniu wierszy nadmiarowych i niedostatecznych dla każdej z kolumn wyznaczane są różnice pomiędzy liczbą w kółku a najbliższą taryfą wpisaną w wierszu nadmiarowym. Jeśli liczba w okręgu znajduje się na linii dodatniej, różnica nie jest określana. Wśród uzyskanych liczb znajdź najmniejszą. Liczba ta nazywana jest rentą pośrednią. Po ustaleniu renty pośredniej przechodzą do nowej tabeli. Tabelę tę uzyskuje się z poprzedniej tabeli poprzez dodanie czynszu pośredniego do odpowiednich taryf w wierszach ujemnych. Pozostałe elementy pozostają takie same. W takim przypadku wszystkie komórki nowej tabeli są uważane za wolne. Po zbudowaniu nowej tabeli jej komórki zaczynają się wypełniać. Teraz liczba wypełnionych komórek jest o jedną większa niż na poprzednim etapie. Ta dodatkowa komórka znajduje się w kolumnie, w której zarejestrowano rentę pośrednią. Wszystkie pozostałe komórki znajdują się po jednej w każdej z kolumn i zawierają najmniejsze liczby dla danej kolumny, ujęte w kółka. W kółkach znajdują się dwie identyczne liczby w kolumnie, w której w poprzedniej tabeli zapisano rentę pośrednią.

Ponieważ w nowej tabeli liczba komórek do wypełnienia jest większa niż liczba kolumn, przy wypełnianiu komórek należy zastosować specjalną regułę, która wygląda następująco. Wybierz określoną kolumnę (wiersz), w której znajduje się jedna komórka z zaznaczonym kółkiem. Ta komórka jest wypełniona, a ta kolumna (wiersz) jest wyłączona z analizy. Następnie weź określony wiersz (kolumnę), w którym znajduje się jedna komórka z umieszczonym w niej okręgiem. Ta komórka jest wypełniona, a ten wiersz (kolumna) jest wyłączony z analizy. Kontynuując w ten sposób, po skończonej liczbie kroków, wszystkie komórki, w których znajdują się kółka z zawartymi w nich liczbami, zostaną wypełnione. Jeżeli dodatkowo możliwa jest dystrybucja całego dostępnego w punktach wyjścia ładunku pomiędzy punktami przeznaczenia, wówczas uzyskuje się optymalny plan zadania transportowego. Jeśli nie zostanie uzyskany optymalny plan, przechodzą do nowego stołu. Aby to zrobić, znajdź zbędne i niewystarczające wiersze, czynsz pośredni i na tej podstawie zbuduj nową tabelę. W takim przypadku mogą pojawić się pewne trudności w określeniu znaku ciągu, gdy jego nieprzydzielona reszta wynosi zero. W takim przypadku wiersz uważa się za dodatni pod warunkiem, że druga wypełniona komórka, znajdująca się w kolumnie powiązanej z tym wierszem przez inną wypełnioną komórkę, znajduje się w wierszu dodatnim.

Po skończonej liczbie iteracji opisanych powyżej nieprzydzielona reszta wynosi zero. W efekcie uzyskuje się optymalny plan danego zadania transportowego.

Opisany powyżej sposób rozwiązania problemu transportowego ma prostszy logiczny schemat obliczeń niż metoda potencjalna. Dlatego w większości przypadków, aby znaleźć rozwiązanie konkretnych problemów transportowych za pomocą komputera, stosuje się metodę czynszów różnicowych.

Przykład rozwiązania problemu.

Dla problemu transportowego, którego dane początkowe podano w tabeli. 1.2.1 znaleźć optymalny plan stosując metodę renty różnicowej.

Tabela 1.2.1 Dane wyjściowe zadania transportowego

Rozwiązanie. Przejdźmy dalej od stołu. 1.2.1 do tabeli. 1.2.2, dodanie jednej dodatkowej kolumny do wskazania nadmiaru i niedoboru w poszczególnych wierszach oraz jednego wiersza do zapisania odpowiednich różnic.

Tabela 1.2.2 Nadwyżki i braki

Punkty odjazdu	Miejsca docelowe	Rezerwy	Niedobór(-), Nadmiar(+)
W 1	O 2	O 3	O 4	O 5
A1			4			+60
A2	1	8		5	3	-80
A3						+20
Wymagania
Różnice			–

W każdej kolumnie tabeli. 1.2.2 znajdujemy stawki minimalne i zakreślamy je. Wypełnij komórki zawierające wskazane liczby. Aby to zrobić, wpisz maksymalną dozwoloną liczbę w każdej komórce. Przykładowo w komórce znajdującej się na przecięciu wiersza A 1 i kolumny B 3 wpisujemy liczbę 120. W tej komórce nie można umieścić większej liczby, gdyż w tym przypadku zostałyby przekroczone potrzeby celu B 3.

W wyniku wypełnienia powyższych komórek otrzymano tzw. warunkowo optymalny plan, według którego potrzeby destynacji B 1, B 2, B 3 i B 4 są w pełni zaspokojone, a częściowo potrzeby destynacji B 5 . Jednocześnie rezerwy punktu wyjścia A 2 są w pełni rozdzielone, rezerwy punktu wyjścia A 1 są częściowo rozdzielone, a rezerwy punktu wyjścia A 3 pozostają całkowicie nierozdzielone.

Po uzyskaniu warunkowo optymalnego planu określamy linie zbędne i niewystarczające. Tutaj linia A 2 jest niewystarczająca, gdyż rezerwy punktu odjazdu A 2 są w pełni wykorzystane, a potrzeby miejsca docelowego B5 są częściowo zaspokojone. Ilość niedoboru wynosi 80 jednostek.

Linie A 1 i A 3 są zbędne, ponieważ zapasy źródeł A 1 i A 3 nie są całkowicie przydzielone. W tym przypadku wartość nadwyżki linii A 1 wynosi 60 jednostek, a linii A 3 wynosi 20 jednostek. całkowita ilość nadwyżki 60+20=80 pokrywa się z całkowitą kwotą niedoboru równą 80.

Po określeniu nadmiarowych i niewystarczających wierszy dla każdej z kolumn znajdujemy różnice pomiędzy stawkami minimalnymi zapisanymi w nadmiarowych wierszach a stawkami w wypełnionych komórkach. W w tym przypadku różnice te wynoszą odpowiednio 5,4,2,1 (tabela 1.2.2). W przypadku kolumny B 3 różnica nie jest zdefiniowana, ponieważ liczba wpisana w kółko w tej kolumnie znajduje się w wierszu dodatnim. W kolumnie B 1 liczba w okręgu wynosi 1, a w zbędnych wierszach komórek tej kolumny najmniejsza liczba to 6. Zatem różnica dla tej kolumny wynosi 6-1=5. Podobnie znajdujemy różnice dla innych kolumn: dla B 2 12-8 = 4; dla B47-5=2; dla B 5 4-3=1.

Wybieramy najmniejszą ze znalezionych różnic, czyli czynsz pośredni. W tym przypadku czynsz pośredni wynosi 1 i znajduje się w kolumnie B 5. Po znalezieniu czynszu pośredniego przechodzimy do tabeli. 1.2.3

Tabela 1.2.3 Czynsz pośredni

Punkty odjazdu	Miejsca docelowe	Rezerwy	Niedobór(-), Nadmiar(+)
W 1	O 2	O 3	O 4	O 5
A1			4			+60
A2	2	9		6	4	-60
A3					4	-0
Wymagania
Różnice			–

W tej tabeli w wierszach A 1 i A 3 (które są zbędne) przepisujemy odpowiednie taryfy z wierszy A 1 i A 3 tabeli. 1.2.2. elementy wiersza A 2 (które były niewystarczające) uzyskuje się poprzez dodanie do odpowiednich taryf znajdujących się w wierszu A 2 tabeli. 1.2.2, renta pośrednia, tj. 1.

W tabeli 1.2.3 liczba wypełnionych komórek wzrosła o jeden. Wynika to z faktu, że liczba stawek minimalnych w każdej z kolumn tej tabeli wzrosła o jeden, a mianowicie w kolumnie B 5 znajdują się teraz dwa elementy minimalne 4. Liczby te otaczamy kółkami; należy pamiętać o celach, w których stoją. Należy także wypełnić komórki zawierające najniższe taryfy dla pozostałych kolumn. To są komórki tabeli. 1.2.3, w którym odpowiednie taryfy są ujęte w kółka. Po ustaleniu określonych komórek ustalamy kolejność ich wypełniania. Aby to zrobić, znajdujemy kolumny (wiersze), w których jest tylko jedna komórka do wypełnienia. Po zidentyfikowaniu i wypełnieniu określonej komórki wykluczamy odpowiednią kolumnę (wiersz) z rozważań i przechodzimy do wypełniania kolejnej komórki. W tym przypadku wypełniamy komórki w następującej kolejności. Najpierw wypełnij komórki A 1 B 3, A 2 B 1, A 2 B 2, A 2 B 4, ponieważ są to jedyne komórki, które wypełniają kolumny B 1, B 2, B 3 i B 4. Po wypełnieniu wskazanych komórek należy wypełnić komórkę A 3 B 5, gdyż jako jedyna należy ją wypełnić w wierszu A3. Po wypełnieniu tej komórki pomijamy linię A 3. Wtedy w kolumnie B 5 pozostanie tylko jedna komórka do wypełnienia. To jest komórka A 2 B 5, którą wypełniamy. Po wypełnieniu komórek ustawiamy linie zbędne i niewystarczające. Jak widać z tabeli. 1.2.3, nadal istnieje saldo niepodzielone. Uzyskano zatem warunkowo optymalny plan problemu i musimy przejść do nowej tabeli. W tym celu dla każdej z ich kolumn znajdujemy różnicę pomiędzy liczbą wpisaną w kółko tej kolumny a najmniejszą liczbą względem niej, znajdującą się w zbędnych wierszach. Wśród tych różnic najmniejsza wynosi 1. Jest to czynsz pośredni. Przejdźmy do kolejnej tabeli (tabela 1.2.4).

Tabela 1.2.4 Optymalny plan zadania transportowego

Punkty odjazdu	Miejsca docelowe	Rezerwy	Niedobór(-), Nadmiar(+)
W 1	O 2	O 3	O 4	O 5
A1			4
A2	3	10		7	5
A3
Wymagania

W nowej tabeli elementy wierszy A 2 i A 3 uzyskuje się poprzez dodanie do odpowiednich numerów wierszy A 2 i A 3 (które są niewystarczające) tabeli. 1.2.3 renta pośrednia, tj. 1. W rezultacie w tabeli. 1.2.4 liczba komórek do wypełnienia wzrosła o jeszcze jeden i stała się równa 6. Określamy wskazane komórki i wypełniamy je. Najpierw wypełniamy komórki A 1 B 3, A 2 B 1, A 2 B 2, A 2 B 4, a następnie A 3 B 5, A 2 B 5, A 1 B 5. Dzięki temu wszystkie dostępne dostawy od dostawców są dystrybuowane zgodnie z rzeczywistymi potrzebami miejsc docelowych. Liczba wypełnionych komórek wynosi 7 i mają one najmniejszą wagę C ij . Otrzymuje się zatem optymalny plan pierwotnego problemu transportowego:

W przypadku tego planu transportu całkowite koszty wynoszą:

S=4*120+5*60+1*110+8*90+5*80+3*70+4*20=2300.

Część praktyczna

Zadanie. Niech będzie n kandydatów do wykonywania tych stanowisk. Powołanie kandydata i na stanowisko j wiąże się z kosztami C ij (i, j = 1,2,…, n). Należy znaleźć przypisanie kandydatów do wszystkich stanowisk, które dają minimalne koszty całkowite, przy czym każdy kandydat może być przypisany tylko do jednego stanowiska i na każdym stanowisku może pracować tylko jeden kandydat. Początkowe dane przedstawiono w tabeli:

Tabela 2.4 Dane wyjściowe

A i B j	B1	B2	B3	B4
A1
A2
A3
A4

dane wejściowe:

n – liczba kandydatów i stanowisk pracy, cały typ dane

C (n, n) - koszty (rub.), prawdziwy typ dane.

Wyjście:

Smin - koszty całkowite (rub.), rzeczywisty typ danych;

X (n, n) - przydział kandydata do pracy, typ danych integer.

Jeżeli przy ustalaniu optymalnego planu problemu transportowego metodą potencjałów najpierw znaleziono jakiś plan podstawowy, a następnie go konsekwentnie udoskonalano, to przy szukaniu rozwiązania problemu transportowego metodą rent różniczkowych pierwszą część ładunek jest dystrybuowany pomiędzy miejscami docelowymi w najlepszy możliwy sposób (tzw. dystrybucja warunkowo optymalna), a w kolejnych iteracjach całkowita ilość niealokowanych dostaw jest stopniowo zmniejszana. Opcja początkowego rozkładu obciążenia jest określana w następujący sposób. W każdej z kolumn tabeli danych zadania przewozowego znajduje się stawka minimalna. Znalezione liczby są otoczone kółkami, a komórki zawierające wskazane liczby są wypełniane. Zapisane są w nich maksymalne możliwe liczby. W rezultacie uzyskuje się określony rozkład dostaw ładunków do miejsc docelowych. Rozkład ten generalnie nie spełnia ograniczeń pierwotnego problemu transportowego. Dlatego kolejnym krokiem powinno być stopniowe ograniczanie dostaw ładunków nieprzydzielonych, tak aby całkowity koszt transportu pozostał minimalny. Aby to zrobić, najpierw określ nadmiarowe i niewystarczające wiersze.

Po ustaleniu wierszy nadmiarowych i niedostatecznych dla każdej z kolumn wyznaczane są różnice pomiędzy liczbą w kółku a najbliższą taryfą wpisaną w wierszu nadmiarowym. Jeśli liczba w okręgu znajduje się na linii dodatniej, różnica nie jest określana. Wśród uzyskanych liczb znajdź najmniejszą. Liczba ta nazywana jest rentą pośrednią . Po ustaleniu renty pośredniej przechodzą do nowej tabeli. Tabelę tę uzyskuje się z poprzedniej tabeli poprzez dodanie czynszu pośredniego do odpowiednich taryf w wierszach ujemnych. Pozostałe elementy pozostają takie same. W takim przypadku wszystkie komórki nowej tabeli są uważane za wolne. Po zbudowaniu nowej tabeli jej komórki zaczynają się wypełniać. Teraz liczba wypełnionych komórek jest o jedną większa niż na poprzednim etapie. Ta dodatkowa komórka znajduje się w kolumnie, w której zarejestrowano rentę pośrednią. Wszystkie pozostałe komórki znajdują się po jednej w każdej z kolumn i zawierają najmniejsze liczby dla danej kolumny, ujęte w kółka. W kółkach znajdują się dwie identyczne liczby w kolumnie, w której w poprzedniej tabeli zapisano rentę pośrednią.

Ponieważ w nowej tabeli liczba komórek do wypełnienia jest większa niż liczba kolumn, przy wypełnianiu komórek należy zastosować specjalną regułę, która wygląda następująco. Wybierz określoną kolumnę (wiersz), w której znajduje się jedna komórka z umieszczonym w niej okręgiem. Ta komórka jest wypełniona, a ta kolumna (wiersz) jest wyłączona z analizy. Następnie weź określony wiersz (kolumnę), w którym znajduje się jedna komórka z umieszczonym w niej okręgiem. Ta komórka jest wypełniona, a ten wiersz (kolumna) jest wyłączony z analizy. Kontynuując w ten sposób, po skończonej liczbie kroków, wszystkie komórki, w których znajdują się kółka z zawartymi w nich liczbami, zostaną wypełnione. Jeżeli dodatkowo możliwa jest dystrybucja całego dostępnego w punktach wyjścia ładunku pomiędzy punktami przeznaczenia, wówczas uzyskuje się optymalny plan zadania transportowego. Jeśli nie zostanie uzyskany optymalny plan, przechodzą do nowego stołu. Aby to zrobić, znajdź zbędne i niewystarczające wiersze, czynsz pośredni i na tej podstawie zbuduj nową tabelę. W takim przypadku mogą pojawić się pewne trudności w określeniu znaku ciągu, gdy jego nieprzydzielona reszta wynosi zero. W takim przypadku wiersz uważa się za dodatni pod warunkiem, że druga wypełniona komórka, znajdująca się w kolumnie powiązanej z tym wierszem przez inną wypełnioną komórkę, znajduje się w wierszu dodatnim.

Po skończonej liczbie iteracji opisanych powyżej nieprzydzielona reszta wynosi zero. W efekcie uzyskuje się optymalny plan danego zadania transportowego.

Opisany powyżej sposób rozwiązania problemu transportowego ma prostszy schemat obliczeń logicznych niż omówiona powyżej metoda potencjalna. Dlatego w większości przypadków, aby znaleźć rozwiązanie konkretnych problemów transportowych za pomocą komputera, stosuje się metodę czynszów różnicowych.

Przykład (4):

Dla problemu transportowego, którego wstępne dane podano w tabeli 11, znajdź plan optymalny, stosując metodę czynszów różnicowych.

Rozwiązanie. Przejdźmy od Tabeli 11 do Tabeli 12, dodając jedną dodatkową kolumnę do wskazania nadmiaru i niedoboru w poszczególnych wierszach oraz jeden wiersz do zapisania odpowiednich różnic.

Tabela 10.

Punkty odjazdu	Miejsca docelowe
Punkty odjazdu



Wymagania

Tabela 11.

Punkty odjazdu

Miejsca docelowe

Wada

nadmiar (

Wymagania

Różnica

W każdej kolumnie tabeli 12 znajdujemy stawki minimalne i zakreślamy je. Wypełnij komórki zawierające wskazane liczby. Aby to zrobić, wpisz maksymalną dozwoloną liczbę w każdej komórce. Przykładowo w komórce znajdującej się na przecięciu wiersza i kolumny wpisujemy liczbę 120. W tej komórce nie można umieścić większej liczby, gdyż w tym przypadku zostałyby przekroczone potrzeby miejsca docelowego.

W wyniku wypełnienia powyższych komórek uzyskuje się tzw. plan warunkowo optymalny, według którego potrzeby destynacji są w pełni zaspokojone, a częściowo potrzeby destynacji . Jednocześnie rezerwy punktu wyjścia zostały w pełni rozdzielone, częściowo - zaopatrzenie punktu wyjścia, a zapasy punktu wyjścia pozostały całkowicie niedystrybuowane.

Po uzyskaniu warunkowo optymalnego planu określamy linie zbędne i niewystarczające. Tutaj linia jest niewystarczająca , ponieważ rezerwy punktu wyjścia są w pełni wykorzystane, a potrzeby miejsca docelowego są częściowo zaspokojone. Ilość niedoboru wynosi 80 jednostek.

Smyczki I są zbędne, ponieważ zapasy są pierwotne I nie do końca rozdysponowany. W tym przypadku ilość nadmiaru linii wynosi 60 jednostek, a linia jest równa jednostkom. Całkowita kwota nadwyżki pokrywa się z całkowitą kwotą niedoboru, równą.

Po określeniu nadmiarowych i niewystarczających wierszy dla każdej z kolumn znajdujemy różnice pomiędzy stawkami minimalnymi zapisanymi w nadmiarowych wierszach a stawkami w wypełnionych komórkach. W tym przypadku różnice te wynoszą odpowiednio 5, 4, 2, 1 (tabela 11). Różnica jest niezdefiniowana dla kolumny, ponieważ liczba zakreślona w tej kolumnie znajduje się w wierszu dodatnim. W kolumnie liczba w okręgu jest równa, a w zbędnych wierszach w komórkach danej kolumny liczbą jest najmniejsza liczba. Zatem różnica dla tej kolumny jest równa.W podobny sposób znajdujemy różnice dla innych kolumn: for; Dla; Dla. .

Wybieramy najmniejszą ze znalezionych różnic, czyli czynsz pośredni. W tym przypadku czynsz pośredni jest równy i znajduje się w kolumnie . Po znalezieniu czynszu pośredniego przechodzimy do tabeli 11.

W tej tabeli w wierszach i (które są zbędne) przepisujemy odpowiednie taryfy z wiersza Tabela 10. Elementy linii (która okazała się niewystarczająca) uzyskuje się poprzez dodanie do odpowiednich taryf znajdujących się w tabeli linii. 10, renta pośrednia, tj.

W tabeli 11, liczba wypełnionych komórek wzrosła o jeden. Wynika to z faktu, że liczba stawek minimalnych w każdej kolumnie tej tabeli wzrosła o jeden, a mianowicie kolumna ma teraz dwa elementy minimalne. Zamykamy te liczby w kółkach; komórki, w których stoją, muszą być wypełnione. Należy także wypełnić komórki zawierające najniższe taryfy dla pozostałych kolumn. To są komórki tabeli. 11, w którym odpowiednie taryfy są ujęte w kółka.

Tabela 11.

Punkty odjazdu

Miejsca docelowe

Wada

nadmiar (

Wymagania

Różnica

Po ustaleniu określonych komórek ustalamy kolejność ich wypełniania. Aby to zrobić, znajdujemy kolumny (wiersze), w których jest tylko jedna komórka do wypełnienia. Po zidentyfikowaniu i wypełnieniu określonej komórki wykluczamy odpowiednią kolumnę (wiersz) z rozważań i przechodzimy do wypełniania kolejnej komórki. W tym przypadku wypełniamy komórki w następującej kolejności. Najpierw wypełniamy komórki ,,,, ponieważ są to jedyne komórki do wypełnienia w kolumnach. Po wypełnieniu określonych komórek wypełnij komórkę, ponieważ jako jedyna wypełnia wiersz . Po wypełnieniu tej komórki (tabela 2.16) wykluczamy linię z rozważań . Następnie w kolumnie pozostała tylko jedna komórka do wypełnienia. To jest klatka , które wypełniamy. Po wypełnieniu komórek ustawiamy linie zbędne i niewystarczające (Tabela 11). Jak widać z Tabeli 11, saldo nadal pozostaje nierozdzielone. W rezultacie uzyskano warunkowo optymalny plan problemu i musimy przejść do nowej tabeli. W tym celu dla każdej z kolumn znajdujemy różnice pomiędzy liczbą wpisaną w kółko tej kolumny a najmniejszą liczbą względem niej, umieszczoną w zbędnych wierszach (tabela 11). Wśród tych różnic najmniejsza jest. Jest to czynsz pośredni. Przejdźmy do nowej tabeli (Tabela 12).