Тема 2. ОПТИМИЗАЦИЯ РЕШЕНИЙ НА ОСНОВЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Лекции 4-6. Учебные вопросы: 1. Однопродуктовая транспортная модель. 2. Базисные решения транспортной задачи. 3. Способ минимального элемента. 4. Приближённое решение транспортной задачи. 5. Алгоритм метода потенциалов. 6. Методология венгерского метода. 7. Несбалансированные транспортные модели. 8. Принципы балансирования транспортной задачи. 9. Инструментарий Excel «Поиск решения». 10. Многоэтапная транспортная модель. 11. Многоиндексная транспортная задача. 12. Оптимизация минимаксной транспортной задачи.

ПН 1 ПН 2 ПН 3 ПО 1 ПО 2 ПО 3 c 11 c 21 c 31 c 13 c 23 c 33 c 32 c 12 c 22 a1a1 a2a2 a3a3 b1b1 b2b2 b3b3 m = 3 n = 3 1. Однопродуктовая транспортная модель

Постановка задачи оптимизации В представленной модели осуществляется перевозка некоторого однотипного груза из m пунктов отправления (ПО) в n пунктов назначения (ПН). Запасы грузов в ПО и потребности ПН составляют соответственно – a i, i = 1, …, m; b j, j = 1, …, n. Транспортировка единицы груза из i-го ПО в j-й ПН оценивается величиной c ij, i = 1, …, m; j = 1, …, n. Введём обозначения: x ij – количество перевозимого груза из i-го ПО в j-й ПН, i = 1, …, m; j = 1, …, n; C – суммарная стоимость перевозки грузов из ПО в ПН. В рамках рассматриваемой модели представляется целесообразным найти такой план перевозок, при котором суммарная стоимость транспортирования всех грузов из ПО в ПН будет минимальной.

Формализация транспортной задачи Целевая функция Ограничения:

Понятия о решениях транспортной задачи Опорное решение – решение, удовлетворяющее части ограничений транспортной задачи. Допустимое решение – решение, удовлетворяющее всем ограничениям транспортной задачи. Базисное решение – решение, удовлетворяющее всем ограничениям транспортной задачи и содержащее не менее n × m – (m + n – 1) нулевых элементов в матрице перевозок. Оптимальное решение – решение, удовлетворяющее всем ограничениям транспортной задачи и минимизирующее значение целевой функции. Оптимальное решение – такое допустимое решение транспортной задачи, которое минимизирует значение целевой функции. Оптимальное решение – базисное решение транспортной задачи, минимизирующее значение целевой функции.

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj Базисные решения транспортной задачи

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj Способ северо-западного угла

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj 00 Способ северо-западного угла

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj 000 Способ северо-западного угла

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj Способ северо-западного угла C = = 6 × × × × × 25 = = 445

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj Способ минимального элемента

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj 020 Способ минимального элемента

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj 0205 Способ минимального элемента

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj 005 Способ минимального элемента

jiji ПН 1 ПН 2 ПН 3 aiai ПО ПО ПО bjbj Способ минимального элемента C = = 4 × × × × × 5 = = 245

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj Приближённое решение транспортной задачи

Способ Фогеля jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj 21

Способ Фогеля jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj 0200 vjvj 35

Способ Фогеля jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj 050 vjvj 3

Способ Фогеля jiji ПН 1 ПН 2 ПН 3 aiai ui1ui1 ПО ПО ПО bjbj vj1vj1 C = = 8 × × × × × 15 = = 235

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj Алгоритм метода потенциалов

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj 251 Метод потенциалов + -

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj 251 Метод потенциалов

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj Метод потенциалов

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj 143 Метод потенциалов C = 4 × × × × × 20 = 220

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj Методология венгерского метода

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj 032 Венгерский метод

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj +2 Венгерский метод

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj Венгерский метод

jiji ПН 1 ПН 2 ПН 3 aiai uiui ПО ПО ПО bjbj vjvj Венгерский метод

Целевая функция Ограничения: 7. Несбалансированные транспортные модели

Транспортная модель в условиях избытка Целевая функция Ограничения:

Целевая функция Ограничения: 8. Принципы балансирования транспортной задачи

9. Инструментарий Excel «Поиск решения»

Результаты решения задачи в Excel

ПН 1 ПН 2 ПН 4 ПО 1 ПО 2 ПО 3 c 11 c 21 c 31 s 13 s 23 s 24 c 32 c 12 c 22 a1a1 a2a2 a3a3 b1b1 b2b2 b4b4 m = 3 n = 4 ПН 3 ПП 1 ПП 2 s 14 s 12 s 22 s 11 s 21 d1d1 d2d2 p = 2 b3b3 10. Многоэтапная транспортная модель

Многоэтапная транспортная задача Целевая функция: В представленной модели осуществляется перевозка некоторого однотипного груза из m пунктов отправления в p промежуточных пунктов (склады, базы хранения), а затем из p промежуточных пунктов в n пунктов назначения. Запасы грузов в ПО, ёмкости ПП и потребности ПН составляют – a i, i = 1, …, m; d k, k = 1, …, p; b j, j = 1, …, n.

Ограничения:

Решение двухэтапной транспортной задачи в Excel

Целевая функция: 11. Многоиндексная транспортная задача В рассматриваемой задаче осуществляется перевозка некоторого однотипного груза из m пунктов отправления в n пунктов назначения на p типах транспортных средств (воздушном, морском, железнодорожном, автомобильном). Запасы грузов в ПО, потребности ПН и возможности ТС составляют – a i, i = 1, …, m; b j, j = 1, …, n; d k, k = 1, …, p.

Ограничения:

Пример решения задачи в Excel

Целевая функция: 12. Минимаксная транспортная задача В минимаксной транспортной задаче осуществляется перевозка однотипного груза с заданной матрицей времени следования ТС t ij, из m ПО в n ПН i = 1, …, m; j = 1, …, n. Запасы грузов в ПО и потребности ПН составляют соответственно – a i, i = 1, …, m; b j, j = 1, …, n. Критерием оптимизации здесь является минимум общего (не суммарного!) времени завершения всех перевозок.

Ограничения:

Пример решения задачи в Excel

1. Одной из задач линейного программирова- ния, имеющих большую область экономических приложений, является транспортная задача. 2. Для решения транспортной задачи имеются приближённые (Фогеля) и точные методы (рас- пределительный, потенциалов, венгерский). ЗАКЛЮЧЕНИЕ 3.Достаточно эффективным средством для решения задач транспортного типа является инструментарий Excel «Поиск решения».