КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Применение метода линейного программирования для решения задач управления
Фирма, работающая в условиях того или иного типа рынка, должна воспринимать его как общие условия своего функционирования и в соответствии с ними выстраивать общую линию (стратегию) поведения на рынке. Вместе с тем при реализации этой стратегии она может сталкиваться с множеством более или менее сложных проблем, которые также могут быть исследованы и решены с помощью соответствующих моделей. Так, если все факторы проблемы заданы однозначно, известны также взаимосвязи между ними и результирующими показателями, для разрешения производственных трудностей можно использовать модели, решение которых отыскивается с помощью метода линейного программирования (МЛП). Основная область применения МЛП - поиск оптимального распределения ограниченных ресурсов при наличии конкурирующих потребностей. Типичные ситуации, в которых можно применять линейное программирование: • составление номенклатуры товаров, запланированных к производству, минимизирующей общие издержки при ограничениях на трудовые ресурсы и уровни запасов; • определение оптимального маршрута доставки товаров, а в более общем случае - продвижения продукта по точкам технологической цепи; • определение оптимального сочетания продуктов на складе; • определение оптимального местоположения нового предприятия с учетом ограничений на расход кабеля или минимизации капитальных затрат; • распределение работников по рабочим местам для минимизации общих производственных издержек; • календарное планирование: составление календарных планов с учетом расходов на содержание запасов, оплату сверхурочных работ и заказов на стороне с целью минимизации затрат и т.д. В названии метода отражены его характерные особенности. Линейное — так как все компоненты модели представляются и виде линейных неравенств или уравнений. Программирование, так как отыскивается наилучшая программа действий при иных условиях и ограничениях. Метод линейного программирования, впервые сформулированный Л.В.Канторовичем, является одним из наиболее развитых методов исследования операций. Общий метод решения задач линейного программирования — симплекс-метод, который разработан американским ученым Дж.Данцигом. Общая задача линейного программирования может быть сформулирована следующим образом. Необходимо отыскать неизвестные х1, х2,..., , хj,..., хп> при которых достигается максимум (минимум) линейной функции (цели) задачи
где aij,bj,cj —заданные величины. Все ограничения представляют собой многогранник условий, существующий в m-мерном пространстве. Решение заключается в том, что одна из вершин выбирается в качестве опорной, а затем в соответствии с определенной процедурой на основе однотипных расчетов исследуются другие вершины многогранника условий так, чтобы решение на каждом шаге улучшалось (увеличивалось или уменьшалось значение целевой функции). Если задача имеет решение, то за конечное число итераций (без перебора всех вершин) можно найти наилучшее с точки фения выбранного критерия решение. Рассмотрим в общем виде задачу линейного программирования. Пусть планируется производство различных видов услуг У1, У2,.., Уп. Считается, что рынок предъявит спрос на каждую услугу в размере не больше, чем q1 q2,..., qn.. Для производства этих услуг требуются различные виды ресурсов R1,R2,..., Rm в количестве единиц не больше, чем b1 ,b2 ,...,bт.. Для производства услуги i-го вида требуется aij единиц-j-го вида ресурсов. При этом предполагается продавать услуги по ценам p1, а себестоимость единицы услуги е1, т.е. прибыль от каждой единицы услуги составит сi =pi,— еi. Таким образом, требуется произвести объем услуг, не превышающий спрос по каждой услуге так, чтобы получить максимум прибыли при имеющихся ресурсах. Модель задачи имеет следующий вид: 1) хi - количество услуг i-гo вида, подлежащее определению; 2)xi≥0; 3)xi≤qi. 4)В матричной форме
Найти оптимальные хi* (i=1, 2,..., п), которые удовлетворяют системе ограничений 1—4 и обращают в максимум целевую функцию Линейное программирование может применяться и для решения задач динамического характера, в которых рассматривается конечное число периодов времени, и результаты предыдущего периода определяют исходные параметры следующего. Несмотря на то, что по сути своей задачи линейного программирования относятся к классу детерминированных, в ряде случаев их можно использовать и для решения задач, постановка которых в явном виде содержит информацию вероятностного характера. Основной прием в этих ситуациях — постараться ввести соответствующие случайные изменения к эквивалентным детерминированным соотношениям, например, вместо распределения вероятностей появления различных значений случайной величины использовать средние значения. Метод линейного программирования имеет ограничения: линейность всех соотношений; необходимость в каждый момент времени оперировать только одним набором ограничений. Весьма часто влияние экономических факторов на результаты деятельности не может быть описано с помощью линейных соотношений, например, когда затраты на производство продукта растут медленнее, чем его объемы, или выручка от реализации продукта зависит от цены и спроса на продукт, который, в свою очередь, также зависит от цены. Для описания таких систем, когда эффективность системы возрастает или убывает непропорционально изменению масштабов производства, приходится прибегать к нелинейной формулировке ограничений или целевых функций. К задачам нелинейного программирования обычно относят задачи следующего типа: требуется оптимизировать f(х1, х2, ..., xi ..., xn,) при ограничениях: Естественно, за введение нелинейности в модели приходится платить дополнительную цену: увеличение объема вычислительных операций при том, что нельзя назвать два—три эффективных алгоритма, как в линейном программировании, для решения любых нелинейных задач. Весьма эффективный в одном случае алгоритм может оказаться совершенно непригодным в другом. Вместе с тем все большая доступность машинных программ решения нелинейных задач большой размерности, предназначенных для подготовки решений в сложных ситуациях, улучшающаяся подготовка руководителей и специалистов в области исследования операций способствует развитию теории нелинейного программирования и более широкому использованию в практических целях.
|