Лекции Хуторецкий

В этой задаче m ограничений. Среди них есть ограничения-неравенства (5), если m1 > 0, и

ограничения-равенства (6), если m > m1.

Литература

Вентцель Е.С. Исследование операций: задачи, принципы, методология. 2 изд. М.: Нау-

ка, 1988.

Гермейер Ю.Б., Морозов В.В., Сухарев А.Г., Федоров В.В. Задачи по исследованию операций. М.: Изд-во МГУ, 1979 (стр. 4 – 7).

Мур Д., Уэдерфорд Л.Р. и др. Экономическое моделирование в Microsoft Excel. 6 изд.

М.: Издательский дом «Вильямс», 2004 (глава 1).

Розен В.В. Математические модели принятия решений в экономике. М.: Книжный дом

«Университет», Высшая школа, 2002 (лекция 1).

Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении. 2 изд.,

испр. М.: Дело, 2002 (глава 1).

Эйджин Н. Методика проведения исследования операций. В кн.: Исследование опера-

ций. В 2 т. Том 1. Методологические основы и математические методы. М.: Мир, 1981 (раз-

дел 1-2).

2. Линейное программирование (8 ч.)

Если в задаче (4) – (6) функции f и gi для всех i линейны, то она относится к классу за-

дач линейного программирования (ЗЛП), которые хорошо решаются и имеют обширные при-

ложения.

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

Определения. В общем виде ЗЛП записывается следующим образом:

n

f(x) = c j x j max (min) при условиях

(7)

j 1

aij x j = bi, i

;

1, m1

(8)

j

aij x j

bi, i m1

1, m2 ;

(9)

j

aij x j

bi, i m2

1, m ;

(10)

j

xj 0 для j 1, n1 ; xj 0 для j n1 1, n2 ; n2 n.

(11)

11

Матрица A = (aij) размерности m n ― это матрица задачи, вектор x = (x1, …, xn)T ― вектор переменных, b = (b1, …, bm)T ― вектор правых частей ограничений, с = (с1, …, сn) ― вектор коэффициентов ЦФ.

Вектор x Rn является допустимым решением задачи (7) – (11), если он удовлетворяет условиям (8) – (11).

Задача совместна, если множество ее допустимых решений непусто.

Для задачи (7) – (11) с максимизируемой (минимизируемой) ЦФ и множеством допус-

тимых решений X вектор x* X является оптимальным решением, если f(x*) ≥ (≤) f(x) для всех x X.

Задача (7) – (11) с максимизируемой (минимизируемой) ЦФ и множеством допустимых решений X ограниченна, если f(x) ≤ (≥) M для всех x X и некоторого M R.

Задача (7) – (11) разрешима, если множество ее оптимальных решений непусто.

Стандартная форма ЗЛП:

n

f(x) = c j x j max (min)

j 1

при условиях j aij x j ( ) bi для всех i; xj 0 для всех j.

Если задача максимизации записана в стандартной форме, то m1 = m2 = 0 и n1 = n.

Обозначение. 0n — нуль-вектор в Rn.

Используя введенные выше обозначения, можем записать стандартную форму в матричном виде: c,∙x max (min) при условиях A∙x ( ) b, x 0n.

Определение. ЗЛП в канонической форме(1):

n
f(x) = c j x j max (min) при условиях						(12)
j 1
aij x j = bi, i				;
			1, m			(13)
j
xj 0, j 1, n .						(14)
Если ЗЛП записана в канонической форме, то m1 = m и n1 = n.
Матричная запись канонической формы:
c,∙x max (min) при условиях:					A∙x = b, x 0n.

Определение. Полуканоническая форма ЗЛП:

c,∙x max (min) при условиях (13) и (11).

(1) Каноническую форму задачи ЛП называют также стандартной или основной, а стандартную ― симметричной.

12

Здесь и неоднократно далее мы будем говорить о сводимости и эквивалентности задач оптимизации. Формулировка точного определения сводимости(1) задач выходит за рамки программы курса. Дадим определение, достаточное для наших целей.

Определения.

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

Задачи P1 и P2 эквивалентны, если P1 сводится к P2 и P2 сводится к P1.

Теорема 2.1 (об эквивалентности форм записи ЗЛП). Перечисленные в разделе 2.1

формы записи ЗЛП эквивалентны.(2)

2.2. Экономическая интерпретация задачи линейного программирования

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

ных сочетаниях применять n технологических способов (или просто способов). Предположим также, что в реализации технологических способов участвуют ингредиенты (материальные и трудовые ресурсы, оборудование, другие факторы производства, полуфабрикаты, конечные продукты, полезности) с номерами 1,...,m. Каждый ингредиент может производиться и/или потребляться рассматриваемой системой.

Мерой использования технологического способа в плановом периоде является его ин-

тенсивность, определенная в соответствии с содержанием способа и принимающая неотри-

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

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

(основного для данного способа) ингредиента. Пусть xj 0 — интенсивность использования способа j (xj = 0 означает, что способ не применяется). Тогда вектор x = (x1,...,xn)T естественно назвать планом производства.

Пусть gi(x) — чистое потребление системой ингредиента i за плановый период при плане x (разность потребления и производства); gi(x) < 0 означает, что в системе к концу пе-

риода образуется избыток ингредиента i, равный |gi(x)|.

В начале периода система имеет запас bi ингредиента i; bi < 0 означает, что система имеет обязательство по поставкам ингредиента i (за плановый период) во внешнюю среду в размере |bi|.

(1)О сводимости и эквивалентности задач оптимизации см.: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982 (стр. 26, 27).

(2)Алгоритм преобразования ЗЛП, существование которого доказывает теорему, описан в книге: Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006 (§4.1.3).

13

Допустим, что план x дает системе (в течение планового периода) полезность (напри-

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

f(x) max	при условиях			(15)
gi(x) bi				(16)
	для i 1, m ,
x 0n.				(17)

Это задача нелинейного программирования. Смысл ограничения (16) зависит от знака

bi. Неотрицательное bi ― это исходный запас ингредиента, и потребление не должно его превышать. Если же bi < 0, то и левая часть неравенства должна быть отрицательной. В та-

ком случае |bi| мы интерпретируем как обязательство по поставке ингредиента во внешнюю для системы среду. Условие (16) в этом случае удобно записать в виде –gi(x) |bi|: чистое производство ингредиента должно покрывать запланированные поставки.

Для того чтобы задачу планирования можно было формализовать в виде задачи линей-

ного программирования, должны выполняться следующие условия.

Делимость. Если способ может применяться с интенсивностями a и b (a < b), то его можно применять с любой интенсивностью x[a, b].

Пропорциональность. Затраты, выпуски и полезность, производимые каждым спосо-

бом, пропорциональны его интенсивности.

Аддитивность. Затраты и выпуски ингредиента, производимые разными способами,

суммируются; полезности, производимые всеми способами, тоже суммируются.

Предположим, что перечисленные условия выполняются. Из принципа пропорцио-

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

висят от его интенсивности и не зависят от интенсивностей других способов. Пусть aij —

удельное потребление ингредиента i технологическим способом j; aij < 0 означает, что способ j при единичной интенсивности производит |aij| единиц ингредиента i. Пусть xj — интенсив-

ность использования технологического способа j, cj — его удельная полезность.

Из сформулированных выше свойств системы с очевидностью следует, что чистое по-

требление ингредиента i (i 1, m ) и целевая функция задачи принимают вид
gi(x) = aij x j	и f(x) = c j x j .
j	j
Теперь можем записать задачу планирования следующим образом:
f(x) = c j x j max при условиях aij x j bi для i			,	x 0n.
		1, m			(18)
j	j

14

Получили ЗЛП в стандартной форме. Ее целевая функция описывает суммарную по-

лезность плана x, левая часть ограничения с номером i ― это потребление ингредиента при плане x.

Обозначения. Столбец с номером j и строку с номером i матрицы A обозначим [A]j и

[A]i соответственно.

Столбец [A]j дает технологическое описание способа деятельности системы, указывая в каких количествах потребляются/производятся ингредиенты при единичной интенсивности использования этого способа. Величина cj (удельная полезность) добавляет к этому описа-

нию экономическую компоненту.

Введем вектор переменныt недостатка si (i 1, m ) и перейдем к канонической форме:

c j x j max при условиях	aij x j + si = bi для i		, x 0n, s 0m.
		1, m
j	j

Если bi 0, то si ― это неиспользованный при плане x остаток ингредиента i. Если же bi < 0,

то si есть объем производства ингредиента i сверх задания |bi|.

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

2.3.1.Общие свойства

Определения.

Многогранное множество ― это совокупность всех решений системы линейных урав-

нений и нестрогих линейных неравенств.

Ограниченное многогранное множество называется многогранником.

Вектор x Rn является выпуклой линейной комбинацией или взвешенным средним векто-

ров x1, …, xk из Rn, если x = i ai xi , где ai R+ для i 1, m и i ai = 1.

Множество всех выпуклых линейных комбинаций векторов x0 и x1 из Rn ― это отрезок

[x0, x1] с концами x0 и x1; [x0, x1] = {(1 – )x0 + x1 | [0, 1]}.

(x0, x1) = [x0, x1] \ {x0, x1} ― множество внутренних точек отрезка.

Точка множества называется угловой (крайней, экстремальной), если она не является внутренней точкой никакого отрезка, лежащего в этом множестве.

Прямой суммой или суммой по Минковскому множеств A Rn и B Rn называют мно-

жество A + B = {a + b | a A, b B}.

15

Теорема 2.2 (о свойствах ЗЛП). Множество допустимых и множество оптимальных решений ЗЛП (7) – (11) обозначим X и X * соответственно.

(а) X и X * ― многогранные множества.(1)

(б) Число угловых точек множества X конечно.(2)

(в) Пусть K ― множество точек, удовлетворяющих условиям (8) – (11) при bi = 0 для всех i. Множество X является прямой суммой некоторого многогранника и множества K(3).

(г) X * (задача разрешима), если и только если она совместна и ограниченна(4).

(д) Если задача (7) – (11) включает условие неотрицательности всех переменных (на-

пример, записана в стандартной или канонической форме) и X * , то в X * есть угловая точка множества X.(5)

2.3.2.Свойства задачи в канонической форме

Всоответствии с утверждением (д) теоремы 2.2 оптимальное решение ЗЛП в канониче-

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

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

Определения и обозначения. Пусть A ― матрица ЗЛП в канонической форме, r ―

ранг матрицы A.

Базисом матрицы назовем максимальный набор ее линейно независимых столбцов. Бу-

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

Если β = ([A]j(1), …, [A]j(r)) ― базис матрицы A, то множество N(β) = {j(i) | i 1, r } назы-

вают базисным множеством, переменные задачи с номерами j N(β) ― базисными перемен-

ными.

Относительно базиса β = ([A]j(1), …, [A]j(r)) матрицы A любой вектор x размерности n1

(столбец) или 1 n (строку) можно разбить на базисную часть xб(β) и небазисную часть xн(β).

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

сномерами j N(β) в том порядке, в котором соответствующие столбцы входят в матрицу A.

(1)Доказательство оставляем читателю в качестве упражнения.

(2)Доказательство: Ашманов С.А. Линейное программирование. М.: Наука, 1981 (теорема 2.19).

(3)Доказательство: там же, теорема 2.25.

(4)Доказательство для канонической формы: Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980 (теорема 1 на стр. 155). Эквивалентность форм записи ЗЛП позволяет распространить утверждение на ЗЛП общего вида.

(5)Более общий результат доказан в книге: Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973 (следствие 32.3.1). См. также: Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006 (утверждение 16 на стр. 132).

16

Базисная и небазисная части вектора-столбца (вектора-строки) тоже являются столбца-

ми (строками).

Теорема 2.3 (алгебраическое описание угловых точек).(1) Пусть X ― множество допус-

тимых решений ЗЛП (12) – (14) и ранг матрицы A равен r. Допустимая точка x = (x1, …, xn)T

является угловой точкой множества X, если и только если существуют номера j(i), i 1, r такие, что β = ([A]j(i) | i 1, r ) ― базис матрицы A и xн(β) = 0n–r.

Теорема 2.4 (об исключении линейно зависимых ограничений).(2) Если задача (12) – (14) совместна и одна из строк матрицы A линейно зависит от других, то исключение из за-

дачи соответствующего ограничения не изменяет множество допустимых решений.

Следствие 2.1.(3) Если совместная ЗЛП записана в канонической форме (12) – (14), то можно считать, что строки матрицы A линейно независимы и m ≤ n. Тогда ранг матрицы за-

дачи равен m, всякий базис матрицы A состоит из m столбцов и имеет квадратную невырож-

денную базисную матрицу.

Предположение 9. Учитывая следствие 2.1, в дальнейшем без ограничения общности будем считать, что либо задача (12) – (14) несовместна, либо строки матрицы A линейно не-

зависимы.

Определения. Пусть А ― матрица задачи (12) – (14) и β ― базис матрицы А.

Матрица B(β), составленная из столбцов базиса β в том порядке, в котором они входят в базис, называется базисной матрицей.

(B(β))–1 = B–1(β) ― обратная базисная матрица (существует по следствию 2.1).

Если x Rn и xн(β) = 0n–m, будем говорить, что x ― базисное решение системы уравнений

(13), порожденное базисом β.

Мы будем опускать явное указание на базис β и писать B, B–1, xб и xн вместо B(β), B–1(β), xб(β) и xн(β), если это не приводит к разночтениям.

Следствие 2.2.(3) Пусть X ― множество допустимых решений задачи (12) – (14). Если угловая точка x множества X порождена базисом β, то xб(β) = B–1(β) b ≥ 0m и xн(β) = 0n–m.

Следствие 2.2 обосновывает следующие определения.

Определения и обозначения. Пусть A ― матрица задачи (12) – (14).

Базис β матрицы A является допустимым, если B–1(β) b ≥ 0m.

(1)Доказательство: Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980 (теорема 1 на стр. 147).

(2)Доказательство: Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006 (замечание 22, стр. 109 – 110).

(3)Доказательство оставляем читателю в качестве упражнения.

17

Базисное допустимое решение (БДР) задачи (12) – (14), порожденное допустимым базисом β матрицы A, ― это вектор x = x(β) Rn такой, что xб(β) = B–1(β) b и xн(β) = 0n–m.

Следствие 2.3(1). Для ЗЛП в канонической форме множество БДР совпадает с множест-

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

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

Каждой ЗЛП (которую в этом контексте называют прямой задачей) соответствует, так называемая, двойственная задача, которая тоже является задачей линейного программиро-

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

экономического анализа.

2.4.1. Экономическая мотивация построения двойственной задачи

Рассмотрим ЗЛП в стандартной форме (18). Упрощая изложенную в разделе 2.2 эконо-

мическую интерпретацию этой задачи, предположим, что моделируемая система ― это

предприятие, применяющее однопродуктовые технологические способы: способ j 1, n про-

изводит продукт j. Интенсивность использования способа будем измерять количеством про-

изведенного продукта, то есть xj ― это плановый объем производства продукта j. В список ингредиентов включим только используемые предприятием ресурсы (с номерами i 1, m ).

Тогда aij ― расход ресурса i на единицу продукта j (удельная ресурсоемкость), bi ― наличие ресурса i.

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

дукта j. Допустим, что некто хочет купить имеющиеся на предприятии ресурсы. Если потен-

циальный покупатель заплатит yi за единицу ресурса i, то суммарный платеж составит

m
h(y) = yibi	= y, b , где y = (yi | i 1, m ), b = (bi | i 1, m )T.	(19)

i 1

Понятно, что покупатель стремится минимизировать эту сумму.

Однако владеющее ресурсами предприятие, используя ресурсы 1, …, m в количествах a1j, …, amj соответственно, может реализовать технологический способ j с единичной интен-

сивностью, произвести единицу продукта j и получить доход cj. Поэтому предприятие не продаст указанный комплект ресурсов дешевле, чем за cj. Это значит, что гипотетические цены ресурсов yi должны удовлетворять условиям

aij yi
	≥ cj для j 1, n .			(20)
i

(1) Доказательство оставляем читателю в качестве упражнения.

18

Таким образом, вектор «справедливых» цен y должен быть решением задачи миними-

зации функции (19) с условиями (20) и y ≥ 0m. Это и есть задача, двойственная к ЗЛП в стан-

дартной форме (18).

Предположим теперь, что предприятие максимизирует прибыль и cj ― удельная при-

быль от продукта j. При калькуляции удельной прибыли в составе себестоимости учитыва-

ются затраты на приобретение ресурсов по каким-то «базовым» ценам. Эти затраты покупа-

тель ресурсов должен компенсировать. Поэтому следует определить только «надбавки» (не-

отрицательные) к базовым ценам. Вектор надбавок y = (yi | i 1, m ) должен удовлетворять ус-

ловиям (20), которые при такой интерпретации требуют, чтобы прибыль от продажи ком-

плекта ресурсов (a1j, …, amj) не должна быть меньше прибыли от использования этого ком-

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

двойственную задачу, но с другой интерпретацией.
Итак, для ЗЛП в стандартной форме
f(x) = c, x → max	при условиях Ax ≤ b, x ≥ 0n
двойственная задача имеет вид
h(y) = y, b → min	при условиях yA ≥ c, y ≥ 0m.
2.4.2. Математическая мотивация построения двойственной задачи
Для ЗЛП в канонической форме
f(x) = c, x → max при условиях Ax = b, x ≥ 0n		(21)

найдем оценку максимального значения ЦФ на множестве X допустимых решений задачи.

Если x X, то выполняется равенство b – Ax = 0n. Тогда для любого вектора-строки y R1 m

имеем

c, x = c, x + y(b – Ax) = c, x – y(Ax) + y, b = c x – (yA) x + y, b = c – yA, x + y, b .

Если c – yA ≤ 0n, то f(x) = c, x ≤ y, b . Таким образом, y, b есть верхняя граница значений f(x) на X при любом y таком, что y R1 m и yA ≥ c. Следовательно, чтобы найти точную верх-

нюю границу этих значений, нужно решить следующую задачу:

h(y) = y, b → min при условии yA ≥ c. (22)

Это двойственная задача для ЗЛП в канонической форме. От двойственной задачи для стандартной формы она отличается отсутствием условия неотрицательности двойственных переменных yi.

Запишем задачу (22) подробней:

19

m	m
h(y) = bi yi → min при условиях	aij yi
		≥ cj для j 1, n .			(23)
i 1	i 1

Ориентируясь на запись (23), сформулируем правила построения двойственной задачи для ЗЛП в канонической форме (21).

П1. Каждому ограничению-равенству прямой задачи сопоставляем двойственную пе-

ременную.

П2. Каждой переменной прямой задачи сопоставляем двойственное ограничение.

П3. В левой части двойственного ограничения стоит скалярное произведение вектора коэффициентов при соответствующей переменной прямой задачи на вектор двойственных переменных. Правая часть ограничения ― коэффициент ЦФ прямой задачи при соответст-

вующей переменной.

П4. Левую и правую части двойственного ограничения соединяем знаком «≥».

П5. Целевая функция двойственной задачи двойственной задачи есть скалярное произ-

ведение вектора правых частей ограничений прямой задачи на вектор двойственных пере-

менных. В двойственной задаче ЦФ минимизируется.

2.4.3. Построение двойственной задачи в общем случае

Определения и обозначения. Задачу, двойственную для задачи линейного программи-

рования P обозначают P*.

Пусть P ― ЗЛП общего вида, P1 ― результат приведения задачи P к канонической

форме. Задача, двойственная к P1, по определению является двойственной и для P: P* = P1* .

Наша ближайшая цель ― сформулировать правила построения двойственной задачи для ЗЛП общего вида (7) – (11) с максимизируемой ЦФ. Чтобы данное выше определение однозначно фиксировало вид задачи P*, нужно задавать способ перехода от P к P1.

Если в задаче P переменная xj объявлена неположительной, то для перехода к канони-

ческой форме сделаем замену переменной xj = –zj и накладываем на zj условие неотрицатель-

ности. После замены коэффициенты при zj в ограничениях и ЦФ имеют значения –aij (i 1, m )

и –cj. По правилам П3 и П4 ограничение задачи P1* , соответствующее по правилу П2 пере-

менной zj, имеет вид

m	m
(aij ) yi	≥ –cj, или, эквивалентно, aij yi ≤ cj.
i 1	i 1

Если в задаче P переменная xj не ограничена по знаку, то делаем замену переменных xj = uj – vj и объявляем переменные uj и vj неотрицательными. После замены коэффициенты

20