Зіставлення методу потенціалів i симплекс-методу
Проiлюструємо зв’язок мiж методом потенцiалiв i симплекс-методом на
прикладi розв’язання такої задачi:
Будемо розв’язувати її паралельно методом потенцiалiв i симплекс-методом. Знайдемо початковий розв’язок методом північно-західного кута.
| v1=5 | v2=10 | v3=18 | |||||||
| u1=0 | – | ||||||||
| u2=-6 | – | ||||||||
| -7 | |||||||||
| – | – | ||||||||
| – |
Записуємо задачу у вигляді системи:
min z=5x11+10x12+7x13+6x21+4x22+12x23 ;
x11+ x12+ x13 =5; (5.21)
x21 + x22+ x23=10; (5.22)
x11 + x21 =3; (5.23)
x12 + x22 =7; (5.24)
x13 + x23=5; (5.25)
x11,x12,x13,x21,x22,x23 ³0.
Вилучимо перше рівняння й зведемо систему до діагонального вигляду відносно змінних x11,x12,x22,x23 :
min z=5x11+10x12+7x13+6x21+4x22+12x23;
x11+ x21 =3; (5.21a)
x13 + x23 =5; (5.22a)
-x13 + x21+ x22 =5; (5.23a)
x12+ x13 - x21 =2; (5.24a)
x11,x12,x13,x21,x22,x23 ³0.
Примітка:
(5.21a)=(5.23)
(5.22a)=(5.25)
(5.23a)=(5.22)—(5.25)
(5.24a)=(5.24)+(5.25)—(5.22)
Далi наводимо транспортну таблицю i симплекс-таблицю для вiдповiдного кроку:
 | v1=5 | Ýv2=10 | v3=18 | ||||||||||||||
 | БП | x11 | x12 | x13 | x21 | x22 | x23 | Р | |||||||||
   u1=0 | x13 | z | -7 | ||||||||||||||
 | – | Å | x11 | ||||||||||||||
 | x12 | -1 | |||||||||||||||
 u2=-6 | x22 | -1 | |||||||||||||||
| -7 | Å | – | x23 | ||||||||||||||
| Z=115 | |||||||||||||||||
 | v1=5 | v2=-1 | v3=7 | ||||||||||||||
 | БП | x11 | x12 | x13 | x21 | x22 | x23 | Р | |||||||||
 u1=0 | z | -11 | |||||||||||||||
  | – | -11 | Å | x11 | |||||||||||||
| x13 | -1 | ||||||||||||||||
 u2=5 | x21 | x22 | |||||||||||||||
  | Å | – | x23 | -1 | |||||||||||||
| 5 ß | Z=93 | ||||||||||||||||
| v1=5 | V2=3 | v3=7 | |||||||||||||||
| БП | x11 | x12 | x13 | x21 | x22 | x23 | Р | ||||||||||
| u1=0 | 0 | z | -7 | -4 | |||||||||||||
| -7 | x11 | -1 | |||||||||||||||
| x13 | |||||||||||||||||
| u2=1 | x22 | ||||||||||||||||
| -4 | x21 | -1 | |||||||||||||||
| Z=81 |
Як бачимо, між методом потенціалів та симплекс-методом існує взаємооднозначний зв’язок.
Задачi для самостійної роботи
Задача 1. Три нафтопереробні заводи з максимальним щоденним виробничим обсягом 6, 5 та 8 млн галонів бензину постачають три бензосховища, потреби яких складають 4, 8 та 7 млн галонів. Бензин транспортується до бензосховищ трубопроводом. Вартість перекачування бензину на одну милю, розрахована з урахуванням довжини трубопроводу, складає 1 цент на 100 галонів. У таблиці відстаней вказано, що завод 1 не зв’язаний зі сховищем 3. Сформулюйте відповідну транспортну задачу.
| бензосховища | ||||
| Заводи | ||||
| - | ||||
Задача 2. Розв’яжіть транспортну задачу методом потенціалів двічі: перший раз початковий розв’язок знайдiть методом північно-західного кута, другий – методом найменшої вартостi. Порівняйте їх.
Задача 3. Розв’яжіть транспортну задачу методом потенціалів двічі: перший раз початковий розв’язок знайдiть методом північно-західного кута, другий – методом найменшої вартостi. Порівняйте їх.
Задача 4. Розв’яжіть транспортну задачу методом потенціалів. Початковий розв’язок знайдіть методом північно-західного кута.
Задача 5. Розв’яжіть транспортну задачу методом потенціалів. Початковий розв’язок знайдiть методом найменшої вартостi.
Задача 6. Розв’яжіть транспортну задачу методом потенціалів та симплекс-методом, а також покажіть, що між ітераціями цих методів існує взаємооднозначна відповідність. Початковий розв’язок знайдiть методом північно-західного кута.
Задача 7. Розв’яжіть таку транспортну задачу:
Задача 8. Розв’яжіть транспортну задачу:
Задача 9. Розв’яжіть таку транспортну задачу:
Задача 10. Розгляньте оптимальну транспортну таблицю задачі 1 (табл. 5.9). У кожному з наведених випадків знайдіть зміни обсягу виробництва та попиту, за яких поточний розв’язок залишається допустимим.
1) вихідний пункт 1 – пункт призначення 1;
2) вихідний пункт 1 – пункт призначення 2;
3) вихідний пункт 2 – пункт призначення 2;
4) вихідний пункт 3 – пункт призначення 3.
Задача 11. Розв’яжiть задачу розподілу верстатів чотирьох різних типів за п'ятьма типами робіт. Нехай є 25, 30, 20 і 30 верстатів відповідних типів. П'ять типів робіт характеризуються 20, 15, 30, 10 і 25 операціями відповідно. На верстаті 4 не можна виконувати роботу 4. Виходячи з коефіцієнтів вартості операцій, наведених в таблиці, побудуйте модель оптимального розподілу верстатів за типами робіт.
| Тип верстатів | Тип робіт | ||||
| - |
Задача 12. У наведеній транспортній задачі сумарний попит переважає сумарний обсяг виробництва. Нехай штрафи за недопостачання одиниці продукції в пункти призначення 1, 2 і 3 дорівнюють 5, 3 і 2 відповідно. Знайдіть оптимальний розв’язок.
Задача 13. У деяких реальних умовах постановка транспортної задачi може ускладнюватися такими додатковими умовами:
а) з пункту 
в пункт 
перевезення здiйснити не можна;
б) з пункту виробництва в пункт споживання треба забезпечити перевезення точно 
одиниць продукцiї;
в) з пункту виробництва в пункт споживання треба завезти не менше ніж одиниць продукцiї;
г) з пункту виробництва в пункт споживання треба завезти не бiльше ніж одиниць продукцiї.
Для кожної з умов визначте, що треба зробити, щоб урахувати її при розв’язаннi транспортної задачi. Вiдповiдь подайте у виглядi транспортних таблиць.
Задача 14. У незбалансованій транспортній задачі призначається плата за зберігання кожної одиниці невивезеного товару з вихідного пункту й вантажу. Нехай коефіцієнти вартості зберігання вантажу у вихідних пунктах 1, 2 і 3 дорівнюють 5, 4 і 3 відповідно. Знайдіть оптимальний розв’язок, якщо весь обсяг вантажу вихідного пункту 2 має бути вивезений для того, щоб вивільнити місце для нової продукції.
Задача 15. Нехай у транспортній задачі розмірністю 3x3 через 
позначено кількість вантажу, що перевозиться з i в j, 
– коефіцієнт вартості відповідного перевезення. Обсяги виробництва у вихідних пунктах 1, 2 і 3 дорівнюють 15, 30 і 85 одиниць, а попит в пунктах призначення 1, 2 і 3 – 20, 30 і 80 одиниць. Припустимо, що початковий розв’язок, одержаний методом північно-західного кута, є оптимальним базисним розв’язком задачі. Відповідні значення потенціалів вихідних пунктів 1, 2 і 3 дорівнюють 2, 3 і 5, а значення потенціалів пунктів призначення 1, 2 і 3 – 2, 5 і 10.
1. Знайдіть сумарні транспортні видатки.
2. Вкажіть найменші значення 
для небазисних змінних, при яких розв’язок залишається оптимальним
Задача 16. Визначте початковий розв’язок транспортної задачі за допомогою
а) методу північно-західного кута; б) методу найменшої вартості; в) наближеного методу Фогеля. Знайдіть оптимальний розв’язок, виходячи з найкращого початкового розв’язку.
Задача 17. Повітряна лінія зв'язує два міста: А і В. Екіпаж, що формується в місті А (В) і вилітає у місто В (А), повинен здійснити зворотний рейс у місто А (В) в того самого або наступного дня. Екіпаж, що формується в А, можна призначити для зворотного рейсу в А за умови, якщо між часом прибуття у В і часом вильоту з В минуло не менше 90 хв. Задача полягає у складанні розкладу польотів, що мінімізує сумарний час простоїв усіх екіпажів. Розв’яжiть цю задачу про призначення, використовуючи такий розклад:
| Рейс | Виліт з А | Приліт в В | Рейс | Виліт з В | Приліт в А |
| 6:00 | 8:30 | 7:30 | 9:30 | ||
| 8:15 | 10:45 | 9:15 | 11:15 | ||
| 13:30 | 16:00 | 16:30 | 18:30 | ||
| 15:00 | 17:30 | 20:00 | 22:00 |
Задача 18. Знайдіть найкоротший шлях між вершинами 1 і 7 у мережі, зображеній на рис. 5.2, сформулювавши задачу з проміжними пунктами. Відстані між різними вершинами вказано на дугах мережі.
Рис. 5.2
Задача 19. Директор ресторану, складаючи план роботи на чергові N днів, повинен попіклуватися про щоденний запас чистих серветок. Потреба ресторану в серветках за ці N днів дорівнює b1, b2,..., bN і може бути задоволена трьома різними шляхами:
1) покупкою нових серветок за ціною p1 центів;
2) пранням використаних серветок у пральні з терміном виконання 24 год за ціною p2 центів;
3) пранням використаних серветок у пральні з терміном виконання 48 год за ціною p3 центів.
Сформулюйте цю задачу у виглядi транспортної.
Контрольнi запитання
1. Чи завжди можна збалансувати транспортну задачу?
2. Чи можуть для збалансування транспортної моделi одночасно бути потрiбнi як фiктивнi пункти виробництва, так i фiктивнi пункти споживання?
3. Який фiзичний змiст має кiлькiсть вантажу, що перевозиться з фiктивного пункту виробництва у пункти призначення?
4. Яка основна умова для застосування методу розв’язання транспортної задачі?
5. Зіставити кроки розв’язання транспортної задачi i симплекс-методу.
6. Чи будуть збігатися iтерацiї симплекс-методу i методу розв’язання транспортної задачі, якщо використовується однаковий початковий базисний розв’язок?
7. Чи вiдрiзняється принципово процедура побудови замкнених циклiв, що використовується для вибору змiнної, яка виводиться з базису, у методi розв’язання транспортної задачі вiд тiєї, що використовується з аналогiчною метою в симплекс-методi при перевiрцi умови допустимостi?
8. Що являють собою потенцiали, якщо знайти їм вiдповiдники у ЗЛП?
9. Чи може вплинути на вибiр змiнної, що вводиться у базис, довiльний вибiр значення одного з потенцiалiв на iтерацiї розв’язання транспортної задачi?
10. Чи змiняться оптимальнi значення 
, якщо до всiх коефiцiєнтiв 
додати одне й те саме число?
11. Чи може збалансована транспортна модель не мати допустимих розв’язкiв?
12. Чи вироджений будь-який базисний розв’язок задачi про призначення?
13. Чи можна розв’язати задачу про призначення методом, що використовується для розв’язання транспортної задачі?
14. Якщо у транспортнiй моделi являють собою найменший коефiцiєнт вартостi перевезень з початкового пункту i в пункт призначення j, то чи мають транспортна задача i вiдповiдна їй задача з промiжними пунктами однаковий оптимальний розв’язок?