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

Страницы работы

Фрагмент текста работы

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

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

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

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

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

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


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

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

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

a11x+...+ a1nxn = b1;

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

am1 x1+...+ amnxn = bm,

          где  bi0, i = 1,..., m.

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

Z =c1x1+...+cnxn ,                                              2.2                                                                           

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

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

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

Z(x) = cxmin;                                  

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

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

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

Похожие материалы

Информация о работе