Анализ затраты - выпуск появился раньше, чем линейное программирование. Его исторические корни можно обнаружить уже в работах Франсуа Кенэ (1694-1774) - придворного медика мадам Помпадур и Людовика XV, прежде всего в "Экономической таблице" ("Tableau Ёсоnоmique"), где представлено движение потоков продукции между тремя общественными классами: фермерами, земельными собственниками и промышленниками. Исследование процесса капиталистического воспроизводства Карлом Марксом также содержит элементы анализа затраты - выпуск. Основная заслуга в создании современного варианта этого анализа принадлежит лауреату Нобелевской премии американскому экономисту В. В. Леонтьеву, который впервые изложил основы указанного метода в 1936 г., а затем - в 1941 г.- дал его полное описание.1
Первоначально при анализе затраты - выпуск рассматривалась замкнутая экономическая система: все товары, производимые в одних секторах системы, выступали как потенциальные затраты в других. Так, потребительские товары рассматривались как затраты, необходимые для создания "услуг труда". В период после начала второй мировой войны все большее внимание стала привлекать открытая модель. В открытой модели уже не требуется, чтобы все товары носили промежуточный характер; я предполагается, что существуют основные факторы (такие элементы, которые выступают в качестве производственных факторов, но сами невоспроизводимы,- например, земля) и конечные продукты (такие блага, как, например, кинофильмы; их можно произвести, но нельзя использовать для изготовления других благ). В такой модели принимается, что объем первичных факторов и структура конечного спроса определяются экзогенно (вне рассматриваемой системы), и анализ затраты - выпуск используется для того, чтобы определить объемы производства в различных отраслях, соответствующие заданному конечному спросу. Открытая модель затраты - выпуск использовалась, например, для решения задач мобилизованного планирования в условиях войны: в таких условиях с помощью модели определяли, как изменится распределение ресурсов в различных секторах экономики, если конечный спрос будет удовлетворяться "пушками" вместо "масла".
Основная идея анализа затраты - выпуск состоит в том, что связь между выпуском продукции и объемом затрат носит линейный характер. Анализ затраты - выпуск относится практически только к процессу производства; теория спроса не играет при этом никакой роли (в отдельных случаях она может быть использована, но и тогда ее роль несущественна). Во-вторых, особое значение в анализе затраты - выпуск придается ситуации общего равновесия, достигающегося благодаря взаимосвязи производственных планов множества отраслей, составляющих экономику в целом. В-третьих, анализ затраты - выпуск предназначен для эмпирических исследований. Именно эмпирическая направленность отличает указанное направление от моделей Вальраса и опубликованных в последующий период работ в области теории общего равновесия. Практическим преимуществом моделей затраты - выпуск, позволяющим использовать их в эмпирическом анализе, служит их относительная простота: модель затраты - выпуск охватывает не столь широкий круг явлений, как модель общего равновесия. Четвертую особенность анализа затраты - выпуск составляет его тесная связь с линейным программированием: для того, чтобы определить "наилучшее распределение ресурсов" в модели затраты- выпуск, следует решить соответствующую задачу линейного программирования.
Развитие линейного программирования связано прежде всего с именем Джорджа Б. Данцига.2 Метод линейного программирования, разработанный в 1947 г., использовался при планировании операций Военно-Воздущных Сил США. В последующем линейное программирование стало применяться при решении задач планирования и управления производством, а затем составным элементом вошло в экономическую теорию.3
Анализ затраты - выпуск
Матрица межотраслевых потоков
Рассмотрим модель затраты - выпуск леонтьевского типа, используя для этого простой пример. Пусть экономика включает всего две отрасли: сельское хозяйство и промышленность. В качестве затрат на производство продукции каждой отрасли непосредственно используется такой первичный фактор производства, как труд, а также продукция другой отрасли. Межотраслевые потоки в этой экономике представлены в табл. 1, которая, как можно заметить, мало отличается от "Экономической таблицы" Кенэ.
Таблица 1
| Матрица межотраслевых потоков | ||||||||||||||||||||
|
Каждому виду благ соответствует отдельная строка. Читая таблицу по строкам, можно видеть, как используется валовой выпуск каждого из выпускаемых видов продукции. В промышленности, например, за год было произведено 30 единиц продукции, которая оказалась поровну распределенной между сельским хозяйством, промышленностью и конечным спросом. Точно так же последняя строка показывает, что из 40 единиц труда, использованного в течение года, 20 единиц было занято в сельском хозяйстве и 20 - в промышленности.
Приведенные величины можно складывать по строке, поскольку они измерены в одних и тех же натуральных единицах. Складывать указанные элементы по столбцу нельзя, так как в разных строках используются неодинаковые единицы измерения. Однако каждый столбец, рассматриваемый как единое целое (или как вектор), все же имеет определенный смысл. Первый и второй столбцы представляют собой значения аргументов соответствующих производственных функций для отдельных отраслей. Так, первый столбец показывает, что, затратив 20 единиц продукции сельского хозяйства, 10 единиц продукции промышленности и 20 единиц труда, можно произвести 60 единиц продукции сельского хозяйства.
Экономику, описываемую с помощью данных табл. 1, можно рассматривать как черный ящик, который преобразует 40 единиц труда в выпуск чистой продукции, включающей 30 единиц сельскохозяйственной продукции и 10 единиц промышленных товаров, предназначенных для конечного потребления. Остается определить, какие еще сочетания продуктов могут входить в состав конечного потребления.
Матрица затрат
Табл. 1 использовалась только для описательных целей. Чтобы превратить ее в инструмент анализа, необходимо ввести некоторые дополнительные предположения. Назовем сельское хозяйство отраслью 1, промышленность - отраслью 2, а труд будем обозначать индексом "О". Тогда данные, приведенные в табл. 1, можно представить в общем виде (см. табл. 2).
Таблица 2
|
Производственные функции теперь можно записать в следующем виде:
X1 = f1(x11, x21, x01),
X2 = f2(x12, x22, x02).
Леонтьев использует сильное допущение, в соответствии с которым производственные функции 'имеют следующую форму:
где аij - минимальные затраты продукта i, необходимые для производства одной единицы продукта j.4 Нетрудно убедиться в том, что тем самым предполагается постоянная эффективность использования ресурсов при изменении масштабов производства, т. е. если все хij увеличить в одно и то же число раз, то и Хj, возрастет ровно во столько же раз. Изокванты таких производственных функций, предполагающих фиксированные соотношения используемых факторов производства, представляют собой поверхности, пересекающиеся под прямыми углами.
Для того чтобы с помощью данных табл. 1 найти значения aij, надо просто разделить элементы первого столбца на сумму элементов первой строки, а элементы второго столбца - на сумму элементов второй строки; рассчитанная таким образом матрица
дает (при допущениях Леонтьева) полное описание технологии производства, применяемой в народном хозяйстве. Такую матрицу обычно называют матрицей коэффициентов] прямых затрат (inputre quirements matrix).
Граница потребительских возможностей
Теперь когда, мы уже умеем описывать технологию, используемую в экономике, можно перейти к вопросу о том, какие структуры ("Меню") конечного спроса оказываются возможными при заданном объеме затрат труда.
Чтобы произвести одну единицу товара 1, необходимо затратить по меньшей мере а11 единиц товара 1, а21 единиц товара 2 и а01 единиц труда. Следовательно, для производства Х1 единиц товара 1 потребуется а11Х1 единиц товара 1, а21Х2 единиц товара 2 и a01X1 единиц труда. Точно так же для производства Х2 единиц товара 2 необходимо затратить по крайней мере а12Х2 единиц товара 1, a22X2 единиц товара 2 и а02Х2 единиц труда. Суммируя необходимые затраты обоих продуктов, получаем: общий объем потребности в затратах продукта 1 равен а11Х1 + а12Х2; общий объем потребности в затратах продукта 2 равен а21Х1 + а22Х2, и общий объем потребности в затратах труда составляет а01Х1 + a02X2
Очевидно, что общее количество каждого товара, используемого для производства и для конечного потребления, должно удовлетворять следующим ограничениям:
а11Х1 + а12Х2 + c1 ≤ X1.
а21Х1 + а22Х2 + c2 ≤ X2.
а01Х1 + а02Х2 + c0 ≤ X0.
После некоторых преобразований можно записать эти ограничения следующим образом:
X0 ≥ a01Х1 + а02Х2 (2)
При такой записи видно, что вектор потребления не может быть больше, чем линейная комбинация векторов (1 - a11, -a21) и (a12, 1 - a22), взятых с неотрицательными весами Х1 и Х2. Совокупность всех таких линейных комбинаций представлена на рис. 1 заштрихованной областью. Вдумываясь в смысл уравнения (1), можно заключить: если мы хотим увеличить размеры потребления, следует сделать так, чтобы величины Х1 и Х2 были как можно больше. Уравнение (2) задает ограничение на затраты труда и тем самым устанавливает пределы для значений Х1 и Х2, так как комбинация a01 и a02 взятых с весами Х1 и Х2, не может превышать Х0.
Представим на минуту, что весь труд затрачивается в производстве продукта 1. Тогда из уравнения (2) должно следовать, что Х1 = Х0/а01, а Х2 = 0. При таких весах структура конечного потребления характеризуется точкой А на рис. 1. А теперь прибегнем к прямо противоположному предположению: допустим, что все затраты труда целиком направляются на производство продукта 2; в таком случае структура конечного потребления описывается точкой В. Однако ни одна из этих двух точек не может считаться допустимой. В точке А для производства продукта отрасли 1 необходимо затратить продукт отрасли 2 в количестве, характеризуемом отрезком Od, что, разумеется, невозможно, поскольку количество труда, выделенное для отрасли 2, равно нулю, и поэтому продукт 2 вообще не производится. Точно так же в точке В, когда весь труд используется только в отрасли 2, необходимы затраты продукта 1 в количестве Ое, но продукт 1 при этом вообще не выпускается.
 Рис.1 |
Теперь рассмотрим случай, когда некоторая доля, скажем одна треть, всех ресурсов труда направляется в отрасль 1, а оставшиеся две трети - в отрасль 2. То, что одна треть всего труда используется в отрасли 1, означает, что мы перемещаемся на одну треть расстояния ОА из начала координат в направлении точки А. (Получившаяся точка обозначена на рис. 1 буквой D.) А так как две трети всего количества труда используется в отрасли 2, то мы получаем точку Е, которая расположена на расстоянии 2/3 0В от начала координат (в направлении точки В). Сложив векторы OD и ОЕ, получим точку F, которая описывает соответствующий вектор конечного потребления.
 Рис.2 |
Заметим, что весь валовой выпуск отрасли 1 измеряется расстоянием по горизонтали от точки О до точки D; из этой величины на производство продукта 2 используется часть, характеризуемая расстоянием по горизонтали от точки О до точки Е. Точно так же из всего валового выпуска отрасли 2 (измеряется расстоянием по вертикали от точки О до точки Е) на производство продукта 1 используется количество, равное по величине расстоянию по вертикали от точки 0 до точки D. Таким образом, точка F показывает, какое количество продуктов отраслей 1 и 2 остается для конечного потребления. Нетрудно убедиться, что точка F должна лежать на отрезке, соединяющем точки В и А, а точнее, находиться на расстоянии, равном одной трети длины этого отрезка, отсчитываемой от точки В.5
При иных вариантах распределения всего объема затрат труда между отраслями 1 и 2 мы получим в качестве возможных векторов потребления другие точки, также лежащие на отрезке АВ. Часть отрезка АВ, соответствующую неотрицательным значениям объемов потребления обоих продуктов, а именно отрезок GH, обычно называют границей потребительских возможностей.
С помощью рис. 1 нетрудно определить, как отражаются на потребительских возможностях изменения различных параметров. Например, увеличение общего объема затрат труда сместило бы точку А еще дальше по лучу OD, а точку В - по лучу ОЕ, одновременно отрезок GH "сдвинулся" бы дальше от начала координат. С другой стороны, если сокращается минимум затрат труда, необходимых для производства продукта 1, т. е. уменьшается a01, то точка А сместится вниз по лучу OD, тогда как точка В останется на прежнем месте.
Различные спецификации модели затраты - выпуск
Получив общее представление об открытой модели (с одним первичным фактором), рассмотрим теперь более подробно различные спецификации модели затраты - выпуск. В данном разделе мы познакомимся с закрытой и открытой моделями общего вида, открытой моделью с несколькими первичными факторами, леонтьевской моделью с несколькими технологиями, неоклассической моделью и моделью, предполагаемой анализом производственных процессов (activity analysis model).
Выше уже отмечалось, что в основе закрытой модели лежит предпосылка, согласно которой все производимые блага представляют собой промежуточные товары. Экзогенный конечный спрос и экзогенное предложение первичных факторов производства отсутствуют; каждый товар изготовляется внутри системы и в свою очередь используется для производства других товаров. В соответствии со введенными выше обозначениями аij представляет собой количество товара i, необходимое для производства единицы товара j. Сведем все коэффициенты затрат в матрицу
Как и прежде, элементы i-й строки показывают, какое количество товара i необходимо для производства единицы этого товара и каждого из (n - 1) остальных товаров. Столбец j рассматривается как вектор, показывающий объем необходимых затрат различных товаров на производство единицы продукта j.
Чтобы произвести продукцию различных отраслей в объемах, представленных вектором валовых выпусков (вектором предложения)
необходимы затраты в объеме, равном ах (вектор спроса). При равновесии разность между спросом и предложением по каждому из товаров равна нулю. Таким образом, равновесные объемы валового выпуска по отраслям, х, должны удовлетворять уравнению
x* = ax*, или [I - а] х* = 0.
Условия, при которых существует равновесное решение закрытой модели, исследованы в целом ряде работ. Одно из условий, одновременно необходимое и достаточное, заключается в том, что характеристический корень матрицы а должен быть равен единице.6
Открытая модель отличается от замкнутой тем, что вводится вектор экзогенного конечного спроса (с). В этом случае условие равновесия (равенство спроса и предложения по всем товарам) записывается в следующем виде:х* = ах* + с. Валовой выпуск равен сумме спроса на факторы производства и конечного спроса. Как и раньше, эту запись можно упростить:
[I - a] х* = с, или х* = [I - а]-1 с. (3)
Для существования решения в этом случае достаточно чтобы наибольший по модулю характеристический корень матрицы а был меньше 1.7 Решение уравнения (3) в явном виде демонстрирует, что равновесные объемы (валового) выпуска зависят от экзогенно задаваемых размеров конечного спроса. Определив величины ∂xi/∂cj = [I - а]-1ij мы найдем, в какой пропорции должно возрасти производство г-го товара при увеличении конечного спроса на товар j.
Чтобы получить открытую модель, включающую первичный фактор производства, достаточно прибегнуть к небольшой модификации. В дополнение к условию равновесия, задаваемому уравнением (3), введем условие полной занятости:
а0х* = L, где a0 = (а01, а02,...,a0n),
которое представляет вектор минимальных затрат первичного фактора, необходимых для производства единицы каждого из товаров 1, 2, . . ., n, а символ L обозначает наличные ресурсы первичного фактора. Из уравнения (3) и условия полного использования (полной занятости) фактора получаем следующее соотношение: L = a0 [I - а]-1 с. Указанное соотношение может служить характеристикой границы производственных возможностей.8
Чтобы перейти к описанию открытой модели с несколькими первичными факторами, введем новое обозначение: bij будет означать минимальное количество i-го первичного фактора, необходимое для производства одной единицы j-го продукта; объединим эти коэффициенты в матрицу следующего вида:
Ограниченность ресурсов означает, что bx ≤ s, где s = (s1, s2,..., sm)T представляет собой вектор имеющихся объемов каждого из m первичных факторов.9 Из данногонеравенства и условия равновесия, согласно которому х* = [I - а]-1 с, можно определить границу производственных возможностей.
b [I - а]-1c ≤ s. (4)
На рис. 2 приведена иллюстрация для случая n = 2, m = 2; уравнение (4) включает два линейных неравенства с двумя неизвестными, с1 и c2. В общем случае уравнение (4) содержит m линейных неравенств с n неизвестными.
Каждый грамотный экономист знает, что теоретическая концепция, которая оперирует количествами товаров, обязательно должна упоминать и их цены. Не составляет исключения и анализ затраты - выпуск. Символом w = (w1, w2,..., wm) будем обозначать цены первичных факторов производства, а символом р = (р1, р2,..., pn) - цены изготовляемых продуктов. Тогда условие конкурентного равновесия, согласно которому величина прибыли ни в одной из отраслей не должна представлять собой положительную величину, задается системой неравенства
Согласно этому неравенству, валовой доход от продажи единицы продукции не должен превышать величины удельных производственных издержек. В матричной записи система неравенств выглядит следующим образом: p ≤ pa + wb или, прибегнув к некоторым преобразованиям,10 можно записать:
p ≤ wb [I - а]-1. (5)
Матрица b [I - а]-1 имеет размерность m × n; элемент матрицы, стоящий на пересечении i-й строки и j-го столбца, можно рассматривать как размеры совокупных прямых и косвенных затрат i-го первичного фактора, необходимых для производства одной единицы продукта j.11 Умножив эту матрицу справа на вектор конечного спроса (с), получаем общее количество первичных факторов требующееся для производства различных видов дедукции в размерах, удовлетворяющих конечный опрос с [уравнение (4)]. Умножив эту матрицу слева на вектор w, можно определить суммарные издержки, связанные с производством единицы каждого из указанных видов продукции [уравнение (5)]. Если m = 1, иначе говоря, в нашей модели предполагается использование лишь одного первичного фактора, например только живого труда, равновесные цены равны цене труда, умноженной на вектор, характеризующий прямые и косвенные затраты труда в каждой из отраслей. В этом случае цены прямо пропорциональны количеству труда, "воплощенного" в продуктах, и, следовательно, справедливы простейшие утверждения теории трудовой стоимости.
Рассмотрим теперь еще одно обобщение модели затраты - выпуск, которое называют "леонтьевской моделью с несколькими технологиями". Эта модель предполагает, что предприниматели могут выбирать различные технологии для производства одного и того же продукта. Например, на рис. 3 изображен случай, когда единицу j-го продукта можно произвести, используя любое из трех сочетаний (A, В и С) двух видов затрат. Более того, поскольку и здесь мы предполагаем, что при изменении масштабов производства его эффективность остается постоянной, то 1/2 единицы этого продукта можно произвести при комбинации затрат, отвечающей точке на середине отрезка 0В, а еще 1/2 - при комбинации затрат, отвечающей точке на середине отрезка ОС. Суммируя эти векторы, мы получим точку D, лежащую посредине отрезка ВС. Точка D также соответствует допустимой комбинации затрат, с помощью которых можно произвести единицу продукта. Очевидно, что все другие "выпуклые комбинации" технологий также могут считаться допустимыми, и любая комбинация затрат, которой соответствует точка заштрихованной области на рис. 3, позволяет произвести одну единицу j-го продукта.
В общем виде модель с несколькими технологиями формулируется следующим образом. Пусть аij представляет собой количество i-го товара, необходимое, чтобы j-и производственный процесс протекал с единичной интенсивностью, а dij - количество i-го товара, производимого при единичной интенсивности j-го производственного процесса. Будем полагать, что с1ц равно единице, если в ходе j-го процесса производится продукт i, а в противном случае dij = 0. Например, если
это означает, что первые три процесса позволяют произвести товар, которому присвоен номер один, а четвертый и пятый процессы - товар номер два. При этом предполагается, что каждый технологический процесс позволяет изготовить только один вид продукта: в каждом столбце матрицы d единица встречается только один раз.
Пусть символ xj обозначает интенсивность j-го производственного процесса; тогда вектор валовых выпусков, соответствующий вектору интенсивности производственных процессов х = (x1,..., xr)T, может быть задан произведением dx. Точно так же вектор затрат, необходимых для производства данного количества продуктов, задается произведением ах, а вектор затрат первичных ресурсов - произведением bх, где bij теперь обозначает количество i-го первичного ресурса, необходимое для осуществления j-го производственного процесса с единичной интенсивностью. Равновесие производства, т. е. равенство спроса и предложения по каждому из производимых продуктов, выражается соотношением ах = ах + с, или
(d - а) х = с, (6)
а ограничение на ресурсы - неравенством
bx ≤ s. (7)
В этой модели границы потребительских возможностей экономики заданы условиями (6) и (7).
 Рис.3 |
Для поддержания равновесного уровня цен необходимо: 1) чтобы каждый процесс, используемый в настоящий момент для производства данного продукта, приносил нулевую прибыль; 2) чтобы прибыль, которую может обеспечить любой другой процесс, не применяемый в настоящий момент для производства того же продукта, не превышала прибыли, приносимой используемым процессом, иначе говоря, чтобы все остальные производственные процессы либо характеризовались нулевой прибылью, либо приносили убытки. Обозначая, как и прежде, символом р цены производимых товаров и символом w цены первичных ресурсов, можно записать следующее соотношение: pd ≤ pa + wb, где равенство выполняется по крайней мере для одного из производственных процессов в каждой отрасли (именно этот процесс - или один из этих процессов - и будет использован). Тогда, обозначив символами d, 
и b матрицы, соответствующие этому единственному процессу, который используется в соответствующей отрасли, можно записать следующее равенство: 
, или 
. Такой набор производственных процессов, включающий по одному процессу для каждой отрасли, называют технологией. А поскольку можно составить множество возможных сочетаний различных производственных процессов, модель и называется "леонтьевской моделью с несколькими технологиями". Как будет показано в следующем разделе, выбор технологии может быть обеспечен в результате решения задачи линейного программирования.
и b матрицы, соответствующие этому единственному процессу, который используется в соответствующей отрасли, можно записать следующее равенство: , или . Такой набор производственных процессов, включающий по одному процессу для каждой отрасли, называют технологией. А поскольку можно составить множество возможных сочетаний различных производственных процессов, модель и называется "леонтьевской моделью с несколькими технологиями". Как будет показано в следующем разделе, выбор технологии может быть обеспечен в результате решения задачи линейного программирования.
Неоклассическая модель представляет собой естественное обобщение леонтьевской модели с различными технологиями. В ней предполагается постоянная эффективность при изменении масштабов производства. В этой модели предприниматели могут выбирать из бесконечного множества процессов, задаваемого уравнением: 1 = fj (аij,..., anj,; bij,..., bmj),- один какой-либо процесс, используемый для производства товара j. Как и прежде, коэффициенты аij здесь обозначают размеры затрат, необходимых для производства товаров, а bij - необходимые объемы затрат первичных факторов. Единственное отличие состоит в том, что множество возможных процессов теперь бесконечно велико; в леонтьевской же модели предполагалось существование конечного числа производственных процессов. На рис. 4 изображен случай, когда n = 2, а m = 0. Для производства единицы товара 2 можно использовать любую комбинацию затрат, которая соответствует точке, лежащей на единичной изокванте для первого товара (скажем, комбинацию, соответствующую точке A), а для производства товара 2 - любую комбинацию затрат, которая соответствует одной из точек единичной изокванты, рассчитанной для второго товара (например, точке В). Таким образом, неоклассическая модель представляет собой "сглаженный" вариант леонтьевской модели с несколькими технологиями; во многих cлучаях неоклассическую модель можно интерпретировать как некую предельную аппроксимацию леонтьевской модели, допускающей различные технологии.
 Рис.4 |
Завершим наш краткий обзор моделью, предполагаемой анализом производственных процессов. Она представляет собой некоторую модификацию модели с несколькими технологиями: в этом случае снимается условие, согласно которому в каждом производственном процессе создается только один продукт. Вновь рассмотрим матрицу d. где элемент, стоящий на пересечении i-й строки и j-го столбца, dij, предполагался равным единице, если с помощью j-го процесса можно производить товар i, а в противном случае был равен нулю. Ранее мы исходили иа того, что в каждом столбце матрицы единица встречалась только один раз. Теперь мы снимем это условие и предположим, что число ненулевых элементов в каждом столбце матрицы может быть больше, чем один. Например, матрица
описывает случай, когда с помощью 2-го, 3-го и 5-го процессов можно произвести оба товара - 1 и 2.12 Предположение о том, что при некоторых сочетаниях факторов производства можно изготовлять одновременно несколько продуктов, существенно расширяет границы анализа. Так, используя эту модель, можно исследовать проблему загрязнения окружающей среды, когда одновременно с "полезными" продуктами производятся и "вредные"; можно также изучать любые вопросы, связанные с "внешними" эффектами хозяйственной деятельности ("externalities").13
Линейное программирование
Геометрическая интерпретация
В ходе анализа затраты - выпуск часто возникает следующая задача: надо найти такое распределение ресурсов, которое обеспечивает максимальный объем продукта, направляемого для удовлетворения конечного спроса (национального продукта) при заданных ценах. В обозначениях леонтьевской модели, предполагающей использование нескольких первичных факторов производства, это значит, что мы стремимся максимизировать произведение рс при ограничениях на ресурсы, задаваемых уравнением (4), а также при очевидном ограничении на неотрицательность величины c ≤ 0. Иначе говоря, мы хотим максимизировать линейную функцию управляемых переменных (сi) при наличии ряда ограничений, которые представлены системой линейных неравенств, включающих эти переменные. Подобную задачу можно решить с помощью методов линейного программирования.
Мы можем легче разобраться в сути линейного программирования, если усвоим, что представляет собой "стандартная форма" линейного уравнения. Возьмем простой пример: 4x1 + 3x2 = 30, или в матричной записи
Множество решений данного уравнения, т. е. множество всех упорядоченных пар (x1, x2), удовлетворяющих этому уравнению, можно представить в виде прямой, перпендикулярной вектору (4,3) и отделенной от начала координат расстоянием, равным 
, причем это расстояние отсчитывается по оси вектора (4,3).
, причем это расстояние отсчитывается по оси вектора (4,3).
Этот случай показан на рис. 5. Сначала нанесем на график точку, соответствующую вектору коэффициентов рассматриваемого уравнения - упорядоченной паре (4,3), а затем изобразим вектор как исходящую из начала координат стрелку, острие которой попадает в точку с координатами (4,3). Эта стрелка представляет собой гипотезу прямоугольного треугольника со сторонами, длина которых соответственно равна 4 и 3 единицам, поэтому и длина вектора равна 
. Затем разделим постоянный член линейного уравнения (30) на число, характеризующее длину вектора коэффициентов (5), в результате получим величину, равную 6. Точка А расположена на расстоянии в 6 единиц от начала координат, отсчитываемом в задаваемом стрелкой направлении. Теперь построим прямую, проходящую через точку А и перпендикулярную стрелке. Эта прямая и представляет собой множество решений нашего уравнения: если умножить координаты любой точки данной прямой на вектор коэффициентов Уравнения (4,3), то всегда в точности получим число 30.
. Затем разделим постоянный член линейного уравнения (30) на число, характеризующее длину вектора коэффициентов (5), в результате получим величину, равную 6. Точка А расположена на расстоянии в 6 единиц от начала координат, отсчитываемом в задаваемом стрелкой направлении. Теперь построим прямую, проходящую через точку А и перпендикулярную стрелке. Эта прямая и представляет собой множество решений нашего уравнения: если умножить координаты любой точки данной прямой на вектор коэффициентов Уравнения (4,3), то всегда в точности получим число 30.
Рассмотрим уравнение, постоянный член которого равен большему числу:
Так же как и раньше, разделим постоянный член уравнения на число, характеризующее длину вектора, в результате получим теперь число 7. Точка В расположена на расстоянии в 7 единиц от начала координат, отсчитываемом в направлении, которое задано стрелкой. Прямая, перпендикулярная стрелке и проходящая через точку В, описывает множество решений нового уравнения.
 Рис.5 |
В том случае, если бы уравнение имело следующий вид:
нам надо было бы построить прямую, проходящую через начало координат (расстояние от начала координат тогда составляло бы 0/5) и было бы перпендикулярно стрелке.
Наконец, допустим, что уравнение содержит отрицательный постоянный член, например:
В таком случае для того, чтобы определить местоположение прямой, нужно было бы отложить от начала координат 2 единицы в направлении, противоположном направлению стрелки. Именно в этом и заключается смысл выражения "направленное расстояние" ("directed distance"):
положительные расстояния откладываются в направлении, указываемом стрелкой, а отрицательные - в противоположном направлении.
Тот же способ описания линейных уравнений используется и в тех случаях, когда приходится иметь дело с пространствами большей размерности. В этом и состоит главное достоинство "стандартного представления" линейного уравнения. Мы можем рассмотреть, например, следующее уравнение в трехмерном пространстве:
Как и прежде, построим стрелку, соответствующую вектору коэффициентов, и найдем ее длину (
), затем разделим число 7 на величину, характеризующую длину вектора. Отложив от начала координат расстояние 
в направлении, указываемом стрелкой (это направление соответствует знаку "+"), получим точку, через которую проведем плоскость, перпендикулярную отложенному вектору. Построенная таким образом плоскость и описывает множество решений уравнения.
), затем разделим число 7 на величину, характеризующую длину вектора. Отложив от начала координат расстояние в направлении, указываемом стрелкой (это направление соответствует знаку "+"), получим точку, через которую проведем плоскость, перпендикулярную отложенному вектору. Построенная таким образом плоскость и описывает множество решений уравнения.
Точно так же поступаем и в случае, когда пространство оказывается n-мерным. Пусть задано уравнение следующего вида:
Вычислим длину вектора коэффициентов:
и разделим число b на эту величину. Множество решений нашего уравнения представляет собой гиперплоскость, ортогональную вектору коэффициентов, а направленное расстояние гиперплоскости от начала координат равно b/|а| . Понятие "ортогональный"- это обобщение понятия "перпендикулярный" на n-мерный случай (гиперплоскость перпендикулярна вектору по всем тем (n - 1) направлениям, когда имеет смысл понятие перпендикулярности. Описанную поверхность называют гиперплоскостью потому, что она играет ту же роль в n-мерном пространстве, которую в трехмерном пространстве играет обычная плоскость: гиперплоскость делит n-мерное пространство на два полупространства (попасть с одной стороны гиперплоскости на другую можно, только "проткнув" насквозь гиперплоскость).
С учетом всего сказанного становится понятным, почему множество решений следующего линейного неравенства:
представляет собой одно из полупространств, образованных гиперплоскостью ах = b; иначе говоря, множество решений неравенства включает все точки, лежащие по одну сторону указанной гиперплоскости. Так, множество решений в одном из предшествовавших примеров, изображенном на рис. 5,
включает все точки, которые лежат как ниже гиперплоскости в данном случае (прямой), проходящей через точку А, равно как и на самой гиперплоскости (прямой).14 Если изменить знак неравенства на обратный, множество решений будет содержать точки, лежащие как выше гиперплоскости, так и на самой гиперплоскости.
Графическое решение
С математической точки зрения полупространства представляют собой очень "удобные" множества: они являются выпуклыми (отрезок прямой, соединяющей любые две точки данного множества, полностью принадлежит этому же множеству) и замкнутыми (данное множество содержит все свои предельные точки). Полупространства играют важную роль в задачах линейного программирования. Чтобы убедиться в этом, рассмотрим стандартную задачу линейного программирования: пусть требуется отыскать
при следующих ограничениях:
и
где символы еj, Аij и ri; характеризуют известные параметры задачи, тогда как xj неизвестны. Понятно, что в матричной форме указанную задачу можно записать следующим образом:
Множеством решений для каждого линейного неравенства Аix ≤ ri входящего в число ограничений, будет служить полупространство. Точно так же для каждого ограничения x ≥ 0 множество решений представляет собой полупространство; это можно еще более наглядно показать, представив указанные ограничения в следующем виде:
и т. д. Точки х, одновременно удовлетворяющие всем ограничениям-неравенствам, должны одновременно принадлежать всем полупространствам, соответствующим этим неравенствам, иначе говоря, они должны принадлежать пересечению всех перечисленных полупространств. А пересечение любого числа замкнутых выпуклых множеств само является замкнутым выпуклым множеством. Такое пересечение содержит те значения x, которые удовлетворяют всем ограничениям, оно называется допустимым множеством.15 На рис.6 приведен пример для случая n = 2, m = 2. Допустимое множество представлено заштрихованной областью, оно представляет собой пересечение n + m = 4 различных полупространств.
 Рис.6 |
Чтобы решить задачу линейного программирования, требуется отыскать такую точку x, принадлежащую допустимому множеству, которой соответствует наибольшее значение целевой функции ex. Рассмотрим теперь, что представляют собой линии уровня данной целевой функции, т. е. линии, все точки которых характеризуют одно и то же значение целевой функции: ex = constant. Последнее соотношение, как мы уже знаем, представляет собой уравнение гиперплоскости, ортогональной вектору е; "направленное расстояние" гиперплоскости от начала координат пропорционально заданному численному значению постоянной величины. Если константа равна О, то гиперплоскость проходит через начало координат. Будем теперь увеличивать значение постоянной величины; в этом случае гиперплоскость будет смещаться в направлении, заданном вектором е, удаляясь от начала координат. В результате мы получим целое "семейство" гиперплоскостей. Обратимся к примеру, изображенному на рис. 6. Нетрудно видеть, что постоянная величина, которая соответствует гиперплоскости, проходящей через точку 2, меньше, чем константа, которая соответствует гиперплоскости, проходящей через точку 6, а постоянная величина для гиперплоскости, проходящей через точку 6, в свою очередь уступает той, которая соответствует гиперплоскости, проходящей через точку 4. Каждая из перечисленных выше гиперплоскостей располагается "все дальше" от начала координат.
Рассмотрим линию уровня целевой функции, представленную гиперплоскостью, которая проходит через точку 4. На этой линии уровня лежит всего одна точка, принадлежащая допустимому множеству, а именно точка 4. Что же касается всех остальных точек допустимого множества, то они принадлежат тем линиям уровня, которые соответствуют меньшим значениям целевой функции. Следовательно, в нашем примере точка 4 служит Решением задачи. В общем случае задача решается столь же просто: мы ищем такую допустимую точку х, которая принадлежит самой удаленной от начала координат линии (гиперплоскости) уровня целевой функции.16
Симплекс-метод
Благодаря тому, что целевая функция линейна, решение задачи линейного программирования всегда лежит на границе допустимого множества; двигаясь из любой внутренней точки множества по направлению к его границе всегда можно "выйти" к искомой линии (поверхности) уровня. Более того, по крайней мере одна вершина угла (из числа тех углов, которые образованы пересечением) граничных линий допустимого множества) всегда служит решением этой задачи. Если же поверхности уровня целевой функции будет принадлежать целая грань допустимого множества, например грань 4-6 на рис. 6, то решением задачи с одинаковым успехом можно считать любую вершину угла, принадлежащего этой грани, и вообще любую точку грани (на рис. 6 - вершины углов, представленные точками 4 и 6, а также все точки указанной грани, т. е. отрезка, соединяющего вершины 4 и 6). Это значит, что для отыскания оптимального решения достаточно найти даже не просто границу допустимого множества, а одни только вершины соответствующих углов. Поскольку же число таких вершин конечно, то подобное сужение области поиска решения значительно облегчает) вычислительные процедуры.
Можно еще больше упростить расчеты. Использовав дополнительные переменные xn+i ≡ ri - Аiх (i = 1,..., m), запишем "каноническую задачу" в новом виде:)
причем вектор х теперь содержит (n + m) компонент. Дополнительные компоненты вектора коэффициентов целевой функции, соответствующие новым переменным xn+i, равны нулю; что же касается матрицы А, то она расширена за счет добавления единичной матрицы размерностью m × m (единичная матрица - это матрица, у которой по диагонали расположены единицы, а остальные элементы представляют собой нули). Из сказанного ясно, что новая постановка задачи полностью эквивалентна первоначальной.
В чем состоит смысл введения дополнительных переменных? Допустим, что xn+i = 0, тогда Aix = ri;, иначе говоря, если введенная дополнительная переменная равна нулю, то соответствующее ограничение становится жестким (в этом случае оно выполняется как равенство). Кроме того, из определения этих переменных следует: когда хn+i принимает положительные значения, то Аiх < ri.
Рассмотрим теперь пример, когда n = 2 (см. рис. 7). Пусть точка х' характеризует такое допустимое решение, при котором i-е ограничение не является жестким (выполняется как строгое неравенство). Тогда, по определению переменной xn+i, Аiх' = ri - xn+i;, причем xn+1 > 0. Обратим внимание на следующее обстоятельство: Aix = ri представляет собой уравнение гиперплоскости, "направленное расстояние" которой от начала координат равно OD = ri/|Ai|.
 Рис.7 |
Аналогичным образом Aix = ri - xn+i - уравнение такой гиперплоскости, которая параллельна упомянутой выше, но расположена на расстоянии ОС = (ri - xn+i)/|Ai| от начала координат. А это значит, что решение, представленное точкой x, отделено от соответствующего ограничения расстоянием, равным
CD = OD - ОС = ri/|Ai| - (ri - xn+i)/|Ai| = xn+i/|Ai|.
Отсюда видно, что значение рассматриваемой дополнительной переменной пропорционально "направленному расстоянию" точки-решения от того ограничения, которому соответствует указанная дополнительная переменная.
Теперь рассмотрим всю систему ограничений, фигурирующих в канонической задаче: (А | I) х = r. Система ограничений представляет собой систему m уравнений, содержащих (n + m) переменных. Известно, что m-мерный вектор r всегда можно представить в форме линейной комбинации m линейно независимых столбцов матрицы (A|I).17 Следовательно, мы можем выбрать любые m линейно независимых столбцов матрицы А, приравнять нулю те значения xi, которые соответствуют остальным столбцам рассматриваемой матрицы, и решить задачу лишь относительно остальных xi. Такое решение, которое будет содержать не более m нулевых значений xi, обычно называют базисным решением. Если же, кроме того, все xi в этом решении неотрицательны, оно называется допустимым базисным решением.
Геометрически базисное решение соответствует пересечению гиперплоскостей ограничений. Допустимое базисное решение соответствует вершине допустимого множества. Для задачи, представленной на рис. 6, существует 6 базисных решений.
Таблица 3
Обратите внимание, что только точки 1, 2, 4 и 6 являются допустимыми базисными решениями; при выборе остальных точек некоторые xi оказываются отрицательными. Рассмотрим, например, точку 3: в этом случае x1 = О, х2 > О (что видно непосредственно из рис. 6), а x3 (точка 3 находится на нулевом расстоянии от первого ограничения), x4 < 0 (расстояние точки 3 от второго ограничения характеризуется отрицательной величиной, поскольку оно отсчитывается в "обратную сторону").
|
Обратите внимание, что только точки 1, 2, 4 и 6 являются допустимыми базисными решениями; при выборе остальных точек некоторые xi оказываются отрицательными. Рассмотрим, например, точку 3: в этом случае x1 = О, х2 > О (что видно непосредственно из рис. 6), а x3 (точка 3 находится на нулевом расстоянии от первого ограничения), x4 < 0 (расстояние точки 3 от второго ограничения характеризуется отрицательной величиной, поскольку оно отсчитывается в "обратную сторону").
Теперь мы можем перейти к непосредственному изложению симплекс-метода. Заметим, что при m = 2 и n = 2 существует
способов выбрать два m = 2 линейно независимых столбца, а в общем случае будет существовать
базисных решений. Алгоритм симплекс-метода представляет собой не что иное, как способ, или процедуру, последовательного перебора базисных решений с целью отыскать решение задачи линейного программирования. Алгоритм симплекс-метода носит итеративный характер; отталкиваясь от некоторого допустимого базисного решения, мы последовательно решаем, какой вектор-столбец следует ввести в базис, а какой - вывести из состава векторов, образующих базис, чтобы тем самым приблизиться к оптимальному решению.
Геометрически симплекс-метод можно представить следующим образом. Прежде всего требуется найти какое-нибудь допустимое базисное решение. Заметим, что в нашей задаче (как и во всех обычных задачах, предполагающих отыскание максимума) простейшим допустимым базисным решением может служить начало координат, т. е. точка, у которой
xi = О (i = 1,..., n),
xn+i = ri (i = 1,..., m).
Обратимся к примеру, изображенному на рис. 6. В этом случае предполагается, что мы начинаем движение из точки 1, причем базис образуют третий и четвертый столбцы) матрицы
Значение целевой функции в этой точке, очевидно, равно нулю:
e1·0 + e2·0 + 0·r1 + 0·r2 = 0.
Теперь наша задача состоит в том, чтобы определить какой столбец следует ввести в базис. Какую из двух переменных - x1 или х2 - сделать положительной? Предположим, что значение х1 увеличивается от 0 до 1. Тогда целевая функция возрастет на е1 единиц. Точно так же в тех случаях, когда значение х2 возрастет от 0 до 1, значение целевой функции увеличится на е2 единиц*.В нашем примере предполагается, что е1 > е2, и нам выгоднее придать положительное значение х1, а не х2. Поэтому выберем первый столбец матрицы (А|I) и введем его в базис.18
Можно выбрать столбец и другим способом. Повернем рис. 6 таким образом, чтобы вектор коэффициентов целевой функции (е1, е2) был направлен вертикально вверх, а перпендикулярная вектору прямая, проходящая через начало координат, заняла бы горизонтальное положение. Можно перемещаться из начала координат в любом из двух направлений: либо вверх по оси x1, либо вверх по оси x2. Движение по оси x1 обеспечивает более крутой подъем (если отсчитывать от горизонтальной линии, образованной линией уровня целевой функции); поэтому мы и выбираем переменную х2.
Теперь нам предстоит выбрать, какую из переменных - x3 или x4 - приравнять нулю, или, что то же самое, какой столбец матрицы (A|I) - третий или четвертый - вывести из базиса. Из табл. 3 видно, что если мы выведем из базиса третий столбец, то решение переместится в точку 6; если же вывести четвертый столбец, то решение сместится в точку 5. Заметим, что выбрать столбец, который мы исключаем из базиса, значит решать вопрос о том, насколько далеко мы продвинемся вдоль оси х1. Так как при этом необходимо оставаться в пределах допустимого множества, мы должны остановиться в точке первого пересечения; поэтому мы исключаем из базиса третий столбец и перемещаемся в точку 6.
Теперь начинаем описанную процедуру снова. У нас есть допустимое базисное решение, представленное точкой 6. При этом в состав базиса входят первый и четвертый столбец. Дальше мы можем двигаться в двух направлениях: либо спускаться вниз по оси x1 к началу координат, если мы решим вернуть в базис третий столбец, либо двигаться по грани 4-6, если мы предпочитаем ввести в базис второй столбец. Исходя из ориентиров, определяемых новой горизонтальной линией (ею по-прежнему служит та же линия уровня целевой функции), мы можем обнаружить, что, двигаясь в обратном направлении вдоль оси x1, мы будем "возвращаться вниз" (иначе говоря, значение целевой функции будет уменьшаться), а двигаясь по грани 4-6, мы будем подниматься вверх. Выбираем второе направление и вводим в базис второй столбец матрицы (А|I). Чтобы выбрать столбец, который следует исключить из базиса, снова нужно найти, насколько далеко можно продвинуться в заданном направлении. Если исключить из базиса четвертый столбец, то мы попадем в точку 4, а если первый, то переместимся в точку 3. Требование, согласно которому решение должно принадлежать допустимому множеству, вновь заставляет нас остановиться на первой из упомянутых точек пересечения. Поэтому следует вывести из базиса четвертый столбец.
Теперь допустимое базисное решение содержит первый и второй столбцы матрицы (A|I) и соответствует точке 4 на рис. 6. Перед нами снова два возможных направления движения: по грани 2-4 или по грани 4-6. В первом случае пришлось бы вводить в базис третий столбец, а во второй - четвертый. Сверившись с ориентирующей нас горизонтальной линией, находим, что как в первом, так и во втором случаях это будет означать перемещение вниз: ни в каком из этих двух направлений значение Целевой функции не возрастает. Отсюда заключаем, что найдено оптимальное решение задачи линейного программирования.
Итак, симплекс-метод - это алгоритм восхождения До граням допустимого множества; мы движемся по направлению наибольшей крутизны подъема до тех пор, пока не будет найдено оптимальное решение. Основное Достоинство описанного метода состоит в том, что итеративную процедуру можно разложить на простые правила, ввести в программы для ЭВМ. Электронно-вычислительные машины, снабженные соответствующими программами, могут решать большие и невероятно сложные задачи линейного программирования.19
Двойственность
Исходной задаче линейного программирования
соответствует непосредственно связанная с ней "двойственная задача":
В последние годы была проделана большая работа по исследованию взаимосвязей между этими двумя задачами. Были получены неожиданные и весьма важные результаты: оказалось, например, что если х* является оптимальным решением исходной задачи, а w* - оптимальным решением двойственной задачи, то ex* = w*r, т. е. оптимальные значения обеих целевых функций, совпадают между собой. Далее, если i-я дополнительная переменная исходной задачи в точке оптимума характеризуется положительным значением (i-e ограничение не является жестким), то в точке оптимального решения двойственной задачи wi* равно нулю. В свою очередь если wi* положительно, то i-е ограничение исходной, или основной, задачи должно быть жестким (должно выполняться как равенство). Эти свойства позволяют интерпретировать wi* как некую "теневую цену", соответствующую i-му ограничению исходной задачи, иначе говоря, wi* показывает, на сколько увеличится найденное оптимальное значение целевой функции в основной задаче, если ri возрастает на одну единицу. Возвращаясь к леонтьевской модели, предполагающей функционирование нескольких первичных факторов производства, поставим следующую задачу линейного программирования:
Тогда оптимальные значения wi*s, найденные при решении двойственной задачи следующего вида:
могут играть роль равновесных цен первичных ресурсов, связанных с ценами выпускаемой продукции р. Если бы наличные ресурсы i-го первичного фактора возросли на единицу, то национальный продукт рс* увеличился бы на величину, равную wi*. В ограничениях двойственной задачи читатель без труда узнает условие равновесия, которое требовало, чтобы ни одна из рассматриваемых отраслей не получала прибыли (это условие уже было сформулировано выше, см. уравнение (5)).20
Университет Дюка
ПРИМЕЧАНИЯ:
1 Leontief W.W. Quantitative Input and Output Relation in the Economic System of the United States.- Review of Economic Statistics (August 1936), p. 105-125; Leontief W.W. The Structure of American Economy, 1919-1939. Cambridge, Harvard University Press, 1941.
2 Dantzig D. Maximization of a Linear Function of Variables Subject to Linear Inequalities.- В: К о о p m a n s Т. С. (e d.). Activity Analysis of Production and Allocation. New York, John Wiley & Sons, 1951.
3 Dorfman R., Samuelson P., S о 1 о w R. Linear Programming and Economic Analysis. New York, McGraw-Hill, 1958. Это классическое руководство по применению линейного программирования для решения самых разнообразных экономических проблем.
4 Запись min (x, у, z) означает, что среди чисел х, у, z выбирается самое меньшее.
5 Поскольку D = 1/3 А, а Е = 2/3 В, то 1/3 А + 2/3 В = D + Е = F.
6 См.: К а r 1 i n S. Mathematical Methods and Theory of Games, Programming and Economics. Reading, Mass., Addison-Wesley, 1959, ch. 8 (русский перевод: К а р л и н С. Математические методы в теории игр, программировании и экономике. М., "Мир" 1964).
7 См., например: Graham D.A.A Geometrical Exposition of Input-Output Analysis.- American Economic Review 65 (March 1975), p. 115-126.
8 Это линейное уравнение, содержащее n неизвестных: С1, С2,..., Сn. Множество решений составляет так называемую гиперплоскость, которая в n-мерном пространстве представляет собой то же, что обычная плоскость - в трехмерном пространстве.
9 Верхний подписной знак Т указывает на транспонирование.
10 Здесь мы предполагаем, что все элементы матрицы [I - a]-1 неотрицательны. Указанное условие выполняется, когда наибольший по модулю характеристический корень матрицы а меньше единицы.
11 Если наибольший по модулю (выполняется условие равновесия, о котором шла речь выше) и характеристический корень матрицы а меньше единицы, то [I - а]-1 = I + а + а2 + а3 + ... и b [I - а]-1 = b + bа + bа2 + bа3 + ... . В последнем выражении нетрудно распознать сумму прямых затрат первичных факторов, косвенных затрат первого порядка, косвенных затрат второго порядка и т. д. Обратите внимание, что для создания какого-либо изделия приходится приложить столько труда, сколько необходимо непосредственно в производстве этого товара, плюс столько, сколько потребуется для производства тех ресурсов, которые используются в качестве затрат при производстве этого изделия, плюс тот труд, который необходим для того, чтобы произвести продукты, используемые при изготовлении упомянутых ресурсов и т. д.
12 Вообще говоря, нельзя требовать, чтобы все элементы были либо нулями, либо единицами, поскольку уровень производства, обеспечивающий выпуск единицы одного товара, может вместе с тем предполагать изготовление нескольких единиц (или долей единицы) другого товара.
13 См., например: Maler K.-G. A Study in Environmental Economics. Baltimore, John Hopkins University Press, 1974.
14 В двухмерном пространстве прямая совпадает с гиперплоскостью; в одномерном пространстве роль гиперплоскости играет точка. Заметим, что размерность гиперплоскости всегда на единицу меньше размерности соответствующего пространства.
15 Обратите внимание на то, что такое пересечение - допустимое множество - может оказаться пустым. Это бывает тогда, когда задача плохо поставлена и попросту не имеет решения.
16 В задаче на отыскание минимума решение расположено на самой близкой изокванте. И в том, и в другом случаях оптимальное решение существует, когда допустимое множество решений ограничено, иначе говоря, когда отсутствует возможность бесконечно перемещать линию уровня целевой функции "вовне" (в задаче на максимум) или "вовнутрь" (в задаче на минимум). Речь идет, естественно, о перемещении "вовне" и "вовнутрь" вдоль направления, задаваемого вектором коэффициентов целевой функции.
17 В m-мерном пространстве любые m линейно независимых векторов образуют базис. См., например: N i k а i d о Н. Introduchtion to Sets and Mappings in Modern Economics, New York, North Holland American Elsevier, 1970, p. 48-57.
18 Отметим, что в произведении (А|I) х, xi, по существу, может интерпретироваться как "вес" i-го столбца матрицы (А|I). Так что, когда мы решаем сделать х, положительным, это равносильно тому, что мы просто включаем в базис i-й столбец матрицы (А|I).
19 Read R. A Mathematical Background for Economists and Social Scientists. Englewood Cliffs, N.Y., Prentice-Hall, 1972. В гл.16 более подробно рассмотрена формальная сторона симплекс-метод.
20 Читатели, которых интересует более подробный анализ данного вопроса, могут обратиться к книге: I n t r i 1 1 i g a t о r М. Mathematical Optimization and Economic Theory. Englewood Llitts, N.Y., Prentice-Hall, 1971, ch. 5 (русский перевод: И н т р и л л и г а т о р М. Математические методы оптимизации и экономическая теория. М., "Прогресс", 1975).
