Транспортна задача

Транспортна задача. Знаходження початкового базисного розподілу поставок

1. Загальна постановка транспортної задачі

2. Знаходження опорного плану транспортної задачі.

1. Нехай із деяких M пунктів відправлення (постачальників) A1, A2, … , Am потрібно перевезти вантаж в N пунктів призначення (споживачів) B1, B2, … , Bn. Відомо, скільки вантажу маємо в кожному пункті відправлення і скільки потребується його в кожному пункті призначення. Відомі також витрати доставки одиниці вантажу від постачальника до споживача або відстань між пунктами перевезень. Необхідно визначити, яку кількість вантажу повинен направити постачальник тому або іншому споживачу, щоб загальні витрати на його транспортування (загальна кількість тонно-кілометрів) або час його доставки були мінімальними.

Для запису моделі транспортної задачі введемо такі позначення:

Аі – запаси вантажу у I-му пункті відправлення (I = 1,2,3,…, m);

Bj– потреба у вантажі у J –му пункті призначення (J = 1,2,3,…, n);

Хij – кількість одиниць вантажу, перевезеного від І–го пункту відправлення до J–го пункту призначення;

Сij – тарифи перевезення одиниці вантажу від І–го пункту відправлення до J–го пункту призначення.

Тоді математична постановка задачі зводиться до знаходження мінімального значення функції

(1)

При умовах

(2)

(3)

(4)

Оскільки змінні задовольняють системам лінійних рівнянь (2) і (3) і умовам невід’ємності (4), то забезпечується доставка необхідної кількості вантажу в кожний із пунктів призначення, вивезення наявного вантажу із всіх пунктів відправлення, а також не допускаються зворотні перевезення.

Означення. Будь – який невід’ємний розв’язок системи лінійних рівнянь (2) і (3), що визначається матрицею називається планом транспортної задачі.

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

Вхідні дані ТЗ записують у вигляді таблиці 1.

Таблиця 1.

Пункти відправлення	Пункти призначення	Запаси
B1	B2	B3	…	BN
А1	С11 Х11	С12 Х12	С13 Х13	…	С1N Х1N	A1
А2	С21 Х21	С22 Х22	С23 Х23	…	С2N Х2N	A2
А3	С31 Х31	С32 Х32	С33 Х33	…	С3N Х3N	A3
…	…	…	…	…	…	…
Аm	Сm1 Хm1	Сm2 Хm2	Сm3 Хm3	…	СMn ХmN	Am
Потреби	B1	B2	B3	…	Bn

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

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

(5)

То модель такої транспортної задачі називається Закритою. Якщо вказана умова не виконується, то модель транспортної задачі називається Відкритою.

Теорема. Для розрішимості транспортної задачі необхідно і достатньо, щоб запаси вантажу у пунктах відправлення дорівнювали потребам у вантажі у пунктах призначення, тобто, щоб виконувалась рівність (5).

У випадку, якщо запаси перевищують потреби, тобто , вводиться фіктивний (N+1)-й пункт призначення із потребою і відповідні тарифи вважаються рівними нулю: СIn+1=0 ( ). Отримана задача є транспортною задачею для якої виконується рівність (5).

Аналогічно при вводиться фіктивний (M+1)-й пункт відправлення із запасом вантажу і тарифи вважаються рівними нулю: СM+1J=0 ( ).

2. Знаходження опорного плану транспортної задачі.

Як і при розв’язанні задач ЛП симплексним методом, визначення оптимального плану ТЗ починається із знаходження якого – небудь її опорного плану. Для його побудови використовуються наступні методи:

1. північно – західного кута;

2. мінімальної вартості;

3. подвійної переваги.

Суть цих методів заключається в тому, що опорний план знаходять послідовно за N+M-1 Кроків, на кожному із яких в таблиці умови задачі заповнюють одну клітинку, яку називають Зайнятою. Заповнення однієї із клітинок забезпечує повністю або задоволення потреб у вантажі одного із пунктів призначення, або вивезення вантажу із одного із пунктів відправлення. У першому випадку тимчасово виключається із розгляду стовпчик, що містить заповнену на даному кроці клітинку, і розглядають задачу, таблиця умов якої містить на один стовпчик менше, ніж було перед цим кроком, але ту ж кількість рядків і відповідно змінені запаси вантажу у одному із пунктів відправлення. У другому випадку тимчасово виключається із розгляду рядок, що містить заповнену клітинку, і вважають, що таблиця умов має на один рядок менше і відповідних змінах потреб у вантажі у пункті призначення, стовпчик якого містить зайняту клітинку.

Після виконання N+M-2 Кроків отримують задачу із одним пунктом відправлення і одним пунктом призначення. При цьому залишиться вільною лише одна клітинка, а запаси пункту відправлення будуть дорівнювати потребам пункту відправлення що залишилися. Заповнивши цю клітинку (N+M-1-Й крок), отримують шуканий опорний план.

Метод північно –західного кута. При знаходженні опорного плану транспортної задачі методом північно – західного кута на кожному кроці розглядають перший пункт відправлення і перший пункт призначення із тих, що залишилися. Заповнення клітинок таблиці умов починається із лівої верхньої клітинки для невідомого Х11 (північно – західний кут) і закінчують для невідомого ХMn.

2. Термінологічний словник

Будь – який невід’ємний розв’язок системи лінійних рівнянь (2) і (3), що визначається матрицею називається Планом транспортної задачі.

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

3. Рекомендована література

1. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.

2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

3. Бугір М. К. Математика для економістів. Лінійна алгебра, лінійні моделі: Навч. посіб. — К.: ВЦ «Академія», 1998.

4. Гвоздинський А. М. Оптимізаційні задачі в організаційному управлінні: Навч. посіб.-Харків: ХДТУР, 1997.

Транспортна задача

Пункти відправлення

Потреби