Линейное программирование в управлении

Размещено на http://www.allbest.ru/

Введение

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

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

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти пионерские работы была присуждена Нобелевская премия по экономике.

1. Область задач, использующих линейное программирование

Типичные варианты применения линейного программирования в управлении производством:

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

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

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

· управление технологическим процессом (сведение к минимуму выхода стружки при резке стали, отходов кожи или ткани в рулоне или полотнище);

· регулирование запасов (определение оптимального сочетания продуктов на складе или в хранилище);

· календарное планирование производства (составление календарных планов, минимизирующих издержки с учетом расходов на содержание запасов, оплата сверхурочной работы и заказов на стороне);

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

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

· календарное планирование транспорта (минимизация издержек подачи грузовиков под погрузку и транспортных судов к погрузочным причалам);

· распределения рабочих (минимизация издержек при распределении рабочих по станкам и рабочим местам);

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

1. рационального использования сырья и материалов;

2. задачи оптимального раскроя;

3. оптимизации производственной программы предприятий;

4. оптимального размещения и концентрации производства;

5. составления оптимального плана перевозок, работы транспорта (транспортные задачи);

6. управления производственными запасами;

7. и многие другие, принадлежащие сфере оптимального планирования.

линейный программирование управленческий метод

2. Алгоритм разработки управленческого решения с использованием линейного программирования

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

2) Далее на функцию накладывается ряд ограничений в виде системы линейных неравенств. Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.

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

4) Для построенной модели выбирается метод решения и с помощью него находится решение поставленной задачи.

Простейшим методом решения задачи линейного программирования является графический. Графический метод используется для получения решения задач, в которых участвуют в рассмотрении только две переменные. Графический метод довольно прост и нагляден. Он основан на геометрическом представлении допустимых решений задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлен выпуклым многоугольником, неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случае несовместности системы ограничений задачи ОДР является пустым множеством. При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи, существует бесконечное множество решений (альтернативный оптимум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.

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

Метод искусственного базиса применяется при наличии в ограничении знаков “равно”, “больше либо равно”, “меньше либо равно” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m, а в задачи минимизации - с положительными m. Таким образом, из исходной получается новая m - задача.

Если в оптимальном решении m - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении m - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

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

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

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

Особенности заключаются в наличии двух таблиц - основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу, называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи:

1. если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

2. коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

3. свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

4. матрица ограничений двойственной задачи получается путем транспортирования матрицы ограничений прямой задачи;

5. знаки неравенств в ограничениях изменяются на противоположные;

6. число ограничений прямой задачи равно числу переменных двойственной задачи, и наоборот.

Двойственную задачу выгоднее решать, чем прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений. [2, c 70-71]

Симплексный метод позволяет наряду с получением решения прямой задачи получать и решение двойственной задачи. Этот результат и лежит в основе двойственного симплексного метода решения задачи. Суть метода состоит в таком последовательном переборе угловых точек допустимого множества Q0двойственной задачи, при котором значение целевой функции возрастает, т. е. в применении симплексного метода к решению двойственной задачи. Будем предполагать, что задача невырождена, т. е. каждой угловой точке множества Q0 соответствует квадратная невырожденная система уравнений размерности m, матрицу которую и называют двойственным базисом прямой задачи. Вместе с тем двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными).

Отыскание решения задачи двойственным симплекс-методом включает в себя следующие этапы:

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р 0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)-и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия начиная со второго этапа.

Двойственный симплексный метод называют также методом последовательного уточнения оценок, поскольку угловые точки задачи, возникающие при итерациях, можно рассматривать как приближенные значения точной оценки у*, т. е. как приближенные оценки влияния условий задачи на величину минимума целевой функции. [2, c.87-92]

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

3. Линейное программирование: методы

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

- если имеется математическая определенность и количественная ограниченность между изучаемыми факторами и переменными величинами;

- если имеется взаимозаменяемость факторов благодаря последовательности расчетов;

- в случае если математическая логика совмещена с пониманием сущности явлений, которые изучаются.

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

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

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

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

Размещено на Allbest.ru