Линейное программирование

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

В самом общем виде задачу Л.п. можно записать так. Даны ограничения типа

или в так называемой канонической форме, к которой можно привести все три указанных случая

Требуется найти неотрицательные числа x_j (j = 1, 2, …, n), которые минимизируют (или максимизируют) линейную форму

Таким образом, здесь представлена общая задача математического программирования с теми оговорками, что как ограничения, так и целевая функция — линейные, а искомые переменные — неотрицательны. Обозначения можно трактовать следующим образом: b_i — количество ресурса вида i; m — количество видов этих ресурсов; a_ij — норма расхода ресурса вида i на единицу продукции вида j; x_j — количество продукции вида j, причем таких видов — n; c_j — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции; нумерация ресурсов разделена на три части: от 1 до m₁, от m₁ + 1 до m₂ и от m₂ + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов; в первом случае — «не больше», во втором — «столько же», в третьем — «не меньше»; Z — в случае максимизации, например, объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т.п. Добавим еще одно обозначение, оно появится несколько ниже; v_i — оптимальная оценка i-го ресурса.

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

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

Рассмотрим две задачи Л.п. — на максимум и на минимум — на упрощенных примерах. Предположим, требуется разработать план производства двух видов продукции (объем первого — x₁; второго — x₂) с наиболее выгодным использованием трех видов ресурсов (наилучшим в смысле максимума общей прибыли от реализации плана). Условия задачи можно записать в виде таблицы (матрицы):

Вид продукции

Норма затрат на единицу продукции

Прибыль на единицу продукции

Исходя из норм, зафиксированных в таблице, запишем неравенства (ограничения):

a₁₁x₁ + a₁₂x₂ ≤ b_i

a₂₁x₁ + a₂₂x₂ ≤b₂

a₃₁x₁ + a₃₂x₂ ≤ b₃

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

x₁≥ 0, x₂≥ 0.

Требуется найти такие значения x₁ и x₂, при которых общая сумма прибыли, т.е. величина c₁ x₁ + c₂ x₂ будет наибольшей, или короче:

Удобно показать условия задачи на графике (рис. Л.2).

Рисунок 4 –Линейноепрограммирование,I

(штриховкой окантована область допустимых решений)

Любая точка здесь, обозначаемая координатами x₁ и x₂, составляет вариант искомого плана. Очевидно, что, например, все точки, находящиеся в области, ограниченной осями координат и прямой AA, удовлетворяют тому условию, что не может быть израсходовано первого ресурса больше, чем его у нас имеется в наличии (в случае, если точка находится на самой прямой, ресурс используется полностью). Если то же рассуждение отнести к остальным ограничениям, то станет ясно, что всем условиям задачи удовлетворяет любая точка, находящаяся в пределах области, края которой заштрихованы, — она называется областью допустимых решений (или областью допустимых значений, допустимым множеством).

Остается найти ту из них, которая даст наибольшую прибыль, т.е. максимум целевой функции. Выбрав произвольно прямую c₁x₁ + c₂x₂ = П и обозначив ее MM, находим на чертеже все точки (варианты планов), где прибыль одинакова при любом сочетании x₁ и x₂ (см. Линия уровня). Перемещая эту линию параллельно ее исходному положению, найдем точку, которая в наибольшей мере удалена от начала координат, однако не вышла за пределы области допустимых значений. (Перемещая линию уровня еще дальше, уже выходим из нее и, следовательно, нарушаем ограничения задачи). Точка M₀ и будет искомым оптимальным планом. Она находится в одной из вершин многоугольника. Может быть и такой случай, когда линия уровня совпадает с одной из прямых, ограничивающих область допустимых значений, тогда оптимальным будет любой план, находящийся на соответствующем отрезке.

Координаты точки M₀ (т.е. оптимальный план) можно найти, решая совместно уравнения тех прямых, на пересечении которых она находится.

Противоположна изложенной другая задача Л.п.: поиск минимума функции при заданных ограничениях. Такая задача возникает, например, когда требуется найти наиболее дешевую смесь некоторых продуктов, содержащих необходимые компоненты (см. Задача о диете). При этом известно содержание каждого компонента в единице исходного продукта — a_ij, ее себестоимость — c_j ; задается потребность в искомых компонентах — b_i.

Эти данные можно записать в таблице (матрице), сходной с той, которая приведена выше, а затем построить уравнения как ограничений, так и целевой функции. Предыдущая задача решалась графически. Рассуждая аналогично, можно построить график (рис. Л.3), каждая точка которого — вариант искомого плана: сочетания разных количеств продуктов x₁ и x₂.

Рисунок 5 –Линейноепрограммирование,II

Область допустимых решений здесь ничем сверху не ограничена: нужное количество заданных компонентов тем легче получить, чем больше исходных продуктов. Но требуется найти наиболее выгодное их сочетание. Пунктирные линии, как и в предыдущем примере, — линии уровня. Здесь они соединяют планы, при которых себестоимость смесей исходных продуктов одинакова. Линия, соответствующая наименьшему ее значению при заданных требованиях, — линия MM. Искомый оптимальный план — в точке M₀.

Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л.п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве (выпуклый многогранник).

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

Разработан целый ряд вычислительных приемов, позволяющих решать на ЭВМ задачи линейного программирования, насчитывающие сотни и тысячи переменных, неравенств и уравнений. Среди них наибольшее распространение приобрели методы последовательного улучшения допустимого решения (см. Симплексный метод, Базисное решение), а также декомпозиционные методы решения крупноразмерных задач, методы динамического программирования и др. Сама разработка и исследование таких методов — развитая область вычислительной математики.

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

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