Пункт призначення Пункт відправлення | 1 | 2 | 3 | 4 | Запаси |
1 | 1 | 7 | 3 | 6 | 21 |
2 | 7 | 1 | 1 | 4 | 26 |
3 | 3 | 3 | 7 | 3 | 25 |
4 | 1 | 3 | 5 | 5 | 24 |
Потреби | 25 | 19 | 24 | 28 | S = 96 |
Допустимий план методом північно-західного кута
Сутність його полягає в наступному. Будемо розподіляти вантаж, починаючи з завантаження лівій верхній, умовно званої північно-західній, клітини (1; 1), рухаючись потім від неї по рядку вправо або за стовпцем вниз. У клітку (1; 1) занесемо менше з чисел a 1, b 1, тобто x 11 = min (a 1, b 1). Якщо а 1> b 1, то x 11 = b 1 і перший споживач У 1 буде повністю задоволений. Надалі 1-й стовпець таблиці в розрахунок не приймається, в ньому змінні. Рухаючись вправо по першому рядку таблиці, заносимо в сусідню клітину (1, 2) менше з чисел (a 1 - b 1) і b 2, тобто x 12 = min ((a 1 - b 1), b 2). Якщо (a 1 - b 1) <b 2, то запаси першого постачальника вичерпані і перший рядок таблиці надалі в розрахунок не приймається. Переходимо до аналогічного розподілу запасу вантажу другого постачальника. Якщо b 1> a 1 то х 11 = min (a 1, b 1) = а 1. При цьому запас першого постачальника буде вичерпано, а тому. Перший рядок з подальшого розгляду виключається. Переходимо до розподілу запасів другого постачальника. У клітку (2; 1) заносимо найменше з чисел (a 2, b 1 - а 1). Заповнивши таким чином клітину (1, 2) або (2; 1), переходимо до завантаження наступної клітини по другому рядку або за дві колонки. Процес розподілу по другій, третій і наступним рядкам (стовпцям) проводиться аналогічно розподілу по першому рядку або на одну колонку до тих пір, поки не вичерпаються ресурси.Ai * - надлишок нерозподіленого вантажу від постачальника Ai
Bj * - недостача в постачанні вантажу споживачеві Bj
Розміщуємо в клітку (1,1) менше з чисел A1 *= 21 і B1 *= 25
Так як запаси постачальника A1 вичерпані, то рядок 1 надалі в розрахунок не приймається
Розміщуємо в клітку (2,1) менше з чисел A2 *= 26 і B1 *= 4
Так як попит споживача B1 задоволений, то стовпець 1 надалі в розрахунок не приймається
Розміщуємо в клітку (2,2) менше з чисел A2 *= 22 і B2 *= 19
Так як попит споживача B2 задоволений, то стовпець 2 надалі в розрахунок не приймається
Розміщуємо в клітку (2,3) менше з чисел A2 *= 3 та B3 *= 24
Так як запаси постачальника A2 вичерпані, то рядок 2 надалі в розрахунок не приймається
Розміщуємо в клітку (3,3) менше з чисел A3 *= 25 і B3 *= 21
Так як попит споживача B3 задоволений, то стовпчик 3 надалі в розрахунок не приймається
Розміщуємо в клітку (3,4) менше з чисел A3 *= 4 і B4 *= 28
Так як запаси постачальника A3 вичерпані, то рядок 3 в подальшому в розрахунок не приймається
Розміщуємо в клітку (4,4) менше з чисел A4 *= 24 і B4 *= 24
Пункт призначення Пункт відправлення | 1 | 2 | 3 | 4 | Запаси |
1 | 1 21 | 7 - | 3 - | 6 - | 21 |
2 | 7 4 | 1 19 | 1 3 | 4 - | 26 |
3 | 3 - | 3 - | 7 21 | 3 4 | 25 |
4 | 1 - | 3 - | 5 - | 5 24 | 24 |
Потреби | 25 | 19 | 24 | 28 | S = 96 |
Допустимий план методом північно-західного кута
Алгоритм складається з двох кроків:
Попередній крок
Общеповторяющійся крок
Попередній крок:
Знаходимо допустимий ациклічний план.
Складаємо систему потенціалів.
Аналізуємо систему на потенційність.
Общеповторяющійся крок:
Позитивні різниці
Означіваем цикл.
Вибираємо найменше значення перевезення в клітинах негативною полуцепі.
З перевезень в кожній клітині негативною полуцепі віднімаємо Q, а до позитивних перевезення додається. Ця операція - зрушення по циклу на величину Q.
Перераховуємо систему потенціалів.
Перевіряємо систему на потенційність.
Якщо система не потенціальна, то переходимо до пункту 1 общеповторяющегося кроку.
Вважаючи потенціал U1 = 0, визначаємо інші потенціали зі співвідношення Ui + Vj = Ci, j (i = 1.. M, j = 1.. N), переглядаючи всі зайняті клітини.
Потенціали Ui, Vj:
U1 = 0 V1 = C1 ,1-U1 = 1 U2 = C1 ,2-V1 = 6 V2 = C2 ,2-U2 = - 5 V3 = C2 ,3-U2 = - 5 U3 = C3 ,3-V3 = 12 V4 = C3 ,4-U3 = - 9 U4 = C4 ,4-V4 = 14 Визначаємо значення оцінок Si, j = Ci, j-(Ui + Vj) для всіх вільних клітин S1, 2 = c1, 2 - (u1 + v2) = 12.
S1, 3 = c1, 3 - (u1 + v3) = 8.
S1, 4 = c1, 4 - (u1 + v4) = 15.
S2, 4 = c2, 4 - (u2 + v4) = 7.
S3, 1 = c3, 1 - (u3 + v1) = - 10.
S3, 2 = c3, 2 - (u3 + v2) = - 4.
S4, 1 = c4, 1 - (u4 + v1) = - 14.
S4, 2 = c4, 2 - (u4 + v2) = - 6.
S4, 3 = c4, 3 - (u4 + v3) = - 4.
B1 | B2 | B3 | B4 | |
A1 | 12 | 8 | 15 | |
A2 | 7 | |||
A3 | -10 | -4 | ||
A4 | -14 | -6 | -4 |
Для неї оцінка дорівнює - 14.
Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".
Постачальник | Споживач | Запаси вантажу | |||||||||||||||||||
B1 | B2 | B3 | B4 | ||||||||||||||||||
A1 |
|
|
|
| 21 | ||||||||||||||||
A2 |
|
|
|
| 26 | ||||||||||||||||
A3 |
|
|
|
| 25 | ||||||||||||||||
A4 |
|
|
|
| 24 | ||||||||||||||||
Потреба | 25 | 19 | 24 | 28 |
У результаті переміщення по циклу отримаємо новий план:
Постачальник | Споживач | Запаси вантажу | |||||||||||||||||||
B1 | B2 | B3 | B4 | ||||||||||||||||||
A1 |
|
|
|
| 21 | ||||||||||||||||
A2 |
|
|
|
| 26 | ||||||||||||||||
A3 |
|
|
|
| 25 | ||||||||||||||||
A4 |
|
|
|
| 24 | ||||||||||||||||
Потреба | 25 | 19 | 24 | 28 |
Значення цільової функції змінилося на 56 одиниць в порівнянні з попереднім етапом.
Етап 2
Вважаючи потенціал U1 = 0, визначаємо інші потенціали зі співвідношення Ui + Vj = Ci, j (i = 1.. M, j = 1.. N), переглядаючи всі зайняті клітини.
Потенціали Ui, Vj:
U1 = 0 V1 = C1 ,1-U1 = 1 U4 = C1 ,4-V1 = 0 V4 = C4 ,4-U4 = 5 U3 = C4 ,3-V4 = - 2 V3 = C3 ,3-U3 = 9 U2 = C3 ,2-V3 = - 8 V2 = C2 ,2-U2 = 9 Визначаємо значення оцінок Si, j = Ci, j-(Ui + Vj) для всіх вільних клітин
S1, 2 = c1, 2 - (u1 + v2) = - 2.
S1, 3 = c1, 3 - (u1 + v3) = - 6.
S1, 4 = c1, 4 - (u1 + v4) = 1.
S2, 1 = c2, 1 - (u2 + v1) = 14.
S2, 4 = c2, 4 - (u2 + v4) = 7.
S3, 1 = c3, 1 - (u3 + v1) = 4.
S3, 2 = c3, 2 - (u3 + v2) = - 4.
S4, 2 = c4, 2 - (u4 + v2) = - 6.
S4, 3 = c4, 3 - (u4 + v3) = - 4.
B1 | B2 | B3 | B4 | |
A1 | -2 | -6 | 1 | |
A2 | 14 | 7 | ||
A3 | 4 | -4 | ||
A4 | -6 | -4 |
Постачальник | Споживач | Запаси вантажу | |||||||||||||||||||
B1 | B2 | B3 | B4 | ||||||||||||||||||
A1 |
|
|
|
| 21 | ||||||||||||||||
A2 |
|
|
|
| 26 | ||||||||||||||||
A3 |
|
|
|
| 25 | ||||||||||||||||
A4 |
|
|
|
| 24 | ||||||||||||||||
Потреба | 25 | 19 | 24 | 28 |
Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".
Робимо зрушення по циклу на величину перевезень в 17 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус".
У результаті переміщення по циклу отримаємо новий план:
Постачальник | Споживач | Запаси вантажу | |||||||||||||||||||
B1 | B2 | B3 | B4 | ||||||||||||||||||
A1 |
|
|
|
| 21 | ||||||||||||||||
A2 |
|
|
|
| 26 | ||||||||||||||||
A3 |
|
|
|
| 25 | ||||||||||||||||
A4 |
|
|
|
| 24 | ||||||||||||||||
Потреба | 25 | 19 | 24 | 28 |
Значення цільової функції змінилося на 102 одиниць в порівнянні з попереднім етапом.
Етап 3
Вважаючи потенціал U1 = 0, визначаємо інші потенціали зі співвідношення Ui + Vj = Ci, j (i = 1.. M, j = 1.. N), переглядаючи всі зайняті клітини.
Потенціали Ui, Vj:
U1 = 0 V1 = C1 ,1-U1 = 1 V3 = C1 ,3-U1 = 3 U4 = C1 ,4-V1 = 0 U2 = C3 ,2-V3 = - 2 V2 = C2 ,2-U2 = 3 V4 = C4 ,4-U4 = 5 U3 = C4 ,3-V4 = - 2 Визначаємо значення оцінок Si, j = Ci, j-(Ui + Vj) для всіх вільних клітин
S1, 2 = c1, 2 - (u1 + v2) = 4.
S1, 4 = c1, 4 - (u1 + v4) = 1.
S2, 1 = c2, 1 - (u2 + v1) = 8.
S2, 4 = c2, 4 - (u2 + v4) = 1.
S3, 1 = c3, 1 - (u3 + v1) = 4.
S3, 2 = c3, 2 - (u3 + v2) = 2.
S3, 3 = c3, 3 - (u3 + v3) = 6.
S4, 2 = c4, 2 - (u4 + v2) = 0.
S4, 3 = c4, 3 - (u4 + v3) = 2.
B1 | B2 | B3 | B4 | |
A1 | 4 | 1 | ||
A2 | 8 | 1 | ||
A3 | 4 | 2 | 6 | |
A4 | 0 | 2 |
Транспортна задача вирішена.
Постачальник | Споживач | Запаси вантажу | |||||||||||||||||||
B1 | B2 | B3 | B4 | ||||||||||||||||||
A1 |
|
|
|
| 21 | ||||||||||||||||
A2 |
|
|
|
| 26 | ||||||||||||||||||
A3 |
|
|
|
| 25 | ||||||||||||||||
A4 |
|
|
|
| 24 | ||||||||||||||||
Потреба | 25 | 19 | 24 | 28 |
Метод мінімального елемента
1111 33333 квітні 1955 6777
Пункт призначення Пункт відправлення | 1 | 2 | 3 | 4 | Запаси |
1 | 1 21 | 7 - | 3 - | 6 - | 21 |
2 | 7 - | 1 19 | 1 7 | 4 - | 26 |
3 | 3 - | 3 - | 7 - | 3 25 | 25 |
4 | 1 4 | 3 - | 5 17 | 5 3 | 24 |
Потреби | 25 | 19 | 24 | 28 | S = 96 |
Розподільний метод
Розподільний метод являє собою набір таких дій: спочатку будується вихідний опорний план перевезень по одному з вищевикладених правил, а потім послідовно проводиться його поліпшення до отримання оптимального. Для цього для кожної вільної клітини будують замкнутий цикл. Якщо в матриці перевезень міститься опорний план, то для кожної вільної клітини можна утворити і до того ж лише один замкнутий цикл, у якому цю вільну клітину і деяку частину занятиx клітин.Тарифи в клітинах, що знаходяться в непарних вершинах циклу, беремо зі знаком плюс, а в парних - зі знаком мінус. За кожному циклу підраховуємо алгебраїчну суму S ij тарифів.
Якщо замкнутий цикл має вигляд: (i, j) -> (k, j) -> (k, l) -> (t, l) -> ... -> (U, v) -> (i, v), то S ij = C ij - C kj + C kl - C tl + ... + C uv - C iv, де (i, j) - вільна клітина.
Якщо алгебраїчна сума S ij негативна, то шляхом зміни значень, що стоять в клітинах замкнутого циклу, можна отримати план з меншим значенням цільової функції. Критерієм оптимальності при знаходженні мінімуму функції служить неотрицательности алгебраїчних сум S ij. Якщо зазначена вимога не дотримано, план не оптимальний і підлягає поліпшення.
Обчислення при вирішенні транспортної задачі розподільчим методом ведуться за наступним алгоритмом:
вихідні дані завдання розташовують у розподільній таблиці;
будують вихідний опорний план за правилом "північно-західного кута", або за правилом "мінімального елемента", або методом Фогеля; при цьому повинні виявитися зайнятими r = m + n-1 клітин. Однак, якщо опорний план є виродженим, то ця умова не дотримується. Для збереження числа зайнятих клітин r = m + n-1 незмінним проробляють наступні кроки: в таблиці відшукують клітку, що має мінімальний тариф і не утворить циклу з зайнятими клітинами, поміщають в неї базисний нуль і вважають її надалі зайнятою. Процес пошуку таких клітин триває до тих пір, поки число зайнятих клітин не стане рівним m + n-1;
роблять оцінку першої вільної клітини шляхом побудови замкнутого циклу і обчислення з цього циклу величини S ij. Якщо S ij <0, то переходять до наступного пункту алгоритму;
переміщують по циклу кількість вантажу, рівне найменшому з чисел, розміщених у парних клітинах циклу (у клітках зі знаком мінус). Далі повертаються до пункту с. Якщо S ij> = 0, то оцінюють наступну вільну клітину, і т.д., поки не виявлять клітку з негативною оцінкою. Серед всіх клітин з Оцінка менше нуля потрібно знайти клітину з найбільшим порушенням оптимальності, тобто клітку з найменшою оцінкою. Якщо, нарешті, оцінки всіх вільних клітин виявляться невід'ємними, то оптимальне рішення знайдено.
Пункт призначення Пункт відправлення | 1 | 2 | 3 | 4 | Запаси |
1 | 1 21 | 7 - | 3 - | 6 - | 21 |
2 | 7 - | 1 19 | 1 7 | 4 - | 26 |
3 | 3 - | 3 - | 7 - | 3 25 | 25 |
4 | 1 4 | 3 - | 5 17 | 5 3 | 24 |
Потреби | 25 | 19 | 24 | 28 | S = 96 |
найменша перевезення 17, робимо зрушення
Пункт призначення Пункт відправлення | 1 | 2 | 3 | 4 | Запаси |
1 | 1 4 | 7 - | 3 17 | 6 - | 21 |
2 | 7 - | 1 19 | 1 7 | 4 - | 26 |
3 | 3 - | 3 - | 7 - | 3 25 | 25 |
4 | 1 21 | 3 - | 5 - | 5 3 | 24 |
Потреби | 25 | 19 | 24 | 28 | S = 96 |
Оптимальний план вийшов розподільчим методом, аналогічний оптимальному плану, отримано методом потенціалів
Цей текст може містити помилки.
Програмування, комп'ютери, інформатика і кібернетика | Контрольна робота
Схожі роботи:
Рішення задач методом північно-західного кута рапределітельного мінімального і максимального
Рішення задач симплекс методом
Рішення прикладних задач методом дихотомії
Рішення задач лінійного програмування симплекс методом
Розвязання задач графічним методом методом потенціалів методом множників Лангранжа та симплекс-методом
Визначення поверхневого натягу методом максимального тиску в газовому бульбашці
Дослідження температурного поля зовнішнього кута методом електричного моделювання
Основні порти Північно-Західного федерального округу
Рекреаційний потенціал Північно-західного району Російської Федерації