Практична робота № 1. Оптимізація транспортних зв’язків між постачальникам та споживачами

Оптимізація транспортних зв’язків між постачальникам та споживачами

ЗАВДАННЯ: На підставі вихідних даних вирішити методом потенціалів транспортну задачу лінійного програмування.

Таблиця 1 – Вихідні дані до практичної роботи №1.

Варіант	i	j	А1	А2	В1	В2	1-1	1-2	2-1	2-2

Методичні вказівки.

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

1. На підставі таблиці вихідних даних (табл. 2) складається вихідна транспортна задача. При цьому використовуються наступні вихідні позначення:

і – кількість постачальників;

j – кількість споживачів;

А1 – можливості постачання першого постачальника;

А2 – можливості постачання другого постачальника;

В1 – потребі в матеріальних ресурсах першого споживача;

В2 – потребі в матеріальних ресурсах другого споживача;

1-1 – тариф перевезення від першого постачальника до першого споживача;

1-2 – тариф перевезення від першого постачальника до другого споживача;

2-1 – тариф перевезення від другого постачальника до першого споживача;

2-2 – тариф перевезення від другого постачальника до другого споживача.

Усі відсутні дані студент проставляє самостійно. При цьому величина тарифів перевезення від постачальників до споживачів повинна коливатися від 1 до 10.

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

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

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

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

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

6. Після того, як побудований контур оптимізації, можна робити перерозподіл постачань. Для цього на вершині контуру оптимізації в тій клітці, що повинна оптимізуватись (та, котра мала негативну оцінку) ставиться знак «+», а потім, переходячи послідовно до наступного вершинам (по годинній чи стрілці проти вартовий стрілки), знак поперемінно міняється на протилежний. Ті клітки, у яких вершини контуру мають знак «+», будуть одержувати додаткові постачання, а з кліток, у яких вершини контуру мають знак «мінус», постачання будуть вилучатися. Перерозподіл повинний вироблятися таким чином, щоб у його процесі віднімалося і додавалося те саме число. Необхідність дотримання даної вимоги зв'язана з тим, що після проведення перерозподілу в загальному плані повинний зберігатися баланс між можливостями окремих постачальників і потребами споживачів. При проведенні перерозподілу додавати і віднімати необхідно максимально можливе число. В окремих випадках, коли як заповнені клітки використовуються клітки з нульовими постачаннями, і на такі клітки випадає негативне значення вершини контуру, то в подібних випадках «0» переноситься в клітку (даний крок не поліпшує стан плану постачання, але дозволяє одержати оптимальне рішення – такий крок іноді називають «неодруженим кроком оптимізації»).

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

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

S =STij*Qij,

де Tij - тариф на перевезення одиниці матеріального ресурсу від i-го постачальника до j-му споживача;

Qij – обсяг постачання матеріальних ресурсів (вантажу) від i-го постачальника до j-му споживача.

Дата добавления: 2015-07-11