Общая постановка задачи линейного программирования

Сферы применения линейного моделирования

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

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

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

Задача линейного программирования, формы ее записи, способы преобразования

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

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

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

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

Замечание. max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].

В том случае, когда требуется найти минимум  функции  , можно перейти к нахождению максимума функции , поскольку min F(x) = – max[– F(x)].

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

Чтобы перейти  от одной формы записи задачи линейного  программирования к другой, нужно уметь,

во-первых, сводить задачу минимизации функции к задаче максимизации;

во-вторых, переходить от ограничений - неравенств к ограничениям - равенствам и наоборот;

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

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

В то же время  каждое уравнение системы ограничений можно записать в виде неравенств: или .

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений - неравенств в ограничения-равенства равно числу преобразуемых неравенств.

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

Отметим, наконец, что если переменная , не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными и , приняв .

Целевая функция и ее оптимизация

Функцию, экстремальное  значение которой нужно найти  в условиях экономических возможностей, называют целевой или критерием оптимальности. 

Экономические возможности  формализуются в виде системы ограничений. 

Все это составляет математическую модель. 

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

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

Наилучший вариант доставляет целевой функции экстремальное  значение.

Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.;

Область решения системы неравенств

Графически способ решения  задач линейного программирования целесообразно использовать:

1. Для решения задач  с двумя переменными, когда  ограничения выражены неравенствами;

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

Запишем задачу линейного  программирования с двумя переменными:

целевая функция (ЦФ):         (1)

ограничения:            (2)

                                  , .         (3)

Каждое из неравенств (2) – (3) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми , ; ; .

В том случае, если система  неравенств (2) – (3) совместна, область  ее решений есть множество точек, принадлежащих всем указанным полуплоскостям.

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

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

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

Областью допустимых решений  системы неравенств (2) – (3) может  быть:

выпуклый многоугольник;

выпуклая многоугольная  неограниченная область;

пустая область;

луч;

отрезок;

единственная точка.

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

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

Суть графического метода заключается в следующем.

По направлению (против направления) вектора  в ОДР производится поиск оптимальной точки .

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

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

При поиске оптимального решения задач ЛП возможны следующие  ситуации:

существует единственное решение задачи;

существует бесконечное  множество решений (альтернативный оптимум);

ЦФ не ограничена;

область допустимых решений  – единственная точка;

задача не имеет решений.

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

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

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

Координаты указанной  точки определяют оптимальный план данной задачи.

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

Для практического решения  задачи линейного программирования (1) – (3) на основе ее геометрической интерпретации необходимо следующее:

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2) – (3) знаков неравенств на знаки равенств.

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

3. Определить многоугольник решений.

4. Построить вектор .

5. Построить прямую , проходящую через начало координат и перпендикулярную вектору .

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

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

Оптимальный и допустимый планы, задачи линейного программирования

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

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

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

Решение ЗЛП в экономике и управлении используется как инструмент оптимизационного моделирования следующих задач:

• нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);
• оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);
• определение оптимального рациона (оптимизация состава химической смеси);
• транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);
• задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции);
• задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

Понятие опорной прямой

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

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

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

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

Граничные точки образуют границу данного множества.

Замкнутым называют множество, содержащее все свои граничные точки.

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

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

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

Замкнутый ограниченный выпуклый многоугольник является выпуклой линейной комбинацией своих   угловых точек.

Пересечение любого числа  выпуклых множеств есть множество выпуклое (если только оно непустое).

Компания "Краски" производит краску для внутренних и наружных работ из сырья двух типов: и .

Следующая таблица представляет основные данные для задачи.

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

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

1. Переменные, которые следует определить.

2. Целевая функция, подлежащая оптимизации.

3. Ограничения, которым должны удовлетворять переменные.

Определение переменных —  первый шаг в создании модели. После  определения переменных построение ограничений и целевой функции  обычно не вызывает трудностей.

В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ.

Обозначим эти объемы как  переменные модели: — ежедневный объем производства краски для наружных работ; — ежедневный объем производства краски для внутренних работ.

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

В соответствии с целями компании получаем задачу:

Максимизировать .

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

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

Из таблицы с данными  имеем следующее.

Используемый объем  сырья  (т)

Используемый объем  сырья  (т)

Так как ежедневный расход сырья  и ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.

(сырье  )

     (сырье )

Существует еще два  ограничения по спросу на готовую  продукцию:

(1) максимальный ежедневный  объем производства краски для  внутренних работ не должен  превышать 2 т и (2) ежедневный  объем производства краски для  внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на одну тонну.

Первое ограничение  простое и записывается как  .

Второе можно сформулировать так: разность между ежедневными  объемами производства красок для внутренних и наружных работ не должна превышать одной тонны, т.е. .

Еще одно неявное ограничение  состоит в том, что переменные и должны быть неотрицательными.

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

Окончательно задача будет  записана следующим образом:

Максимизировать при выполнении ограничений

,

,

,

, .

Любое решение, удовлетворяющее  ограничениям модели, является допустимым. Например, решение и будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности.

Значение целевой функции при этом решении будет равно (тысяч руб.).

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

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

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

Следовательно, необходима эффективная процедура отбора допустимых решений для поиска оптимального.