краткий курс
МАТЕМАТИЧЕСКИЕ МЕТОДЫИССЛЕДОВАНИЯ ОПЕРАЦИЙВ ЭКОНОМИКЕ
П. Конюховский
УЧЕБНОЕ ПОСОБИЕ
Санкт-Петербург
Москва • Харьков • Минск
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, задается следующей таблицей.
Название |
Доходность (в%) |
Срок выкупа (год) |
Надежность (в баллах) |
А
|
5,5
|
2001
|
5
|
В
|
6,0
|
2005
|
4
|
С
|
8,0
|
2010
|
2
|
D
|
7,5
|
2002
|
3
|
Е
|
5,5
|
2000
|
5
|
F
|
7,0
|
2003
|
4
|
Предположим, что при принятии решения о приобретении активов должны быть соблюдены условия:
a) суммарный объем капитала, который должен быть вложен, составляет $ 100 000;
b) доля средств, вложенная в один объект, не может превышать четверти от всего объема;
c) более половины всех средств должны быть вложены в долгосрочные активы (допустим, на рассматриваемый момент к таковым относятся активы со сроком погашения после 2004 г.);
d) доля активов, имеющих надежность менее чем 4 балла, не может превышать трети от суммарного объема.
Приступим к составлению экономико-математической модели для данной ситуации. Целесообразно начать процесс с определения структуры управляемых переменных. В рассматриваемом примере в качестве таких переменных выступают объемы средств, вложенные в активы той или иной фирмы. Обозначим их как хА
, х
В
, х
C
, х
D
,
хЕ
,
х
F
. Тогда суммарная прибыль от размещенных активов, которую получит инвестор, может быть представлена в виде
На следующем этапе моделирования мы должны формально описать перечисленные выше ограничения a-d на структуру портфеля.
a) Ограничение на суммарный объем активов:
х
A
+ х
B
+ х
C
+ х
D
+ х
E
+ х
F
≤ 100 000. (2)
b) Ограничение на размер доли каждого актива:
х
A
≤ 25 000, xB
≤ 25 000,xC
≤ 25 000,
xD
≤ 25 000,xE
≤ 25 000,xF
≤ 25 000. (3)
c) Ограничение, связанное с необходимостью вкладывать половину средств в долгосрочные активы:
xB
+ xC
≥50 000. (4)
d) Ограничение на долю ненадежных активов:
х
C
+ х
D
≤ 30 000. (5)
Наконец, система ограничений в соответствии с экономическим смыслом задачи должна быть дополнена условиями неотрицательности для искомых переменных:
х
A
≥ 0, х
B
≥ 0, хС
≥ 0, х
D
≥ 0, х
E
≥ 0, х
F
≥ 0. (6)
Выражения (1)-(6) образуют математическую модель поведения инвестора. В рамках этой модели может быть поставлена задача поиска таких значений переменных х
A
, xB
, xC
, xD
, xE
, xF
, при которых достигается наибольшее значение прибыли (т. е. функции (1)) и одновременно выполняются ограничения на структуру портфеля активов (2)-(6).
Перейдем теперь к рассмотрению более общих моделей и задач.
Простейшая задача производственного планирования
. Пусть имеется некоторый экономический объект (предприятие, цех, артель и т. п.), который может производить некоторую продукцию n
видов. В процессе производства допустимо использование m
видов ресурсов (сырья). Применяемые технологии характеризуются нормами затрат единицы сырья на единицу производимого продукта. Обозначим через а
i,j
количество i
-го ресурса(i
Î
1:
m
), которое тратится на производство единицы j
-го продукта (j
Î
1:n). Весь набор технологических затрат в производстве j-го продукта можно представить в виде вектора-столбца
а технологию рассматриваемого предприятия (объекта) в виде прямоугольной матpицы pазмеpности m
на n
:
Если j
-й продукт производится в количестве xj
, то в рамках описанных выше технологий мы должны потратить a
1,j
xj
первого ресурса,a
2,j
xj
— второго, и так далее, am,j
xj
- m
-го. Сводный план производства
по всем продуктам может быть представлен в виде n
-мерного вектора-строки х = (х
1
, х
2
,...,х
j
,...,х
n
).
Тогда общие затраты по i
-му ресурсу на производство всех продуктов можно выразить в виде суммы
представляющей собой скалярное произведение векторов а
j
и х.
Очевидно, что всякая реальная производственная система имеет ограничения на ресурсы, которые она тратит в процессе производства. В рамках излагаемой модели эти ограничения порождаются m
-мерным вектором b
=
(b1
,
b2
,...,
bm
),
где bi
— максимальное количествоi
-гo продукта, которое можно потратить впроизводственном процессе. В математической форме данные ограничения представляются в виде системы m
неравенств:
Применяя правила матричной алгебры, систему (7) можно записать в краткой форме, представив левую часть как произведение матрицы А
на вектор х
, а правую — как вектор b
:
К системе (8) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства: х
1
≥0,..., х
j
≥0, .... х
n
≥0, или, что то же самое,
Обозначив через с
j
цену единицы j
-го продукта, получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором х:
Формулы (8)-(10) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого экономического объекта, поведением которого мы хотим управлять. В рамках данной модели, вообще говоря, можно поставить различные задачи, но, скорее всего, самой «естественной» будет задача поиска такого плана производства х
Î
Rn
,
который дает наибольшее значение суммарного дохода, т. е. функции (10), и одновременно удовлетворяет системе ограничений (8)-(9). Кратко такую задачу можно записать в следующем виде:
Несмотря на явную условность рассматриваемой ситуации и кажущуюся простоту задачи (11), ее решение является далеконе тривиальным и во многом стало практически возможным только после разработки специального математического аппарата. Существенным достоинством используемых здесь методов решения является их универсальность, поскольку к модели (11) могут быть сведены очень многие как экономические, так и неэкономические проблемы.
Поскольку любая научная модель содержит упрощающие предпосылки, для корректного применения полученных с ее помощью результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее «сильным» упрощением в рассмотренной модели является предположение о прямо пропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат а
i,j
.
Очевидно, что это допущение далеко не всегда выполняется. Так, объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно в зависимости от изменения компонентов объема производства х
. К другим упрощающим предпосылкам относятся предположения о независимости цен с
j
от объемов х
j
, что справедливо лишь для определенных пределов их изменения, пренебрежение эффектом кооперации в технологиях и т. п. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления совершенствования модели.
Транспортная задача
. Рассмотрим проблему организации перевозки некоторого продукта между пунктами его производства, количество которых равно m
,
и n
пунктами потребления. Каждый i
-й пункт производства (i
Î
1:m
) характеризуется запасом продукта аi
≥ 0, а каждый j-и пункт потребления (j
Î
1: n
) — потребностью в продукте bj
≥ 0. Сеть дорог, соединяющая систему рассматриваемых пунктов, моделируется с помощью матрицы С размерности m
на n
, элементы которой с
i,j
представляют собой нормы затрат на перевозку единицы груза из пункта производстваi
в пункт потребления j
.
План перевозки груза в данной транспортной сети представляется в виде массива элементов размерности m
х n
:
х = (
x
1,1
…
x
1,n
, x2,1
….,x2,n
,… , xi,1
, …, xi,n
,…, xm,1
,…,xm,n
).
(12)
В (12) план перевозок х
может рассматриваться как вектор, распадающийся на m
групп, по n элементов в каждой, причем i
-я группа соответствует объемам груза, вывозимым из j
-го пункта производства во все возможные пункты потребления. Если реальная перевозка между пунктами i
и j
отсутствует, то полагают х
i,j
= 0.
Ограничения на возможные значения х
Î
Rmn
имеют вид:
1. Ограничение на удовлетворение потребностей во всех пунктах потребления:
2. Ограничения на возможности вывоза запасов из всех пунктов производства:
3. Условия неотрицательности компонентов вектора плана:
х, х
i,j
≥ 0,i
Î
l : m,
j
Î
l : n.
(15)
Существенной характеристикой описываемой модели является соотношение параметров а
i
и bj
.
Если суммарный объем производства равен суммарному объему потребления, аименно,
то система называется сбалансированной.
При выполнении условия сбалансированности разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т. е. условия (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
Ì
Rn
, где х
Î
D
удовлетворяют системе ограничений
и, возможно, ограничениям
х
1
≥0,х
2
≥0,..., х
j
≥0,...,х
n
≥0. (1.3)
* Напомним, что частные примеры, сводящиеся к задаче линейного программирования, были описаны во введении.
Не умаляя общности, можно считать, что в системе (1.2) первые m
ограничений являются неравенствами, а последующие —l
-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности
(или тривиальными ограничениями).
Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относительный характер. Так, задача поиска максимума функции
эквивалентна задаче поиска минимума функции
Часто условия задачи (1.1)-(1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме
f(x)
= сх
→ max, Ax
≤
b
, х
≥ 0, (1.6)
где с
их
— векторы из пространстваRn
,
b
— вектор из пространстваRm
, а А
— матрица размерности m
х n
.
Задачу линейного программирования, записанную в форме (1.1)-(1.3), называют общей задачей линейного программирования
(ОЗЛП).
Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные х
j
наложены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования
(КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:
Поскольку любая оптимизационная задача однозначно определяется целевой функцией f
и областьюD
, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D
, f
).
Условимся относительно терминологии, которая используется в дальнейшем и является общепринятой в теории линейного программирования.
Планом
ЗЛП называется всякий вектор х
из пространства Rn
.
Допустимым планом
называется такой план ЗЛП, который удовлетворяет ограничениям (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
,
(xj
≥
0,
хj
≥
0).
Проиллюстрируем применение описанных выше рекомендаций на примере. Пусть задана задача линейного программирования(D, f)
в общей форме с целевой функцией
f(x)
= 5х
1
+ 3x
2
+ x
3
+ 2х
4
-2х
5
→ max
и множеством допустимых планов D
, определенным системой уравнений и неравенств,
2х
1
|
+ 4х
2
|
+ 5x
3
|
=7, |
- 3x
2
|
+ 4x
3
|
– 5x
4
– 4x
5
|
≤ 2, |
3х
1
|
- 5x
3
|
+ 6x
4
– 2x
5
|
≤ 4, |
х
1
≥ 0, |
x
3
|
≥ 0. |
Тогда в соответствии со сформулированными правилами эквивалентная каноническая задача будет иметь вид (D',f'
), где:
а множество D'
определено как:
Нетрудно заметить, что «платой» за переход от общей формы задачи линейного программирования к канонической является рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения.
1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ
1.2.1. Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования
. Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как линейного, так и нелинейного программирования.
Фундаментальным понятием линейной алгебры является линейное (вещественное) пространство
. Под ним подразумевается множество некоторых элементов (именуемых векторами
или точками
), для которых заданы операции сложения и умножения на вещественное число (скаляр), причем элементы, являющиеся результатом выполнения операций, также в соответствии с определением должны принадлежать исходному пространству.
Частными случаями линейных пространств являются вещественная прямая, плоскость, геометрическое трехмерное пространство.
Вектор λ1
a
1
+ λ2
a
2
+ …+ λm
a
m
называется линейной комбинацией
векторов а
1
а
2
,..., а
m
с коэффициентами λ1
, λ2,
λm
,
Система векторов линейного пространства а
1
а
2
,..., а
m
называется линейно зависимой
, если существуют такие числа λ1
, λ2,
λm
не равные одновременно нулю, что их линейная комбинация λ1
a1
+ λ2
a2
+ …+ λm
am
равняется нулевому вектору (вектору, все компоненты которого равны нулю). В противном случае систему а
1
,а
2
,..., а
m
называют линейно независимой
, т. е. линейная комбинация данных векторов может быть равна нулевому вектору только при нулевых коэффициентах λ1
, λ2,
…, λm
Максимально возможное количество векторов, которые могут образовывать линейно независимую систему в данном линейном пространстве, называют размерностью пространства
, а любую систему линейно независимых векторов в количестве, равном размерности, — базисом пространства
.
Линейное пространство обычно обозначают какRn
, где n
— его размерность.
Любое подмножество данного линейного пространства, которое само обладает свойствами линейного пространства, называется линейным подпространством.
Множество Н
, получаемое сдвигом некоторого линейного подпространстваL
Ì
Rn
на векторa
Î
Rn
: H=L+a
, называется аффинным множеством
(пространством). Если фундаментальным свойством любого линейного пространства или подпространства является принадлежность ему нулевого вектора, то для аффинного множества это не всегда так. На плоскости примером подпространства является прямая, проходящая через начало координат, а аффинного множества — любая прямая на плоскости. Характеристическим свойством аффинного множества является принадлежность ему любой прямой, соединяющей две любые его точки. Размерность аффинного множества совпадает с размерностью того линейного подпространства, сдвигом которого оно получено.
Если рассматривается некоторое линейное пространствоRn
, то принадлежащие ему аффинные множества размерности 1 называются прямыми,
а размерности (n
-1)—гиперплоскостями
. Так, обычная плоскость является гиперплоскостью для трехмерного геометрического пространства R3
, а прямая — гиперплоскостью для плоскости R
2
. Всякая гиперплоскость делит линейное пространство на два полупространства.
Множество V векторов (точек) линейного пространства R
n
называется выпуклым,
если оно содержит отрезок прямой, соединяющей две его любые точки, или, другими словами, из того, чтоa
Î
V
и b
Î
V
, следует, что х
= (1- λ) х а+
λ
хb
ÎV
, где 0 ≤λ≤ 1.
Линейная комбинация
векторов а
1
,а
2
... а
m
называется выпуклой
, если λi
≥0, iÎ1:m
и
Множество, содержащее все возможные выпуклые комбинации точек некоторого множества М
, называют выпуклой оболочкой
данного множества. Можно показать, что выпуклая оболочка множества М
является наименьшим выпуклым множеством, содержащим М
.
Выпуклая оболочка конечного множества точек называется выпуклым многогранником
, а непустое пересечение конечного числа замкнутых полупространств — многогранным выпуклым множеством
. В отличие от выпуклого многогранника последнее может быть неограниченным.
Точкаv
выпуклого множества V
называется его угловой (крайней)
точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V
. Угловые точки выпуклого многогранника являются его вершинами,
а сам он — выпуклой оболочкой
своих вершин.
Множество К
называется конусом
с вершиной в точкеx0
, еслиx
0
ÎК
, и из того, что некоторая точка х
принадлежит К ( х
Î К
), следует, что в К
содержится и луч, начинающийсяв х0
и проходящий через х
, т. е.
или
Выпуклая оболочка конечного множества лучей, исходящих из одной точки, называется многогранным выпуклым конусом
с вершиной в данной точке.
1.2.2. Первая геометрическая интерпретация ЗЛП и графический метод решения
. Рассмотрим следующий пример. Пусть дана задача максимизации линейной целевой функции
f(x)
= 3х
1
+ х
2
→ max
на множестве
Так как количество переменных в неравенствах, задающих область допустимых планов задачи, равно двум, то ее можно изобразить на координатной плоскости (см. рис. 1.1
).
На рис. 1.1
показано, что каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каждого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x)
= 3х
1
+ х
2
в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.
Напомним, что линией уровня функции
называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение. Градиентом
функцииf(x)
называется вектор
Δf(x) = df
,…, df
dx
1
dxn
указывающий направление наиболее быстрого возрастания функции, и, стало быть, ориентированный перпендикулярно линиям уровня.
Для линейной функции двух переменных линия уровня представляет собой прямую, перпендикулярную вектору с
, который служит градиентом данной функции. Следовательно, если линия уровня определяется уравнениемf(x)=c1
x1
+ c2
x2
=const
, то этот вектоp имеет вид
и указывает направление возрастания функции.
Таким образом, с геометрической точки зрения задача максимизации сводится к определению такой точки области D
, через которую проходит линия уровня, соответствующая наибольшему из возможных значений. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной вектору с
) до тех пор, пока не достигнем такой точки области допустимых планов D
, из которой смещение в направлении вектора с
было бы невозможно. Такой метод решения получил название графического
. Заметим, что решение задачи поиска минимума линейной функции осуществляется аналогично, с той лишь разницей, что движение по линиям уровня должно производиться в направлении, обратном градиенту целевой функции, т. е. по вектору (-с
).
На рис. 1.1
изображен некоторый частный случай, для которого решение ЗЛП достигается в угловой точке х*
= (0, 6) области D
. Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.
Рисунок (а
) иллюстрирует ситуацию неограниченности целевой функцииf(x)=cx
на множестве D
, т.е. сколько бы мы ни перемещались по линиям уровня в направлении вектора с
, ее значение будет возрастать.
В случае, изображенном на рисунке (b
), линия уровня, соответствующая максимальному значениюf(x),
касается грани множестваD
, и, соответственно, все точки, лежащие на этой грани, являются оптимальными планами.
Во всех рассмотренных иллюстрациях допустимые планы ЗЛП представлялись в виде некоторого многогранного выпуклого множества на плоскости. Такое их представление в литературе получило название первой геометрической интерпретации задачи линейного программирования
.
Заметим также, что аналогичным образом могут быть построены интерпретации ЗЛП для случая трехмерного пространстваR
3
, где множеству D
будет соответствовать некоторый ограниченный или неограниченный многогранник, а поведение целевой функции будет характеризоваться поверхностями (плоскостями) уровня.
Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается полезным. В частности, он может быть применен не только к задачам с двумя переменными и ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых n
-
m
= 2, где n
— количество переменных, а m
— ранг матрицы А
.
Действительно, можно выбрать две произвольные переменные х
j1
,xj2
и, используя систему уравнений, выразить через них остальные переменные
где φj
(xj
1
, xj
2
) —линейные функции.
Подставив выражения (1.9) в целевую функцию, мы получим эквивалентную задачу
при ограничениях
Последняя ЗЛП может быть решена графически.
1.2.3. Основные теоремы линейного программирования
. Рассмотрим некоторые теоремы. Отражающие фундаментальные свойства задач линейного программирования и лежащие в основе методов их решения. Они по существу обобщают на случай задач с произвольным количеством переменных те свойства, которые мы наблюдали в двумерном случае.
Теорема 1.1
. Если целевая функция
f
принимает максимальное значение в некоторой точке множества допустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.
Доказательство.
Чтобы не усложнять изложение, ограничимся тем случаем, когда множество D
ограничено, и, следовательно, является выпуклым многогранником.
Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых множеств:
Если D — замкнутое ограниченное выпуклое множество, имеющее конечное число угловых точек, то любая точка х
Î
D может быть представлена в виде выпуклой комбинации угловых точек D
*
.
|
* Строгое доказательство данного утверждения см., например, в [14].
Пусть х
1
, х
2
,…,х
m
— угловые точки множестваD
, а х*
— точка, в которой целевая функция f
достигает максимума.
На основе сформулированного выше утверждения точку х*
можно представить в виде выпуклой комбинации угловых точек х
1
, х
2
,..., xm
Так как х*
— точка максимума, то для любого х
Î
D
сх
* ≥
сх
. Функцияf(x)
— линейная, поэтому
cледовательно,
где xr
— угловая точка, удовлетворяющая условию
Из (1.10) видно, что сх* ≤
сх
r
.В то же время справедливо обратное неравенство: сх*
≥
сх
r
. Откуда следует, что сх* = сх
r
, т. е. существует по крайней мере одна угловая точках
r
, в которой целевая функция принимает максимальное значение. -
Теорема 1.2
. Если целевая функция
f
принимает максимальное значение в нескольких точках множества D, то она принимает это же значение в любой точке, являющейся их выпуклой комбинацией.
|
Доказательство.
Пусть максимальное значение функции f
достигается в точках х̃
1
, х̃
2
,...,x̃s
, т. е. сх
~i
=f*,
i
Î
l:s.
Рассмотрим произвольную выпуклую комбинацию этих точек
Найдем значение целевой функции в точке х*
Итак, для произвольной выпуклой комбинации х*
точек х̃1
, х̃
2
,...,x~s
справедливо равенство
1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ
ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП
1.3.1. Векторная форма записи КЗЛП и ее применение
. Рассмотрим каноническую задачу линейного программирования
Обозначим через а
j
столбцы матрицы А
и будем рассматривать их как векторы пространстваRm
.
Тогда каждому допустимому плану КЗЛП — n
-мерному вектору х
— соответствует неотрицательная линейная комбинация столбцов а
j
, равная столбцуb
Î
Rm
:
Такое представление ограничений КЗЛП обычно называют векторной формой записи.
Векторы а
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
являются линейно независимыми, то они образуют базис в пространстве Rm
, и их, вообще говоря, будет достаточно для представления вектора b
в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации окажутся неотрицательными, то мы получаем так называемый базисный допустимый план х
, у которого не более m
компонентов отличны от нуля. Сформулируем определение базисного плана более строго, так как это одно из фундаментальных понятий теории линейного пpогpаммиpования.
-Пусть задана некоторая каноническая ЗЛП
(D,f),
А —матрица системы ограничений задачи, и β= {а
j
1
, аj2,..., аj
m
} —линейно независимая система столбцов матрицы А, образующая базис
Rm
.
Обозначим множество номеров столбцов, входящих в систему
b
, через
N
(
β
)
= {
j
1
,
j2
,...,
jm
}. План х называется
базисным планом задачи
(D,f),
если его компоненты, соответствующие базисным столбцам и называемые базисными компонентами, больше или равны нулю (хj
≥
0,
j
Î
N
(
β
)},
а все остальные компоненты
(небазисные) — равны
нулю
(
xj
=
0,
j
Ï
N (
β)).
-Базисный план х называется
невырожденным, если все его базисные компоненты строго
положительны, и
вырожденным в противном случае.
1.3.2. Свойства базисных планов
. Следующая теорема трактует понятие базисного плана в терминах первой геометрической интерпретации ЗЛП.
Теорема 1.3.
Каждый допустимый базисный план является угловой точкой множества допустимых планов D.
|
Доказательство.
Ради простоты положим, что базисными векторами являются первые m
столбцов матрицы A
, т. е. β={a
l
,a
2
,...,am
}. Тогда утверждение теоремы 1.3 может быть переформулировано следующим образом:
Если существует такой
n
-мерный вектор
что
x
1
a
1
+х
2
а
2
+...+x
k
ak
=b
, то х есть угловая точка множества D.
Проведем доказательство от противного, т. е. предположим, что рассматриваемый базисный план х
не является угловой точкой множества D
. Тогда ее можно представить в виде выпуклойкомбинации некоторых двух различных допустимых планов х
1
и х
2
:
x
= λx
1
+(1-λ)x
2
, 0<λ<1.
В координатной форме последнее утверждение означает
Поскольку последние (n
-
k
) компоненты вектора х
по предположению равны 0, а числа х
j
1
,xj
2
≥ 0 и λ, (1 -λ )>0, то эти же компоненты в векторах x
1
и х
2
также равны 0. Поэтому, с учетом допустимости планов х
1
и х
2
, можно утверждать, что
Вычитая из (1.15) (1.16), получим
Так как векторы а
1
,а
2
,...,а
k
— линейно независимы, то коэффициенты х
1
1
–х
2
1
=0,..., х
1
k
–х
2
k
=0, из чего следует, что x
1
=х
2
. Это противоречит предположению, что х
1
и х
2
являются различными угловыми точками множестваD
. Следовательно, х
не может быть представлен в виде выпуклой комбинации двух точек D
и по определению является угловой точкой данного множества. -
Интересно отметить, что справедливо и обратное утверждение, которое приведем без доказательства:
Если х — угловая точка множества D, то она является допустимым базисным планом задачи
(D, f).
В завершение параграфа необходимо отметить практическое значение установленной связи между угловыми точками и допустимыми базисными решениями: она позволяет формализовать (и тем самым существенно упростить) процесс перехода от одной угловой точки к другой.
1.4. СИМПЛЕКС-МЕТОД
1.4.1. Основные этапы симплекс-метода
. Исходя из свойств линейных экстремальных задач, рассмотренных в предыдущих параграфах, можно заключить, что на принципиальном уровне поиск их решений сводится к последовательному перебору угловых точек множества допустимых планов или, что то же самое, перебору соответствующих допустимых базисных планов. Следует подчеркнуть, что такой перебор для реальных многомерных задач возможен только в теоретическом плане и на практике неосуществим (или крайне неэффективен) даже при условии использованиямощной вычислительной техники. Средством решения данной проблемы явились прикладные оптимизационные методы, основанные на последовательном, целенаправленном переборе базисных планов ЗЛП.
Классическим методом решения ЗЛП стал симплекс-метод
, получивший также в литературе название метода последовательного улучшения плана
, разработанный в 1947г. американским математиком Джорджем Данцигом.
Идея такого перехода от одного базисного плана к другому, при котором происходит «улучшение» значения целевой функции, может быть продемонстрирована для случая m
= 2 с помощью рис. 1.4.
Если вектор ограничений b принадлежит конусу, натянутому на некоторые два базисных вектора условий {аj
1
,аj
2
}, то существует такой базисный план х
с базисными компонентами х
j1
,
х
j2
,
чтоb=
х
j1
aj1
+ х
j2
aj2
. Разумеется, таких планов может быть несколько в зависимости от выбора системы базисных векторов. Чтобы различать их по соответствующей величине целевой функцииf(x)=cj
1
xj
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
выделен конус, натянутый на систему расширенных столбцов ā
2
и ā
3
, отвечающих текущему допустимому базису. Нетрудно заметить, что данный базис не является оптимальным, например, для базиса {а3
, а4
} точка пересечения соответствующего конуса и прямой будет находиться выше. Можно, наоборот, указать базис с «худшим» значением целевой функции: {а
1
а2
}. Наконец, рассматриваемая геометрическая интерпретация КЗЛП иллюстрирует и общую идею критерия, который используется в симплекс-методе для определения оптимальности (или неоптимальности) текущего плана: если существуют векторы-столбцы, лежащие выше плоскости,
проходящей через векторы текущего базиса, то он не является оптимальным и может быть «улучшен».
С вычислительной точки зрения критерий оптимальности в симплекс-методе реализуется через нахождение специальных оценок для небазисных векторов-столбцов, относительно текущего базиса.
Для удобства дальнейшего изложения введем некоторые обозначения. Учитывая то, что симплекс-метод представляет собой некоторый итеративный вычислительный процесс, то черезq
будем обозначать номер очередной (текущей) итерации. Соответственно, набор базисных столбцов, получаемых на q
-й итерации, будет обозначаться как β
(
q
)
:
Для того чтобы было легче отличить номер итерации от номеров компонентов матриц и векторов, он заключен в круглые скобки. Номера столбцов, входящих в базис, обозначим через N
(β(q)
), а именно
При этом Nr
(β(q)
) =jr
— номер столбца, занимающего 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
0
(β(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
векторы {а
2
,а
3
} образуют допустимый базис, а векторы {а
3
,a
4
} —недопустимый, т. к. разложение b
по а
3
и а
4
содержит один отрицательный компонент плана, что противоречит условиям КЗЛП.
Можно доказать, что допустимость базиса, к которому осуществляется переход, обеспечивается следующим правилом вывода столбца из текущего базиса:
-для столбца
l
, претендующего на ввод в базис, и вектора ограничений
b
рассматриваются
отношения
и определяется такая строка
r
, что
Полученный индекс
r
определяет номер столбца в
N
(β(q
)
), выводимого из базиса, а именно
, N
(β(q
)
).
Таким образом, если базис на q
-й итерации включал столбцы с номерами
то базис на итерацииq
+ 1 будет состоять из столбцов с номерами:
Отдельно следует обсудить тот случай, когда столбец al
(β(q
)
), претендующий на ввод в базис, не содержит положительных компонентовal
(β(q
)
) ≤ 0). Это означает, что целевая функция в задаче не ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения. Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального плана.
Геометрически ситуация, когда al
(β(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
)
) привести ее столбец, соответствующий вводимому в базис вектору, к «базисному» виду.
Для это применяется преобразование Жордана—Гаусса
(так называемый метод полного исключения). В данном случае оно состоит в том, что мы должны «заработать» единицу на месте элемента ar,l
(β(q
)
) (он обычно называется ведущим
)* и нули на месте остальных элементов столбца al
(β(q
)
). Первое достигается посредством деления r
-й строки на ведущий элемент, второе — путем прибавления вновь полученной r
-й строки, умноженной на подходящий коэффициент, к остальным строкам матрицы A
(β(q
)
).
* Напомним, что l
— номер столбца, вводимого в базис, а r
— номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.
Формально результат выполнения данного преобразования над элементами A
(β(q
)
) и b
(β(q
)
) может быть выражен в следующем виде
Следует особо отметить смысл элементов вектора b
(β(q
)
). Его нулевой компонент b
0
(β(q
)
) в соответствии с построением содержит значение целевой функции
, достигаемое ею на текущем плане
а остальные элементы — ненулевые компоненты этого плана:
Название метода произошло от понятия симплекса. Напомним, что m
-симплексом
называют выпуклый многогранник, аффинная оболочка* которого есть аффинное множество размерности m
. В данном случае можно считать, что система расширенных базисных столбцов {а
j
1
,а
j
2
,..., а
jm
}, рассматриваемых как точки в Rm
+1
, порождает (m
-1)-мерный симплекс в пространствеRm
+1
.
*Аффинной оболочкой
множества называют наименьшее аффинное множество, в котором содержится данное множество.
В заключение настоящего пункта обобщим изложенные вопросы и приведем схему алгоритма симплекс-метода для решения задачи максимизации.
Она включает однократно выполняемый 0-этап и повторяемый конечное число раз I-этап (стандартную итерацию).
0-этап. Нахождение допустимого базисного плана
(см. п. 1.4.5). Результатом 0-этапа является допустимый базисный план х
(β(1)
), а также соответствующие ему матрица A
(β(1)
) и вектор b
(β(1)
), которые будут использованы на первой итерации. Полагаем номер текущей итерацииq
равным 1 и переходим к I-этапу.
I
-этап. Стандартная итерация алгоритма
— выполняется для очередного базисного плана x
(β(q
)
).
1°. Проверка оптимальности
текущего базисного плана:осуществляется просмотр строки оценок а
0
(β(q
)
). Возможны два варианта:
1′. a
0
(β(q
)
)≥0 — план, соответствующий текущему базису задачи, оптимален
. Вычислительный процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х
*
= x
(β(q
)
) и значение целевой функции f
(x
*
)=f
(x
(β(q
)
)).
1″. В строке оценок а
0
(β(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
)
)=jr
для столбца, выводимого из базиса. Переходим к пункту 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
)
. Наконец, в строке а
0
(β(q
)
) находятся текущие оценки столбцов, а ячейка b
0
(β(q
)
) содержит значение целевой функции, достигаемое для текущего плана.
Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное практическое значение нестолько как удобная форма организации ручного счета, сколько как основа для реализации данного алгоритма в рамках программного обеспечения ЭВМ.
1.4.3. Пример решения ЗЛП симплекс-методом
. Рассмотрим на конкретном примере процесс решения КЗЛП табличным симплекс-методом. Пусть дана каноническая задача ЛП:
Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по данным столбцам вектора ограничений с положительными коэффициентами. Последнее означает, что столбцы {5, 2, 3} образуют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых элементов формируется матрица Δ(β(1)
) и обратная по отношению кнейΔ-1
(β(1)
):
Используя их, по формуле (1.26) получаем
-84 |
0 |
0 |
-88 |
0 |
1/3 |
0 |
0 |
1/3 |
1 |
= |
2 |
1 |
0 |
3 |
0 |
; |
-2/3 |
0 |
1 |
-4/3 |
0 |
Используя полученные значения A
(β(1)
) и b
(β(1)
), заполняем симплекс-таблицу T
(1)
, соответствующую первой итерации (q
=1).
Поскольку строка оценок a
0
(β(1)
) в первом и четвертом столбцах содержит отрицательные элементы (a
0,1
(β(1)
) = -84, a
0,4
(β(1)
) = -88), план х
(β(1)
) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f
(x
(β(1)
)) = -226 может быть улучшено. Следуя рекомендации п.1˝ алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l
= 4 (т.к. |-88| > |-84|). Рассматриваем ведущий
столбец (выделен пунктирной рамкой)
Он содержит два положительных элемента. Применяя рекомендацию п. 2" алгоритма, получаем λ1
= 4/(1/3) =12, λ2
=14/3,и, стало быть r
= 2. Следовательно, столбец с номером N
2
(β(1)
) = 2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи N
(β(2)
) = {5, 4, 3}. Элемент a
2,3
(β(1)
) является ведущим (обведен кружком). Применив формулы (1.28)-(1.31), переходим к симплекс-таблице, соответствующей второй итерации T
(2)
, и полагаем индекс текущей итерацииq
= 2.
В ходе выполнения второй итерации опять-таки определяются вводимый столбец а
1
, выводимый а
4
и ведущий элемент a
2,1
(β(2)
). Перейдя к итерации q
= 3, имеем таблицу T
(3)
.
Как видно из T
(3)
, строка оценок содержит только неотрицательные значения, поэтому достигнутый базис N
(β(3)
) = {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отя, в некоторых частных случаях, он может оказаться слишком громоздким.
Идея метода минимизации невязок состоит в построении соответствующей вспомогательной задачи, для которой можно в явном виде указать исходный базисный план, и решении ее с помощью процедуры симплекс-метода.
Не умаляя общности, можно считать, что вектор ограничений в исходной задаче неотрицателен, т. е. bi
≥ 0,i
Î 1: m
. Тогда для КЗЛП максимизации функции
на множестве, определяемом ограничениями
строится вспомогательная задача
Как видно из (1.36)-(1.39), задача (
,
) отличается от задачи (D,
f
) матрицей, получаемой в результате добавления кисходной матрице А
единичной матрицы, которой соответствуют дополнительные (фиктивные) переменные х
n
+1
,...,х
n+m
. Данным переменным (собственно говоря, их и называют невязками
) в целевой функции
отвечают коэффициенты (-1), а переменным х
1
,...,х
n
, которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенностью (
,
) является наличие в ней очевидного исходного базиса, образуемого добавленными столбцами, и соответствующего плана с базисными компонентами хn+i
= bi
≥ 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
0
(β(q
)
) и ведущий столбецal
(β(q
)
). Данные соображения положены в основу вычислительной схемы симплекс-метода, основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом
. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц T
1
и Т
2
(q
)
. Таблица T
1
(рис. 1.7
) является общей для всех итераций и служит для получениястроки оценок текущего базисного плана a
0
(β(q
)
). Если обозначить через δi
(β(q
)
) (i
Î 0 : m
) строки матрицы Δ-1
(β(q
)
), то из (1.26), в частности, следует, что
Как видно из рис. 1.7
, T
1
состоит из трех блоков:
-
в центре содержится матрица
А
;
-
в левом блоке таблицы на каждой итерации дописываются нулевые строки матрицы
Δ-1
(β(q
)
)для текущего базиса
;
- нижний блок, расположенный под матрицей
А
, на каждой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).
Симплекс-таблица Т
2
(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)
) и соответствующие ему матрицу Δ-1
(β(1)
)и вектор b
(β(1)
).
2. Заполняем центральную часть таблицы T
1
, содержащую матрицу А
.
3. Содержимое матрицы Δ-1
(β(1)
)и вектора b
(β(1)
), полученных на этапе поиска допустимого базисного плана, переносится в таблицу T
2
(1)
.
4. Полагаем номер текущей итерацииq
равным 1 и переходим к I-этапу.
1-этап. Стандартная итерация алгоритма
— выполняется для очередного базисного плана x
(β(q
)
).
1°. Проверка оптимальности текущего базисного плана
. Содержимое нулевой строки таблицы T
2
(q
)
— δ0
(β(q
)
) переписывается в соответствующую графу таблицы T
1
. По формуле (1.42) рассчитываем и заполняем строку a
0
(β(q
)
). Осуществляем просмотр строки оценок a
0
(β(q
)
). Возможны два варианта:
1΄. a
0
(β(q
)
)≥0 —план, соответствующий текущему базису задачи, оптимален.
Вычислительный процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х
* =x
(β(q
)
) и оптимальное значение целевой функцииf
(х
*)=f
(x
(β(q
)
)).
1". В строке оценок a
0
(β(q
)
)существует по меньшей мере один элемент a
0,j
(β(q
)
)<0, т. е. имеющий отрицательную оценку. Следовательно, план x
(β(q
)
) —неоптимален
. Выбирается номер l
, соответствующий элементу, имеющему минимальную (максимальную по абсолютной величине) отрицательную оценку:
l
-й столбец матрицы A
становится ведущим
и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма.
2°. Определение столбца, выводимого из базиса
. Переписываем ведущий столбец а
l
из таблицы T
1
в текущую таблицу Т
2
(q
)
. По формуле а
l
(β(q
)
) = Δ-1
(β(q
)
)а
l
заполняем соответствующий столбец в таблицеТ
2
(q
)
. Возможны два варианта:
2'. Для всехi
Î 1: m
а
i,l
(β(q
)
)≤0. Делается вывод о неограниченности целевой функции
и завершается вычислительный процесс.
2". Существует по крайней мере один индексi
Î 1: m
, для которого а
i,l
(β(q
)
)>0. Согласно правилу (1.27) определяются место r
и номерNr
(β(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
1
и Т
2
(1)
не представляет труда.
На первой итерации мы переписываем нулевую строку
из Т
2
(1)
вT
1
и, умножив ее на матрицу A
, получаем строку оценок
Так какa
0
(β(1)
) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β(1)
, и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l
=4.
Переписываем столбец
из таблицы T
1
в Т
2
(1)
и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу Δ-1
(β(q
)
), расположенную в таблице Т
2
(1)
слева, на а
4
.
После заполнения таблицы Т
2
(1)
данными по вводимому в новый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов bi
(β(1)
) и ai,l
(β(1)
) для {i
Î1:m| ai,l
(β(1)
)>0} и определив минимальное из них, находим, что r
=2. Следовательно, столбец с номером N
2
(β(q
)
) =2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с N
(β(2)
) ={5, 4, 3}. Элементa
2,3
(β(1)
) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к симплекс-таблице, соответствующей второй итерации Т
2
(2)
, и полагаем индекс текущей итерацииq
= 2.
Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам Т
2
(2)
и Т
2
(3)
, на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т
2
(3)
. Легко заметить, что в процессе решения мы «прошли» по той же самой последовательности допустимых базисных планов, которая встречалась в п. 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
1
x
1
+ ... +с
j
х
j
+
с
j
+1
х
j+
1
+
...
+с
n
xn →
max,x
ÎD,
(1.50)
где D определяется системой уравнений и неравенств:
то
двойственной
по отношению к ней называется общая задача
ЛП
где D
*
определяется системой уравнений и неравенств:
Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.
Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:
1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.
2. Вектор коэффициентов целевой функции с
и столбец ограничений b
меняются местами.
3. Матрица ограничений задачи A
транспонируется.
4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х
j
≥ 0 или uj
≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (aj
u
≥ с
j
или ai
x
≤ bj
).
5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, ai
x
≤ bj
или aj
u
≥ с
j
)
, определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (ui
≥ 0 или xi
≥ 0).
-Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей
:
Тем самым имеет смысл говорить о паре взаимно двойственных задач.
В матричной форме пара двойственных общих задач линейного программирования может быть кратко записана как:
Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D
,f
):
тогда двойственной к ней будет задача (D*
,f*
):
1.6.3. Теоремы двойственности и их применение
. Фундаментальные свойства, которыми обладают двойственные задачи линейного программирования, могут быть сформулированы в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности
.
Теорема 1.4
. Если х, и— допустимые планы для пары двойственных задач
(D,f
) и (D*,f*
), т
o
f
(x
) ≤ f
(u
). |
Доказательство.
Достаточно доказать теорему для случая, когда задача (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
*), проводятся аналогично. -
Теорема 1.6.
Если целевая функция
f
в задаче
(D, f)
не ограничена сверху, то двойственная к
ней задача (D*,
f
*) не имеет допустимых планов.
|
Доказательство.
Если предположить, что у двойственной задачи (D
*,f
*) существует хотя бы один допустимый план и̃
, то, согласно теореме 1.4, для любого допустимого плана х
задачи (D, f
) справедливо неравенство f
(
x
)
≤ f
*(
)<+∞. Последнее означает, что целевая функция f
задачи (D, f
) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о существовании допустимых планов двойственной задачи (D*,f
*) неверно. -
Следующее утверждение, известное как теорема равновесия
, используется при проверке оптимальности планов ЗЛП.
Теорема 1.7.
Пусть х*
и u* —
оптимальные планы канонической задачи (D, f) и двойственной по отношению к ней задачи
(D*,f*).
Если
j
-я компонента плана х* строго положительна
(xj
*
>0),
то соответствующее
j-e
ограничение двойственной задачи выполняется как равенство: а
1,j
u
1
* +...+а
m,j
um
*
= с
j
; если же
j
-й компонент плана х* имеет нулевое значение (х
j
*
=0), то j-e ограничение двойственной задачи выполняется как неравенство: а
1,j
u
1
* +...+а
m,j
um
*≥
с
j
.
|
Доказательство.
Векторы х*
и и*,
будучи допустимыми планами соответствующих задач, удовлетворяют условиям: Ах* =
b
, х
*
>
0 и и
*
А-с
≥
0
. Найдем скалярное произведение
Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е.
u*b
=сх*.
Последнее означает, что (u*
А-с)х
*
=0 . Однако скалярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные произведения их соответствующих координат равны нулю. Следовательно, еслиxj
*
> 0, то u*
а
j
– с
j
= 0, если жеxj
= 0, то возможно u*
а
j
– с
j
≥ 0 , что и утверждается в теореме. -
Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область допустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (m
= 2, n
= 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая имеет только две переменные.
Еще раз вернемся к таблице Т
2
(q
)
(рис. 1.8
), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ-1
(β(q
)
), для которой было введено обозначение δ0
(β(q
)
). Поэлементно она может быть записана в следующем виде:
Введем вектор
=(δ0,1
(β(q
)
), δ0,2
(β(q
)
),..., δ0,m
(β(q
)
)). Нетрудно проверить, что строка оценок a
0
(β(q
)
) может быть представлена следующим образом:
Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũ
А
≥
с
. Следовательно, вектор и является допустимым планом двойственной задачи.
В то же время элемент b
0
(β(q
)
), содержащий текущее значение целевой функции и равный на последней итерацииf(x*)
,
допускает представление
Согласно теореме 1.5 из равенства f
(х*
)=f
*(ũ
) вытекает, что вектор ũ
служит оптимальным планом двойственной задачи:u
= ũ.
Окончательно можно утверждать, что для оптимального базиса
-Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как, прямой, так и двойственной задачи.
Читателю в качестве самостоятельного упражнения предлагается построить задачу, двойственную к (1.34)-(1.35), решение которой было приведено в п. 1.5.2, и убедиться, что вектор u
= (-10, 32, 2), полученный в таблице Т
2
(3)
, является для нее допустимым и оптимальным планом.
1.6.4. Экономическая интерпретация.
Традиционная экономическая интерпретация двойственной задачи ЛП базируется на модели простейшей задачи производственного планирования
, описанной во введении. Напомним, что в ней каждый (j
-й) элемент вектора х
рассматривается как план выпуска продукции данного вида в натуральных единицах, с
j
— цена единицы продукции j
-го вида, а
j
— вектор, определяющий технологию расходования имеющихся m
ресурсов на производство единицы продукции j
-го вида, b
— вектор ограничений на объемы этих ресурсов.
Предположим, что для некоторых значений A
,
b
и с
найден оптимальный план х
*
, максимизирующий суммарный доход max{cx
}=cx
*. Достаточно естественным представляется вопрос: как будет изменяться оптимальный план х
* при изменении компонент вектора ограничений b
и, в частности, при каких вариациях b
оптимальный план х
* останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана.
Очевидно, что исследование устойчивости х
* имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсовbi
; могут существенно колебаться после принятия планового решения х
*.
Когда вектор ограничений 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
устремить Δbi
→
0, то мы получим
Учитывая, что в соответствии с теоремой 1.5
и подставив (1.57) в (1.56), приходим к выражению
-Из формулы (1.58) вытекает экономическая интерпретация оптимальных переменных двойственной задачи
.
Каждый элемент ui
*
может рассматриваться как предельная (мгновенная) оценка вклада i
-го ресурса в суммарный доход F
при оптимальном решении х
*. Грубо говоря, величина
ui
*
равна приросту дохода, возникающему при увеличении ресурса i на единицу при условии оптимального использования ресурсов.
В различных источниках компоненты оптимального плана двойственной задачи также называются двойственными оценками
или теневыми ценами
, а Л.В.Канторович предлагал такой термин, как объективно обусловленные оценки.
На основе теорем двойственности для пары задач ЛП в общей форме
могут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия.
-Если при использовании оптимального плана прямой задачи
i-e
ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, т.е. если
В рамках рассматриваемой задачи производственного планирования это означает, что если некоторый ресурс bi
, имеется в избыточном количестве (не используется полностью при реализации оптимального плана), то i
-e ограничение становится несущественным и оценка такого ресурса равна 0.
-Если при использовании оптимального плана двойственной задачи
j-e
ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, т. е. если a
1,j
u
1
*
+...а
m,j
и
m
– с
j
> 0, то х
j
*
=
0.
Учитывая экономическое содержание двойственных оценок u
1
*,...,um
, выражение а
1,j
u
1
* +…am,j
um
*
может быть интерпретировано как удельные затраты наj
-й технологический процесс. Следовательно, если эти затраты превышают прибыль от реализации единицы j
-го продукта, то производство j
-го продукта является нерентабельным и не должно присутствовать в оптимальном производственном плане (xj
*
=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
~ {а
1
, а
2
} и т. д.).
-В дальнейшем систему
β={aj
1
, aj
2
,...,ajm
} из т линейно-независимых столбцов матрицы условий прямой задачи А будем называть
сопряженным базисом
, или
двойственно допустимым базисом
, если всякий вектор и
Î Rm
, удовлетворяющий условиям, удовлетворяет также условиям иа
j
≥cj
(j
Î1:n),
т. е. является допустимым планом двойственной задачи
(1.49).
План двойственной задачи и
, соответствующий сопряженному базису β={aj
1
, aj
2
,...,ajm
}, называют опорным планом
. Его «опорность» заключается в том, что в системе ограничений u
а
j
≥ cj
(j
Î1:n
), задающих область определения двойственной задачиD
*, т
неравенств с номерами j
ÎN
(β) обращаются в равенства.
Следует обратить внимание на то, что не всем сопряженным базисам
соответствуют допустимые базисные планы прямой задачи. В частности, вектор b
не может быть разложен с неотрицательными коэффициентами по базисам {а
1
, а
2
}, {а
3
, а
4
} или {а
4
, а
5
}. В связи с этим систему коэффициентов разложения вектора b
по сопряженному базису называют псевдопланом
. В то же время базис {а2
, а3
} является допустимым для прямой задачи, и, более того, из иллюстрации видно, что он, с одной стороны, определяет максимум прямой задачи (наивысшую точку пересечения прямой, проходящей через конец b
, с конусом К
), а с другой — минимум двойственной (низшую точку пересечения этой прямой с лежащей над К
опорной гиперплоскостью):
Последний факт является не чем иным, как геометрической иллюстрацией утверждения теоремы 1.5.
Описанные выше свойства пары двойственных задач линейного программирования являются идейной основой двойственного симплекс-метода, который представляет собой итеративный процесс целенаправленного перебора сопряженных (двойственно допустимых) базисов и соответствующих псевдопланов. В этом и заключено его принципиальное отличие от обычного симплекс-метода, в котором последовательно рассматриваются допустимые базисные планы прямой задачи*. Нетрудно догадаться, что при определенной структуре задачи путь, предлагаемый двойственным алгоритмом, может оказаться более коротким.
* В данном пункте используется та же система обозначений, что и в п. 1.4.1.
-Критерий оптимальности псевдоплана х в двойственном симплекс-методе заключается в том,
что х одновременно должен являться допустимым планом прямой задачи, т. е. все его
компоненты должны быть неотрицательны
(х
j
≥ 0).
Обратно, если хотя бы одна из компонент псевдоплана является отрицательной, то процесс улучшения значения целевой функции может быть продолжен. Геометрическая иллюстрация данной ситуации приведена на рис. 1.13
. Здесь на плоскости (для m
= 2) изображена система столбцов ограничений КЗЛП, из которых {а
1
, а
2
} образуют текущий базис. Как видно из рисунка, вектор ограничений имеет отрицательную координату по направлению, задаваемому вектором а
1
. В то же время очевидны и те базисы (например, {а
2
, а
3
}), в которых b
будет иметь все положительные координаты. Однако это не всегда так. Пример на рис. 1.14
иллюстрирует случай отсутствия допустимых планов у прямой задачи: вектор b
имеет отрицательную компоненту в текущем базисе {а
1
, а
2
} по направлению а
2
, а для всех остальных небазисных столбцов (а
3
, а
4
) данная координата является положительной, т. е. b
и столбцы, являющиеся кандидатами на ввод в очередной базис, лежат в разных полуплоскостях, образуемых прямой, проходящей через вектор а
1
,
и при любых базисах, отличных от текущего, соответствующая координата вектора b
все равно останется отрицательной.
-Таким образом, в двойственном симплекс-методе признаком отсутствия допустимых планов у
решаемой КЗЛП является неотрицательность каких-либо
r
-х компонент во всех столбцах а
j
,
представленных в текущем базисе
β (ar,j
(β) ≥ 0, j
Î1:n
)если
br
(β) < 0 l.*
* Здесь следует подчеркнуть, что двойственный симплекс-метод непосредственно нацелен на нахождение решения прямой задачи.
С другой стороны, если br
(β)<0 и в строке а
r
(β) существуют отрицательные координаты, то псевдоплан можно улучшить выводя из базиса столбец, находящийся на r
-м
месте, и вводя в него некоторый вектор al
, имеющий отрицательную r
-ую
координату. При наличии в векторе b
(β) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно определяется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.
Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис определял опорную плоскость, ниже которой располагаются все небазисные векторы. Для этого требуется, чтобы оценки всех небазисных векторова
0
,j
(β) ( j
ÎN
(β)), вычисляемые по формулам
а
0
,j
(β) = -cj
+
c
(β)а
j
(β)
(см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l
должен быть определен таким образом. Чтобы
После выбора выводимого и вводимого векторов производится обычный пересчет симплекс-таблицы по формулам, аналогичным формулам (1.28)-(1.31), и процесс итеративно повторяется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множества допустимых планов.
1.7.2. Алгоритм и табличная реализация двойственного симплекс-метода
. Обобщая сказанное в предыдущем пункте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.
0-этап. Нахождение исходного сопряженного (двойственно допустимого базиса).
Результатом 0-этапа являются сопряженный базисβ(1)
и соответствующие ему псевдоплан x
(β(1)
), матрица A
(β(1)
) и вектор b
(β(1)
), которые будут использованы на первой итерации. Полагаем номер текущей итерации q
равным 1 и переходим к I-этапу.
I
-этап. Стандартная итерация алгоритма
— выполняется для очередного сопряженного базиса β(q
)
.
1°. Проверка оптимальности
текущего псевдоплана: осуществляется просмотр значений bi
(β(q
)
), i
Î1:m
. Возможны два варианта:
1΄. Для всех i
Î1:m
, bi
(β(q
)
) ≥ 0. Тогда текущий псевдоплан x
(β(q
)
) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным
планом. Вычислительный процесс закончен. Элементы оптимального плана х
* определяются по формуле
а достигаемое на нем значение целевой функции равно
1". Существует по меньшей мере один номер строки r
Î1:m
, для которого br
(β(q
)
)<0 . Следовательно, псевдоплан x
(β(q
)
) — неоптимален.
Выбирается строка с номером r
, такая, что
Она становится ведущей и определяет номер столбца N
r
(β(q
)
), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.
2°. Определение столбца, вводимого в базис.
Рассматривается ведущая строка а
r
(β(q
)
). Возможны два варианта:
2'. Для всех j
Î1:n
а
r,j
(β(q
)
) ≥ 0. Делается вывод об отсутствии допустимых планов у решаемой задачи
(D
= Ø) и завершается вычислительный процесс*.
* Очевидно, что для определения пустоты множества допустимых планов достаточно найти полностью неотрицательную строку а
i
(β(q
)
), соответствующую bi
(β(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
(1)
(за исключением столбца b
(β(1)
)) будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b
(β(1)
) в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации в п. 1.5.2:
В результате имеем:
Как видно из таблицы Т
(1)
, в столбце b
(β(1)
) содержатся отрицательные элементы b
1
(β(1)
) = - 1/3<0), то есть базис β(1)
={
5
,
1
,
3
} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b
(β(1)
) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — r
=1 и N
1
(β(1)
)=5. Далее рассматриваем строку a
1
(β(1)
) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем λ2
=42:(-(-1/6))=252, λ4
=38:(-(-1/6))=228. λ2
> λ4
, следовательно, номер столбца, вводимого в базис — l
=4. Осуществляем преобразование иполучаем симплекс-таблицу T
(2)
.
Поскольку b
(β(2)
)>0, то достигнутый базис N
(β(2)
)={4,1,3} является оптимальным. Из Т
(2)
можно выписать оптимальный план х
* =(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. Какая точка выпуклого множества называется угловой?
|