Зіставлення методу потенціалів i симплекс-методу

Проiлюструємо зв’язок мiж методом потенцiалiв i симплекс-методом на
прикладi розв’язання такої задачi:

Будемо розв’язувати її паралельно методом потенцiалiв i симплекс-методом. Знайдемо початковий розв’язок методом північно-західного кута.

	v 1=5	v 2=10	v 3=18
u 1=0						–
u 2=-6						–
	-7
	–		–
			–

Записуємо задачу у вигляді системи:

min z=5x₁₁+10x₁₂+7x₁₃+6x₂₁+4x₂₂+12x₂₃ ;

x₁₁+ x₁₂+ x₁₃ =5; (5.21)

x₂₁ + x₂₂+ x₂₃=10; (5.22)

x₁₁ + x₂₁ =3; (5.23)

x₁₂ + x₂₂ =7; (5.24)

x₁₃ + x₂₃=5; (5.25)

x₁₁,x₁₂,x₁₃,x₂₁,x₂₂,x₂₃ ³0.

Вилучимо перше рівняння й зведемо систему до діагонального вигляду відносно змінних x ₁₁, x ₁₂, x ₂₂, x ₂₃:

min z=5x₁₁+10x₁₂+7x₁₃+6x₂₁+4x₂₂+12x₂₃;

x₁₁+ x₂₁ =3; (5.21a)

x₁₃ + x₂₃ =5; (5.22a)

-x₁₃ + x₂₁+ x₂₂ =5; (5.23a)

x₁₂+ x₁₃ - x₂₁ =2; (5.24a)

x₁₁,x₁₂,x₁₃,x₂₁,x₂₂,x₂₃ ³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дного кроку:

v 1=5

Ý v 2=10

v 3=18

БП

x 11

x 12

x 13

x 21

x 22

x 23

Р

u 1 =0

x 13

z

-7

–

Å

x 11

x 12

-1

u 2=-6

x 22

-1

-7

Å

–

x 23

Z=115

v 1=5

v 2=-1

v 3=7

БП

x 11

x 12

x 13

x 21

x 22

x 23

Р

u 1=0

z

-11

–

-11

Å

x 11

x 13

-1

u 2=5

x 21

x 22

Å

–

x 23

-1

5 ß

Z=93

v 1=5

V 2=3

v 3=7

БП

x 11

x 12

x 13

x 21

x 22

x 23

Р

u 1=0

0

z

-7

-4

-7

x 11

-1

x 13

u 2=1

x 22

-4

x 21

-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 днів дорівнює b₁, b₂,..., b_N і може бути задоволена трьома різними шляхами:

1) покупкою нових серветок за ціною p₁ центів;

2) пранням використаних серветок у пральні з терміном виконання 24 год за ціною p₂ центів;

3) пранням використаних серветок у пральні з терміном виконання 48 год за ціною p ₃ центів.

Сформулюйте цю задачу у вигляд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жними пунктами однаковий оптимальний розв’язок?