Использование линейного программирования в процессе принятия управленческих решений

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

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

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

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

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

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

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

     ОДР – это множество значений переменных X1,X2,...,Xn, удовлетворяющих ограничениям задачи. Для задач с двумя переменными ОДР представляет собой множество точек (X1; X2), т.е. некоторую область на плоскости (обычно – многоугольник). Для задач с тремя переменными ОДР представляет собой многогранник в пространстве, для задач с большим количеством переменных – некоторую область многомерного пространства. Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается в одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР. Поэтому задачу линейного программирования с двумя переменными можно решить следующим образом:

- построить  ОДР на плоскости в системе  координат (X1; X2),

- определить  все угловые точки ОДР,

- вычислить  значения целевой функции в этих точках и выбрать оптимальное решение.

     Решим графическим методом следующую  задачу: предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты  приносит предприятию прибыль в  размере 25 ден.ед., выпуск одной тонны серной кислоты – 40 ден.ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной кислоты и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

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

     Составим  математическую модель задачи. Для  этого введем переменные. Обозначим  через X1 количество выпускаемой соляной кислоты (в тоннах), через X2 – количество серной кислоты (в тоннах).

     Составим  ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить  не менее 200т. соляной кислоты. Это  ограничение можно записать следующим образом: X1 ≥ 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100т. серной кислоты: X2 ≥ 100.

     Составим  ограничение на опасные отходы. При  выпуске одной тонны соляной  кислоты образуется 0,5т. опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5·X1 т. При выпуске серной кислоты образуется 1,2·X2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5·X1 + 1,2·X2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение: 0,5·X1 + 1,2·X2 ≤ 600.

     Кроме того, переменные X1 и X2 по своему физическому  смыслу не могут принимать отрицательных  значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо указать ограничения неотрицательности): X1 ≥ 0, X2 ≥ 0.

     В данной задаче требуется определить выпуск кислот, при котором прибыль  будет максимальной. Прибыль от выпуска  одной тонны соляной кислоты  составляет 25 ден.ед.; значит, прибыль  от выпуска соляной кислоты составит 25·X1 ден.ед. Прибыль от выпуска серной кислоты составит 40·X2 ден.ед. Таким образом, общая прибыль от выпуска кислот составит 25·X1+40·X2 ден.ед. Требуется найти такие значения переменных X1 и X2, при которых эта величина будет максимальной.

     Таким образом, целевая функция для  данной задачи будет иметь следующий  вид:

E = 25·X1+40·X2 → max.

     Приведем  полную математическую модель рассматриваемой  задачи:

X1 ≥ 200

X2 ≥ 100 (1.3)

0,5·X1 + 1,2·X2 ≤ 600

X1 ≥ 0, X2 ≥ 0.

E = 25·X1+40·X2 → max.

     В этой задаче имеется два ограничения  “больше или равно” и одно ограничение  “меньше или равно”. Целевая  функция подлежит максимизации.

     Ограничение X1 ≥ 200 задается вертикальной линией X1=200. Все точки (X1; X2), расположенные справа от этой линии, удовлетворяют ограничению X1 ≥ 200, расположенные слева – не удовлетворяют. Ограничение X2 ≥ 100 задается горизонтальной линией X2=100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению X2 ≥ 100, расположенные снизу – не удовлетворяют.

     Для построения линии, задающей ограничение 0,5·X1 + 1,2·X2 ≤ 600, удобно записать его в виде равенства: 0,5·X1 + 1,2·X2 = 600. Выразим одну из переменных через другую: X2 = -0,417·X1 + 500. Это уравнение прямой. Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой – не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5·X1 + 1,2·X2 ≤ 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.

     Пересечение всех полуплоскостей, удовлетворяющих  ограничениям задачи, представляет собой  ОДР. На рис. 3 она выделена цветом.

     Рисунок 3. Решение задачи графическим методом

     Оптимальное решение находится в одной  из угловых точек ОДР (на рис.2 они  обозначены как A,B,C). Эти точки можно найти путем решения соответствующих систем из двух уравнений. Найдем значения целевой функции в этих точках:

E(A) = 25·200 + 40·100 = 9000;

E(B) = 25·200 + 40·416,67 = 21666,8;

E(C) = 25·960 + 40·100 = 28000.

     Таким образом, оптимальное решение находится в точке C=(960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 ден.ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5·960 + 1,2·100 = 600 т. 
 

Заключение

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

Шаг 1. Определение переменных решения.

Шаг 2. Определение линейной целевой функции и линейных ограничений.

Шаг 3, Выражение целевой функции через переменные задачи.

Шаг 4. Выражение ограничений через переменные задачи.

     При формулировке задач с двумя или  со множеством переменных применяется  одна и та же процедура. Однако задачу с двумя переменными можно  решить графически. Ограничения, которые обычно представлены неравенствами знака "Ј" или "і", изображаются на графике с помощью прямых и областей на плоскости. Каждое ограничение разделяет плоскость графика на допустимую и недопустимую области. Область, точки которой удовлетворяют всем ограничениям задачи, называется допустимым множеством. Допустимое множество содержит все возможные решения задачи.

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

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

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

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

Список  литературы

1. Аттетков А.В. и др. Методы оптимизации. М., 2001.
2. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. М., 2003.
3. Бусыгин А.В. Эффективный менеджмент. Управление как специфический тип профессиональной деятельности. М., 1999.
4. Вентцель Е.С. Исследование операций. М., 1972.
5. Зайцев М.Г., Варюхин С.Е. Методы оптимизации управления и принятия решений. М., 2008. 
6. Ларичев О.И. Теория принятия управленческих решений. М., 2002.
7. Литвак Б.П. Разработка управленческих решений. М., 2001.
8. Ременников В.Б. Управленческие решения. М., 2005.
9. Трояновский В.М. Математическое моделирование в менеджменте. М., 2002. 
10. Урубков А.Р., Федотов И.В. Методы и модели оптимизации управленческих решений. М., 2009.
11. Эддоус М., Стенсфилд Р. Методы принятия решений. М., 1997.
12. Юкаева В.С. Управленческие решения. М., 2002.