233

Павел Владимирович Конюховский

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

Серия «Краткий курс»

Главный редактор В. Усманов

Заведующий редакцией Л. Волкова

Художественный редактор В. Земских

Верстка Е. Маслова

Корректоры Н. Викторова, Н. Солнцева

ББК 22.183я7+65.529 УДК 519.8(075)+658.012.122(075)

Конюховский П.В.

К65 Математические методы исследования операций в экономике--СПб: Питер, 2000. -- 208 с.: ил. -- (Серия «Краткий курс»).

ISBN 5-8046-0190-3

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

Серия книг «Краткий курс» предназначена для студентов экономических и управленческих специальностей всех форм обучения, а также для всех интересующихся соответствующей темой.

© Конюховский П.В., 2000

© Серия, оформление, Издательский дом «Питер», 2000

Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав.

ISBN 5-8046-0190-3

ЗАО «Издательство "Питер"». 196105, Санкт-Петербург, ул.-Благодатная, 67.

Лицензия ЛР № 066333 от 23.02.99.

Налоговая льгота -- общероссийский классификатор продукции ОК 005-93, том 2,95 3000 -- книги и брошюры.

Подписано в печать 04.08.2000. Формат 60x90/16. Усл. п. л. 13.

Доп. тираж 5000. Заказ № 881.

Отпечатано с готовых диапозитивов в АООТ «Типография „Правда"». 191119, С.-Петербург, Социалистическая ул., 14.

СОДЕРЖАНИЕ

Предисловие

Введение

Глава 1. Линейное программирование

1.1 Постановка задачи линейного программирования

1.2 Основные свойства ЗЛП и ее первая геометрическая интерпретация

1.3 Базисные решения и вторая геометрическая интерпретация ЗЛП

1.4 Симплекс-метод

1.5. Модифицированный симплекс-метод

1.6 Теория двойственности в линейном программировании

1.7. Двойственный симплекс-метод

Ключевые понятия

Контрольные вопросы

Глава 2. Нелинейное программирование

2.1. Методы решения задач нелинейного программирования

2.2. Двойственность в нелинейном программировании

Ключевые понятия

Контрольные вопросы

Глава 3. Транспортные и сетевые задачи

3.1. Транспортная задача и методы ее решения

3.2. Сетевые задачи

Ключевые понятия

Контрольные вопросы

Глава 4. Дискретное программирование

4.1. Типы задач дискретного программирования

4.2.Метод Гомори

4.3.Метод ветвей и границ

Ключевые понятия

Контрольные вопросы

Глава 5. Динамическое программирование

5.1. Общая схема методов динамического программирования

5.2. Примеры задач динамического программирования

Ключевые понятия

Контрольные вопросы

Глава 6. Краткий обзор других разделов исследования операций

6.1. Теория игр

6.2. Теория оптимального управления

Ключевые понятия

Контрольные вопросы

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



ПРЕДИСЛОВИЕ

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

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

Обращаясь к задачам и проблемам, составляющим предмет исследования операций, нельзя не вспомнить о вкладе, внесенном в их решение представителями отечественной научной школы, среди которых в первую очередь должен быть назван Л.В. Канторович, ставший в 1975 г. лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике.

Предлагаемая вашему вниманию книга задумана как учебное пособие для специалистов в области экономики и управления предприятиями, и призвано создать общее представление о типах задач, изучаемых в исследовании операций, методах их решения и принципиальных идеях, лежащих в основе этих методов. Математические аспекты предмета по отношению к поставленным перед настоящим изданием целям не являются первостепенными. Однако, по мнению автора, попытки излагать те или иные результаты в полном отрыве от математического аппарата, на основе которого они получены, являются несостоятельными и выхолащивающими объективную количественную сторону изучаемых объектов. Поэтому для понимания излагаемого здесь материала от читателя потребуется определенное владение базовыми знаниями из соответствующих разделов математического анализа и линейной алгебры. Необходимо признать, что любая книга экономико-математического направления может быть подвергнута критике либо за чрезмерную перегруженность математическими изысками и оторванность от реальной экономической проблематики, либо за отсутствие математической строгости и корректности, и, естественно, каждый автор, исходя из своих вкусов, представлений и умения, ищет оптимальное сочетание того и другого. Ну а о том, насколько это удается, судит читатель...

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

Несколько замечаний по используемым в ходе изложения условным обозначениям:

Ш базовые понятия предмета при их первом появлении в тексте выделяются курсивом, а наиболее важные их них (те, которые стоит не забывать и после прочтения!) -- жирным шрифтом;

Ш перед фундаментальными определениями стоит символ; <

Ш количество приводимых в данной книге теорем минимизировано (это, однако, не должно создать у неподготовленного читателя превратного впечатления об их действительном количестве); в тех местах, где встречается теорема, ее формулировка выделяется слева двойной чертой;

Ш доказательство теоремы завершается символом. ^

Автор выражает искреннюю благодарность и признательность своим коллегам по кафедре экономической кибернетики СПбГУ В.Ф. Капустину и А.А. Канарейкину за ценные советы и замечания, способствовавшие улучшению качества настоящего учебного пособия.

ВВЕДЕНИЕ

Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л.В. Канторовича «Математические методы организации и планирования производства», вышедшая в 1939 г. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Дж. Данцига, посвященная решению линейных экстремальных задач.

Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что «исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами» [14].

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

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

1. Постановка задачи.

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

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

4. Решение задач, сформулированных на базе построенной математической модели.

5. Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели.

6. Реализация полученного решения на практике.

Центральное место в данной книге отведено вопросам, относящимся к четвертому пункту приведенной выше схемы. Это делается не потому, что он является самым важным, сложным или интересным, а потому, что остальные пункты существенно зависят от конкретной природы изучаемой системы, в силу чего для действий, которые должны производиться в их рамках, не могут быть сформулированы универсальные и содержательные рекомендации. По этому поводу, например, X. Таха заметил, что исследование операций одновременно является как наукой, так и искусством [27].

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

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

Управление портфелем активов. Рассмотрим проблему принятия инвестором решения о вложении имеющегося у него капитала. Набор характеристик потенциальных объектов для инвестирования, имеющих условные имена от А до F, задается следующей таблицей.

Название	Доходность (в %)	Срок выкупа (год)	Надежность (в баллах)
А	5,5	2001	5
В	6,0	2005	4
С	8,0	2010	2
D	7,5	2002	3
Е	5,5	2000	5
F	7,0	2003	4

Предположим, что при принятии решения о приобретении активов должны быть соблюдены условия:

a. суммарный объем капитала, который должен быть вложен, составляет $ 100 000;

b. доля средств, вложенная в один объект, не может превышать четверти от всего объема;

c. более половины всех средств должны быть вложены в долгосрочные активы (допустим, на рассматриваемый момент к таковым относятся активы со сроком погашения после 2004 г.);

d. доля активов, имеющих надежность менее чем 4 балла, не может превышать трети от суммарного объема.

Приступим к составлению экономико-математической модели для данной ситуации. Целесообразно начать процесс с определения структуры управляемых переменных. В рассматриваемом примере в качестве таких переменных выступают объемы средств, вложенные в активы той или иной фирмы. Обозначим их как х_А, х_В, х_С, х_D, х_E, х_F. Тогда суммарная прибыль от размещенных активов, которую получит инвестор, может быть представлена в виде

(1)

На следующем этапе моделирования мы должны формально описать перечисленные выше ограничения a-d на структуру портфеля.

a) Ограничение на суммарный объем активов:

x_A + x_B + x_С + x_D + x_E + x_F 100 000 . (2)

b) Ограничение на размер доли каждого актива:

х_А 25 000, х_В 25 000, х_С 25 000,

x_d 25 000, х_е 25 000, x_f 25 000. (3)

c) Ограничение, связанное с необходимостью вкладывать половину средств в долгосрочные активы:

х_В + х_С 50 000 (4)

d) Ограничение на долю ненадежных активов:

x_C + x_D 30 000. (5)



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

х_А 0, х_B 0, х_C 0, x_D 0, х_Е 0, x_F 0. (6)

Выражения (1)-(6) образуют математическую модель поведения инвестора. В рамках этой модели может быть поставлена задача поиска таких значений переменных х_а, х_B, х_C, x_d, x_e, х_F, при которых достигается наибольшее значение прибыли (т. е. функции (1)) и одновременно выполняются ограничения на структуру портфеля активов (2)-(6).

Перейдем теперь к рассмотрению более общих моделей и задач.

Простейшая задача производственного планирования. Пусть имеется некоторый экономический объект (предприятие, цех, артель и т. п.), который может производить некоторую продукцию п видов. В процессе производства допустимо использование т видов ресурсов (сырья). Применяемые технологии характеризуются нормами затрат единицы сырья на единицу производимого продукта. Обозначим через a_i,j количество i-го ресурса (i 1: m), которое тратится на производство единицы j-го продукта (j1:n). Весь набор технологических затрат в производстве j-го продукта можно представить в виде вектора-столбца

а технологию рассматриваемого предприятия (объекта) в виде прямоугольной матрицы размерности т на п:



Если j-й продукт производится в количестве x_j, то в рамках описанных выше технологий мы должны потратить a_1,j x_j первого ресурса, a_2,j x_j -- второго, и так далее, a_mj x_j -- т-го. Сводный план производства по всем продуктам может быть представлен в виде n-мерного вектора-строки x = (x_1, x₂,...,x_j,...,x_n) . Тогда общие затраты по i-му ресурсу на производство всех продуктов можно выразить в виде суммы

представляющей собой скалярное произведение векторов а_j и х. Очевидно, что всякая реальная производственная система имеет ограничения на ресурсы, которые она тратит в процессе производства. В рамках излагаемой модели эти ограничения порождаются m-мерным вектором b = (b_1, b₂,...,b_m), где b_i -- максимальное количество i-го ресурса, которое можно потратить в производственном процессе. В математической форме данные ограничения представляются в виде системы т неравенств:

a_1,1 x_l+a_l,2x₂+...+a_l,n x_n b_l,

o_2,l x_l+a_2,2 x₂+...+a_2,n x_n b₂,

a_m,_l x_l+a_m,2 x₂+...+a_m,n x_n b_n. (7)

Применяя правила матричной алгебры, систему (7) можно записать в краткой форме, представив левую часть как произведение матрицы А на вектор х, а правую -- как вектор b:

Ах b. (8)

К системе (8) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства: x₁, 0,..., x_j 0, ..., х_п 0, или, что то же самое,

x 0. (9)

Обозначив через с_j цену единицы j-го продукта, получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором х:

(10)

Формулы (8)-(10) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого экономического объекта, поведением которого мы хотим управлять. В рамках данной модели, вообще говоря, можно поставить различные задачи, но, скорее всего, самой «естественной» будет задача поиска такого плана производства xRⁿ, который дает наибольшее значение суммарного дохода, т. е. функции (10), и одновременно удовлетворяет системе ограничений (8)-(9). Кратко такую задачу можно записать в следующем виде:

где (11)

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

Поскольку любая научная модель содержит упрощающие предпосылки, для корректного применения полученных с ее помощью результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее «сильным» упрощением в рассмотренной модели является предположение о прямо пропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат а_i,j. Очевидно, что это допущение далеко не всегда выполняется. Так, объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно в зависимости от изменения компонентов объема производства х. К другим упрощающим предпосылкам относятся предположения о независимости цен с_j от объемов х_j, что справедливо лишь для определенных пределов их изменения, пренебрежение эффектом кооперации в технологиях и т. п. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления совершенствования модели.

Транспортная задача. Рассмотрим проблему организации перевозки некоторого продукта между пунктами его производства, количество которых равно m, и n пунктами потребления. Каждый i-й пункт производства (i 1: т) характеризуется запасом продукта а_i 0, а каждый j-и пункт потребления (j 1: п) -- потребностью в продукте b_j 0. Сеть дорог, соединяющая систему рассматриваемых пунктов, моделируется с помощью матрицы С размерности т на п, элементы которой с_i,j представляют собой нормы затрат на перевозку единицы груза из пункта производства i в пункт потребления j. План перевозки груза в данной транспортной сети представляется в виде массива элементов размерности т п:

x = (x_1,1,…,x_1,n, x_2,1,…,x_2,n,…, x_i,1,…,x_i,n,…, xm,1,…, x_m,n) (12)

В (12) план перевозок х может рассматриваться как вектор, распадающийся на т групп, по п элементов в каждой, причем i-я группа соответствует объемам груза, вывозимым из i-го пункта производства во все возможные пункты потребления. Если реальная перевозка между пунктами i и / отсутствует, то полагают x_t ,_j = 0 .

Ограничения на возможные значения xR^mn имеют вид:

1 . Ограничение на удовлетворение потребностей во всех пунктах потребления:

(13)

2. Ограничения на возможности вывоза запасов из всех пунктов производства:

(15)

3. Условия неотрицательности компонентов вектора плана: х, Xfj >0, Ге1:т, /el: л . (15)

Существенной характеристикой описываемой модели является соотношение параметров а_; и Ь. . Если суммарный объем производства равен суммарному объему потребления, а именно,



то система называется сбалансированной. При выполнении условия сбалансированности разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т. е. условия (13) и (14) приобретают форму равенств.

По аналогии с задачей производственного планирования предположим, что затраты на перевозку прямо пропорциональны количеству перевозимого груза. Тогда суммарные затраты на перевозку в системе примут вид:

(16)

Функция (16) и описанные выше ограничения, записанные в форме

(17)

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