52.   Etapy procedury rozwišzywania zadania transportowego.

-zbilansowanie zadania

-wyznaczanie wstępnego rozwiązania bazowego (np. metodą kąta północno-zachodniego, metodą

minimalnego elementu macierzy kosztów, metodą VAM)

-wyznaczanie rozwiązania optymalnego (np. metodą potencjałów)

53.   Metody wyznaczania wstępnego rozwišzania bazowego zadania transportowego.

metoda kąta północno-zachodniego

metoda minimalnego elementu macierzy kosztów

metoda VAM

54.   Postępowanie w przypadku degeneracji rozwišzania bazowego zadania transportowego.

Jeżeli zadanie ma mniej niż m+n-1 zmiennych bazowych (zadanie zdegenerowane) należy dołączyć

brakującą liczbę zmiennych bazowych z wartościami zerowymi. Wyboru należy dokonać tak, aby graf

rozwiązania był grafem spójnym i bez cykli.

55.   Interpretacja elementów tablicy wskaźników optymalności w metodzie potencjałów.

C⁰ = [c⁰_ij] i = 1, 2, …, m; j = 1, 2, …, n

gdzie c⁰_ij = u_i + v_j + c_ij

rozwiązanie optymalne [C⁰]>=0

56.   Kryterium stopu w algorytmie rozwišzywania zadania transportowego metodš potencjałów.

Jeżeli wszystkie elementy tablicy wskaźników optymalności w metodzie potencjałów są większe bądź równe 0, to znaleźliśmy rozwiązanie optymalne C⁰ ≥ 0

57.   Przykłady problemów decyzyjnych formułowanych w postaci zadania transportowego.

Określenie planu przewozowego pomiędzy dostawcami a odbiorcami tak, aby uwzględnić dostępne zapasy

dostawców i wymaganego zapotrzebowanie odbiorców aby łączne koszty transportu były minimalne.

58.   Postępowanie w przypadku całkowitej blokady przewozu na wybranej trasie w algorytmie rozwišzywania zadania transportowego.

W przypadku całkowitej blokady przewozu na wybranej trasie x_k,l =0 należy w macierzy kosztów w c_k,l

podstawić M jako bardzo dużą liczbę

59.   Postępowanie w przypadku częściowej blokady trasy w algorytmie rozwišzywania zadania transportowego.

0<=x<=ϴ_k,l ϴ_k,l <min(a_k,b_l)

W przypadku blokady x_k,l, należy w tablicy C wiersz k-ty podzielić na dwa wiersze. Górną część

podzielonego wiersza pozostawić bez zmian a do dolnej części w miejsce x_k,l, wstawić M(bardzo dużą

liczbę) pozostałe komórki w wierszu i tabeli pozostawić bez zmian. Następnie wyznaczyć rozwiązanie w

X^*.

60.   Postać zadania transportowego z kryterium czasu I i II rodzaju.

I. rodzaju min T(x)=∑_i∑_jt_ijx_ij

II. rodzaju z=min max(t_ij)

x€X

x_ij>0

 

61. Sformułuj zagadnienie przydziałów?

n wyborów (czynności) można wykonać w m miejscach produkcji. Znane są ograniczone moce produkcyjne poszczególnych miejsc pracy, często też zadania planowe w zakresie produkcji wyrobów. Jest też dana macierz K=[k_ij], której elementy oznaczają koszy i-tego miejsca pracy przy wykonywaniu jednostki j-tego wyboru. Należy zaproponować przydział zadań produkcyjnych do poszczególnych miejsc pracy, optymalny z punktu widzenia jednego z kryteriów:

- minimalizacji kosztów lub czasu wykonywania zadań planowych

- maksymalizacji efektów (ilości wyprodukowanych wyrobów)

62. Co to sš przydziały wzajemnie jednoznaczne?

Przedziały wzajemne jednoznaczne są wtedy jeżeli jeden element i tylko jeden element przydziału

pierwszego i na odwrót, jest przyporządkowany każdemu elementowi przedziału drugiego jeden i tylko

jeden element zbioru pierwszego.

63. Co to jest tablica oczek dopuszczalnych?

Jest to tablica możliwości przedziału. Oczka dopuszczalne odpowiadają możliwości przedziału zbioru A

danych elementów zbioru B. Pozostałe oczka tej tablicy są przekreślone i niedopuszczalne.

64. Co to sš niezależne oczka dopuszczalne w algorytmie wyznaczania przydziału najliczniejszego?

Wybrany zbiór oczek dopuszczalny będzie stanowił zbiór oczek niezależnych, gdy w każdym wierszu i w

Każdej kolumnie będzie wybrane nie więcej niż jedno oczko (wybrane oczka oznacza się jedynkami).