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

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

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

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

, ;

2) в каждую i-ю строку ограничений вводим искусственную неотрицательную базисную переменную;

3) целевая функция равна алгебраической сумме искусственных переменных.

Математическая модель вспомогательной задачи имеет вид:

.

Эта задача имеет очевидное базисное решение:

.

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

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

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

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

Прямая задача

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

	С1	…	Сn
B1	a11	…	a1n
…	…	…	…
Bm	am1	…	amn

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

;

где – количество выпускаемой продукции.

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

Фирма вместо выпуска продукции хочет продать имеющиеся у неё запасы ресурсов другой фирме.

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

Цены не могут быть отрицательными, .

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

;

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

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

Две задачи I и II линейного программирования называются симметричными взаимно двойственными задачами, или просто двойственными задачами.