Метод Фогеля, транспортная задача

1. Здійснити транспортування матриці

А= [pic 1]

Розв′язання:

При транспортуванні міняємо місцями рядки та стовпці:

А=     ⇒   АТ =     [pic 2][pic 3]

1. Нехай задана матриця А=[pic 4]

Знайти всі елементи матриці  [pic 5], якщо відомо, що вона дорівнює матриці

В = [pic 6]

Розв′язання:

Якщо дві матриці дорівнюють одна одній, то їх відповідні елементи рівні між собою.

В = ;   А = В  ⇒     ⇒ [pic 7][pic 8]

a = 2, b = 4, c = 16, d = 2, e = 2, f = 1223, i = 45, k = 5, l = 1.

1.  Здійснити загальну математичну постановку транспортної задачі і побудувати опорний план методом апроксімації Фогеля.

[pic 9]

Розв’язання:

         Нехай запаси деякого однорідного продукту знаходяться на трьох пунктах

постачання (базах) А1,А2,А3 і цей продукт потрібно доставити в п′ять пунктів споживання (призначення) В1,В2,В3,В4,В5. Задача полягає в тому, щоб визначити, яку кількість продукту потрібно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовольнити повністю потреби кожного пункту споживання і при цьому сумарна вартість перевезень була б мінімальною (зворотні перевезення виключаються). Вартість перевезень Сіj (у грн.) з бази Аі  до пункту призначення Вj вказана в таблиці, де також наведені дані про запаси аі  (у тонах) продукту на базі Аі  і  його потреби  bj (у тонах) пункту призначення Вj.

Сумарні запаси Σ аі = 300+150+250=700 ,

сумарні потреби Σ bj=170+110+100+120+200=700.

Σ аі = Σ bj , запаси дорівнюють потребам, тобто це закрита модель транспортної

задачі.

Складемо математичну модель задачі. Нехай хіj – кількість одиниць продукту, що планується перевезти з пункту Аі до пункту Вj (це план перевезень). Тоді загальна вартість усіх перевезень буде : Z = Σ Σ Cij хij  ,  її необхідно мінімізувати.

Кількість одиниць продукту не може бути від’ємною, тому хіj ≥ 0.

З умови задачі випливає, що повинні виконуватись таки умови : Σ хij = аі , і =1,2,3 ,

тобто весь продукт з пунктів Аі  необхідно вивезти. Крім того потреби Вj повинні бути повністю задоволені, тобто  Σ хij = bj , j = 1,2,3,4,5.
                Таким чином, математична модель задачі має вигляд :

[pic 10]

Підставляємо конкретні значення: математична модель задачі має вигляд :

[pic 11]

        [pic 12]

Побудуємо початковий опорний план методом апроксімації Фогеля:

1) знаходимо для кожного рядка і стовпця різницю між двома найменшими тарифами і записуємо її відповідно справа від вибраного рядка і знизу під вибраним стовпчиком;

2) серед записаних чисел вибираємо найбільше і заповнюємо клітину з найменшим тарифом серед допустимих клітин у рядку чи стовпчику, для якого вибрано число;

3) викидаємо із розгляду (викреслюємо) рядок та стовпчик (або стовпчик), де вичерпано запаси чи потреби;

4) повертаємося до пункту 1 і виконуємо послідовність пунктів 1–3 до тих пір, поки не буде вичерпано всі запаси і потреби.

Знаходимо різниці по рядках.
Для рядка А1 перший мінімальний елемент = 15, другий мінімальний елемент = 50. Їх різниця рівна d = 35.
Для рядка А2 перший мінімальний елемент = 40, другий мінімальний елемент = 60. Їх різниця рівна d = 20.
Для рядка А3 перший мінімальний елемент = 10, другий мінімальний елемент = 11. Їх різниця рівна d = 1.
Знаходимо різниці по стовпцях.
Для стовпця В1 перший мінімальний елемент = 50, другий =70. Їх різниця d = 20.
Для стовпця В2  перший мінімальний елемент = 10, другий =50. Їх різниця d =40.
Для стовпця В3 перший мінімальний елемент = 15, другий = 40. Їх різниця d = 25.
Для стовпця В4 перший мінімальний елемент = 11, другий = 60. Їх різниця d = 49.
Для стовпця В5 перший мінімальний елемент = 25, другий =70. Їх різниця d = 45.
Обчисливши всі різниці, бачимо, що найбільша з них відповідає стовпцю В4. У цьому стовпці мінімальний тариф записаний у клітці, що перебуває на перетинанні рядка А3 і стовпця В4.  Таким чином, цю клітинку варто заповнити.