4.2. Метод мінімального елемента

Спочатку вибирають у вхідній таблиці клітинку, що відповідає найбільш дешевому маршруту, для якої досягається . Покладаємо , якщо , та викреслюємо рядок з номером . В цьому випадку змінюємо на . Якщо ж , то покладаємо і викреслюємо стовпець з номером , замінивши при цьому на .

Якщо , то покладаємо і викреслюємо або рядок з номером , або стовпець з номером .

Якщо викреслено стовпець, то замінивши на ; якщо викреслимо рядок, то замінюємо на .

В кожному випадку отримується нова таблиця (нова трансформована задача), яку заповнюємо тим же методом мінімального елемента.

§5. Метод потенціалів розв’язування транспортної задачі.

Нехай маємо транспортну задачу. Побудуємо двоїсту для неї задачу, приписавши обмеженням (2) змінні u₁,u₂,u₃, а обмеженням (3) – v₁,v₂,v₃,v₄ двоїстої задачі. Вона має вигляд

max w=a₁u₁+ a₂u₂+ a₃u₃+ b₁u₁+b₂v₂+ b₃v₃+ b₄v₄ (9)

при обмеженнях

u₁+v₁≤c₁₁, u₁+v₂≤c₁₂, u₁+v₃≤c₁₃, u₁+v₄≤c₁₄,

u₂+v₁≤c₂₁, u₂+v₂≤c₂₂, u₂+v₃≤c₂₃, u₂+v₄≤c₂₄, (10)

u₃+v₁≤c₃₁, u₂+v₂≤c₃₂, u₃+v₃≤c₃₃, u₃+v₄≤c₃₄.

Нехай маємо деякий базисний розв’язок задачі (1)-(4), отриманий, наприклад, методом північно-західного кута. Нехай, наприклад, його базисними змінними будуть х₁₁, х₁₂, х₂₂, х₂₃, х₃₃, х₃₄.

Складаємо систему рівнянь, яка отримується з (10), якщо замінити на = в тих, обмеженнях, які відповідають базисним змінним:

u₁+v₁≤c₁₁, u₁+v₂≤c₁₂, u₂+v₂≤c₂₂, u₂+v₃≤c₂₃, u₃+v₃≤c₃₃, u₃+v₄≤c₃₄. (11)

Алгоритму методу потенціалів розв’язування транспортної задачі (1) – (4):

1. Знаходимо вихідний базисний розв’язок (методом північно – західного кута або методом мінімальних елементів).

2. Розв’язуємо відповідну усьому базисному розв’язку систему рівнянь типу системи (11), яка одержується з обмежень задачі, двоїстої до (1) – (4) заміною знаків  на  в тих обмеженнях, у відповідність базисним змінним цього базисного розв’язку. В результаті знаходимо значення потенціалів u_i , I = 1…m, та v_j, j = 1…n.

3. Для всіх небазисних індексів (I, j) обчислюємо _ij= u_i + v_j – c_ij. Якщо всі ці оцінки  0, то процес закінчено: розглядуваний базисний розв’язок є оптимальним. Якщо серед _ij є > 0 , то за певним правилом вибираємо одну з цих оцінок (наприклад, найбільшу або першу із додатніх у порядку їх обчислення).

4. Будуємо новий базисний розв’язок, вводячи в число базисних змінних змінну х_ij , що відповідає вибраній симплекс – різниці _ij > 0, і виводимо із числа базисних одну із старих базисних змінних.

Повертаємось до п. 2, маючи на увазі новий базисний розв’язок.

Білет 15

1. Метричні простори. Відкриті та замкнуті множини, їх властивості.

Означення. Метричним простором називається пара , що складається з деякої множини X елементів і відстані, тобто однозначної, невід'ємної, дійсної функції , визначеної для будь-яких х і у з X, і яка задовольняє таким трьом аксіомам:

1) тоді і тільки тоді, коли ;

2) (аксіома симетрії): ;

3) (аксіома трикутника): ;

Сам метричний простір позначатимемо .

Приклади метричних просторів.

1. Множина упорядкованих груп з n дійсних чисел

з відстанню (1)

називається – n-вимірним арифметичним евклідовим простором Справедливість аксіом 1) і 2) для очевидна. Покажемо, що в виконана й аксіома трикутника.

Нехай , і ; тоді аксіому трикутника записуємо у вигляді

(2)

Припускаючи дістанемо а нерівність (2) набуває при цьому вигляду

(3)

Але ця нерівність відразу випливає з відомої нерівності Коші-Буняковського:

(4)

Справді, внаслідок цієї нерівності маємо

тим самим нерівність (3), а отже, і (2) доведено.

2. Множина С [a, b] усіх неперервних дійсних функцій, визначених на сегменті [a, b], з відстанню

(5)

також утворює метричний простір. Аксіоми 1) – 3) перевіряємо безпосередньо. Цей простір відіграє дуже важливу роль в аналізі. Ми його позначатимемо тим самим символом С [a, b], що й множину точок цього простору. Замість С [0;1] ми писатимемо просто С.

Граничні точки. Замикання.

Відкритою кулею у метричному просторі ми називатимемо сукупність точок , які задовольняють умову

Точка називається центром цієї кулі, а число — її радіусом.

Замкнутою кулею ми назвемо сукупність точок , які задовольняють умову

Відкриту кулю радіуса з центром ми називатимемо також -околом точки і позначатимемо символом .

Точка називається точкою дотику множини , якщо будь-який її окіл містить хоча б одну точку з М. Сукупність усіх точок дотику множини М позначається [M] і називається замиканням цієї множини.

Теорема 1 Операція замикання має такі властивості:

1) ,

2) ,

3) якщо , то ,

4) .

Доведення.

Доведемо, наприклад, четверту властивість. Якщо , то х міститься принаймні в одній з множин або , тобто

.

Оскільки і , то обернене включення випливає з властивості 3). Теорему доведено.

Точка називається граничною точкою множини , якою будь-який її окіл містить нескінченно багато точок з М.

Гранична точка може належати, а може не належати М. Наприклад, якщо М — множина раціональних чисел з відрізка [0,1], то кожна точка цього відрізка — гранична для M.

Точка х, яка належить М, називається ізольованою точкою цієї множини, якщо в досить малому її околі немає точок з M, відмінних від х.

Усяка точка дотику множини М є або гранична, або ізольована точка цієї множини.

Замикання складається, взагалі кажучи, з точок трьох типів:

1) ізольовані точки множини М;

2) граничні точки множини M, які належать M;

3) граничні точки множини М, які не належать М.

Відкриті і замкнуті множини

Множина М, що лежить у метричному просторі , називається замкнутою, якщо вона збігається з своїм замиканням: . Інакше кажучи, множина називається замкнутою, якщо вона містить всі свої граничні точки.

Приклади.

1. Усякий сегмент числової прямої є замкну­та множина.

2. Замкнута куля є замкнута множина. Зокрема, у просторі множина функцій f, які задовольняють умову , замкнута.

Теорема 2. Перетин будь-якого числа і сума будь-якого скінченного числа замкнутих множин є замкнуті множини.

Доведення. Нехай — перетин замкнутих множин і нехай х — гранична точка для F. Це означає, що будь-який її окіл має нескінченно багато точок з F. Але тоді тим більше має нескінченно багато точок з кожної і, отже, бо всі замкнуті, точка х належить кожній ; отже, , тобто замкнута.

Нехай тепер — сума скінченного числа замкнутих множин: , і нехай точка х не належить . Покажемо, що х не може бути граничною для . Справді, х не належить жодній із замкнутих множин , отже, не є граничною ні для жодної з них. Тому для кож­ного і можна знайти такий окіл точки х, яка має не більш як скінченне число з . Взявши з околів найменший, дістанемо окіл точки х, що містить не більш як скінченне число точок з .

Отже, якщо точка х не належить , то вона не може бути граничною для , тобто замкнута. Теорему доведено.

Точка х називається внутрішньою точкою множини М, якщо існує окіл цієї точки, який цілком міститься в М.

Множина, всі точки якої внутрішні, називається відкритою.

Приклади.

1. Інтервал числової прямої є відкрита множина; справді якщо, , то , де , повністю міститься в інтервалі .

2. Відкрита куля в будь-якому метричному просторі є відкрита множина. Справді, якщо , то . Припустимо, що . Тоді .

Теорема 3. Щоб множина М була відкрита, необхідно і достатньо, щоб її доповнення R\M до всього простору R було замкнуте.

Доведння. Якщо М відкрита, то кожна точка х з М має окіл, який повністю належить М, тобто такий що не має жодної спільної точки з R\M. Отже, жодна з точок, які не належать R \ M, не може бути точкою дотику для R \ M, тобто R \ M замкнуте. Навпаки, якщо R\M замкнуте, то будь-яка точка М має окіл, який повністю лежить в М, тобто М відкрита.

Оскільки порожня множина і всі R замкнуті і водночас є доповненнями одна одної, то порожня множина і всі R відкриті.

Теорема 4. Сума будь-якого числа і перетин будь-якого скінченого числа відкритих множин є відкриті множини.