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

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

скачати


Пункт

призначення

Пункт

відправлення

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) = c 1,2 - c 1,1 + c 4,1 - c 4,3 + c 2,3 - c 2,2 = 2 (1,3) = c 1,3 - c 1 , 1 + c 4,1 - c 4,3 = - 2 (1,4) = c 1,4 - c 1,1 + c 4,1 - c 4,4 = 1 (2,1) = c 2 , 1 - c 2,3 + c 4,3 - c 4,1 = 10 (2,4) = c 2,4 - c 2,3 + c 4,3 - c 4,4 = 3 (3,1 ) = c 3,1 - c 3,4 + c 4,4 - c 4,1 = 4 (3,2) = c 3,2 - c 3,4 + c 4,4 - c 4,3 + c 2,3 - c 2,2 = 0 (3,3) = c 3,3 - c 3,4 + c 4,4 - c 4,3 = 4 (4,2) = c 4,2 - c 4 , 3 + c 2,3 - c 2,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) = c 1,2 - c 1,3 + c 2,3 - c 2,2 = 4 (1,4) = c 1,4 - c 1,1 + c 4,1 - c 4 , 4 = 1 (2,1) = c 2,1 - c 2,3 + c 1,3 - c 1,1 = 8 (2,4) = c 2,4 - c 2,3 + c 1, 3 - c 1,1 + c 4,1 - c 4,4 = 1 (3,1) = c 3,1 - c 3,4 + c 4,4 - c 4,1 = 4 (3,2) = c 3,2 - c 3,4 + c 4,4 - c 4,1 + c 1,1 - c 1,3 + c 2,3 - c 2,2 = 2 (3,3) = c 3 , 3 - c 3,4 + c 4,4 - c 4,1 + c 1,1 - c 1,3 = 6 (4,2) = c 4,2 - c 4,1 + c 1,1 - c 1,3 + c 2,3 - c 2,2 = 0 (4,3) = c 4,3 - c 4,1 + c 1,1 - c 1,3 = 2

Оптимальний план вийшов розподільчим методом, аналогічний оптимальному плану, отримано методом потенціалів


Додати в блог або на сайт

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

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

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