Заняття 4 Рішення транспортної задачі лінійного програмування розподільчим методом.

Мета заняття – закріплення практичних навиків рішення транспортної задачі розподільчим методом.

Завдання. Скласти оптимальний план перевезень вантажів розподільним методом.

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

Вказівки до виконання

Завдання виконується у такій послідовності:

1. За даними табл. 3.1 скласти транспортну матрицю, вважаючи “i” – дорівнюється останній, а “j” – передостанній цифрі номеру залікової книжки.

2. Знайти оптимальний план транспортної задачі.

Побудувати вихідний припустимий план за допомогою одного із засобів (за вказівкою викладача): північно-західного куту, мінімального значення цільового елементу рядка або стовпця, методу апроксимації Фогеля.

3. Перевірити кількість завантажених клітин, яких повинно бути у кількості m+n-1=6+8-1=13. Якщо завантажених клітин менше, то треба додати нульові завантаження клітин.

4. Розрахувати допоміжні числа (потенціали) рядків і стовпчиків та ), використовуючи формулу

для завантажених клітин.

5. Знайти потенціали не завантажених клітин

.

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

Якщо є клітини для яких , то отриманий план не оптимальний, і від нього треба перейти до нового опорного плану.

5. Перерозподілити завантаження кліток.

Вибрати клітину, для якої виконується умова . Цю клітину треба додати до плану перевезень, а іншу вивести із плану. Для цього будують цикл та роблять перенос по циклу, перерозподіляють завантаження кліток і знов виконують перевірку нового плану на оптимальність. Процес буде тривати доки не буде знайдений оптимальний план. Після кожної ітерації визначити значення транспортної роботи.

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

1. Склад математичної моделі транспортної задачі лінійного програмування.

2. Методи розв'язання задач лінійного програмування.

3. Сутність і алгоритм розв'язання транспортної задачі лінійного програмування розподільчим методом.

4. Способи побудови початкового припустимого плану при розв'язуванні транспортної задачі розподільчим методом.

5. Перевірка припустимого плану на оптимальність.

6. Поліпшення неоптимального плану.

7. Основні типи транспортних задач, що вирішуються розподільчим методом.

8. Транспортна задача відкритого типу.

9. Визначення допоміжних чисел (потенціалів) рядків і стовпчиків матриці.

10. Перерозподіл завантаження кліток матриці. Побудова контуру.

11. Знаходження потенціальних не завантажених кліток.

ЛІТЕРАТУРА [1,2, 3, 5]