Метод линейного программирования

 

7.1.1. Общая характеристика метода

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

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

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

 

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

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

,

где .

При этом следует принимать во внимание принципиальные предположения о характере целевой функции и левых частей ограничений.

1. Целевая функция f(x₁, x₂, x₃,..., x_п) предполагается линейной относительно всех своих переменных, т.е. может быть представлена в форме .

2. Левые части ограничений являются линейными функциями относительно своих переменных х₁, х₂,..., х_n, могут быть представлены в форме

.

Переменные х₁, х₂,..., х_n могут принимать свои значения только из множества неотрицательных действительных чисел , т.е. .

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

, (7.1)

 

где множество допустимых альтернатив ∆β формируется системой ограничений типа равенств и неравенств:

. (7.2)

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

Задача минимизации линейной целевой функции при ограничениях типа равенств и неравенств может быть сведена к общей задаче линейного программирования вида (7.1), поскольку f(x) → min эквивалентно f(x) → mах. Именно поэтому, не ограничивая общности, в последующем, говоря о задачах линейного программирования, будем иметь в виду задачи максимизации линейных функций типа (7.1):

В случае отсутствия ограничений типа равенств, т.е. при q = 0, задача линейного программирования называется стандартной задачей линейного программирования, которая с учетом сделанных предположений, может быть записана в виде, где множество допустимых альтернатив ∆β формируется как ограничения типа неравенств:

(7.3)

и х₁, х₂,..., х_n >0.

С другой стороны, при отсутствии ограничения типа неравенств при q = m задача линейного программирования называется канонической основной задачей линейного программирования, которая с учетом сделанных предположений может быть записана в виде

где множество допустимых альтернатив ∆β формируется системой ограничений типа неравенств:

и х₁, х₂,..., х_n >0.

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

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

1. Система ограничений (7.3) противоречива или несовместна, т.е. не существует ни одного набора значений х₁, х₂,..., х_n, которые удовлетворяют ограничениям. В этом случае задача линейного программирования не имеет решения.

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

3. Система ограничений (7.3) не является противоречивой, и при этом соответствующая ей область пространства Rⁿ является ограниченной. В этом случае задача линейного программирования имеет решения.

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

 

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

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

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