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

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

Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допустимых плановD некоторой задачи ЛП. Как видно из рисунка, целевая функция f (ее поведение отражает линия уровня, показанная жирным пунктиром) достигает экстремального значения в точке х*, а изменению ее коэффициентов от с к с' или с" на рисунке соответствует поворот линии уровня относительно х*. Активным, т. е. обращающимся в равенство, ограничениям в точке х* соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с, линия уровня целевой функции не выходит за пределы образуемого линиями ограничений конуса, х* остается оптимальным планом. Как показано на рис. 1.10, этот план не меняется при переходе от с к с', и, наоборот, при переходе от с к с" линия уровня целевой функции f(x)=c"x пересечет линию (2), что вызовет изменение оптимального базисного плана, которым теперь станет точка

.

Используя условия оптимальности плана ЗЛП

нетрудно получить количественные оценки для пределов колебаний коэффициентов целевой функции, при которых не происходит изменение оптимального плана. Допустим, вариации подвергся некоторый элемент с_r : с_r^′ = с_r +ε_r. Возможны два случая:

1. Столбец r не входит в оптимальный базис (r ÎN(β^(q))). Тогда для неизменности оптимального плана необходимо и достаточно выполнение условия

Отсюда можно получить значение для допустимой вариации

2. Столбец r входит в оптимальный базис (r ÎN(β^(q))). В этом случае для сохранения оптимальности текущего плана потребуется выполнение для всех небазисных столбцов (jÏN(β^(q)))условий

Следовательно, в этом случае допустимая вариация должна удовлетворять условиям

Приведенный пример исследования чувствительности оптимального плана по отношению к изменению параметров задачи является весьма простым. Очевидно, что существуют и более сложные задачи, в которых, например, исследуются совместные вариации параметров разных типов. Они составляют предмет специального раздела исследования операций, получившего название параметрического программирования. Заинтересованный читатель может получить дополнительную информацию по данному предмету в [1, 6].

1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

1.7.1. Основные идеи двойственного симплекс-метода.Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г.

В процессе изложения идей, положенных в основу двойственного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На рис. 1.11 изображен конус К положительных линейных комбинаций расширенных векторов условий а^j для случая m = 2, n = 6, а на рис. 1.12 — (для большей наглядности) — поперечное сечение данного конуса некоторой плоскостьюL, проходящей параллельно оси аппликат.

С каждым планом и задачи, двойственной по отношению к (1.48), можно взаимно однозначно связать гиперплоскость, проходящую через начало координат и перпендикулярную вектору (-1,и). Допустимые планы двойственной задачи (1.49) должны удовлетворять условиям иА ≥ с, которые можно переписать в виде (1,и)А ≥ 0 . Последнее означает, что всякий расширенный вектор условий а^j лежит «ниже» плоскости, определяемой вектором (-1, и). Таким образом, любому допустимому плану двойственной задачи в рассматриваемом примере соответствует некоторая плоскость, расположенная выше всех расширенных векторов, а стало быть, и конуса К. На рис. 1.12, где изображено поперечное сечение, конусу К отвечает многогранник, а «гиперплоскостям двойственных планов» — пунктирные линии, являющиеся их следами.

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

Из геометрической иллюстрации видно, что плоскости, не соприкасающиеся с конусом К, заведомо не представляют интереса, так как для любой из них легко указать плоскость, у которой искомая точка пересечения лежит ниже. Таким образом, процесс поиска экстремума сводится к последовательному перебору плоскостей, касающихся «верхних» граней конуса, или, как еще говорят, опорных по отношению к конусу. Для случая, изображенного на рис. 1.12, таковыми являются гиперплоскости π_1,2, π_2,3, π_3,4 и π_4,5. Как можно заметить, каждая из рассматриваемых гиперплоскостей натянута на некоторый базисный набор расширенных векторов а^j, что, собственно, и использовано для их обозначения (π_1,2 ~ {а¹, а²} и т. д.).

-В дальнейшем системуβ={a^j1, a^j2,...,a^jm} из т линейно-независимых столбцов матрицы условий прямой задачи А будем называть сопряженным базисом, или двойственно допустимым базисом, если всякий вектор и Î R^m, удовлетворяющий условиям, удовлетворяет также условиям иа^j≥c_j(jÎ1:n), т. е. является допустимым планом двойственной задачи (1.49).

План двойственной задачи и, соответствующий сопряженному базису β={a^j1, a^j2,...,a^jm}, называют опорным планом. Его «опорность» заключается в том, что в системе ограничений uа^j ≥ c_j (jÎ1:n), задающих область определения двойственной задачиD*, т неравенств с номерами jÎN(β) обращаются в равенства.

Следует обратить внимание на то, что не всем сопряженным базисам соответствуют допустимые базисные планы прямой задачи. В частности, вектор b не может быть разложен с неотрицательными коэффициентами по базисам {а¹, а²}, {а³ , а⁴ } или {а⁴, а⁵}. В связи с этим систему коэффициентов разложения вектора b по сопряженному базису называют псевдопланом. В то же время базис {а², а³} является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивысшую точку пересечения прямой, проходящей через конец b, с конусом К), а с другой — минимум двойственной (низшую точку пересечения этой прямой с лежащей над К опорной гиперплоскостью):

Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.