Двойственные задачи

Метод искусственного базиса (М-метод)

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

1. Привести ЗЛП к каноническому виду.

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

3. Выписать исходное базисное решение.

4. Решить М-задачу симплексным методом. При решении учесть следующие возможные случаи:

а) если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующее решение исходной задачи является оптимальным и экстремумы целевых функций равны;

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

в) если М-задача не имеет оптимального решения, то исходная задача также не имеет оптимального решения.

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

Пример 8. Найти наибольшее значение функции при ограничениях:

(2.29)

Задача дана в каноническом виде. Составим М-задачу, для этого введем в первое уравнение переменную х₅, во второе – переменную х₆, в целевую функцию добавим – М х₅ – М х₆.

(2.30)

(2.31)

Первоначальный базис х₅, х₆. Решаем задачу симплексным методом.

(2.32)

(2.33)

Решение допустимое . Переведем в базис переменную х ₂, входящую в целевую функцию с положительным коэффициентом. Оценочные отношения для переменной х₂ равны 2 и 5. Первое уравнение системы является разрешающим. Новый базис х₂, х₆. Т.к. искусственная переменная х₅ выведена из базиса, не учитываем ее в дальнейших вычислениях. Система ограничений и целевая функция принимают вид:

(2.34)

(2.35)

Решение . Целевая функция .

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

(2.36)

. (2.37)

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

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

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

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

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

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

Симметричная пара

1. В исходной задаче знаки неравенств системы m ограничений приводятся к единому виду: «≤» в задаче на максимум и «≥» в задаче на минимум.

2. Каждому ограничению исходной задачи ставится в соответствие двойственная переменная y_i, i =1, 2, … m.

3. Составляется целевая функция Z от переменных y_i (i =1, 2, … m), коэффициентами которой будут свободные члены системы ограничений исходной задачи. Цель меняется на противоположную.

4. Составляется система ограничений двойственной задачи. Матрицу коэффициентов системы ограничений двойственной задачи получают транспонированием матрицы коэффициентов исходной задачи. Знаки неравенств системы ограничений двойственной задачи противоположны знакам неравенств в исходной задаче. Свободными членами неравенств системы ограничений являются коэффициенты целевой функции исходной задачи. Переменные y_i (i =1, 2, … m) неотрицательны.

В таблице 2.2 показано соответствие задач симметричной пары.

Таблица 2.2. Соответствие стандартных взаимно-двойственных задач

Исходная задача	Двойственная задача
(2.38)	(2.39)

Несимметричная пара

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

2. Если переменные x_j (j=1, 2, …n) исходной задачи неотрицательны, то ограничения двойственной задачи имеют вид неравенств со знаком «≤» для задачи на максимум и «≥» для задачи на минимум.

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

В таблице 2.3 показано соответствие задач несимметричной пары.

Таблица 2.3. Соответствие задач несимметричной пары

Исходная задача	Двойственная задача
(2.40)	(2.41)
(2.42)	(2.43)

Смешанная пара

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

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

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

В таблице 2.4 показано соответствие задач смешанной пары.

Таблица 2.4. Соответствие смешанных взаимно-двойственных задач

Исходная задача	Двойственная задача
(2.44)	(2.45)

Дата добавления: 2014-01-06