Короткі теоретичні відомості. 1. Постановка транспортної задачі

Практичне заняття №6

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

Завдання до теми

1. Постановка транспортної задачі.

2. Методи визначення початкових опорних планів: північно-західного кута, мінімального елемента.

3. Знаходження оптимального розв´язання транспортної задачі методом потенціалів.

4. Економічний аналіз отриманого оптимального розв´язання транспортної задачі.

1. Постановка транспортної задачі (Т 3).

2. Математична модель Т 3.

3. Умова збалансованості Т 3.

4. Зв'язок Т.3. із задачею лінійного програмування (3 Л П).

5. Визначення розв’язання (плану) Т 3.

6. Умова можливості розв'язання Т 3.

7. Визначення опорного плану Т 3.

8. Виродженість і невиродженість опорного плану.

9. Зв'язок виродженості й невиродженості опорного плану Т3 із заповнюванням таблиці Т 3.

10. Визначення циклу в таблиці Т 3.

11. Зв'язок опорного плану Т 3 з циклічністю.

12. Метод північно-західного кута для визначення початкового опорного плану.

13. Метод мінімального елемента.

14. Метод Фогеля.

15. Суть методу потенціалів.

16. Вимоги до опорності плану при застосуванні методу потенціалів.

Література: [5, с. 192 – 235; 6, с.125 – 155;10, с. 7 – 32].

Тема. Розв´язання задачі про призначення

Мета: навчитися розв´язувати задачу про призначення та проводити економічний аналіз отриманих результатів.

Математична модель задачі про призначення має вигляд:

Функція мети min (max).

Система граничних умов: (18)

, якщо i - й ресурс призначений на виконання j − ой роботи; 0 − інакше.

Для розв`язку задачі про призначення застосовується угорський метод.

Незалежним нулем будемо називати єдиний вибраний нуль у рядку та стовпці матриці витрат С, на перетині яких він знаходиться. Якщо, крім вибраного незалежного нуля, в рядку або стовпці присутні ще нулі, то їх далі необхідно вважати залежними. Незалежний нуль на місці (i, j) є призначенням і – го завдання на виконання j-м ресурсом.

Фактично наведений метод розв`язку зводиться до перетворень рядків і стовпців за допомогою деяких констант доти, поки достатнє число коефіцієнтів Cij не обернеться на нуль, що дасть шуканий результат.

Дата добавления: 2015-05-23