Понятие линейного программирования. Общая форма представления задачи линейного программирования (ЗЛП)

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

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

Для случая n независимых переменных  ЗЛП имеет вид:

Целевая функция:

                                    (3.4)

при ограничениях:

                                           (3.5)

 и дополнительных ограничениях:

,                                                                          (3.6)

 где  - некоторые заданные величины в соответствии с условием задачи.

Другая форма записи:

Экономическая интерпретация ЗЛП состоит в следующем. Имеется несколько видов производственной деятельности - j (), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы, запасы которых составляют величины – b_i . Расход i – го ресурса на единицу продукта j – го вида производственной деятельности равен – a_ij. При таком потреблении результат j – го вида производственной деятельности для единицы соответствующего продукта (удельная стоимость или прибыль) характеризуется величиной c_j.

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

Основными допущениями, принимаемыми при построении математических моделей ЗЛП, являются: 1) пропорциональность; 2) аддитивность; 3) неотрицательность. Первые два допущения вытекают из свойства линейности функций и предполагают следующее.

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

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

Неотрицательность следует из экономического смысла ЗЛП: ни по  одному из видов производственной деятельности переменные   x_j  (будь то выпуск продукции, время работы предприятия и т.д.) не могут быть отрицательными.

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