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

Линейное программирование (ЛП) является одним из наиболее развитых и широко применяемых методов  исследования операций . Широкое использование методов ЛП при решении конкретных задач обусловлено значительным увеличением быстродействия и объема памяти вычислительных машин (более 70% от общего числа применяемых оптимизационных методов составляют методы ЛП).

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

Задачи ЛП часто встречаются  на практике, например, при решении  проблем, связанных с распределением ресурсов, планированием производства, организацией работ и т. д. Широкий  класс важнейших производственных задач поддается четкой математической формулировке, которая дает возможность  подходить к задачам с количественной стороны и решать их численными методами.

Задачами линейного программирования называются оптимизационные задачи, в которых ограничения представляются в виде линейных равенств или неравенств и целевая функция линейна.

В общем виде, когда количество неизвестных равно n, задача ЛП формулируется следующим образом:

среди неотрицательных неизвестных  , удовлетворяющих системе

определить такие, при которых линейная (целевая) функция

достигает своего наименьшего (наибольшего) значения.

Уравнения или неравенства  являются ограничениями задачи ЛП.

В канонической форме общая  задача ЛП имеет вид:

минимизировать (максимизировать)

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

  

где    - заданные постоянные величины;   - искомые переменные.

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

Для сокращения вычислений при решении задач ЛП разработаны  методы, которые отыскивают решение  шаг за шагом. Эти методы можно  разбить на две группы: универсальные, с помощью которых могут решаться любые задачи ЛП (симплекс-метод  Дж. Данцига, метод разрешающих множителей Л.В. Канторовича); специальные, применяемые для решения отдельных типов задач ЛП (распределительный метод, венгерский метод, метод потенциалов и т.д.).

Решение задачи ЛП включает следующие этапы:

1. определение переменных задачи;
2. определение ограничений в виде линейных уравнений или неравенств;
3. задание целевой функции, подлежащей минимизации или максимизации;
4. решение задачи каким-либо методом.

Наиболее простым методом  является графическое решение задач  ЛП, которое применяется в случае, когда в задачу входят только две  переменные.

 

1.  Графическое решение задач линейного программирования с двумя неизвестными

 

Задача ЛП с двумя неизвестными имеет следующий вид:

среди неизвестных  и , удовлетворяющих системе

            

найти такие, при которых целевая функция

              

достигает наименьшего (наибольшего) значения.

Так как система ограничений  представляет собой систему линейных неравенств, то множество ее решений  есть выпуклый многоугольник М, лежащий в первой четверти координатной плоскости (рис. 1).

Рис. 1

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

Если зафиксировать какое-нибудь значение функции Z=d, то получится линейное уравнение с двумя неизвестными графиком которого является прямая плоскости. При изменении d от до + прямая смещаясь параллельно самой себе (рис.1), при некотором значении   достигает многоугольника М и имеет с ним общую точку А (точка входа), а затем, пройдя многоугольник М, при некотором значении будет иметь с ним последнюю общую точку В (точка выхода).

Целевая функция  достигает наименьшего значения в точке входа А, а наибольшего значения в точке выхода В.

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

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

1. построить область решений системы ограничений;
2. построить прямую, соответствующую целевой функции;
3. параллельным переносом этой прямой найти точку входа или выхода (в зависимости от требования задачи):
4. определить координаты этой точки и вычислить в них значение целевой функции.

 

Пример 1

Выпускается два вида изделий А и Б. Предприятие располагает ресурсами: материальными до 300 единиц, финансовыми до 100 единиц, трудовыми до 200 единиц. Для изготовления одного изделия А необходимо 5 единиц материальных, 2 единицы финансовых и 2 единицы трудовых ресурсов, а изделия Б - 5 единиц материальных, 1 единица финансовых и 4 единицы трудовых ресурсов. Прибыль от реализации одного изделия А составляет 8 условных единиц, а изделия Б - 12 условных единиц. Требуется так спланировать объем выпуска продукции, чтобы прибыль была максимальной.

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

Первое ограничение получено из условия, что количество материальных ресурсов при производстве изделий А и Б не должно превышать имеющегося запаса 300 единиц. Второе и третье неравенства учитывают, что финансовые и трудовые ресурсы составляют соответственно не более 100 единиц и 200 единиц. Последние ограничения показывают, что количество изделий А и Б не должно быть отрицательным.

Целевая функция выражает прибыль от реализации производственной продукции и имеет вид

.

Таким образом, имеется задача ЛП, которая состоит в определении  оптимальных значений и являющихся неотрицательными числами, удовлетворяющих линейным неравенствам и дающих максимальное значение целевой функции.

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

Прямую  получаемую из первого неравенства, удобно провести, соединяя пару подходящих точек, например и , (рис. 2).

 

Рис. 2

 

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

Аналогично строятся прямые, получаемые из преобразованных второго и третьего неравенств. Условия неотрицательности переменных и ограничивают область их допустимых значений первым квадрантом.

Полученное таким образом  пространство решений - многоугольник АВСDO (заштрихован). Из всех допустимых решений нужно найти такое, при котором целевая функция принимает максимальное значение.

Чтобы найти оптимальное  решение, следует определить в каком  направлении возрастает целевая  функция Для этого фиксируем произвольное значение функции Z, например, Z=240, и построим прямую (штриховая линия на рис. 2). При параллельном перемещении прямой в направлении, увеличивающем значение функции Z до величины Z₁, получим, что точкой выхода будет вершина В многоугольника решений. Определим координаты точки В. Точка В есть результат пересечения прямых и , следовательно, ее координаты определяются из системы уравнений:

Решая эту систему, получим: ,

Вычислим значение целевой  функции  при этих значениях неизвестных:

Полученное решение означает, что для достижения максимальной прибыли, которая равна 640 условных единиц,, необходимо производить 20 единиц изделий А и 40 штук изделий Б.

Решение задачи ЛП можно  получить без построения прямой Z путем определения значения целевой функции в вершинах многоугольника:

в точке А при величина ,

в точке В при величина Z=640,

в точке С при величина Z=400.

Максимальное значение целевой  функции Z=640 условных единиц достигается в точке В,.

Проверим  использование  ресурсов для полученного решения. Подставляя полученные значения , в исходные неравенства, устанавливаем, что материальные и трудовые ресурсы используются полностью, а 20 единиц финансовых ресурсов остаются неиспользованными.

 

Пример 2

 

Предприятие выпускает два  вида изделий А и Б. На изготовление изделия А требуется 1 металлического листа, 2 м труб и 1 чел-ч (человеко час) трудозатрат. На изделие Б - 3,5 листа, 0,5 м труб 1 чел-ч трудозатрат. Имеется 350 листа, 240 м труб и 150 чел-ч трудозатрат. По плану требуется выпускать не менее 110 изделий, обеспечивая прибыль не менее 1400 единиц. Необходимо определить оптимальное число изделий каждого вида, обеспечивающее максимальную прибыль, если прибыль от реализации одного изделия А составляет 10 рублей, а от изделия Б - 20 рублей.

Пусть - число изделий А, а - число изделий Б. Прибыль от реализации изделий А составляет рублей, а от реализации изделий Б - рублей, т.е. необходимо максимизировать целевую функцию

.

Расход металлического листа  составляет труб трудозатрат Поэтому ограничения задачи имеют вид

Первые три неравенства  описывают ограничения по ресурсам, четвертое и пятое соответственно плановое задание по общему числу  изделий и ограничение по прибыли.

 

Рис. 3

 

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

Первое неравенство: прямую , задаваемую уравнением строим по точкам и Пробная точка (0, 0) удовлетворяет неравенству 0<350, т.е. она входит в искомую полуплоскость (отмечена стрелкой у прямой).

Второе неравенство: прямую 2, задаваемую уравнением строим аналогично - при и Точка (0, 0) принадлежит искомой полуплоскости.

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

Пересечение полуплоскостей дает выпуклый многоугольник ABCDE. Для нахождения максимума Z надо построить линию уровня целевой функции. Пусть Z=0, тогда уравнение линии уровня будет . Оно описывает прямую, проходящую через начало координат параллельно прямой , т. е. Прямую Z перемещаем параллельно самой себе до величины Z₁, т. е. до тех пор, пока она не выйдет из многоугольника. Получаем точку С, где пересекаются прямые:

Решая полученную систему  уравнений, находим оптимальное  решение - координаты точки С: , . Вычислим максимальное значение целевой функции

 рублей.

Замечание. Допустим, что в рассматриваемой задаче требовалось бы найти минимум целевой функции

.

В этом случае линия целевой  функции совпала бы с прямой , т.е. все точки отрезка АЕ являлись бы оптимальными решениями (бесчисленное множество решений).

 

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

 

Геометрический метод  решения задач ЛП достаточно прост  и нагляден для случая двух переменных. Подавляющее большинство производственных задач содержит значительно большее  число неизвестных и применение геометрического метода становится невозможным. Поэтому разработаны аналитические методы, которые легко алгоритмируются и позволяют решать задачи ЛП с произвольным количеством неизвестных, в том числе и на ЭВМ. В настоящее время основным общим методом решения задач ЛП является симплекс-метод, предложенный Дж. Данцигом.