Стисла теоретична довідка. Запорізький національний технічний університет

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Запорізький національний технічний університет

ЗАТВЕРДЖУЮ

Проректор з навчальної

роботи ЗНТУ

проф. __________ Коваль А.Д.

“_ 15 _”____ 11 ______ 2006 р.

КОМПЛЕКС

Навчально-методичного забезпечення дисципліни

“Дослідження операцій в транспортних системах”

Для студентів денної та заочної форм навчання

з напрямку 1004 “Транспортні технології”

Частина ІІ. Методичні вказівки до виконання практичних занять

Розділ 2. Транспортна задача лінійного програмування. Динамічне програмування. Теорія масового обслуговування.

Факультет: Транспортний

Кафедра: Транспортні технології

Комплекс навчально-методичного забезпечення дисципліни “Дослідження операцій в транспортних системах” для студентів денної та заочної форм навчання за напрямком 1004 “Транспортні технології” (частина ІІ, розділ 2)/ Склали: доц. Кузькін О.Ф., доц. Лащених О.А. – Запоріжжя: ЗНТУ, 2006.– 49 с.

Укладачі: доц., к.т.н. Кузькін О.Ф.

доц., к.т.н Лащених О.А.

Рецензент: проф., д.т.н. Бабушкін Г.Ф.

Відповідальний за випуск: ст. виклад. Каплуновська А.М.

Затверджено на засіданні

Ради Транспортного

факультету ЗНТУ

Протокол № _ 2 від “_ 08 __” ___ 11 ___ 2006 р.

ПРАКТИЧНЕ ЗАНЯТТЯ №6

ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ ЗА КРИТЕРІЄМ ВАРТОСТІ ПЕРЕВЕЗЕНЬ

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

Стисла теоретична довідка

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

Нехай є m пунктів зосередження вантажу (або пунктів виробництва) А ₁, А ₂, ..., А_m, в яких розміщено однорідний вантаж у кількості а ₁, а ₂, ..., а_m одиниць. Цей вантаж повинен бути доставлений у n пунктів споживання В ₁, В ₂,..., В_n з обсягом попиту відповідно b ₁, b ₂,..., b_n. Передбачається, що можливе транспортування з кожного пункту постачання до кожного пункту споживання. Задані транспортні витрати С_ij, пов’язані з доставкою одиниці вантажу з пунктів А_i до пунктів В_j (; ).

Задача полягає у складанні такого плану перевезень, який забезпечує виконання наступних умов:

1) запаси кожного постачальника повинні бути повністю вивезені;

2) попит всіх пунктів споживання повинен бути задовільнений за рахунок розподілу всього запасу вантажів, тобто

;

3) забезпечити мінімальні транспортні витрати.

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

Таблиця 6.1 – Умови транспортної задачі

Постачальники	Споживачі	Наявність вантажу
В 1	В 2	...	Вj	...	Вn
А 1	С 11	С 12	...	С 1j	...	С 1 n	а 1
А 2	С 21	С 22	...	С 2j	....	С 2 n	а 2
...	...	...	...	.....	...	...	...
Аi	Сi 1	Сi 2	...	Сij	...	Cin	ai
....	...	...	...	...	...	...	...
Am	Cm 1	Cm 2	...	Cm j	...	Cmn	am
Потреба в вантажах	b 1	b 2	...	bj	...	bn

Позначимо через x_ij кількість вантажу, який перевозиться з пункту постачання А_i до пункту споживання В_j. Тоді математична постановка задачі полягає у визначенні мінімального значення функції

,

при обмеженнях:

– по обсягам постачань

, ();

– по обсягам споживання

, ();

– на невід’ємність змінних задачі

, (; ).

Умови необхідні і достатні для розв’язання задачі визначаються балансом наявності вантажу та попиту на нього

.

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

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

Розв’язування транспортної задачі методом потенціалів включає наступні етапи:

1) складання базисного опорного плану перевезень;

2) перевірка отриманого плану на оптимальність;

3) поліпшення плану у випадку, коли він не є оптимальним, до отримання оптимального рішення.

Складання базисного опорного плану перевезень.

Для складання базисного опорного плану перевезень використовують декілька методів, зокрема: північно-західного кута, мінімального елементу в матриці, абсолютної подвійної переваги.

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

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

1) якщо а ₁ > b ₁, то х ₁₁ = b ₁;

2) якщо а ₁ < b ₁, то х ₁₁ = a ₁;

3) якщо а ₁ = b ₁, то х ₁₁ = a ₁.

У першому випадку всі інші поставки першого стовпчика припускаються рівними нулю: x_{i 1} = 0(i= 2 .. m).У другому – всі інші поставки першого рядка вважаються рівними нулю: x _{1 j}= 0(j= 2 .. n).У третьому випадку, якщо заповнюється наступна клітинка стовпчика нулем, то всі інші поставки першого рядка прирівнюються нулю, і, навпаки, якщо наступна клітинка рядка заповнюється нулем, то всі інші поставки першого стовпчика прирівнюються нулю. Наступну поставку заповнюємо у першому рядку, поклавши , якщо а ₁ > b ₁, а в другому рядку , якщо а ₁ < b ₁. Для менш імовірного випадку а ₁ = b ₁ заповнюємо наступну клітинку стовпчика або рядка нулем (x ₂₁ = 0 або x ₁₂ = 0). Така процедура продовжується доти, доки не будуть розподілені всі запаси постачальників споживачам. Загальна кількість N поставок (кількість заповнених клітинок) у опорному плані має дорівнювати . Якщо (опорний план є виродженим), необхідно ввести нульові поставки таким чином, щоб заповнені клітинки утворювали східчасту структуру.

Метод мінімального елемента в матриці. Алгоритм методу складається з таких операцій.

1. Пошук мінімального елемента у матриці транспортних витрат.

2. Визначення мінімального числа серед обсягів постачань і споживання x_ij = min{ а_і; b_j }для клітинки таблиці з мінімальним елементом С_ij.

3. Виключення з розгляду рядка або стовпчика:

і -го рядка, якщо a_i < b_j (x_ij = a_i);

j -го стовпчика, якщо a_i > b_j (x_ij = b_j).

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

4. З запасів і- го постачальника та потреб j- го споживача знімається визначений обсяг поставки.

Пункти 1–4 виконуються доти, доки не будуть отримані поставки.

Метод абсолютної подвійної переваги. Спочатку проглядаємо всі рядки матриці і в кожному з них відзначаємо елемент з мінімальним значенням транспортних витрат. Далі проглядаємо стовпчики матриці і також відзначаємо в них елементи з мінімальним значенням транспортних витрат. Клітинки, які мають подвійні позначки (**), заповнюються в першу чергу максимально можливими обсягами перевезень за правилами, розглянутим раніше. Після кожного призначення поставки x_ij виключаються з подальшого розгляду відповідні рядок або стовпчик. Далі заповнюються клітинки, що відзначені однією позначкою (*) і також після кожного призначення поставки виключається з подальшого розгляду відповідний рядок або стовпчик. Серед клітинок, що залишились без позначок, обсяги перевезень розподіляються за способом найменшого значення елементу С_ij.

Перевірка отриманого плану на оптимальність.

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

Позначимо потенціали рядків через U_i (i= 1 ..m), а потенціали стовпчиків через V_j (j= 1 ..n). Припустимий план при рішенні задачі на мінімум транспортних витрат буде оптимальним в тому і тільки в тому разі, якщо виконуються умови

Таким чином, для заповнених клітинок матриці складаються рівняння виду . Так як кількість заповнених клітинок дорівнює , то отримана система з невідомими потенціалами має рівнянь. Оскільки кількість невідомих перевищує на одиницю число рівнянь, то потенціалу будь-якого рядка U_i або стовпчика V_j можна надати будь-якого значення (наприклад, нульового), інші потенціали однозначно визначаються через нього.

Після обчислення потенціалів для вільних клітинок матриці обчислюються оцінки

.

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

Покращення плану перевезень.

Для покращення плану перевезень у випадку його не оптимальності необхідно виконати наступні дії:

1) знайти вільну клітинку з найменшим від’ємним значенням (якщо таких клітинок декілька, то можна взяти будь-яку з них). Ця клітинка називається перспективною та у наступному опорному плані перевезень у ній буде призначена поставка;

2) побудувати цикл перерахунку поставок. Циклом в таблиці транспортної задачі називається замкнена ламана лінія, вершини якої розташовані в зайнятих клітинках таблиці, а відрізки лінії – вздовж рядків і стовпчиків, причому один відрізок лінії кожної вершини знаходиться в рядку, а інший цієї ж вершини - в стовпчику. За першу клітинку циклу береться перспективна клітинка. Інші вершини циклу повинні знаходитися у заповнених клітинках. На рис. 6.1 показані деякі з можливих варіантів циклів транспортної задачі;

Рисунок 6.1 – Можливі варіанти циклів транспортної задачі

3) виконати перехід до нового опорного плану перевезень за наступними правилами:

а) всі вершини циклу по черзі позначаються знаками “ – “ і “ + ”, починаючи з перспективної клітинки, яка позначається знаком “ + ”;

б) в клітинках зі знаком “ – “ відшукується найменше значення поставки. Це значення поставки додається до поставок у клітинках, позначених знаком “ + ” і віднімається від поставок клітинок, позначених знаком “ – “.

Отриманий план знов перевіряється на оптимальність до отримання оптимального рішення задачі.