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



Транспортна задача належить до типу розподільчих задач лінійного програмування. Економічний зміст таких задач може стосуватися різ­номанітних проблем, що переважно зовсім не пов’язано із перевезенням вантажів, як, наприклад, задачі оптимального розміщення виробництва, складів, оптимального призначення тощо.

Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у 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; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!