Файл: Сирл, С. Матричная алгебра в экономике.pdf

Еще две угловые точки могут быть получены из систем: Злу + 2х2 = = 8, хх = 0; и 2лу + Зх2 = 7, х2 = 0; но они недопустимы, т. е. они не лежат в области допустимых решений.

Поскольку установлено, что оптимальное решение есть всегда уг­ ловая точка области допустимых решений, задача значительно упро­ стилась. Если имеется я неизвестных х1у ..., хп и яг + я ограничений,

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

в) МАТРИЧНАЯ ФОРМУЛИРОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Обычно в линейном программировании имеют дело с задачами, сформулированными в виде одной из следующих форм:

где с есть я-мерный вектор коэффициентов целевой функции (обычно коэффициенты характеризуют удельную прибыль или затраты); -X—я-мерный вектор переменных решения (неизвестных); А — матри­ ца «технологических коэффициентов» размером m X я; Ь — яг-мерный вектор дефицитных ресурсов с bt > 0, i = 1 , ..., m\ z — значение

целевой функции; > означает соответственно «больше», «равно», -«меньше».

Пример. Теперь рассмотренную ранее задачу (1) можно сформу­ лировать в матричных терминах:

Оба технологических ограничения относятся к типу «меньше чем ...». В данном параграфе рассматриваются задачи формы I (максими­ зация) с ограничением «меньше.чем ...». В параграфе 2 рассматривают­ ся задачи формы II (минимизация); в параграфе 3 излагается пробле­ ма смешанных ограничений (как «меньше чем ...», так и «больше чем...»), а также освещен случай, когда ограничения представлены ра­

1 Последовательность аи а2, ..., ап, ... называется неубывающей монотонной, если ап < ап+1 для всех п.

г) ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЫЕ

Запишем задачу (2) в несколько измененной форме: максимизировать z = с*'х*

новая форма идентична первоначальной за небольшим исключением: множество т дополнительных переменных, введенных по одной в каж­ дое из неравенств Ах ^ Ь, превратило неравенства в равенства. Из требования неотрицательности этих дополнительных переменных и равенства нулю связанной с ними прибыли следует, что если х*

Когда задача записана в форме (3), то можно прямо применять модифи­ цированный симплекс-метод. Как указывалось, этот метод решения задач линейного программирования проверяет допустимые угловые точки. Хотя существует бесконечно много векторов х*, таких, что А*х* = Ь, х* > 0, угловых точек, удовлетворяющих условиям Ах ^ Ь, х >- 0, всегда конечное число*1.

**Эти переменные иногда называют балансовыми или выравнивающими. —

Прим. ред.

1 С помощью обобщенной обратной матрицы из главы VII можно найти всех*, удовлетворяющие уравнению А*х* = Ь; однако в данном случае из равенства

ограничения на отрицательность. Таким образом, хотя метод обощенных обрат­ ных матриц и является общей формой для всех решений урвнения А*х* =; Ь, он не может ничем помочь при поиске оптимального решения задачи линейного программирования.

228

д ) Б А З И С

Базисом мы называем здесь матрицу т х т, столбцами которой являются т линейно-независимых столбцов матрицы А*. Поскольку А* = [А I т], всегда существует по крайней мере один набор из т линейно-независимых столбцов матрицы А*, полученный с помощью единичной матрицы 1т, Далее, из того, что А* содержит т -г п столб­

однозначно соответствует некоторой угловой точке, хотя среди этих точек могут быть и недопустимые. Например, рассмотрим базис В, состоящий из k столбцов (матрицы А) соответствующих переменных, входящих в х, и m — k столбцов (матрицы /), ассоциированных с пе­ ременными, входящими в xs. Напомним, что из результатов главы VII

ние методом расчленения дает

В данном случае х равен х*, матрица Аг есть В, уг равен Ь, а хх пред ставляет собой т- мерный вектор решения для переменных, соответст­ вующих базису В. Мы назовем этот вектор Хв вектором базисных пе­ ременных. Выражение (4) можно переписать с учетом введенных обоз­ начений в форме

мы находим одновременно решение системы уравнений А*х* = Ь. Это решение ассоциировано с единственной угловой точкой: посколь­ ку k переменных, входящих в xs, приравнены к нулю (т — k ассо­ циированы с хв), то k неравенств Ах < b должны обратиться в ра­ венства; кроме того, п — k переменных, входящих в х, приравнены к нулю, что обращает в равенства соответствующие им ограничения неотрицательности. Таким образом, исходные переменные, входящие в х*, будут решением системы из п уравнений, образованной превра­ щением неравенств типа Л х < Ь и х | > 0 в равенства. Единственное решение этой системы по определению является угловой точкой. Каждый базис связан с единственной угловой точкой, которая в за­ висимости от того, удовлетворяет она или нет всем остальным ограни­ чениям, либо будет, либо не будет допустимой.

Пример. В задаче (1) существует шесть базисов, которые следую­ щим образом связаны с угловыми точками:

229

Два последние базиса соответствуют недопустимым угловым точкам, и при решении задачи с применением модифицированного симплексметода они не будут приниматься во внимание.

Прежде чем подробно описать в матричных обозначениях этапы модифицированного симплекс-метода, мы обратимся к задаче на ми­ нимизацию и некоторым обобщениям.

Мы сначала рассмотрим случай, когда условия представлены одно­ сторонними неравенствами типа «больше чем ...» (другие возможные случаи рассматриваются в параграфе 3). Задачи минимизации обычно встречаются в ситуациях, где надо достигнуть некоторого опреде­ ленного уровня заданной характеристики при минимальных затратах. В следующем примере рассматривается такой случай.

230