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

дена из базиса, чего мы и добивались.

После того как вычислены В-1 и с'вВ~г, следует проверить правиль­ ность расчетов, сопоставив полученные значения с соответствующими значениями в В£ов1При нахождении z и B^,,1 большую роль играет точ­ ность вычислений, в данном примере необходимо производить расчеты с точностью до шести значащих цифр. ЭВМ легко справляются с та­ кой работой; впрочем решение хв можно выполнить и вручную, так как при этом получаются не слишком громоздкие числа; далее следует отдельно подсчитать значение г.

254

Оптимальное решение теперь получено; можно проверить его, вернувшись к этапу 2'.

He следует проверять искусственные переменные, поскольку он» не могут вторично войти в базис из-за своих высоких коэффициентов затрат. Так как ни одно из значений (СвВ~1а'1 — cj) не больше 0, теку­ щее решение оптимально.

Сейчас мы находимся в угловой точке, лежащей в области допусти­ мых решений, как это всегда бывает в тех случаях, когда искусствен­ ные переменные удалены из базиса. Если бы эта точка не была опти­ мальным решением, мы продолжили бы процесс подобно тому, как это делалось ранее, чтобы перейти в соседнюю угловую точку, понижая при этом значение целевой функции, и так до тех пор, пока не дойдем до оптимального решения. В данном случае первая из достигнутых допустимых точек оказалась оптимальным решением; обычно это не так. В общей ситуации к моменту удаления искусственных переменных мы оказываемся в допустимой угловой точке, далее мы продолжаем процесс, используя этап 2 при решении задачи на максимизацию или соответственно этап 2' при решении задачи на минимизацию.

6. ВЫВОДЫ

Линейное программирование представляет собой важный инстру­ мент в решении задачи распределения ресурсов при наличии ограни­ чений. Оно важно как для изучения теоретических проблем, так и для приложений, поскольку это общий метод решения очень широкогокласса задач. Существует несколько методов, с помощью которых мож­ но получить решения; мы рассмотрели один из наиболее эффектив­ ных—модифицированный симплекс-метод. Хотя для описания линей­ ного программирования можно применять графический анализ, тем, не менее именно матричная алгебра оказывает наибольшую помощь- в общей постановке задач и при описании методов решения. Мы дали здесь краткое введение в эту область, не претендуя на полноту.изложе­ ния. Существует много побочных вопросов, других алгоритмов, воз­ можных усложнений и теоретических проблем, которые оказались не затронутыми в тексте. Для ознакомления с ними мы отсылаем читателя к работам Хедли [9] и Данцига [6], где дан полный анализ, предмета.

Некоторые весьма эффективные машинные программы позволяют решать очень большие задачи. Решение вручную даже малых задач утомительно. Именно существование машинных программ обеспечи­ вает экономическую возможность приложения линейного программи­ рования. В дополнение к обычным машинным программам существу-

255

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

Упражнения

1. Графически решите следующие задачи:

а) максимизировать г = 2хх + 5х2

при условии, что лу + Зх2 < 16,

ний, линию постоянных значений целевой функции, угловые точки и наилуч­ шее решение, расположенное в одной из угловых точек.

дает решение двойственной задачи, т. е. покажите, что решение задачи из упраж­ нения 3 может быть получено непосредственно из решения упражнения 1.

5. Решите с помощью модифицированного симплекс-метода следующие

7 x t + 4 х 2 > 2 0 ,

3xj + 4х2 < —6 ,

Xlt Х2 > 0.

6 . Покажите, что задача, двойственная к какой-либо двойственной задаче, совпадает с соответствующей основной задачей.

7. Запишите следующие задачи линейного программирования в форме, удобной для применения модифицированного симплекс-метода (не решайте их):

2 5 6

Выясните, почему эта задача может быть полезной для получения матрицы, об­ ратной к матрице

иполучите А - 1 этим способом

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

с положительными компонентами, который может быть использован при реше­ нии задачи.

10. Из упражнений 5а, 56 и 7а выпишите векторы и матрицы, позволяющие сформулировать задачу в матричной форме. Сделайте это для формулировки типа Ах < b (или Ах > Ь) и для формулировки типа А*х* = 6.

11.Решите задачу из примера на стр. 240 на нахождение >1аилучшего спо­ соба размещения.

12.Рассмотрите следующую задачу и двойственную к ней:

Определите, применяя лишь графический метод, значение целевой функции

воптимальной точке.

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

14.На сколько дополнительных единиц может возрасти значение целевой функции, если управляющий ослабит:

рицы 1т, соответствующей А*, то г'-й столбец В -1 состоит из нулей, за исключе­

нием своего /-го элемента, равного 1, и, следовательно, г/; в у' — св В -1 равен нулю. (Заметьте, что cBj — коэффициент прибыли дополнительной переменной

у в соответствующий столбец которой оказался /-м столбцом В,— равен нулю.)

variables subject to linear inequalities. In T. C. Koopmans (ed.), Activity Analy­

идинамическое программирование. М., «Мир»,- 1967.)

11.L a n c a s t e r К- (1968). Mathematical Economics. Macmillan, New York.

12.S t i g 1 е г G. J. (1945). The cost of subsistence. Journal of Farm Eco­ nomics, 27, 303—314.

13.W e i n g a r t n e r H. M. (1963). Mathematical Programming and the

Analysis of Capital Budgeting Problems. Prentice-Hall, Englewood Cliffs, N. J.