- •1. Построение экономико-математической модели задачи линейного программирования (на конкретном примере).
- •Этапы моделирования
- •Основные типы моделей:
- •§2. Основы линейного программирования.
- •Примеры задач линейного программирования
- •3. Виды заданий системы ограничений экономико-математической модели. Переход от стандартного к каноническому заданию
- •4. Геометрический смысл решения неравенств и системы неравенств
- •5. План решения задачи линейного программирования геометрическим методом
- •Строим вектор - нормальный вектор, он указывает направление возрастания функции.
- •Мысленно перемещаем прямую в направлении вектора , тогда:
- •§9. Критерии оптимальности симплекс - метода.
- •12. Метод искусственного базиса
- •7) Далее задачу решают на max или min.
- •13. Транспортная задача. Общая подстановка. Открытая и закрытая модели
- •14. Построение первоначального плана транспортной задачи методом северо-западного угла
- •15. Построение первоначального плана транспортной задачи методом минимального эллипса
- •16. Улучшение первоначального плана транспортной задачи методом потенциалов. Основные этапы. Цикл, потенциалы
- •Предварительный шаг решения:
- •17. Составление системы потенциалов для заполненных клеток при решении транспортной задачи
- •Общий шаг решения:
- •18. Проверка на потенциальность незаполненных клеток при решении транспортной задачи.
16. Улучшение первоначального плана транспортной задачи методом потенциалов. Основные этапы. Цикл, потенциалы
Определение 1. Циклом в таблице называется ломаная, с вершинами в клетках таблицы и звеньями, лежащими вдоль строк и столбцов, если выполняются условия:
Ломаная должна быть связанной, т. е. из любой вершины можно попасть в любую другую.
В каждой вершине ломаной встречаются два звена, одно из которых расположено по строке, другое - по столбцу.
Число вершин ломаной - четное.
Первоначальный план, как правило, ацикличен.
Теорема. Чтобы план перевозок был оптимальным, необходимо и достаточно, чтобы ему соответствовала такая система из чисел , для которых выполняются следующие условия:
(для всех клеток принадлежащих множеству X или для заполненных клеток).
(для всех клеток, не принадлежащих множеству Х или для всех пустых клеток).
Числа называют потенциалами соответствующих пунктов отправления и Алгоритм решения транспортной задачи методом потенциалов.
Определение 2. Совокупность уравнений вида для всех клеток с перевозками образует систему уравнений с переменными. Такая система имеет бесконечное множество решений. Чтобы система была определенной, принято считать . Оставшиеся переменные находят из системы.
Предварительный шаг решения:
составляем опорное решение задачи одним из трех методов.
строим систему потенциалов для клеток с перевозками.
назначения
17. Составление системы потенциалов для заполненных клеток при решении транспортной задачи
Общий шаг решения:
Улучшаем план перевозок, составляя цикл, в одной из вершин которого находится максимально не потенциальная клетка, т. е. соответствующая . Остальные вершины цикла находятся в заполненных клетках. Вершины цикла, начиная с максимально не потенциальной клетки, обозначают знаками . Рассматривают перевозки в отрицательных вершинах и находят среди них наименьшую . Далее эту минимальную перевозку перемещают по циклу, вычитая от перевозок с отрицательными вершинами и прибавляя к перевозкам с положительными вершинами.
Исправляем систему потенциалов: потенциал новой клетки оставляют без изменения, а от соответствующего потенциала вычитают . Затем исправляют систему потенциалов для клеток с положительными перевозками, для которых потенциальность нарушена.
Проверяем на потенциальность не заполненные клетки и решаем задачу дальше.
Замечание: Если задача решается на max, то система потенциалов составляется так же, а условие потенциальности незаполненных клеток имеет вид: .