Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Лекція №5 транспортна задача лінійного програмування






1. Постановка задачі.

Симплекс-метод вирішення ОЗЛП являється універсальним і може бути застосованим для рішення будь-яких задач такого типу. Однак існують деякі типи задач лінійного програмування, які допускають більш просте рішення. До таких задач відноситься транспортна задача.

Нехай є m пунктів відправлення (ПВ) A 1, A 2, … Am, в яких сконцентровані запаси певного однорідного вантажу в кількості, відповідно a 1, a 2, … am одиниць. Також є n пунктів призначення (ПП) B 1, B 2, … Bn з потребами у цьому вантажі, відповідно: b 1, b 2, … bn одиниць.

Припускається, що (транспортна задача є „закрита” або „збалансована”). Відома вартість cij перевезення одиниці вантажу від кожного пункту відправлення Ai до кожного пункту призначення Bj. Таблиця (матриця) вартості cij перевезень задана:

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

 

2. Формалізація задачі.

 

Введемо позначення:

xij – кількість вантажу, що відправляється з i -го пункту відправлення Ai в j -й пункт призначення Bj. Невід’ємні значення xij (кількість яких m × n) повинні задовольняти наступним умовам (обмеженням):

1) загальна кількість вантажу, що направляється з кожного пункту відправлення в усі пункти призначення, повинна дорівнювати запасу вантажу в цьому ПВ, тобто:

(1)

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

(2)

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

Функція L та обмеження (1) і (2) лінійні, так що це є типова задача лінійного програмування. Особливості транспортної задачі дозволяють вирішити її більш простим способом, ніж симплекс-методом:

1) всі коефіцієнти при змінних в обмеженнях (1) і (2) дорівнюють 1;

2) не всі з m + n є незалежними, оскільки , через що в транспортній задачі базисних змінних m + n– 1, а вільних mn – (m + n -1) = (m -1)(n -1).

 

3. Основні визначення.

1) значення xij одиниць вантажу, що направляється з пункту відправлення Ai в пункт призначення Bj будемо називати перевезенням.

2) будь-яку сукупність значень xij будемо називати планом перевезень.

3) план перевезень будемо називати допустимим, якщо він задовольняє балансовим умовам (1) і (2) – всі запаси вивезені, всі потреби задовільнено.

4) допустимий план перевезень будемо називати опорним, якщо в ньому ненульових перевезень (базисних змінних xij) r = m + n –1, а інші перевезення (змінні) дорівнюють нулю.

5) план перевезень будемо називати оптимальним, якщо він серед всіх допустимих планів призводить до найменшої загальної вартості перевезень.

 

4. Транспортна таблиця.

На відміну від симплекс-метода, вирішення транспортної задачі зводиться до більш простих операцій, які виконуються в таблиці, що називається транспортною (табл. 1). В такій таблиці в певному порядку записують умови транспортної задачі, в т.ч.:

1) пункти відправлення Ai та пункти призначення Bj. При цьому кожному з m рядків ставиться у відповідність певний ПВ Ai, а кожному стовпцю – певний ПП Bj;

2) запаси вантажу ai, що є в кожному пункті відправлення записуються в останньому стовпці;

3) потреби у вантажі bj, що є в кожному пункті призначення записуються в останній рядок;

4) вартість перевезення cij одиниці вантажу з кожного ПВ Ai в кожний ПП Bj записуються в верхньому лівому кутку клітини на перетині відповідних i -го рядка та j -го стовпця.

5) кількість одиниць вантажу xij, що перевозиться з ПВ Ai в ПП Bj записується у відповідній клітині у правому нижньому куті.

Таблиця 1

  B 1 B 2 ... Bj ... Bn Запаси ai
A 1 c 11 x 11 c 12 x 12   c 1 j x 1 j   c 1 n x 1 n a 1
A 2 c 21 x 21 c 22 x 22   c 2 j x 2 j   c 2 n x 2 n a 2
           
Ai ci 1 xi 1 ci 2 xi 2   cij xij   cin xin ai
           
Am cm 1 xm 1 cm 2 xm 2   cmj xmj   cmn xmn am
Потреби bj b 1 b 2 bj bn

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

Таким чином, рішення транспортної задачі зводиться до наступного: знайти такі невід’ємні значення перевезень (базисних змінних), які б задовольняли таким умовам:

1) сума перевезень по кожному рядку повинна дорівнювати запасу вантажу у даному пункті відправлення;

2) сума перевезень по кожному стовпцю повинна дорівнювати потребам відповідного пункту призначення;

3) загальна вартість усіх перевезень повинна бути мінімальною.

 

Транспортна таблиця з порушенням балансу.

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

1) транспортна задача з надлишком запасів: . В цьому випадку вводять фіктивний пункт призначення B ф (додатковий стовпець) з потребами: , вартість перевезення одиниці вантажу в фіктивний пункт призначення ci ф=0. Перевезення xi ф з Ai в B ф означає, що в пункті відправлення Ai залишились невикористані (невідправлені) запаси вантажу у кількості xi ф одиниць.

2) транспортна задача з надлишком потреб: . В цьому випадку вводять фіктивний пункт відправлення A ф (додатковий рядок) з запасами: , вартість перевезення одиниці вантажу з фіктивного пункту відправлення c ф j =0. Перевезення x ф j з A ф в Bj означає, що в пункті призначення Bj частина потреб у розмірі x ф j одиниць вантажу залишилась непокрита.

 

5. Знаходження опорного плану перевезень у транспортній таблиці.

 

Існує декілька методів знаходження опорного (початкового) плану перевезень:

1) північно-східного кута – застосовується частіше при виконанні розрахунків на ЕОМ;

2) метод найменшої вартості;

3) метод подвійної переваги – дозволяє отримати план перевезень досить близький до оптимального і скоротити обсяг розрахунків у порівнянні з методом північно-східного кута у середньому на 20-25%.

Суть вказаних методів у тому, щоб розподілити всі запаси вантажу і задовольнити всі потреби в ньому, при цьому кількість базисних (зайнятих) клітин має бути не більш, ніж r = m + n –1.

 


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал