ЛП – введение

ЛП – введение

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

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

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

Исходное решение заменяют улучшенным, и продолжают такой процесс, пока либо дальнейшее улучшение становится невозможным, либо «стоимость» дальнейших вычислений слишком высока. Ввиду громоздкости и большой размерности такие методы реализуются на ЭВМ.

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

ЛП – наиболее изученный и широко применяемый метод исследования операций. Впервые идеи ЛП были изложены советским математиком Л.В.Канторовичем в 1939 г. в работе «Математические методы организации и планирования производства». В 1947 г. американский ученый Дж. Данциг опубликовал симлекс–метод решения оптимизационных задач, описываемых линейными моделями, а сам термин ЛП впервые появился в 1951 г. Развитие вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов и созданы программы решения задач ЛП.

ЛП – наиболее часто используемый метод оптимизации. Более 70% от общего числа оптимизационных методов составляют методы ЛП.

ЛП широко применяется при управлении сложными системами (отраслью промышленности, производственными процессами, запасами, транспортом, производственными предприятиями и т. п.).

ЛП используется для решения задач автоматизированного машиностроительного производства. Например, определение кратчайшего пути перемещения крана-штабелера в автоматизированном складе, последовательность обработки деталей на нескольких автоматических станках, планирование производства продукции, загрузка автоматизированного оборудования, задача о раскрое и т.д.

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

Линейные модели строятся при следующих допущениях:

1) пропорциональность, т.е. затраты ресурсов на производство вида продукции и вклад каждого продукта в целевую функцию прямо пропорциональны его уровню;

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

3) неотрицательность, т.е. объемы произведенной продукции не могут быть отрицательными величинами.

Два первых допущения обеспечивают строгую линейность целевой функции и ограничений.

Довольно часто задачи, которые описываются нелинейными моделями, аппроксимируются линейными моделями.

Задача ЛП описывается математической моделью следующего вида:

среди неотрицательных неизвестных, удовлетворяющих системе