Вихідна інформація про часові параметри робіт, що використовуються для побудови графіка 3 страница

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

Існує низка методів відшукання опорних планів: методи по мінімальних параметрів «у рядку», «у стовпці», «у масиві»; метод різниці мінімальних параметрів у рядку і стовпці; найчастіше застосовується метод «північно-західного кута».

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

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

Питання для контролю знань:

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

2. Порядок формулювання задач лінійного програмування.

3. Методи оптимізації опорних планів транспортної задачі.

4. Математична постановка задачі

5. Елементи моделі математичного програмування

6. Загальна форма запису задач лінійного програмування

Лекція № 11. Методи рішення транспортної задачі

Мета лекції – вивчення основних методів складання і оптимізації базисного плану

Питання:

1. Складання базисного плану за методом «північно-західного кута»

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

3. Складання базисного плану за методом найменшого елемента

4 Оптимізація базисного плану

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

Під час складання базисного плану може бути використано один із нижченаведених методів:

1. метод північно-західного кута;

2. метод подвійної переваги;

3. метод найменшого елемента та ін.

1. Складання базисного плану за методом «північно-західного кута»

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

Таблиця 11.1

Дата добавления: 2014-11-06