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

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

В самом общем виде эта задача записывается так:

Z = f (x)→max(min)      x ЄM, где х = (x₁, ... , х_n) - искомые переменные параметры; Z - целевая функция; М - область допустимых значений переменных x₁, .. , х_n. Область М представляет некоторую систему математических зависимостей (уравнений, неравенств), описывающих количественные характеристики переменных x_j(j = 1, ... , n) исвязи между ними.

Дополнительным   условием,    включаемым   в   математическое описание при   решении прикладных задач (проектирования, планирования производства, экономических и т.п.), является условие неотрицательности значений искомых переменных, в соответствии с которым все x_j ≥ 0.

С позиции математики это требование не является обязательным. Действительно, при решении задачи на минимум и целевая функция и входящие в нее переменные могут оказаться отрицательными. Однако, применительно к названным выше и другим прикладным задачам подобное решение, очевидно, будет неприемлемым. Кроме обязательного условия неотрицательности, при необходимости, на все или некоторые переменные x_j   могут накладываться дополнительные ограничения  на величины их значений, определяемые в результате решения. Это может быть, например, определенное задание по выпуску продукции  некоторого вида (x₁≤100 тонн) при планировании работы предприятия или задание надежности  проектируемого изделия (x₂  ≥0,8). Исходя из изложенного, данный вид ограничений определяют как граничные условия.

Математическое программирование включает такие разделы как линейное, нелинейное, целочисленное, стохастическое и другие программирования. Названные математические дисциплины отличаются друг от друга видом целевых функций Z и области М. Например, если f(x) и М - линейны, имеет место задача линейного программирования; в случае нелинейности Z или (и) М - задачи нелинейного программирования; при введении дополнительного условия целочисленности искомых переменных - задача целочисленного программирования. Стохастическое программирование представляет совокупность методов решения задач рассматриваемого класса вероятностного характера, где исходные и искомые параметры являются случайными величинами. Приведенную классификацию можно продолжить, так  как,  например, в нелинейном   программировании  выделяют  методы выпуклого, квадратичного, параметрического и других видов программирования, в алгоритмах которых учитываются особенности целевых функций и налагаемых ограничений.

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

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

Задана система m линейно независимых уравнений с n неизвестными  x_1,...,x_n, называемая системой ограничений задачи линейного программирования:

a₁₁x₁  +...+ a_1nx_n = b₁;

……………………………...                                      2.1                                                                                                                                

a_m1 x₁+...+ a_mnx_n = b_m,

          где  b_i≥0, i = 1,..., m.

Характерной особенностью задачи линейного программирования является то, что число уравнений в модели меньше числа неизвестных, т. е. m<n. Требуется найти неотрицательные значения переменных (x_j≥0,              j= 1, ..., n), которые удовлетворяют уравнениям 2.1 и обращают в минимум целевую функцию

Z =c₁x₁+...+c_nx_n ,                                              2.2                                                                           

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

Иногда стоит задача не минимизации линейной формы 2.2, а ее максимизации. Эта задача сводится к предыдущей путем перемены знака у переменной Z.                       

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

Z(x) = cx →min;                                  

Ax=b(b≥0), x≥0, где А — матрица коэффициентов размером m×n; b— m-мерный вектор свободных членов; х и с — n-мерные векторы искомых переменных и коэффициентов в целевой функции.

Сделаем несколько пояснений по поводу этой задачи. Система уравнений 2.1 для случая, когда число уравнений равно числу неизвестных (m=n), рассматривается в обычной алгебре. Если при этом определитель системы не равен нулю, то система имеет единственное решение, для нахождения которого имеются хорошо разработанные приемы. Если же число уравнений меньше числа неизвестных (m<n), то система уравнений 2.1 имеет бесчисленное множество решений, т. е. имеется бесконечное множество наборов переменных x_j, j=1,...,n, удовлетворяющих уравнениям   2.1. Каждый набор переменных x_j, j=1,...,n,, удовлетворяющий системе уравнений 2.1, является  решением этой системы.

Дополнительным условием является наложение на переменные x_j добавочного ограничения, состоящего в том, что эти переменные должны быть неотрицательными (x_j≥0). В общем случае имеется бесчисленное множество решений, удовлетворяющих этому добавочному условию. Любое решение системы 2.1 с неотрицательными значениями переменных  называется допустимым решением. Суть решения задачи линейного программирования состоит в том, чтобы