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

краткий курс

МАТЕМАТИЧЕСКИЕ МЕТОДЫИССЛЕДОВАНИЯ ОПЕРАЦИЙВ ЭКОНОМИКЕ

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

УЧЕБНОЕ ПОСОБИЕ

Санкт-Петербург

Москва • Харьков • Минск

2000

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

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

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

ББК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.

Подписано к печати15.09.99. Формат 60х90/16. Усл. п. л. 13.

Тираж 5000. Заказ 4418.

Отпечатано с фотоформ в АООТ «Типография „Правда”».

119. С.-Петербург, Социалистическая ул., 14.

ПРЕДИСЛОВИЕ

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х _A + х _B + х _C + х _D + х _E + х _F ≤ 100 000. (2)

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

х _A ≤ 25 000, x_B ≤ 25 000,x_C ≤ 25 000,

x_D ≤ 25 000,x_E ≤ 25 000,x_F ≤ 25 000. (3)

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

x_B + x_C ≥50 000. (4)

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

х _C + х _D ≤ 30 000. (5)

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

х _A ≥ 0, х _B ≥ 0, х_С ≥ 0, х _D ≥ 0, х _E ≥ 0, х _F ≥ 0. (6)

Выражения (1)-(6) образуют математическую модель поведения инвестора. В рамках этой модели может быть по­ставлена задача поиска таких значений переменных х _A , x_B , x_C , x_D , x_E , x_F , при которых достигается наибольшее значение при­были (т. е. функции (1)) и одновременно выполняются ограничения на структуру портфеля активов (2)-(6).

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

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

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

Если j -й продукт производится в количестве x_j , то в рамках описанных выше технологий мы должны потратить a _1,j x_j перво­го ресурса,a _2,j x_j — второго, и так далее, a_m,j x_j - m -го. Свод­ный план производства по всем продуктам может быть пред­ставлен в виде n -мерного вектора-строки х = (х ₁ , х ₂ ,...,х _j ,...,х _n ). Тогда общие затраты по i -му ресурсу на производство всех про­дуктов можно выразить в виде суммы

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

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

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

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

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

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

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

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

х = ( x _1,1 … x _1,n , x_2,1 ….,x_2,n ,… , x_i,1 , …, x_i,n ,…, x_m,1 ,…,x_m,n ). (12)

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

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

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

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

3. Условия неотрицательности компонентов вектора плана:

х, х _i,j ≥ 0,i Î l : m, j Î l : n. (15)

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

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

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

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

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

f(x)=cx → min, x Î D, (18)

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

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

Пусть на некотором множествеD определена функцияf(x). Напомним, что точка х* , принадлежащая D (х * Î D ), называет­ся точкой глобального максимума , если для любого xÎ D выполняется неравенствоf(x) ≤ f(x*). В этом случае значение f(x*) называется глобальным максимумом функции . Точ­ка х̀́ называется точкой локального максимума , если су­ществует некоторая окрестность этой точки, в любой точке ко­торой значение функции меньше, чем в х́̀ (f(x) ≤ f(x́̀)). По аналогии, с точностью до знака неравенства, определяются глобальный и локальный минимумы . Обобщающим понятием для максимума и минимума является таксой термин, как эк­стремум (оптимум).

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

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

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

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

ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1.1. Формы задачи линейного программирования.

В общем виде задача линейного программирования* (в дальней­шем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции

на некотором множествеD Ì Rⁿ , где х Î D удовлетворяют сис­теме ограничений

и, возможно, ограничениям

х ₁ ≥0,х ₂ ≥0,..., х _j ≥0,...,х _n ≥0. (1.3)

* Напомним, что частные примеры, сводящиеся к задаче линейного программирования, были описаны во введении.

Не умаляя общности, можно считать, что в системе (1.2) пер­вые m ограничений являются неравенствами, а последующие —l -уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направ­ления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противопо­ложный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме нера­венств, но в силу особой структуры их обычно выделяют от­дельно и называют условиями неотрицательности (или три­виальными ограничениями).

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

эквивалентна задаче поиска минимума функции

Часто условия задачи (1.1)-(1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращен­ной матричной форме

f(x) = сх → max, A_x ≤ b , х ≥ 0, (1.6)

где с их — векторы из пространстваRⁿ , b — вектор из простран­стваR^m , а А — матрица размерности m х n .

Задачу линейного программирования, записанную в форме (1.1)-(1.3), называют общей задачей линейного програм­мирования (ОЗЛП).

Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные х _j наложены усло­вия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матрич­ной форме КЗЛП можно записать в следующем виде:

Поскольку любая оптимизационная задача однозначно оп­ределяется целевой функцией f и областьюD , на которой отыс­кивается оптимум (максимум), будем обозначать эту задачу парой (D , f ).

Условимся относительно терминологии, которая использу­ется в дальнейшем и является общепринятой в теории линейно­го программирования.

Планом ЗЛП называется всякий вектор х из пространства Rⁿ .

Допустимым планом называется такой план ЗЛП, кото­рый удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов . Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию

max f(x) = f(x*).

Величина f * = f (х*) называется оптимальным значением целевой функции.

Решением задачи называется пара (х * , f* ), состоящая из oптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

1.1.2. Переход к канонической форме . Подавляющее боль­шинство известных методов решения задач линейного програм­мирования предназначены для канонических задач. Поэтому начальный этап решения всякой общей задачи линейного про­граммирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче.

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

- ограничения в виде неравенств преобразуются в уравне­ния за счет добавления фиктивных неотрицательных переменных х _i , (i Î 1:m) , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

- переменные, на которые не наложено условие неотрица­тельности, представляются в виде разности двух новых неотрицательных переменных:

- = - =

х _j = х_j – х _j , (x_j ≥ 0, х_j ≥ 0).

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

f(x) = 5х ₁ + 3x ₂ + x ₃ + 2х ₄ -2х ₅ → max

и множеством допустимых планов D , определенным системой уравнений и неравенств,

Тогда в соответствии со сформулированными правилами эк­вивалентная каноническая задача будет иметь вид (D',f' ), где:

а множество D' определено как:

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

1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

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

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

Частными случаями линейных пространств являются веще­ственная прямая, плоскость, геометрическое трехмерное про­странство.

Вектор λ₁ a ¹ + λ₂ a ² + …+ λ_m a ^m называется линейной комбина­цией векторов а ¹ а ² ,..., а ^m с коэффициентами λ₁ , λ_2, λ_m ,

Система векторов линейного пространства а ¹ а ² ,..., а ^m называется линейно зависимой , если существуют такие числа λ₁ , λ_2, λ_m не равные одновременно нулю, что их линейная комбинация λ₁ a¹ + λ₂ a² + …+ λ_m a^m равняется нулевому вектору (вектору, все компоненты которого равны нулю). В против­ном случае систему а ¹ ,а ² ,..., а ^m называют линейно независи­мой , т. е. линейная комбинация данных векторов может быть равна нулевому вектору только при нулевых коэффициентах λ₁ , λ_2, …, λ_m

Максимально возможное количество векторов, которые могут образовывать линейно независимую систему в данном линейном пространстве, называют размерностью простран­ства , а любую систему линейно независимых векторов в коли­честве, равном размерности, — базисом пространства .

Линейное пространство обычно обозначают какRⁿ , где n — его размерность.

Любое подмножество данного линейного пространства, ко­торое само обладает свойствами линейного пространства, назы­вается линейным подпространством. Множество Н , получае­мое сдвигом некоторого линейного подпространстваL Ì Rⁿ на векторa Î Rⁿ : H=L+a , называется аффинным множеством (пространством). Если фундаментальным свойством любого ли­нейного пространства или подпространства является принад­лежность ему нулевого вектора, то для аффинного множества это не всегда так. На плоскости примером подпространства явля­ется прямая, проходящая через начало координат, а аффинного множества — любая прямая на плоскости. Характеристическим свойством аффинного множества является принадлежность ему любой прямой, соединяющей две любые его точки. Размерность аффинного множества совпадает с размерностью того линейно­го подпространства, сдвигом которого оно получено.

Если рассматривается некоторое линейное пространствоRⁿ , то принадлежащие ему аффинные множества размерности 1 на­зываются прямыми, а размерности (n -1)—гиперплоско­стями . Так, обычная плоскость является гиперплоскостью для трехмерного геометрического пространства R³ , а прямая — ги­перплоскостью для плоскости R ² . Всякая гиперплоскость делит линейное пространство на два полупространства.

Множество V векторов (точек) линейного пространства R ⁿ называется выпуклым, если оно содержит отрезок прямой, соединяющей две его любые точки, или, другими словами, из того, чтоa Î V и b Î V , следует, что х = (1- λ) х а+ λ хb ÎV , где 0 ≤λ≤ 1.

Линейная комбинация

векторов а ¹ ,а ² ... а ^m называется выпуклой , если λ_i ≥0, iÎ1:m и

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

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

Точкаv выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V . Угловые точки выпуклого многогранника являются его верши­нами, а сам он — выпуклой оболочкой своих вершин.

Множество К называется конусом с вершиной в точкеx₀ , еслиx ₀ ÎК , и из того, что некоторая точка х принадлежит К ( х Î К ), следует, что в К содержится и луч, начинающийсяв х₀ и проходящий через х , т. е.

или

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

1.2.2. Первая геометрическая интерпретация ЗЛП и графический метод решения . Рассмотрим следующий пример. Пусть дана задача максимизации линейной целевой функции

f(x) = 3х ₁ + х ₂ → max

на множестве

Так как количество переменных в неравенствах, задающих область допустимых планов задачи, равно двум, то ее можно изобразить на координатной плоскости (см. рис. 1.1 ).

На рис. 1.1 показано, что каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каж­дого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x) = 3х ₁ + х ₂ в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

Напомним, что линией уровня функции называется множе­ство точек из ее области определения, в которых функция при­нимает одно и то же фиксированное значение. Градиентом функцииf(x) называется вектор

Δf(x) = df ,…, df

dx ₁ dx_n

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

Для линейной функции двух переменных линия уровня пред­ставляет собой прямую, перпендикулярную вектору с , который служит градиентом данной функции. Следовательно, если ли­ния уровня определяется уравнениемf(x)=c₁ x₁ + c₂ x₂ =const , то этот вектоp имеет вид

и указывает направление возрастания функции.

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

На рис. 1.1 изображен некоторый частный случай, для кото­рого решение ЗЛП достигается в угловой точке х* = (0, 6) обла­сти D . Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.

Рисунок (а ) иллюстрирует ситуацию неограниченности це­левой функцииf(x)=cx на множестве D , т.е. сколько бы мы ни перемещались по линиям уровня в направлении вектора с , ее значение будет возрастать.

В случае, изображенном на рисунке (b ), линия уровня, со­ответствующая максимальному значениюf(x), касается грани множестваD , и, соответственно, все точки, лежащие на этой гра­ни, являются оптимальными планами.

Во всех рассмотренных иллюстрациях допустимые планы ЗЛП представлялись в виде некоторого многогранного выпук­лого множества на плоскости. Такое их представление в лите­ратуре получило название первой геометрической интерпре­тации задачи линейного программирования .

Заметим также, что аналогичным образом могут быть пост­роены интерпретации ЗЛП для случая трехмерного простран­стваR ³ , где множеству D будет соответствовать некоторый ограниченный или неограниченный многогранник, а поведе­ние целевой функции будет характеризоваться поверхностями (плоскостями) уровня.

Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается полезным. В частности, он может быть применен не только к задачам с двумя перемен­ными и ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых n - m = 2, где n — количество пе­ременных, а m — ранг матрицы А .

Действительно, можно выбрать две произвольные перемен­ные х _j1 ,x_j2 и, используя систему уравнений, выразить через них остальные переменные

где φ_j (x_{j 1} , x_{j 2} ) —линейные функции.

Подставив выражения (1.9) в целевую функцию, мы получим эквивалентную задачу

при ограничениях

Последняя ЗЛП может быть решена графически.

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

Теорема 1.1 . Если целевая функция f принимает мак­симальное значение в некоторой точке множества до­пустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.

Доказательство.

Чтобы не усложнять изложение, ограничимся тем случаем, когда множество D ограничено, и, следовательно, является вы­пуклым многогранником.

Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых множеств:

* Строгое доказательство данного утверждения см., например, в [14].

Пусть х ¹ , х ² ,…,х ^m — угловые точки множестваD , а х* — точка, в которой целевая функция f достигает максимума.

На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой комбинации угловых то­чек х ¹ , х ² ,..., x^m

Так как х* — точка максимума, то для любого х Î D сх * ≥ сх . Функцияf(x) — линейная, поэтому

cледовательно,

где x^r — угловая точка, удовлетворяющая условию

Из (1.10) видно, что сх* ≤ сх ^r .В то же время справедливо об­ратное неравенство: сх* ≥ сх ^r . Откуда следует, что сх* = сх ^r , т. е. существует по крайней мере одна угловая точках ^r , в которой целевая функция принимает максимальное значение. -

Доказательство.

Пусть максимальное значение функции f достигается в точ­ках х̃ ¹ , х̃ ² ,...,x̃^s , т. е. сх ^~i =f*, i Î l:s. Рассмотрим произвольную выпуклую комбинацию этих точек

Найдем значение целевой функции в точке х*

Итак, для произвольной выпуклой комбинации х* точек х̃¹ , х̃ ² ,...,x^~s справедливо равенство

1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП

1.3.1. Векторная форма записи КЗЛП и ее примене­ние . Рассмотрим каноническую задачу линейного программи­рования

Обозначим через а ^j столбцы матрицы А и будем рассматри­вать их как векторы пространстваR^m . Тогда каждому допусти­мому плану КЗЛП — n -мерному вектору х — соответствует неотрицательная линейная комбинация столбцов а ^j , равная столбцуb Î R^m :

Такое представление ограничений КЗЛП обычно называют векторной формой записи.

Векторы а ^j , j Î l:n будем называть векторами требований задачи (D, f ), а вектор b — вектором ограничений . Множе­ство всех неотрицательных линейных комбинаций столбцов а^j с геометрической точки зрения может быть представлено как многогранный выпуклый конус, натянутый на систему векто­ров а ^j в пространстве R ^m (рис. 1.3).

Соответственно, вопрос о существовании допустимого пла­на задачи (D, f ) равнозначен вопросу о принадлежности векто­ра b данному конусу, а компоненты х _j некоторого допустимогоплана х Î D являются не чем иным, как коэффициентами раз­ложения вектора ограничений задачи b по векторам, требо­ваний а ^j .

Такое представление КЗЛП получило название второй гео­метрической интерпретации.

В дальнейшем без ограничения общности можем предпола­гать, что число уравнений, задающих множествоD , меньше или равно числу переменных задачи (m ≤ n ). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, зна­чит, множество D пустое), либо содержит избыточные (линейно зависимые) уравнения.

Если некоторые т столбцов а ^{j 1} ,а ^{j 2} ,...,а ^jm матрицы A явля­ются линейно независимыми, то они образуют базис в простран­стве R^m , и их, вообще говоря, будет достаточно для представ­ления вектора b в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации окажутся неотрицатель­ными, то мы получаем так называемый базисный допустимый план х , у которого не более m компонентов отличны от нуля. Сформулируем определение базисного плана более строго, так как это одно из фундаментальных понятий теории линейного пpогpаммиpования.

-Пусть задана некоторая каноническая ЗЛП (D,f), А —матрица системы ограничений задачи, и β= {а ^{j 1} , аj2,..., а^{j m} } —линейно независимая система столбцов матрицы А, образующая базис R^m . Обозначим множе­ство номеров столбцов, входящих в систему b , через N ( β ) = { j ₁ , j₂ ,..., j_m }. План х называется базисным планом задачи (D,f), если его компоненты, соответствующие базисным столбцам и называемые базисными компонен­тами, больше или равны нулю (х_j ≥ 0, j Î N ( β )}, а все остальные компоненты (небазисные) — равны нулю ( x_j = 0, j Ï N ( β)).

-Базисный план х называется невырожденным, если все его базисные компоненты строго

положительны, и вы­рожденным в противном случае.

1.3.2. Свойства базисных планов . Следующая теорема трактует понятие базисного плана в терминах первой геометри­ческой интерпретации ЗЛП.

Доказательство.

Ради простоты положим, что базисными векторами являют­ся первые m столбцов матрицы A , т. е. β={a ^l ,a ² ,...,a^m }. Тогда утверждение теоремы 1.3 может быть переформулировано сле­дующим образом:

Если существует такой n -мерный вектор

что x ₁ a ¹ +х ₂ а ² +...+x _k a^k =b , то х есть угловая точка множе­ства D.

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

x = λx ¹ +(1-λ)x ² , 0<λ<1.

В координатной форме последнее утверждение означает

Поскольку последние (n - k ) компоненты вектора х по пред­положению равны 0, а числа х _j ¹ ,x_j ² ≥ 0 и λ, (1 -λ )>0, то эти же компоненты в векторах x ₁ и х ₂ также равны 0. Поэтому, с учетом допустимости планов х ¹ и х ² , можно утверждать, что

Вычитая из (1.15) (1.16), получим

Так как векторы а ¹ ,а ² ,...,а ^k — линейно независимы, то коэф­фициенты х ¹ ₁ –х ² ₁ =0,..., х ¹ _k –х ² _k =0, из чего следует, что x ¹ =х ² . Это противоречит предположению, что х ¹ и х ² являются раз­личными угловыми точками множестваD . Следовательно, х не может быть представлен в виде выпуклой комбинации двух точек D и по определению является угловой точкой данного множества. -

Интересно отметить, что справедливо и обратное утвержде­ние, которое приведем без доказательства:

Если х — угловая точка множества D, то она являет­ся допустимым базисным планом задачи (D, f).

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

1.4. СИМПЛЕКС-МЕТОД

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

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

Идея такого перехода от одного базисного плана к другому, при котором происходит «улучшение» значения целевой функ­ции, может быть продемонстрирована для случая m = 2 с помо­щью рис. 1.4. Если вектор ограничений b принадлежит конусу, натянутому на некоторые два базисных вектора условий {а^{j 1} ,а^{j 2} }, то существует такой базисный план х с базисными компонентами х _j1 , х _j2 , чтоb= х _j1 a^j1 + х _j2 a^j2 . Разумеется, таких планов может быть несколько в зависимости от выбора систе­мы базисных векторов. Чтобы различать их по соответствую­щей величине целевой функцииf(x)=c_{j 1} x_{j 1} +с _{j 2} х _{j 2} , вводятся так называемые расширенные векторы условий и ограничений . В общем случае расширенный столбец условийā^j получается соединением коэффициента целевой функции с ^j и столбца а ^j :

расширенный вектор ограничений определим как

В дальнейшем для удобства нумерации элементов будем счи­тать, что добавляемый коэффициент целевой функции с _j явля­ется нулевым элементом j -го расширенного столбца условий, т. е.ā_0,j = с _j . При изображении расширенных векторов нулевая координата откладывается вдоль вертикальной оси — оси апп­ликат.

Рассмотрим также вектор

=

Геометрически определение вектора b означает, что он при­надлежит конусу, натянутому на расширенные векторы, а век­тор служит его проекцией. Нулевая координата вектора b имеет вид:

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

Из геометрической иллюстрации следует, что для решения задачи мы должны среди векторов а ^j выбрать такой набор {а ^{j 1} ,а ^{j 2} }, чтобы, прямая, проведенная через конец вектора параллельно оси аппликат, пересекала конус, натянутый на систему соответствующих расширенных столбцов { ā^{j 1} , ā^{j 2} }, в «наивысшей» точке.

На рис. 1.4 выделен конус, натянутый на систему расширен­ных столбцов ā ² и ā ³ , отвечающих текущему допустимому ба­зису. Нетрудно заметить, что данный базис не является опти­мальным, например, для базиса {а³ , а⁴ } точка пересечения соответствующего конуса и прямой будет находиться выше. Можно, наоборот, указать базис с «худшим» значением целе­вой функции: {а ¹ а² }. Наконец, рассматриваемая геометричес­кая интерпретация КЗЛП иллюстрирует и общую идею крите­рия, который используется в симплекс-методе для определения оптимальности (или неоптимальности) текущего плана: если существуют векторы-столбцы, лежащие выше плоскости, проходящей через векторы текущего базиса, то он не явля­ется оптимальным и может быть «улучшен».

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

Для удобства дальнейшего изложения введем некоторые обозначения. Учитывая то, что симплекс-метод представляет собой некоторый итеративный вычислительный процесс, то че­резq будем обозначать номер очередной (текущей) итерации. Соответственно, набор базисных столбцов, получаемых на q -й итерации, будет обозначаться как β ^{( q )} :

Для того чтобы было легче отличить номер итерации от номе­ров компонентов матриц и векторов, он заключен в круглые скобки. Номера столбцов, входящих в базис, обозначим через N (β^(q) ), а именно

При этом N_r (β^(q) ) =j_r — номер столбца, занимающего r -ю пози­цию в базисе. Тогда текущий базисный план х имеет вид:

Обозначим через Δ(ß^(q) ) матрицу, составленную из столбцов {а^{j 1} , а^{j 2} ,..., а^jm }, образующих базис, через Δ(ß^(q) ) матрицу, об­разованную из соответствующих расширенных столбцов и до­полненную слева столбцом специального вида:

а через ∆^-1 (β^(q) ) и ∆^-1 (β^(q) ) — матрицы, обратные по отношению к ним. Также представляется удобным ввести отдельные обо­значения для элементов матрицы ∆^-1 (β^(q) ):

δ_i (β^(q) ) — i -я строка матрицы ∆ˉ^-1 (β^(q) ), (i Î 0: m );

δ_ij (β^(q) ) — элемент матрицы ∆^-1 (β^(q) ), находящийся в i -й строке j -го столбца (i Î 0: m , j Î 0 : m ).

Расширенный вектор ограничений b представляется в виде линейной комбинации расширенных векторов условий с коэф­фициентами, равными базисным компонентам текущего базис­ного плана:

Если интерпретировать компоненты векторов а^j и b как ко­ординаты в ортогональном базисе, то их столбцы координат от­носительно произвольного базиса (β^(q) ), дополненного единич­ным вектором (-1,0,..., 0), направленным противоположно оси аппликат примут вид:

а для расширенной матрицы задачи в целом можно записать

Нулевая строка данной матрицы a ₀ (β^{(q )} ) содержит координаты расширенных векторов условий по оси аппликат. Согласно по­строению, элементы данной строки имеют следующие знаки:

- a _0,j (β^{(q )} ) < 0 — для расширенных векторов условий, рас­положенных выше плоскости, натянутой на систему расширенных базисных векторов;

- a _0,j (β^{(q )} )> 0 — для расширенных векторов условий, рас­положенных ниже плоскости, натянутой на систему расширенных базисных векторов;

- a _0,j (β^{( q )} ) = 0 — для расширенных базисных векторов.

Подводя итог сказанному, сформулируем критерий опти­мальности допустимого базисного плана в симплекс-методе:

-план является оптимальным, если для всех j Î1:n a _0,j (β^{(q )} ) ≥ 0, и неоптимальным в противном

случае, т. е. если существует такое l Îl : n , что a _0l (β^{(q )} ) < 0.

Значения a _0,j (β^{(q )} )также называют оценками столбцов мат­рицы А относительно текущего базиса, или симплекс-разнос­тями.

В случае неоптимальности текущего базиса в алгоритме сим­плекс-метода осуществляется переход к следующему базису. Это делается за счет вывода одного столбца из базиса и ввода другого. Для обеспечения улучшения значения целевой фун­кции в базис должен быть введен вектор-столбец, имеющий от­рицательную оценку. Если таких столбцов несколько, то для ввода рекомендуется выбирать столбец , имеющий макси­мальную по модулю оценку . Отметим, что данное правило но­сит относительный характер и не гарантирует наилучшего выбора вводимого столбца. Одновременно на этой стадии тре­буется принять решение о том, какой столбец следует вывести из базиса. Сделать это нужно таким образом, чтобы вновь формируемый базис оказался допустимым. Данное требование может быть легко проиллюстрировано для случая m = 2. Например, на рис. 1.3 векторы {а ² ,а ³ } образуют допустимый ба­зис, а векторы {а ³ ,a ⁴ } —недопустимый, т. к. разложение b по а ³ и а ⁴ содержит один отрицательный компонент плана, что противоречит условиям КЗЛП.

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

-для столбца l , претендующего на ввод в базис, и вектора ограничений b рассматриваются

отношения

и определяется такая строка r , что

Полученный индекс r определяет номер столбца в N (β^{(q )} ), выводимого из базиса, а именно , N (β^{(q )} ).

Таким образом, если базис на q -й итерации включал столбцы с номерами

то базис на итерацииq + 1 будет состоять из столбцов с номе­рами:

Отдельно следует обсудить тот случай, когда столбец a_l (β^{(q )} ), претендующий на ввод в базис, не содержит положительных компонентовa_l (β^{(q )} ) ≤ 0). Это означает, что целевая функция в задаче не ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения. Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального плана. Геометрически ситуация, когда a^l (β^{(q )} ) ≤ 0, соответствует тому, что ось ординат оказыва­ется внутри конуса, натянутого на систему расширенных стол­бцов а ^j , а значит, прямая, проведенная через конец вектора b параллельно оси аппликат, однажды «войдя» в этот конус, более никогда из него «не выходит».

Вообще говоря, после перехода от базиса β^{(q )} к базису β^{(q +1)} мы можем заново сформировать матрицы ∆ (β^{(q+ 1)} ), Δ^-1 (β^{(q +1)} ) и, вычислив А (β^{(q +1)} ) = Δ^-1 (β^{(q +1)} )A , делать выводы о его оптималь­ности. Однако, учитывая, что β^{(q +1)} отличается от β^{(q )} всего лишь одним столбцом, с точки зрения техники вычислений представляется рациональным непосредственно переходить от A (β^{(q )} ) иb (β^{(q )} ) к A (β^{(q +1)} ) иb (β^{(q +1)} ) . Дело в том, что у матриц типа A (β^{(q )} ) столбцы, соответствующие базисным векторам, состоят из нулей, за исключением одного элемента, равного единице. Позиция этого ненулевого элемента определяется по­рядковым номером базисного столбца в N (β^{(q )} ). Поэтому для получения матрицы A (β^{(q +1)} ) достаточно с помощью линейных операций над строками матрицы A (β^{(q )} ) привести ее столбец, соответствующий вводимому в базис вектору, к «базисному» виду.

Для это применяется преобразование Жордана—Гаусса (так называемый метод полного исключения). В данном случае оно состоит в том, что мы должны «заработать» единицу на мес­те элемента a_r,l (β^{(q )} ) (он обычно называется ведущим )* и нули на месте остальных элементов столбца a^l (β^{(q )} ). Первое достига­ется посредством деления r -й строки на ведущий элемент, вто­рое — путем прибавления вновь полученной r -й строки, умно­женной на подходящий коэффициент, к остальным строкам матрицы A (β^{(q )} ).

* Напомним, что l — номер столбца, вводимого в базис, а r — номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.

Формально результат выполнения данного преобразования над элементами A (β^{(q )} ) и b (β^{(q )} ) может быть выражен в следующем виде

Следует особо отметить смысл элементов вектора b (β^{(q )} ). Его нулевой компонент b ₀ (β^{(q )} ) в соответствии с построением содержит значение целевой функции , достигаемое ею на теку­щем плане

а остальные элементы — ненулевые компоненты этого плана:

Название метода произошло от понятия симплекса. Напом­ним, что m -симплексом называют выпуклый многогранник, аффинная оболочка* которого есть аффинное множество размерности m . В данном случае можно считать, что система рас­ширенных базисных столбцов {а ^{j 1} ,а ^{j 2} ,..., а ^jm }, рассматривае­мых как точки в R^{m +1} , порождает (m -1)-мерный симплекс в пространствеR^{m +1} .

*Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное множество.

В заключение настоящего пункта обобщим изложенные во­просы и приведем схему алгоритма симплекс-метода для решения задачи максимизации. Она включает однократно выполняемый 0-этап и повторяемый конечное число раз I-этап (стандартную итерацию).

0-этап. Нахождение допустимого базисного плана

содержание   ..  615  616  617   ..