Транспортная Задача Линейного Программирования в Excel • Условие задачи

Пример решения транспортной задачи методом потенциалов

Пример подробного решения транспортной задачи методом потенциалов. В задаче с неправильным балансом, открытая модель приводится к закрытой. Первый опорный план строится методом наименьшей стоимости. Задача решается методом потенциалов. Рассмотрена проблема зацикливания при вырожденном плане. Задача имеет не единственное решение. Приводятся несколько альтернативных опорных планов.

Условие задачи

Требуется составить такой план перевозок, при котором суммарные затраты на перевозки будут минимальны. То есть нужно найти матрицу перевозок X , каждый элемент которой равен количеству груза , которое нужно перевезти со склада поставщика на склад потребителя .

Указание. Первый опорный план составить методом наименьшей стоимости.

Решение задачи методом потенциалов

1. Приведение задачи к закрытому типу

2. Составление первого опорного плана методом наименьшей стоимости

Составляем первый опорный план методом наименьшей стоимости. Фиктивного потребителя Φ заполняем в последнюю очередь. Наименьшая стоимость 1 в клетке (2, 3). Даем в нее наибольшую поставку 7. Потребитель B3 получил требуемое количество груза: b3 = 7. Вычеркиваем столбец B3.

Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (1, 1). Даем в нее наибольшую поставку 15. Поставщик A1 реализовал весь имеющийся у него груз: a1 = 15. Вычеркиваем строку A1.

Среди не зачеркнутых клеток, наименьшая стоимость 2 в клетке (2, 2). Даем в нее наибольшую поставку 2. Поставщик A2 реализовал весь имеющийся у него груз: a2 = 2 + 7 = 9. Вычеркиваем строку A2.

Среди не зачеркнутых клеток, наименьшая стоимость 3 в клетке (3, 1). Даем в нее наибольшую поставку 6. Потребитель B1 получил требуемое количество груза: b1 = 15 + 6 = 21. Вычеркиваем столбец B1.

Среди не зачеркнутых клеток, наименьшая стоимость 5 в клетке (3, 4). Даем в нее наибольшую поставку 6. Потребитель B4 получил требуемое количество груза: b4 = 6. Вычеркиваем столбец B4.

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (3, 2). Даем в нее наибольшую поставку 1. Поставщик A3 реализовал весь имеющийся у него груз: a3 = 6 + 1 + 6 = 13. Вычеркиваем строку A3.

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (4, 2). Даем в нее наибольшую поставку 8. Поставщик A4 реализовал весь имеющийся у него груз: a4 = 8. Вычеркиваем строку A4.

Среди не зачеркнутых клеток, наименьшая стоимость 6 в клетке (5, 2). Даем в нее наибольшую поставку 4. Потребитель B2 получил требуемое количество груза: b2 = 2 + 1 + 8 + 4 = 15. Вычеркиваем столбец B2.

Даем наибольшую поставку 5 в оставшуюся не зачеркнутую клетку (5, 5). Получаем первый опорный план.

Найдем значение целевой функции F 1 для первого опорного плана. Она равна сумме всех затрат на перевозки. Умножим стоимость перевозки единицы груза на количество перевезенного груза , и просуммируем по всем клеткам:

.

Наша дальнейшая задача заключается в нахождении такого плана X перевозок, то есть таких значений переменных , при котором целевая функция имеет наименьшее значение:
.

3. Построение оптимального плана

3.1. Шаг 1

Наименьшая оценка Δ3,3 = -3 в клетке (3,3). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 1.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (3,3).

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 1 в клетке (3,2). Выполняем сдвиг по циклу на величину 1: в клетках, помеченных знаком ′+′, прибавляем 1; в клетках, помеченных знаком ′–′, вычитаем 1. В результате клетка (3,3) входит в базис со значением 1, а клетка (3,2) выходит из базиса.
Получаем таблицу 2.1.

Целевая функция:
F2 = 2·15 + 2·3 + 1·6 + 3·6 + 2·1 + 5·6 + 6·8 + 6·4 + 0·5 = 164
Мы видим, что целевая функция стала меньше. Изменение целевой функции:
.
Оно равно произведению оценки клетки (3,3) , которую мы ввели в базис, на поставку в эту клетку:
.

3.2. Шаг 2. Переход к вырожденному плану

Наименьшие оценки Δ4,1 = Δ5,1 = -3 в клетках (4,1), (5,1). Мы можем ввести в базис любую из них. Вводим в базис клетку (4,1). Строим цикл для этой клетки. Изображаем его в таблице 2.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (4,1).

Мы видим, что одна из базисных переменных равна нулю: . Такой план, в котором одна или несколько базисных переменных равны нулю называют вырожденным планом.

Целевая функция:
F3 = 2·15 + 2·9 + 1·0 + 2·7 + 5·6 + 3·6 + 6·2 + 6·4 + 0·5 = 146
Она стала еще меньше. Изменение целевой функции:
.
Оно равно произведению оценки клетки (4,1) , которую мы ввели в базис, на поставку в эту клетку:
.

3.3. Шаг 3

Наименьшая оценка Δ1,4 = -4 в клетке (1,4). Вводим ее в базис. Строим цикл для этой клетки. Изображаем его в таблице 3.3. Расставляем знаки ′+′ и ′–′ в вершинах цикла, чередуя их, начиная со знака ′+′ в клетке (1,4).

Переходим к следующему опорному плану. Для этого определяем наименьшее значение поставок в вершинах цикла со знаком ′–′. Оно равно 0 в клетке (2,3). Выполняем сдвиг по циклу на величину 0: в клетках, помеченных знаком ′+′, прибавляем 0; в клетках, помеченных знаком ′–′, вычитаем 0. В результате клетка (1,4) входит в базис со значением 0, а клетка (2,3) выходит из базиса.
Получаем таблицу 4.1.

Целевая функция:
F4 = 2·15 + 3·0 + 2·9 + 2·7 + 5·6 + 3·6 + 6·2 + 6·4 + 0·5 = 146
Ее значение не изменилось, поскольку при переходе к новому базису, изменений поставок не произошло. Мы только изменили состав базисных переменных, перешли от одного вырожденного плана ⇑ к другому.

Возможность зацикливания при вырожденном плане

К счастью, при решении задач методом потенциалов, случаи зацикливания не известны, хотя математически не доказано, что их не существует.

Однако известен способ, который позволяет избежать зацикливания при решении любой задачи линейного программирования. Он заключается в том, что мы изменяем исходные данные задачи на бесконечно малую величину ε , и получаем решение, в ходе которого отсутствуют вырожденные планы, и которое стремится к истинному решению при .

Для транспортной задачи этот метод заключается в следующем.
1. Вводим малое число ε .
2. Вводим новые значения мощностей поставщиков и потребителей по следующим формулам:
(1) ;
(2)
3. Решаем транспортную задачу методом потенциалов с мощностями и .
В результате получаем приближенное решение задачи, которое, чем меньше ε , тем ближе к истинному решению.

Доказано, (см. [3] стр. 369 ⇓) что при замене (1) – (2):
1) отсутствуют вырожденные опорные планы;
2) при , решение задачи стремится к истинному решению:
.
Здесь и – решение задачи с мощностями и .
То есть, при достаточно малом ε , мы получаем приближенное решение транспортной задачи.

3.4. Шаг 4

эксперт
Мнение эксперта
Михаил Соловьев, консультант по вопросам работы с продуктами Microsoft
Если у вас возникнут сложности, я помогу разобраться!
Задать вопрос эксперту
, имеет m n компонент по числе ограничений ТЗ , которые называются потенциалами переменные ,, , потенциалы поставщиков; переменные , ,- потенциалы потребителей. Если же вы хотите что-то уточнить, обращайтесь ко мне!
Среди не зачеркнутых клеток, наименьшая стоимость 3 в клетке (3, 1). Даем в нее наибольшую поставку 6. Потребитель B1 получил требуемое количество груза: b1 = 15 + 6 = 21. Вычеркиваем столбец B1.
Транспортная Задача Линейного Программирования в Excel • Условие задачи

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

Вообще говоря, чем большая точность определяется (чем меньше число), тем больше времени понадобится для поиска решения. Методы, используемые Поиском Решения, позволяют существенно ускорить поиск, если установить исходное значение, достаточно близкое к искомому решению.

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Adblock
detector