Задача линейного программирования

Задача линейного программирования

Линейное программирование

К оглавлению…

Создание Данцигом в конце 1940-х годов симплекс-метода стало началом современной эры в оптимизации. Этот метод позволил экономистам формулировать большие модели и систематически и эффективно анализировать их. Открытие Данцига совпало с появлением цифровых компьютеров, и симплекс-метод стал одним из первых примеров удачного использования этой новой революционной технологии. С тех пор реализация симплекс-метода постоянно совершенствуется. Сегодня линейное программирование и симплекс-метод — наиболее широко используемые средства оптимизации, и, несмотря на то что в настоящее время появились новые классы эффективных методов (например, метод внутренней точки), актуальность и важность симплекс-метода гарантированы в обозримом будущем.

Возможно эта страница вам будет полезна:

Предмет математическое программирование

Постановка задачи линейного программирования. Общая, нормальная и каноническая формы записи

К оглавлению…

Задача оптимизации, в которой требуется найти числа Задача линейного программирования, обращающие в максимум (минимум) линейную форму

Задача линейного программирования

при линейных ограничениях (типа равенств и неравенств)

Задача линейного программирования

называется общей задачей линейного программирования (ЛП). Здесь . Задача линейного программированияЗадача линейного программирования Задача линейного программирования — некоторые заданные конечные наборы индексов; Задача линейного программирования Задача линейного программирования — заданные числа.

Задача, в которой требуется найти максимум линейной формы (1.1) при условиях (1.2) и условиях

Задача линейного программирования

называется задачей линейного программирования в нормальной форме. В матричном виде задача в нормальной форме записи имеет вид

Задача линейного программирования

где Задача линейного программирования-векторы; Задача линейного программирования вектор; Задача линейного программирования (-матрица; символом Задача линейного программирования обозначено количество элементов множества Задача линейного программирования; символом % (штрих) обозначается операция транспонирования.

Задача, в которой максимизируется линейная форма (1.1) при условиях (1.3) и (1.4), называется задачей линейного программирования в канонической форме записи.

В матричном виде задача в канонической форме записывается следующим образом

Задача линейного программирования

где Задача линейного программирования — матрица и Задача линейного программирования — вектор.

В задачах (1.5), (1.6) ограничения Задача линейного программирования и Задача линейного программирования называются основными, ограничения вида Задача линейного программирования — прямыми. Линейная форма Задача линейного программирования называется целевой функцией. Столбцы Задача линейного программирования матрицы Задача линейного программирования называются векторами условий.

Вектор Задача линейного программирования, удовлетворяющий всем ограничениям задачи линейного программирования, назовем ее планом. План Задача линейного программирования, обращающий в максимум линейную форму Задача линейного программирования, называется оптимальным планом или решением задачи линейного программирования.

Задачу линейного программирования, заданную в любой форме, можно свести к задаче в канонической форме записи.

Покажем на простых примерах, как задачу, заданную в общей форме, можно свести к канонической.

Возможно эта страница вам будет полезна:

Решение задач по математическому программированию

Задача №1

Привести к канонической форме записи задачу

Задача линейного программирования

Решение:

Для того чтобы первое ограничение записать в форме равенства, введем неотрицательную переменную Задача линейного программирования Заменим переменную Задача линейного программирования, на значения которой не наложено требование отрицательности, разностью двух неотрицательных переменных

Задача линейного программирования

После этих преобразований исходная задача запишется в канонической форме

Задача линейного программирования

Задача №2

Привести к канонической форме задачу

Задача линейного программирования

Решение:

Умножим коэффициенты целевой функции (а) на (-1), в результате вместо задачи минимизации получим задачу максимизации:

Задача линейного программирования

Введем дополнительные неотрицательные переменные Задача линейного программирования и запишем ограничения (с) и (d) в виде

Задача линейного программирования

Исключим из задачи переменную Задача линейного программирования, на которую не наложено условие неотрицательности. Для этого из условия (Ь) выразим Задача линейного программирования:

Задача линейного программирования

Подставив (h) в (f), (g), получим каноническую форму задачи :

Задача линейного программирования

Отметим что задача максимизации функции (i) эквивалентна максимизации функции

Задача линейного программирования

Задача линейного программирования в нормальной форме записи (1.5) приводится к канонической форме путем добавления неотрицательных переменных Задача линейного программирования. В результате получим эквивалентную задачу в канонической форме

Задача линейного программирования

Здесь Задача линейного программирования — единичная Задача линейного программирования — матрица.

Теорема. Для того чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы множество ее планов было не пусто, а целевая функция ограничена сверху на множестве планов.

Таким образом, для построения решения задачи линейного программирования надо определить, какая из ситуаций Задача линейного программирования или Задача линейного программирования имеет для нее место, и, если реализовалась ситуация Задача линейного программирования, то найти оптимальный план Задача линейного программирования.

Возможно эта страница вам будет полезна:

Примеры решения задач по математическому программированию

Базисный план задачи линейного программирования

К оглавлению…

Выше показано, что любая задача линейного программирования может быть приведена к канонической форме. Поэтому далее основные теоремы и алгоритмы будут рассмотрены применительно к задаче (1.6), что не снижает общности рассмотрения.

Исследуем задачу линейного программирования в канонической форме (1.6), считая для определенности, что

Задача линейного программирования

В дальнейшем, вплоть до подразд. 1.6, мы будем предполагать, что

Задача линейного программирования

Очевидно, что при нарушении условия (1.8) система Задача линейного программирования либо несовместна, либо содержит линейно зависимые условия, которые можно исключить из рассмотрения (см. подразд. 1.6).

План Задача линейного программирования задачи (1.6) назовем базисным планом, если существует такое подмножество Задача линейного программирования множества индексов Задача линейного программирования, что 1) Задача линейного программирования, 2) Задача линейного программирования — матрица Задача линейного программирования, построенная по правилу Задача линейного программированияЗадача линейного программирования, не вырождена.

Напомним, что Задача линейного программирования — это Задача линейного программирования-й столбец матрицы Задача линейного программирования.

Множество Задача линейного программирования назовем базисом или множеством базисных индексов. Множество Задача линейного программирования и будем называть множеством небазисных индексов, матрицу Задача линейного программирования — базисной матрицей.

Иногда базисный план удобно обозначать в виде пары Задача линейного программирования, состоящей из плана Задача линейного программирования и соответствующего ему базиса Задача линейного программирования.

Базисный план считается невырожденным, если

Задача линейного программирования

Отметим, что в общем случае плану Задача линейного программирования можно приписать несколько наборов базисных индексов

Задача линейного программирования

удовлетворяющих условиям 1) — 3). Базисному плану Задача линейного программирования соответствует единственный набор базисных индексов Задача линейного программирования, если имеют место неравенства (1.9), т.е. базисный план является невырожденным.

Легко проверить, что по заданному набору базисных индексов Задача линейного программирования базисный план Задача линейного программирования восстанавливается однозначно по правилу

Задача линейного программирования

Здесь Задача линейного программирования — матрица, обратная к базисной матрице Задача линейного программирования.

Далее будет показано, что симплекс-метод при решении задачи (1.6) генерирует последовательность планов Задача линейного программирования каждый из которых является базисным планом. Поскольку наша цель — построить последовательность планов, сходящихся к решению задачи (1.6), то итерации симплекс -метода будут иметь смысл только в том случае, если

а) задача (1.6) имеет базисные планы;

б) существует оптимальный базисный план.

Оказывается, оба условия, а и б, верны при минимальных предположениях.

Теорема (основная теорема ЛП). Если для задачи (1.6) существует план, то для нее существует и базисный план. Если задача (1.6) имеет оптимальные планы, то хотя бы один из них базисный.

Возможно эта страница вам будет полезна:

Заказать работу по математическому программированию

Исследование базисного плана на оптимальность

К оглавлению…

Пусть Задача линейного программирования — базисный план задачи (1.6) с базисом Задача линейного программирования и базисной матрицей Задача линейного программирования. Сформируем Задача линейного программирования-вектор Задача линейного программирования и подсчитаем Задача линейного программирования-вектор потенциалов Задача линейного программирования по правилу

Задача линейного программирования

Вычислим оценки

Задача линейного программирования

Отметим, что по построению

Задача линейного программирования

Для базисного плана Задача линейного программирования справедливы следующие утверждения.

Утверждение 1. (Признак оптимальности базисного плана.) Базисный план х является решением задачи (1.6), если

Задача линейного программирования

Утверждение 2. (Достаточное условие неограниченности сверху целевой функции.) Если существует индекс Задача линейного программирования, для которого Задача линейного программирования и все компоненты Задача линейного программирования, вектора

Задача линейного программирования

не положительны, то целевая функция задачи (1.6) не ограничена сверху на множестве планов.

Утверждение 3. (Возможность строгого улучшения плана.) Пусть Задача линейного программирования — невырожденный базисный план задачи (1.6) и для некоторого Задача линейного программирования справедливы соотношения

Задача линейного программирования

где вектор Задача линейного программирования определен по формуле (1.10). Тогда существует базисный план Задача линейного программирования, для которого Задача линейного программирования.

Компоненты нового базисного плана Задача линейного программирования и соответствующий ему базис Задача линейного программирования строятся по правилу

Задача линейного программирования

где

Задача линейного программирования

любой индекс из множества

Задача линейного программирования

Задача №3

Исследовать на оптимальность план Задача линейного программирования задачи

Задача линейного программирования

Решение:

В рассматриваемой задаче векторы условий Задача линейного программирования имеют вид

Задача линейного программирования

План Задача линейного программирования является невырожденным базисным планом с базисом Задача линейного программирования. Данному базису соответствует базисная матрица

Задача линейного программирования

Для проверки плана Задача линейного программирования на оптимальность подсчитаем вектор потенциалов Задача линейного программирования:

Задача линейного программирования

и оценки

Задача линейного программирования
Задача линейного программирования

Поскольку все оценки Задача линейного программирования то, согласно утверждению 1, план Задача линейного программирования является оптимальным.

Возможно эта страница вам будет полезна:

Помощь по математическому программированию

Симплекс-метод. Общая итерация

К оглавлению…

Пусть Задача линейного программирования — некоторый базисный план задачи (1.6) с базисом Задача линейного программирования. В результате исследования, основанного на утверждениях 1-3, выясняется либо 1) оптимальность плана Задача линейного программирования либо 2) неразрешимость задачи (1.6) в силу неограниченности сверху целевой функции на множестве планов, либо 3) возможность перехода к новому базисному плану Задача линейного программирования, для которого Задача линейного программирования.

Последовательный переход от одного базисного плана к «лучшему» базисному плану вплоть до получения оптимального плана составляет основную идею симплекс-метода.

Для реализации симплекс-метода кроме исходных данных задачи (1.6) (векторов Задача линейного программирования и матрицы Задача линейного программирования) на каждой итерации необходимо знать следующие параметры:

текущий базисный план Задача линейного программирования (достаточно знать только его базисные компоненты Задача линейного программирования );

соответствующее плану Задача линейного программирования множество базисных индексов Задача линейного программирования; Задача линейного программирования — матрицу Задача линейного программирования обратную к базисной матрице Задача линейного программирования.

Опишем общую итерацию симплекс-метода по шагам. Шаг 1. Вычислим вектор потенциалов Задача линейного программирования, где Задача линейного программирования, и оценки

Задача линейного программирования

Шаг 2. Если Задача линейного программирования то STOP: вектор Задача линейного программирования является оптимальным планом задачи (1.6). В противном случае переходим к шагу 3.

Шаг 3. Выберем индекс Задача линейного программирования, для которого Задача линейного программирования. Построим вектор Задача линейного программирования. Если Задача линейного программирования, то STOP: задача (1.6) не имеет решения в силу неограниченности сверху целевой функции на множестве планов. В противном случае перейдем к шагу 4.

Шаг 4. Найдем минимум

Задача линейного программирования

и выберем индекс Задача линейного программирования, для которого Задача линейного программирования.

Шаг 5. Построим новый базисный план Задача линейного программирования соответствующий ему базис Задача линейного программирования по правилам

Задача линейного программирования

Шаг 6. Вычислим матрицу Задача линейного программирования, обратную к новой базисной матрице Задача линейного программирования, по формуле Задача линейного программирования, где матрица Задача линейного программирования, отличается от единичной Задача линейного программирования -матрицы только Задача линейного программирования-м столбцом, который имеет вид

Задача линейного программирования

Задача линейного программирования — единичный Задача линейного программирования-вектор с единицей на Задача линейного программирования-м месте.

Переходим к следующей итерации, исходя из новых плана Задача линейного программирования, базиса Задача линейного программирования и матрицы Задача линейного программирования, обратной к новой базисной матрице Задача линейного программирования.

Замечания. 1. На шаге 3 выбирается индекс Задача линейного программирования, для которого Задача линейного программирования. В общем случае существует несколько индексов, удовлетворяющих этому условию. При численной реализации симплекс-метода для выбора Задача линейного программирования можно использовать дополнительные «уточняющие» правила, например, следующие:

Задача линейного программирования

На шаге 4 выбирается индекс Задача линейного программирования или Задача линейного программирования для которого Задача линейного программирования. В общем случае этот выбор может оказаться неоднозначным. Можно использовать дополнительные уточняющие правила, например, следующие:

Задача линейного программирования

В современных версиях симплекс-метода для нахождения вектора потенциалов Задача линейного программирования (см. шаг 1) и вектора Задача линейного программирования (см. шаг 3) решаются системы Задача линейного программирования и Задача линейного программирования, соответственно. Для эффективного решения последних используется Задача линейного программирования-разложение базисной матрицы Задача линейного программирования.

Легко подсчитать, что приращение целевой функции при переходе от начального базисного плана Задача линейного программирования к новому базисному плану Задача линейного программирования равно:

Задача линейного программирования

По построению,

Задача линейного программирования

Следовательно, при Задача линейного программирования происходит «строгое улучшение» плана: Задача линейного программирования. Из описания шага 4 видно, что в случае невырожденности начального базисного планаЗадача линейного программирования всегда верно неравенство Задача линейного программирования.

В случае, когда базисный план Задача линейного программирования (с базисом Задача линейного программирования) является вырожденным, может реализоваться ситуация: Задача линейного программирования. При этом мы получаем Задача линейного программирования.

В этом случае не происходит улучшения целевой функции, но итерация может оказаться полезной, так как изменяется базис и новый базис может быть ближе к оптимальному базису, чем старый.

Задача №4

Решить задачу ЛП симплекс-методом

Задача линейного программирования

Решение:

Для данной задачи Задача линейного программирования а векторы Задача линейного программирования и матрица Задача линейного программирования имеют вид Задача линейного программирования;

Задача линейного программирования

В качестве начального базисного плана возьмем вектор Задача линейного программирования, которому соответствует базисное множество Задача линейного программирования и базисная матрица

Задача линейного программирования

Используя

Очевидно, что

Задача линейного программирования

Используя

Задача линейного программирования

осуществим первую итерацию симплекс-метода. Шаг 1. Вычислим вектор потенциалов

Задача линейного программирования

и оценки

Задача линейного программирования
Задача линейного программирования

Шаг 2. Поскольку среди оценок Задача линейного программирования есть отрицательные, то переходим к шагу 3.

Шаг 3. Выберем в качестве индекса Задача линейного программирования, для которого Задача линейного программирования, индекс 2, т.е. Задача линейного программирования. Построим вектор

Задача линейного программирования
Задача линейного программирования

Поскольку среди компонент вектора Задача линейного программирования есть положительные, то перейдем к шагу 4. Шаг 4. Найдем минимум

Задача линейного программирования

Очевидно, что в данном примере в качестве индекса Задача линейного программирования, для которого Задача линейного программирования можно взять только индекс 1, т.е.

Задача линейного программирования

Шаг 5. Построим новый базисный план

Задача линейного программирования

и соответствующий ему базис Задача линейного программирования по правилам

Задача линейного программирования

Шаг 6. Построим матрицу

Задача линейного программирования

и найдем матрицу

Задача линейного программирования

обратную к новой базисной матрице Задача линейного программированияЗадача линейного программирования. Переходим ко второй итерации, исходя из новых плана Задача линейного программирования, базиса Задача линейного программирования и матрицы Задача линейного программирования.

Осуществим вторую итерацию.

Шаг 1. Вычислим вектор потенциалов

Задача линейного программирования

и оценки

Задача линейного программирования
Задача линейного программирования

Шаг 2. Поскольку все оценки Задача линейного программирования, неотрицательны, то алгоритм заканчивает свою работу: вектор Задача линейного программирования является оптимальным планом рассматриваемой задачи.

Возможно эта страница вам будет полезна:

Задачи математического программирования

Зацикливание. Конечные модификации симплекс- метода

К оглавлению…

Итерацию

Задача линейного программирования

симплекс-метода назовем невырожденной, если Задача линейного программирования.

Ясно, что итерация Задача линейного программирования может оказаться вырожденной только в том случае, если базисный план Задача линейного программирования вырожденный, причем в случае вырожденности итерации справедливы соотношения:

Задача линейного программирования

Теорема. При любом выборе начального базисного плана Задача линейного программирования симплекс-метод за конечное число итераций строит оптимальный базисный план задачи (1.6) либо обнаруживает неограниченность сверху ее целевой функции на множестве планов, если в процессе его реализации не встречаются вырожденные итерации.

При наличии вырожденных итераций при реализации симплекс-метода может возникнуть такая ситуация, когда начиная с некоторого вырожденного базисного плана Задача линейного программирования мы осуществляем последовательность вырожденных итераций

Задача линейного программирования

в которых меняются только базисы Задача линейного программирования базисного плана Задача линейного программирования, причем при некотором конечном Задача линейного программирования имеет место равенство Задача линейного программирования. Очевидно, что если мы продолжим операции симплекс-метода исходя из Задача линейного программирования, то опять получим ту же последовательность итерации (1.12) и т. д. Такое явление получило название зацикливания.

Первоначально считалось, что зацикливание — крайне редкое явление. Однако позже было замечено, что вероятность возникновения зацикливания увеличивается с ростом размеров задачи. Кроме того, зацикливание является типичным явлением для задач ЛП, возникающих при аппроксимации задач целочисленного программирования. В связи с этим возникла необходимость в разработке специальных приемов борьбы с зацикливанием. К настоящему времени известно много таких приемов. Опишем два из них.

  • Стратегия возмущения (метод Чарнса). Предположим, что в задаче (1.6) мы возмутили вектор правых частей Задача линейного программирования, заменив его на Задача линейного программирования:
Задача линейного программирования

где Задача линейного программирования — некоторая невырожденная Задача линейного программирования — матрица со столбцами Задача линейного программирования — достаточно малое число.

Возмущения в векторе Задача линейного программирования вызовут возмущения в базисных компонентах Задача линейного программирования каждого базисного плана следующим образом:

Задача линейного программирования

Матрица Задача линейного программирования должна быть такой, что на первой итерации вектор Задача линейного программирования должен быть строго положительным при достаточно малых Задача линейного программирования. Для этого достаточно положить Задача линейного программирования, где Задача линейного программирования — базисная матрица, соответствующая начальному базису Задача линейного программирования. Тогда для начального базисного плана имеем

Задача линейного программирования

Предположим, что на текущей итерации имеется базисный план Задача линейного программирования возмущенной задачи, для которого справедливы неравенства Задача линейного программирования при достаточно малых Задача линейного программирования. Согласно данным подразд. 1.4, новый базисный план Задача линейного программирования, построенный в результате одной итерации симплекс-метода из Задача линейного программирования, будет также невырожденным, если не существует таких двух базисных индексов Задача линейного программирования что Задача линейного программирования и

Задача линейного программирования

для всех достаточно малых Задача линейного программирования.

Последние соотношения могут иметь место только в том случае, если Задача линейного программирования-я и Задача линейного программирования-я строки матрицы Задача линейного программирования линейно зависимы. Однако это противоречит тому, что Задача линейного программирования. Значит, соотношения (1.14) не могут иметь места и, следовательно, новый базисный план Задача линейного программирования возмущенной задачи будет невырожденным при достаточно малых Задача линейного программирования.

Таким образом, мы показали, что при достаточно малых Задача линейного программирования все итерации симплекс-метода для задачи с возмущенным вектором Задача линейного программирования будут невырожденными и, следовательно, для возмущенной задачи симплекс- метод будет конечным. Кроме того справедлива следующая теорема.

Теорема. Существует такое Задача линейного программирования, что для любого Задача линейного программирования каждому базисному плану возмущенной задачи, порожденному базисом Задача линейного программирования, соответствует базисный план (невозмущенной) исходной задачи, порожденный тем же базисом Задача линейного программирования, а из оптимальности базиса Задача линейного программирования в возмущенной задаче следует его оптимальность в исходной задаче.

Покажем, как описанные выше результаты можно использовать для предотвращения зацикливания в исходной задаче (1.6).

Недостатком описанных выше рассуждений является то, что они верны только при достаточно малых Задача линейного программирования и заранее невозможно указать конкретное значение Задача линейного программирования. Однако существуют правила (лексико-графическая стратегия), которые позволяют «мысленно» осуществить процедуру решения возмущенной задачи без явного выбора значения параметра Задача линейного программирования.

Пусть в начале текущей итерации для исходной задачи есть базисный план Задача линейного программирования, базис Задача линейного программирования и соответствующая ему базисная матрица Задача линейного программирования. Очевидно, что при достаточно малых Задача линейного программирования базис Задача линейного программирования порождает базисный план Задача линейного программирования, где Задача линейного программирования имеет вид (1.13), возмущенной задачи. Предположим, что мы осуществляем итерацию симплекс-метода для исходной и возмущенной задач, исходя из базисных планов Задача линейного программирования и Задача линейного программирования.

Ясно, что для обеих задач шаги 1-3 итерации будут полностью совпадать. Значит, совпадут и индексы Задача линейного программирования, подлежащие вводу в базис. Перейдем к шагу 4, на котором определяется индекс Задача линейного программирования, подлежащий выводу из базиса Задача линейного программирования. Для возмущенной задачи индекс Задача линейного программирования однозначно определяется из соотношений

Задача линейного программирования

где Задача линейного программирования — достаточно малое число.

Легко проверить, что найти единственный индекс Задача линейного программирования определяемый условием (1.15), можно по следующему правилу.

Положим

Задача линейного программирования

и построим множества Задача линейного программирования, по рекуррентным правилам

Задача линейного программирования

где

Задача линейного программирования

По построение,

Задача линейного программирования

Обозначим через Задача линейного программирования наименьший индекс Задача линейного программирования, при котором Задача линейного программирования:

Задача линейного программирования

Пусть Задача линейного программирования. Тогда индекс Задача линейного программирования и совпадает с индексом, определяемым соотношениями (1.15).

Ясно, что для исходной задачи любой индекс вида Задача линейного программирования, где Задача линейного программирования можно взять в качестве индекса, выводимого из базиса. Согласно (1.18) Задача линейного программирования, следовательно, индекс Задача линейного программирования можно выводить из базиса в исходной задаче. Таким образом, в качестве нового базиса для исходной задачи можно взять базис

Задача линейного программирования

где индекс Задача линейного программирования однозначно определяется по правилам (1.16)-(1.19). (Для возмущенной задачи новый базис (1.20) является единственно возможным).

Из сказанного выше следует, что симплекс-метод будет конечным и для исходной задачи (1.6), если на шаге 4 индекс Задача линейного программирования, подлежащий выводу из базиса, определять по правилам (1.16), (1.17), (1.19).

  • Правило Блэнда. В 1977 г. Р. Блэнд предложил очень простое правило предотвращения зацикливания в симплекс- методе. Это правило сводится к следующему.

При реализации итерации симплекс-метода на шаге 3 индекс Задача линейного программирования, подлежащий вводу в новый базис, однозначно определяется по правилу

Задача линейного программирования

а на шаге 4 индекс Задача линейного программирования подлежащий выводу из базиса, однозначно определяется соотношениями

Задача линейного программирования

При использовании дополнительных правил (1.21), (1.22) симплекс-метод для любой задачи ЛП (с заданным начальным базисным планом) за конечное число итераций строит оптимальный базисный план либо обнаруживает неограниченность сверху целевой функции на множестве планов.

Возможно эта страница вам будет полезна:

Примеры решения задач по линейному программированию

Первая фаза симплекс-метода

К оглавлению…

Все предыдущие утверждения и операции симплекс-метода были справедливы в предположении, что для задачи в канонической форме (1.6) выполнено условие (1.8).

Понятно, что для произвольной задачи (1.6) это условие может нарушаться. Поэтому, прежде чем применять описанный симплекс-метод необходимо исходную задачу (1.6) привести к такому виду, для которого выполняются соотношения (1.8).

Кроме того, из описания общей итерации симплекс-метода видно, что для начала его работы необходимо знать начальный базисный план Задача линейного программирования и начальный набор базисных индексов Задача линейного программирования, для которых выполняются соотношения:

Задача линейного программирования

Проблема нахождения такой начальной информации может оказаться нетривиальной. Действительно, в общем случае по трудоемкости это проблема эквивалентна построению решения некоторой задачи линейного программирования. Для преодоления указанной трудности используется двухфазный симплекс-метод, общая схема которого состоит в следующем.

На первой фазе формируется вспомогательная задача ЛП, которая отличается от исходной задачи (1.6). Вспомогательная задача строится таким образом, что для нее выполняется условие (1.8), легко строится начальный базисный план и она имеет решение. Анализ решения вспомогательной задачи позволяет:

1) определить, совместны ли ограничения исходной задачи (1.6);

2) проверить, выполняется ли условие (1.8) для исходной задачи (1.6) и в случае его нарушения обнаружить линейно зависимые основные ограничения и удалить их из условий задачи;

3) в случае совместности ограничений задачи (1.6) построить для нее начальный базисный план Задача линейного программирования и базис Задача линейного программирования.

Если анализ решения вспомогательной задачи закончился построением начального базисного плана для исходной задачи, то переходим ко второй фазе алгоритма. Вторая фаза состоит в решении исходной задачи описанным выше симплекс-методом, при этом в качестве начальной используется информация, полученная на первой фазе.

Опишем подробнее первую фазу алгоритма. Без ограничения общности будем считать, что в задаче (1.6) вектор Задача линейного программирования удовлетворяет неравенству Задача линейного программирования.

Тогда задачу первой фазы можно записать в виде

Задача линейного программирования

где Задача линейного программирования — исходные переменные, Задача линейного программирования — искусственные переменные, Задача линейного программирования — единичная матрица, Задача линейного программирования.

Легко проверить, что вектор Задача линейного программирования с компонентами

Задача линейного программирования

является базисным планом задачи (1.23) с базисом

Задача линейного программирования

и базисной матрицей Задача линейного программирования.

Решим задачу (1.23) симплекс-методом, описанным в подразд. 1.4, используя в качестве начального базисный план (1.24). Поскольку целевая функция задачи (1.23) ограничена сверху на множестве ее планов Задача линейного программирования, то через конечное число итераций будет построен оптимальный базисный план Задача линейного программирования задачи (1.23) и соответствующий ему базис Задача линейного программирования. Справедлива следующая теорема

Теорема. Ограничения исходной задачи (1.6) совместны тогда и только тогда, когда компонента Задача линейного программирования оптимального базисного плана задачи (1.23) равна нулю.

Проведем анализ решения задачи (1.23). Возможны случаи:

Задача линейного программирования

Пусть реализовался случай 1. Прекращаем исследование исходной задачи (1.6), так как согласно теореме она не имеет планов.

Рассмотрим случай 2. Легко проверить, что вектор Задача линейного программирования с базисным множеством Задача линейного программирования является базисным планом задачи (1.6). Переходим ко второй фазе алгоритма, исходя из этого плана.

Исследуем случай 3. Ясно, что вектор Задача линейного программирования является планом задачи (1.6), но множество Задача линейного программирования не является его базисом для задачи (1.6). Попытаемся построить базис для плана в задаче (1.6).

Пусть

Задача линейного программирования

Обозначим

Задача линейного программирования

Возможны под случаи:

Задача линейного программирования

Если реализовался подслучай а, то оптимальному плану Задача линейного программирования задачи (1.23) припишем новый базис

Задача линейного программирования

Очевидно, что по построению,

Задача линейного программирования

Снова проверяем, какая из ситуаций, 2 или 3, имеет место для оптимального плана Задача линейного программирования задачи (1.23) и нового базиса (1.26).

Подслучай б означает, что в исходной задаче (1.6) основное ограничение с индексом Задача линейного программирования является линейно зависимым с остальными основными ограничениями этой задачи. Множество планов задачи (1.6) не изменится, если мы удалим это ограничение, т.е. заменим множество индексов Задача линейного программирования на Задача линейного программирования. Для преобразованной задачи (1.6) вспомогательная задача первой фазы получится из задачи (1.23) после удаления ограничения с индексом Задача линейного программирования и искусственной переменной Задача линейного программирования, т.е. заменой множеств Задача линейного программирования и Задача линейного программирования на

Задача линейного программирования

Очевидно, что для новой задачи первой фазы вектор

Задача линейного программирования

является оптимальным базисным планом с базисом

Задача линейного программирования

для которого

Задача линейного программирования

Для плана

Задача линейного программирования

и новых множеств Задача линейного программирования вновь проверяем, какая из ситуаций,

2 или 3, имеет место.

Ясно, что не более чем через Задача линейного программирования шагов из основных ограничений задачи (1.6) будут исключены все линейно зависимые ограничения и она будет сведена к задаче

Задача линейного программирования

где

Задача линейного программирования

При этом для задачи (1.27) будет построен базисный план Задача линейного программирования с некоторым базисом

Задача линейного программирования

Дальнейшее решение задачи (1.27) осуществляем симплекс-методом, описанным в подразд. 1.4, используя в качестве начальных построений базисный план Задача линейного программирования с базисом Задача линейного программирования.

Возможно эта страница вам будет полезна:

Решение задач по линейному программированию

Теория двойственности в линейном программировании

К оглавлению…

Определение двойственной задачи. Соотношения двойственности

Рассмотрим задачу линейного программирования, заданную в произвольной форме записи:

Задача линейного программирования
Задача линейного программирования

где Задача линейного программирования — некоторые конечные множества индексов. Задачу линейного программирования

Задача линейного программирования

назовем двойственной по отношению к задаче (2.1). При этом задача (2.1) считается прямой.

Из приведенного определения следует, что для задачи линейного программирования в нормальной форме

Задача линейного программирования

двойственной является задача

Задача линейного программирования

а для задачи в канонической форме

Задача линейного программирования

двойственная задача имеет вид

Задача линейного программирования

Легко проверить, что если в качестве исходной взять задачу линейного программирования (2.2), то двойственной к ней будет задача (2.1).

Сравнивая пары двойственных задач (2.1) и (2.2), приходим к следующему правилу построения двойственной задачи:

  • Двойственная задача является задачей минимизации линейной формы, коэффициенты которой совпадают с коэффициентами вектора условий прямой задачи.
  • Каждому Задача линейного программирования-му основному ограничению прямой задачи соответствует Задача линейного программирования-я переменная Задача линейного программирования двойственной задачи. При этом для Задача линейного программирования-й переменной Задача линейного программирования двойственной задачи выполняются соотношения:

а) она не имеет ограничений на знак, если Задача линейного программирования-е основное ограничение прямой задачи имело вид равенства;

б) Задача линейного программирования, если Задача линейного программирования-е основное ограничение прямой задачи имело вид неравенства Задача линейного программирования.

Каждой Задача линейного программирования-й переменной Задача линейного программирования прямой задачи соответствует Задача линейного программирования-е основное ограничение двойственной задачи. При этом вид Задача линейного программирования-го основного ограничения двойственной задачи определяется условиями:

а) оно имеет вид равенства, если переменная Задача линейного программирования в прямой задаче не имеет ограничений на знак;

б) оно имеет вид неравенства Задача линейного программирования если в прямой задаче переменная Задача линейного программирования имела ограничение Задача линейного программирования на знак.

Рассмотрим общую задачу линейного программирования (2.1) и двойственную к ней задачу (2.2). Назовем эти задачи парой двойственных задач.

Теорема. Если одна из задач двойственной пары имеет решение, то другая задача также имеет решение. При этом для любых оптимальных планов

Задача линейного программирования

имеет место равенство

Задача линейного программирования

Следствие 1. Для разрешимости одной из задач двойственной пары необходимо и достаточно, чтобы каждая из задач этой пары имела хотя бы один план.

Следствие 2. Для того чтобы одна из задач двойственной пары имела планы, а множество планов другой задачи было пусто, необходимо и достаточно, чтобы целевая функция первой задачи была не ограничена на множестве ее планов.

Следствие 3. Для любых планов

Задача линейного программирования

задач двойственной пары справедливо неравенство

Задача линейного программирования

Следствие 4. Для оптимальности планов

Задача линейного программирования
Задача линейного программирования

задач двойственной пары необходимо и достаточно выполнение равенства

Задача линейного программирования

Задача №5

Записать задачу, двойственную к данной

Задача линейного программирования

Решение:

Чтобы записать задачу, двойственную к данной, приведем систему к виду (2.1)

Задача линейного программирования

Теперь воспользуемся определением (2.2) и запишем задачу, двойственную к данной

Задача линейного программирования

Базисный двойственный базисный план

Далее для определенности будем рассматривать пару двойственных задач (2.5), (2.6), в которой прямая задача имеет каноническую форму записи (2.5) с матрицей

Задача линейного программирования

Вектор Задача линейного программирования назовем двойственным планом, если Задача линейного программирования.

Двойственный план Задача линейного программирования называется базисным двойственным планом, если существует такое множество Задача линейного программирования что

Задача линейного программирования

Как и раньше, множество Задача линейного программирования будем называть базисом или множеством базисных индексов, матрицу Задача линейного программирования — базисной матрицей.

Отметим, что двойственный базисный план однозначно восстанавливается по заданному базису:

Задача линейного программирования

Базисный двойственный план у считается невырожденным, если

Задача линейного программирования

Пусть Задача линейного программирования — базисный двойственный план с базисом Задача линейного программирования. Задача линейного программирования-вектор Задача линейного программирования с компонентами, построенными по правилу

Задача линейного программирования

назовем псевдопланом задачи (2.5), соответствующим базису Задача линейного программирования.

Утверждение 1. Если среди базисных компонент псевдоплана Задача линейного программирования нет отрицательных, т. е.

Задача линейного программирования

то псевдоплан Задача линейного программирования — оптимальный план

задачи (2.5). При этом базисный двойственный план Задача линейного программирования, определяющий псевдоплан Задача линейного программирования, является решением задачи (2.6).

Утверждение 2. Пусть среди базисных компонент Задача линейного программированияЗадача линейного программированияпсевдоплана Задача линейного программирования имеется отрицательная компонента Задача линейного программирования и выполняются неравенства

Задача линейного программирования

Тогда целевая функция двойственной задачи не ограничена снизу на множестве своих планов, а ограничения прямой задачи несовместны.

Утверждение 3. Пусть базисный двойственный план Задача линейного программирования (с базисом Задача линейного программирования) является невырожденным. Если среди базисных компонент псевдоплана Задача линейного программирования, построенного по Задача линейного программирования, есть отрицательная компонента Задача линейного программирования, для которой Задача линейного программирования, то можно перейти к новому базисному двойственному плану Задача линейного программирования с лучшим значением двойственной целевой функции: Задача линейного программирования.

Новый базисный двойственный план Задача линейного программирования и соответствующий ему базис Задача линейного программирования строятся по плану

Задача линейного программирования

где

Задача линейного программирования

произвольный индекс из множества

Задача линейного программирования

единичный Задача линейного программирования-вектор с единицей на Задача линейного программирования-м месте.

Возможно эта страница вам будет полезна:

Методы решения задач линейного программирования

Двойственный симплекс-метод

Метод решения канонической задачи линейного программирования, рассмотренный в разд. 1, впредь будем называть прямым симплекс-методом.

Опишем двойственный симплекс-метод, который является специальным алгоритмом построения оптимального плана задачи линейного программирования (2.5) посредством преобразования планов двойственной задачи (2.6).

Для решения задачи (2.5) двойственным симплекс-методом, кроме исходных данных Задача линейного программирования на каждой итерации необходимо знать следующие параметры:

1) текущий базисный двойственный план Задача линейного программирования;

2) соответствующий двойственному плану Задача линейного программирования базис

Задача линейного программирования

3) Задача линейного программирования-матрицу Задача линейного программирования обратную к базисной матрице

Задача линейного программирования

Опишем общую итерацию двойственного симплекс-метода по шагам. Шаг 1. Найдем базисные компоненты псевдоплана Задача линейного программирования, соответствующего базису

Задача линейного программирования

Шаг 2. Если выполняются неравенства

Задача линейного программирования

то STOP: вектор

Задача линейного программирования

является оптимальным планом задачи (2.5), а вектор Задача линейного программирования — оптимальным планом задачи (2.6). В противном случае перейдем к шагу 3.

Шаг 3. Среди базисных индексов

Задача линейного программирования

выберем индекс Задача линейного программирования, для которого Задача линейного программирования. Подставим Задача линейного программирования-вектор Задача линейного программирования и числа Задача линейного программирования, по правилам

Задача линейного программирования

Если Задача линейного программирования, то STOP: ограничения исходной задачи (2.5) несовместны, а целевая функция двойственной задачи (2.6) не ограничена снизу на множестве ее планов. В противном случае перейдем к шагу 4. Шаг 4. Найдем минимум

Задача линейного программирования

и выберем в качестве индекса Задача линейного программирования любой элемент из множества

Задача линейного программирования

Шаг 5. Построим новый базисный двойственный план Задача линейного программирования и соответствующий ему базис Задача линейного программирования по правилам

Задача линейного программирования

Шаг 6. Вычислим матрицу Задача линейного программирования, обратную к новой базисной матрице

Задача линейного программирования

по правилам, описанным на шаге 6 итерации прямого симплекс-метода (см. подразд. 1.4).

Переходим к следующей итерации, исходя из новых значений для базисного двойственного плана Задача линейного программирования, базиса Задача линейного программирования и матрицы Задача линейного программирования.

Замечания. 1. На шаге 3 выбор индекса Задача линейного программирования и на шаге 4 выбор индекса Задача линейного программирования могут оказаться неоднозначным. Как и в прямом симплекс-методе, это может привести к зацикливанию алгоритма. Для предотвращения зацикливания рекомендуется использовать дополнительные правила, аналогичные приведенным в подразд. 1.6. Например, правило Блэнда для двойственного симплекс-метода сводится к следующему: на шаге 3 индекс Задача линейного программирования однозначно определяется условием

Задача линейного программирования

а на шаге 4 индекс Задача линейного программирования однозначно определяется соотношением

Задача линейного программирования

Легко проверить, что если базисный двойственный план Задача линейного программирования является невырожденным, то для нового базисного плана Задача линейного программирования справедливо неравенство Задача линейного программирования. (В общем случае верно неравенство Задача линейного программирования).

Проблема построения начального базисного двойственного плана Задача линейного программирования является нетривиальной. Для ее решения по аналогии с разделом 1 можно разработать двухфазный двойственный симплекс-метод.

Задача №6

Решить задачу ЛП двойственным симплекс-методом

Задача линейного программирования

приняв в качестве начального базисного двойственного плана вектор

Задача линейного программирования

и базисное множество Задача линейного программирования.

Решение:

Базису Задача линейного программирования соответствует базисная матрица

Задача линейного программирования

Построим матрицу

Задача линейного программирования

Используя

Задача линейного программирования

и осуществим первую итерацию.

Шаг 1. Найдем базисные компоненты псевдоплана Задача линейного программирования, соответствующего базису Задача линейного программирования:

Задача линейного программирования

Шаг 2. Условие

Задача линейного программирования

не выполняется, следовательно, переходим к шагу 3.

Шаг 3. В качестве индекса

Задача линейного программирования

для которого Задача линейного программирования, выберем индекс Задача линейного программирования. Подсчитаем вектор Задача линейного программирования и числа Задача линейного программирования, Задача линейного программирования:

Задача линейного программирования

Поскольку среди чисел Задача линейного программирования есть отрицательные, то переходим к шагу 4.

Шаг 4. Найдем минимум

Задача линейного программирования

В данном примере в качестве индекса Задача линейного программирования можно выбрать только индекс Задача линейного программирования.

Шаг 5. Построим новый базисный двойственный план Задача линейного программирования и соответствующий ему базис Задача линейного программирования по правилам

Задача линейного программирования

Шаг 6. По правилам, описанным на шаге 6 прямого симплекс-метода, вычислим матрицу

Задача линейного программирования

обратную к новой базисной матрице

Задача линейного программирования

Переходим ко второй итерации, исходя из новых значений для базисного двойственного плана Задача линейного программирования, базиса

Задача линейного программирования

и матрицы Задача линейного программирования.

Осуществим вторую итерацию.

Шаг 1. Найдем базисные компоненты псевдоплана Задача линейного программирования, соответствующего базису Задача линейного программирования:

Задача линейного программирования

Шаг 2. Поскольку среди компонент

Задача линейного программирования

есть отрицательные, то переходим к шагу 3.

Шаг 3. На данной итерации в качестве индекса Задача линейного программирования, для которого Задача линейного программирования, можно выбрать только индекс Задача линейного программирования. Найдем

Задача линейного программирования

Поскольку среди чисел Задача линейного программирования есть отрицательные, то переходим к шагу 4.

Шаг 4. Найдем

Задача линейного программирования

В качестве индекса Задача линейного программирования можно выбрать только индекс Задача линейного программирования.

Шаг 5. Построим новый базисный двойственный план Задача линейного программирования и соответствующий ему базис Задача линейного программирования:

Шаг 6. Вычислим матрицу

Задача линейного программирования

обратную к новой базисной

Задача линейного программирования

Переходим к третьей итерации, исходя из новых значений для базисного двойственного плана Задача линейного программирования, базиса Задача линейного программирования и матрицы Задача линейного программирования. Опишем третью итерацию.

Шаг 1. Найдем базисные компоненты псевдоплана Задача линейного программирования, соответствующего базису Задача линейного программирования:

Задача линейного программирования

Шаг 2. Все компоненты Задача линейного программирования положительны, следовательно, вектор

Задача линейного программирования

является оптимальным планом рассматриваемой задачи, а вектор Задача линейного программирования — ее оптимальным двойственным планом. Задача решена.

Возможно эти страницы вам будут полезны: