- •Линейное программирование
- •Часть 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
Доказательство:
Пусть наш опорный план и - произвольный план. Тогда имеем
|
(1.39) |
|
(1.40) |
Покажем, что .
По предположению, все j то есть . Кроме того, все . Поэтому
|
(1.41) |
Подставим в (1.39) вместо их разложения по базису
и изменим порядок суммирования
|
(1.42) |
Аналогично, подставляя в (1.41) для каждого j выражение из формулы (1.37), получим:
Так как система векторов линейно независима, то коэффициенты разложения вектора по базису , даваемые формулами (1.42) и (1.34) должны быть одинаковы. Поэтому
получим
,
то есть любой другой план имеет не меньшее значение целевой функции, чем наш опорный план.
Эта теорема дает критерий оптимальности опорного плана.
Теоремы 1.9 и 1.10 дают возможность, начав с некоторого исходного опорного плана, получать последовательность все более лучших опорных планов, которые завершатся либо оптимальным планом, либо будет показано, что целевая функция неограничена.
Отметим следующее:
Если при вычислении минимум достигается при нескольких i, то для вывода из базиса обычно берут вектор с наименьшим индексом.
Для определения вектора , вводимого в базис, обычно берут тот вектор , для которого разность наибольшая
2.6. Алгоритм симплекс-метода
Теперь мы в состоянии сформулировать алгоритм симплекс-метода для решения задач линейного программирования, заданных в канонической форме. Обычно он реализуется в виде так называемой симплекс-таблицы, изображенной на следующей странице.
В первом столбце этой таблицы располагаются обозначения векторов, входящих в базис.
Второй столбец коэффициенты целевой функции, соответствующие векторам, входящим в базис.
Третий столбец компоненты опорного плана. В дополнительной строке в этом столбце пишется величина . Её легко вычислить перемножая числа из второго столбца и третьего столбца и складывая их.
Далее идут столбцы, соответствующие всем векторам , и в этих столбцах записываются координаты этих векторов в рассматриваемом базисе. Заметим, что для векторов, входящих в базис, эти координаты имеют вид (0,0, ... ,0,1,0, ..., 0), где единица стоит в той строке, где находится сам этот базисный вектор.
В дополнительной строке сверху обычно выписывают коэффициенты , соответствующие этим векторам.
В дополнительной строке снизу пишутся величины , вычисляемые по формулам:
.
Заметим, что для векторов, входящих в базис, эти разности всегда равны нулю.
Далее идут следующие этапы, связанные с преобразованием этой таблицы. При ручном счете каждый раз эту таблицу лучше переписывать заново, при счете на ЭВМ (который, естественно, всегда используется при решении практических, а не учебных задач), эта таблица просто преобразуется в памяти ЭВМ.
Этап 1 Просматривается дополнительная строка снизу, где записаны разности .
Если все эти разности , |
то план является оптимальным |
Этап 2
Если есть столбцы, где , то выбирается столбец с максимальным значением этой разности. Индекс j определит вектор, вводимый в базис.
Пусть , то есть в базис надо вводить вектор . Назовем столбец, соответствующий этому вектору, направляющим столбцом. В дальнейшем мы будем направляющий столбец помечать символом .
Этап 3
Просматривается столбец, соответствующий этому вектору. Если все , то значения целевой функции неограничены снизу. Если есть , то находятся
где просматриваются лишь те дроби , |
для которых |
Пусть этот минимум достигается для вектора . Тогда именно вектор подлежит выводу из базиса. Строка, соответствующая этому вектору, называется направляющей строкой. В дальнейшем в примерах мы будем
помечать ее символом . |
Этап 4
После того, как определены направляющие столбец и строка, начинает заполняться новая симплекс-таблица, в которой на месте направляющей
строки будет стоять вектор . |
|
Обычно заполнение этой новой таблицы начинается именно с направляющей строки. В качестве компоненты опорного плана туда
пишется величина , то есть |
|
.
Остальные элементы этой строки заполняются величинами
.
Обратите внимание на особую роль элемента , стоящего на пересечении направляющей строки и направляющего столбца. Именно на него делятся все бывшие элементы направляющей строки. На месте бывшего элемента автоматически появляется единица.
Написанные выше формулы для пересчета элементов направляющей строки можно записать следующим правилом:
.
Этап 5
Далее начинается пересчет всех остальных строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент плана
;
для координат разложения по базису
;
для дополнительной строки
.
Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу
.
Это правило применимо и к компонентам плана, и к величинам , и к разностям . Его даже можно использовать для пересчета элементов самого направляющего столбца, хотя проще заполнить его нулями, оставив
1 на месте бывшего элемента . |
Далее итерации продолжаются.
Пример
Решить задачу линейного программирования
В данном случае вектор равен (0,1,-3,0,2,0), а в векторной форме ограничения могут быть записаны в виде
.
Заполним исходную симплекс-таблицу, взяв в качестве исходного базиса
вектора , |
что удобно из-за их вида. |
Исходная симплекс-таблица
|
Ба- |
|
План |
0 |
1 |
-3 |
0 |
2 |
0 |
|
зис |
|
|
|
|
|
|
|
|
|
|
0 |
7 |
1 |
3 |
-1 |
0 |
2 |
0 |
|
|
0 |
12 |
0 |
-2 |
4 |
1 |
0 |
0 |
|
|
0 |
10 |
0 |
-4 |
3 |
0 |
8 |
1 |
|
|
|
0 |
0 |
-1 |
3 |
0 |
-2 |
0 |
|
|
|
|
|
|
|
|
|
|
Обратите внимание на то, что из-за специфического вида векторов в столбец "план" просто переписался вектор , а в качестве координат векторов в нашем базисе стоят просто сами векторы.
Ну, а величины приходится считать: