ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.03.2024
Просмотров: 31
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Практическое занятие 2.
Методы решения транспортной задачи
Транспортная задача является одной из наиболее распространённых задач линейного программирования и находит широкое практическое приложение. На предыдущем практическом занятии мы рассмотрели методы построения первоначальных планов поставок. Теперь надо выяснить, являются ли найденные планы оптимальными и если нет, то каким образом их оптимизировать.
-
Матрица оценок
Матрица оценок используется для проверки первоначального плана поставок в транспортной задаче на оптимальность.
Элементами матрицы оценок являются оценки клеток (i, j) таблицы поставок, которые вычисляются следующим образом: оценка i-ой строки + оценка j-го столбца + число в верхнем левом углу клетки (коэффициент затрат). При этом оценки строки и столбца выбираются таким образом, чтобы оценки всех отмеченных клеток были равны нулю. Если матрица оценок не содержит отрицательных чисел, то получен оптимальный план поставок. В противном случае необходимо провести оптимизацию плана поставок.
Рассмотрим схему нахождения матрицы оценок на следующем примере.
Пример 1. С помощью матрицы оценок исследовать на оптимальность план поставок (таблица 1).
Решение. Процесс нахождения матрицы оценок можно начинать с любой строки или любого столбца. Начнём с первой строки, присвоив ей нулевую оценку (значение нуль взято для простоты, можно выбрать и другую оценку).
Напомним, что оценки всех отмеченных клеток должны быть равны нулю.
Таблица 1
| | 70 | 120 | 150 | 130 | ||||||||||
| 30 | 4 | 30 | 7 | 2 | 3 | |||||||||
| 190 | 3 | | 1 | | 2 | | 4 | |||||||
| | 40 | | 120 | | 30 | |||||||||
| 250 | 5 | 6 | 3 | | 7 | | ||||||||
| | 120 | | 130 | |||||||||||
Шаг 1. Оценка клетки (1,1) = оценка 1-ой строки + оценка 1-го столбца + число в верхнем левом углу клетки: 0 = 0 + оценка 1-го столбца + 4. Отсюда следует, что оценка 1-го столбца равна -4.Шаг 2. Выбираем отмеченную клетку для которой известна оценка строки или столбца. Это клетка (2,1): 0 = оценка 2-ой строки + (-4) + 3. Отсюда следует, что оценка 2-ой строки равна 1.
Найденные оценки строк
и столбцов удобно записывать, соответственно, справа и снизу таблицы.
| | 70 | 120 | 150 | 130 | | |||||||
| 30 | 4 | 30 | 7 | 2 | 3 | 0 | ||||||
| 190 | 3 | | 1 | | 2 | | 4 | 1 | ||||
| | 40 | | 120 | | 30 | |||||||
| 250 | 5 | 6 | 3 | | 7 | | | |||||
| | 120 | | 130 | |||||||||
| | -4 | | | | | |||||||
Шаг 3. Выбираем отмеченную клетку (2,2):
0 = 1 + оценка 2-го
столбца + 1. Отсюда следует, что оценка 2-го столбца равна -2.
Шаг 4. Выбираем отмеченную клетку (2,3): 0 = 1 + оценка 3-го столбца + 2. Отсюда следует, что оценка 3-го столбца равна -3.
| | 70 | 120 | 150 | 130 | |
| 30 | 4 30 | 7 | 2 | 3 | 0 |
| 190 | 3 40 | 1 120 | 2 30 | 4 | 1 |
| 250 | 5 | 6 | 3 120 | 7 130 | |
| | -4 | -‐2 | -‐3 | | |