Математические методы исследования операций в экономике. Симплекс-метод

 

Он содержит два положительных  элемента. Применяя рекомендацию алгоритма, получаем λ₁=4/(1/3)=12, λ₂=14/3, и, стало быть r=2. Следовательно, столбец с номером N₂(β⁽¹⁾)=2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи N(β⁽²⁾) = {5, 4, 3}. Элемент a_2,3(β⁽¹⁾)  является ведущим (обведен кружком). Переходим к симплекс-таблице, соответствующей второй итерации T⁽²⁾, и полагаем индекс текущей итерации q = 2. 

 

 

 

В ходе выполнения второй итерации опять-таки определяются вводимый столбец а¹, выводимый а⁴ и ведущий элемент a_2,1(β⁽²⁾). Перейдя к итерации q = 3, имеем таблицу T⁽³⁾. 

 

 

 

Как видно из T⁽³⁾, строка оценок содержит только неотрицательные значения, поэтому достигнутый базис N(β⁽³⁾) = {5, 1, 3} является оптимальным. В итоге мы получаем, что вектор х^* = (7, 0, 31/3, 0, 5/3) является оптимальным планом (точкой максимума) задачи (11)-(12), максимальное значение целевой функции равно f*=f(х*)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362). 

 

3. Вычислительная схема, основанная на преобразовании обратных матриц.  Пример решения ЗЛП модифицированным симплекс-методом.

Анализируя вычислительную процедуру симплекс-метода с позиций  оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является этап пересчета значений А и b при переходе от одного базисного плана к другому. Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n, можно добиться существенной «экономии», выполняя на очередной итерации q преобразование  Жордана—Гаусса   не  над   матрицей А(β^(q)),   а   над   матрицей Δ^-1(β^(q)). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А(β^(q)) целиком. Реально в ней использовались только строка оценок a₀(β^(q))  и ведущий столбец a^l(β^(q)). Данные соображения положены в основу вычислительной схемы симплекс-метода, основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.

Приведем решение рассмотренной  ранее задачи (11)-(12), основанное на использовании процедуры модифицированного симплекс-метода. Оно начинается с выбора очевидного исходного базиса, образуемого столбцами {5,2,3}. Для него уже были вычислены Δ^-1(β^(q)) и b(β^(q)), поэтому заполнение начальных таблиц T₁ и Т₂⁽¹⁾ не представляет труда.

На первой итерации мы переписываем нулевую строку 

 

 

из Т₂⁽¹⁾ в T₁ и, умножив ее на матрицу A, получаем строку оценок 

 

 

 

Так как a₀(β⁽¹⁾) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β⁽¹⁾, и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l = 4.

Переписываем столбец 

 

 

 

из таблицы T₁ в Т₂⁽¹⁾ и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу Δ^-1(β^(q)), расположенную в таблице Т₂⁽¹⁾  слева, на а⁴. 

 

 

 

 

 

После заполнения таблицы Т₂⁽¹⁾ данными по вводимому в новый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов b_i(β⁽¹⁾)  и a_i,l(β⁽¹⁾)  для {iÎ1:m| a_i,l(β⁽¹⁾)>0} и определив минимальное из них, находим, что r = 2. Следовательно, столбец с номером N₂(β^(q))=2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с N(β⁽²⁾) = {5, 4, 3}. Элемент a_2,3(β⁽¹⁾)  является ведущим (обведен кружком). Переходим к симплекс-таблице, соответствующей второй итерации Т₂⁽²⁾, и полагаем индекс текущей итерации q = 2.

Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам Т₂⁽²⁾ и Т₂⁽³⁾, на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т₂⁽³⁾.

 

 

4. Понятие двойственной задачи ЛП. Экономическая интерпретация.

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

 

 

 

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

(13)

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

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

(14)

     то задача ЛП

(15)

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

Традиционная экономическая  интерпретация двойственной задачи ЛП базируется на модели простейшей задачи производственного планирования, описанной во введении. Напомним, что в ней каждый (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 

 

(16)

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

 

(17)

 

Учитывая, что

(18)

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

 

(19)

 

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

 

5. Двойственный симплекс-метод. Пример решения ЗЛП двойственным симплекс-методом.

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

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

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

Рис. 2                                   Рис. 3

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

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

• изменение компонент вектора ограничений b, что, допустим, может быть интерпретировано как  корректировка объемов доступных ресурсов в процессе управления экономическим объектом;
• добавление новых ограничений к системе условий задачи, что достаточно часто случается при совершенствовании используемой экономико-математической модели.

 

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

Рассмотрим на конкретном, примере процесс решения КЗЛП двойственным симплекс-методом. Для этого вернемся к задаче (11)-(12). Предположим, что произошли изменения в векторе ограничений b в результате которых

 

Содержание исходной симплекс-таблицы T⁽¹⁾ (за исключением столбца b(β⁽¹⁾)) будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного ранее. Для вычисления значений b(β⁽¹⁾) в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации:

 

В результате имеем:

 

Как видно из таблицы Т⁽¹⁾, в столбце b(β⁽¹⁾) содержатся отрицательные элементы b₁(β⁽¹⁾) = - 1/3<0), то есть базис β⁽¹⁾ ={ ⁵, ¹, ³} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(β⁽¹⁾) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — r = 1 и N₁(β⁽¹⁾)=5. Далее рассматриваем строку a₁(β⁽¹⁾) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем λ₂ =42:(-(-1/6))=252, λ₄ =38:(-(-1/6))=228. λ₂> λ₄, следовательно, номер столбца, вводимого в базис — l = 4. Осуществляем преобразование и получаем симплекс-таблицу T⁽²⁾.

 

Поскольку b(β⁽²⁾) >0, то достигнутый базис N(β⁽²⁾) = {4,1,3} является оптимальным. Из Т⁽²⁾ можно выписать оптимальный план х* = (6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функции f(x*)= 444.