Алгоритм симплекс-метода для задачи на минимум

Шаг 0. Подготовительный этап.

Приводим задачу ЛП к специальной форме (15).

Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме:

  B Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
.. .. …………
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
.. .. …………
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

Заметим, что этой таблице соответствует допустимое базисное решение Алгоритм симплекс-метода для задачи на минимум - student2.ru задачи (15). Значение целевой функции на этом решении Алгоритм симплекс-метода для задачи на минимум - student2.ru

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

Если среди элементов индексной строки симплекс – таблицы Алгоритм симплекс-метода для задачи на минимум - student2.ru нет ни одного положительного элемента то Алгоритм симплекс-метода для задачи на минимум - student2.ru , оптимальное решение задачи ЛП найдено: Алгоритм симплекс-метода для задачи на минимум - student2.ru . Алгоритм завершает работу.

Шаг 3. Проверка на неразрешимость

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

Шаг 4. Выбор ведущего столбца q

Среди элементов Алгоритм симплекс-метода для задачи на минимум - student2.ru выбираем максимальный положительный элемент Алгоритм симплекс-метода для задачи на минимум - student2.ru .Этот столбец объявляем ведущим (разрешающим).

Шаг 5. Выбор ведущей строки p

Среди положительных элементов столбца Алгоритм симплекс-метода для задачи на минимум - student2.ru находим элемент Алгоритм симплекс-метода для задачи на минимум - student2.ru , для которого выполняется равенство

Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Строку p объявляем ведущей (разрешающей). Элемент Алгоритм симплекс-метода для задачи на минимум - student2.ru объявляем ведущим (разрешающим).

Шаг 6. Преобразование симплексной таблицы

Составляем новую симплекс-таблицу, в которой:

а) вместо базисной переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru записываем Алгоритм симплекс-метода для задачи на минимум - student2.ru , вместо небазисной пере менной Алгоритм симплекс-метода для задачи на минимум - student2.ru записываем Алгоритм симплекс-метода для задачи на минимум - student2.ru ;

б) ведущий элемент заменяем обратной величиной Алгоритм симплекс-метода для задачи на минимум - student2.ru ;

в) все элементы ведущего столбца (кроме Алгоритм симплекс-метода для задачи на минимум - student2.ru ) умножаем на Алгоритм симплекс-метода для задачи на минимум - student2.ru ;

г) все элементы ведущей строки (кроме Алгоритм симплекс-метода для задачи на минимум - student2.ru ) умножаем на Алгоритм симплекс-метода для задачи на минимум - student2.ru ;

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

Из элемента вычитается произведение трех сомножителей:

первый – соответствующий элемент ведущего столбца;

второй – соответствующий элемент ведущей строки;

третий – обратная величина ведущего элемента Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2.

Алгоритм симплекс-метода для задачи на максимум

Алгоритм симплекс-метода для задачи на максимум отличается от алгоритма для задачи на минимум только знаками индексной строки коэффициентов в целевой функции Алгоритм симплекс-метода для задачи на минимум - student2.ru , а именно:

На шаге 2: Алгоритм симплекс-метода для задачи на минимум - student2.ru :

На шаге 3 Алгоритм симплекс-метода для задачи на минимум - student2.ru . Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4: Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Пример решения задачи симплекс-методом

Решить задачу, записанную в виде (15).

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Составим симплексную таблицу:

  Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L
Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение Алгоритм симплекс-метода для задачи на минимум - student2.ru не является оптимальным. Значение целевой функции для этого базиса L=0.

Выбираем ведущий столбец – это столбец, соответствующий переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Выбираем ведущую строку. Для этого находим Алгоритм симплекс-метода для задачи на минимум - student2.ru . Следовательно, ведущая строка соответствует переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Проводим преобразование симплексной таблицы, вводя переменную Алгоритм симплекс-метода для задачи на минимум - student2.ru в базис и выводя переменную Алгоритм симплекс-метода для задачи на минимум - student2.ru из базиса. Получим таблицу:

  Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -2 -2
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид Алгоритм симплекс-метода для задачи на минимум - student2.ru . Значение целевой функции на этом базисе L= -2.

Ведущий столбец здесь – столбец, соответствующий переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru . Ведущая строка – строка, соответствующая переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru . После проведения преобразований получим симплексную таблицу:

  Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

Еще одна итерация завершена. Переходим к новой итерации.

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

Метод искусственного базиса

Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:

Алгоритм симплекс-метода для задачи на минимум - student2.ru (16)

Характерная особенность задачи (16) – известное базисное допустимое решение

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Чтобы применить симплекс-метод для решения задачи ЛП в произвольной форме, необходимо привести эту задачу к виду (16), т. е. выделить начальное допустимое базисное решение. Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса и состоит в следующем [1,2,3].

Вычислительная схема метода искусственного базиса

Шаг 1. Приводим задачу ЛП к канонической форме с неотрицательными правыми частями Алгоритм симплекс-метода для задачи на минимум - student2.ru :

Алгоритм симплекс-метода для задачи на минимум - student2.ru (17)

Шаг 2. В каждую i-ю строку ограничений (17) вводим искусственную неотрицательную переменную Алгоритм симплекс-метода для задачи на минимум - student2.ru и строим вспомогательную задачу ЛП вида:

Алгоритм симплекс-метода для задачи на минимум - student2.ru (18)

В задаче (18) Алгоритм симплекс-метода для задачи на минимум - student2.ru – допустимое базисное решение, и задача (18) легко может быть сведена к виду (16). Для этого целевую функцию необходимо выразить через свободные переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru :

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Шаг 3. Для вспомогательной задачи (18) строим симплексную таблицу

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
………………….
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.

Шаг 4. Если Алгоритм симплекс-метода для задачи на минимум - student2.ru и все переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru являются небазисными, то m переменных из Алгоритм симплекс-метода для задачи на минимум - student2.ru войдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид

Алгоритм симплекс-метода для задачи на минимум - student2.ru (19)

Так как переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru , то их исключили из системы (19), не нарушив при этом равенств. Выражая целевую функцию основной задачи Алгоритм симплекс-метода для задачи на минимум - student2.ru через небазисные переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru системы (19), получим исходную задачу (17) в виде (16).

Шаг 5. Если Алгоритм симплекс-метода для задачи на минимум - student2.ru , но в базисе остались искусственные переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru , для которых Алгоритм симплекс-метода для задачи на минимум - student2.ru (вырожденный случай), то проводим для каждой искусственной переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru из базиса следующее преобразование симплексной таблицы.

Выбираем ведущим столбцом столбец такой переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru , для которой элемент индексной строки Алгоритм симплекс-метода для задачи на минимум - student2.ru , а элемент столбца Алгоритм симплекс-метода для задачи на минимум - student2.ru . В этом случае строка искусственной переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru будет ведущей и после стандартного преобразования симплексной таблицы (шаг 6 из прямого симплекс-метода) искусственная переменная Алгоритм симплекс-метода для задачи на минимум - student2.ru выведется из базиса. В результате получим симплексную таблицу, соответствующую шагу 4.

Шаг 6. Если Алгоритм симплекс-метода для задачи на минимум - student2.ru , то допустимого решения в исходной задаче (17) не существует (не могут все искусственные переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru быть равными нулю в задаче (18), а значит система ограничений задачи (17) несовместна) – процесс решения исходной задачи (17) завершается.

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

Выделить допустимое базисное решение для задачи ЛП:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Приведем задачу к канонической форме на минимум с неотрицательными правыми частями:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Заметим, что переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru и Алгоритм симплекс-метода для задачи на минимум - student2.ru можно использовать для введения в исходный базис, поэтому в первую и третью строку ограничений можно не вводить искусственные переменные.

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

Полученная вспомогательная задача имеет вид

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Приведем задачу к виду (16):

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Выпишем соответствующую симплексную таблицу:

  B Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru -2
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru

Ведущий столбец рекомендуется выбирать не по максимальному положительному элементу строки целевой функции, а так, чтобы из базиса выводилась искусственная базисная переменная (соответствующая ведущая строка должна быть строкой искусственной переменной). Так, выбрав ведущим столбцом столбец переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru , получим ведущую строку – строку с переменной z (выбирая ведущим столбцом Алгоритм симплекс-метода для задачи на минимум - student2.ru , получили бы ведущую строку Алгоритм симплекс-метода для задачи на минимум - student2.ru , и из базиса выводилась бы переменная Алгоритм симплекс-метода для задачи на минимум - student2.ru ).

Итак, искусственная переменная z выйдет из базиса, а переменная Алгоритм симплекс-метода для задачи на минимум - student2.ru введется в базис.

Симплексная таблица преобразуется к виду:

  B Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru 11/2 1/2 -1/2
Алгоритм симплекс-метода для задачи на минимум - student2.ru 5/2 5/4 1/4 -1/4
Алгоритм симплекс-метода для задачи на минимум - student2.ru 5/2 3/4 -1/4 1/4

Так как значение Алгоритм симплекс-метода для задачи на минимум - student2.ru , то полученный базис Алгоритм симплекс-метода для задачи на минимум - student2.ru является начальным допустимым базисом для исходной задачи ЛП. Чтобы выразить целевую функцию Алгоритм симплекс-метода для задачи на минимум - student2.ru через небазисные переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru , подставим значение базисной переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru в целевую функцию. В результате получим:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Тогда исходная задача будет иметь вид специальной формы задачи ЛП:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

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

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

Метод работает с теми же симплексными таблицами, что и прямой симплекс-метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис [1,3].

Вычислительная схема двойственного симплекс-метода

Шаг 0. Начинаем с симплексной таблицы, где Алгоритм симплекс-метода для задачи на минимум - student2.ru .

  B Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
…………..
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

Шаг 1. Проверка на оптимальность. Если Алгоритм симплекс-метода для задачи на минимум - student2.ru , то решение Алгоритм симплекс-метода для задачи на минимум - student2.ru – оптимальное.

Шаг 2. Выбор ведущей строки. Выбираем среди номеров i, для которых Алгоритм симплекс-метода для задачи на минимум - student2.ru , номер k с максимальным по модулю значением

Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Строка k объявляется ведущей.

Шаг 3. Проверка на неразрешимость. Если в строке Алгоритм симплекс-метода для задачи на минимум - student2.ru нет отрицательных элементов, то двойственная целевая функция неограниченная и, следовательно, прямая задача не имеет допустимых решений. Процесс решения завершается.

Шаг 4. Выбор ведущего столбца s. Выбираем среди отрицательных элементов строки Алгоритм симплекс-метода для задачи на минимум - student2.ru элемент с номером s, для которого выполняется равенство

Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Столбец s объявляется ведущим, а элемент Алгоритм симплекс-метода для задачи на минимум - student2.ru – ведущим элементом.

Шаг 5. Проводим стандартное преобразование симплексной таблицы (Шаг 6 из прямого симплекс-метода).

Пример решения задачи двойственным симплекс-методом

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

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Приводим задачу к каноническому виду:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

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

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -1 -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru -2 -1 -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1 -2 -1

Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку – это строка переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru , ведущий столбец – это столбец переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru . После преобразования таблица принимает вид

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -1 -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1 -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru -3 -3

Так как в столбце b есть отрицательная переменная Алгоритм симплекс-метода для задачи на минимум - student2.ru , то эту строку выбираем ведущей, а столбец переменной Алгоритм симплекс-метода для задачи на минимум - student2.ru будет ведущим столбцом. После преобразования получаем таблицу:

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -1/3 -1 -1/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru 1/3 -1 -2/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1/3 -1/3

которая является оптимальной. Соответствующее оптимальное решение имеет вид Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Двойственность в ЛП

Постановка задачи

Рассмотрим пару задач ЛП вида:

(I) (II)

Алгоритм симплекс-метода для задачи на минимум - student2.ru

… …

Алгоритм симплекс-метода для задачи на минимум - student2.ru

… …

Алгоритм симплекс-метода для задачи на минимум - student2.ru

… …

Алгоритм симплекс-метода для задачи на минимум - student2.ru

… …

Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Задачу (I) называют прямой задачей ЛП, а (II) – двойственной. Неравенства задач (I) и (II), соответствующие друг другу (по стрелке), называются сопряженными. Заметим, что задача двойственная к (II), есть исходная прямая задача, т. е. соотношение двойственности взаимное. Поэтому можно из такой пары задач любую считать прямой, а другую – двойственной.

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

Построить двойственную задачу к следующей задаче ЛП:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной: согласовать знаки неравенств в ограничениях задачи с целевой функцией. Так как ЦФ минимизируется, то неравенства должны быть записаны с помощью знака « Алгоритм симплекс-метода для задачи на минимум - student2.ru ». Для этого второе неравенство умножим на -1:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Теперь, вводя двойственные переменные Алгоритм симплекс-метода для задачи на минимум - student2.ru , запишем в соответствии с указанным правилом пару двойственных задач:

Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru   Алгоритм симплекс-метода для задачи на минимум - student2.ru

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

Теоремы двойственности

Двойственность является одним из фундаментальных понятий в теории ЛП. Исключительно важную роль играют следующие утверждения, получившие названия теорем двойственности [1,3].

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

Алгоритм симплекс-метода для задачи на минимум - student2.ru

где Алгоритм симплекс-метода для задачи на минимум - student2.ru – оптимальные планы задач (I) и (II) соответственно.

Говорят, что допустимые решения x, y удовлетворяют условиям дополняющей нежесткости (УДН), если при подстановке этих векторов в ограничения задач (I) и (II) хотя бы одно из любой пары сопряженных неравенств обращается в равенство.

Вторая теорема двойственности. Алгоритм симплекс-метода для задачи на минимум - student2.ru оптимальны в задачах (I) и (II) тогда и только тогда, когда они удовлетворяют УДН.

Пример решения пары двойственных задач

Используя теоремы двойственности, решить двойственную задачу, если известно решение прямой задачи:

Алгоритм симплекс-метода для задачи на минимум - student2.ru (20)

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

Алгоритм симплекс-метода для задачи на минимум - student2.ru (21)

Алгоритм симплекс-метода для задачи на минимум - student2.ru По первой теореме двойственности задача разрешима, причем Алгоритм симплекс-метода для задачи на минимум - student2.ru . Найдем оптимальный план Алгоритм симплекс-метода для задачи на минимум - student2.ru задачи (21), используя вторую теорему двойственности. Подставим координаты вектора Алгоритм симплекс-метода для задачи на минимум - student2.ru в ограничения задачи (20). Получим

Следовательно, в силу УДН, неравенство Алгоритм симплекс-метода для задачи на минимум - student2.ru должно выполняться как равенство, т. е. Алгоритм симплекс-метода для задачи на минимум - student2.ru . Далее так как Алгоритм симплекс-метода для задачи на минимум - student2.ru , то в силу УДН

Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Получаем систему линейных уравнений и решаем ее:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Планы Алгоритм симплекс-метода для задачи на минимум - student2.ru и Алгоритм симплекс-метода для задачи на минимум - student2.ru удовлетворяют УДН, следовательно, в силу второй теоремы двойственности, являются оптимальными в задачах (20) и (21) соответственно.

Пример проверки вектора на оптимальность

Исследовать вектор Алгоритм симплекс-метода для задачи на минимум - student2.ru на оптимальность в задаче ЛП:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Вначале нужно проверить, является ли вектор Алгоритм симплекс-метода для задачи на минимум - student2.ru допустимым. Для этого подставляем координаты вектора в ограничения:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Так как второе ограничение выполняется как строгое неравенство, то в силу УДН для оптимальности вектора Алгоритм симплекс-метода для задачи на минимум - student2.ru необходимо выполнение равенства Алгоритм симплекс-метода для задачи на минимум - student2.ru .

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

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Поскольку Алгоритм симплекс-метода для задачи на минимум - student2.ru , то из третьего и четвертого ограничений получаем Алгоритм симплекс-метода для задачи на минимум - student2.ru . Но по УДН из условия Алгоритм симплекс-метода для задачи на минимум - student2.ru следует, что должно выполняться равенство в первом ограничении двойственной задачи:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Подставляя значения Алгоритм симплекс-метода для задачи на минимум - student2.ru , получим Алгоритм симплекс-метода для задачи на минимум - student2.ru Следовательно, УДН не выполняются и вектор Алгоритм симплекс-метода для задачи на минимум - student2.ru не является оптимальным в исходной задаче.

Метод Гомори

Постановка задачи ЦЛП

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

Алгоритм симплекс-метода для задачи на минимум - student2.ru (22)

Симплекс-метод не гарантирует целочисленности решения задачи (22), поэтому для отыскания оптимального целочисленного решения задачи ЦЛП требуются специальные методы. Один из таких методов, приводящий к целочисленному решению за конечное число шагов, предложен американским математиком Р. Гомори [1,2]. Идея метода следующая.

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

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

Алгоритм метода Гомори

Шаг 1. Симплекс-методом находим оптимальное решение задачи (22) без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В этом случае алгоритм завершает работу.

Шаг 2. Пусть оптимальная таблица имеет вид:

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
…………..
Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru

Если элементы Алгоритм симплекс-метода для задачи на минимум - student2.ru – целочисленные, то оптимальное решение Алгоритм симплекс-метода для задачи на минимум - student2.ru является целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.

Шаг 3. Среди дробных компонент Алгоритм симплекс-метода для задачи на минимум - student2.ru таблицы выбираем элемент Алгоритм симплекс-метода для задачи на минимум - student2.ru с максимальной дробной частью Алгоритм симплекс-метода для задачи на минимум - student2.ru и по строке i составляем дополнительное ограничение:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Здесь Алгоритм симплекс-метода для задачи на минимум - student2.ru – целая часть числа Алгоритм симплекс-метода для задачи на минимум - student2.ru (наибольшее целое число, не превышающее число Алгоритм симплекс-метода для задачи на минимум - student2.ru ).

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

Замечания

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

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

Если на шаге 4 в базис вводится переменная дополнительного ограничения Алгоритм симплекс-метода для задачи на минимум - student2.ru , то эта строка вычеркивается из симплексной таблицы (соответствующее ограничение является избыточным).

Пример решения задачи ЦЛП

Решить задачу ЦЛП:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

Решаем задачу без условия целочисленности симплекс-методом. Оптимальная таблица имеет вид

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -14/3 -4/3 -2/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru 5/3 1/3 2/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru 4/3 2/3 -2/3

Оптимальное решение Алгоритм симплекс-метода для задачи на минимум - student2.ru не является целочисленным. Выберем среди нецелочисленных переменных Алгоритм симплекс-метода для задачи на минимум - student2.ru переменную Алгоритм симплекс-метода для задачи на минимум - student2.ru с максимальной дробной частью и построим соответствующее отсечение:

Алгоритм симплекс-метода для задачи на минимум - student2.ru

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

  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -14/3 -4/3 -2/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru 5/3 1/3 2/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru 4/3 2/3 -2/3
Алгоритм симплекс-метода для задачи на минимум - student2.ru -2/3 -1/3 -2/3
  b Алгоритм симплекс-метода для задачи на минимум - student2.ru Алгоритм симплекс-метода для задачи на минимум - student2.ru
L -4 -1 -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru
Алгоритм симплекс-метода для задачи на минимум - student2.ru -1
Алгоритм симплекс-метода для задачи на минимум - student2.ru 1/2 -3/2

Полученная таблица является оптимальной. Соответствующее оптимальное решение Алгоритм симплекс-метода для задачи на минимум - student2.ru является целочисленным. Значение функции на этом решении Алгоритм симплекс-метода для задачи на минимум - student2.ru .

Транспортная задача ЛП

Постановка задачи

Классическая транспортная задача ЛП формулируется следующим образом. Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины:

Алгоритм симплекс-метода для задачи на минимум - student2.ru - объем производства (запас) i-го поставщика, Алгоритм симплекс-метода для задачи на минимум - student2.ru ;

Алгоритм симплекс-метода для задачи на минимум - student2.ru - объем потребления (спрос) j-го потребителя, Алгоритм симплекс-метода для задачи на минимум - student2.ru

Алгоритм симплекс-метода для задачи на минимум - student2.ru - стоимость перевозки (транспортные затраты) единицы продукции от i-го поставщика к j-му потребителю.

Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен, и при этом

Наши рекомендации