Математические методы исследования операций в экономике (стр. 12 из 37)

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

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

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

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

Введем вектор

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

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

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

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

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

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

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

1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП базируется на модели простейшей задачи производственного планирования, описанной во введении. Напомним, что в ней каждый (j-й) элемент вектора х рассматривается как план выпуска продукции данного вида в натуральных единицах, с_j — цена единицы продукции j-го вида, а^j — вектор, определяющий технологию расходования имеющихся m ресурсов на производство единицы продукции j-го вида, b — вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых значений A, bи с найден оптимальный план х*, максимизирующий суммарный доход max{cx}=cx*. Достаточно естественным представляется вопрос: как будет изменяться оптимальный план х* при изменении компонент вектора ограничений b и, в частности, при каких вариациях b оптимальный план х* останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчивости х* имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсовb_i; могут существенно колебаться после принятия планового решения х*.

Когда вектор ограничений b изменяется на Δbили, как еще говорят, получает приращение Δb, то возникают соответствующие вариации для оптимального плана х*(b+Δb) и значения целевой функции f(х*(b+Δb)). Допустим, приращение Δb таково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+Δb)≥0. Определим функциюF(b), возвращающую оптимальное значение целевой функции задачи (D(b), f) для различных значений вектора ограничений b

Рассмотрим отношение ее приращенияF(b+Δb)-F(b) к приращению аргумента Δb. Если для некоторогоi устремить Δb_{i →} 0, то мы получим

Учитывая, что в соответствии с теоремой 1.5

и подставив (1.57) в (1.56), приходим к выражению

-Из формулы (1.58) вытекает экономическая интерпретация оптимальных переменных двойственной задачи. Каждый элемент u_i* может рассматриваться как предельная (мгновенная) оценка вклада i-го ресурса в суммарный доход F при оптимальном решении х*. Грубо говоря, величина u_i*равна приросту дохода, возникающему при увеличении ресурса i на единицу при условии оптимального использования ресурсов.

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

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

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

В рамках рассматриваемой задачи производственного планирования это означает, что если некоторый ресурс b_i, имеется в избыточном количестве (не используется полностью при реализации оптимального плана), то i-e ограничение становится несущественным и оценка такого ресурса равна 0.

-Если при использовании оптимального плана двойственной задачи j-e ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, т. е. если a_1,ju₁^* +...а_m,jи_m – с_j > 0, то х_j^* =0.

Учитывая экономическое содержание двойственных оценок u₁*,...,u_m, выражение а_1,ju₁* +…a_m,ju_m^* может быть интерпретировано как удельные затраты наj-й технологический процесс. Следовательно, если эти затраты превышают прибыль от реализации единицы j-го продукта, то производство j-го продукта является нерентабельным и не должно присутствовать в оптимальном производственном плане (x_j^* =0).

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

1.6.5. Анализ параметрической устойчивости решений ЗЛП. В предыдущем пункте мы затронули некоторые аспекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b. Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции с_j,jÎ1:n.