Тема 3. Транспортна задача. Тема лекції: Транспортна задача

Лекція 7

Тема лекції: Транспортна задача

Мета: ознайомити студентів з основними теоремами та методами розв’язання транспортної задачі

План лекції

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

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

3. Метод північно-західного кута (діагональний).

4. Метод найменших витрат.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

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

Транспортна задача одна з найпоширеніших задач лінійного програмування. Її мета – розробка найбільш раціональних шляхів і способів транспортування однорідної продукції від постачальників до споживачів.

Транспортна задача – це специфічна задача лінійного програмування, яка застосовується для визначення найекономічнішого плану перевезення однорідної продукції від постачальників до споживачів.

У загальному вигляді транспортну задачу можна сформулювати так: в mпунктах постачання А12,…… Am (надалі постачальники) міститься однорідна продукція у кількості відповідно а1, а2,….. аm. Цю продукцію потрібно перевезти в n пункти призначення B1,B2,…… Bn (надалі споживачі) у кількості відповідно b1, b2,….. bn. Вартість перевезення одиниці товару (тариф) із пункту Аi в пункт Bj дорівнює сji.

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

F(xji)= ∑∑ xji сji min (1)

за умов

∑xji =ai (i=1,2…..m) (2)

∑xji =bj (j=1,2…..n) (3)

xji≥0 (i=1,2…..m; j=1,2…..n) (4)

Алгоритм і методи розв’язання транспортної задачі можна використати для знаходження розв’язку деяких економічних задач, які не мають нічого спільного з транспортуванням вантажів. У цьому разі величини тарифів перевезення сji мають різний зміст залежно від конкретної задачі. До таких задач належать наступні:

· Оптимальне закріплення за верстатами операцій з обробки деталей. У них сji означає продуктивність праці.

· Розміщення сільськогосподарських культур за ділянками землі різної врожайності.

· Оптимальні призначення або проблема вибору.

· Задача про скорочення виробництва із врахуванням загальних витрат на виготовлення і транспортування продукції

· Збільшення продуктивності автомобільного транспорту за рахунок мінімізації порожнього пробігу

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

Означення 1. Якщо у транспортної задачі виконується умова балансу

∑bj = ∑ai (5)

То задача називається закритою або збалансованою.

Означення 2. Планом транспортної задачі називається сукупність величин xji (i=1,2…..m; j=1,2…..n), який задовольняє умови обмеження (2) – (4).

Означення 3. Опорний план транспортної задачі називається не виродженим, якщо він містить N=m+n-1 додатних елементів xji

Означення 4. Якщо опорний план містить менше N<m+n-1 додатних елементів, то він називається виродженим.

Означення 5. Оптимальним планом транспортної задачі називають матрицю Х* , яка задовольняє умови задачі (2) – (4) і для якої цільова функція F набуває мінімального значення.

Теорема 1. (Необхідна і достатня умова існування розв’язку задачі ТЗ).

Транспортна задача має розв’язок тоді і тільки тоді, коли вона збалансована, тобто виконується умова (5).

Теорема 2. Для того щоб деякий план Х транспортної задачі був оптимальним необхідно і достатньо, щоб йому відповідала така система із m+n чисел ui (i=1,2…..m) vj ( j=1,2…..n) для якої виконуються умови

vj - ui = сji для xji>0

vj - ui ≤ сji для xji=0.

Означення 6. Числа vj та ui називаються потенціалами строк та стовпців.

3. Метод північно-західного кута (діагональний.)

Побудова опорного плану задачі починають із заповнення верхньої клітинки таблиці x11 , в яку записують менше з двох чисел a1 та b1.

Далі переходять до наступної клітинки в рядку або стовпчику і заповнюють ії і т.д. Закінчують заповнювати таблицю у правій нижній клітинці.

Зауважемо, що користуючись методом північно-західного кута початковий опорний план залежить від величин ai та bj і зовсім не залежить від вартостей перевезення сji, а тому він буде далекий від оптимального.

4. Метод найменшої вартості.

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

Приклад 1. Отримати початковий опорний план транспортної задачі методом північно-західного кута та методом найменшої вартості.

   
           
                   
           
                   
           
                   
             

Наши рекомендации