- •Линейное программирование
- •Часть I Содержание:
- •1. Основные понятия
- •1.1. Примеры моделей, приводящих к задачам линейного программирования
- •Задача о диете
- •1.2. Стандартная и каноническая формы задачи линейного программирования
- •Первая стандартная форма задачи линейного программирования имеет вид
- •Канонической формой задачи линейного программирования называется задача вида
- •5. Ограничения на неотрицательность переменных.
- •1.3. Геометрическая интерпретация задач линейного программирования
- •Решение
- •Решение
- •Решение
- •2. Симплекс-метод
- •2.1. Выпуклые множества и многогранники
- •Доказательство
- •Доказательство.
- •Доказательство
- •2.2. Вершины выпуклого многогранника
- •Определение. Вершиной или крайней точкой выпуклого многогранника называется любая его точка, которая не является внутренней точкой никакого отрезка, целиком принадлежащего этому многограннику.
- •Доказательство
- •Доказательство
- •Доказательство
- •Доказательство
- •2.3. Переход от вершины к вершине
- •2.4. Переход к новому базису
- •2.5. Отыскание оптимального плана
- •Доказательство:
- •Доказательство:
- •2.6. Алгоритм симплекс-метода
- •Этап 1 Просматривается дополнительная строка снизу, где записаны разности .
- •Первая итерация
- •И он достигается на векторе , то этот вектор подлежит выводу из базиса и соответствующая ему строка и будет направляющей строкой.
- •Вторая итерация
- •2.7. Метод искусственного базиса
- •Вариант 1
- •Вариант 2
- •Первая итерация Так как из базиса выводится вектор , то в получающейся симплекс-таблице соответствующий столбец сразу удаляется.
- •Вторая итерация
- •Третья итерация Мы вернулись к исходной задаче и продолжаем решать ее по стандартной схеме.
- •3. Двойственные задачи
- •3.1. Постановка двойственных задач Симметричные двойственные задачи
- •Несимметричная двойственная задача
- •Переменные называется по-разному. Часто их называют учетными, неявными или фиктивными ценами.
- •3.2. Свойства двойственных задач
- •Доказательство.
- •1. Симметричная пара
- •2. Несимметричная пара Доказательство в этом случае почти дословно повторяет предыдущее.
- •Теорема 3. ( в формулировке для несимметричной двойственной задачи)
- •Доказательство.
- •Теорема 3. (в формулировке для симметричной двойственной задачи).
- •3.3. Двойственный симплекс-метод
- •4. Транспортная задача
- •4.1. Постановка задачи
- •Приведение открытой транспортной задачи к сбалансированной
- •4.2. Простейшие свойства транспортной задачи
- •Доказательство
- •Доказательство
- •Доказательство
- •4.3. Методы определения первоначального опорного плана
- •4.3.1. Построение исходного опорного плана (метод северо-западного угла)
- •Пример 1
- •Пример 2
- •4.3.2. Метод минимального (максимального) элемента
- •Пример № 2
- •Решение:
- •4.3.3. Метод аппроксимации Фогеля
- •Решение:
- •4.3.4. Метод двойного предпочтения
- •4.4. Методы проверки опорного плана на оптимальность
- •4.4.1. Потенциалы. Критерий оптимальности плана
- •4.4.2. Дельта-метод
- •4.5. Алгоритм улучшения плана
- •Вторая итерация Этап 1
- •Третья итерация Этап 1
- •Теорема Если все запасы и все потребности целые числа, то оптимальный план перевозок тоже целочисленный. Доказательство
- •4.6. Снятие вырожденности
- •4.6.1. Эпсилон-прием
- •Построение исходного опорного плана.
- •Первая итерация
- •Вторая итерация Этап 1
- •Третья итерация Этап 1
Доказательство
Пусть |
точки, принадлежащие множеству G . |
Докажем теорему методом математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.
Пусть теорема верна для некоторого k. Возьмём точку и рассмотрим выпуклую комбинацию
,
где все |
и . |
Представим |
в виде |
Но коэффициенты |
и |
,
и, раз мы считаем, что для k теорема верна, точка
.
Но тогда является выпуклой комбинацией точек
и и, по определению выпуклого множества, . |
Теорема доказана.
Теорема 2. Допустимая область задачи линейного программирования является выпуклым множеством.
Доказательство.
В стандартной форме в матричных обозначениях допустимая область G определяется условием
Пусть |
и |
принадлежат G , т.е. |
Но тогда для |
имеем |
т.е. x принадлежит G и, следовательно, выпукло.
В канонической форме область G определена условиями
Пусть и принадлежат G, т.е.
.
Но тогда для |
имеем |
т.е. и, следовательно, G выпукло. Теорема доказана.
Таким образом, допустимая область в задаче линейного программирования является выпуклым множеством. По аналогии с двумерным или трехмерным случаями, при любом n эту область называют выпуклым
многогранником в n - мерном пространстве |
|
Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто).
Доказательство
Если решение задачи линейного программирования единственно, то оно выпукло по определению точка считается выпуклым множеством Пусть теперь и два оптимальных плана задачи линейного программирования.
Тогда |
и . |
Рассмотрим . |
В силу выпуклости области |
допустимых значений, . |
Но для этого плана |
т.е. есть также оптимальный план и, в силу этого, множество оптимальный планов выпукло. Теорема доказана.
Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).
2.2. Вершины выпуклого многогранника
На примере задачи линейного программирования с n=2 мы видели, что особую роль играют вершины допустимой области. Но что понимать под вершиной выпуклого многогранника при n>3, когда не существует геометрически наглядного образа ?
Легко заметить, что при n=2 и n=3 вершина выпуклого многогранника это такая точка, которая не является внутренней точкой никакого отрезка, концы которого принадлежат этому многограннику (см. рис 14). Этим свойством обладают только вершины .