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

С помощю этого онлайн калькулятора можно построить двойственную задачу линейного программирования (ЛП) по отношению к исходной задаче. Для построения двойственной задачи, введите данные исходной задачи и нажмите на кнопку «Вычислить». Теоретическую часть и численные примеры смотрите ниже.

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

Пусть задана прямая задача линейного программирования (ЛП) в общем виде:

Задаче (1) соответствует следующая двойственная задача ЛП:

В этих задачах знак ∀ — определяет, что на данную переменную не налагается ограничение в виде неотрицательности, т.е. она произвольная.

Отметим, что если задача ЛП (2) является двойственной к задаче ЛП (1), то задача ЛП (1) является двойственной к задаче ЛП (2). Говорят, что задачи ЛП (1) и (2) взаимно двойственные задачи линейного программирования.

Рассмотрим подробно процесс построения двойственной задачи к исходной задачи линейного программирования. Для построения двойственной задачи:

1. Упорядочивается запись исходной задачи ЛП: если целевая функция исследуется на максимум, то ограничения (1b), (1c) должны иметь знак или «=», или «≤», а если целевая функция исследуется на минимум, то ограничения (1b), (1c) должны иметь знак или «=» , или «≥». Если в исходной задаче ЛП есть ограничения, не удовлетворяющие этим условиям, то это можно исправить, умножая данное ограничение на −1.

2. Каждому ограничению исходной задачи ставится в соответствие переменная

. Число переменных двойственной задачи равно числу ограничений исходной задачи, а число ограничений двойственной задачи равно числу переменных исходной задачи.

3. Если в исходной задаче целевая функция исследуется на максимум, то целевая функция двойственной задачи исследуется на минимум.

4. Свободные члены исходной задачи становятся коэффициентами целевой функции двойственной задачи.

5. Коэффициенты целевой функции исходной задачи становятся свободными членами двойственной задачи.

6. Матрица коэффициентов двойственной задачи получается транспонированием матрицы коэффициентов исходной задачи.

7. Если на переменную

наложено ограничение в виде неотрицательности, то j-е ограничение двойственной задачи записывается в виде неравенства. Если же переменная

исходной задачи произвольная, то j-е ограничение двойственной задачи имеет знак равенства.

8. Если в исходой задаче имеются ограничения в виде равенств, то на соответствующие переменные двойственной задачи не налагаются условия неотрицательности.

Чтобы посмотреть пример построения двойственной задачи воспользуйтесь онлайн калькулятором в начале страницы. Для этого введите коэффициенты исходной задачи в ячейки калькулятора и нажмите на кнопку «Построить».

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

Найти максимум функции

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

следовательно, все элементы в столбцах

Обнулим все элементы столбца

кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор

Определяем, какой вектор выходит из базиса. Для этого вычисляем

соответствует строке 3. Из базиса выходит вектор

Сделаем исключение Гаусса для столбца

учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

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

соответствует строке 1. Из базиса выходит вектор x2. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x3. Определяем, какой вектор выходит из базиса. Для этого вычисляем

соответствует строке 3. Из базиса выходит вектор x5. Сделаем исключение Гаусса для столбца x3, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными

нет отрицательных элементов.

Решение исходной задачи можно записать так:

Значение целевой функции в данной точке:

Найти оптимальный план задачи линейного программирования:

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:

Базисные векторы x4, x5, x6, следовательно, все элементы в столбцах x4, x5, x6, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x4, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x5, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x6, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

В строке 5 элементы, соответствующие переменным x1, x2, x3, x4, x5, x6 неотрицательны, а число находящийся в пересечении данной строки и столбца x0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Примеры решения задач графическим методом

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

Построим многоугольник решений. Для этого начертим граничные прямые. Из первого
неравенства запишем уравнение

.
Это уравнение первой граничной прямой. Найдём точки пересечения этой прямой с осями
координат. При

из уравнения получим

. Это
значит, что первая прямая отсекает от осей координат отрезки

Аналогично строим остальные граничные прямые. Вторая прямая от осей
координат отсекает отрезки, равные 6. Третья прямая проходит параллельно оси

,
отсекая на оси

отрезок, равный 2. Четвёртая прямая имеет уравнение

.
Она совпадает с осью

Из рисунка ниже видно, что множество точек четырёхугольника ABDE
удовлетворяет всем четырём неравенствам системы.

Следовательно, четырёхугольник ABDE является многоугольником
решений системы (заштрихован вовнутрь).

Начертим линию равных значений функции цели. Приняв в равенстве F =1,
получим, что эта линия отсекает отрезки 1 и 1/3 соответственно на оси

и
на оси

Двигая эту прямую параллельно самой себе в направлении градиента — вектора

(бордового цвета),
получим опорные прямые. Первая прямая (зелёного цвета) имеет с многоугольником общую точку
A. Здесь функция цели достигает минимума. Двигаясь дальше, придём к точке В.
Здесь максимум. Координаты точки В: (2, 4). Подставляя в функцию цели координаты
точки В, т. е.

,
получим максимальное значение функции цели:

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

Решение. Многогранником решений является открытая область

Проведём линию равных значений функции цели при F =1, как в
предыдущем примере (она опять чёрного цвета).

Из рисунка видно, что прямая ближайшнее от начала координат опорное
положение займёт в точке В. Следовательно, в этой точке функция цели имеет минимум.
Координаты точки В: (2, 2). Подставляя в функцию цели

, получим
минимальное значение функции:

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

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

Если X и Y − допустимые точки задач (1) и (2), соответственно, то

При этом, если для каких то допустимых точек

являются решениями задач (1) и (2) соответственно.

Доказательство. Запишем взвимно двойственные задачи (1) и (2) в матричном виде.

матрица коэффициентов ограничений исходной задачи, которая разделена на четыре матрицы следующих порядков:

Сделаны также следующие обозначения:

(5b) и (5c) можно записать так:

Легко показать, что

Множители в правой части выражения (9) неотрицательны. Тогда их произведение не отрицательно, т.е. выполнено условие (8).

Учитывая (7) и (8) упростим выражение 6:

С другой стороны:

(4b) и (4c) можно записать так

Учитывая (12) и Y1 упростим выражение (11):

Из (9) и (13) получим:

т.е. выполнено условие (3).

Докажем вторую часть утверждения 1. Для любой допустимой точки x задачи (1)

в том числе

наибольшее значение целевой функции задачи (1).

С другой стороны для любой допустимой точки y задачи (2)

− наименьшее из значений целевой функции задачи (2). Таким образом получили, что

является решением задачи (1), а

Теорема 1 (первая теорема двойственности). Если исходная задача имеет решение

, то двойственная ей задача также имеет решение

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

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

Представленные задачи взаимно двойственные, и в этих задачах допустимые области пусты.

Теорема 2 (вторая теорема двойственности или условие дополняющей нежесткости). Планы

пары двойственных задач (1) и (2) являются решениями этих задач тогда и только тогда, когда выполняются следующие условия:

или выполняется условие:

Докажем эквивалентность условий (15) и (16) с условием (17).

Из (4с) и (5с) имеем:

Из (15) и (16) имеем:

Подставляя (19),(20) в (21),(22) соответственно и упрощая получим:

через остальные слагаемые из (23) и подставляя в (24) получим:

А Запись (25) − это другой вид записи равенства (17).

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

В статье Формы записи задачи линейного программирования мы рассмотрели различные формы записи задачи линейного программирования. В этом параграфе мы рассмотрим двойственные задачи к задачам ЛП в различных формах.

1) Двойственной к задаче ЛП в канонической форме

является задача ЛП в основной форме

2) Двойственной к задаче ЛП в основной форме

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

3) Двойственной к задаче ЛП в стандантной форме

является задача ЛП также в стандартной форме

Все эти три пары взаимно двойственных задач получаются из пары двойственных задач в общем виде (1) и (2) при различных значениях n1 и m1. Первая пара задач получается из (1) и (2) при m1=0, n1=n. Вторая пара задач получается из задач (1) и (2) при m1=m, n1=0. Третья пара задач получается из (1) и (2) при m1=m, n1=n.

Иногда более удобно рассматривать задачи ЛП в векторно-матричной форме. Высше представленные пары двойственных задач представим в векторно-матричной форме записи.

векторы строки порядка

− матрица порядка

Решить задачи графическим методом самостоятельно, а затем посмотреть решения

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

Правильное решение и ответ.

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

Примеры решения ЗЛП симплекс методом

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

Р е ш е н и е. Матрица коэффициентов

Составляем симплексную таблицу. В столбец x0 записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1. Последние три векторы столбцы обазуют базис в трехмерном пространствое. Следовательно базисные переменные

, а свободные переменные

. min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x3. Сделаем исключение Гаусса для столбца x2, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x1. Определяем, какой вектор выходит из базиса. Для этого вычисляем

. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x4. Сделаем исключение Гаусса для столбца x1, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Текущий опорный план является оптимальным, так как в строках 4 под переменными

Решение можно записать так:

Значение целевой функции в данной точке: F(X)=

Базисные векторы x4, x3, следовательно, все элементы в столбцах x4, x3, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x4, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x3, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x2. Определяем, какой вектор выходит из базиса. Для этого вычисляем

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

Условие дополняющей нежесткости

Равенства (15) и (16) называются условиями дополняющей нежесткости. Рассмотрим уравнение (16). Левая часть уравнения является скалярным произведением неотрицательных векторов

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

не удовлетворяется как равенство, то соответствующая координата вектора

равна нулю и обратно − если некоторая координата вектора

больше нуля, то соответствующее неравенство в системе (4b) в точке

удовлетворяется как равенство.

Аналогичные рассуждения можно привести и для равенства (15). Условие дополняющей нежесткости позволяет найти оптимальный план двойственной задачи, если известен оптимальный план исходной задачи. Рассмотрим это на примере пар двойственных задач ЛП записанных в стандартной форме.

Дана следующая задача ЛП:

Решить данную задачу. Построить двойственную задачу и найти ее решение используя решение исходной задачи.

Запишем задачу ЛП в матричном виде:

Поскольку задача с двумя переменными, то ее можно решить графически.

Решая систему линейных уравнений (27) получим координаты точки M, т.е. оптимальный план задачи ЛП (26):

или в векторном виде:

Целевая функция в этой точке равна:

Построим двойственную к (26) задачу ЛП:

В векторно матричном виде задача ЛП (30) будет выглядеть так:

Условие дополняющей нежесткости (15) и (16) в случае задач ЛП в стандартной форме примут вид:

Условие (32) позволяет найти оптимальный план двойственной задачи ЛП (30). Поскольку все координаты оптимального плана

исходной задачи положительны, то из равенства (32) следует, что неравенства (30b) и (30c) в оптимальной точке

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

Решив данное уравнение находим оптимальный план

Найдем значение целевой функции в данной точке:

Значение целевых функций в оптимальных точках исходной и двойственной задач равны. Следовательно получено правильное решение.

Графический метод решения задачи ЛП (30) смотрите на Рис.2:

Рассмотрим пример с той же допустимой областью, что и пример 1, но с другой целевой функцией.

Решить данную задачу. Построить двойственную задачу и найти ее решение используя решение исходной задачи и условия дополняющей нежесткости.

Из Рис.3 видно, что оптимальным является точка

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

ограничение (33b) удовлетворяется как строгое неравенство следовательно исходя из условия дополняющей нежесткости (31), первая координата вектора

должна быть равна нулю:

. Из равенства (32) следует, что неравенство (34b) в оптимальной точке

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

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

Графический метод решения задачи ЛП (34) представлен на Рис.4. Прямая, ортогональная к вектору целевой функции B перемещаем перпендикулярно к вектору целевой функции до соприкосновения к допустимой области задачи ЛП (желтая область). Полученная точка M является решением задачи ЛП.

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

1. Построить многоугольник решений системы неравенств.

2. Начертить из семейства прямых, соответствующих линейной форме, линию
равных значений функции цели. Для построения линии равных значений придадим F
некоторое числовое значение. Во многих задачах удобно принять, что F =1.
Тогда получим

Затем, откладывая на оси

, а на оси

3. Двигать прямую (или линейку) вдоль градиента — вектора

параллельно линии равных значений в сторону многоугольника решений до соприкосновения с
многоугольником решений. Если первая встреча с многоугольником решений произойдёт в крайней
точке с координатами

4. Двигаясь дальше, придём к некоторому опорному положению, когда прямая
будет иметь одну общую точку

с многоугольником решений. В этой точке функция цели достигает своего максимума.

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

Продолжаем решать задачи графическим методом вместе

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

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

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

Легко заметить, что функция F может неограниченно возрастать
при заданной системе ограничений, поэтому можно условно записать, что

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

Решение. Изображённая на рисунке ниже область не содержит ни одной общей точки,
которая бы удовлетворяла всем неравенствам системы ограничений. То есть система ограничений противоречива
и не может содержать ни одного решения, в том числе и оптимального.

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

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

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

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

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

Все точки отрезка CD дают одно
и то же значение функции цели, которое и служит её оптимальным значением:

.
Следовательно, имеется не одно, а бесчисленное множество оптимальных решений, совпадающих с точками
отрезка CD, в частности, с двумя угловыми точками C и D. Этот пример показывает,
что в некоторых случаях единственность оптимального решения нарушается.

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

Начало темы «Линейное программирование»

Поделиться с друзьями

Симплекс метод онлайн

Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.