Методы линейного программирования

Введение

Линейное программирование или сокращенно ЛП (Linear Programming,
LP) – это раздел более общей теории математического программирования
(Mathematical Programming, MP). Математическое программирование
занимается изучением проблем принятия решений, которые могут быть
математически сформулированы как задачи нахождения максимума
(минимума) некоторой, вообще говоря, нелинейной функции (целевой
функции) многих переменных, при заданной системе ограничений на
основные переменные задачи.
Методы линейного программирования применяются для решения
многих экстремальных задач, с которыми довольно часто приходится иметь
дело в экономике. Решение таких задач сводится к нахождению крайних
значений (максимума и минимума) некоторых функций переменных
величин.
Линейное программирование основано на решении системы линейных
уравнений (с преобразованием в уравнения и неравенства), когда
зависимость между изучаемыми явлениями строго функциональна. Для него
характерны математическое выражение переменных величин, определенный
порядок, последовательность расчетов (алгоритм), логический анализ.
Применять его можно только в тех случаях, когда изучаемые переменные
величины и факторы имеют математическую определенность и
количественную ограниченность, когда в результате известной
последовательности расчетов происходит взаимозаменяемость факторов,
когда логика в расчетах, математическая логика совмещаются с логически
обоснованным пониманием сущности изучаемого явления.
С помощью этого метода в промышленном производстве, например,
исчисляется оптимальная общая производительность машин, агрегатов,
поточных линий (при заданном ассортименте продукции и иных заданных
величинах), решается задача рационального раскроя материалов (с
оптимальным выходом заготовок). В сельском хозяйстве он используется для

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

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

экономических задач

Линейное программирование – математический раздел, посвященный
теории и методам решения экстремальных задач на множествах -мерного
векторного пространства, задаваемых системами линейных уравнений и
неравенств. Впервые принципы новой отрасли математики под названием
линейное программирование было предложены Л.В. Канторовичем в работе
«Математические методы организации и планирования производства».
Метод линейного программирования дает возможность
аргументировать наилучшее экономическое решение в обстоятельствах
строгих ограничений, имеющих отношение к применяемым в изготовлении
ресурсам (основные фонды, использованные материалы, рабочие средства).
Использование данного метода в экономическом рассмотрении дает
возможность регулировать проблемы, связанные главным образом с
планированием работы компании. Этот метод может помочь установить
подходящие величины выпуска продукта, а кроме того тенденции более
результативного применения существующих в директиве компании
производственных ресурсов.
Математическое программирование может использоваться и в
отношении тех экономических явлений, взаимосвязь между которыми не
считается линейной. Для данной цели могут быть применены методы
нелинейного, динамического и выпуклого программирования.
Нелинейное программирование опирается на нелинейный характер
целевой функции или ограничений, либо и того и другого. Формы целевой
функции и неравенств ограничений в этих условиях могут быть различными.
Нелинейное программирование используется в экономическом анализе
в частности, при установлении связи среди признаков, выражающих
эффективность работы компании и размер данной работы, текстуру расходов
в производстве, конъюнктуру торга и т.д.