<< Пред.           стр. 5 (из 13)           След. >>

Список литературы по разделу

  то
  В рамках рассматриваемой задачи производственного планирования это означает, что если некоторый ресурс bi имеется в избыточном количестве (не используется полностью при реализации оптимального плана), то i-е ограничение становится несущественным и оценка такого ресурса равна 0.
  >Если при использовании оптимального плана двойственной задачи j-e ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, т. е. если то
  Учитывая экономическое содержание двойственных оценок выражение может быть интерпретировано как удельные затраты на j-й технологический процесс. Следовательно, если эти затраты превышают прибыль от реализации единицы j-го продукта, то производство j-го продукта является нерентабельным и не должно присутствовать в оптимальном производственном плане
  Несмотря на возможные аналогии, которые могут возникнуть у читателей, знакомых с такими фундаментальными понятиями экономической теории, как предельные издержки и предельный доход, двойственные оценки не следует однозначно отождествлять с ценами (хотя такие попытки иногда предпринимались на начальной стадии становления исследования операций как науки). Еще раз подчеркнем, что переменные двойственной задачи по своему смыслу являются оценками потенциальной возможности получения дополнительной прибыли за счет увеличения соответствующего ресурса в условиях оптимального функционирования управляемого экономического объекта.
  1.6.5. Анализ параметрической устойчивости решений ЗЛП. В предыдущем пункте мы затронули некоторые аспекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b. Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции
  С точки зрения экономической интерпретации задача исследования параметрической устойчивости может быть рассмотрена как изучение тех пределов колебания цен на продукцию управляемого предприятия (фирмы), при которых принятый план выпуска продукции продолжает оставаться оптимальным.
  Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допустимых планов D некоторой задачи ЛП.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 1.10.
 
  Как видно из рисунка, целевая функция f (ее поведение отражает линия уровня, показанная жирным пунктиром) достигает экстремального значения в точке х*, а изменению ее коэффициентов от с к с' или с" на рисунке соответствует поворот линии уровня относительно х*. Активным, т. е. обращающимся в равенство, ограничениям в точке х* соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с, линия уровня целевой функции не выходит за пределы образуемого линиями ограничений конуса, х* остается оптимальным планом. Как показано на рис. 1.10, этот план не меняется при переходе от с к с', и, наоборот, при переходе от с к с" линия уровня целевой функции f(x) = c"x пересечет линию (2), что вызовет изменение оптимального базисного плана, которым теперь станет точка
  Используя условия оптимальности плана ЗЛП
 
 
 
  нетрудно получить количественные оценки для пределов колебаний коэффициентов целевой функции, при которых не происходит изменение оптимального плана. Допустим, вариации подвергся некоторый элемент cr : c'r=cr + ?r . Возможны два случая:
  1 . Столбец r не входит в оптимальный базис (r?N(?(q))). Тогда для неизменности оптимального плана необходимо и достаточно выполнение условия
 
 
  Отсюда можно получить значение для допустимой вариации
 
  (1.59)
  2. Столбец r входит в оптимальный базис (r?N(?(q))). В этом случае для сохранения оптимальности текущего плана потребуется выполнение для всех небазисных столбцов (j?N(?(q))) условий
 
  (1.60)
 
  Следовательно, в этом случае допустимая вариация должна удовлетворять условиям
 
  (1.61)
  Приведенный пример исследования чувствительности оптимального плана по отношению к изменению параметров задачи является весьма простым. Очевидно, что существуют и более сложные задачи, в которых, например, исследуются совместные вариации параметров разных типов. Они составляют предмет специального раздела исследования операций, получившего название параметрического программирования. Заинтересованный читатель может получить дополнительную информацию по данному предмету в [1, 6].
 
 
  1 .7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
 
  1.7.1. Основные идеи двойственного симплекс-метода. Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г.
  В процессе изложения идей, положенных в основу двойственного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На рис. 1 .11 изображен конус К положительных линейных комбинаций расширенных векторов условий для случая т = 2, п = 6, а на рис. 1 .12 - (для большей наглядности) - поперечное сечение данного конуса некоторой плоскостью L, проходящей параллельно оси аппликат.
  С каждым планом и задачи, двойственной по отношению к (1.48), можно взаимно однозначно связать гиперплоскость, проходящую через начало координат и перпендикулярную вектору (-1,и). Допустимые планы двойственной задачи (1.49) должны удовлетворять условиям иА ? с, которые можно переписать в виде (1, и) Последнее означает, что всякий расширенный вектор условий лежит "ниже" плоскости, определяемой вектором (-1, u). Таким образом, любому допустимому плану двойственной задачи в рассматриваемом примере соответствует некоторая плоскость, расположенная выше всех расширенных векторов, а стало быть, и конуса К. На рис. 1.12, где изображено поперечное сечение, конусу К отвечает многогранник, а "гиперплоскостям двойственных планов" - пунктирные линии, являющиеся их следами.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 1.11 Рис. 1.12
 
  По аналогии с интерпретацией решения прямой задачи процесс решения двойственной задачи может быть представлен как поиск такой гиперплоскости, которая лежит выше конуса К и пересекает прямую, проведенную через конец вектора параллельно оси аппликат, в самой нижней точке.
  Из геометрической иллюстрации видно, что плоскости, не соприкасающиеся с конусом К, заведомо не представляют интереса, так как для любой из них легко указать плоскость, у которой искомая точка пересечения лежит ниже. Таким образом, процесс поиска экстремума сводится к последовательному перебору плоскостей, касающихся "верхних" граней конуса, или, как еще говорят, опорных, по отношению к конусу. Для случая, изображенного на рис. 1.12, таковыми являются гиперплоскости ?1,2, ?2,3, ?3,4, и ?4,5. Как можно заметить, каждая из рассматриваемых гиперплоскостей натянута на некоторый базисный набор расширенных векторов , что, собственно, и использовано для их обозначения (?1,2 ? {, } и т. д.).
  ^В дальнейшем систему из т линейно- независимых, столбцов матрицы условий прямой задачи А будем называть сопряженным базисом, или двойственно допустимым базисом, если всякий вектор u ? Rm, удовлетворяющий условиям (i?1:m), удовлетворяет также условиям (j?1:n), т. е. является допустимым планом двойственной задачи (1.49).
 
  План двойственной задачи и, соответствующий сопряженному базису . называют опорным планом. Его "опорность" заключается в том, что в системе ограничений (j?1:n), задающих область определения двойственной задачи D* , т неравенств с номерами j ? N(?) обращаются в равенства.
  Следует обратить внимание на то, что не всем сопряженным базисам соответствуют допустимые базисные планы прямой задачи. В частности, вектор b не может быть разложен с неотрицательными коэффициентами по базисам или В связи с этим систему коэффициентов разложения вектора b по сопряженному базису называют псевдопланом. В то же время базис является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивысшую точку пересечения прямой, проходящей через конец , с конусом К), а с другой - минимум двойственной (низшую точку пересечения этой прямой с лежащей над К опорной гиперплоскостью):
 
 
  Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.
  Описанные выше свойства пары двойственных задач линейного программирования являются идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в котором последовательно рассматриваются допустимые базисные планы прямой задачи. Нетрудно догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом, может оказаться более коротким.
 
  >Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том, что х одновременно должен являться допустимым планом прямой задачи, т. е. все его компоненты должны быть неотрицательны (xj ? 0).
 
 Обратно, если хотя бы одна из компонент псевдоплана является отрицательной, то процесс улучшения значения целевой функции может быть продолжен. Геометрическая иллюстрация данной ситуации приведена на рис. 1.13. Здесь на плоскости (для т = 2) изображена система столбцов ограничений КЗЛП, из которых {а1, а2} образуют текущий базис. Как видно из рисунка, вектор ограничений имеет отрицательную координату по направлению, задаваемому вектором а1. В то же время очевидны и те базисы (например, {а2, а3}), в которых b будет иметь все положительные координаты. Однако это не всегда так. Пример на рис. 1.14 иллюстрирует случай отсутствия допустимых планов у прямой задачи: вектор b имеет отрицательную компоненту в текущем базисе {а1, а2} по направлению а2, a для всех остальных небазисных столбцов (а3, а4) данная координата является положительной, т. е. b и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных полуплоскостях, образуемых прямой, проходящей через вектор а4, и при любых базисах, отличных от текущего, соответствующая координата вектора b все равно останется отрицательной.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  Рис. 1.13 Рис. 1.14
  >Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у решаемой КЗЛП является неотрицательность каких-либо r-х компонент во всех столбцах аj, представленных в текущем базисе? , если 5
  С другой стороны, если и в строке существуют отрицательные координаты, то псевдоплан можно улучшить, выводя из базиса столбец, находящийся на r-м месте, и вводя в него некоторый вектор а', имеющий отрицательную r-ую координату. При наличии в векторе b(?) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно определяется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.
  Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис определял опорную плоскость, ниже которой располагаются все небазисные векторы. Для этого требуется, чтобы оценки всех небазисных векторов , вычисляемые по формулам
 
 
 
 
 (см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца / должен быть определен таким образом, чтобы
 
 
  , где (1.62)
 
  После выбора выводимого и вводимого векторов производится обычный пересчет симплекс-таблицы по формулам, аналогичным формулам (1.28)-(1.31), и процесс итеративно повторяется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множества допустимых планов.
  1.7.2. Алгоритм и табличная реализация двойственного симплекс-метода. Обобщая сказанное в предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.
  0-этап. Нахождение исходного сопряженного (двойственно допустимого базиса). Результатом 0-этапа являются сопряженный базис ?(1) и соответствующие ему псевдоплан х(?(1)), матрица и вектор , которые будут использованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к 1-этапу.
  I-этап. Стандартная итерация алгоритма - выполняется для очередного сопряженного базиса (?(q)).
  1°. Проверка оптимальности текущего псевдоплана: осуществляется просмотр значений , . Возможны два варианта:
  Г. Для всех , . Тогда текущий псевдоплан одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный процесс закончен. Элементы оптимального плана х* определяются по формуле
 
  , , (1.63)
 а достигаемое на нем значение целевой функции равно
 
  . (1.64)
 
  1". Существует по меньшей мере один номер строки , для которого . Следовательно, псевдоплан - неоптимален. Выбирается строка с номером r, такая, что
  (1.65)
  Она становится ведущей и определяет номер столбца , который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.
  2°. Определение столбца, вводимого в базис. Рассматривается ведущая строка . Возможны два варианта:
  2' . Для всех . Делается вывод об отсутствии допустимых, планов у решаемой задачи (D = ?) и завершается вычислительный процесс 6.
  2". В строке существует по крайней мере один элемент . Согласно правилу (1.62) определяются l - номер столбца, вводимого в очередной базис. Переходим к пункту 3° алгоритма.
  3°. Пересчет элементов матрицы и столбца относительно нового базиса. В соответствии с формулами (1.28)-( 1 .31 ) осуществляв^ расчет элементов матрицы задачи и вектора ограничений относительно нового базиса , который получается в результате вывода из базиса столбца аr и ввода в него столбца аl . Полагаем номер текущей итерации q:=q+1 и переходим к первому пункту алгоритма.
  По аналогии со стандартным симплекс-методом вычислительную процедуру двойственного симплекс-метода удобно оформлять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иногда считается целесообразным добавить к двойственной симплекс-таблице строку, содержащую строку со значениями , которые вычисляются на этапе определения столбца, вводимого в базис.
  1.7.3. Особенности применения двойственного симплекс-метода. Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исходного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть определен достаточно легко.
  Рассмотрим задачу минимизации:
  , (1.66)
 
  при ограничениях
  , ; (1.67)
 
  , , (1.68)
  где
 
  , (1.69)
  Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные хп+1, хп+2,..., хп+т :
  (1.70)
  (1.71)
  (1.72)
 
  Задача, двойственная к (1.70)-(1.72), будет иметь вид:
  (1.73)
 
  (1.74)
  (1.75)
 
  Из (1.74)-(1.75) очевиден допустимый план двойственной задачи
 
  (1.76)
 и исходный сопряженный базис, образуемый векторами . При этом начальный псевдоплан равен
 
  (1.77)
 
  Таким образом, при решении задачи вида (1.66)-(1.68) двойственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.
  Другое важное направление использования двойственного симплекс-метода связано с поиском оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как они уже были решены с помощью стандартной симплекс-процедуры. Типичными примерами таких изменений являются:
  > изменение компонент вектора ограничений b, что, допустим, может быть интерпретировано как корректировка объемов доступных ресурсов в процессе управления экономическим объектом;
  > добавление новых ограничений к системе условий задачи, что достаточно часто случается при совершенствовании используемой экономико-математической модели.
 
  В первом случае, т. е. при изменении вектора b, достоинства двойственного симплекс-метода очевидны, так как ранее найденный оптимальный базис можно использовать в качестве исходного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотрении методов решения целочисленных задач.
  В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод.
  1.7.4. Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b, в результате которых
 
 
 
 
  Содержание исходной симплекс-таблицы T(1) (за исключением столбца будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации в п. 1.5.2:
 
 
 
  В результате имеем:
 
 
 
 
 
 
 
 
 
 
 
 
 
  Как видно из таблицы Т(1), в столбце содержатся отрицательные элементы , то есть базис не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно - и . Далее рассматриваем строку . В ней имеются отрицательные элементы. Вычисляем , . , следовательно, номер столбца, вводимого в базис - l = 4. Осуществляем преобразование и получаем симплекс-таблицу Т(2).
 
 
 
 
 
 
 
 
 
 
  Поскольку , то достигнутый базис является оптимальным. Из T(2) можно выписать оптимальный план х* =(6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функции f(x*) = 444.
 
  КЛЮЧЕВЫЕ ПОНЯТИЯ
 
  > Общая задача линейного программирования (ОЗЛП).
  > Каноническая задача линейного программирования (КЗЛП).
  > Допустимый план.
  > Оптимальный план.
  > Первая геометрическая интерпретация ЗЛП.
  > Базисное решение ЗЛП.
  > Вторая геометрическая интерпретация ЗЛП.
  > Вырожденный и невырожденный план ЗЛП.
  > Симплекс-метод - метод последовательного улучшения плана.
  > Критерий оптимальности допустимого базисного плана.
  > Метод минимизации невязок.
  > Модифицированный симплекс-метод - вычислительная схема, связанная с преобразованием обратных матриц.
  > Двойственная задача линейного программирования.
  > Симметричность отношения двойственности.
  > Теоремы двойственности.
  > Экономическая интерпретация двойственных оценок.
  > Параметрическая устойчивость решения ЗЛП.
  > Двойственный симплекс-метод - метод последовательного уточнения оценок.
  > Сопряженный (двойственно допустимый) базис.
  > Опорный план и псевдоплан.
 
  КОНТРОЛЬНЫЕ ВОПРОСЫ
 
 1.1. Сформулируйте задачу линейного программирования.
 1.2. Дайте определение для следующих понятий: план, допустимый план, оптимальный план, решение задачи.
 1.3. Чем отличается общая задача линейного программирования от канонической?
 1.4. Всегда ли общую задачу линейного программирования можно привести к каноническому виду?
 1.5. Дайте определения для следующих понятий: аффинное множество, гиперплоскость, базис.
 1.6. Чем отличается выпуклый многогранник от многогранного выпуклого множества?
 1.7. В чем отличие понятий "линейная оболочка" и "выпуклая оболочка"?
 1.8. Любой ли конус является выпуклым множеством?
 1.9. Какая точка выпуклого множества называется угловой?
 1.10. В чем заключается первая геометрическая интерпретация задачи линейного программирования?
 1.11. В чем заключается вторая геометрическая интерпретация задачи линейного программирования? В чем ее отличие от первой?
 1.12. Какой план называется базисным?
 1.13. Как связаны базисные планы и угловые точки области определения задачи линейного программирования?
 1.14. Какой план задачи линейного программирования называется вырожденным?
 1.15. Как с точки зрения второй геометрической интерпретации можно представить процесс поиска оптимального плана в задаче линейного программирования?
 1.16. Сформулируйте критерий оптимальности допустимого базисного плана, применяемый в симплекс-методе.
 1.17. Сформулируйте основные этапы стандартной итерации симплекс-метода.
 1.18. Для чего применяется преобразование Жордана-Гаусса?
 1.19. Какой элемент симплекс-таблицы называется ведущим?
 1.20. При каких условиях делается вывод о неограниченности целевой функции в решаемой задаче? Какая геометрическая интерпретация соответствует данному случаю?
 1.21. Можно ли заранее точно определить количество итераций, которое потребуется для решения задачи симплекс-методом? Можно ли найти верхнюю границу для данной величины?
 1.22. Какая задача называется вырожденной? По каким признакам можно узнать, что текущий план является вырожденным?
 1.23. Какие проблемы возникают при решении вырожденных задач?
 1.24. Какую экономическую интерпретацию имеет ситуация вырожденности?
 1.25. В чем основная идея метода возмущений?
 1.26. Для чего предназначен метод минимизации невязок?
 1.27. Сформулируйте основные отличия модифицированного симплекс-метода по отношению к стандартному.
 1.28. Перечислите преимущества модифицированного симплекс-метода.
 1.29. Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее стандартным и модифицированным симплекс-методом?
 1.30. Дайте определение двойственной задачи.
 1.31. Какими основными свойствами обладает пара двойственных задач?
 1.32. В чем заключается экономическая интерпретация переменных двойственной задачи?
 1.33. Какой смысл вкладывается в понятие "параметрическая устойчивость"?
 1.34. Сформулируйте условия для допустимых изменений целевой функции задачи, при которых ее оптимальный план остается неизменным.
 1.35. Перечислите основные идеи, на которых базируется алгоритм двойственного симплекс-метода.
 1.36. Дайте определение сопряженного базиса.
 1.37. Что такое псевдоплан?
 1.38. Сформулируйте критерий оптимальности, используемый' в алгоритме двойственного симплекс-метода.
 1.39. По каким признакам можно определить, что множество допустимых планов задачи, решаемой двойственным симплекс-методом, пусто?
 1.40. В каких ситуациях могут быть реализованы преимущества двойственного симплекс-метода?
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

<< Пред.           стр. 5 (из 13)           След. >>

Список литературы по разделу