Занятие Методы решения транспортной задачи
 Скачать 407.42 Kb.
|
|
Практическое занятие 2. Методы решения транспортной задачи Транспортная задача является одной из наиболее распространённых задач линейного программирования и находит широкое практическое приложение. На предыдущем практическом занятии мы рассмотрели методы построения первоначальных планов поставок. Теперь надо выяснить, являются ли найденные планы оптимальными и если нет, то каким образом их оптимизировать. Матрица оценок Матрица оценок используется для проверки первоначального плана поставок в транспортной задаче на оптимальность. Элементами матрицы оценок являются оценки клеток (i, j) таблицы поставок, которые вычисляются следующим образом: оценка i-ой строки + оценка j-го столбца + число в верхнем левом углу клетки (коэффициент затрат). При этом оценки строки и столбца выбираются таким образом, чтобы оценки всех отмеченных клеток были равны нулю. Если матрица оценок не содержит отрицательных чисел, то получен оптимальный план поставок. В противном случае необходимо провести оптимизацию плана поставок. Рассмотрим схему нахождения матрицы оценок на следующем примере. Пример 1. С помощью матрицы оценок исследовать на оптимальность план поставок (таблица 1). Решение. Процесс нахождения матрицы оценок можно начинать с любой строки или любого столбца. Начнём с первой строки, присвоив ей нулевую оценку (значение нуль взято для простоты, можно выбрать и другую оценку). Напомним, что оценки всех отмеченных клеток должны быть равны нулю. Таблица 1
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||