Линейная оптимизация. Обобщённый алгоритм решения задачи линейной оптимизации (линейного программирования)

Линейная  оптимизация

            Задача  линейной  оптимизации характеризуется тем, что целевая функция L()  и ограничения в виде равенств и/или неравенств  (= (x₁,…,x_n) – вектор переменных) – линейные. При этом в своей исходной постановке  задача  линейной оптимизации может характеризоваться тем, что требуется отыскать либо минимум, либо максимум целевой функции, а в качестве ограничений могут выступать линейные равенства и  неравенства одновременно.

         Примером задачи линейной  оптимизации является так называемая задача о ресурсах (об использовании сырья): предприятия изготавливают n видов продукции  с использованием m видов сырья. Запасы  сырья  ограничены и  составляют  b_i  единиц (i = ). Количество сырья, необходимое для изготовления единицы продукции каждого вида, задаётся матрицей А =  (i = ; j = ). Доход, получаемый предприятием от реализации одной единицы продукции каждого вида, равен c_j. Необходимо составить такой план выпуска продукции n видов (т.е. сколько и чего производить), чтобы доход предприятия от её реализации был максимальным.

       В этом случае формальная постановка задачи оптимизации выглядит следующим образом. Если x_j – число единиц продукции j-го вида, то, очевидно, что на их производство не может быть потрачено больше, чем b_i единиц сырья i-го вида. Поэтому  ограничения примут вид

                                                     (),

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

                                                    .

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

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

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

        Так, если в системе ограничений присутствует неравенство, у которого левая часть меньше правой, т.е. неравенство вида

                                             a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n ≤ b_i,

то к его левой части необходимо прибавить неотрицательную величину x_n+i. В таком случае данное неравенство преобразуется в уравнение

                                             a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n + x_n+i  = b_i.

Аналогично, если в системе ограничений присутствует неравенство, у которого левая часть больше правой, т.е. неравенство вида

                                             a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n ≥ b_i,

то из его левой части необходимо вычесть неотрицательную величину x_n+i . В таком случае данное неравенство преобразуется в уравнение

                                             a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n – x_n+i  = b_i.

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

       Тогда задачу линейного программирования в канонической форме можно сформулировать так: найти такие неотрицательные значения переменных x₁, x₂, …, x_n, которые  удовлетворяют ограничениям

a₁₁x₁ + a₁₂x₂ + … + a_1jx_j +… + a_1nx_n = b₁;

 a₂₁x₁ + a₂₂x₂ + … + a_2jx_j + … + a_2nx_n = b₂;

…………………………………………

a_j1x₁ + a_j2x₂ + … + a_ijx_j + … + a_inx_n = b_i;

                              …. …………………………………….                             (1)

    a_m1x₁ + a_m2x₂ + … + a_mjx_j + … + a_mnx_n = b_m

и обращают в минимум целевую функцию

                                L() = c₁x₁ + c₂x₂ + … + c_jx_j + … + c_nx_n.                              (2)

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

      В такой постановке задача линейной оптимизации называется основной задачей линейного программирования (ОЗЛП).

      Следует отметить, что при m = n данная задача имеет единственное решение и с точки зрения выбора решения не имеет смысла (т.е. по сути, не является оптимизационной). При m < n задача имеет множество решений и, следовательно, существует возможность выбора наилучшего (оптимального) решения.