Рішення задач методом північно західного кута рапределітельного мінімального і максимального елемента

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Пункт
призначення
Пункт
відправлення
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
Вартість перевезень Z = 1 × 21 +4 × 7 +1 × 19 +1 × 3 +7 × 21 +3 × 4 +5 × 24 = 350
Допустимий план методом північно-західного кута
Алгоритм складається з двох кроків:
Попередній крок
Общеповторяющійся крок
Попередній крок:
Знаходимо допустимий ациклічний план.
Складаємо систему потенціалів.
Аналізуємо систему на потенційність.
Общеповторяющійся крок:
Позитивні різниці , Знаходимо найбільшу, включаємо цю клітку в набір і будуємо на ній цикл.
Означіваем цикл.
Вибираємо найменше значення перевезення в клітинах негативною полуцепі.
З перевезень в кожній клітині негативною полуцепі віднімаємо 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
Якщо є кілька кліток з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (4,1).
Для неї оцінка дорівнює - 14.
Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".


Постачальник
Споживач
Запаси вантажу
B1
B2
B3
B4
A1
1
21
7
3
6
21
A2
-
7
4
1
19
+
1
3
4
26
A3
3
3
-
7
21
+
3
4
25
A4
+
1
3
5
-
5
24
24
Потреба
25
19
24
28
Робимо зрушення по циклу на 4, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус".
У результаті переміщення по циклу отримаємо новий план:
Постачальник
Споживач
Запаси вантажу
B1
B2
B3
B4
A1
1
21
7
3
6
21
A2
7
1
19
1
7
4
26
A3
3
3
7
17
3
8
25
A4
1
4
3
5
5
20
24
Потреба
25
19
24
28
Вартість перевезень Z = 294
Значення цільової функції змінилося на 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
-
1
21
7
+
3
6
21
A2
7
1
19
1
7
4
26
A3
3
3
-
7
17
+
3
8
25
A4
+
1
4
3
5
-
5
20
24
Потреба
25
19
24
28
Якщо є кілька кліток з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (1,3). Для неї оцінка дорівнює - 6.
Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус".
Робимо зрушення по циклу на величину перевезень в 17 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус".
У результаті переміщення по циклу отримаємо новий план:
Постачальник
Споживач
Запаси вантажу
B1
B2
B3
B4
A1
1
4
7
3
17
6
21
A2
7
1
19
1
7
4
26
A3
3
3
7
3
25
25
A4
1
21
3
5
5
3
24
Потреба
25
19
24
28
Вартість перевезень Z = 192
Значення цільової функції змінилося на 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
Так як всі оцінки Si, j> = 0, то отриманий план є оптимальним.
Транспортна задача вирішена.
Постачальник
Споживач
Запаси вантажу
B1
B2
B3
B4
A1
1
4
7
3
17
6
21
A2
7
1
19
1
7
4
26
A3
3
3
7
3
25
25
A4
1
21
3
5
5
3
24
Потреба
25
19
24
28
Вартість перевезень F = 192
Метод мінімального елемента
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
Z = 1 × 22 +1 × 19 +1 × 7 +3 × 25 +1 × 4 +5 × 17 × 3 +5 = 226, у методі північно-західного кута вартість перевезення була вищою і становила 350.

Розподільний метод

Розподільний метод являє собою набір таких дій: спочатку будується вихідний опорний план перевезень по одному з вищевикладених правил, а потім послідовно проводиться його поліпшення до отримання оптимального. Для цього для кожної вільної клітини будують замкнутий цикл. Якщо в матриці перевезень міститься опорний план, то для кожної вільної клітини можна утворити і до того ж лише один замкнутий цикл, у якому цю вільну клітину і деяку частину заняти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
(1,2) = c1 ,2-c1, 1 + c4 ,1-c4, 3 + c2 ,3-c2, 2 = 2 (1,3) = c1 ,3-c1, 1 + c4 ,1-c4 , 3 = - 2 (1,4) = c1 ,4-c1, 1 + c4 ,1-c4, 4 = 1 (2,1) = c2 ,1-c2, 3 + c4 ,3-c4, 1 = 10 (2,4) = c2 ,4-c2, 3 + c4 ,3-c4, 4 = 3 (3,1) = c3 ,1-c3, 4 + c4 ,4-c4, 1 = 4 (3, 2) = c3 ,2-c3, 4 + c4 ,4-c4, 3 + c2 ,3-c2, 2 = 0 (3,3) = c3 ,3-c3, 4 + c4 ,4-c4, 3 = 4 (4,2) = c4 ,2-c4, 3 + c2 ,3-c2, 2 = - 2
найменша перевезення 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
(1,2) = c1 ,2-c1, 3 + c2 ,3-c2, 2 = 4 (1,4) = c1 ,4-c1, 1 + c4 ,1-c4, 4 = 1 (2,1 ) = c2 ,1-c2, 3 + c1 ,3-c1, 1 = 8 (2,4) = c2 ,4-c2, 3 + c1 ,3-c1, 1 + c4 ,1-c4, 4 = 1 (3,1) = c3 ,1-c3, 4 + c4 ,4-c4, 1 = 4 (3,2) = c3 ,2-c3, 4 + c4 ,4-c4, 1 + c1 ,1-c1 , 3 + c2 ,3-c2, 2 = 2 (3,3) = c3 ,3-c3, 4 + c4 ,4-c4, 1 + c1 ,1-c1, 3 = 6 (4,2) = c4 ,2-c4, 1 + c1 ,1-c1, 3 + c2 ,3-c2, 2 = 0 (4,3) = c4 ,3-c4, 1 + c1 ,1-c1, 3 = 2
Оптимальний план вийшов розподільчим методом, аналогічний оптимальному плану, отримано методом потенціалів
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Контрольна робота
149.5кб. | скачати


Схожі роботи:
Рішення задач методом північно-західного кута рапределітельного мінімального і максимального
Рішення задач симплекс методом
Рішення прикладних задач методом дихотомії
Рішення задач лінійного програмування симплекс методом
Розвязання задач графічним методом методом потенціалів методом множників Лангранжа та симплекс-методом
Визначення поверхневого натягу методом максимального тиску в газовому бульбашці
Дослідження температурного поля зовнішнього кута методом електричного моделювання
Основні порти Північно-Західного федерального округу
Рекреаційний потенціал Північно-західного району Російської Федерації
© Усі права захищені
написати до нас