Алгоритм розв'язання транспортної задачі методом потенціалів
ТРАНСПОРТНА Задача лінійного програмування
.1. Сутність транспортної задачі лінійного програмування
. . Алгоритм розв'язання транспортної задачі методом потенціалів
.3. Рішення транспортної задачі лінійного програмування за допомогою надбудови «Пошук рішення» в MS Excel
.4. Оптимізація завантаження виробничих потужностей підприємств з виробництва запасних частин для залізничного транспорту
.5. Початкові дані
.6. Послідовність рішення задачі
Оглавление
1. ТРАНСПОРТНА Задача лінійного програмування. 1
1.1. Сутність транспортної задачі лінійного програмування. 1
1.2. Алгоритм розв'язання транспортної задачі методом потенціалів. 3
Операція 2. Перевірка плану на оптимальність. 10
Операція 2.1. Розрахунок потенціалів. 10
Операція 3. Поліпшення плану. 12
Операція 3.1. Побудова ланцюга (контуру, циклу) перерозподілу поставок. 12
Операція 3.2. Перерозподіл поставок. 13
3.3. Рішення транспортної задачі лінійного програмування за допомогою надбудови «Пошук рішення» в MS Excel 16
Висновки. 20
Сутність транспортної задачі лінійного програмування
У різних місцях відправки є однорідний вантаж, який потрібно доставити в кілька пунктів призначення. Відомо, скільки вантажу відправляється з кожного пункту і скільки вантажу має надійти в пункт призначення. Причому байдуже, який саме відправник буде доставляти вантаж того чи іншого одержувачу. Потрібно так організувати перевезення, щоб забезпечити мінімальний загальний пробіг вантажу, т. Е. Мінімізувати витрати на транспортування. Економіко-математична модель транспортної задачі представляється зазвичай у вигляді транспортної таблиці або матриці.
|
|
|
Таблиця 1.1
Економіко-математична модель транспортної задачі
Примітка. А i - назва пункту відправлення; В j - назва пункту призначення; ai - виробнича потужність постачальників; bj - попит споживачів; m - число постачальників; n - число споживачів; i - номер рядка (i-й постачальник) i = 1 ... m; j - номер стовпця (j-й споживач) j = 1 ... n; cij - показник критерію оптимальності, питомі витрати на транспортування одиниці продукції (собівартість перевезень) від постачальника i до споживача j; xij - кількість продукції, що перевозиться від постачальника i до споживача j, план перевезень, розподіл поставок, кореспонденція вантажів.
Умови завдання в прийнятих позначеннях такі.
1.Кожен постачальник повинен дати рівно стільки продукції, стільки у нього є, т. Е. Сума поставок за кожним рядком повинна буде дорівнює потужності ai цього рядка:
. ( 1.1)
2. Кожен споживач повинен отримати рівно стільки продукції, скільки йому потрібно, тому що. Е. Сума поставок за кожним стовпчиком повинна буде дорівнює попиту bi цього шпальти:
|
|
|
. ( 1.2)
3.З вищенаведених умов ( 1.1) і ( 1.2) слід:
. ( 1.3)
У разі якщо 
, То транспортна задача лінійного програмування називається відкритою. якщо 
, То це незбалансована завдання з дефіцитом. якщо 
, То це незбалансована завдання з надлишком.
Щоб визначити сумарні витрати на перевезення, досить підсумувати твори обсягів кожної поставки на відповідні їм питомі витрати на транспортування. План буде оптимальним, якщо ця сума (цільова функція F) буде зведена до мінімуму:
. ( 1.4)
Транспортна задача є закритою, якщо дотримується умова ( 1.3). Якщо ця умова не дотримується, то для приведення відкритої транспортної задачі до закритого виду вводиться фіктивний споживач ФВ або фіктивний постачальник ФА. Різниця між виробничою потужністю і попитом відноситься на його рахунок. Витрати з доставки вантажу до фіктивного споживача або фіктивного постачальника дорівнюють нулю, так як вантаж практично не перевозиться.
Алгоритм розв'язання транспортної задачі методом потенціалів
Метод потенціалів відноситься до групи методів послідовного наближення. Спочатку відшукується вихідний допустимий план перевезень, який, як плавило, не є оптимальним, а потім за певною итеративной процедурі цей план доводиться до оптимального варіанту.
|
|
|
Для опису алгоритму використовуємо формульно-словесний спосіб. Розглянемо приклад транспортної задачі (табл. 1.2).
Таблиця 1.2
Вихідна транспортна матриця
У табл. 1.2 по рядках матриці представлені пункти (станції) відправлення від А1 до А4 і обсяги навантаження в тоннах - 100, 150, 90, 30 т, а по стовпцях - пункти (станції) призначення від В1 до В5 і обсяги вивантаження - 40, 80, 110, 50, 90 т. Дана транспортна задача є збалансованою (ai = bj = 370 т), тому додавати фіктивного споживача ФВ або фіктивного постачальника ФА не потрібно. На перетині рядків і стовпців в клітинах матриці в маленьких квадратиках записані показники критерію оптимальності транспортної задачі, наприклад, витрати на перевезення одиниці вантажу або найкоротші відстані між відповідними пунктами (станціями) навантаження і вивантаження. Відстань між станцією навантаження А1 і станцією вивантаження В1, як випливає з матриці, дорівнює 10 (або 100, 1000 і т. Д.) Км, потім - 9, 8, 5 км і т. Д. Тоді метою, рішення задачі з'явиться відшукання сукупності обсягів перевезень між усіма пунктами (станціями) навантаження і вивантаження (кореспонденцій), що забезпечує мінімальний обсяг перевізної роботи (вантажообігу) в тонно-кілометрах. Будь-яку сукупність кореспонденцій, що забезпечує весь обсяг перевезень, будемо називати планом, а сукупність, що забезпечує мінімум вантажообігу, - оптимальним планом перевезень.
|
|
|
Алгоритм розв'язання транспортної задачі лінійного програмування будемо описувати за операціями з присвоєнням номера та назви.
Операція 1. Побудова опорного плану.
Опорним, називається будь-який допустимий, як правило, не оптимальний план, який є вихідним для подальшого вирішення. Для побудови опорного плану існує ряд методів. Найпростіший з них - метод північно-західного кута (табл. 1.3).
Таблиця 1.3
Дата добавления: 2019-09-02; просмотров: 273; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!