Опишіть економічну і математичну постановку класичної транспортної задачі.

Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників А_і в обсягах a1, a2…an одиниць відповідно необхідно перевезти n споживачам Bj в обсягах b1, b2…bn одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості cij перевезень одиниці продукції від кожного А_і -го постачальника до кожного В_j -го споживача, що подані як елементи матриці виду:

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

У такій постановці задачі ефективність плану перевезень визначається його вартістю і така задача має назву транспортної задачі за критерієм вартості перевезень.

Запишемо її математичну модель. Позначимо через xij обсяг продукції, що перевозиться від Aj постачальника до Bj споживача . Тоді умови задачі зручно подати у вигляді такої таблиці:

 

Мають виконуватися такі умови:

сумарний обсяг продукції, що вивозиться з кожного і -го пункту, має дорівнювати запасу продукції в даному пункті:

сумарний обсяг продукції, що ввезений кожному j -му споживачеві, має дорівнювати його потребам:

сумарна вартість всіх перевезень повинна бути мінімальною:

Очевидно, що .

.                                                            (5.5)

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

Домовимося планом транспортної задачі називати будь-який невід’ємний розв’язок системи обмежень (5.2)—(5.4), який позначають матрицею X=xij . Значення невідомих величин xij— обсяги продукції, що мають бути перевезені від i- х постачальників до j -х споживачів, називатимемо перевезеннями.

Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі, і для якої цільова функція (5.1) набирає найменшого значення.

Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевеpень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а1 та b1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.

Опорний план транспортної задачі, як зазначалося раніше, має містити не більше ніж (m + n – 1) відмінних від нуля компонент. Якщо їх кількість дорівнює (m + n – 1), то такий опорний план називають невиродженим. Якщо ж кількість додатних компонент менша ніж (m + n – 1), то опорний план є виродженим. Вироджений план може виникати не лише за побудови опорного плану, але і при його перетвореннях у процесі знаходження оптимального плану.

Найчастіше, щоб позбутися виродженості опорного плану, в деякі клітини таблиці транспортної задачі в необхідній кількос-ті вводять нульові постачання. Обсяги запасів постачальників і потреби споживачів після цього не змінюються, однак клітини зі значенням «нуль» вважаються заповненими.

33.як впливає на оптимальний план введення нової зміної

за допомогою додаткових змінних прямої задачі. Якщо

додаткова змінна в оптимальному плані дорівнює нулю, то відповідний ре-

сурс є дефіцитним, а якщо відмінна від нуля - ресурс недефіцитний.

Тому якщо додаткова

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

якщо uі 0, то відповідна продукція нерентабельна

Додаткові змінні двоїстої задачі розташовуються в індексному рядку

останньої симплекс-таблиці в стовпцях «А1»-«А4

Під впливом різних обставин ціна одиниці продукції на підприємстві

може змінюватися (збільшуватися або зменшуватися). Тому завжди цікаво

знати, в межах яких змін ціни продукції кожного виду оптимальний план її

виробництва залишається той же самий:

Для визначення інтервалів зміни коефіцієнтів цільової функції скорис-

таємося тим, що при цьому симплекс-таблиця, що відповідає оптимальному

плану, зберігає свій вигляд за винятком елементів індексного рядка. Нові

оцінки повинні задовольняти умові оптимальності задачі максиміза-

ції, тобто бути невід’ємними.