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

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

Теорема 1.7

Теорема 1.7. Пусть х* и u* — оптимальные планы канонической задачи (D, f) и двойственной по отношению к ней задачи (D*,f*). Если j-я компонента плана х* строго положительна (xj*>0), то соответствующее j-e ограничение двойственной задачи выполняется как равенство: а1,ju1* +...+аm,jum*= сj; если же j-й компонент плана х* имеет нулевое значение (хj* =0), то j-e ограничение двойственной задачи выполняется как неравенство: а1,ju1* +...+аm,jum*≥ сj .

Доказательство.

Векторы х* и и*, будучи допустимыми планами соответствующих задач, удовлетворяют условиям: Ах* = b, х* > 0 и и*А-с ≥ 0. Найдем скалярное произведение

Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u*b=сх*. Последнее означает, что (u*А-с)х* = 0 . Однако скалярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные произведения их соответствующих координат равны нулю. Следовательно, если xj* > 0, то u*аjсj = 0, если же xj = 0, то возможно u*аj – сj ≥ 0 , что и утверждается в теореме. A

Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область допустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая имеет только две переменные.

Еще раз вернемся к таблице Т2(q) (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ-1(q)), для которой было введено обозначение δ0(q)). Поэлементно она может быть записана в следующем виде:

Введем вектор = (δ0,1(q)), δ0,2(q)),..., δ0,m(q))). Нетрудно проверить, что строка оценок a0(q)) может быть представлена следующим образом:

Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũА≥с. Следовательно, вектор и является допустимым планом двойственной задачи.

В то же время элемент b0(q)), содержащий текущее значение целевой функции и равный на последней итерации f(x*), допускает представление

Согласно теореме 1.5 из равенства f(х*) = f*(ũ) вытекает, что вектор ũ служит оптимальным планом двойственной задачи: u = ũ.

Окончательно можно утверждать, что для оптимального базиса

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

Читателю в качестве самостоятельного упражнения предлагается построить задачу, двойственную к (1.34)-(1.35), решение которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2), полученный в таблице Т2(3), является для нее допустимым и оптимальным планом.