Главная Учебники - Разные Лекции (разные) - часть 33
Задача №1 (Симплекс метод решения задачи линейного программирования.) Найти Fmax
= 9x1
+ 10x2
+ 16x3,
при ограничениях: Запишем задачу в каноническом виде: F=9x1
+ 10x2
+ 16x3
→max Заполним начальную таблицу: Таблица 0. Отношение, θ Zj вычисляется по формуле Оценки (∆j) вычисляются по формуле Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец. Заполняем столбец «θ», по минимальному значению определяем направляющую строку. На пересечение строки и столбца находится направляющий элемент. Заполняем новую таблицу Таблица 1. Отношение, θ Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е. Столбец Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент. Остальные элементы в небазисных столбцах и в столбце Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец. Заполняем столбец «θ» По минимальному значению определяем направляющую строку. На пересечении направляющей строки и столбца находится направляющий элемент. Заполнение второй таблицы осуществляется по аналогии с предыдущей. Таблица 2. Отношение, θ Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение. Ответ: Максимальное значение функции Fmax
=400 достигается в точке с координатами: Задача №2 (Метод Литтла) Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла. Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно: Предположим что кратчайший путь будет следующим: т.1→ т.2→ т.3→ т.4→ т.5→ т.6→т.1 и составит Решение: Первый этап. Шаг 1. Приведем матрицу расстояний по строкам и столбцам (в строке вычитаем из каждого элемента минимальный, затем в столбцах) ↓ ↓ Шаг 2. Определим оценки нулевых клеток: Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6) Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞). Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки. Второй этап. Шаг 1. Приведем матрицу расстояний по строкам и столбцам. ↓ Шаг 2. Определим оценки нулевых клеток: Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2) Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 – 1 ставим ∞). Третий этап. Шаг 1. Приведем матрицу расстояний по строкам и столбцам. ↓ ↓ Шаг 2. Определим оценки нулевых клеток: Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5) Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞). Четвертый этап. Шаг 1. Приведем матрицу расстояний по строкам и столбцам. ↓ Шаг 2. Определим оценки нулевых клеток: Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4) Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞). Пятый этап. Остались не задействованными связи 2 – 3 и 6 – 1. В результате получаем следующую цепочку: 1→ 2→ 3 → 4→ 5→ 6 →1 Длина пути составляет: L=18,87+32,06+31,76+32,14+22,14+97,42=234,39 это и есть кратчайший путь.
|