Решение

1. Производится x₁ кг продукта R и x₂ кг продукта Q в неделю. Максимизируется полученная за неделю прибыль Р (ф. ст.), где

Р = 5 x₁ + 8x₂ (ф. ст. в неделю)

в условиях следующей системы ограничений:

RM1: 2 x₁ + 3 x₂ 10 кг в неделю;

RM2: 3,5 x₁ + 1,5 x₂ 12 кг в неделю:

x₁, x₂ 0.

2. Используя формулировку прямой модели, построим двойственную модель. Минимизировать G = 10 у₁ + 12 у₂ (ф. ст. в неделю) в условиях следующей системы ограничений:

Продукт R: 2 у₁ + 3,5 у₂ 5 ф. ст. за единицу:

Продукт Q: 3 у₁ + 1,5 у₂ 8 ф. ст. за единицу;

y₁, y_{2 0}

3. Прямая модель. Переменные модели — это количество каждого продукта, которое необходимо производить каждую неделю. Целевая функция задачи - это общая прибыль, получаемая в неделю от производства продуктов R и Q. Каждое ограничение соответствует одному виду сырья. Левая часть каждого ограничения представляет собой общее количество сырья одного вида, требуемое для производства обоих продуктов. Правая часть ограничений содержит общее количество сырья каждого вида, которое фирма может использовать в течение недели.

Двойственная модель. Переменные модели — это теневые цены ресурсов для прямой модели, т.е. величины, на которые увеличилось бы значение целевой: функции при росте имеющегося запаса сырья соответствующего вида на единицу. Теневые цены характеризуют стоимость единицы сырья каждого вида. Целевая функция задачи — это общая еженедельная стоимость всех видов сырья, используемых при производстве R и Q. Каждое ограничение связано с одним из продуктов. В левой части каждого ограничения дана общая стоимость всех видов сырья, используемых при выпуске 1 кг соответствующего продукта; в правой - прибыль от выпуска единицы соответствующего продукта. Обратимся вновь к формулировке двойственной модели и попытаемся дать интерпретацию отдельным ее компонентам (см. стр. 41).

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

4. Графическое решение прямой задачи приведено на рис. 1.28.

Оптимальным решением задачи является точка А, лежащая на пересечении ограничения на сырье 1 и оси Q. Чтобы получать максимальную прибыль, следует производить только продукт Q в количестве 3 кг. При этом RM1 будет использоваться полностью, а RM2 — нет. Максимальная прибыль составит: 3 х 8 = 26,67 ф. ст. в неделю. Ниже приводится графическое решение двойственной задачи (рис.1.29).

Минимизировать G:

Продукт R:

Продукт Q:

Данная задача является задачей минимизации. Необходимо уменьшить значение целевой функции настолько, насколько это возможно, следовательно, перемещение линии уровня целевой функции осуществляется параллельно ее исходному положению в направлении начала координат. Точка Z является последней крайней точкой допустимого множества, через которую проходит линия уровня, и, таким образом, оптимальным решением двойственной задачи. Z является пересечением линии ограничения для продукта Q и оси y₁ т.е.: y₂ = 0.

И 3у₁ + 1,5у₂ = 8, следовательно, y₂ = 0 и y₁ = 2 .

Минимальная стоимость ресурсов в двойственной задаче имеет вид:

G= 10 х 2 +12х0 = 26,67 ф. ст. в неделю.

Это значение совпадает со значением целевой функции прямой задачи.

Обобщая полученные решения, можно сделать вывод, что максимальное значение прибыли, равное 26,27 ф. ст. в неделю, достигается, если продукт Q выпускать в количестве 3 кг, а продукт R не производить вообще. Стоимость сырья, т.е. теневые цены ресурсов, составила 2,67 ф. ст. за 1 кг RM1 и ноль для RM2. Эту же информацию можно было бы получить через проведение полного анализа только прямой задачи.

РЕЗЮМЕ

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

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

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

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

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

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

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

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

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

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