Математическое программирование

МАТЕМАТИЧЕСКОЕ  ПРОГРАММИРОВАНИЕ 

1. Задачи оптимизации при ограничениях–неравенствах. 

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

     В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции F(х₁, х₂, …, х_n) при условиях

     g_i(х₁, х₂, …, х_n)≤b, i=1, 2, ..., m. 

     F(х₁, х₂, …, х_n)→max

       

     где F(х₁, х₂, …, х_n), g_i – некоторые заданные функции,

     b_i – некоторые действительные числа. 

     Если  все функции g_i и F являются линейными относительно (х₁, х₂, …, х_n), то соответствующая задача называется задачей линейного программирования (ЗЛП).

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

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

     Система уравнений или неравенств g_i называется системой ограничений задачи.

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

      - эта совокупность называется  оптимальным планом.

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

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

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

     

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

     

       

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

     

     

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

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

     1. Задачи планирования производства.

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

     Введем  обозначения:

     a_ij – расход i–го ресурса на производство j–го товара

     c_j – прибыль, полученная от реализации единицы продукции j–го вида

      - план производства, где x_j - количество продукции j–го вида, предусмотренное планом (j=1,2,...,n);

     c_jx_j – прибыль, получаемая при выпуске x_j единиц продукции.

     Общая прибыль предприятия от реализации всех видов продукции может быть выражена суммой таких произведений:

     

     и является функцией цели данной задачи.

     a_ijx_j – количество ресурса j-го вида, затраченного на производство продукции j-го вида в количестве x_j.

     Суммарный расход i–го ресурса на производство всех видов продукции не должен превышать суммарный запас этого ресурса.

     

     Т.к. переменные x_i- это количество выпускаемой продукции, то должно выполняться условие неотрицательности переменных.

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

     

                                (1) 
 
 

     Задача  о диете. 

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

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

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

     Введем  обозначения:

     b_i – суточная норма i-го питательного вещества;

     a_ij – содержание i-го питательного вещества в единице j-го продукта;

     c_j – стоимость единицы j-го продукта;

      - общий рацион.

     Функция цели показывает общую стоимость  рациона

     

     a_ijx_j – потребление i-го питательного вещества в j-ом продукте.

     Суммарное потребление i–го питательного вещества (во всех продуктах) не должно быть меньше биологической нормы b_i.

     

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

     

                                 (2) 

     Транспортная  задача. 

     В m пунктах производится однородный продукт a_i, i=1,2,...,m, в n пунктах имеется потребность в этом продукте в количестве b_j, j=1,2,...,n.

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

     Требуется составить наиболее дешевый план перевозок от производителей к потребителям, удовлетворяющий следующим условиям:

• От каждого производителя должен быть вывезен весь произведенный продукт.
• Потребность каждого потребителя должна быть полностью удовлетворена.
• Не допускаются встречные перевозки.

     Введем  обозначение матриц перевозок и  тарифов:

      , где X – матрица перевозок

     x_ij - количество груза, перевезенного от поставщика к потребителю.

     Матрица тарифов:

     

     c_ij – тариф на перевозку груза от i-го поставщика к j-му потребителю.

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

     

     Условия:

     

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

     

     

     

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

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

     3.1. Графический метод. 

     Пусть дана математическая модель задачи линейного  программирования в виде (1). Допустимый план задачи можно представить как точку в пространстве Rⁿ. Д – область допустимых планов (Д).

     Множество оптимальных планов образует в пространстве Rⁿ область Д⁰ – область оптимального планирования.

     Множество точек пространства Rⁿ, координаты которых удовлетворяют линейному уравнению

     

     называется  гиперплоскостью.

     Гиперплоскость делит все пространство на две полуплоскости:

     - положительная Н⁺:

     - отрицательная Н^-:

     Линейные  функции цели в гиперпространстве  соответствуют гиперплоскости.

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

     Если  , то говорят о нулевом уровне функции цели.

     Уровень функции цели возрастает в направлении  градиента этой функции или нормали функции цели:

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

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

     Найдем  решение задачи:

     (1)

     (2)

     (3)

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

     (4) .

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

     Стороны этого многогранника лежат на прямых (4).

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