Гл. 12. Линейное программирование
Минимизировать G:
У,
У2
| Продукт R: 2 |
| [ |
наличие RM1^ х (количество ^ + (наличие RM2 ^ х (количество ^ в неделю J у RM1(кг) J [ в неделю J у RM2 (кг) J
| У1 |
| У2 |
3.5
(RM1 (кг)") х (количество "\ + (RM2 (кг)") Ф (количество "\
[ для R J [ RM1 (кг) J [ для R J . [ RM2 (кг) J
(ф. ст. в неделю)
2 5 ф.ст.
прибыли
на единицу
Продукт Q: 3
1.5
| Уг |
| У1 |
^ 8 ф.ст.
Прибыли
На единицу
| ( |
RM1 ^ х (количество ^ + ( RM2 ^ х (количество ^ для Q (кг) J [ RM1 (кг) J [для Q (кг) J [ RM2 (кг) J
Данная задача является задачей минимизации. Необходимо уменьшить значение целевой функции настолько, насколько это возможно, следовательно, перемещение линии уровня целевой функции осуществляется параллельно ее исходному положению в направлении начала координат. Точка Z является последней крайней точкой допустимого множества, через которую проходит линия уровня, и, таким образом, оптимальным решением двойственной задачи. Z является пересечением линии ограничения для продукта Q и оси yj т.е.: Уг = 0
и Зу, + 1,5у2 = 8,
Следовательно,
У2 = 0 и У1 = 2 J .
Минимальная стоимость ресурсов в двойственной задаче имеет вид:
О 10 х 21 +12x0 = 26,67 ф. ст. в неделю.
Это значение совпадает со значением целевой функции прямой задачи.
Обобщая полученные решения, можно сделать вывод, что максимальное значение прибыли, равное 26,27 ф. ст. в неделю, достигается, если продукт Q
Выпускать в количестве 3 — кг, а продукт R не производить вообще. Стоимость
Сырья, т.е. теневые цены ресурсов, составила 2,67 ф. ст. за 1 кг RM1 и ноль для RM2. Эту же информацию можно было бы получить через проведение полного анализа только прямой задачи.
448 Ч. 4. Моделирование в бизнесе
РЕЗЮМЕ
Модели линейного программирования используются в решении проблемы распределения ограниченных ресурсов для достижения своих целей в бизнесе. Целью может являться максимизация прибыли за неделю или минимизация ежедневных издержек. Формулировка задачи линейного программирования требует последовательного выполнения следующих шагов:
Шаг 1. Определение переменных решения.
Шаг 2. Определение линейной целевой функции и линейных ограничений.
Шчг 3. Выражение целевой функции через переменные задачи.
Шаг 4. Выражение ограничений через переменные задачи.
При формулировке задач с'двумя или со множеством переменных применяется одна и та же процедура. Однако задачу с двумя переменными можно решить графически. Ограничения, которые обычно представлены неравенствами знака "5" или "£", изображаются на графике с помощью прямых и областей на плоскости. Каждое ограничение разделяет плоскость графика на допустимую и недопустимую области. Область, точки которой удовлетворяют всем ограничениям задачи, называется допустимым множеством. Допустимое множество содержит все возможные решения задачи.
Оптимальное решение, которое всегда находится в крайней точке допустимого множества, можно найти после нанесения на график линии уровня целевой функции. Целевая функция перемещается параллельно этой линии в направлении, противоположном началу координат, в случае максимизации целевой функции, или в сторону начала координат в случае ее минимизации. Координаты последней крайней точки, через которую проходит линия уровня перед тем, как она всецело окажется вне пределов допустимого множества, являются значениями переменных, которые оптимизируют целевую функцию задачи.
Поскольку практическая реализация модели может осуществляться в условиях неопределенности, большое место в линейном программировании занимает анализ чувствительности модели. Этот метод позволяет учесть вариацию и неопределенность коэффициентов целевой функции и значений правой части ограничений задачи.
Задачи линейного программирования со множеством переменных решаются на компьютерах с помощью симплекс-метода. Итоговая таблица алгоритма симплекс-метода содержит оптимальное значение целевой функции, соответствующие ему значения переменных решения и значения остаточных или избыточных переменных. Кроме того, в ней указываются теневые цены на ресурсы. Итоговую таблицу симплекс-метода можно использовать также в анализе чувствительности, чтобы выявить общее воздействие изменений в запасах лимитирующих ресурсов на целевую функцию и каждое из ограничений.
Для каждой исходной задачи линейного программирования существует ее двойственная формулировка. Решения прямой и двойственной задачи одинаковы. Двойственную модель можно получить непосредственно из исходной прямой модели, поменяв местами ее коэффициенты. Иногда более простая формулировка двойственной задачи дает существенные преимущества в процессе решения по сравнению со сложной постановкой прямой задачи.
Гл. 12. Линейное программирование 449