Элементы линейной алгебры и геометрии выпуклых множеств

ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ И ГЕОМЕТРИИ ВЫПУКЛЫХ МНОЖЕСТВ
Определение 1.3. Точка множества называется внутренней, если существует окрестность этой точки, состоящая только из точек данного множества.
Определение 1.4. Точка множества называется граничной, если любая окрестность этой точки содержит, как точки принадлежащие данному множеству, так и не принадлежащие ему.
Определение 1.5. Множество точек называется замкнутым, если оно включает в себя все свои граничные точки.
Примеры замкнутых множеств:
1) любой отрезок на числовой прямой;
2) числовая прямая, так как она включает в себя пустое множество своих граничных точек.

ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ И ГЕОМЕТРИИ ВЫПУКЛЫХ МНОЖЕСТВ
Определение 1.6. Точка множества называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

ОПРЕДЕЛЕНИЕ ВЫПУКЛОГО МНОГОГРАННИКА
Определение 1.8. Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым многогранником (многоугольником), если оно ограниченно и выпуклой многогранной (многоугольной) областью, если оно неограниченно.

ОПРЕДЕЛЕНИЕ БАЗИСНОГО РЕШЕНИЯ
Определение 1.9. Любые m переменных системы n линейных уравнений 1.18 называются базисными, если определитель матрицы коэффициентов при этих m переменных отличен от нуля. Остальные переменные системы называются свободными.

РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ ГРАФИЧЕСКИ
Рассмотрим графическое решение системы m линейных неравенств:

Задача 1.4. Изобразить графически множество неотрицательных решений системы неравенств и определить координаты угловых точек области допустимых решений:
РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ ГРАФИЧЕСКИ

РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ ГРАФИЧЕСКИ

Задача 1.5. Найти область неотрицательных решений системы неравенств:
РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ ГРАФИЧЕСКИ

Задача 1.6. Найти область неотрицательных решений системы неравенств:
РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ ГРАФИЧЕСКИ

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Определение 2.1. Решение задачи ЛП называется допустимым, если оно содержится в области допустимых решений системы ограничений задачи.
Определение 2.2. Допустимое базисное решение задачи ЛП называется опорным планом.
Определение 2.3. Целевая функция в задаче ЛП называется ограниченной, если в задаче на максимум целевая функция ограничена на допустимом множестве сверху, а в задаче на минимум – снизу.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЛП
Теорема 2.1. Если в задаче ЛП допустимое множество не пусто и целевая функция ограничена, то существует хотя бы одно оптимальное решение.
Теорема 2.2. Между множествами опорных решений задачи ЛП и угловых точек области допустимых решений существует взаимно однозначное соответствие.
Теорема 2.3. Если в задаче ЛП все переменные имеют условие не отрицательности и целевая функция ограничена сверху (снизу) на допустимом множестве, то угловая точка, в которой целевая функция принимает наибольшее (наименьшее) значение среди всех угловых точек множества допустимых решений, является оптимальным решением.

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ВЕКТОР ГРАДИЕНТ. СЛУЧАЙ АЛЬТЕРНАТИВНОГО РЕШЕНИЯ
Определение 2.4. Вектор, координаты которого являются частными производными функции F(x) по соответствующим переменным, называется вектором градиентом и обозначается

ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ О НАИЛУЧШЕМ ИСПОЛЬЗОВАНИИ РЕСУРСОВ

ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ О НАИЛУЧШЕМ ИСПОЛЬЗОВАНИИ РЕСУРСОВ
:

АНАЛИЗ ВЛИЯНИЯ ПРАВОЙ ЧАСТИ АКТИВНЫХ ОГРАНИЧЕНИЙ НА ОПТИМАЛЬНОЕ РЕШЕНИЕ
:

АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ.
В рамках анализа модели на чувствительность выявляется чувствительность оптимального решения к определенным изменениям исходной модели.
Если прямая проходит через точку, в которой находится оптимальное решение, то соответствующее ограничение будем считать активным, соответствующий ресурс - дефицитным.
Если ограничение пассивное, то соответствующий ресурс является недефицитным и имеется в избытке.
При анализе модели на чувствительность к правым частям ограничений, определяются:
а)предельно допустимые увеличения запаса дефицитного ресурса, позволяющие улучшить найденное оптимальное решение ;
б)предельно допустимое снижение запаса недефицитного ресурса , не изменяющее найденное ранее оптимальное значение целевой функции.