Оптимальное смешение. Цели

Модели

Введем обозначения:

п — количество выпускаемых продуктов;

т — количество используемых производственных ресурсов (на­пример, производственные мощности, сырье, рабочая сила);

а_ij — объем затрат i-го ресурса на выпуск единицы j-й продук­ции;

с_j — прибыль от выпуска и реализации единицы j-го продукта;

b_i — количество имеющегося i-го ресурса;

х_j — объем выпуска j-го продукта.

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

(1)

(2)

(3)

Здесь (1) — целевая функция (максимум прибыли);

(2) — система специальных ограничений (constraint) на объем фактически имеющихся ресурсов;

(3) — система общих ограничений (на неотрицательность переменных);

х_j — переменная (variable).

Задача (1)—(3) называется задачей линейного программирования в стандартной форме на максимум.

Задача линейного программирования в стандартной форме на ми­нимум имеет вид

(4)

(5)

(6)

Вектор х = (x₁, x₂, ..., x_n), компоненты х_j которого удовлетво­ряют ограничениям (2) и (3) (или (5) и (6) в задаче на минимум), называется допустимым решением или допустимым планом задачи ЛП.

Совокупность всех допустимых планов называется множеством допустимых планов.

Допустимое решение задачи ЛП, на котором целевая функция (1) (или (3) в задаче на минимум) достигает максимального (минималь­ного) значения, называется оптимальным решением задачи ЛП.

С каждой задачей ЛП связывают другую задачу ЛП, которая записывается по определенным правилам и называется двойствен­ной задачей ЛП.

Двойственной к задаче ЛП (1)—(3) является задача

Соответственно, двойственной к задаче ЛП (7)—(9) является задача (1)—(3). Каждой переменной (специальному ограничению) исходной задачи соответствует специальное ограничение (пере­менная) двойственной задачи. Если исходная задача ЛП имеет решение, то имеет решение и двойственная к ней задача, при этом значения целевых функций для соответствующих оптимальных решений равны.

Компонента оптимального решения двойственной задачи (7)—(9) называется двойственной оценкой (Dual Value) ограничения исходной задачи ЛП.

Пусть j = max ( ), где х_j — компонента допустимого решения задачи (1)—(3).

Тогда при выполнении условий невырожденности оптималь­ного решения имеют место следующие соотношения:

Изменим значение правой части b_i одного основного ограни­чения (RHS) исходной задачи ЛП.

Пусть — минимальное значение правой части основного ограничения, при котором решение у* двойственной задачи не из­менится. Тогда величину называют нижней границей (Lower Bound) устойчивости по правой части ограничения.

Пусть — максимальное значение правой части основного ограничения, при котором решение y* двойственной задачи не из­менится. Тогда величину называют верхней границей (Upper Bound) устойчивости по правой части ограничения.

Изменим значение одного коэффициента с_j целевой функции исходной задачи ЛП.

Пусть — минимальное значение коэффициента целевой функ­ции, при котором оптимальное решение x* исходной задачи не изменится. Тогда величину называют нижней границей устой­чивости по коэффициенту целевой функции.

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

Примеры. Пример 1. Сколько производить?

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

Вопросы:

1. Сколько продукта 1 следует производить для того, чтобы обеспечить максимальную прибыль?

2. Сколько продукта 2 следует производить для того, чтобы обеспечить максимальную прибыль?

3. Какова максимальная прибыль?

4. На сколько возрастет максимальная прибыль, если запасы сырья увеличатся на 1 т?

5. На сколько возрастет максимальная прибыль, если допус­тимый объем трудозатрат увеличится с 400 до 500 ч?

Решение. Пусть х₁ — объем выпуска продукта 1 в тоннах, х₂ — объем выпуска продукта 2 в тоннах. Тогда задача может быть опи­сана в виде следующей модели линейного программирования:

Используя пакет РОМ for WINDOWS (далее - POMWIN), ис­ходную информацию для решения этой задачи можно представить в виде следующей таблицы:

Решая эту задачу, получаем следующий результат:

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

Чтобы обеспечить максимальную прибыль, следует произво­дить 16,47 т продукта 1 и 14,12 т продукта 2.

Максимальная прибыль равна 988,24 тыс. руб.

В правом столбце таблицы указаны двойственные оценки для каждого ограничения. Так, величина 3,82 показывает, что при увеличении запаса сырья на 1 т (до 121) максимальное значение целевой функции для нового оптимального плана увеличится по сравнению с 988,24 на 3,82 тыс. руб. Аналогично можно интер­претировать значение двойственной оценки 1,32 для второго ре­сурса.

Следующая таблица содержит дополнительную информацию, предоставляемую пакетом POMWIN:

Два правых столбца таблицы — границы устойчивости по зна­чениям коэффициентов целевой функции (верхняя часть табли­цы) и правых частей ограничений (нижняя часть).

Так, в случае если прибыль, получаемая от реализации 1 т про­дукта 1, изменится, но останется в пределах от 21 до 40,83, коли­чество продукта 1 в оптимальном плане не изменится.

В случае если запас сырья изменится, но останется в пределах от 85,71 до 166,66, двойственная оценка этого ресурса не изменится.

Соответственно, если допустимый объем трудозатрат изменит­ся в пределах от 288 до 560 ч, двойственная оценка этого ресурса не изменится.

Если допустимый объем трудозатрат увеличится с 400 до 500 ч, то максимальная прибыль увеличится на 132 тыс. руб.

Пример 2. Производить или покупать?

Фирма производит два типа химикатов. На предстоящий ме­сяц она заключила контракт на поставку следующего количества этих химикатов:

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

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

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

Вопросы:

1. Сколько химикатов типа 1 следует производить фирме?

2. Сколько химикатов типа 2 следует производить фирме?

3. Сколько химикатов типа 1 следует закупать со стороны?

4. Сколько химикатов типа 2 следует закупать со стороны?

5. Каковы минимальные издержки на выполнение контракта?

6. Следует ли изменить объем закупок химикатов типа 2 со стороны, если их цена возрастет до 75 тыс. руб. за тонну?

7. На сколько возрастут минимальные издержки, если фонд времени работы реактора 2 сократится с 400 до 300 ч?

Решение. Введем обозначения:

x₁— количество продукта 1, производимого компанией;

z₁ — количество продукта 1, закупаемого компанией;

x₂ — количество продукта 2, производимого компанией;

z₂ — количество продукта 2, закупаемого компанией.

Модель линейного программирования приведена в следующей таблице:

Условия неотрицательности переменных: ; ; ; .

Таблица исходной информации для расчетов в POMWIN имеет следующий вид:

Результаты расчетов:

Таблица двойственных оценок и границ устойчивости:

Из таблицы двойственных оценок и границ устойчивости вид­но, что в пределах изменения закупочной цены на химикат типа 2 от 61 до 76 (ее фактическое значение 66) оптимальный план не изменится.

Из таблицы также видно, что изменение ресурса времени ра­боты реактора 2 в пределах от 225 до 765 не приведет к измене­нию двойственной оценки соответствующего ограничения.

Ответы: 1. 55,55 т. 2. 38,89 т. 3. 44,44 т. 4. 81,11 т.

5. 11 475,56 тыс. руб. 6. Нет, не следует.

7. Ha 111 тыс. руб.

Оптимальное смешение. Цели

В данной главе показаны возможности использования модели линейного программирования для решения задач оптимального сме­шения. Наряду с рассмотренной в главе 1 задачей планирования производства это одна из наиболее известных областей приложе­ния модели линейного программирования. Модели оптимально­го смешения имеют много общего с моделями оптимального пла­нирования производства. В то же время существуют и некоторые особенности.

После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь формулировать и использовать для эконо­мического анализа следующие понятия:

• смесь;

• ингредиент смеси;

• компонент смеси;

• рецепт смешения.

Модели

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

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

Рассмотрим сначала однопродуктовые модели оптималь­ного смешения.

Введем обозначения:

п — количество исходных ингредиентов;

т — количество компонентов в смеси;

х_j — количество j-го ингредиента, входящего в смесь;

а_ij —количество i-го компонента в j-м ингредиенте;

с_j —стоимость единицы j-го ингредиента;

b_i — количество i-го компонента всмеси.

Модель А: