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

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

Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса.

Алгоритм метода искусственного базиса.

Шаг 1.

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

(35.1)

Шаг 2:

Строим вспомогательную задачу ЛП

(35.2)

.

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

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

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

(35.3)

Шаг 3:

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

Шаг 4:

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

Шаг 5:

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

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

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

Итак, у нас получилась вспомогательная задача ЛП:

Исходная симплекс-таблица примет тогда вид:

базис	св. члены
	35	3	3	8
	10	1	2	1
	15	1	2	3
	20	2	1	5

Дальнейшие итерации приводятся без особых пояснений.

Первая итерация

Так как из базиса выводится вектор , то в получающейся симплекс-таблице соответствующий столбец сразу удаляется.

базис	св. члены
	35	3	3	8
	10	1	2	1
	15	1	2	3
	20	2	1	5

базис	св. члены
	3	-1/5	7/5	-8/5
	6	3/5	9/5	-1/5
	3	-1/5	7/5	-3/5
	4	2/5	1/5	1/5

Вторая итерация

На этой итерации из базиса выводится вектор . Соответственно из симплекс-таблицы удаляется столбец, соответствующий этому вектору, и все введенные дополнительные переменные исчезают.

базис	св. члены
	3	-1/5	7/5
	6	3/5	9/5
	3	-1/5	7/5
	4	2/5	1/5

 

базис	св. члены
	0	0	-1
	15/7	6/7	-9/7
	15/7	-1/7	5/7
	25/7	15/7	-1/7

Третья итерация

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

базис	св. члены
	-90/7	-30/7
	15/7	6/7
	15/7	-1/7
	25/7	15/7

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

Значит, задача решена и оптимальный план имеет вид: (0, 15/7, 25/7, 15/7)

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

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

Таблица 36.1

Прямая задача	Двойственная задача
Максимизация	Минимизация
Коэффициенты в целевой функции	Константы в правых частях ограничений
Константы в правых частях ограничений	Коэффициенты в целевой функции
i-я строка, составленная из коэффициентов при неизвестных в ограничениях	i-й столбец, составленный из коэффициентов при неизвестных в ограничениях
j-й столбец, составленный из коэффициентов при неизвестных в ограничениях	j-я строка, составленная из коэффициентов при неизвестных в ограничениях
i-е неравенство вида (этот знак неравенства согласован с целевой функцией на максимум)	i-я неотрицательная переменная:
i-е соотношение в виде равенства	i-я переменная , не имеющая ограничения в знаке
j-я неотрицательная переменная:	j-е неравенство вида (этот знак неравенства согласован с целевой функцией на минимум)
i-я переменная , не имеющая ограничения в знаке	i-е соотношение в виде равенства

 

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

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

Таблица 36.2

Прямая задача (I)	Двойственная ей задача (II)
……………………… ……… - любое …….. - любое	……… - любое …….. - любое ……………………………..

 

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

Грубо говоря, двойственная задача - это на 90⁰ повернутая исходная прямая задача. В этой связи полезно усвоить следующую схему соответствия.

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

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

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

 

Таблица 36.3

Прямая задача (I)	Двойственная ей задача (II)
- любое - любое	- любое

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

 

 

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

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

Таблица 37.1

Прямая задача (I)	Двойственная ей задача (II)
……………………… ………	……… ……………………………..

Пара двойственных задач (I) и (II) называется парой симметрических двойственных задач.

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

Рассмотрим пару симметрических двойственных задач в матричной форме записи.

Таблица 37.2.

Прямая задача (I)	Двойственная ей задача (II)

Здесь , , , ,

- матрица из строк и столбцов, - транспонированная матрица. Введем обозначения для допустимых областей задачи (I) и (II).

,

Основное неравенство двойственности: для любых допустимых решений прямой задачи и для любых допустимых решений двойственной задачи выполняется неравенство .

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

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

, (37.1)

где , оптимальные планы задач (I) и (II) соответственно.

Вторая теорема двойственности: чтобы допустимые решения , пары двойственных задач (I) и (II) были оптимальными необходимо и достаточно, чтобы выполнялись условия:

1) , (37.2)

2) . (37.3)

 

Критерии оптимальности.

Первый критерий оптимальности: Решение оптимально тогда и только тогда, когда существует решение такое, что

. (38.1)

Второй критерий оптимальности: чтобы допустимые решения , - пары двойственных задач (I) и (II) были оптимальны, необходимо и достаточно, чтобы выполнялись соотношения:

1) если , то ; (38.2)

2) если , то ; (38.3)

3) если , то ; (38.4)

4) если , то . (38.5)

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

, (38.6)

, , .

Пусть решение задачи найдено одним из стандартных методов: , .

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

, (38.7)

, , .

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

.

Найдем оптимальный план задачи , используя вторую теорему двойственности. Подставим координаты вектора в ограничения задачи (38.6).

Получим

Следовательно, неравенство должно выполняться как равенство, то есть .

Далее, так как , , то

, .

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

, ,

Планы и , в силу второй теоремы двойственности, являются оптимальными в задачах (38.6) и (38.7) соответственно.