- •Предмет «Математическое программирование», общая постановка задачи, различные его разделы.
- •Экономические постановки задач линейного программирования.
- •Постановка и математическая модель задачи оптимального планирования.
- •Постановка и математическая модель задачи на смеси и соединения
- •Постановка и математическая модель задачи раскроя материалов.
- •Постановка и математическая модель транспортной задачи.
- •Постановка и математическая модель задачи о назначении.
- •Линейная зависимость системы векторов, ранг системы векторов.
- •Разложение вектора по векторам базиса.
- •Метод Жордана-Гаусса, решение систем линейных уравнений.
- •Постановка и математическая модель распределительной (х-задачи).
- •Формы записи задачи линейного программирования (общая, векторная, матричная).
- •Виды решений систем линейных уравнений.
- •Выпуклое множество и его особые точки.
- •Теорема о представлении.
- •Теорема об экстремуме целевой функции.
- •Свойство решений задачи линейного программ-я.
- •Теорема об опорном плане.
- •Геометрическая интерпретация задачи линейного программирования.
- •Графический метод решения задачи линейного программирования с двумя неизвестными
- •Графический метод решения задачи линейного программирования с п неизвестными.
- •Формы задачи линейного программирования. Переход от одной формы к другой.
- •24. Симплексный метод решения задачи линейного программирования:
- •25. Метод искусственного базиса.
- •Несовместность условий в линейном программировании.
- •Двойственность в линейном программировании:
- •Транспортная задача, ее модель.
- •Методы построения первого опорного плана транспортной задачи.
- •Вырожденность в транспортной задаче.
- •Альтернативный оптимум в транспортной задаче.
- •Запреты в транспортной задаче.
- •35 Задача динамического программирования. Функция Беллмана.
- •36. Задачи целочисленного программирования. Метод ветвей и границ. Метод Гомори.
- •37.Задачи нелинейного программирования.
24. Симплексный метод решения задачи линейного программирования:
Для решения задачи симплекс-методом мы должны ответить на два вопроса:
1. Является ли очередной опорный план оптимальным; если не является, то указать к какому опорному плану необходимо перейти.
2. Как перейти от одного опорного плана к другому.
Теорема1. Если для некоторого вектора Аj выполняется соотношение zj – сj>0 , то план х0 не является оптимальным и можно перейти к плану х1 такому, что z(х1) ≤ z(х0).
Теорема2. Если для всех векторов А1, А2,…, Аn некоторого опорного плана х0 выполняется соотношение zj – сj≤ 0 , то опорный план 0 х является оптимальным. Величины (zj – сj) – называются оценками соответствующих векторов.
Для перехода к новому опорному плану, необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести из него.
Альтернативный оптимум (множество оптимальных решений).
Если среди неположительных оценок свободных векторов имеется хотя бы одна нулевая, то полученный опорный план будет оптимальным, но не единственным. В этом случае можно перейти к другим опорным планам (вводятся в базис векторы, которым соответствуют нулевые оценки) и, затем, общее оптимальное решение записать в виде выпуклой комбинации полученных оптимальных опорных планов.
ЗЛП не имеет оптимального решения, т.к. целевая функция не ограничена снизу. Если в симплекс-таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя из него вывести. Следовательно, дальнейшее уменьшение целевой функции возможно только при переходе к неопорному плану.
ЗЛП не имеет оптимального решения, т.к. система ограничений противоречива. Поскольку при решении задачи обычным симплекс–методом должен быть исходный опорный план, то
система линейных уравнений заведомо непротиворечива. Следовательно, такой случай не может встретиться при решении обычным симплекс-методом.
25. Метод искусственного базиса.
Если задача линейного программирования находится в канонической форме, но исходный опорный план отсутствует, то такая задача не может быть решена обычным симплекс-методом. Для решения такой задачи может использоваться один из следующих способов:
I способ. Выделение исходного опорного плана с помощью метода Жордана–Гаусса. Необходимо отдельно выписать систему линейных уравнений задачи и с помощью метода Жордана–Гаусса выделить некоторое неотрицательное базисное решение (опорный план). Для этого при выборе разрешающей строки необходимо использовать симплексное отношение. Затем, используя преобразованную систему линейных уравнений, можно решать задачу обычным симплекс-методом.
II способ. Симплекс-метод с искусственным базисом.
Пусть задача линейного программирования находится в канонической форме, однако, не во всех уравнениях имеются базисные переменные, то есть исходный опорный план отсутствует. В этом случае в уравнения без базисных
переменных необходимо добавить с коэффициентом +1 некоторую неотрицательную переменную, которая называется искусственной.