- •1)Задача линейного программирования и различные формы ее записи. Приведение общей задачи лп к симметричной форме записи.
- •2)Приведение общей задачи лп к каноническому виду.
- •3)Условие оптимальности базисного плана канонической задачи лп. Симплекс-метод и его сходимость.
- •4)Теорема о существовании решения задачи лп.
- •5)Формулы пересчета при симплекс-методе.
- •6)Построение начального базисного плана с помощью искусственных переменных.
- •7)Двойственность для задач линейного программирования в симметричной форме записи. Критерии оптимальности.
- •8)Запись двойственной задачи и условий дополнительности для задачи лп общего вида.
- •9)Транспортная задача в матричной постановке. Существование решения. Критерий оптимальности для транспортной задачи. Метод потенциалов. Связь с симплекс-методом.
- •10)Динамическое программирование. Принцип оптимальности Беллмана. Функциональное уравнение динамического программирования на примерах. Особенности применения динамического программирования.
3)Условие оптимальности базисного плана канонической задачи лп. Симплекс-метод и его сходимость.
Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, записанную в каноническом виде. Идея симплексного метода последовательного улучшения плана, заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Значение целевой функции при этом перемещении для задач на максимум не убывает.
Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Опорным решением называется базисное неотрицательное решение.
Алгоритм симплексного метода 1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду. 2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу 1. Все строки таблицы 1-го шага заполняем по данным системы ограничений и целевой функции.
Возможны следующие случаи при решении задач на максимум:
1. Если все коэффициенты последней строки симплекс-таблицы j 0, то найденное
решение оптимальное.
2 Если хотя бы один коэффициент j 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем, так как F(X) , т.е.целевая функция не ограничена в области допустимых решений.
Если хотя бы один коэффициент последней строки отрицателен, а при соответствующей переменной есть хотя бы одно положительное оценочное отношение , то нужно перейти к другому опорному решению.
4. Если отрицательных коэффициентов в последней строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольший по абсолютной величине отрицательный коэффициент.
5. Если хотя бы один коэффициент k < 0,то k - тый столбец принимаем за ведущий.
6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.
7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.
Заполняем симплексную таблицу 2:
заполняем базисный столбец нулями и единицей
переписываем ведущую строку, разделив ее на ведущий элемент
если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы
остальные коэффициенты находим по правилу “прямоугольника”
Получаем новое опорное решение, которое проверяем на оптимальность:
Если все коэффициенты последней строки j 0, то найденное решение максимальное.
Если нет, то заполняем симплексную таблицу 8-го шага и так далее.
Если целевая функция F(X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность коэффициентов j при всех j = 1,2,...n.
Сходимость симплекс-метода. Вырожденность в задачах ЛП. Важнейшим свойством любого вычислительного, алгоритма является сходимость, т. е. возможность получения в ходе его применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).
Легко заметить, что проблемы со сходимостью симплекс-метода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения отношения
будут достигнуты для нескольких строк таблицы Т (q) одновременно. Тогда на следующей итерации столбец b(β(q+1)) будет содержать нулевые элементы.