Главная | Обратная связь | Поможем написать вашу работу!

Рекомендації щодо розв’язування

Слід зауважити, що в процесі побудови математичної моделі транспортної задачі можливо передбачати наступне:

– якщо не можна перевезти вантаж з і -го пункту до -го пункту призначення, то необхідно блокувати такий зв’язок, задаючи , де М – велике число;

– якщо треба обов’язково доставити вантаж з і -го пункту до -го, то необхідно значенню надати обов’язкового об’єму ресурсів, потім це значення відняти від відповідних значень , та і цим самим зробити нові початкові дані; після цього розв’язується нова транспортна задача, в якій для змінної з обов’язковим постачанням має місце ;

– якщо має місце умова , то вводиться додаткова -та колонка; при цьому , а потужність дорівнює ; тоді в -й колонці споживання ресурсів величина потужності дорівнює a_ij.

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

1. У будь-якому плані розподілу ресурсів має бути завжди баланс по кожному рядку та кожній колонці.

2. При переході від одного плану до іншого значення поліпшується на величину

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

3. Якщо кількість рівнянь потенціалів для дорівнює кількості змінних та , то цикл перерозподілу ресурсів побудовано невірно (особливо така помилка зустрічається тоді, коли будується вироджений цикл для невиродженого плану).

4. Під час коригування змінних циклу на величину хоча б одна із змінних має бути нульовою.

5. Якщо значення , та – цілі числа, то кожний побудований план розподілу ресурсів також цілочисловий.

6. Для будь-якого плану , де

7. Якщо одержано , то цикл перерозподілу побудовано невірно.

8. Якщо різниця між кількістю рівнянь потенціалів і змінними та дорівнює одиниці, тобто система не має розв’язку, то при побудові нового плану невірно перерозподілено ресурси.

Для зменшення обсягів і тривалості обчислень доцільно:

– у разі виродження плану вибирати фіктивну базисну змінну з мінімальним значенням з множини сполучних ;

– якщо є кілька , які не виконують умови оптимальності, з однаковим значенням , то вибирати для початку циклу доцільно таку , в якій величина мінімальна (оскільки ця змінна стає базисною);

– за наявності кількох варіантів побудови циклу вибирати такий, у якого вершини циклу з позначкою „-” мають максимальні значення ;

– при розв’язуванні системи рівнянь потенціалів доцільно надати нульового значення такому потенціалу, у колонці та рядку якого є з максимальним значенням .

Практично розв’язати транспортну задачу вручну важко і при відпрацьованих навичках можна розв’язати лише задачу розміром за 2-3 години. Задачі великих обсягів треба розв’язувати за допомогою ЕОМ, які мають стандартні програми для транспортної задачі.

Висновки

1. Транспортна задача є типовою задачею розподілу ресурсів між пунктами постачання та споживання.

2. Згідно з особливостями математичної моделі транспортної задачі розроблені спеціальні методи її розв’язування, які мають простіші алгоритми розв’язування, ніж симплексний метод.

3. При розв’язуванні транспортної задачі методом потенціалів використовують двоїсту теорію.

4. У випадку множини оптимальних розв’язків можна використовувати додаткові критерії за допомогою принципу послідовних критеріїв.

5. Розв’язок транспортної задачі завжди цілочисловий, якщо цілочисловими є початкові дані.

Контрольні запитання

1. Як обґрунтувати теоретичні умови оптимальності в методі потенціалів?

2. Що треба зробити, коли значення потенціалів визначаються неоднозначно?

3. В яких випадках транспортна задача має множину оптимальних розв’язків?

4. Що дає наявність множини оптимальних розв’язків транспортної задачі?

5. Як розв’язується відкрита транспортна задача?

6. Ознаки виродження транспортної задачі, як такі задачі розв’язуються?

⇐ Предыдущая 2 3 4 5 6 7 8 9 1011