Економічна і математична постановка транспортної задачі.
Транспортна задача належить до типу розподільчих задач лінійного програмування. Економічний зміст таких задач може стосуватися різноманітних проблем, що переважно зовсім не пов’язано із перевезенням вантажів, як, наприклад, задачі оптимального розміщення виробництва, складів, оптимального призначення тощо.
Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників необхідно перевезти n споживачам. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного постачальника до кожного споживача. Необхідно визначити план перевезень, за якого вся продукція була б вивезена від постачальників, повністю задоволені потреби споживачів і загальна вартість всіх перевезень була б мінімальною.
Математична модель транспортної задачі. Позначимо через обсяг продукції, що перевозиться від постачальника до споживача . Тоді умови задачі зручно подати у вигляді такої таблиці:
Спож. | В1 | В2 | ... | Вn | |
Постач. | b1 | b2 | ... | bn | |
A1 | а1 | с11 x11 | с12 x12 | ... | с1n x1n |
A2 | а2 | с21 x21 | с22 x22 | … | с2n x2n |
… | … | … | … | … | … |
Am | аm | сm1 xm1 | сm2 xm2 | … | сmn xmn |
Мають виконуватися такі умови:
1)сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті
|
|
2)сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам:
3)сумарна вартість всіх перевезень повинна бути мінімальною:
Як впливає на оптимальний план введення нової змінної.
Опорний план транспортної задачі має містити не більше ніж (m + n – 1) відмінних від нуля компонент. Якщо їх кількість дорівнює (m + n – 1), то такий опорний план називають невиродженим. Якщо ж кількість додатних компонент менша ніж (m + n – 1), то опорний план є виродженим. Вироджений план може виникати не лише за побудови опорного плану, але і при його перетвореннях у процесі знаходження оптимального плану.
Найчастіше, щоб позбутися виродженості опорного плану, в деякі клітини таблиці транспортної задачі в необхідній кількості вводять нульові постачання. Обсяги запасів постачальників і потреби споживачів після цього не змінюються, однак клітини зі значенням «нуль» вважаються заповненими.
Головною умовою при введенні нульової поставки є збереження необхідної і достатньої умови опорності плану транспортної задачі — його ациклічності. Клітина має вибиратись у такий спосіб, щоб неможливо було побудувати замкнений цикл.
|
|
Тобто введення нової змінної впливає на оптимальний план позитивно.
Дата добавления: 2018-02-18; просмотров: 1654; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!