Операція 3.2. Перерозподіл поставок.
Перерозподіл поставок (див. Табл. 1.6) проводиться по ланцюгу. Спочатку визначимо обсяг перерозподілу поставок. Для цього дамо клітинам - вершин ланцюга - знаки. У небазисну клітку А2В4 ставимо «+», оскільки в неї буде вводитися поставка. Далі, чергуючи «+» з «-», розставляємо знаки по решті вершин контуру. Величина обсягу перерозподілу поставок приймається рівною мінімальної постачання в негативній клітці. Для нашого випадку це 50 одиниць вантажу. Перерозподіл полягає в тому, що до поставок в позитивних клітинах знайдений обсяг додається, а для негативних клітин віднімається. Результат представлений в табл. 1.6.
Функціонал F 'нового плану, представленого в табл. 1.6 (виділені поставки), становить 1950 ткм, що на 200 ткм менше значення функціоналу F попереднього плану.
Отриманий покращений план, представлений в табл. 1.6, в свою чергу, вимагає перевірки на оптимальність, тому необхідно повернутися до операції 2.
Сукупність дій, описаних в операціях 2 і 3, в процесі виконання завдання повторюється до тих пір, поки не буде отримано оптимальний план. Ця сукупність носить ітеративний (циклічний) характер, тому вона називається ітерацією. Через певний число ітерацій план стає оптимальним. Після цього здійснюється перехід від другої операції до четвертої (табл. 1.8).
Таблиця 1.8
Повторення операцій 2, 3
Від матриці до матриці вантажообіг (витрати на транспортування) повинні знижуватися. Якщо план не оптимальний, то необхідно провести повторний розрахунок потенціалів, перевірити небазисних клітини на відповідність умові оптимальності.
|
|
|
Покажемо подальше вирішення завдання, ґрунтуючись на даних табл. 1.6. Результат дій другої і третьої ітерацій наведено в табл. 1.8.
Перевірка плану на оптимальність свідчить про те, що для двох клітин умови оптимальності не виконуються. Після перерозподілу поставок по клітці А4В3, отримуємо новий план (табл. 1.9).
Таблиця 1.9
Оптимальний план поставок
Перевірка плану перевезень на оптимальність за умовою ( 1.8) показала, що для всіх небазисних клітин матриці умови оптимальності виконуються. Функціонал F '' оптимального плану дорівнює 1920 ткм. Таким чином, отриманий план перевезень, що забезпечує мінімальний обсяг перевізної роботи для транспортування всього вантажу між станціями навантаження і вивантаження.
Рішення транспортної задачі лінійного програмування за допомогою надбудови «Пошук рішення» в MS Excel
Розглянемо послідовність рішення попереднього прикладу надбудови «Пошук рішення» в MS Excel.
Спочатку вводяться вихідні дані (рис. 1.1).
|
|
|
Мал. 2.1. Початкові дані
Розрахунок обмежень транспортної задачі необхідно виконувати в нижчеподаній послідовності: в осередку стовпчика С15: С18 вводимо залежність за допомогою функції СУММ Майстра функцій. Для цього у відповідному діалоговому вікні вводимо адресу рядка. На рис. 1.2 представлений адреса для осередку С15. Аналогічні розрахунки слід виконати для всіх пунктів виробництва і споживання.
Мал. 1.2. Введення обмежувальних рівнянь
Потім в клітинку D12 вводимо цільову функцію (рис. 1.3), що представляє собою суму творів собівартості перевезення тонни вантажу на один кілометр і відповідно обсяг перевезень, умовно прийнятий за одиницю за всіма пунктами виробництва і споживання.
Мал. 1.3. Введення цільової функції
На наступному етапі запускаємо «Пошук рішення» і заповнюємо відповідні поля (рис. 1.4.). В поле з одиницями розташовуються змінювані осередки.
Слід пам'ятати, що при введенні обмежень повинні дотримуватися рівності вмісту осередків розрахованих сум зазначених в умові значенням (балансові обмеження транспортної задачі). Введені залежності повинні бути дорівнюють обсягу виробництва і споживання відповідно.
|
|
|
Мал. 1.4. Етап «Пошук рішення»
У вкладці «Параметри» відзначити «Лінійна модель» і «Ненегативне значення». Потім натиснути «Виконати» і зберегти отримане значення (рис. 1.5.).
Мал. 1.5. Результати етапу «Пошук рішення»
Як видно з рис. 1.5, функціонал (F = 1920 ткм), знайдений за допомогою методу потенціалів, збігається зі значенням цільової функції певної за допомогою надбудови «Пошук рішення» в MS Excel.
Висновки
1. Транспортні задачі - найбільш поширений клас задач лінійного програмування. їх використання в управлінських процесах пов'язано з визначенням такого плану перевезення вантажу від постачальників до споживачів, щоб загальні транспортні витрати були найменшими за умови, що мають бути задоволені потреби всіх споживачів.
2. Алгоритм розв'язування транспортної задачі має два етапи. На першому етапі цього алгоритму розташовано початковий опорний план транспортної задачі. Для його знаходження найчастіше використовуються методи північно-західного кута, мінімальної вартості, подвійної переваги тощо. На другому етапі розв'язання транспортної задачі методом потенціалів виконується перевірка знайденого опорного плану на оптимальність. Якщо план неоптимальний, то потрібно перерозподілити вантаж, зменшуючи вартість транспортування, і повернутися до першого етапу алгоритму, розглянувши наступний опорний план.
|
|
|
3. Транспортна задача може бути узагальнена на випадок "некла-сичної" постановки: трьохіндексна транспортна задача, трьохіндексна транспортна задача з різними видами вантажу, чотирьохіндексна транспортна задача тощо.
4. Транспортна задача за критерієм часу виникає при перевезенні термінових вантажів, коли загальна вартість перевезень має другорядне значення, а на перше місце виходить час. Вона не належить до задач лінійного програмування, оскільки її цільова функція не лінійна. Методика розв'язування цих задач базується на розвантажувальних циклах.
5. Багатокритеріальні постановки транспортної задачі є моделями транспортних задач з кількома критеріями якості, наприклад загальна вартість перевезення вантажу та загальний час перевезення. Ця задача зводиться до скалярної транспортної задачі за допомогою згортки критеріїв якості до одного критерію, після чого вона розв'язується стандартними методами.
Дата добавления: 2019-09-02; просмотров: 163; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!