Линейное программирование – математический раздел, посвященный теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Впервые принципы новой отрасли математики под названием линейное программирование было предложены Л.В. Канторовичем в работе «Математические методы организации и планирования производства».
Метод линейного программирования дает возможность аргументировать наилучшее экономическое решение в обстоятельствах строгих ограничений, имеющих отношение к применяемым в изготовлении ресурсам (основные фонды, использованные материалы, рабочие средства). Использование данного метода в экономическом рассмотрении дает возможность регулировать проблемы, связанные главным образом с планированием работы компании. Этот метод может помочь установить подходящие величины выпуска продукта, а кроме того тенденции более результативного применения существующих в директиве компании производственных ресурсов.
Математическое программирование может использоваться и в отношении тех экономических явлений, взаимосвязь между которыми не считается линейной. Для данной цели могут быть применены методы нелинейного, динамического и выпуклого программирования.
Нелинейное программирование опирается на нелинейный характер целевой функции или ограничений, либо и того и другого. Формы целевой функции и неравенств ограничений в этих условиях могут быть различными.
Нелинейное программирование используется в экономическом анализе в частности, при установлении связи среди признаков, выражающих эффективность работы компании и размер данной работы, текстуру расходов в производстве, конъюнктуру торга и т.д.
Динамическое программирование основывается на концепции дерева заключений. Любой уровень данного дерева служит стадией для установления результатов прошлого постановления и для ликвидации неэффективных альтернатив данного постановления. Таким образом, динамическое программирование содержит многостадийный, многоэтапный вид. Данный тип программирования используется в экономическом анализе с целью отыскивания подходящих альтернатив формирования компании как в настоящее время, так и в будущем.
Выпуклое программирование предполагает собою разновидность нелинейного программирования. Данный тип программирования выражает нелинейный вид связи среди итогов работы компании и исполняемыми ею расходами. Выпуклое (по другому вогнутое) программирование исследует выпуклые целевые функции и выпуклые системы ограничений (точки допустимых значений). Выпуклое программирование используется в анализе хозяйственной деятельности с целью минимизации расходов, а вогнутое – с целью максимизации прибыли в обстоятельствах существующих ограничений воздействия условий, оказывающих большое влияние в рассматриваемых характеристиках противоположным образом. Следовательно, при анализируемых типах программирования выпуклые целевые функции минимизируются, а вогнутые-максимизируются.
Одним из основных методов линейного программирования является симплексный метод- это метод направленного перебора основных решений задачи. Он дает возможность за конечное число шагов расчета или отыскать наилучшее решение, или определить, то что рационального решения не существует.
Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности.
Рассмотрим данный метод на примере решения следующей задачи.
Предприятие ООО «Пшеница» предполагает выпускать два вида продукции: печенье и пряники, для производства которых используется сырьё трех видов: мука, сахар, дрожжи. Производство обеспечено сырьем каждого вида в количествах: 750, 807, 840 кг. На изготовление печенья требуется затратить сырья каждого вида 5, 4, 1 кг, соответственно, а для пряников – 2, 5, 7 кг. Прибыль от реализации печенья составляет 30 ден. ед., для пряников – 49 ден. ед.
Занесём необходимые нам данные во вспомогательную таблицу:
|
Вид сырья |
Продукция |
Ограничения по сырью |
|
|
печенье |
пряники |
||
|
мука |
5 |
2 |
750 |
|
сахар |
4 |
5 |
807 |
|
дрожжи |
1 |
7 |
840 |
|
прибыль |
30 |
49 |
|
Обеспечим точную формулировку проблемы. Пускай и – количество печенья и пряников, запланированных к изготовлению. Так как число материала согласно любому типу ограничено, то обязаны осуществляться соответствующие неравенства:
.
Данная система неравенств считается и концепцией ограничений этой проблемы. Целевая роль (линейная форма), выражающая доход компании, имеет вид
.
Итак, задача сводится к нахождению максимума функции 
при ограничениях:
Для сведения системы ограничений-неравенств к системе уравнений добавим к левосторонней части каждого неравенства добавочные неотрицательные переменные В условиях этой задачи они обладают определенной экономической сущностью, а именно высказывают размер остатков материала каждого типа уже после исполнения проекта согласно выпуску продукта. После внедрения добавочных переменных приобретаем систему уравнений:
Необходимо отыскать такое возможное базисное решение данной концепции ограничений, которое бы максимизировало линейную форму .
Решая задачу, приходим к следующему выводу.
.
Таким образом, для получения наибольшей прибыли, равной 7329 ден. ед., из данных запасов сырья предприятие должно изготовить 63 кг печенья и 111 кг пряников.
Итак, можно сказать, что линейное программирование играет важную роль в различных отраслях человеческой деятельности соединяя такие две совершенно разные науки, как экономика и математика. Именно здесь происходит тесное взаимодействие их между собой. Фактическое применение математики в экономических исследованиях, позволяющее объяснить прошлое, увидеть будущее и оценить результат своих действий, потребует значительных усилий, которых на данный момент в экономике не хватает.