Шановні колеги!
Цілями даного уроку є не виклад теорії з курсу Матпрограмування, а простіша мета - показати практичне застосування знань, які Ви отримуєте в процесі вивчення розділу "математичне програмування" в курсі вищої математики. Тому виклад буде максимально простим, але не зовсім "канонічним".
транспортна задача
У чотирьох пунктах відправлення зосереджений однорідний вантаж в кількостях A = (90; 60; 70; 40), який необхідно доставити чотирьом споживачам з попитом B = (30; 50; 90; 90), витрати на транспортування одиниці вантажу наведені в матриці тарифів З :
2,4,5,1
3,7,6,2
1,3,4,2
4,5,2,6
Знайти оптимальний розподіл поставок і мінімальні транспортні витрати.
Рішення.
Початкова умова зведемо в таблицю:
Постачальники і їх ресурси
Споживачі і їх попит
Для вирішення завдання, на відміну від універсального симплекс-методу, використовуємо простіші, але наочні методи вирішення. Початковий план перевезень отримаємо методом Північно-Західного кута. Задовольнимо споживачів, дотримуючись черговості від лівого верхнього кута.
Постачальники і їх ресурси
Споживачі і їх попит
Як видно з початкового плану, поставки рівні потребам, тобто задача є "закритою" або збалансованою. Оцінимо початкові витрати на перевезення:
2 * 30 + 4 * 50 + 5 * 10 + 6 * 60 + 4 * 20 + 2 * 50 + 6 * 40 = 1090
Оцінимо оптимальність обраного плану за допомогою методу потенціалів. Для цього введемо дві додаткові колонки - alpha і beta. Приймаємо перший рядок рівною нулю. Виходячи з цього розраховуємо всі інші значення (див. Таблицю).
Принцип розрахунку грунтується на тому, що beta [j] - alpha [i] = C [i, j] тобто різниця значень додаткових рядки і колонки дорівнює витратам (вартості) перевезення. Оскільки рядок 1 ми взяли рівною нулю, то beta [j] - 2 = 0, звідки значення для першої колонки дорівнює 2.
Постачальники і їх ресурси
Споживачі і їх попит
Тепер визначимо потенціал кожної клітини, яка не брала участі в початковому плані, використовуючи ту ж саму формулу beta [j] - alpha [i] = C [i, j]. Однак, що виходить число у нас буде так само "псевдостоімость" перевезення. Обчислимо значення beta [j] - alpha [i] - C [i, j]. Різниця занесемо в нижній лівий кут клітки. Отримаємо наступну таблицю:
Постачальники і їх ресурси
Споживачі і їх попит
Тепер вибираємо опорну клітку. Найменше значення має клітина (4, 3) - різниця потенціалів -6. Ми включаємо її в новий план. Відповідно, необхідно провести коригування по стовпцю і рядку з іншими клітинами, вже знаходяться в плані. Природно, коригування повинна зберігати баланс обсягів перевезень - ресурсів по рядку повинно бути не більше, ніж їх є на складі, а по стовпчику не більш, ніж їх необхідно в пункті призначення.
Постачальники і їх ресурси
Споживачі і їх попит
Витрати на перевезення за даним планом складуть 2 * 30 + 4 * 50 + 5 * 10 + 6 * 60 + 2 * 20 + 2 * 70 + 6 * 20 = 970. Як видно, план став більш оптимальним, в порівнянні з початковою. Застосуємо метод потенціалів для нового плану. Отримаємо таблицю:
Постачальники і їх ресурси
Споживачі і їх попит
Тепер знову визначимо потенціал кожної клітини, яка не брала участі в плані, використовуючи формулу beta [j] - alpha [i] = C [i, j]. Обчислимо значення beta [j] - alpha [i] - C [i, j]. Різниця занесемо в нижній лівий кут клітки. Відразу ж визначаємо опорну клітку. Отримаємо наступну таблицю:
Постачальники і їх ресурси
Споживачі і їх попит
Витрати на перевезення за даним планом складуть 2 * 30 + 4 * 50 + 6 * 60 + 2 * 30 + 1 * 10 + 2 * 70 + 6 * 10 = 890. Як видно, план став більш оптимальним, в порівнянні з початковою. Застосуємо метод потенціалів для нового плану.
Постачальники і їх ресурси
Споживачі і їх попит
Витрати на перевезення за даним планом складуть 2 * 30 + 4 * 50 + 6 * 50 + 2 * 40 + 1 * 10 + 2 * 10 + 2 * 70 = 810. Як видно, план став більш оптимальним, в порівнянні з початковою. Застосуємо метод потенціалів для нового плану.
Постачальники і їх ресурси
Споживачі і їх попит
Витрати на перевезення за даним планом складуть 1 * 30 + 4 * 50 + 6 * 50 + 2 * 40 + 1 * 40 + 2 * 10 + 2 * 40 = 750. Застосуємо метод потенціалів для наступного плану.
Постачальники і їх ресурси
Споживачі і їх попит
Витрати на перевезення за даним планом складуть 1 * 30 + 4 * 10 + 3 * 40 + 6 * 50 + 2 * 40 + 1 * 80 + 2 * 10 = 670. Застосуємо метод потенціалів для наступного плану.
Постачальники і їх ресурси
Споживачі і їх попит
Витрати на перевезення за даним планом складуть 2 * 10 + 1 * 20 + 3 * 50 + 6 * 50 + 2 * 40 + 1 * 80 + 2 * 10 = 670. Застосуємо метод потенціалів для наступного плану.
Постачальники і їх ресурси
Споживачі і їх попит
Оскільки всі обчислені відносні потенціали більше нуля (різниця потенціалів негативна), то план є оптимальним.
Відповідь.
10,0,0,80
0,0,50,10
20,50,0,0
0,0,40,0.
Витрати на перевезення 670.
Натисніть, щоб рекомендувати цю сторінку іншим: