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

краткий курс

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

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

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

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

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

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-этап. Нахождение допустимого базисного плана (см. п. 1.4.5). Результатом 0-этапа является допустимый базис­ный план х (β⁽¹⁾ ), а также соответствующие ему матрица A (β⁽¹⁾ ) и вектор b (β⁽¹⁾ ), которые будут использованы на первой итера­ции. Полагаем номер текущей итерацииq равным 1 и переходим к I-этапу.

I -этап. Стандартная итерация алгоритма — выполня­ется для очередного базисного плана x (β^{(q )} ).

1°. Проверка оптимальности текущего базисного плана:осуществляется просмотр строки оценок а ₀ (β^{(q )} ). Возможны два варианта:

1′. a ₀ (β^{(q )} )≥0 — план, соответствующий текущему базису за­дачи, оптимален . Вычислительный процесс закончен. Соглас­но формулам (1.33) и (1.32) выписываются оптимальный план задачи х ^* = x (β^{(q )} ) и значение целевой функции f (x ^* )=f (x (β^{(q )} )).

1″. В строке оценок а ₀ (β^{(q )} ) существует по меньшей мере один элемент а _0,j (β^{(q )} )<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x (β^{(q )} ) —неоптимален. Выбирается столбец с номером l , имеющий минимальную (максимальную по абсолютной величине) отрицательную оценку

Он называется ведущим и должен быть введен в очередной базис . Переходим к пункту 2° алгоритма.

2°. Определение столбца, выводимого из базиса . Рассмат­ривается ведущий столбеца ^l (β^{(q )} ) Возможны два варианта:

2'. Для всех i Î1:m а _i,l (β^{(q )} )≤0. Делается вывод о неогра­ниченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере одна строка с номером i Î1:m , для которой а _i,l (β^{(q )} )>0 . Согласно правилу (1.27) опре­деляются место r и номер N _r (β^{(q )} )=j_r для столбца, выводимого из базиса. Переходим к пункту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относи­тельно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи А и век­тора ограничений b относительно базиса β^{(q+ 1)} , который полу­чается после введения в базис β^{(q )} столбца а ^l и выводом из него столбца а ^r . Полагаем номер текущей итерацииq : = q +l и пере­ходим к первому пункту алгоритма.

Рис.1.5

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

* Настоящая структура симплекс-таблиц строится на идеях и прин­ципах их организации, предложенных в [1].

Симплекс-таблица Т^{(q )} , изображенная на рис. 1.5 , соответ­ствует допустимому базису КЗЛП β^{(q )} ), получаемому наq -й ите­рации. Столбец N (β^{(q )} ) содержит номера базисных столбцов (в той последовательности, в которой они входят в базис), стол­бец b (β^{(q )} ) —компоненты вектора ограничений относительно текущего базиса β^{(q )} ,A (β^{(q )} ) — компоненты матрицы задачи относительно текущего базиса β^{(q )} . Наконец, в строке а ₀ (β^{(q )} ) находятся текущие оценки столбцов, а ячейка b ₀ (β^{(q )} ) содержит значение целевой функции, достигаемое для текущего плана.

Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное практическое значение нестолько как удобная форма организации ручного счета, сколь­ко как основа для реализации данного алгоритма в рамках про­граммного обеспечения ЭВМ.

1.4.3. Пример решения ЗЛП симплекс-методом . Рас­смотрим на конкретном примере процесс решения КЗЛП таблич­ным симплекс-методом. Пусть дана каноническая задача ЛП:

Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по дан­ным столбцам вектора ограничений с положительными коэф­фициентами. Последнее означает, что столбцы {5, 2, 3} образу­ют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых эле­ментов формируется матрица Δ(β⁽¹⁾ ) и обратная по отношению кнейΔ^-1 (β⁽¹⁾ ):

Используя их, по формуле (1.26) получаем

Используя полученные значения A (β⁽¹⁾ ) и b (β⁽¹⁾ ), заполняем симплекс-таблицу T ⁽¹⁾ , соответствующую первой итерации (q =1).

Поскольку строка оценок a ₀ (β⁽¹⁾ ) в первом и четвертом столбцах содержит отрицательные элементы (a _0,1 (β⁽¹⁾ ) = -84, a _0,4 (β⁽¹⁾ ) = -88), план х (β⁽¹⁾ ) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f (x (β⁽¹⁾ )) = -226 может быть улучшено. Следуя рекомендации п.1˝ алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l = 4 (т.к. |-88| > |-84|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)

Он содержит два положительных элемента. Применяя рекомен­дацию п. 2" алгоритма, получаем λ₁ = 4/(1/3) =12, λ₂ =14/3,и, стало быть r = 2. Следовательно, столбец с номером N ₂ (β⁽¹⁾ ) = 2 должен быть выведен из базиса. Таким образом, по­лучаем очередной допустимый базис задачи N (β⁽²⁾ ) = {5, 4, 3}. Элемент a _2,3 (β⁽¹⁾ ) является ведущим (обведен кружком). При­менив формулы (1.28)-(1.31), переходим к симплекс-таблице, соответствующей второй итерации T ⁽²⁾ , и полагаем индекс те­кущей итерацииq = 2.

В ходе выполнения второй итерации опять-таки определяют­ся вводимый столбец а ¹ , выводимый а ⁴ и ведущий элемент a _2,1 (β⁽²⁾ ). Перейдя к итерации q = 3, имеем таблицу T ⁽³⁾ .

Как видно из T ⁽³⁾ , строка оценок содержит только неотрицатель­ные значения, поэтому достигнутый базис N (β⁽³⁾ ) = {5, 1, 3} яв­ляется оптимальным. В итоге мы получаем, что вектор х ^* =(7, 0, 31/3, 0, 5/3) является оптимальным планом (точ­кой максимума) задачи (1.34)-(1.35), максимальное значение целевой функции равно f * =f (х *)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362).

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

Легко заметить, что проблемы со сходимостью симплекс-ме­тода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения от­ношения

будут достигнуты для нескольких строк таблицы Т^{(q )} одновре­менно. Тогда на следующей итерации столбец b (β^{(q +1)} ) будет со­держать нулевые элементы. Напомним, что

-допустимый базисный план канонической задачи ЛП, со­ответствующий базису β^{(q )} , называется вырожденным , если некоторые его базисные компоненты равны нулю, т. е. вектор b (β^{(q )} ) содержит нулевые элементы.

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

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

С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро кону­са, натянутого на систему расширенных векторов текущего базиса. Так, в случае, изображенном на рис. 1.6 , эта линия по­падает в ребро, определяемое вектором а ^{j 2} , т. е., несмотря на то что текущий базис содержит столбцы а ^{j 1} и а ^{j 2} , для представле­ния вектора b достаточно только одного а ^{j 2} .

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

Необходимо, однако, сказать, что рассмотренная здесь про­блема зацикливания для большинства практически значимых задач является достаточно редкой и маловероятной. Более того, она очень часто разрешается за счет ошибок округлений при выполнении расчетов на ЭВМ.

1.4.5. Нахождение допустимого базисного плана . В рас­смотренном выше примере исходный базисный план, необходи­мый для начала вычислений по симплекс-методу, был подобран за счет особенностей матрицы условий. Действительно, данная матрица уже содержала необходимое количество «почти базис­ных» столбцов. Очевидно, что для подавляющего большинства задач ЛП невозможно подобным образом сразу и в явном виде указать исходный допустимый базисный план. Вообще говоря, существуют различные приемы решения данной задачи. Мы остановимся на одном из них, получившем название метода минимизации невязок . Его сильной стороной, безусловно, яв­ляется универсальность. Xотя, в некоторых частных случаях, он может оказаться слишком громоздким.

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

Не умаляя общности, можно считать, что вектор ограниче­ний в исходной задаче неотрицателен, т. е. bⁱ ≥ 0,i Î 1: m . Тогда для КЗЛП максимизации функции

на множестве, определяемом ограничениями

строится вспомогательная задача

Как видно из (1.36)-(1.39), задача (, ) отличается от за­дачи (D, f ) матрицей, получаемой в результате добавления кисходной матрице А единичной матрицы, которой соответ­ствуют дополнительные (фиктивные) переменные х _{n +1} ,...,х _n+m . Данным переменным (собственно говоря, их и называют не­вязками ) в целевой функции отвечают коэффициенты (-1), а переменным х ₁ ,...,х _n , которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенно­стью (, ) является наличие в ней очевидного исходного ба­зиса, образуемого добавленными столбцами, и соответствую­щего плана с базисными компонентами х_n+i = b_i ≥ 0, i Î 1: m . В силу структуры целевой функции f̃ в процесс поиска ее мак­симума процедурой симплекс-метода фиктивные переменные (невязки) х_n+i должны минимизироваться желательно до нуля, что может быть достигнуто за счет последовательного перевода их в небазисные компоненты плана. Если в оптималь­ном плане х̃ , полученном в результате решения вспомогатель­ной задачи, последние m компонент (т. е. невязки) равны нулю, то его начальные n компонент удовлетворяют системе ограни­чений, определяющих область D , и легко (простым отбра­сыванием невязок) может быть преобразован в стартовый до­пустимый план основной задачи (D, f ). При этом все строки симплекс-таблицы, полученной на последней итерации вспо­могательной задачи (за исключением нулевой), могут быть перенесены в первую таблицу основной задачи. Элементы же нулевой строки для вновь формируемой симплекс-таблицы вы­числяются по формулам:

где β^(*) — базис, полученный на последней итерации вспомога­тельной задачи.

В случае, когда оптимальный план вспомогательной задачи х̃ все же содержит не равные нулю фиктивные компоненты (т. е. ( )<0), мы приходим к заключению об отсутствии до­пустимых планов у исходной задачи (D, f ), т. е.D = Ø.

1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

1.5.1. Вычислительная схема, основанная на преобра­зовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, не­трудно заметить, что наиболее критичным в этом плане являет­ся этап пересчета значений А и b при переходе от одного базис­ного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n , можно добиться существенной «экономии», вы­полняя на очередной итерацииq преобразование Жордана—Га­уссане над матрицей А (β^{(q )} ), а над матрицей Δ^-1 (β^{(q )} ). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно получить А (β^{(q )} )по Δ^-1 (β^{(q )} ). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А (β^{(q )} )целиком. Реаль­но в ней использовались только строка оценок a ₀ (β^{(q )} ) и ведущий столбецa^l (β^{(q )} ). Данные соображения положены в основу вы­числительной схемы симплекс-метода, основанной на преобра­зовании обратных матриц, которую также называют модифици­рованным симплекс-методом . Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.

Вычислительной схеме модифицированного симплекс-мето­да соответствует система таблиц T ₁ и Т ₂ ^{(q )} . Таблица T ₁ (рис. 1.7 ) является общей для всех итераций и служит для получениястроки оценок текущего базисного плана a ₀ (β^{(q )} ). Если обозна­чить через δ_i (β^{(q )} ) (i Î 0 : m ) строки матрицы Δ^-1 (β^{(q )} ), то из (1.26), в частности, следует, что

Как видно из рис. 1.7 , T ₁ состоит из трех блоков:

- в центре содержится матрица А ;

- в левом блоке таблицы на каждой итерации дописывают­ся нулевые строки матрицы Δ^-1 (β^{(q )} )для текущего ба­зиса ;

- нижний блок, расположенный под матрицей А , на каж­дой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).

Симплекс-таблица Т ₂ ^{(q )} , изображенная на рис. 1.8 , соответ­ствует допустимому базису КЗЛП β^{(q )} , получаемому наq -й ите­рации. Столбец N (β^{(q )} ) содержит номера базисных столбцов (в последовательности вхождения в базис); столбец b (β^{(q )} ) — компоненты вектора ограничений относительно текущего ба­зиса β^{(q )} ; Δ^-1 (β^{(q )} ) — матрица, обратная по отношению к матри­це расширенных столбцов текущего базиса β^{(q )} ; графа а ^l со­держит расширенный вектор условий, вводимый в базис на текущей итерации, а следующая графа — координаты а ^l (β^{(q )} )этого же столбца в текущем базисе β^{(q )} .

По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.

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

1. Для поиска допустимого базиса может быть применен ме­тод минимизации невязок, рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедурамодифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план x (β⁽¹⁾ ) и соответствую­щие ему матрицу Δ^-1 (β⁽¹⁾ )и вектор b (β⁽¹⁾ ).

2. Заполняем центральную часть таблицы T ₁ , содержащую матрицу А .

3. Содержимое матрицы Δ^-1 (β⁽¹⁾ )и вектора b (β⁽¹⁾ ), получен­ных на этапе поиска допустимого базисного плана, переносит­ся в таблицу T ₂ ⁽¹⁾ .

4. Полагаем номер текущей итерацииq равным 1 и перехо­дим к I-этапу.

1-этап. Стандартная итерация алгоритма — выполня­ется для очередного базисного плана x (β^{(q )} ).

1°. Проверка оптимальности текущего базисного плана . Содержимое нулевой строки таблицы T ₂ ^{(q )} — δ₀ (β^{(q )} ) переписы­вается в соответствующую графу таблицы T ₁ . По формуле (1.42) рассчитываем и заполняем строку a ₀ (β^{(q )} ). Осуществля­ем просмотр строки оценок a ₀ (β^{(q )} ). Возможны два варианта:

1΄. a ₀ (β^{(q )} )≥0 —план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Со­гласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х * =x (β^{(q )} ) и оптимальное значение целевой функ­цииf (х *)=f (x (β^{(q )} )).

1". В строке оценок a ₀ (β^{(q )} )существует по меньшей мере один элемент a _0,j (β^{(q )} )<0, т. е. имеющий отрицательную оцен­ку. Следовательно, план x (β^{(q )} ) —неоптимален . Выбирает­ся номер l , соответствующий элементу, имеющему минималь­ную (максимальную по абсолютной величине) отрицательную оценку:

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

2°. Определение столбца, выводимого из базиса . Перепи­сываем ведущий столбец а ^l из таблицы T ₁ в текущую таблицу Т ₂ ^{(q )} . По формуле а ^l (β^{(q )} ) = Δ^-1 (β^{(q )} )а ^l заполняем соответствую­щий столбец в таблицеТ ₂ ^{(q )} . Возможны два варианта:

2'. Для всехi Î 1: m а _i,l (β^{(q )} )≤0. Делается вывод о неограни­ченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере один индексi Î 1: m , для ко­торого а _i,l (β^{(q )} )>0. Согласно правилу (1.27) определяются мес­то r и номерN_r (β^{(q )} ) для столбца, выводимого из базиса. Пере­ходим к пункту 3° алгоритма.

3°. Пересчет относительно нового базиса элементов столбца b и матрицы Δ^-1 . Переход к новому базисуβ^{(q +1)} , кото­рый получается введением в базис β^{(q )} столбца а ^l и выводом из него столбца а ^r , осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:

Полагаем номер текущей итерацииq : =q +l и переходим к первому пункту алгоритма.

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

1.5.2. Пример решения ЗЛП модифицированным сим­плекс-методом. Приведем решение рассмотренной ранее за­дачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3оно начинается с выбора очевидного исходного базиса, обра­зуемого столбцами {5,2,3}. Для него уже были вычислены Δ^-1 (β^{(q )} ) и b (β^{(q )} ), поэтому заполнение начальных таблиц T ₁ и Т ₂ ⁽¹⁾ не представляет труда.

На первой итерации мы переписываем нулевую строку

из Т ₂ ⁽¹⁾ вT ₁ и, умножив ее на матрицу A , получаем строку оце­нок

Так какa ₀ (β⁽¹⁾ ) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β⁽¹⁾ , и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l =4.

Переписываем столбец

из таблицы T ₁ в Т ₂ ⁽¹⁾ и пересчитываем его координаты относи­тельно текущего базиса, т. е. умножаем матрицу Δ^-1 (β^{(q )} ), рас­положенную в таблице Т ₂ ⁽¹⁾ слева, на а ⁴ .

После заполнения таблицы Т ₂ ⁽¹⁾ данными по вводимому в но­вый базис столбцу можно перейти к определению номера выво­димого столбца. Эта процедура осуществляется в полной ана­логии с обычным симплекс-методом. Рассмотрев отношения элементов b_i (β⁽¹⁾ ) и a_i,l (β⁽¹⁾ ) для {i Î1:m| a_i,l (β⁽¹⁾ )>0} и определив минимальное из них, находим, что r =2. Следовательно, стол­бец с номером N ₂ (β^{(q )} ) =2 должен быть выведен из базиса. Та­ким образом, получаем очередной допустимый базис задачи с N (β⁽²⁾ ) ={5, 4, 3}. Элементa _2,3 (β⁽¹⁾ ) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к сим­плекс-таблице, соответствующей второй итерации Т ₂ ⁽²⁾ , и пола­гаем индекс текущей итерацииq = 2.

Повторяя те же самые действия (их легко проследить по при­водимым здесь таблицам Т ₂ ⁽²⁾ и Т ₂ ⁽³⁾ , на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т ₂ ⁽³⁾ . Легко заметить, что в процессе решения мы «про­шли» по той же самой последовательности допустимых базис­ных планов, которая встречалась в п. 1.4.3.

1.6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

1.6.1. Понятие двойственной задачи ЛП . Пусть задана КЗЛП (1.7). Если целевая функцияf (x ) = cx достигает макси­мального значения на множествеD , то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m -мерный вектор, то

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с . Тогда при любых х ≥ 0 справедливо неравенство

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

-Если задана каноническая задача ЛП

то задача ЛП

называется двойственной по отношению к ней. Соот­ветственно, задача (D, f ) no отношению к

(D*,f *)назы­вается прямой (или исходной).

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

-Если задана общая задача ЛП

f (x ) = c ₁ x ₁ + ... +с _j х _j + с _{j +1} х _{j+ 1} + ... +с _n x_{n →} max,x ÎD, (1.50)

где D определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется об­щая задача ЛП

где D * определяется системой уравнений и неравенств:

Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. макси­мум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец огра­ничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х _j ≥ 0 или u_j ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (a^j u ≥ с _j или a_i x ≤ b_j ).

5. Множество номеров ограничений, имеющих форму нера­венств в прямой задаче (например, a_i x ≤ b_j или a^j u ≥ с _j ) , опреде­ляют множество индексов переменных, на которые накладыва­ется условие неотрицательности, в двойственной задаче (u_i ≥ 0 или x_i ≥ 0).

-Из приведенного определения вытекает важное свой­ство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей :

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

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

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D ,f ):

тогда двойственной к ней будет задача (D* ,f* ):

1.6.3. Теоремы двойственности и их применение . Фун­даментальные свойства, которыми обладают двойственные за­дачи линейного программирования, могут быть сформулирова­ны в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности .

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

Достаточно доказать теорему для случая, когда задача (D ,f ) является канонической. Рассмотрим пару двойственных задач

Из того, что вектор и является допустимым планом задачи (D *, f *), следует, что иА ≥ с . Умножив левую и правую части дан­ного неравенства на вектор х ≥ 0 , получим равносильную сис­тему неравенств

Одновременно для вектора х, являющегося допустимым планом задачи (D, f ), справедливо равенствоAx=b . Тем самым доказа­но, что и b ≥ сх . -

Замечание. Теорема 1.4, разумеется, верна и для оптималь­ных планов взаимно двойственных задач:f(x*) ≤ f*(u*) , где х* и u*— любые оптимальные планы задач (D, f ) и (D*,f *). На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*).

Теорема 1.5. Если для некоторых допустимых планов и взаимно двойственных задач (D, f ) и (D *,f *)вы­полняется равенство f()=f*( ), то и являются оптимальными планами для этих задач.

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

Согласно теореме 1.4, для всех допустимых планов х задачи (D, f ) справедливо неравенство сх < b . По условию теоремыf()=f( ) или, что то же самое, с = b . Следовательно, верно утверждение: для любого x ÎDс >сх , т. е. х является опти­мальным планом для задачи (D, f ).

Рассуждения, доказывающие оптимальность плана для за­дачи (D* ,f *), проводятся аналогично. -

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

Если предположить, что у двойственной задачи (D *,f *) су­ществует хотя бы один допустимый план и̃ , то, согласно теоре­ме 1.4, для любого допустимого плана х задачи (D, f ) справед­ливо неравенство f ( x ) ≤ f *( )<+∞. Последнее означает, что целевая функция f задачи (D, f ) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о сущест­вовании допустимых планов двойственной задачи (D*,f *) не­верно. -

Следующее утверждение, известное как теорема равнове­сия , используется при проверке оптимальности планов ЗЛП.

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

Векторы х* и и*, будучи допустимыми планами соответствую­щих задач, удовлетворяют условиям: Ах* = b , х * > 0 и и * А-с ≥ 0 . Найдем скалярное произведение

Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u*b =сх*. Последнее означает, что (u* А-с)х * =0 . Однако ска­лярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные про­изведения их соответствующих координат равны нулю. Следо­вательно, еслиx_j * > 0, то u* а ^j – с _j = 0, если жеx_j = 0, то возмож­но u* а ^j – с _j ≥ 0 , что и утверждается в теореме. -

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

Еще раз вернемся к таблице Т ₂ ^{(q )} (рис. 1.8 ), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ^-1 (β^{(q )} ), для которой было введено обозначение δ₀ (β^{(q )} ). По­элементно она может быть записана в следующем виде:

Введем вектор =(δ_0,1 (β^{(q )} ), δ_0,2 (β^{(q )} ),..., δ_0,m (β^{(q )} )). Нетруд­но проверить, что строка оценок a ₀ (β^{(q )} ) может быть представ­лена следующим образом:

Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũ А ≥ с . Следовательно, век­тор и является допустимым планом двойственной задачи.

В то же время элемент b ₀ (β^{(q )} ), содержащий текущее значе­ние целевой функции и равный на последней итерацииf(x*) , до­пускает представление

Согласно теореме 1.5 из равенства f (х* )=f *(ũ ) вытекает, что вектор ũ служит оптимальным планом двойственной задачи:u = ũ.

Окончательно можно утверждать, что для оптимального базиса

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

Читателю в качестве самостоятельного упражнения предла­гается построить задачу, двойственную к (1.34)-(1.35), реше­ние которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2), полученный в таблице Т ₂ ⁽³⁾ , является для нее допустимым и оптимальным планом.

1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП бази­руется на модели простейшей задачи производственного планирования , описанной во введении. Напомним, что в ней каждый (j -й) элемент вектора х рассматривается как план вы­пуска продукции данного вида в натуральных единицах, с _j — цена единицы продукции j -го вида, а ^j — вектор, определяющий технологию расходования имеющихся m ресурсов на производ­ство единицы продукции j -го вида, b — вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых значений A , b и с найден оптимальный план х * , максимизирующий суммарный доход max{cx }=cx *. Достаточно естественным представляется во­прос: как будет изменяться оптимальный план х * при измене­нии компонент вектора ограничений b и, в частности, при ка­ких вариациях b оптимальный план х * останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчи­вости х * имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсовb_i ; могут существенно колебаться после принятия планового решения х *.

Когда вектор ограничений b изменяется на Δb или, как еще говорят, получает приращение Δb , то возникают соответству­ющие вариации для оптимального плана х*( b + Δb ) и значения целевой функции f(х *(b + Δb )). Допустим, приращение Δb та­ково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*( b + Δb ) ≥0. Определим функциюF (b ), возвраща­ющую оптимальное значение целевой функции задачи (D (b ), f ) для различных значений вектора ограничений b

Рассмотрим отношение ее приращенияF ( b + Δb ) -F(b) к при­ращению аргумента Δb . Если для некоторогоi устремить Δb_{i →} 0, то мы получим

Учитывая, что в соответствии с теоремой 1.5

и подставив (1.57) в (1.56), приходим к выражению

-Из формулы (1.58) вытекает экономическая интерпре­тация оптимальных переменных двойственной зада­чи . Каждый элемент u_i * может рассматриваться как предель­ная (мгновенная) оценка вклада i -го ресурса в суммарный доход F при оптимальном решении х *. Грубо говоря, величи­на u_i * равна приросту дохода, возникающему при увеличе­нии ресурса i на единицу при условии оптимального ис­пользования ресурсов.

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

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

-Если при использовании оптимального плана прямой за­дачи i-e ограничение выполняется как строгое неравен­ство, то оптимальное значение соответствующей двой­ственной переменной равно нулю, т.е. если

В рамках рассматриваемой задачи производственного плани­рования это означает, что если некоторый ресурс b_i , имеется в избыточном количестве (не используется полностью при реа­лизации оптимального плана), то i -e ограничение становится несущественным и оценка такого ресурса равна 0.

-Если при использовании оптимального плана двойствен­ной задачи j-e ограничение выполняется как строгое не­равенство, то оптимальное значение соответствую­щей переменной прямой задачи должно быть равно нулю, т. е. если a _1,j u ₁ ^* +...а _m,j и _m – с _j > 0, то х _j ^* = 0.

Учитывая экономическое содержание двойственных оценок u ₁ *,...,u_m , выражение а _1,j u ₁ * +…a_m,j u_m ^* может быть интерпретиро­вано как удельные затраты наj -й технологический процесс. Сле­довательно, если эти затраты превышают прибыль от реализа­ции единицы j -го продукта, то производство j -го продукта является нерентабельным и не должно присутствовать в опти­мальном производственном плане (x_j ^* =0).

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

1.6.5. Анализ параметрической устойчивости реше­ний ЗЛП . В предыдущем пункте мы затронули некоторые ас­пекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b . Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции с _j ,j Î1:n .

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

Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допусти­мых плановD некоторой задачи ЛП. Как видно из рисунка, це­левая функция f (ее поведение отражает линия уровня, пока­занная жирным пунктиром) достигает экстремального значе­ния в точке х *, а изменению ее коэффициентов от с к с' или с" на рисунке соответствует поворот линии уровня относительно х *. Активным, т. е. обращающимся в равенство, ограничениям в точке х * соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с , линия уровня целе­вой функции не выходит за пределы образуемого линиями огра­ничений конуса, х* остается оптимальным планом. Как показа­но на рис. 1.10 , этот план не меняется при переходе от с к с' , и, наоборот, при переходе от с к с" линия уровня целевой функции f(x)=c"x пересечет линию (2), что вызовет изменение опти­мального базисного плана, которым теперь станет точка .

Используя условия оптимальности плана ЗЛП

нетрудно получить количественные оценки для пределов коле­баний коэффициентов целевой функции, при которых не проис­ходит изменение оптимального плана. Допустим, вариации под­вергся некоторый элемент с _r : с _r ^′ = с _r +ε_r . Возможны два случая:

1. Столбец r не входит в оптимальный базис (r ÎN (β^{(q )} )). Тог­да для неизменности оптимального плана необходимо и доста­точно выполнение условия

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

2. Столбец r входит в оптимальный базис (r ÎN (β^{(q )} )). В этом случае для сохранения оптимальности текущего плана потре­буется выполнение для всех небазисных столбцов (j ÏN (β^{(q )} ))условий

Следовательно, в этом случае допустимая вариация должна удовлетворять условиям

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

1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

1.7.1. Основные идеи двойственного симплекс-метода. Непосредственное приложение теории двойственности к вы­числительным алгоритмам линейного программирования позво­лило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода , или метода по­следовательного уточнения оценок . Впервые он был предло­жен Лемке в 1954 г.

В процессе изложения идей, положенных в основу двойст­венного симплекс-метода, еще раз воспользуемся второй геометрической интерпретацией ЗЛП. Рассмотрим некоторую КЗЛП (1.48). На рис. 1.11 изображен конус К положительных линейных комбинаций расширенных векторов условий а ^j для случая m = 2, n = 6, а на рис. 1.12 — (для большей наглядно­сти) — поперечное сечение данного конуса некоторой плос­костьюL , проходящей параллельно оси аппликат.

С каждым планом и задачи, двойственной по отношению к (1.48), можно взаимно однозначно связать гиперплоскость, проходящую через начало координат и перпендикулярную век­тору (-1,и ). Допустимые планы двойственной задачи (1.49) должны удовлетворять условиям иА ≥ с , которые можно пере­писать в виде (1,и )А ≥ 0 . Последнее означает, что всякий рас­ширенный вектор условий а ^j лежит «ниже» плоскости, опреде­ляемой вектором (-1, и ). Таким образом, любому допустимому плану двойственной задачи в рассматриваемом примере соот­ветствует некоторая плоскость, расположенная выше всех рас­ширенных векторов, а стало быть, и конуса К . На рис. 1.12 , где изображено поперечное сечение, конусу К отвечает многогран­ник, а «гиперплоскостям двойственных планов» — пунктирные линии, являющиеся их следами.

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

Из геометрической иллюстрации видно, что плоскости, не соприкасающиеся с конусом К , заведомо не представляют инте­реса, так как для любой из них легко указать плоскость, у кото­рой искомая точка пересечения лежит ниже. Таким образом, процесс поиска экстремума сводится к последовательному пе­ребору плоскостей, касающихся «верхних» граней конуса, или, как еще говорят, опорных по отношению к конусу . Для слу­чая, изображенного на рис. 1.12 , таковыми являются гиперплоскости π_1,2 , π_2,3 , π_3,4 и π_4,5 . Как можно заметить, каждая из рассматриваемых гиперплоскостей натянута на некоторый ба­зисный набор расширенных векторов а ^j , что, собственно, и ис­пользовано для их обозначения (π_1,2 ~ {а ¹ , а ² } и т. д.).

-В дальнейшем систему β={a^{j 1} , a^{j 2} ,...,a^jm } из т линейно-не­зависимых столбцов матрицы условий прямой задачи А будем называть сопряженным базисом , или двойствен­но допустимым базисом , если всякий вектор и Î R^m , удовлетворяющий условиям, удовлетворяет также ус­ловиям иа ^j ≥c_j (j Î1:n), т. е. является допустимым пла­ном двойственной задачи (1.49).

План двойственной задачи и , соответствующий сопряженно­му базису β={a^{j 1} , a^{j 2} ,...,a^jm }, называют опорным планом . Его «опорность» заключается в том, что в системе ограничений u а ^j ≥ c_j (j Î1:n ), задающих область определения двойственной задачиD *, т неравенств с номерами j ÎN (β) обращаются в ра­венства.

Следует обратить внимание на то, что не всем сопряжен­ным базисам соответствуют допустимые базисные планы пря­мой задачи. В частности, вектор b не может быть разложен с неотрицательными коэффициентами по базисам {а ¹ , а ² }, {а ³ , а ⁴ } или {а ⁴ , а ⁵ }. В связи с этим систему коэффициентов разложения вектора b по сопряженному базису называют псев­допланом . В то же время базис {а² , а³ } является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивыс­шую точку пересечения прямой, проходящей через конец b , с конусом К ), а с другой — минимум двойственной (низшую точ­ку пересечения этой прямой с лежащей над К опорной гипер­плоскостью):

Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.

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

* В данном пункте используется та же система обозначений, что и в п. 1.4.1.

-Критерий оптимальности псевдоплана х в двойствен­ном симплекс-методе заключается в том,

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

компоненты должны быть не­отрицательны (х _j ≥ 0).

Обратно, если хотя бы одна из компонент псевдоплана яв­ляется отрицательной, то процесс улучшения значения целе­вой функции может быть продолжен. Геометрическая иллюст­рация данной ситуации приведена на рис. 1.13 . Здесь на плоскости (для m = 2) изображена система столбцов ограниче­ний КЗЛП, из которых {а ¹ , а ² } образуют текущий базис. Как видно из рисунка, вектор ограничений имеет отрицательную ко­ординату по направлению, задаваемому вектором а ¹ . В то же время очевидны и те базисы (например, {а ² , а ³ }), в которых b будет иметь все положительные координаты. Однако это не все­гда так. Пример на рис. 1.14 иллюстрирует случай отсутствия допустимых планов у прямой задачи: вектор b имеет отрицатель­ную компоненту в текущем базисе {а ¹ , а ² } по направлению а ² , а для всех остальных небазисных столбцов (а ³ , а ⁴ ) данная коор­дината является положительной, т. е. b и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных полу­плоскостях, образуемых прямой, проходящей через вектор а ¹ ,

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

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

решаемой КЗЛП является неотрицательность каких-либо r -х компонент во всех столбцах а ^j ,

представленных в текущем базисе β (a_r,j (β) ≥ 0, j Î1:n )если b_r (β) < 0 l.*

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

С другой стороны, если b_r (β)<0 и в строке а _r (β) существуют отрицательные координаты, то псевдоплан можно улучшить выводя из базиса столбец, находящийся на r -м месте, и вводя в него некоторый вектор a^l , имеющий отрицательную r -ую координату. При наличии в векторе b (β) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно опре­деляется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.

Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис опре­делял опорную плоскость, ниже которой располагаются все не­базисные векторы. Для этого требуется, чтобы оценки всех не­базисных векторова _{0 ,j} (β) ( j ÎN (β)), вычисляемые по формулам

а _{0 ,j} (β) = -c_{j +} c (β)а ^j (β)

(см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l должен быть опреде­лен таким образом. Чтобы

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

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

0-этап. Нахождение исходного сопряженного (двой­ственно допустимого базиса). Результатом 0-этапа являют­ся сопряженный базисβ⁽¹⁾ и соответствующие ему псевдоплан x (β⁽¹⁾ ), матрица A (β⁽¹⁾ ) и вектор b (β⁽¹⁾ ), которые будут исполь­зованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I -этап. Стандартная итерация алгоритма — выполня­ется для очередного сопряженного базиса β^{(q )} .

1°. Проверка оптимальности текущего псевдоплана: осу­ществляется просмотр значений b_i (β^{(q )} ), i Î1:m . Возможны два варианта:

1΄. Для всех i Î1:m , b_i (β^{(q )} ) ≥ 0. Тогда текущий псевдоплан x (β^{(q )} ) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный про­цесс закончен. Элементы оптимального плана х * определяют­ся по формуле

а достигаемое на нем значение целевой функции равно

1". Существует по меньшей мере один номер строки r Î1:m , для которого b_r (β^{(q )} )<0 . Следовательно, псевдоплан x (β^{(q )} ) — неоптимален. Выбирается строка с номером r , такая, что

Она становится ведущей и определяет номер столбца N _r (β^{(q )} ), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.

2°. Определение столбца, вводимого в базис. Рассматрива­ется ведущая строка а _r (β^{(q )} ). Возможны два варианта:

2'. Для всех j Î1:n а _r,j (β^{(q )} ) ≥ 0. Делается вывод об отсут­ствии допустимых планов у решаемой задачи (D = Ø) и за­вершается вычислительный процесс*.

* Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную строку а _i (β^{(q )} ), соответствующую b_i (β^{(q )} ) < 0.

2". В строке а _r (β^{(q )} ) существует по крайней мере один эле­мент а _r,j (β^{(q )} )<0. Согласно правилу (1.62) определяются l — номер столбца, вводимого в очередной базис. Переходим к пун­кту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относи­тельно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и век­тора ограничений b относительно нового базиса β^{(q +1)} , который получается в результате вывода из базиса β^{(q )} столбца а ^r и вво­да в него столбца а ^l . Полагаем номер текущей итерации q : = q+ 1 и переходим к первому пункту алгоритма.

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

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

Рассмотрим задачу минимизации:

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

где

Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные х _{n +1} , х _{n +2} ,... , х _n+m :

Задача, двойственная к (1.70)—(1.72), будет иметь вид:

Из (1.74)-(1.75) очевиден допустимый план двойственной задачи

и исходный сопряженный базис, образуемый векторами а ^{n+ 1} ,а ^{n+ 2} ,…., а ^n+m . При этом начальный псевдоплан равен

Таким образом, при решении задачи вида (1.66)-(1.68) двой­ственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.

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

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

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

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

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

1.7.4. Пример решения ЗЛП двойственным симплекс-методом . Рассмотрим на конкретном, примере процесс реше­ния КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b в результате которых

Содержание исходной симплекс-таблицы T ⁽¹⁾ (за исключением столбца b (β⁽¹⁾ )) будет идентично содержанию таблицы, полу­чающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b (β⁽¹⁾ ) в данном случае мож­но воспользоваться обратной матрицей, полученной на послед­ней итерации в п. 1.5.2:

В результате имеем:

Как видно из таблицы Т ⁽¹⁾ , в столбце b (β⁽¹⁾ ) содержатся отрицательные элементы b ₁ (β⁽¹⁾ ) = - 1/3<0), то есть базис β⁽¹⁾ ={ ⁵ , ¹ , ³ } не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b (β⁽¹⁾ ) является единствен­ным, поэтому номер столбца, выводимого из базиса, опреде­ляется однозначно — r =1 и N ₁ (β⁽¹⁾ )=5. Далее рассматриваем строку a ₁ (β⁽¹⁾ ) = (0, -1/6, 0, -1/6, 1). В ней имеются отри­цательные элементы. Вычисляем λ₂ =42:(-(-1/6))=252, λ₄ =38:(-(-1/6))=228. λ₂ > λ₄ , следовательно, номер столбца, вводимого в базис — l =4. Осуществляем преобразование иполучаем симплекс-таблицу T ⁽²⁾ .

Поскольку b (β⁽²⁾ )>0, то достигнутый базис N (β⁽²⁾ )={4,1,3} является оптимальным. Из Т ⁽²⁾ можно выписать оптимальный план х * =(6, 0, 32/3, 2, 0) и соответствующее ему значение це­левой функцииf (x *)= 444.

КЛЮЧЕВЫЕ ПОНЯТИЯ

- Общая задача линейного программирования (ОЗЛП).

- Каноническая задача линейного программирования(КЗЛП).

- Допустимый план.

- Оптимальный план.

- Первая геометрическая интерпретация ЗЛП.

- Базисное решение ЗЛП.

- Вторая геометрическая интерпретация ЗЛП.

- Вырожденный и невырожденный план ЗЛП.

- Симплекс-метод — метод последовательного улучшенияплана.

- Критерий оптимальности допустимого базисного плана.

- Метод минимизации невязок.

- Модифицированный симплекс-метод — вычислительнаясхема, связанная с преобразованием обратных матриц.

- Двойственная задача линейного программирования.

- Симметричность отношения двойственности.

- Теоремы двойственности.

- Экономическая интерпретациядвойственных оценок.

- Параметрическая устойчивость решения ЗЛП.

- Двойственный симплекс-метод — метод последовательно­го уточнения оценок.

- Сопряженный (двойственно допустимый) базис.

- Опорный план и псевдоплан.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.1. Сформулируйте задачу линейного программирования.

1.2. Дайте определение для следующих понятий: план, допус­тимый план, оптимальный план,

решение задачи.

1.3. Чем отличается общая задача линейного программирова­ния от канонической?

1.4. Всегда ли общую задачу линейного программирования можно привести к каноническому виду?

1.5. Дайте определения для следующих понятий: аффинное множество, гиперплоскость, базис.

1.6. Чем отличается выпуклый многогранник от многогранно­го выпуклого множества?

1.7. В чем отличие понятий «линейная оболочка» и «выпуклая оболочка»?

1.8. Любой ли конус является выпуклым множеством?

1.9. Какая точка выпуклого множества называется угловой?

1.10. В чем заключается первая геометрическая интерпрета­ция задачи линейного программирования?

1.11. В чем заключается вторая геометрическая интерпрета­ция задачи линейного программирования?

В чем ее отли­чие от первой?

1.12. Какой план называется базисным?

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

программирования?

1.14. Какой план задачи линейного программирования называ­ется вырожденным?

1.15. Как с точки зрения второй геометрической интерпрета­ции можно представить процесс поиска

оптимального плана в задаче линейного программирования?

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

симплекс-методе.

1.17. Сформулируйте основные этапы стандартной итерации симплекс-метода.

1.18. Для чего применяется преобразование Жордана—Гаусса?

1.19. Какой элемент симплекс-таблицы называется ведущим?

1.20. При каких условиях делается вывод о неограниченности целевой функции в решаемой задаче?

Какая геометриче­ская интерпретация соответствует данному случаю?

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

задачи симплекс-методом? Можно ли найти верхнюю границу для данной величины?

1.22. Какая задача называется вырожденной? По каким призна­кам можно узнать, что текущий план

является вырожден­ным?

1.23. Какие проблемы возникают при решении вырожденных задач?

1.24. Какую экономическую интерпретацию имеет ситуация вырожденности?

1.25. В чем основная идея метода возмущений?

1.26. Для чего предназначен метод минимизации невязок?

1.27. Сформулируйте основные отличия модифицированного симплекс-метода по отношению к

стандартному.

1.28. Перечислите преимущества модифицированного симп­лекс-метода.

1.29. Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее

стандартным и мо­дифицированным симплекс-методом?

1.30. Дайте определение двойственной задачи.

1.31. Какими основными свойствами обладает пара двойствен­ных задач?

1.32. В чем заключается экономическая интерпретация пере­менных двойственной задачи?

1.33. Какой смысл вкладывается в понятие «параметрическая устойчивость»?

1.34. Сформулируйте условия для допустимых изменений це­левой функции задачи, при которых ее

оптимальный план остается неизменным.

1.35. Перечислите основные идеи, на которых базируется алго­ритм двойственного симплекс-метода.

1.36. Дайте определение сопряженного базиса.

1.37. Что такое псевдоплан?

1.38. Сформулируйте критерий оптимальности, используемый в алгоритме двойственного симплекс-

метода.

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

двойственным сим­плекс-методом, пусто?

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

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

2.1. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

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

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

Общая задача нелинейного программирования (ОЗНП) оп­ределяется как задача нахождения максимума (или минимума) целевой функцииf (x ₁ ,х _{2 ,} ...,x_n ) на множествеD , определяемом системой ограничений

где хотя бы одна из функций f илиg_i является нелинейной.

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

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

Как и в ЗЛП, вектор х * = (x ₁ ^* ,x ₂ ^* ,...,x_n ^* ) Î D называется допус­тимым планом , а если для любого x Î D выполняется неравен­ствоf (x *) ≥ f (x ), то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.

С точки зрения экономической интерпретацииf(x) может рассматриваться как доход, который получает фирма (предпри­ятие) при плане выпуска х , а g_i (х ) ≤ 0 как технологические ог­раничения на возможности выпуска продукции. В данном слу­чае они являются обобщением ресурсных ограничений в ЗЛП (а _i х – b_i ≤ 0).

Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:

или запись условий дискретности множеств:

Набор ограничений, определяющих множество D , при необ­ходимости всегда можно свести либо к системе, состоящей из одних неравенств:

либо, добавив фиктивные переменные у , к системе уравнений:

Перечислим свойства ЗНП, которые существенно усложня­ют процесс их решения по сравнению с задачами линейного про­граммирования:

1. Множество допустимых плановD может иметь очень сложную структуру (например, быть невыпуклым или несвяз­ным).

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

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

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

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

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

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

гдеu ÎR^m — вектор дополнительных переменных, называе­мых множителями Лагранжа. Функцию Ф(х,и ), где x ÎRⁿ , u ÎRⁿ , называют функцией Лагранжа . В случае дифференцируемости функций f иg_i справедлива теорема, опре­деляющая необходимое условие существования точки услов­ного экстремума в задаче (2.3)-(2.4). Поскольку она непосредственно относится к предмету математического ана­лиза, приведем ее без доказательства.

Теорема 2.1 . Если х * является точкой условного эк­стремума функции (2.3) при ограничениях

(2.4) и ранг матрицы первых частных производных функций

равен т, то существуют такие и ₁ ^* , и ₂ ^* ,...,и _m ^* , не равные одновременно нулю, при которых

Из теоремы (2.1) вытекает метод поиска условного экстре­мума, получивший название метода множителей Лагранжа, или просто метода Лагранжа . Он состоит из следующих этапов.

1. Составление функции Лагранжа Ф(х,и ).

2. Нахождение частных производных

3. Решение системы уравнений

относительно переменныхx и u .

4. Исследование точек, удовлетворяющих системе (2.7), на максимум (минимум) с помощью достаточного признака экст­ремума.

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

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

2.1.3. Градиентные методы решения задач безуслов­ной оптимизации . Ведущее место среди прямых методов ре­шения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационар­ных точек дифференцируемой функции. Напомним, что стаци­онарной называется точка, в которойf (x )=0 и которая в со­ответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество то­чек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х ⁽¹⁾ перемещаться в направлении вектора f (x ⁽¹⁾ ), то функция f будет возрастать, по крайней мере, в некоторой окрестности х ⁽¹⁾ . Следовательно, для точки х ⁽²⁾ = х ⁽¹⁾ +λf (x ⁽¹⁾ ), (λ>0), лежащей в такой окрестности, справедливо неравенствоf (x ⁽¹⁾ )≤ f (x ⁽²⁾ ). Продолжая этот про­цесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1 ).

Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага λ в рекуррентной формулe

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

В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее изве­стных из них.

Метод наискорейшего спуска

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

Пустьf(x)=f(x ₁ ,x ₁ ,...x_n ) —дифференцируемая функция, заданная на Rⁿ , а х ^{(q )} =(x ₁ ^{(q )} ,x ₂ ^{(q )} ,...,x _n ^{(q )} ) — некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, каса­ющихся выбора исходной точки (или, как еще говорят, началь­ного приближения) х ⁽⁰⁾ , не существует, однако по возможно­сти она должна находиться близко от искомого оптимального плана х *. Как уже говорилось выше, если х ^{(q )} — нестационарная точка (т. е. |f (x ^{(q )} )|>0), то при движении в направлении f (x ^{(q )} ) функция f (х ) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продол­жалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значенияf(x) от шагового множителя λ > 0. полагая х = х^{(q )} + λf (x ^{(q )} )

или, в координатной форме,

Чтобы добиться наибольшего из возможных значений f при движении по направлениюf (x ^{(q )} ), нужно выбрать такое значе­ние , которое максимизирует функцию φ(λ) (φ()= max(φ(λ)). Для вычисления , используется необходимое условие экстре­мума d φ(λ)/d λ =0. Заметим, что если для любого λ>0 d φ()/d λ> 0, то функция f (х) не ограничена сверху (т. е. не име­ет максимума). В противном случае, на основе (2.10) получаем

что, в свою очередь, дает

Если считать, что следующая точка х ^{( q + 1 )} соответствует оп­тимальному значению λ=, то в ней должно выполняться условиеd φ()/d λ =0, и следует находить из условияf (x ^{(q +1)} )f (x ^{(q )} )=0 или

Условие (2.13) означает равенство нулю скалярного про­изведения градиентов функции f точках x ^{(q +1)} и x ^{(q )} . Гео­метрически оно может быть интерпретировано как перпенди­кулярность векторов градиентов функции f в указанных точ­ках, что и показано на рис. 2.2 . Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точкеx ^{(q +1)} векторf (x ^{(q +1)} ), будучи градиентом, перпендику­лярен линии уровня, проходящей через данную точку. Стало быть, векторf (x ^{(q )} ) является касательным к этой линии. Итак, движение в направлении градиентаf (x ^{(q )} ) следует продолжать до тех пор, пока он пересекает линии уровня оп­тимизируемой функции.

После того как точка x ^{(q +1)} найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение коор­динат точек, рассматриваемых на последовательных итераци­ях. Одновременно с этим координаты вектора Δf (x ^{(q )} ) должны быть близки к нулю.

Метод дробления шага

Для нахождения шага λ в методе наискорейшего спуска требу­ется решить уравнение (2.13), которое может оказаться доста­точно сложным. Поэтому часто ограничиваются «подбором» такого значения λ, что φ(λ) > φ(0). Для этого задаются некото­рым начальным значением λ₁ , (например,λ₁ =l) и проверяют условие φ(λ₁ ) >φ(0). Если оно не выполняется, то полагают

λ₂ = 1/2 λ₁

и т. д. до тех пор, пока не удается найти подходящий шаг, с кото­рым переходят к следующей точке x ^{(q +1)} . Критерий завершения алгоритма, очевидно, будет таким же, как и в методе наискорей­шего спуска.

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

в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений х ⁽⁰⁾ .

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

-Функция f(x) = f (x ₁ , x ₂ , …, x_n )называется выпуклой в области D, если для любых двух точек х ⁽¹⁾ ,

х ⁽²⁾ ÎD и любо­го λ Î [0,1] выполняется неравенство

если же

то функция называется вогнутой.

Геометрический смысл понятий выпуклости и вогнуто­сти для случая функции одной переменной представлен на рис. 2.3. Из него, в частности, видно, что график выпуклой функ­ции лежит ниже отрезка, соединяющего точки (х ⁽¹⁾ , f (x (¹⁾ )) и (х ⁽²⁾ , f (x ⁽²⁾ )), а график вогнутой — выше .

Можно доказать, что достаточным условием выпуклости функцииf (x ₁ , x ₂ , …, x_n ) является положительная определен­ность матрицы

называемой также матрицей Гессе , во всех точках х Î D . Со­ответственно, достаточным условием вогнутости являет­ся отрицательная определенность матрицы Гессе. В част­ности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства fⁿ (x )≥0 (fⁿ (x )≤0).

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

Теорема 2.2. Если f(x) выпуклая (вогнутая) на Rn функция и f (x *)= 0, то х* — точка глобального мини­мума (максимума).

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

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

Пусть х — произвольная точка, отличная от точки х *. Тогда, для любого λ Î [0,1], в силу вогнутости функцииf(x) будет вы­полняться

из чего следует

Если ввести вектор l = х - х * и обозначить Δх = λ(x – х * ) = λl , то длина вектора Δх будет равна ||Δx ||=λ||l ||. Следовательно,

Устремив λ → 0 и учитывая, что вектор l сонаправлен с Δх , получим

По условию теоремы f (x *)=0. Это означает, что для любо­го вектора l (а, стало быть, для любой точки х ) согласно формуле, выражающей производную по направлению через градиент,

Следовательно, для любой точки х , не равной х *, справедли­во неравенствоf(x)-f(x)≤ 0 <=> f(x)≤ f(x *) , т.е. х * — точка гло­бального максимума. -

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

2.1.5. Метод допустимых направлений . Данный метод также называется методом возможных направлений или же по имени автора—методом Зойтендейка, см. [16]. Его основную идею будет удобно продемонстрировать на примере ЗНП с огра­ничениями в форме неравенств:

В указанном методе так же, как и в градиентных методах, на­ходится последовательность точек х ⁽⁰⁾ х ⁽¹⁾ ,..., х ^{(q )} ..., таких, что f (х ^{(q +1)} ) ≥ f (x ^{(q )} ) *. При этом переход от точки x ^{(q )} ) к точке х ^{(q +1)} )происходит по некоторому выбранному направлению s ^{(q )} с ша­говым множителем λ_q :

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

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

-Направление s называется допустимым (возможным) в точке x ^{(q )} ÎD ,если существует такое

λ > 0,что x ^{(q +1)} = x ^{(q )} + λs Î D.

-Направление s называется прогрессивным в точке x ^{(q )} Î D ,если существует такое λ >0, что

f (x ^{(q )} + λs )> > f (x ^{(q )} ) для задачи максимизации и f (x ^{(q )} + λs ) <f (x ^{(q )} ) для задачи минимизации.

На основе данных определений достаточно просто сформу­лировать критерий проверки оптимальности точки (так назы­ваемый критерий оптимальности в терминах допустимых и про­грессивных направлений):

-точка х* является оптимальным планом задачи (2.16), если в ней ни одно допустимое

направление не является прогрессивным.

В алгоритме метода допустимых направлений правила выбо­ра точких ^{(q +1)} , к которой происходит очередной переход, раз­личаются в зависимости от того, где находится текущая точка х ^{(q )} . Принципиально возможны две ситуации.

1° . Точка х ^{(q )} лежит внутри области D , т. е. для всехi Î 1: m g_i (х ^{(q )} ) < 0 (см. рис. 2.4 ). Очевидно, что для внутренней точки любое направление будет допустимым (при выборе достаточно малого шага), поэтому естественным представляется движение в сторону «гарантированного» возрастания значения функции, а именно в направлении градиента. Значит, для внутренней точ­ки х ^{(q )} целесообразно выбратьs ^{(q )} =f (х ^{(q )} ).

Шаговый множитель λ_q выбирается так, чтобы, с одной сто­роны, новая точках ^{(q +1)} принадлежала D , а с другой — значе­ние целевой функции в ней f (х ^{(q +1)} ) было как можно большим.

С этой целью сначала найдем промежуток [0,] из условиядля чего необходимо решить систе­му неравенств:

Зная промежуток [0, ], определяем значение шагового множителя λ_q из условия максимизации значения функции в направленииs^(q) :

Вновь найденная точка x ^{(q +1)} может находиться или внутри областиD , или на ее границе. В первом случае (на рис. 2.4 ему соответствует точка ^{(q +1)} переходим к началу данного пункта и повторяем вышеописанные действия, а во втором (точка ^{(q +1)} на рис. 2.4 ) — действуем по рассматриваемой далее схеме.

2°. Точка x ^{(q )} находится на границе области (см. рис. 2.5 ). Это означает, что одно или несколько неравенств из системы ог­раничений задачи (2.16) выполняются как строгие равенства:g_i (x ^{(q )} ) = 0. Например, на рис. 2.5 и g ₁ (x ^{(q )} ) = 0 иg ₃ (x ^{(q )} ) = 0.

Ограничение, которое в текущей точке выполняется как ра­венство, называют активным. Множество номеров активных ограничений в точке x ^{(q )} будем обозначать как I (x ^{(q )} ). В приме­ре, изображенном на рис. 2.5 , I (x ^{(q )} ) = {1, 3}. Также из рисунка видно, что все допустимые направления, исходящие из точки x ^{(q )} , должны образовывать тупые углы с векторами градиентов фун­кций, задающих активные ограничения в данной точке. По­следнее условие может быть выражено через задание ограниче­ний на значения скалярных произведений вектора направленияs на градиенты функции ограничений:

где I _л — множество номеров индексов линейных ограничений, I _н — множество номеров индексов нелинейных ограничений. Со­ответственно, I (x ^{(q )} )◠I _л —номера линейных активных ограни­чений, а I (x ^{(q )} )◠I _н — номера нелинейных активных ограниче­ний. Отличие условий (2.20) от условий (2.21) заключается в том, что в случае линейного ограничения направление, образу­ющее прямой угол с градиентом ограничивающей функции (т. е. их скалярное произведение равно нулю), будет заведомо допустимым, а в случае нелинейного ограничения — возможно, нет.

Все возможные направления в точке x ^{(q )} образуют так назы­ваемый конус допустимых направлений , и из них для следующего перехода, очевидно, нужно выбрать прогрессивное. Если такового не существует, то согласно сформулированному выше критерию точка x ^{(q )} является оптимальной! Для ускорения мак­симизации функции желательно, чтобы угол между искомым допустимым прогрессивным направлениемs ^{(q )} и градиентом це­левой функции ∇f (x ^{(q )} ) был как можно меньше или, что то же самое, как можно большей была бы проекция s на∇f (x ^{(q )} ) (при условиях нормировки вектораs ^{(q )} ). Иными словами, желатель­но, чтобы неравенствоs ^{(q )} ∇f (x ^{(q )} )+σ≥0 выполнялось при ми­нимально возможном σ∈R . Тогда задачу отыскания наилучше­го допустимого прогрессивного направленияs ^{(q )} можно свести к задаче минимизации параметра σ:

при условиях

гдеs ₁ ² +s ₂ ² +...+s_n ² , ≤ l —условие нормировки, обеспечивающее ограниченность решения;

τ — некоторое достаточно малое число, характеризую­щее «строгость» выполнения неравенств.

В отличие от всех остальных, последнее условие в системе (2.23) является нелинейным, что существенно усложняет про­цесс решения задачи (2.22)-(2.23). Поэтому на практике дляопределения направленияs ^{(q )} (возможно, не лучшего) перехо­дят от данной задачи к задаче линейного программирования пу­тем замены указанных выше условий нормировки на ограниче­ния вида –l ≤ s_j , ≤1:

После того как прогрессивное направлениеs ^{(q )} найдено, ша­говый множитель определяется по методу, описанному в п. 1°.

В заключение отметим, что при практических расчетах алго­ритм завершается при достижении такой точки х *, в которой |∇f (x *)|<ε, где ε —достаточно малое число.

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

2.1.6. Пример решения ЗНП методом допустимых на­правлений . Рассмотрим процесс применения метода допусти­мых направлений на конкретном примере. Пусть дана ЗНП:

Итерация 1 . В качестве начального приближения возьмем точку х ⁽¹⁾ = (0,0). Нетрудно заметить, что она удовлетворяетсистеме неравенств (2.27), т. е. х ⁽¹⁾ ∈D . Для х ⁽¹⁾ все неравенства выполняются как строгие, т. е. множество индексов активных ограничений I (х ⁽¹⁾ )=∅. Следовательно, в х ⁽¹⁾ любое направле­ние является допустимым, и нам остается определить, с каким шагом λ₁ можно двигаться вдоль градиента целевой функции s ⁽¹⁾ =∇f (x ⁽¹⁾ )=(1, 1). Система неравенств типа (2.18), из решения которых определяется интервал допустимых значений для λ, для данной задачи примет вид:

Тогда

достигается при λ₁ = 3 . Отсюда получаем следующую точку

Итерация 2. Путем подстановки координат точки x ⁽²⁾ в (2.27) определим множество активных ограничений в точке x ⁽²⁾ : I (x ⁽²⁾ )={2}. Соответственно, задача (2.24) - (2.25), кото­рую требуется решить для определения допустимого прогрес­сивного направленияs ⁽²⁾ с учетом того, что ∇f (x ⁽²⁾ )=(1, 1) и ∇g ₂ (x ⁽²⁾ )= (0, 1) примет вид:

В данном случае оптимальный план ЗЛП находится доволь­но просто и равен (σ,s ₁ ,s ₂ )* =(-1,1, 0). Отбросив дополнитель­ную переменную σ, получаем векторs ⁽²⁾ = (1,0), т. е. очередная точка будет определяться как

Действуя по аналогии с предыдущей итерацией, для опреде­ления промежутка допустимых значений шагового множителя λ составляем систему неравенств (2.18):

Окончательно имеем λ∈ [0; 1].

Тогда

достигается при λ₂ =1. Отсюда получаем следующую точку x ⁽³⁾ = (3,4).

Итерация 3. В точке x ⁽³⁾ множество активных ограничений будет иметь вид I (x ⁽³⁾ )={1,2}. Найдем значения градиентов: ∇f (x ⁽³⁾ ) = (1, 1), ∇g ₁ (x ⁽³⁾ ) = (2x ₁ ⁽³⁾ , 2x ₂ ⁽³⁾ ) =(8, 6) и ∇g ₂ (x ⁽²⁾ ) = (0,1).

Задача определения допустимого прогрессивного направле­ния (2.24)-(2.25) будет иметь вид:

Значение τ из практических соображении следует брать до­статочно малым, например τ =0,001. Опуская решение данной задачи, приведем интересующие нас компоненты ее оптималь­ного плана:s ⁽³⁾ = (0,0). Итак, не существует прогрессивного на­правления, исходящего из точки х ⁽³⁾ Таким образом, оптималь­ный план рассматриваемой задачи (2.26)-(2.27) х * = (4,3), а максимальное значение целевой функции f * = х ₁ ⁽³⁾ + х ₂ ⁽³⁾ =7.

Графическая иллюстрация проведенного процесса решения представлена графически на рис. 2.6.

2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

2.2.1. Понятие седловой точки. В настоящем параграфе мы кратко остановимся на некоторых фундаментальных моментах теории нелинейного программирования. Отправной точкой для них является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств:

где X — некоторая область в пространствеRⁿ .

По аналогии с п. 2.1.2 определим для задачи (2.28) функцию Лагранжа:

-Пара векторов (х, u ) называется седловой точкой фун­кции Ф (х, и ) в некоторой области X x U , если

для любых x ∈ X и u ∈ U

Неравенства (2.30) также называют неравенствами седловой точки .

В качестве примера седловой точки может быть приведена точка (0, 0) для функции Ф(х,и ) = -х ² + и ² , определенной на множестве R х R . В самом деле, Ф(0,0)=0, Ф(х ,0)=-х ² , Ф(0, и ) = и ² , а для любых x ∊R иu ∊R выполняются неравенства –х ² ≤0 и 0 ≤и ² .

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

2.2.2. Теорема Куна—Таккера. Центральное место в те­ории нелинейного программирования занимает теорема Куна— Таккера, которая связывает решение ЗНП с наличием седловой точки у соответствующей функции Лагранжа.

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

По определению седловой точки

при всех x ∊X ,и≥ 0. Из второго неравенства в (2.32) следует, что

Однако (2.33) может иметь место только тогда, когда g_i (x )≤0 при всех i ∊1:m . Действительно, если существует та­коеk, чтоg_k (x )>0, то, положив и _i =0 для всехi ≠ k и выбрав достаточно большое и _k > 0, можно добиться того, что значение

окажется больше постоянного выражения

Из того, что для всех i ∊1:m выполняются неравенстваg_i (x )≤0, следует, что х является допустимым планом задачи (2.28).

Если в левую часть неравенства (2.33) подставить значения u_i = 0,i ∊1:m , то получим, что

Вместе с тем из того что,g_i (x )≤0 и u_i ≥0, следует оценка

Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке х :

Тогда на основании левой части неравенства седловой точки (2.32) имеем, что для всех х ∊Х (в том числе и для х ∊D )

Но условию ЗНП для любыхх ∊D верны неравенства g_i (x )≤0, что, в сочетании с условием u_i ≥0, позволяет записать

Значит,

Окончательно получаем, что для любыхх ∊D справедливо со­отношениеf(x) ≥f(x), т. е. х — оптимальный план задачи (2.28). -

Утверждение, обратное теореме (2.3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при вы­полнении дополнительных условий, которым должна удовлет­ворять задача (2.28). Важнейшим из них является так называе­мое условие регулярности Слейтера:

-Говорят, что функция g_i (х), задающая ограничение в за­даче (2.28), удовлетворяет условию регулярности Слей­тера, если существует такая точка , принадлежащая области допустимых планов D, что

т. е. является внутренней точкой относительно ограниченияg_i (x). Поэтому данное условие также называют условием теле­сности.

Вообще говоря, существуют разные варианты необходимо­го условия Куна—Таккера. Приведем один из них.

Мы не будем здесь приводить доказательство теоремы (2.4), которое является довольно сложным. Заинтересованный чита­тель может найти его в таких источниках, как [1, 13].

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

ОпределимF(x) как функцию, ставящую в соответствие каждому значению х минимальное значение функции Ф(х,и ) по и :

и по аналогии

Рассмотрим задачу отыскания максимума функцииF(x)

и задачу минимизации G(u)

Очевидно, что

Отсюда следует, что максимум F(x) находится в допустимой областиD и совпадает с максимумом целевой функцииf(x) зада­чи (2.28):

Таким образом, задача (2.34), в определенном смысле, рав­носильна (2.28). Аналогичные выводы могут быть получены и для (2.35). Задачи (2.34) и (2.35) образуют двойственную пару. Как нетрудно догадаться, данное отношение является обобще­нием отношения двойственности для задач линейного програм­мирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых х ∊Х , и ≥0

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

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

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

КЛЮЧЕВЫЕ ПОНЯТИЯ

- Общая задача нелинейного программирования.

- Условная и безусловная оптимизация.

- Прямые и непрямые методы решения оптимизационных задач.

- Стационарная точка.

- Градиентные методы.

- Метод наискорейшего спуска и методы дробления шага.

- Выпуклая и вогнутая функции.

- Матрица Гессе.

- Достаточное условие выпуклости (вогнутости).

- Задача выпуклого программирования.

- Допустимое направление.

- Прогрессивное направление.

- Седловая точка.

- Теорема Куна—Таккера.

- Условие регулярности Слейтера.

КОНТРОЛЬНЫЕ ВОПРОСЫ

2.1. При каких условиях оптимизационная задача может быть отнесена к классу нелинейных?

2.2. Приведите пример экономической модели, сводящейся к задаче нелинейного программирования.

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

программирования.

2.4. Какой смысл вкладывается в понятие «условная оптими­зация»?

2.5. Для чего предназначен метод множителей Лагранжа и в чем он состоит?

2.6. Какая точка называется стационарной?

2.7. Какие принципиальные этапы входят в градиентные ме­тоды?

2.8. Для решения каких задач предназначены метод наиско­рейшего спуска и метод дробления шага?

2.9. Дайте определение выпуклой (вогнутой) функции.

2.10. Сформулируйте достаточное условие выпуклости (во­гнутости) функции.

2.11. В чем заключена специфика задач выпуклого программи­рования?

2.12. Перечислите основные этапы, входящие в метод допусти­мых направлений.

2.13. Сформулируйте задачу, которая должна быть решена при определении шага в методе

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

2.14. Исходя из каких соображений определяется допустимое прогрессивное направление?

2.15. Какое условие используется для определения оптималь­ности текущей точки в методе

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

2.16. Дайте определение седловой точки. Приведите пример функции, имеющей седловую точку.

2.17. Сформулируйте необходимое и достаточное условия тео­ремы Куна—Таккера. Какое значение

они имеют для ре­шения задач нелинейного программирования?

2.18. В чем состоит условие регулярности Слейтера? Поясните его содержание.

2.19. Какое условие получило название «правила дополняю­щей нежесткости»?

2.20. Приведите пример пары двойственных задач нелинейного программирования.

2.21. Какие свойства пары нелинейных двойственных задач мо­гут быть применены для их решения?

ГЛАВА 3. ТРАНСПОРТНЫЕ И СЕТЕВЫЕ ЗАДАЧИ

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

3.1. ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ

3.1.1. Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной, постановке , о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты по­требления (║x_i,j ║_{m xn} ), который минимизирует целевую функцию

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

при соблюдении условия баланса

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

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m +n )хmn . Матрицы систем уравне­ний в ограничениях (3.2) и (3.3) имеют ранги, равные соответ­ственноm иn . Однако, если, с одной стороны, просуммировать уравнения (3.2) по m , а с другой — уравнения (3.3) по n , то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспорт­ной задачи равен m +n -1, и ее невырожденный базисный план должен содержать m +n -1 ненулевых компонент.

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

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта а _i ), а столбцы — пунктам потребления (послед­няя клетка каждого столбца содержит значение потребности b_j ). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о пе­ревозке из i -го пункта в j -й: в левом верхнем углу находится

цена перевозки единицы продукта, а в правом нижнем — значе­ние объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (х _i,j = 0), называют сво­бодными , а ненулевые — занятыми (x_i,j >0).

3.1.2. Построение исходного допустимого плана в транс­портной задаче. По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом мето­де северо-западного угла . Суть метода состоит в последова­тельном распределении всех запасов, имеющихся в первом, вто­ром и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте про­изводства или к попытке полного, удовлетворения потребно­стей в очередном пункте потребления. На каждом шагеq вели­чины текущих нераспределенных запасов обозначаются а _i ^{(q )} , а текущих неудовлетворенных потребностей — b_j ^{(q )} . Построение допустимого начального плана, согласно методу северо-запад­ного угла, начинается с левого верхнего угла транспортной таб­лицы, при этом полагаем а _i ⁽⁰⁾ =а _i , b_j ⁽⁰⁾ = b_j . Для очередной клетки, расположенной в строкеi и столбце j , рассматриваются зна­чения нераспределенного запаса в i -ом пункте производства и неудовлетворенной потребности j -ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: x_i,j = min{а _i ^{(q )} , b_j ^{(q )} }. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на дан­ную величину:

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а _i ^{(q +1)} =0 или b_j ^{(q +1)} =0 . Если справедливо первое, то это означает, что весь запас i -го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте произ­водства i +1, т. е. переместиться к следующей клетке вниз по столбцу. Если же b_j ^{(q +1)} = 0, то значит, полностью удовлетворе­на потребность для j -го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все пере­численные операции.

Основываясь на условии баланса запасов и потребностей (3.5), нетрудно доказать, что за конечное число шагов мы полу­чим допустимый план. В силу того же условия число шагов ал­горитма не может быть больше, чем m +n -1, поэтому всегда останутся свободными (нулевыми) mn -(m+n -1) клеток. Следовательно, полученный план является базисным. Не ис­ключено, что на некотором промежуточном шаге текущий не­распределенный запас оказывается равным текущей неудовлет­воренной потребности (а _i ^{(q )} = b_j ^{(q )} ). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и по­требления), а это означает «потерю» одной ненулевой компо­ненты в плане или, другими словами, вырожденность построен­ного плана.

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

Особенностью допустимого плана,, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимально­го. Это происходит потому, что при его построении никак не учитываются значения с _i,j . В связи с этим на практике для по­лучения исходного плана используется другой способ — ме­тод минимального элемента , в котором при распределении объемов перевозок в первую очередь занимаются клетки с наи­меньшими ценами.

3.1.3. Критерий оптимальности. Рассмотрим более по­дробно структуру матрицы транспортной задачи. Схематично она показана на рис. 3.2.

Из него видно, что матрица имеет размерность (m +n )хmn , состоит из нулей и единиц и распадается на две группы однотип­ных блоков. Первая (верхняя) соответствует ограничениям на

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

Построим двойственную задачу. С учетом специфической структуры матрицы транспортной задачи вектор двойственных переменных будет иметь размерность m +n , причем его компо­ненты, соответствующие первой группе ограничений, обозна­чим через (-u_i ), i ∊1: m , а второй — через v_j , j ∊1:n (рис. 3.2 ). Тогда двойственная задача будет иметь вид:

Переменные u_i называют потенциалами пунктов производства , а v_j — потенциалами пунктов потребления . Применяя доказанные в главе 1 теоремы двойственности (см. теорему1.7), можно получить критерий оптимальности для плана транспортной задачи:

-Для того, чтобы допустимый план транспортной зада­чи х _i,j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы и _i , v_j , для которых

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

3.1.4. Алгоритм метода потенциалов для транспорт­ной задачи. Критерий (3.8)-(3.9) положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов . Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом.

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

Алгоритм начинается с выбора некоторого допустимого ба­зисного плана (методы его построения были рассмотрены в п. 3.1.2). Если данный план не вырожденный, то он содержит m + n -1 ненулевых базисных клеток, и по нему можно так оп­ределить потенциалы u_i и v_j , чтобы для каждой базисной клет­ки (т. е. для той, в которой х _i,j > 0) выполнялось условие

Поскольку система (3.10) содержит m +n -1 уравнение и m +n неизвестных, то один из потенциалов можно задать произволь­но (например, приравнять v_j или u_i к нулю). После этого ос­тальные неизвестные u_i и v_j определяются однозначно.

Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, по­строенный методом северо-западного угла (см. табл. 3.2).

Потенциал первого пункта потребления принимаем равным нулю (v ₁ =0). Теперь, зная его, мы можем определить потенци­алы для всех пунктов производства, связанных с первым пунк­том ненулевыми перевозками. В данном случае их два (это пер­вый и второй пункты), получаем:

Имея u ₂ и учитывая, что во второй строке таблицы существу­ют еще ненулевые компоненты х _2,2 и х _2,3 , можно определить v ₂ = u ₂ +c _2,2 =-10+17=7 и v ₃ =u ₂ +c _2,3 =-10+15=5, после чего появляется возможность рассчитать u ₃ =v ₃ – c _3,3 =5-25 =-20 и, наконец, v ₄ =u ₃ +c _3,4 =-20 +21=1. В результате получаем полную систему потенциалов, показанную в табл. 3.3.

Для свободных клеток транспортной таблицы вычисляют­ся величины α_i,j = v_j -u_i , называемые разностями потенциа­лов . В табл. 3.4 они выписаны для всех небазисных клеток под ценами.

Разность потенциалов α_i,j можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j . Согласно критерию оптимальности (3.8)-(3.9), если все α_i,j ≤ с _i,j , то план оптимален, в противном случае, если существует хотя бы одна разность потенциалов α_i,j > с _i,j , то он может быть улучшен. Про­цесс «улучшения» плана состоит в определении вводимой и выво­димой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

Кандидатом на ввод, очевидно, может быть любая клетка, в которой α_i,j > с _i,j , поскольку после ввода в базис будет обеспе­чено равенство α_i,j = с _i,j . Для определенности обычно рекомен­дуется брать ту клетку, в которой оценка α_i,j -с _i,j максималь­на. В рассматриваемом нами примере это будет клетка (3, 1).

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

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

В построенной цепочке, начиная с вводимой клетки (кото­рая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (та­ковой, в частности, является клетка, вводимая в план, посколь­ку она должна стать базисной). Знаком «—» — те клетки, в ко­торых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирает­ся клетка с наименьшим значением х _i,j (обозначим его θ). Она и становится кандидатом на вывод, т. к. уменьшение объема пе­ревозок на большую величину может привести к отрицатель­ным значениям х _i,j в других «минусовых» клетках. Затем произ­водится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем θ, а из объемов клеток, помеченных знаком «—», он вычитается. В ре­зультате ввода одной клетки и вывода другой получается новыйбазисный план, для которого на следующей итерации описан­ные выше действия повторяются.

В нашем примере знаком «—» отмечены клетки (2,1) и (3,3), причемx _2,1 = 6,x _3,3 =26. Вычислив значение θ = min{x _2,1 , x _3,3 } = 6, осуществляем преобразование и переходим к следующему ба­зисному плану, показанному в табл. 3.6.

Для вновь полученного плана повторяются действия стан­дартной итерации: рассчитываются потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план в табл. 3.6 также не является оптимальным (в клетке (1,3) α_i,j =25 > с _i,j =21), поэтому вновь строим цепочку преобразо­вания плана и переходим к следующему базисному плану (табл. 3.7).

Из транспортной таблицы 3.7 видно, что полученный план оптимален, так как все разности потенциалов для небазисныхклеток α_i,j = v_j – u_i не превышают соответствующих цен с _i,j . По данному плану вычисляется оптимальное (наименьшее) значе­ние суммарных издержек на перевозку

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного пла­на. Возможность получения вырожденного плана уже отмеча­лась при описании метода северо-западного угла. Нетрудно за­метить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одина­ковое минимальное значение будет достигнуто сразу на не­скольких клетках, помеченных знаком «—», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m +n -1 ненулевых компонент. Способ преодоления вы­рожденности в транспортной задаче весьма прост, а именно:предлагается дополнить текущий план необходимым коли­чеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему по­тенциалов, и далее действовать в соответствии с правилами опи­санного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К такому выводу легко прий­ти, если положить, что добавляемые фиктивные клетки содер­жат некоторый малый объем ε.

3.2. СЕТЕВЫЕ ЗАДАЧИ

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

-Ориентированным графом называется тройка (I, D, G), в которой I — непустое множество вершин ,D — множество дуг и G — отображение, которое каж­дой дуге d ∊ D ставит в соответствие упорядоченную пару вершин (i, j) , где i, j ∊ I.

-Неориентированным графом называется тройка ( I , D , G), в которой I — непустое множество вершин , D — множество ребер и G — отображение, которое каж­дому ребру d ∊D ставит в соответствие неупорядочен­ную пару вершин [i, j ], где i, j ∊ I.

Граф (I , D, G ) называется конечным , если множестваI и D конечны.

Геометрически граф может быть представлен в виде множе­ства точек (изображающих вершины) и соединяющих их линий (со стрелками), соответствующих ребрам (дугам) (рис. 3.3, 3.4 ). Очевидно, что с каждым ориентированным графом можно одно­значно связать неориентированный, заменив дуги на ребра. Если любые две вершины графа соединяются не более чем од­ной дугой (ребром), то граф называется простым и может быть задан с помощью пары (I , D ). В этом случае каждая дуга (реб­ро)d полностью определяется парой соединяемых вершин (i , j ), что условно записывается в виде:d=(i,j). Упорядочен­ная пара вершин (i, j ), которая ставится в соответствие некото­рой дуге d , задает ее ориентацию: i называется началом дуги, аj — ее концом , а сама дуга считается инцидентной данным вер­шинам.

Путем длины п в ориентированном графе (I ,D ) называется упорядоченная последовательность различных дуг (d ₁ , d ₂ ,..., d_n ), для которых начало каждой последующей со­впадает с концом предыдущей. Конечный путь, у которого на­чальная вершина совпадает с конечной, называется контуром.

Для неориентированного графа аналогом понятия путь яв­ляется цепь , а контура — цикл .

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

Связный неориентированный граф, не содержащий циклов,называется деревом .

Если Y ⊂D , а отображениеG_Y является сужением отобра­женияG на множество Y , то граф (I , Y , G_Y ) называют частич­ным графом (реберным подграфом) графа (I , D, G ).

Рассмотрим задачу: имеется конечный граф (I , D, G ), каж­дой вершине i которого сопоставлено некоторое число b_i , на­зываемое интенсивностью вершины . Граф (I , D, G ), верши­нам которого сопоставлены значения интенсивностей b_i , будем называть сетью . Если b_i > 0, то вершина i называется источни­ком , если b_i < 0, то — стоком , а если b_i = 0, то — нейтральной вершиной. Множество источников, стоков и нейтральных вер­шин обозначим соответственноI ⁺ , I ^- ,I ⁰ .

Для определенной выше сети потоком называется такая совокупность величин, заданных на множестве дуг, Х ={х _d }_{d ∊ D} ,что

где D_i ⁺ — множество дуг, исходящих из вершины i , a D_i ^- — мно­жество дуг, входящих в нее. Величина х _d называется значени­ем потока по дуге d и содержательно интерпретируется как количество продукта, пропускаемого по данной дуге.

Соотношение (3.11) означает, что для любой вершины сети разность выходящего и входящего потоков равна ее интенсив­ности.

На базе введенной терминологии может быть сформулирова­но много различных задач. Рассмотрим наиболее известные из них. Для каждой дуги d ∊D определим значения c_d ≥ 0, называ­емые стоимостью перемещения единицы продукта по дуге, тогда суммарная стоимость потока Х примет вид

Задачу минимизации функции (3.13) при ограничениях (3.11)-(3.12) обычно называют линейной сетевой задачей . Очевидно, что она является задачей линейного программирова­ния. Если дополнительно для каждой дуги сетиd ∊D опреде­лить величины r_d ≥ 0, называемые пропускными способно­стями , то, добавив ограничения

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

Приведенные формулировки задач специально даны в столь абстрактном виде, что позволяет подчеркнуть их универсаль­ность. К очевидной сфере их приложения относится организа­ция грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные сетью дорог, и характеризуются потребностями в некотором продукте (b_i <0) или его запасами (b_i >0). Задачи определения плана, минимизирующего затраты на перевозки, которые с матема­тической точки зрения полностью идентичны (3.11)-(3.13), (3.14), также называют транспортными задачами в сете­вой постановке.

3.2.2. Метод потенциалов для транспортной задачи в сетевой постановке. Рассмотрим задачу определения опти­мального потока Х в некоторой сети (I , D, G ), для которого

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

где r_d ≥ 0. Предполагается также, что сеть является сбаланси­рованной, т. е.

Для задачи (3.15)-(3.17) справедлив критерий оптималь­ности:

-Для того, чтобы допустимый поток Х={х _d } _{d ∊ D} (т. е. удовлетворяющий условиям (3.16)-(3.17)) был опти­мальным, необходимо и достаточно существование для каждой вершины i ∊ I такого числа v_i , называемого по­тенциалом , что для всех дуг d = (i, j)

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

Для решения транспортной задачи в сетевой постановке (3.15)-(3.17) также может быть применен метод потенциа­лов , который является обобщением описанного выше мето­да потенциалов для транспортной задачи в матричной поста­новке.

Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее можно привести к ка­нонической форме. При этом достаточно просто устанавлива­ется, что ранг матрицы задачи равен m -1, где m — количество вершин в сети. Введем дополнительно еще некоторые понятия, используемые при описании свойств сетевых задач.

Остовом сети (I , D, G ) называется любое ее частичное дере­во (частичный граф, являющийся деревом). Справедливо утвер­ждение:

-Произвольному остову сети (I, D, G) соответствует ба­зис задачи (3.15)-(3.17) и наоборот.

Пусть имеется некоторый поток Х={х _d } _{d ∊ D} . Рассмотрим множество дуг D(X) = {d ∊D | 0 < x_d < r_d }. Опорой потока Х назы­вается частичный граф (I , D(X), G ). Говорят, что поток Х не­вырожден , если его опора (7, D(X), G) является остовом сети (I, D, G ). Иными словами, используя терминологию транспорт­ной задачи, в невырожденном потоке, которому отвечает допу­стимый базисный план задачи, дороги, по которым осуществля­ются перевозки груза, не достигающие по объему ограничения на пропускную способность, образуют остов (связанную под­сеть без циклов) рассматриваемой транспортной сети.

Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой постановке.

1°. Предполагается, что в начале очередной итерации q имеется некоторый допустимый невырожденный поток Х={х _d ^{(q )} } _{d ∊ D} (о методах его генерации на начальном этапе бу­дет сказано в дальнейшем).

По имеющемуся потоку Х ^{(q )} строится система потенциалов пунктов сети. Для этого выбирается произвольный пунктi ₀ , потенциал которого полагаетсяv_{i 0} =0. Множество вершин, смежных с i ₀ , обозначим через I (i ₀ ). Тогда для любой вершины j ∊ I (i ₀ ) потенциалы рассчитываются по правилу

если (i ₀ ,j )∊D (X ^{(q )} ) (дуга направлена от i ₀ ),и

если (j ,i ₀ )∊G (D (X ^{(q )} )) (j ,i ₀ )∊D (X ^{(q )} ) (дуга направлена кi ₀ ).

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

Имея полную систему потенциалов, для всех дуг следует про­верить условия критерия оптимальности (3.19)-(3.21). Если они выполняются, то текущий поток Х ^{(q )} — оптимальный и, следовательно, алгоритм завершен; в противном случае — пе­реходим к построению следующего «улучшенного» потока.

2°. По аналогии с другими методами последовательного улуч­шения плана очередной поток получается за счет «ввода» в него одной дуги и «вывода» другой. Если условия критерия опти­мальности нарушаются сразу для нескольких дуг, то для ввода имеет смысл выбрать ту, на которой достигается максимальное отклонение цены от разности потенциалов соединяемых вер­шин. Пусть для ввода выбрана некоторая дугаd_l = (s, t ), направ­ленная из вершины s в вершину t . Из правил построения по­тенциалов следует, что в остове существуют две цепи, одна из которых соединяет базовую вершину i ₀ , потенциал которой был принят равным нулю, с s , а другая — i ₀ с t. Если дополнить остов дугойd_l , образуется единственный цикл. Построенныйцикл является аналогом цепочки преобразования плана в мето­де потенциалов для транспортной задачи в матричной постанов­ке. Обозначим черезD⁺ _{(s,t )} множество дуг данного цикла, ориен­тация которых совпадает с ориентацией дугиd_l = (s, t ), а через D^- _{(s,t )} — множество дуг, имеющих противоположную ориента­цию. Определим величину возможной корректировки объемов грузоперевозок, «перемещаемых» по циклу

Идея формулы (3.24) достаточно прозрачна: при циклическом преобразовании текущего потока увеличиваются объемы гру­зоперевозок на тех дугах, которые сонаправлены вводимой дуге, и уменьшаются на дугах, имеющих обратную ориентацию. Соответственно, при добавлении мы должны следить за тем, чтобы не превысить ограничения на пропускные способности (θ ≤ r _d –х _d ^{(q )} ), а при вычитании — за неотрицательностью х _d ^{(q )} . После определения θ происходит пересчет компонент текуще­го потока по формуле

В результате мы получаем новый допустимый поток х _d ^{(q +1)} ), полагаем номер текущей итерацииq +1 и переходим к п. 1°.

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

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

1. К множеству вершин сети добавляется фиктивная нулевая вершина с нулевой интенсивностью (b ₀ = 0).

2. Все вершины, имеющие отрицательную интенсивность (спрос) b_i < 0, соединяются с добавленной вершиной 0 входя­щими дугами (0, i ), а вершины, обладающие положительной интенсивностью (запасом) b_i >0, — исходящими дугами (i ,0). Ограничения на пропускные способности для добавляемых дуг отсутствуют.

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

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

3.2.3. Задача о кратчайшем пути. Классическим приме­ром сетевых задач является определение кратчайшего пути между вершинами сети. Пусть задан граф (I , D, G ), каждой дуге которого поставлено в соответствие число c_d , называемое дли­ной . Также пусть выделены две вершины графаs иt , и требует­ся найти путь наименьшей длины, ведущий из вершины s в вер­шину t.

Если в графе имеются «кратные» дуги, соединяющие одина­ковые начало и конец, то достаточно оставить одну — с наи­меньшей длиной, а остальные отбросить. Таким образом, доста­точно рассматривать задачу о кратчайшем пути для простогографа (I , D ), в котором дуги определяются упорядоченными па­рами вершинd = (i ,j ). Тогда естественно путьL , идущий из вер­шины s в вершину t , задавать в виде упорядоченного набора вер­шин, через которые проходит данный путь:

а длины дуг обозначать как c_d = c_i,j .

Длина описанного выше произвольного пути L определяет­ся по формуле

Легко заметить, что задача о кратчайшем пути является част­ным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого до­статочно присвоить вершине s единичный запас, вершине t еди­ничную потребность, все остальные вершины положить нейт­ральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и ре­шение ее специальными (частными) методами. К их числу отно­сится, например, метод Минти, основные идеи которого мы изложим ниже.

Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путьL=(s=i ₀ , i ₁ , ..., i_{p- 1} , i_p =t).

На предварительном (нулевом) этапе алгоритма:

- формируется массив значений так называемых модифициро­ванных длин _i,j , которые перед началом первой итерации полагаются равными с _i,j ≥0;

- осуществляется отметка вершиныi ₀ = s числом m_{i 0} =0.

Стандартная итерация включает этапы:

1°. Отметка вершин сети . Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как (на первой итерации ={i ₀ }). Для каждой вершиныi ∊ ищутся дуги, со­единяющие ее с еще не помеченными вершинами-потомками j , модифицированная длина которых _i,j = 0. Найденные таким способом вершины j помечаются числом m_j =i , указывающим на «родителя». В том случае, когда сразу несколько дуг, имею­щих _i,j = 0, заканчиваются в одной и той же вершине j , значе­ние для ее пометки выбирается произвольно.

Если среди вновь помеченных вершин окажется вершинаt , то, значит, найден искомый путь (i ₀ , i ₁ ,..., i _{(p- 1)} , i_p ), где

на чем алгоритм завершается.

В случае, если вершины t нет среди отмеченных, и одновре­менно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

2°. Преобразование значений модифицированных длин дуг . Для каждой вершиныi ∊ ищутся дуги, соединяющие ее с еще не помеченными вершинами j , и находятся

Далее модифицированные длины всех дуг, которые соединя­ют отмеченные вершины с неотмеченными (i ∊ ,j ∉ ), умень­шаются на величину

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

Затем происходит переход к следующей итерации.

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

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

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

Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рис. 3.5.

На предварительном этапе вершина 1 отмечается числом m ₁ = 0, а модифицированные длины совпадают с заданными дли­нами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем ∆ = min{ _1,2 , _1,3 }=2 и вычитаем ее из _1,2 , _1,3 . После преобразования имеем _1,2 = 0, _1,3 = 1.

Итерация 2. Помечаем вершину 2 m ₂ = 1 (см. рис. 3.6 ). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются верши­ны 3,4,5. Из чего определяем ∆ = min{ _1,3 , _2,3 , _2,4 , _2,5 }=1 ипосле соответствующего преобразования имеем

Итерация 3 . В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m ₃ = 1 (рис. 3.7 ). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются вершины 4,5. Из чего определяем ∆ = min{ _2,4 , _2,5 , _3,4 , _3,5 }=1 и после пре­образования имеем _2,4 =8, _2,5 =0, _3,4 =3, _3,5 =5.

Итерация 4. Помечаем вершину 4 m ₄ =2 (см. рис. 3. 8 ). Даль­нейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются верши­ны 5,6. Из чего определяем ∆ = min{ _2,5 , _3,5 , _4,5 , _4,6 }=3 и после преобразования имеем _2,5 =5, _3,5 =0, _4,5 =0, _4,6 =5.

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4. Руководствуясь теми же сообра­жениями, что и на итерации 3, пометим вершину 5 числом m ₅ =3 (рис. 3.9 ). Дальнейшая пометка невозможна, поэтому перехо­дим к этапу 2. Смежной с ранее отмеченными вершинами являет­ся вершина 6. Из чего определяем ∆ = min{ _4,6 , _5,6 }=2 и после преобразования имеем _4,6 =3, _5,6 =0.

Итерация 6. В вершину 6 ведет дуга нулевой длины из вер­шины 5, поэтому помечаем ее числом m ₆ =5 (см. рис. 3.10 ). По­скольку мы отметили конечную вершину маршрута, то алго­ритм завершен и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6).

Следует также добавить, что если бы наш выбор на итераци­ях 3 и 5 был иным, то мы получили бы альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет не­сколько решений.

КЛЮЧЕВЫЕ ПОНЯТИЯ

- Транспортная таблица

- Метод северо-западного угла.

- Потенциал.

- Цепочка преобразования плана.

- Граф (ориентированный и неориентированный).

- Ребра и вершины.

- Путь и контур.

- Цепь и цикл.

- Связность.

- Дерево.

- Частичный граф.

- Транспортная сеть.

- Поток.

- Линейная сетевая задача.

- Остов сети.

- Опора потока.

- Невырожденный поток.

- Задача о кратчайшем пути.

- Алгоритм Минти.

КОНТРОЛЬНЫЕ ВОПРОСЫ

3.1. Какие специфические свойства позволяют выделить транспортные задачи в отдельный класс из

множества за­дач линейного программирования?

3.2. Опишите метод построения допустимого плана транспор­тной задачи.

3.3. Сколько ненулевых элементов должен содержать невы­рожденный базисный план транспортной

задачи?

3.4. Сформулируйте критерий оптимальности для допустимо­го плана транспортной задачи.

3.5. Что положено в основу метода потенциалов?

3.6. Из чего вытекает критерий оптимальности допустимого плана транспортной задачи?

3.7. Перечислите основные этапы метода потенциалов.

3.8. Какие условия должны быть соблюдены при построении цепочки преобразования плана в методе

потенциалов?

3.9. Что следует делать при возникновении ситуации вырож­денности текущего плана в транспортной

задаче?

3.10. Приведите формулировку линейной сетевой задачи.

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

транспортной задачи в сетевой постановке.

3.12. Дайте определение понятия «остов сети». Какая связь су­ществует между остовом сети и

базисом транспортной за­дачи в сетевой постановке?

3.13. Какой поток называют невырожденным?

3.14. Перечислите основные этапы метода потенциалов для транспортной задачи в сетевой

постановке.

3.15. Каким способом можно получить допустимый поток в транспортной сети?

3.16. В чем состоит задача о кратчайшем пути?

3.17. Перечислите основные этапы метода Минти.

ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

4.1.1. Основные понятия. Многие экономические задачи ха­рактеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуа­ций приводит к моделям дискретного программирования. В об­щем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или мини­мума) целевой функцииf (x ₁ , x ₂ ,...,x_n ) на множествеD , опреде­ляемом системой ограничений

где Ω— некоторое конечное, или счетное*, множество. Ус­ловие х ∊Ω. называется условием дискретности. Особое место среди дискретных задач занимает целочисленная за­дача линейного программирования в канонической форме (ЦКЗЛП):

* Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.

где Z ⁺ ={0; 1; 2; ...} — множество неотрицательных целых чи­сел.

Заметим, что в некоторых ситуациях требование «целочисленности» может быть наложено лишь на некоторые перемен­ныеx_j , что кардинально не меняет характера задачи.

Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным ана­логом и, найдя соответствующее решение, округлить его ком­поненты до ближайших целых значений. Пример, показанный на рис. 4.1 , демонстрирует, что при округлении оптимального плана х * обычной задачи ЛП до целых значений получается точ­ка ([х ₁ *],[x ₂ ^* ]), не принадлежащая области допустимых планов задачи D . Условимся целую часть числа х _j . обозначать [х _j ], а дробную — как {х _j }. Тогда х _j =[х _j ]+{х _j }. Отдельно следует до­бавить, что если даже оптимальный план непрерывной задачи,округленный до целых значений компонент, окажется допусти­мым, то целевая функция может вести себя так, что ее значение будет на нем существенно «хуже», чем на оптимальном плане целочисленной задачи.

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

- задачи с неделимостями;

- экстремальные комбинаторные задачи;

- задачи с разрывными целевыми функциями;

- задачи на несвязных и невыпуклых областях и др.

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

Классическим представителем задач данного класса стала так называемая задача о ранце . Ее фабула носит достаточно услов­ный характер и состоит в том, что солдат (или турист), собираю­щийся в поход, может нести груз весом не болееW кг. Этот груз может состоять из набора предметов n типов, каждый предмет типа j веситw_j кг и характеризуется некоторой «полезностью» u_j , j ∊ 1: n . В рамках описанной ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно положить в ранец, чтобы его суммарная полезность была макси­мальной? Если в качестве компонент плана х _j . принять количе­ство укладываемых предметов типа j , то данную задачу можно записать:

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

4.1.3. Комбинаторные задачи. К данному классу относят­ся задачи оптимизации функции, заданной на конечном множе­стве, элементами которого служат выборки из n объектов.

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

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

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

элементы которой определяются следующим образом:

1, если в маршруте предусмотрен переезд из пунктаi в j ,

x_i,j = 0, если в маршруте не предусмотрен переезд из пункта i в j ,

причем по условию задачи x_ii =0, i ∊1: n .

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

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

С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования:

Условия (4.8) и (4.9) с содержательной точки зрения означа­ют, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера (4.6)-(4.10) не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы:

гдеD — множество перестановок чисел от 1 до n .

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

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

где с _i,j — по-прежнему издержки на перевозку единицы груза;

d_i,j — фиксированная доплата за аренду транспортныхсредств.

При таких предпосылках целевая функция суммарных затрат на перевозку

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

то целевая функция примет вид

Действительно, если у _i,j =0 , то переменные х _i,j =0, а при у _i,j =1 неравенства (4.15) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следова­тельно, задача (4.16) эквивалентна исходной задаче (4.13). В силу характера ограничений (4.14)-(4.15) задача (4.16) яв­ляется задачей частично-целочисленного программирования.

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

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

4.2. МЕТОД ГОМОРИ

4.2.1. Основные идеи и принципы *. Данный метод, кото­рый также носит название метода отсекающих плоскостей , предназначен для решения ЦЗЛП в канонической форме (4.2)-(4.3). Кратко представим его основные идеи.

* Впервые был предложен Р.Гомори в 1957-1958 гг.

Отправной точкой для решения задачи (4.2)-(4.3) является решение ее непрерывного аналога, т. е. КЗЛП без учета условий целочисленности. Если получаемый в результате оптимальный план х * содержит только целые компоненты, то мы автомати­чески получаем и соответствующее решение ЦЗЛП. В против­ном случае к системе ограничений задачи должно быть добавле­но такое ограничение, для которого:

- найденный нецелочисленный оптимальный план х * не удов­летворяет вновь добавляемому ограничению;

- любой допустимый целочисленный план непрерывной задачи (4.2)-(4.3) удовлетворяет вновь добавляемому ограниче­нию.

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

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

Теперь необходимо несколько более подробно остановиться на принципах формирования отсекающих ограничений. Вос­пользуемся системой обозначений, применявшихся при изло­жении вычислительных методов линейного программирования. Пусть β^{(q )} — оптимальный базис, полученный на последней итерации решения нецелочисленной ЗЛП. Если обозначить через α_i,j и ά_i коэффициенты матрицы задачи и вектора ограниче­ний в текущем базисе (A (β^{(q )} ) и b (β^{(q )} ))

то i -ое уравнение в системе ограничений задачи примет вид:

Так как план x (β^{(q )} ) является базисным, то в каждом уравнении все коэффициенты α_i,j , соответствующие базисным столбцам (j ∊N (β^{(q )} )), равны нулю за исключением некоторого α_i,ji =1, на основе чего из (4.18) получаем:

Если представить каждый коэффициент α_i,j в виде суммы це­лой и дробной частей α_i,j =[α_i,j ]+{α_i,j }, то получим

или

Из (4.21) следует, что если все х _j ,j ∊1: n являются целыми, то целым будет и выражение

стоящее в левой части(4.21), и, стало быть, правая часть данно­го уравнения:

также должна быть целой. Предположим, что

тогда, в силу того, что 0 ≤ {ά_i } < 1, а {α_i,j } ≥ 0, x_j ≥ 0, должно вы­полняться неравенство

Однако неравенства (4.22) и (4.23) противоречат требуемой целочисленности правой части (4.21)x_j (β^{(q )} ). Следовательно, для целочисленных решений должно выполняться условие, проти­воположное неравенству (4.22), или, что то же самое,

В то же время (4.24) не выполняется для любого нецелочислен­ного базисного плана х . Действительно, небазисные компонен­ты плана равны нулю: х _j =0 , j ∊N (β^{(q )} ), и (4.24) приобретает вид {ά_i } ≤0 <=> {ά_i }=0, но это противоречит предположению о нецелочисленности плана х , т. к. в базисном плане х _i = ά_i . Все сказанное позволяет утверждать, что ограничение (4.24) задает правильное отсечение.

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

гдеx_{n +1} ≥0 — фиктивная переменная, добавляемая для преоб­разования неравенства в строгое равенство. Ей соответствует нулевой коэффициент в целевой функции.

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

Индексi соответствует выбранной для формирования отсе­чения строке симплекс-таблицы, содержащей нецелочисленное значение b_i (β^{(q )} ).

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

совместно с добавленным столбцом

образуют сопряженный (двойственно допустимый) базис для сформированной задачи, а (ά₁ , ..., ά_m ,-{ά_i }) являются ненуле­выми компонентами соответствующего псевдоплана. Исходя из этого, приходим к тому, что для решения вновь получен­ной задачи может быть эффективно применена процедура двойственного симплекс-метода (см. параграф 1.7).

Поскольку в начальном псевдоплане имеется только одна от­рицательная компонента (-{ά_i }), то из базиса должен быть вы­веден соответствующий ей вектор а ^{n +1} . Далее, следуя рекомен­дациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то опи­санные действия итеративно повторяются.

Если в ходе решения дополнительная переменная х _{n +1} вновь становится базисной, ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвеча­ющие ей, вычеркивают. С геометрической точки зрения это можно обосновать так: если псевдоплан оказывается внутри полупространства х _{n +1} ≥0, то дополнительное ограничение, оп­ределяемое гиперплоскостью х _{n +1} =0, становится несущест­венным и опускается.

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

1. Решение «текущей» задачи методами линейного програм­мирования (малые итерации). На первой итерации в качестве «текущей» задачи выступает нецелочисленный аналог исходной ЦЗЛП.

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

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

Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнитель­ные ограничения (правильные отсечения) и переходить от те­кущего псевдоплана к новому оптимальному плану.

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

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

4.2.3. Пример решения ЦЗЛП методом Гомори. Рас­смотрим особенности применения метода Гомори на конкрет­ном примере. Пусть дана задача со следующими условиями:

Итерация 1. Используя обычный симплекс-алгоритм, реша­ем непрерывный аналог исходной задачи, в котором игнориру­ются условия целочисленности (4.28). В качестве исходного базиса можно взять первый и второй столбцы. На его основе заполняется таблица T ^(1,1) (первый индекс в обозначении табли­цы соответствует «большой» итерации, а второй — «малой»).

Как видно из строки оценок, данный базис является опти­мальным, однако соответствующий ему план х ={11/5,17/5, 0)не является целочисленным, поэтому выбираем из таблицы T ^(1,1) строку, содержащую первый нецелый элемент, и согласно формуле (4.25) строим отсекающее ограничение:

после чего переходим к следующей «большой» итерации.

Итерация 2. С учетом сформированного отсекающего ог­раничения заполняем симплекс-таблицу T ^(2,1) .

В соответствии с алгоритмом двойственного симплекс-мето­да переходим к следующему базису N (β^(2,2) )={1, 2, 3}.

План, достигнутый в таблицеT ^(2,2) , является не только опти­мальным (b (β^(2,2) )>0), но и полностью состоит из целочислен­ных компонент, т. е. решение задачи найдено: х *=(1, 2,1) и f(x)= 7.

4.3. МЕТОД ВЕТВЕЙ И ГРАНИЦ

4.3.1. Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного програм­мирования методом является метод ветвей и границ . Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг иДойг, а его «второе рождение» произошло в 1963г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].

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

Пусть стоит задача:

гдеD — конечное множество.

Алгоритм является итеративным, и на каждой итерации про­исходит работа с некоторым подмножеством множества D . На­зовем это подмножество текущим и будем обозначать его как D ^{(q )} , гдеq — индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D ⁽¹⁾ =D ),и для него некоторым способом вычисляется значе­ние верхней оценки для целевой функции maxf(x) ≤ ξ( D ⁽¹⁾ ). Стандартная итерация алгоритма состоит из следующих этапов:

1°. Если можно указать планx ^{(q )} ∊D ^{(q )} , для которого f(x ^{(q )} ) ≤ξ( D ^{(q )} ), то x ^{(q )} =х* — решение задачи (4.29).

2°. Если такой план не найден, то область определенияD ^{(q )} некоторым образом разбивается на подмножества D ₁ ^{(q )} ,D ₂ ^{(q )} , ..., D_lq ^{(q )} , удовлетворяющие условиям:

Для каждого подмножества находятся оценки сверху (вер­хние границы) для целевой функции ξD ₁ ^{(q )} ,ξD ₂ ^{(q )} , ..., ξD_{l 1} ^{(q )} , уточняющие ранее полученную оценку ξD ^{(q )} , то есть ξD_i ^{(q )} ≤ ξD ^{(q )} , i ∊1:l_q . Возможно одно из двух:

2.1. Если существует такой план х ^{(q )} , что

то этот план оптимальный.

2.2. Если такой план не найден, то выбирается одно из мно­жеств D_i ^{(q )} ,i ∊1:l_q (как правило, имеющее наибольшую оценку

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются какD ₁ ^{(q +1)} ,D ₂ ^{(q +1)} ,...,D_{l (q +1)} ^{(q +1)} ,после чего процесс повторяется.

Схема дробления множества D представлена на рис. 4.3 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.

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

4.3.2. Решение ЦЗЛП методом ветвей и границ. Рас­смотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, черезD ^{(q )} обозначается подмножество множества допустимых планов за­дачи. Перед началом первой итерации (q = 1) в качестве теку­щего множества берется все множество D (D ⁽¹⁾ = D ), после чего решается стандартная задача линейного программирования (D ⁽¹⁾ , f ). Нетрудно заметить, что она является непрерывным аналогом

исходной задачи (4.2)-(4.3). Если найденный оптималь­ный план ⁽¹⁾ содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3): ⁽¹⁾ =x * . В противном случае значениеf ( ⁽¹⁾ ) становится оценкой (верх­ней границей) значения целевой функции на множестве D ⁽¹⁾ , и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.

1) Выбирается некоторая нецелочисленная компонента пла­на _k ^{(q )} . Поскольку в оптимальном плане она должна быть це­лой, то можно наложить ограничения x_k ≤[_k ^{(q )} ] и x_k ≥[_k ^{(q )} ]+1. Таким образом,D ^{(q )} разбивается на подмножества

Графическая интерпретация такого разбиения множестваD ^{(q )} приведена на рис. 4.4.

2) Решаются задачи линейного программирования

Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:

Если оптимальный план для одной из решенных задач удов­летворяет условию

и содержит только целые компоненты, то, значит, найдено ре­шение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств , полученных как на предыду­щих (D_i ^{(q )} ), так и на текущем (D ₁ ^{(q )} , D ₂ ^{(q )} ) этапе, выбирается об­ласть с наибольшей оценкой ξ(D_i ^{(q )} ). Она становится текущим рассматриваемым подмножеством (D ^{(q +1)} ). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D ₁ ^{(q )} , f ) и (D ₂ ^{(q )} , f ) можно воспользовать­ся результатами решения предыдущей задачи (D ^{(q )} ,f ). Рас­смотрим вариант организации вычислительного процесса на примере задачи ( ₁ ^{(q )} , f ) (для ( ₂ ^{(q )} , f ) он выглядит аналогично с точностью до знаков неравенств).

Предположим, что на последнем шаге решения задачи (D ^{(q )} , f ) был получен оптимальный базис β. Без ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное предположение делается исключитель­но для обеспечения наглядности дальнейшего изложения и оче­видно, что его выполнения можно всегда добиться за счет про­стой перенумерации векторов а ^j . По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D ^{(q )} , f ) и ее вектора ограничений относительно базиса :

Тогда система ограничений задачи (D ^{(q )} , f ) может быть пред­ставлена как

а получаемая на ее основе система ограничений задачи ( ₁ ^{(q )} , f ) как

или

где х _{n +1} ≥ 0 — фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для пре­образования неравенства в строгое равенство.

Очевидно, что 1≤k≤m , т. к. небазисные компоненты опти­мального плана (m +1≤j≤n ) равны нулю, т. е. являются заведо­мо целочисленными. Тогда с учетом сделанных предположений о виде базиса можно записать:

Как видно из (4.39), в k -м столбце имеется всего два отлич­ных от нуля элемента: в k -й и (m +1)-й строках. Если вычесть из (m +1)-го уравненияk -e, то, учитывая, что [ά_k ] – ά_k =-{ά_k }, по­лучим эквивалентную систему:

Проведенные преобразования системы ограниченийD ₁ ^{(q )} по­зволили явно выделить сопряженный базис, образуемый столб­цами с номерами 1,..., m , n +1, и соответствующий ему псевдо­план (ά₁ , ..., ά_m , 0,....,0, -{ά_k }), т.е. для решения задачи (D ₁ ^{(q )} , f ) может быть применен алгоритм двойственного симплекс-мето­да. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.

Для случая задачи (D ₂ ^{(q )} , f ) преобразование симплекс-табли­цы, получаемое на базе аналогичных рассуждений, приведено на рис. 4.6.

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

Подчеркнем, что приведенная реализация метода ветвей и границ является одной из многих . Помимо нее, например, очень популярна версия метода решения задачи коммивояжера, в которой для ветвления и построения оценок используют специфические свойства данной модели. При желании о ней мож­но прочесть в[1, 14].

КЛЮЧЕВЫЕ ПОНЯТИЯ

- Задачи с неделимостями.

- Экстремальные комбинаторные задачи.

- Задачи с разрывными целевыми функциями.

- Правильное отсечение.

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

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

4.1. Какие основные проблемы возникают при решении дис­кретных задач?

4.2. Сформулируйте задачу о ранце.

4.3. Какие экономико-математические модели могут быть све­дены к задаче о коммивояжере?

4.4. Приведите пример моделей с разрывными целевыми функ­циями.

4.5. Какой принцип используется для построения правильно­го отсечения в методе Гомори?

4.6. Перечислите основные этапы, входящие в «большую» итерацию метода Гомори.

4.7. Какую роль играет алгоритм двойственного симплекс-ме­тода при решении целочисленной

линейной задачи мето­дом Гомори?

4.8. Перечислите принципиальные идеи, лежащие в основе ме­тодов ветвей и границ.

4.9. Как производится построение отсечения при решении це­лочисленной линейной задачи методом

ветвей и границ?

4.10. Опишите схему решения целочисленной задачи линейно­го программирования методом ветвей и

границ.

4.11. За счет каких преобразований удается построить сопря­женный базис при добавлении

отсекающего ограничения?

ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

5.1. ОБЩАЯ СХЕМА МЕТОДОВ

ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

* Динамическое программирование как научное направление возник­ло и сформировалось в 1951-1953 гг. благодаря работам Р. Беллмана и его сотрудников.

Обычно методами динамического программирования опти­мизируют работу некоторых управляемых систем , эффект ко­торой оценивается аддитивной , или мультипликативной , целевой функцией. Аддитивной называется такая функция не­скольких переменных f (х ₁ ,x ₂ ,...,х _n ), значение которой вычис­ляется как сумма некоторых функцийf_j , зависящих только от одной переменной х _j :

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

Поскольку логарифм функции типа (5.2) является аддитив­ной функцией, достаточно ограничиться рассмотрением функций вида (5.1).

Изложим сущность вычислительного метода динамическо­го программирования на примере задачи оптимизации

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

Отметим, что в отличие от задач, рассмотренных в преды­дущих главах, о линейности и дифференцируемости функций f_j (x_j ) не делается никаких предположений, поэтому примене­ние классических методов оптимизации (например, метода Лагранжа) для решения задачи (5.3)-(5.4) либо проблематично, либо просто невозможно.

Содержательно задача (5.3)-(5.4) может быть интерпрети­рована как проблема оптимального вложения некоторых ресур­сов j , приводимых к единой размерности (например, денег) с помощью коэффициентов a_j , в различные активы (инвестици­онные проекты, предприятия и т. п.), характеризующиеся фун­кциями прибылиf_j , т. е. такого распределения ограниченного объема ресурса (b ), которое максимизирует суммарную прибыль. Представим ситуацию, когда она решается последова­тельно для каждого актива. Если на первом шаге принято реше­ние о вложении в n -й актив x_n единиц, то на остальных шагах мы сможем распределить b-a_n x_n единиц ресурса. Абстрагируясь от соображений, на основе которых принималось решение на первом шаге (допустим, мы по каким-либо причинам не могли на него повлиять), будет вполне естественным поступить так, чтобы на оставшихся шагах распределение текущего объе­ма ресурса произошло оптимально , что равнозначно реше­нию задачи

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

Очевидно, что максимальное значение (5.5) зависит от размера распределяемого остатка, и если оставшееся количество ресур­са обозначить через ξ, то величину (5.5) можно выразить как функцию от ξ:

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

Если бы имелась возможность влиять наx_n , то мы для получе­ния максимальной прибыли должны были бы максимизировать Ω_n по переменной x_n , т. е. найти Λ_n (b ) и фактически решить задачу:

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

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

Если в выражении (5.9) заменить значения b на ξ, и п наk , то его можно рассматривать как рекуррентную формулу , позво­ляющую последовательно вычислять оптимальные значения це­левой функции при распределении объема ресурса ξ за k шагов:

Значение переменной x_k , при котором достигается рассмат­риваемый максимум, обозначим _k (ξ).

При k = 1 формула (5.11) принимает вид

т. е. допускает непосредственное вычисление функций Λ₁ (ξ) и ₁ (ξ).

Воспользовавшись (5.12) как базой рекурсии, можно с помо­щью (5.11) последовательно вычислить Λ_k (ξ) и _k (ξ),k ∊2:n . Положив на последнем шаге ξ =b , в силу (5.9), найдем глобаль­ный максимум функции (5.3), равный Λ_n (b ), и компоненту опти­мального плана х _n * = _n (b ). Полученная компонента позволяет вычислить нераспределенный остаток на следующем шаге приоптимальном планировании: ξ= b –а _n х* _n , и, в свою очередь, най­ти х *_{n- 1} =_{n- 1} (ξ_{n- 1} ). В результате подобных вычислений последо­вательно будут найдены все компоненты оптимального плана.

Таким образом, динамическое программирование представ­ляет собой целенаправленный перебор вариантов, который при­водит к нахождению глобального максимума. Уравнение (5.11), выражающее оптимальное решение наk -м шаге через решения, принятые на предыдущих шагах, называется основным рекур­рентным соотношением динамического программирова­ния . В то же время следует заметить, что описанная схема решения при столь общей постановке задачи имеет чисто тео­ретическое значение, так как замыкает вычислительный про­цесс на построение функций Λ_k (ξ) (k ∊1:n ), т. е. сводит исход­ную задачу (5.3)—(5.4) к другой весьма сложной проблеме. Однако при определенных условиях применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это относится к задачам, которые допускают таблич­ное задание функций Λ_k (ξ).

5.1.2. Задачи динамического программирования, до­пускающие табличное задание рекуррентных соотноше­ний. Рассмотрим процесс решения модифицированного вариан­та задачи (5.3)-(5.4), в котором переменные х _j и параметры a_j , b могут принимать только целочисленные значения, а ограничение (5.4) имеет вид равенства. В рамках предложенной в п. 5.1.1 ин­терпретации о вложении средств в активы данные предпосылки вполне реалистичны и, более того, могут быть даже усилены тре­бованием о кратности значений х _j , например, 1000 единицам.

Чтобы не усложнять обозначения, условимся операции це­лочисленной арифметики записывать стандартным образом, по­лагая, что промежуточные результаты подвергаются правиль­ному округлению. Так, например, будем считать, что 12/5=2.

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

Поскольку ξ≤b ,x ₁ принимает конечное число целых значений от 0 до b /a ₁ . Это позволяет, например, путем перебора значе­ний f ₁ (x ₁ ) найти функцию Λ₁ (ξ) и задать ее в форме таблицы следующей структуры (табл. 5.1).

Последняя колонка табл. 5.1 ( ₁ (ξ)) содержит значениеx ₁ , на котором достигается оптимальное решение первого шага. Его необходимо запоминать для того, чтобы к последнему шагу иметь значения всех компонент оптимального плана.

На следующем (втором) шаге можно приступить к вычисле­нию функции Λ₂ (ξ), значения которой для каждого отдельно взятого ξ∊ 0: b находятся как

где значения

берутся из табл. 5.1. В результате вычислений формируется таблица значенийΛ₂ (ξ), содержащая на одну колонку больше по сравнению с табл. 5.1, так как теперь необходимо запомнить оптимальные решения первого ( ₁ (ξ)) и второго шагов ( ₂ (ξ)).

На последующих шагах с номеромk (k ∊2:(n-l)) осущест­вляются аналогичные действия, результатом которых стано­вятся таблицы значений Λ_k (ξ), где ξ ∊{0, 1,..., b } (см. табл. 5.2).

На последнем n -ом шаге нет необходимости табулиро­вать функцию Λ_n (ξ), так как достаточно определить лишь Λ_n (b )=f (_n (b )). Одновременно определяется и оптимальное значение n -й компоненты оптимального плана x*_n =_n (b ). Далее, используя таблицу, сформированную на предыдущем шаге, определяем оптимальные значения остальных перемен­ных:

и т. д. или, в общем виде,

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

Выигрыш, который дает применение рассмотренного алго­ритма, может также быть оценен с помощью следующего про­стого примера. Сравним приблизительно по числу операций (состоящих, в основном, из вычислений целевой функции) опи­санный метод с прямым перебором допустимых планов задачи (5.3)-(5.4) при а ₁ =a ₂ = ...а _n =1.

Количество допустимых планов такой задачи совпадает с ко­личеством целочисленных решений уравнения

т. е. равно числу сочетаний с повторениями из n элементов по b . Следовательно, при простом переборе число возможных вари­антов составит

В случае применения метода динамического программирова­ния для вычисления таблицы значений функции Λ_k (ξ) при фик­сированном ξ необходимо выполнить (ξ+1) операций. Поэто­му для заполнения одной таблицы необходимо проделать

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

операций, что при больших n и b существенно меньше, чем в первом случае. Например, если п = 6 и b = 30, то непосредствен­ный перебор потребует выполнения 324 632 операций, а метод динамического программирования — только 2511.

5.1.3. Принцип оптимальности Беллмана. Еще раз под­черкнем, что смысл подхода, реализуемого в динамическом программировании, заключен в замене решения исходной мно­гомерной задачи последовательностью задач меньшей раз­мерности.

Перечислим основные требования к задачам, выполнение ко­торых позволяет применить данный подход:

- объектом исследования должна служить управляемая сис­тема (объект) с заданными допустимыми состояниями и допустимыми управлениями ;

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

- задача не должна зависеть от количества шагов и быть опре­деленной на каждом из них;

- состояние системы на каждом шаге должно описываться оди­наковым (по составу) набором параметров;

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

Рассмотрим вопросы применения модели динамического про­граммирования в обобщенном виде. Пусть стоит задача управ­ления некоторым абстрактным объектом , который может пре­бывать в различных состояниях . Текущее состояние объекта отождествляется с некоторым набором параметров, обознача­емым в дальнейшем ξ и именуемый вектором состояния . Пред­полагается, что задано множество Ξ всех возможных состоя­ний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X , которое, не умаляя общности, можно считать числовым множеством. Управляю­щие воздействия могут осуществляться в дискретные моменты времениk (k ∊1:n ), причем управленческое решение заключа­ется в выборе одного из управлений x_k ∊Х . Планом задачи или стратегией управления называется вектор х =(х ₁ , х ₂ , .., x_{n -1} ), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последователь­ными состояниями объекта ξ_k и ξ_{k +1} существует известная функциональная зависимость, включающая также выбранное управление:ξ_{k +1} = φ_k (x_k , ξ_k ),k ∊1:п -1. Тем самым задание на­чального состояния объекта ξ₁ ∊Ξ и выбор плана х однозначно определяют траекторию поведения объекта, как это показа­но на рис. 5. 1.

Эффективность управления на каждом шаге k зависит от текущего состояния ξ_k , выбранного управления x_k и количе­ственно оценивается с помощью функций f_k (х _k , ξ_k ), являющих­ся слагаемыми аддитивной целевой функции , характеризую­щей общую эффективность управления объектом. (Отметим, что в определение функции f_k (х _k , ξ_k ) включается область до­пустимых значений х _k , и эта область, как правило, зависит от текущего состояния ξ_k .) Оптимальное управление , при задан­ном начальном состоянии ξ₁ , сводится к выбору такого опти­мального плана х * , при котором достигается максимум суммы значений f_k на соответствующей траектории.

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

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

Обозначим Λ_k (ξ) максимальное значение суммы функций f_k на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии ξ . Тогда функции Λ_k (ξ) должны удовлетворять рекуррентному соотношению:

где ξ_{k +1} = φ_k (x_k , ξ)

Соотношение (5.14) называют основным рекуррентным со­отношением динамического программирования. Оно реализу­ет базовый принцип динамического программирования, извест­ный также как принцип оптимальности Беллмана :

- Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было

начальное состо­яние ξ_k на k-м шаге и выбранное на этом шаге управле­ние х _k ,, последующие управления (управленческие реше­ния) должны быть оптимальными по отношению к состоянию ξ_{k +1} = φ_k (x_k , ξ_k ), получающемуся в результа­те решения, принятого на шаге k.

Основное соотношение (5.14) позволяет найти функции Λ_k (ξ) только в сочетании с начальным условием , каковым в нашем случае является равенство

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

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

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения зада­чи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспре­деленным ресурсом ξ . При наличии нескольких ограничений со­стояние управляемого объекта на каждом шаге характеризуется уже набором параметров ξ₁ , ξ₂ ,..., ξ_m , и табулировать значения функций Λ_k (ξ₁ , ξ₂ ,..., ξ_m ) необходимо для многократно больше­го количества точек. Последнее обстоятельство делает приме­нение метода динамического программирования явно нерацио­нальным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информа­цию о них можно найти в специальной литературе [4, 5].

5.2. ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Одним из важнейших классов задач, для которых примене­ние динамического программирования оказывается плодотвор­ным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные х ₁ ,x ₂ , ..,х _k ,... должны определяться в строгой временной по­следовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о найме работников (задачу об использовании рабочей силы).

В данной задаче рассматривается некоторый экономиче­ский объект (фирма, магазин, завод и т. п.), функционирую­щий в течение конечного числа периодов, обозначаемых но­мерамиk (k ∊ l:n ). Каждый периодk характеризуется нормативной потребностью в определенном количестве одно­типных работников m_k . Тот же объем работ может быть вы­полнен другим количеством сотрудников ξ_k , что, однако, влечет дополнительные затраты либо за счет нерационально­го использования рабочей силы, либо ввиду повышения опла­ты за интенсивный труд. Размеры этих дополнительных издер­жек описываются функциямиg_k (ξ_k - m_k ), где (ξ_k - m_k ) — отклонение фактической численности работающих ξ_k , от пла­ново необходимой m_k , причемg_k (0)=0. Управленческое ре­шение на шаге k заключается в выборе величины изменения числа сотрудников х _k ∊Z , что однозначно определяет количе­ство работающих в течение следующего периода: ξ_{k +1} =ξ_k +х _k . Затраты по изменению количества работников (найму и уволь­нению) при переходе от периода k к периоду (k +1) задаются функцией u_k (х _k ) , где также u_k (0)=0. Тогда суммарные издер­жки, вызванные принятым на шаге k решением, характеризу­ются значением функции

План задачи (стратегия управления) х = (x ₁ , ..., х _{n -1} , 0) за­ключается в выборе поэтапных изменений количества работни­ков, а его суммарная эффективность описывается аддитивной функцией