 Линейное программирование и немного капитализмаОтступим на шаг назад и посмотрим, как будет выглядеть задача Канторовича в "конечномерном" приближении, ср. с тем, с чего мы начинали, но только сейчас у нас из задачи полностью исчезла геометрия, остался только бухгалтерский учёт. Ну, и немножко сменим бытовой контекст для разнообразия.
Есть m источников (складов, ..., пронумерованных индексом i), в каждом из которых находится μi ≥ 0 единиц товара (единственного, однородного, неограниченно делимого, ...), и n магазинов, в каждый (j-й) из которых надо доставить νj ≥ 0 единиц этого товара. Предполагается, что всё сбалансировано, и спрос равен предложению,
∑j=1m μi = ∑j=1n νj.
Для любой пары (i,j) = (склад, магазин) задано неотрицательное число cij ≥ 0 — стоимость перевозки (транспортировки) единицы товара между двумя соответствующими точками.
Транспортный план в такой задаче — матрица (не обязательно квадратная — бывают на свете и прямоугольные матрицы!) Fij ≥ 0, i =1, ..., m, j = 1, ..., n, элементы которой есть количество товаров, перевозимых со склада i в магазин j. Стоимость такой перевозки — двойная сумма, подлежащая минимизации
∑i,j Fij cij → minimum при ограничениях
∑j=1,...n Fij = μi, ∑i=1,...,m Fij = νj
означающих соблюдение "граничных условий" (каждый склад опустеет, каждый магазин затарится полностью).
Как находить минимум функции на подмножестве, заданном одним или несколькими равенствами? Ответ в этой задаче нашёл великий Лагранж (см. его грустный портрет: история математики знает очень немного подобных универсалов, революционизировавших несколько областей математики, матфизики и астрономии). Его рецепт прост: если надо найти минимум функции F(x) при ограничениях G1(x)=0, ..., Gr(x)=0, то надо составить линейную комбинацию H = F + λ1G1+...+λr Gr с неопределёнными пока вещественными множителями λk ("множителями Лагранжа") и искать минимум этой комбинации "так, как если бы переменные были независимы". Сказанное означает, что надо выписать все частные производные H = H(x,λ) по иксам и по лямбдам и приравнять их нулю. Вторая половина уравнений имеет вид G1(x)=0, ..., Gr(x)=0 поскольку зависимость Н от лямбд линейная, а первая половина означает геометрически, что градиент функции F = F(x) раскладывается как линейная комбинация градиентов функций Gk. Мы получаем систему уравнений относительно неизвестных (x,λ), которую надо решать как обычно.
Замечание. Описанный метод без долгих комментариев понятен физикам. Пусть F — потенциал силы, действующей на материальную точку. Точка вынуждена оставаться на поверхности, заданной ограничениями. Предположим для простоты, что r = 1, т.е., в пространстве задана гладкая (гипер)поверхность, с которой точка не может сходить. Где будет равновесие? Если б ограничений не было, равновесие было бы достигнуто в минимуме потенциала, там, где сила (градиент потенциала) обращается в нуль. При наличии ограничения возникает сила нормальной ("перпендикулярной") реакции, направленной перпендикулярно поверхности в каждой точке (скажем, если точка вынуждена жить на сфере, сила будет направлена по радиусу). Правило Лагранжа состоит в том, что в точке условного равновесия внешняя сила должна уравновешиваться реакцией опоры. Это позволяет составить уравнения статического баланса: реакция опоры неизвестна по абсолютной величине, но известна по направлению. Если ограничений несколько, то каждая "опора" вносит свой вклад.
Замечание. Не только физики понимают это. Предположим, что вы делаете покупку из нескольких товаров и заинтересованы в том, чтобы сделать её подешевле. При этом в свою тележку вы можете класть не произвольный набор продуктов, а обязаны подчиниться каким-то ограничениям. Например, мы составляем план платежей по ипотеке по месяцам на ближайший год, и должны возвращать банку какие-то деньги. Их можно возвращать не сейчас, а через три или через семь месяцев, но при этом надо соблюдать балансовые ограничения: на наш счёт, конечно, приходит известная вам зарплата, и мы не можем выплатить какую-то сумму до того, как она придёт. Выпишем балансовые ограничения, в которые надо "вписаться". Тогда наша задача станет в точности задачей минимизации при ограничениях. Правило Лагранжа состоит в том, что надо назначить себе штрафы за нарушение разных ограничений, после чего искать минимум затрат с учётом штрафов. Утверждается, что таким образом мы можем найти минимум, совместный с наложенными ограничениями.
Линейное программирование. Задача оптимальной перевозки, описанная выше, имеет (если приглядеться) очень специфический вид: целевой функционал (критерий оптимизации) является линейной функцией независимых переменных (однородность несущественна, поскольку прибавление константы никак не влияет на решение), а наложенные ограничения задаются линейными (неоднородными) нестрогими неравенствами заметим, что ограничение, имеющее вид равенства G(x) = 0 может быть формально заменено двумя "встречными" неравенствами G(x) ≤ 0 и G(x) ≥ 0. Кроме того, по причинам, связанным с двойственностью, мы добавляем к списку ограничений условия неотрицательности независимых переменных х. С учётом сказанного общая задача линейного программирования может быть записана в векторно-матричной форме
c·x → maximumx при ограничениях А·x ≤ b, x ≥ 0 Здесь: - x — вектор-столбец высоты n, составленный из неизвестных переменных xj, j =1,...,n,
- c — вектор-строка длиной n, состоящая из коэффициентов максимизируемого линейного функционала, c·x = cx — матричное произведение, дающее 1х1-матрицу (число),
- b — вектор-столбeц высоты m,
- 0 — вектор-столбец высоты n,
- A — прямоугольная m×n-матрица, (m строк, n столбцов), так что произведение А·x = Ax является вектор-столбцом высоты m.
- Неравенство между векторами означает набор неравенств между всеми соответствующими компонентами: матричное ограничение Аx ≤ b эквивалентно набору из m линейных неоднородных ограничений ai·x ≤ bi, i=1,...,m, где ai суть вектор-строки матрицы А, это же относится к условиям неотрицательности xj ≥ 0, j =1,...,n.
Стандартная экономическая интерпретация этой задачи прозрачна: неизвестный вектор х обозначает вектор товаров, которые некто (производитель, предприниматель) собирается произвести и продать "государству", т.е., по фиксированным внешним ценам с, максимизируя стоимость продаж c·x. Стратегия производителя — выбрать х наиболее выгодным для себя образом из имеющихся возможностей, т.е., с соблюдением определённых ограничений.
Мы предполагаем, что (производственные) возможности ограничены имеющимися ресурсами (вектор b), которые расходуются при производстве товаров линейным образом, описанным матрицей А. Элемент (число) Aij ≥ 0 есть количество единиц i-го ресурса, используемого при производстве единицы j-го товара. Сумма ∑j Aijxj есть общее количество этого ресурса, требуемое при производстве всего пакета товаров х = (x1, ... , xn). Балансовые (ресурсные) ограничения состоят в том, чтобы при выпуске набора х = (x1, ... , xn) обойтись имеющимся вектором ресурсов b = (b1, ... , bm).
Согласно общей идеологии Лагранжа, для нахождения решения надо прибавить к целевому функционалу c·x = ∑ cjxj линейную комбинацию, состоящую из ограничений ai·x − bi ≤ 0 (где ai — i-я строка матрицы А) и ("перевёрнутых") условий неотрицательности − xj ≤ 0 (при всех допустимых i,j) с неопределёнными множителями Лагранжа. После этого надо искать критическую точку полученной билинейной функции. В силу билинейности частные производные по иксам окажутся функциями множителей Лагранжа. Обозначив через ξi ≥ 0, i = 1, ..., m множители, соответствующие i-му "ресурсному" ограничению и ηj ≥ 0 — требованию неотрицательности xj, мы увидим, что условия оптимальности примут вид ξ·A − η ≥ c, что соответствует двойственной экстремальной задаче (переменные η легко изгоняются)
ξ·b → minimumξ при ограничениях ξ·A ≥ c, ξ ≥ 0.
Здесь:
- ξ — вектор-строка длиной m,
- Матричное произведение ξ·A (обратите внимание на то, что порядок множителей заменен на обратный) есть строка длиной n.
- Параметры b,c (наряду с матрицей А) — общие для прямой и обратной задач.
ДвойственностьОбе задачи (и прямая, и двойственная) имеют почти одинаковый вид: задано выпуклое множество в линейном пространстве независимых переменных (x ∈ ℝn в первом случае, ξ ∈ ℝm во втором). Разница в том, что в первом случае мы рассматриваем переменные как вектор-столбец, а во втором — как вектор-строку. Разница проявляется в том, с какой стороны (слева или справа) эти векторы можно умножать на (неквадратную в общем случае) матрицу А. Далее, двойственные ξi переменные соответствуют "ресурсным" ограничениям и могут быть интерпретированы как цены на лимитированные ресурсы. Их неотрицательность отражает знак ≤ в ограничениях Ax ≤ b. Сам вектор доступных ресурсов b становится критерием двойственной задачи. Напротив, компоненты вектора с, задающего критерий ("цены" переменных х), становятся ограничениями, накладываемыми на цены ξ в векторной форме ξА ≥ c. Заметим, что задача минимизации сменилась задачей максимизации.
Решения (векторы) x и ξ называются допустимыми, если каждый из них удовлетворяет всем линейным неравенствам соответствующей задачи. Первая теорема двойственности утверждает, что любые два допустимых решения можно "сравнить" между собой.
Теорема (слабая теорема двойственности).
Если x°, ξ° — допустимые векторы двойственной пары задач, то cx° ≤ ξ°b (это скалярное неравенство, а не векторное!).
Доказательство. cx° ≤ ξ°Аx°, поскольку ξ°А ≥ c и x° ≥ 0 (умножаем неравенства допустимости в двойственной задаче на неотрицательные координаты вектора x°). Осталось воспользоваться неравенствами Аx° ≤ b (допустимость в прямой задаче) и неотрицательностью координат вектора ξ°. ∎
Слабая теорема двойственности позволяет по любому допустимому решению двойственной задачи дать оценку сверху значения оптимума в прямой задаче: это полезно, чтобы понимать, на что в принципе можно рассчитывать, решая прямую задачу линейного программирования. Если нам удастся найти допустимое решение двойственной задачи, которое лучше, чем ξ°, то новая оценка решений прямой задачи будет ещё точнее. Разумеется, в силу полной симметрии аналогичные утверждения верны и после перемены ролями между прямой и двойственной задачами. В связи со слабой теоремой двойственности возникает естественная гипотеза, — если мы найдём самое наилучшее допустимое решение двойственной задачи (настоящий экстремум), то нестрогое неравенство в теореме двойственности превратится в точное равенство.
Но в задаче линейного программирования решение существует не всегда. Заметим, что если бы мы не ограничились исключительно нестрогими неравенствами, а позволили бы строгие, это было бы совершенно очевидно: на одномерной оси иксов поиск максимального значения x → maximum при нестрогом ограничении x < 0 безнадёжен. Но и в случае, когда все неравенства нестрогие, мы можем столкнуться с одной из двух неприятностей: - Множество допустимых векторов х пусто (система линейных ограничений несовместна), или
- Линейный функционал на множестве допустимых векторов неограничен (пример: x → maximum, x ≥ 0).
Во всех остальных случаях решение существует (возможно, неединственное).
Теорема (сильная теорема двойственности).
Если одна из двух проблем имеет оптимальное решение x°, то и двойственная проблема тоже имеет оптимальное решение ξ° (и наоборот), и неравенство вырождается в равенство cx° = ξ°b. ∎
Замечание. Читатель-математик может поднять бровь при виде того, как сформулирована задача линейного программирования. Слишком много обстоятельств выглядят насилием над вожделенной симметрией. Почему "ресурсные неравенства" Ax ≤ b записаны таким образом, а не привычным для математиков образом Ax + b ≤ 0? И почему неравенства в эту сторону, а не в противоположную (мы же не делам никаких предположений про знаки матричных элементов А и знака свободных членов b? Откуда взялись условия неотрицательности для иксов? Что делать с ограничениями типа равенств? В общем, вопросов много. Некоторые условия являются "нормировкой" и могут быть достигнуты при помощи переносов из одной части в другую, умножения неравенств на −1 или замены ограничения типа равенства двумя "встречными" нестрогими неравенствами.
Есть определённая мнемоника, позволяющая запомнить, как писать двойственную задачу по исходной задаче линейного программирования:- Каждая переменная x исходной задачи соответствует "векторному" ограничению в двойственной задаче и наоборот,
- двойственным образом, каждое ограничение на иксы (за исключением ограничения на знак) соответствует двойственной переменной
- Знаки переменных соответствуют направлению соответствующих неравенств: ограничение на иксы вида ... ≤ bi соответствует знаку ξi ≥ 0, ограничение ... ≥ bi соответствует знаку ξi ≤ 0, ограничение ... = bi означает, что на знак ξi не накладывается ограничения. Аналогичным образом, неотрицательность xj ≥ 0 означает, что в двойственной задаче ограничение имеет вид ... ≥ cj, неположительность xj ≤ 0 — ограничению ... ≤ cj, отсутствие ограничений на знак xj означает ограничение типа равенства ... = cj.
- Коэффициенты исходного функционала с соответствуют правым частям ресурсных ограничений b,
- Исходная задача соответствует максимизации функционала cx, двойственная — минимизации ξb.
Но мнемоника мнемоникой, а ощущение того, что тебе рассказывают кулинарный рецепт вместо того, чтобы объяснить стоящие за ним химические свойства и законы, остаётся. И правильно. Правильный рассказ про эти вещи нужно начинать с теории выпуклых множеств и соответствующей теории преобразования Лежандра. Чтобы не растекаться мысию по древу, я пока поставлю в этом месте дорожный указатель, чтоб не забыть. ☯ Двойственность в задаче КанторовичаРассмотрим задачу Канторовича и, распознав в ней задачу линейного программирования, напишем двойственную к ней. Начнём с дискретного варианта, описанного в начале параграфа.
"Иксами" (неизвестными переменными) будут элементы Fαβ, α = 1, ..., A, β = 1, ..., B матрицы перевозок: в отличие от "стандартной" формы наши иксы организованы в прямоугольную матрицу, и нам надо как-то упорядочить их, чтобы индексировать одним индексом j =(α,β) размерности AB. Соответствующий вектор цен c тоже организован в матрицу тех же размеров с элементами cαβ. Заметим, что в исходной задаче ищется минимум (а не максимум, как в стандартной задаче), поэтому для приведения к стандартной форме надо поколдовать со знаками. Переменные неотрицательны, F ≥ 0 (теперь это неравенство матричное), а "ресурсные ограничения" имеют вид балансовых соотношений по всем источникам и стокам (их число равно сумме A + B числа складов и магазинов)
∑α=1A Fαβ = νβ, ∀ β =1, ..., B, и ∑β=1B Fαβ = μα, ∀ α =1, ..., A.
Обозначим соответствующие двойственные переменные через qβ и pα . Согласно "мнемонике", описанной выше, двойственная задача будет иметь вид максимизации суммы
∑α pαμα + ∑β qβνβ
при ограничениях
pα + qβ ≤ cαβ при всех α = 1, ..., A, β = 1, ..., B.
"Экономический" смысл двойственной задачи тоже довольно прозрачен, по крайней мере на первый взгляд. Надо "справедливо поделить" стоимость перевозки cαβ единицы товара (единственного, напомним) со склада α в магазин β между складом и магазином, назначив цену для отправителя pα ("отпускную цену" ) и "цену для получателя" qβ, обе неотрицательных, так, чтобы минимизировать общие суммарные расходы и тех и других.
Однако ж есть нюансы©.
Замечание о знаках. В исходной постановке балансовые ограничения сформулированы в виде точных равенств, тем самым в двойственной задаче мы не имеем априорной информации о знаках двойственных переменных. Если общий баланс (суммарное количество товара на складах и общий заказ в магазинах) не сходится, то в задаче нет допустимых решений вовсе. Чтобы избавиться от такого досадного обстоятельства, надо заменить балансовые равенства на балансовые неравенства. Руководствуясь "логикой снабженца", направление неравенств надо расставить таким образом:
∑α=1A Fαβ ≥ νβ, ∀ β =1, ..., B, и ∑β=1B Fαβ ≤ μα, ∀ α =1, ..., A. Эти неравенства означают, что со склада нельзя вывезти больше товара, чем там есть, а в каждый магазин надо завезти не меньше обязательного минимума товара. В этой ситуации задача всё ещё может оказаться неразрешимой, если товар в глобальном дефиците, но если он имеется в избыточном количестве, то допустимо оставить часть товара гнить на складах или завезти в некоторые магазины больше планового количества. А главное, — все ограничения приобретут канонический вид нестрогих неравенств, и знаки двойственных переменных становятся определёнными. Но — achtung! — "цены" qβ становятся при этом неположительными! qβ = −rβ, где rβ ≥ 0 при всех β = 1, ..., В. После всех подстановок мы получаем двойственные ограничения, имеющие "коммерческий" смысл: расходы rβ для магазина β складываются из затрат на перевозку и "отпускную" стоимость товара со склада (я несколько раз пытался расставить правильно неравенства и знаки, но всякий раз провирался; буду признателен, если кто-нибудь возьмёт на себя труд написать правильный ответ).
 Краткий исторический экскурсЭкстремальными задачами, в частности, задачами, которые потом будут названы задачами линейного программирования, Леонид Витальевич Канторович (1912—1986) стал заниматься в 1938 году, и при помощи общего метода множителей Лагранжа (разумеется, известного математикам) он описал построение двойственной задачи к задаче линейного программирования. Результаты были изложены в тоненькой брошюрке (68 страниц) в 1939 году. Многочисленные "народнохозяйственные примеры" занимали бо́льшую часть её объёма, и решались эти задачи при помощи мелкого трюкачества с использованием двойственных задач, имевших более простую форму.
Но с интерпретацией результатов возникла идеологическая проблема. Идея приписать каждому ресурсному ограничению определённую величину "штрафа", после чего убрать ограничения, заменив их штрафами пропорционально объёму нарушения (перерасходу дефицитного ресурса) ещё как-то могла поместиться в головах советских доктринеров-от-экономики, проповедников планового хозяйства. Но идея назвать эти коэффициенты ценами ресурсов, по которым они должны были бы свободно покупаться и продаваться, оставляя советскому хозяйственнику "всего лишь" задачу максимизации чистой прибыли (доход от продажи минус затраты на сырьё) уже была ересью, за которую могли и на костёр отправить. И это ещё до обсуждения вопроса о том, кто будет назначать эти самые цены. Если их назначить абы как, то никакой баланс не свести: продукты, цены которых ниже "правильных", окажутся в дефиците, а переоцененные продукты будут пылиться на складах.
Канторович, понимая, в какое болото он забрёл, ни разу в своём тексте не использовал слово "цены". Термин для обозначения двойственных переменных, который он предложил — "объективно обусловленные оценки". В таком виде можно было с видом невинности отвечать на вопросы разных савонарол, что-де нахождение объективно обусловленных оценок — прерогатива составителя разумного плана развития народного хозяйства. Отсюда уже (учитывая уровень логической грамотности партийных доктринеров) можно было любые "цены", назначенные Госпланом СССР, объявить объективно обусловленными. А ежели что в дефиците окажется, так это по экономической неграмотности руководителей на местах.
Непрерывная/измеримая версия задачи КанторовичаПоскольку все рецепты уже обкатаны в конечномерной ситуации, можно просто написать двойственную задачу к задаче оптимального перевоза плоской меры μ(x) области Х в плоскую же меру ν(y); решением должна быть мера Π на декартовом квадрате X2 = { (x,y): x,y ∈ X }, минимизирующая интеграл ∫(x,y) C(x,y) dΠ(x,y) стоимости перевозок.
Двойственная задача состоит в определении двух функций φ:X → ℝ и ψ: X → ℝ (уж настолько прилично себя ведущих, насколько получится) так, чтобы при всех х,у выполнялось условие
φ(x) + ψ(y) ≤ C(x,y).
При этих ограничениях надо максимизировать некий функционал, равный интегралу ∫ φ(x) dμ(x) + ∫ ψ(y) dν(y).
❝Учитывая, что меры источника и стока неотрицательны, мы можем только выиграть, если увеличим наши функции, соблюдая ограничения. Для этого надо будет решить локальные экстремальные задачи: φ(x) = maxy ∈ X C(x,y) − ψ(y), соответственно, ψ(y) = maxx ∈ X C(x,y) − φ(x). Если мы сможем решить эти уравнения, то мы найдём очень хорошее допустимое решение двойственной задачи, а значит, по слабой теореме двойственности получим очень важное знание про исходную задачу Канторовича. ❞
Эти соотношения настолько интересны, что я возьму их в рамочку для удобства ссылок из последующих бесед. |
sick
anxious
