Основные теоремы линейного программирования. Фундаментальная теорема и теорема об альтернативном оптимуме.
Теорема. (Фундаментальная). Если задача ЛП имеет оптимальное решение, ( в ограниченной области всегда, а в не ограниченной области в зависимости от ограниченности линейной функции), то оно совпадает, по крайней мере, с одним из опорных решений системы ограничительных уровней.
Данная теорема обобщает все из рассмотренных выше случаев, утверждает, что если задача ЛП имеет оптимальное решение, то оно совпадает хотя бы с одной из вершин области допустимых решений.
Теорема. (Об альтернативном оптимуме). Если maх или min линейной функции достигает в нескольких опорных решениях, то любое оптимальное решение есть выпуклая линейная комбинация оптимальных решений.
Геометрически интерпретация данной теоремы означает. Что в случае альтернативного оптимума линии уравнения проходят через две вершины области допустимых решений и в этом случае оптимальное решение становится любая точка отрезка, соединяющая эти вершины.
-
Содержание
- 9. Алгебраический симплексный метод. Основные положения данного метода.
- 10. Алгоритм решение задачи симплексным методом(первый опорный план)
- 11. Алгоритм решения задачи симплексным методом ( проверка на оптимальность, определения ведущего столбца и строки, построение нового опорного плана).
- 13. Анализ оптимального плана симплексного метода на примере задачи планирования товарооборота.
- Метод искусственного базиса на примере системы ограничений, содержащей уравнения.
- Основные теоремы линейного программирования. Фундаментальная теорема и теорема об альтернативном оптимуме.
- Геометрическая интерпретация симплекс-метода.
- Двойственная задача линейного программирования и ее математическая модель.(не до конца!!!!)
- 21. Виды двойственных задач. Правила составления симметричных двойственных задач линейного программирования.
- 22. Виды двойственных задач. Правила составления несимметричных двойственных задач линейного программирования.
- Основное неравенство теории двойственности. Достаточный признак оптимальности. Первая теорема двойственности.
- 24. Экономический смысл первой теоремы двойственности.
- 25. Вторая теорема двойственности. Определение двойственных оценок с помощью второй теоремы двойственности.
- 26. Определение двойственных оценок однородной задачи линейного программирования симплекс-методом.
- 31) Транспортная задача линейного программирования, ее математическая модель.
- 33. Построение начального опорного решения тз методом наименьших тарифов.
- 34. Построение начального опорного решения тз методом северо-западного угла.
- 35. Построение начального опорного решения тз методом двойного предпочтения.
- 37. Метод потенциалов тз. Проверка плана на вырожденность. Проверка решения транспортной задачи на оптимальность.
- 38. Построение нового опорного решения тз. Понятие цикла.
- 39. Анализ оптимального решения тз. Рекуррентная формула расчета целевой функции.
- Поток Пальма. Поток Эрланга.
- Графы состояний смо.
- Цепи Маркова.
- Случайные процессы. Марковские случайные процессы.
- Уравнения Колмогорова.