Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

Понятие двойственной задачи ЛП. Пусть задана КЗЛП (1.7). Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х ≥ 0 справедливо неравенство

Стремясь получить наилучшую оценку (1.47), мы приходим к формулировке некоторой новой кстремальной задачи, которая в некотором смысле логически сопряжена с задачей (1.7) называется двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному определению двойственной задачи линейного прoграммирования.

F Если задана каноническая задача ЛП

то задача ЛП

называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к

(D*,f*) называется прямой (или исходной).