Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Приклад




Розв’язати методом потенціалів транспортну задачу, умова якої надається таблицею 8.6.

Таблиця 8.6

  Пункти Споживачі   Запаси
B1 B2 B3 B4
A1          
A2          
A3          
Потреби          

Розв’язання

Початковий опорний план ТЗ, який отримано методом північно-західного кута, наведено в таблиці 8.7.

Таблиця 8.7

  Пункти Споживачі Запаси
B1 B2 B3 B4
A1          
A2          
A3          
Потреби          

Для визначення потенціалів ui, vj сформуємо відповідну систему рівнянь:

u1 + v1 = 2,

u1 + v2 = 5,

u2 + v2 = 4,

u2 + v3 = 5,

u3 + v3 = 3,

u3 + v4 = 4.

Покладемо в системі u1 = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v1 = 2, v2 = 5, v3 = 6, v4 = 7, u2 = -1, u3 = -3.

Занесемо отримані потенціали в таблицю 8.8.

Таблиця 8.8

  Пункти Споживачі   Запаси  
B1 B2 B3 B4
A1           u1 = 0
A2           u2 = -1
A3           u3 = -3
Потреби            
  v1 = 2 v2 = 5 v3 = 6 v4 = 7    

 

Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.8.

u1 + v3 = 6 3 –?

u1 + v4 = 7 1–?

u2 + v1 = 1 3,

u2 + v4 = 6 2 –?

u3 + v1 = -1 4,

u3 + v2 = 2 5.

З наведених нерівностей випливає, що умова оптимальності не виконується для клітинок (1.3), (1.4) і (2.4). Тому необхідно перейти до нового опорного плану.

Оберемо клітинку, для якої необхідно здійснити цикл перерахування. Для її вибору обчислимо

13 = (u1 + v3) – с 13 = 0 + 6 – 3 = 3,

14 = (u1 + v4) – с 14 = 0 + 7 – 1 = 6,

24 = (u2 + v4) – с 24 = –1 + 7 – 2 = 4.

max ij = 6.

Отже, цикл перерахування слід здійснити для клітинки (1.4). Виконання перерозподілу продукції в межах циклу можна оцінити з таблиці 8.9.

Таблиця 8.9

  Пункти Споживачі Запаси
B1 B2 B3 B4
A1   70 –   1 +  
A2   4 80 + 70 –    
A3     3 100 + 100 –  
Потреби          

При цьому в клітинки (1.4), (2.2) і (3.2) переноситься 70 одиниць продукції, а з клітинок (1.2), (2.3) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.10). Він є виродженим.

Таблиця 8.10

  Пункти Споживачі Запаси
B1 B2 B3 B4  
A1          
A2          
A3          
Потреби          

Оскільки план з таблиці 8.10 виявився виродженим здійснимо цикл перерахування для клітинки (2.4). Виконання перерозподілу продукції в межах циклу можна оцінити з наступної таблиці (табл. 8.11).

Таблиця 8.11

  Пункти Споживачі   Запаси
B1 B2 B3 B4
A1            
A2     70 – 2 +  
A3     100 + 100 –  
Потреби          

При цьому в клітинки (2.4) і (3.3) переноситься 70 одиниць продукції, а з клітинок (2.3) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.12).

Таблиця 8.12

  Пункти Споживачі Запаси  
B1 B2 B3 B4
A1           u1 = 0
A2           u2 = -1
A3           u3 = 1
Потреби            
  v1 = 2 v2 = 5 v3 = 2 v4 = 3    

 

Для визначення потенціалів ui, vj нового невиродженого плану сформуємо відповідну систему рівнянь:

u1 + v1 = 2,

u1 + v2 =5,

u2 + v2 = 4,

u2 + v4 = 2,

u3 + v3 = 3,

u3 + v4 = 4.

Покладемо в системі u1 = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v1 = 2, v2 = 5, v3 = 2, v4 = 3, u2 = -1, u3 = 1.

Занесемо отримані потенціали в таблицю 8.12. Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.12.

u1 + v3 = 2 3,

u1 + v4 = 3 1–?

u2 + v1 = 1 3,

u2 + v3 = 1 5,

u3 + v1 = 3 4,

u3 + v2 = 6 5–?

З наведених нерівностей випливає, що умова оптимальності не виконується для клітинок (1.4) і (3.2). Тому необхідно перейти до нового опорного плану.

Оберемо клітинку, для якої необхідно здійснити цикл перерахування. Для її вибору обчислимо

14 = (u1 + v4) – с 14 = 0 + 3 – 1 = 2,

32 = (u3 + v2) – с 32 = 1 + 5 – 5 = 1.

max ij = 2.

Отже, цикл перерахування слід здійснити для клітинки (1.4), але при цьому знов отримаємо вироджений опорний план ТЗ. Тому, здійснимо цикл перерахування для клітинки (3.2) (табл. 8.13).

Таблиця 8.13

  Пункти Споживачі Запаси
B1 B2 B3 B4
A1          
A2   80 –   70 +  
A3   5 +   30 –  
Потреби          

 

При цьому в клітинки (2.4) і (3.2) переноситься 30 одиниць продукції, а з клітинок (2.2) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.14).

Таблиця 8.14

  Пункти Споживачі Запаси  
B1 B2 B3 B4
A1           u1 = 0
A2           u2 = -1
A3           u3 = 0
Потреби            
  v1 = 2 v2 = 5 v3 = 3 v4 = 3    

 

Для визначення потенціалів ui, vj нового невиродженого плану сформуємо відповідну систему рівнянь:

u1 + v1 = 2,

u1 + v2 =5,

u2 + v2 = 4,

u2 + v4 = 2,

u3 + v2 = 5,

u3 + v3 = 3.

Покладемо в системі u1 = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v1 = 2, v2 = 5, v3 = 3, v4 = 3, u2 = -1, u3 = 0..

Занесемо отримані потенціали в таблицю (табл. 8.14).

Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.14

u1 + v3 = 2 3,

u1 + v4 = 3 1–?

u2 + v1 = 1 3,

u2 + v3 = 2 5,

u3 + v1 = 2 4,

u3 + v4 = 3 4.

З наведених нерівностей випливає, що умова оптимальності не виконується для клітинки (1.4). Тому необхідно перейти до нового опорного плану.

Таблиця 8.15

  Пункти Споживачі Запаси
B1 B2 B3 B4
A1   70 –   1 +  
A2   4 50 +   100 –  
A3          
Потреби          

 

При цьому в клітинки (1.4) і (2.2) переноситься 70 одиниць продукції, а з клітинок (1.2) і (3.4) така ж кількість продукції вилучається. З урахуванням цього новий план ТЗ матиме вигляд (табл. 8.16).

Таблиця 8.16

  Пункти Споживачі Запаси  
B1 B2 B3 B4
A1           u1 = 0
A2           u2 = 1
A3           u3 = 2
Потреби            
  v1 = 2 v2 = 3 v3 = 3 v4 = 1    

 

Для визначення потенціалів ui, vj нового невиродженого плану сформуємо відповідну систему рівнянь:

u1 + v1 = 2,

u1 + v4 =1,

u2 + v2 = 4,

u2 + v4 = 2,

u3 + v2 = 5,

u3 + v3 = 3.

Покладемо в системі u1 = 0, й отримаємо потенціали початкового опорного плану ТЗ. Вони рівні:

v1 = 2, v2 = 3, v3 = 3, v4 = 1, u2 = 1, u3 = 2.

Занесемо отримані потенціали в таблицю 8.16.Перевіримо виконання умов оптимальності для незаповнених клітинок таблиці 8.16

u1 + v2 = 3 5,

u1 + v3 = 3 3,

u2 + v1 = 3 3,

u2 + v3 = 4 5,

u3 + v1 = 4 4,

u3 + v4 = 3 4.

З наведених нерівностей випливає, що умова оптимальності виконується для клітинки всіх перевірених клітин. Отже, опорний план є оптимальним.

Таким чином,

Х* = (х 11 = 180; х 14 = 70; х 22 = 120; х 24 = 30; х 32 = 30; х 33 = 170).

При цьому

Fmin = 180*2 + 70*1 + 120*4 + 30*2 + 30*5 + 170*3 = 1630 одиниць вартості.





Поделиться с друзьями:


Дата добавления: 2015-09-20; Мы поможем в написании ваших работ!; просмотров: 447 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Наглость – это ругаться с преподавателем по поводу четверки, хотя перед экзаменом уверен, что не знаешь даже на два. © Неизвестно
==> читать все изречения...

2707 - | 2278 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.015 с.