Математическое программирование: Линейное программирование. Постановка задач, методы решения

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

* математические модели очень большого числа экономических задач линейны относительно искомых переменных;

* эти типы задач в настоящее время наиболее изучены;

* для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

* многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;

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

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

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

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

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

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

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

В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х1 , х2 , … хn ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х1, х2, … хn
б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

        максимум или минимум целевой функции (критерий оптимальности);

        систему ограничений в форме линейных уравнений и неравенств;

        требование неотрицательности переменных.

Рассмотрим пример постановки ЗЛП.

Пусть имеется два станка (S1 , S2), на каждом из которых можно производить два вида продукции (P1, P2). Станок S1 производит единицу продукции P1 за 1 час, а единицу продукции P2 - за 2 часа. Станок S2 затрачивает на единицу продукции P1 - 2 часа, а на единицу продукции P2 - 1 час. Станок S1 может работать в сутки не более 10 ч., а станок S2 - не более 8 ч. Стоимость единицы продукции P1 составляет C1 руб., а стоимость единицы продукции P2 - C2 руб.

Требуется определить такие объемы выпуска продукции P1 и P2 на станок, чтобы выручка от реализации производственной продукции была максимальной.

Составим математическую модель задачи:

Обозначим через х1 и х2 количества продукции P1 и P2, которое планируется произвести на каждом отдельном станке. Стоимость произведенной продукции

F = c1х1 + c2 х2. Мы должны назначить х1 и х2 так, чтобы величина F была максимальной. Переменные х1, х2 не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции P1 станок S1 тратит 1x1 часов, а на изготовление продукции P2 – 2x2 часов. Поскольку время работы станка S1 не превосходит 10 ч, то величины х1 и х2 должны удовлетворять неравенству

x1 + 2x2≤ 10.

Аналогично можно получить неравенство для станка S2: 2x1 + x2 ≤ 8.

Кроме того, величины х1 , х2 не могут быть отрицательными: x1 ≥ 0, x2 ≥ 0, по смыслу задачи.

Такие задачи кратко записываются следующим образом:

                (2.1)

x1≥0, x2≥0                    (2.2)

F=c1x1+c2x2→max      (2.3)

Итак, математическая модель задачи: найти такой план выпуска продукции

Х = (х1, х2), удовлетворяющий системе (2.1) и условию (2.2), при котором функция (2.3) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (2.1) и требованиям неотрицательности (2.2), являются допустимыми, а решения, удовлетворяющие одновременно и требованию (2.3) оптимальными.

3. Методы решения задач линейного программирования

3.1. Графический метод решения ЗЛП

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

Графическое решение ЗЛП с двумя переменными и системой ограничений в виде линейных неравенств состоит из 2-х этапов:

1. Построение на плоскости множества решений системы линейных неравенств, являющегося выпуклым многогранным множеством.

2. Выбор в построенном множестве точки х*=(х1*, х2*), доставляющей целевой функции требуемое экстремальное (max или min) значение.

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

Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид

                                        (3.1)

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

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

Все вышесказанное относится и к случаю, когда система ограничений (3.1) включает равенства, поскольку любое равенство

можно представить в виде системы двух неравенств (см. рис. 3.1)

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см.рис. 3.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис. 3.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптимум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

Рисунок 3.1. Геометрическая интерпретация ограничений и ЦФ задачи.

3.1.1. Методика решения ЗЛП графическим методом

I.        В ограничениях задачи (3.1) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II.     Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (3.1). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства. Если  неравенство истинное, то    надо заштриховать полуплоскость, содержащую данную точку;               иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку. Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте. Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.

III.  Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.

IV. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V.    Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII.          Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

3.1.2. Применение графического метода решения ЗЛП на практике

Рассмотрим задачу: Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии  60 изделий, второй линии  80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели  10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определить оптимальные суточные объемы производства первой и второй моделей на основе графического метода решения задачи.