2 Задача линейного программирования

Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок; позволяющего минимизировать суммарной километраж, была дана в работе советского экономиста А. Н. Толстого в 1930 году.

Систематические исследования задач линейного программирования и разработка общих методов их решения получили дальнейшее развитие в работах российских математиков Л. В. Канторовича, В. С. Немчинова и других математиков и экономистов. Также методам  линейного программирования посвящено много работ зарубежных и прежде всего американских ученых.

Задача линейного программирования состоит в следующем: максимизировать (минимизировать) линейную функцию

, где  

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

(*)

причем все 

Замечание. Неравенства могут быть и противоположного смысла. Умножением соответствующих неравенств на (-1) можно всегда получить систему вида (*).

Если число переменных системы ограничений и целевой функции в математической модели задачи равно 2, то её можно решить графически.

Итак, надо максимизировать функцию   и удовлетворяющей системе ограничений.

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

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

Замечание 2. Если  , то проще взять точку (0;0).

У словия неотрицательности    также определяют полуплоскости соответственно с граничными прямыми  . Будем считать, что система неравенств совместна, тогда полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты которых являются решением данной системы – это множество допустимых решений. Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, лучом, многоугольником, неограниченной многоугольной областью. Таким образом, задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция принимает максимальное (минимальное) значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху (снизу). При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим прямую   (где h – некоторая постоянная). Чаще всего берется прямая  . Остается выяснить направление движения данной прямой. Это направление определяется градиентом (антиградиентом) целевой функции

Вектор   в каждой точке перпендикулярной прямой  , поэтому значение f будет возрастать при перемещении прямой в направлении градиента (убывать в направлении антиградиента). Для этого параллельно прямой   проводим прямые, смещаясь в направлении градиента (антиградиента).

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

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

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений.

4. Строят вектор  .

5. Строят прямую  .

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

7. Определяют координаты точки максимума (минимума) функции и вычисляют значение целевой функции в этой точке.

Пример 1. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х₁ - число изготовленных стульев, Х₂ - число сделанных столов. Задача оптимизации имеет вид:

45 Х₁ + 80 Х₂  → max ,

5 Х₁ + 20 Х₂ ≤ 400 ,

10 Х₁ + 15 Х₂ ≤ 450 ,

Х₁   ≥ 0 ,

Х₂ ≥ 0 .

В первой строке выписана целевая функция - прибыль при выпуске Х₁ стульев и Х₂ столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х₁ и Х₂ . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х₁ = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х₁ положительно. Но невозможно представить себе отрицательный выпуск - Х₁ не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х₁ , а по вертикальной оси ординат - значения Х₂ . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х_{1 ,} Х₂) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х₁, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х₂, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на

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

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

0

Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х₁, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х₂, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х₁ , Х₂ ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений 

5 Х₁ + 20 Х₂ = 400 ,

10 Х₁ + 15 Х₂ = 450 .

Из первого уравнения: 5 Х₁ = 400 - 20 Х₂ , Х₁  = 80 - 4 Х₂ . Подставляем во второе уравнение:

10 (80 - 4 Х₂) + 15 Х₂ = 800 - 40Х₂  + 15 Х₂ = 800 - 25 Х₂ = 450,

следовательно, 25 Х₂ = 350, Х₂ = 14, откуда Х₁ = 80 - 4 х 14 = 80 -56 =24.

Итак, четвертая вершина четырехугольника - это (24, 14).

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

Целевая функция 45 Х₁ + 80 Х₂  принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45Х₁ + 80 Х₂  = 2200 проходит между прямыми ограничений 5 Х₁ + 20 Х₂ = 400 и 10 Х₁ + 15 Х₂ = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.