Понятие о линейной оптимизации

Лекция 10 Понятие о линейной оптимизации Произвольная прямая в пространстве ℝ2 , которое мы также называем плоскостью, имеет уравнение 𝑎1 ∙ 𝑥1 + 𝑎2 ∙ 𝑥2 = 𝑐 и делит ℝ2 на две полуплоскости, определяемые неравенствами 𝑎1 ∙ 𝑥1 + 𝑎2 ∙ 𝑥2 ≤ 𝑐 и 𝑎1 ∙ 𝑥1 + 𝑎2 ∙ 𝑥2 ≥ 𝑐. Например, на рис. 1 стрелками отмечены полуплоскости 4𝑥1 + 1.5𝑥2 ≤ 24 , 20𝑥1 + 20𝑥2 ≤ 200 , 𝑥1 ≥ 2 и 1200𝑥1 + 150𝑥2 ≤ 6000. Ниже мы рассмотрим содержательную задачу, с которой связана эта картинка. Произвольная гиперплоскость 𝐻 в пространстве ℝ𝑛 состоит из всевозможных точек 𝑋 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ), удовлетворяющих уравнению вида 𝑎1 𝑥1 + 𝑎2 𝑥2 + ⋯ + 𝑎𝑗 𝑥𝑗 + ⋯ + 𝑎𝑛 𝑥𝑛 = 𝑐 (1) где хотя бы одно из чисел 𝑎𝑗 отлично от нуля. Гиперплоскость 𝐻 делит ℝ𝑛 на два половины, которые мы назовем полупространствами и обозначим ℝ𝑛+ (𝐻) и ℝ𝑛− (𝐻) : ℝ𝑛+ (𝐻) = { 𝑋 ∈ ℝ𝑛 ∶ 𝑎1 𝑥1 + 𝑎2 𝑥2 + ⋯ + 𝑎𝑗 𝑥𝑗 + ⋯ + 𝑎𝑛 𝑥𝑛 ≥ 𝑐 } ℝ𝑛− (𝐻) = { 𝑋 ∈ ℝ𝑛 ∶ 𝑎1 𝑥1 + 𝑎2 𝑥2 + ⋯ + 𝑎𝑗 𝑥𝑗 + ⋯ + 𝑎𝑛 𝑥𝑛 ≤ 𝑐 } 1 (2) (3) Ясно, что ℝ𝑛+ (𝐻) ∪ ℝ𝑛− (𝐻) = ℝ𝑛 и ℝ𝑛+ (𝐻) ∩ ℝ𝑛− (𝐻) = 𝐻 . Уравнение гиперплоскости (1) можно умножить на любое число 𝜆 ≠ 0, так что получим: (𝜆𝑎1 )𝑥1 + (𝜆𝑎2 )𝑥2 + ⋯ +(𝜆𝑎𝑗 )𝑥𝑗 + ⋯ + (𝜆𝑎𝑛 )𝑥𝑛 = 𝜆𝑐 (4) Множество решений (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) уравнения (4) совпадает с множеством решений уравнения (1). Соответственно, любое из неравенств (2) и (3) можно умножить на любое 𝜆 ≠ 0. Определяемые ими множества точек 𝑋 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) при этом не изменятся. Если неравенство (2) умножить на (−1), то получим неравенство вида (3) : (−𝑎1 )𝑥1 + (−𝑎2 )𝑥2 + ⋯ + (−𝑎𝑗 )𝑥𝑗 + ⋯ + (−𝑎𝑛 )𝑥𝑛 ≤ −𝑐 Таким образом, полупространство ℝ𝑛+ (𝐻) можно считать полупространством ℝ𝑛− (𝐻) и наоборот: ℝ𝑛− (𝐻) станет полупространством ℝ𝑛+ (𝐻), если умножить неравенство (3) на (−1). Таким образом, обозначения ℝ𝑛± (𝐻) не вполне корректны. Произвольное полупространство в ℝ𝑛 будем обозначать Π 𝑛 , граничащую с ним гиперплоскость обозначим Π 𝑛−1 (где Π 𝑛−1 ⊂ Π 𝑛 ). При этом гиперплоскость Π 𝑛−1 определяется уравнением вида (1), а полупространство Π 𝑛 определяется неравенством вида (2) или (3) на выбор. Определение 1. Многогранником в пространстве ℝ𝑛 называется пересечение произвольных полупространств Π1𝑛 , Π2𝑛 , … , Π𝑘𝑛 , где 𝑘 - произвольное натуральное число. В частности, любое полупространство является многогранником. В пространстве ℝ2 , которое мы также называем плоскостью (и наглядно представляем его себе, как плоскость), многогранники называются многоугольниками. Полупространства в ℝ2 также называются полуплоскостями. Таким образом, пересечение любого числа полуплоскостей в ℝ2 является многоугольником. 2 На рисунке 2 изображены правильные многогранники в ℝ3 , называемые также Платоновыми телами. Интересно, что других правильных многогранников в ℝ3 не существует, хотя существует бесконечно много разных типов правильных многоугольников в ℝ2 . Определение 2. Если произвольный многогранник 𝑄 𝑛 в пространстве ℝ𝑛 является пересечением различных полупространств Π1𝑛 , Π2𝑛 , … , Π𝑘𝑛 , то его вершиной называется любая точка 𝑋 ∈ 𝑄 𝑛 , которая принадлежит каким-то 𝑛 из гиперплоскостей Π1𝑛−1 , Π2𝑛−1, … , Π𝑘𝑛−1 при том условии, что никакая другая точка в ℝ𝑛 не принадлежит этим 𝑛 гиперплоскостям. Другими словами, вершиной многогранника ∈ 𝑄 𝑛 называется такая точка 𝑋 ∈ 𝑄 𝑛 , что для некоторых, попарно различающихся номеров 𝑖1 , 𝑖2 , … , 𝑖𝑠 , … , 𝑖𝑛 (от 1 до 𝑘) имеет место {𝑋} = Π𝑖𝑛−1 ∩ Π𝑖𝑛−1 ∩ … ∩ Π𝑖𝑛−1 ∩ … ∩ Π𝑖𝑛−1 1 2 𝑠 𝑛 (5) Из определения 2 следует, что многогранник 𝑄 𝑛 ⊂ ℝ𝑛 имеет хотя бы одну вершину только в том случае, когда число 𝑘 полупространств Π𝑖𝑛 , пересечением которых получился этот многогранник, не меньше числа 𝑛. В любом многограннике всегда конечное число вершин. В пространствах ℝ2 и ℝ3 вершинами многогранников являются именно те вершины, которые имеют привычный нам, наглядный смысл. Из (5) следует, что координаты (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) любой вершины многогранника являются единственным решением некоторой системы уравнений 𝑎𝑖1 1 𝑥1 + 𝑎𝑖1 2 𝑥2 + ⋯ + 𝑎𝑖1 𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖1 𝑛 𝑥𝑛 = 𝑐𝑖1 𝑎𝑖2 1 𝑥1 + 𝑎𝑖2 2 𝑥2 + ⋯ + 𝑎𝑖2 𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖2 𝑛 𝑥𝑛 = 𝑐𝑖2 ……………………………………………………… 𝑎𝑖𝑠 1 𝑥1 + 𝑎𝑖𝑠 2 𝑥2 + ⋯ + 𝑎𝑖𝑠 𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖𝑠 𝑛 𝑥𝑛 = 𝑐𝑖𝑠 ……………………………………………………… {𝑎𝑖𝑛 1 𝑥1 + 𝑎𝑖𝑛 2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖𝑛 𝑛 𝑥𝑛 = 𝑐𝑖𝑛 (6) Числа 𝑎𝑖𝑗 и 𝑐𝑖 при 𝑖 ∈ {1,2, … , 𝑘} и 𝑗 = 1, 2, … , 𝑛 определяются тем, что каждая гиперплоскость Π𝑖𝑛−1 имеет уравнение 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 = 𝑐𝑖 а соответствующее полупространство Π𝑖𝑛 определяется неравенством 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≤ 𝑐𝑖 (7) или неравенством 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑗 𝑥𝑗 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 ≥ 𝑐𝑖 (8) Для того, чтобы система (6) имела единственное решение, согласно лекции 4 должно быть выполнено следующее условие: 3 𝑟𝑘(𝐴) = 𝑟𝑘(𝐴̅) = 𝑛 (9) В самом деле, условие 𝑟𝑘(𝐴) = 𝑟𝑘(𝐴̅) является критерием существования решения, а поскольку 𝑟𝑘(𝐴) ≤ 𝑛 , то решение единственно только в том случае, когда 𝑟𝑘(𝐴) = 𝑛 . 𝑎𝑖1 1 𝑎𝑖1 2 … 𝑎𝑖1 𝑗 … 𝑎𝑖1 𝑛 𝑎𝑖2 1 𝑎𝑖2 2 … 𝑎𝑖2 𝑗 … 𝑎𝑖2 𝑛 ………………………… 𝐴= 𝑎 𝑖𝑠 1 𝑎𝑖𝑠 2 … 𝑎𝑖𝑠 𝑗 … 𝑎𝑖𝑠 𝑛 ………………………… ( 𝑎𝑖𝑛 1 𝑎𝑖𝑛 2 … 𝑎𝑖𝑛 𝑗 … 𝑎𝑖𝑛 𝑛 ) 𝑎𝑖1 1 𝑎𝑖1 2 … 𝑎𝑖1 𝑗 … 𝑎𝑖1 𝑛 𝑐𝑖1 𝑎𝑖2 1 𝑎𝑖2 2 … 𝑎𝑖2 𝑗 … 𝑎𝑖2 𝑛 𝑐𝑖2 ……………………………… 𝐴̅ = 𝑎 𝑖𝑠 1 𝑎𝑖𝑠 2 … 𝑎𝑖𝑠 𝑗 … 𝑎𝑖𝑠 𝑛 𝑐𝑖𝑠 ……………………………… ( 𝑎𝑖𝑛 1 𝑎𝑖𝑛 2 … 𝑎𝑖𝑛 𝑗 … 𝑎𝑖𝑛 𝑛 𝑐𝑖𝑛 ) Таким образом, если 𝑘 ≥ 𝑛, то каждая система уравнений (6), определенная каким-то набором попарно различающихся номеров 𝑖1 , 𝑖2 , … , 𝑖𝑠 , … , 𝑖𝑛 от 1 до 𝑘, для которой выполняется условие (9), задает одну вершину многогранника 𝑄 𝑛 . Число вершин может быть любым от 1 до С𝑛𝑘 = 𝑘! (𝑘 𝑛! − 𝑛)! Здесь С𝑛𝑘 равно числу всевозможных наборов из попарно различных индексов 𝑖1 , 𝑖2 , … , 𝑖𝑛 от 1 до 𝑘. Вообще говоря, не каждый из этих наборов задает вершину многогранника, как решение системы уравнений (6). Дело в том, что условие (9) может не выполняться (хотя для определенных наборов полупространств Π1𝑛 , Π2𝑛 , … , Π𝑘𝑛 каждый такой набор индексов удовлетворяет (9) и потому задает вершину, тогда число вершин равно С𝑛𝑘 ). С наглядной точки зрения вершина многогранника характеризуется тем, что никакой отрезок с центром в этой вершине не лежит целиком в многограннике (см. рисунок с платоновыми телами). Теперь мы готовы ввести понятие о задаче линейной оптимизации (которую по старой традиции также называют задачей линейного программирования). Предположим, что задана линейная функция 𝑊(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝛼1 𝑥1 + 𝛼2 𝑥2 + … + 𝛼𝑗 𝑥𝑗 + ⋯ + 𝛼𝑛 𝑥𝑛 + 𝛽 (10) где 𝛼𝑗 , 𝛽 - некоторые числа (постоянные). Cтрого говоря, функция (8) является линейной лишь в том случае, когда 𝛽 = 0. Однако, нет ничего страшного в том, что мы будем называть функцию вида (10) линейной и при 𝛽 ≠ 0. Функция 𝑊(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) называется целевой функцией. Пусть задан многогранник 𝑄 𝑛 ⊂ ℝ𝑛 , определяемый системой неравенств вида (7) и/или (8). Мы назовем его многогранником ограничений. Задача линейной оптимизации состоит в том, чтобы найти такую точку 𝑋̃ = (𝑥̃1 , 𝑥̃2 , … , 𝑥̃𝑛 ), что 𝑋̃ ∈ 𝑄𝑛 и функция (10) принимает в точке 𝑋̃ 4 наибольшее (или наименьшее) значение среди ее значений во всех точках 𝑋 ∈ 𝑄 𝑛 , т.е., должно быть выполнено: 𝑊(𝑥̃1 , 𝑥̃2 , … , 𝑥̃𝑛 ) ≥ 𝑊(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) для всех точек (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ 𝑄𝑛 (11) или 𝑊(𝑥̃1 , 𝑥̃2 , … , 𝑥̃𝑛 ) ≤ 𝑊(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) для всех точек (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ 𝑄𝑛 (12) В случае (11) данная задача условно обозначается (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ 𝑄 𝑛 𝑊(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) → max а в случае (12) пишут (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ 𝑄 𝑛 𝑊(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) → min Любой набор значений переменных 𝑥1 , 𝑥2 , … , 𝑥𝑛 , где точка (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ 𝑄 𝑛 , называется допустимым планом. Набор значений 𝑥̃1 , 𝑥̃2 , … , 𝑥̃𝑛 называется оптимальным планом. Рассмотрим практический пример задачи линейной оптимизации. Лесничество имеет 24 га свободной земли и заинтересовано извлечь из нее доход. Оно может выращивать саженцы новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет чистый доход в 2,5 руб., один бычок - 5 тыс. руб. Выбрать оптимальный план действий для лесничества. 1. В качестве показателя эффективности следует взять годовой доход с земли в рублях. 2. В качестве переменных задачи следует взять: x1 - количество откармливаемых бычков в год; 5 x2 - количество выращиваемых партий новогодних елей по 1000 шт. каждая в год. 3. Целевая функция: 5000∙x1 + 2500∙x2 → max, 4. Ограничения на переменные: 4.1. По использованию земли, га: 4 x1 + 1,5 x2  24. 4.2. По бюджету, руб.: 1200 x1 + 150 x2  6000. 4.3. По трудовым ресурсам, часов: 20 x1 + 20 x2  200. 4.4. Обязательства по контракту, шт.: x1  2. 4.5. Естественные ограничения: x1  0, x2  0. Запись 5000∙x1 +2500∙x2 → max означает, что требуется найти значения x1 удовлетворяющие ограничениям задачи, при которых целевая функция W(x1,x2) = 5000∙x1 + 2500∙x2 принимает наибольшее значение. 6 и x2 , Заштрихованный многоугольник на рисунке – это и есть многогранник 𝑄 2 ⊂ ℝ2 , определяемый ограничениями задачи. Каждая пунктирная линия на рисунке состоит из точек (𝑥1 , 𝑥2 ) ∈ ℝ2 , в которых целевая функция 𝑊(𝑥1 , 𝑥2 ) имеет постоянное значение. На одной из пунктирных линий это значение равно 10 000, на другой 20 000, а не третьей, проходящей через вершину 𝐵, функция 𝑊(𝑥1 , 𝑥2 ) равна 34 000. Наглядно очевидно, что это – наибольшее значение функции 𝑊(𝑥1 , 𝑥2 ) на многограннике (многоугольнике) 𝑄 2 . Для того, чтобы найти оптимальный план данной задачи, осталось вычислить координаты точки 𝐵. Как мы видим, решением задачи линейно оптимизации в данном случае является вершина многогранника ограничений. Это обстоятельство отнюдь не случайно! Теорема 1. Среди решений задачи линейной оптимизации, если они существуют, всегда найдется вершина многогранника ограничений. Если решение единственно, то оно – вершина многогранника ограничений. 7