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

ВАРИАНТ 3

 

ЭКОНОМИЧЕСКИЕ СИТУАЦИИ, РАЗРЕШАЕМЫЕ МЕТОДАМИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ В ЭКОНОМИКЕ

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

Оптимизация плана производства

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

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

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

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

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

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

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

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

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

                             (1)

          (2)

           (3)

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

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

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

       х _j — переменная.

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

 

                                          (4)

                   (5)

                              (6)

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

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

 

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

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

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

Однопродуктовые модели оптималь­ного смешения. Введем обозначения:

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

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

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

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

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

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

Здесь (1) — целевая функция (минимум затрат на получение смеси);

(2)— группа ограничений, определяющих содержание ком­понентов в смеси;

(3) — ограничения не отрицательности переменных.

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

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

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

w — количество условий, отражающих содержание j-го ингре­диента в смеси;

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

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

b_i — минимально допустимая доля i-го компонента в смеси;

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

d_rj — коэффициент, отражающий r-е условие на содержание j-го ингредиента в смеси.

 

Здесь (4) — целевая функция (минимум затрат на получение смеси);

(5) — группа ограничений, определяющих содержание компонентов в смеси;

(6) — группа ограничений на содержание ингредиентов в смеси;

(7) — ограничение на количество смеси;

(8) — ограничения не отрицательности переменных.

Ограничения (5) и (6) отличают задачу смешения от задачи оптимального планирования производства. Значения правых частей этих ограничений равны нулю. Вектор х* с компонентами, являющийся решением этой оптимизационной зада­чи, называют рецептом приготовления смеси или рецептом сме­шения. В многопродуктовых задачах ингредиенты используют­ся для приготовления не одной, а нескольких смесей. При этом в качестве переменной x_kj, такой задачи рассматривается количество ингредиента j, используемое для приготовления смеси k. Крите­рий задачи — максимизация прибыли.

 

Оптимальный раскрой

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

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

Пусть k — индекс вида заготовки, k = 1,.... q; i — индекс спо­соба раскроя единицы материала, i = 1,..., р; а _ik — количество (це­лое число) заготовок вида k , полученных при раскрое единицы материала i -м способом. Приведенное определение рационального способа раскроя мо­жет быть формализовано следующим образом. Способ раскроя v называетсярациональным (оптимальным по Па­рето), если для любого другого способа раскроя i из соотношений а _ik ³ а _vk , k = 1, ..., q , следуют соотношения а _ik = а _vk , k = 1, ..., q .

Определение интенсивности использования рациональных спо­собов раскроя. Обозначения:

j —индекс материала, j = 1,..., п ;

k —индекс вида заготовки, k = 1, ..., q ;

i — индекс способа раскроя единицы материала, i = 1,..., р ;

а _ijk — количество (целое число) заготовок вида k , полученных при раскрое единицы j-го материала i-м способом;

b_k — число заготовок вида k в комплекте, поставляемом заказ­чику;

d_j — количество материала j-го вида;

x_ji — количество единицу j-го материала, раскраиваемых по i-му способу (интенсивность использования способа раскроя);

c_ji — величина отхода, полученного при раскрое единицы j-го материала по i-му способу;

у — число комплектов заготовок различного вида, поставля­емых заказчику.

Раскрой с минимальным расходом материалов:

Здесь (1) — целевая функция (минимум количества использу­емых материалов);

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

(3) — условия не отрицательности переменных.

Раскрой с минимальными отходами:

         

Здесь (4) — целевая функция (минимум отходов при раскрое ма­териалов);

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

(6) — условия не отрицательности переменных.

Планирование финансов

Минимизации целевого фонда. Например, в определенные моменты времени необходимо выплачивать извест­ные суммы денег по взятому ранее займу. Чтобы накопить эти суммы, можно заранее создать целевой фонд, а средства из этого фонда использовать для срочных вкладов. Каждый срочный вклад характеризуется моментом времени вложения, сроком погашения и доходностью. Задача состоит в том, чтобы определить минималь­ный размер целевого фонда и выбрать те виды срочных вкладов, которые следует использовать, чтобы сделать выплату по займу. Обозначения:

у — размер целевого фонда, создаваемого в нулевой момент времени;

t — текущий момент времени, t = 0, 1,.... Т;

d_t — размер выплаты по займу, которую надо произвести в мо­мент времени t (t = 1, ..., Т);

j —индекс срочного вклада, j = 1,..., п ;

v_j — момент времени вложения по срочному вкладу j;

w_j — срок выплаты по срочному вкладу j;

r_j — доходность срочного вклада j (процент по вкладу);

х _j — объем вложений по срочному вкладу j.

Предполагается, что для любого срочного вклада j момент v _j времени вложения фиксирован. Если по срочному вкладу сде­ланы вложения в размере х _j, то через w _j единиц времени вклад­чику выплачивается сумма (1 + r_j )х _j. Без ограничения общности можно считать, что для любого момента времени существует та­кой вклад, выплата по которому производится в следующий мо­мент времени. При этом доходность такого вклада может быть нулевая. Использование вклада с нулевой доходностью означает, что деньги остаются на руках у владельца.

Пусть G_t — множество индексов j, таких, что t= v_j , т.е. по вкладу j сделано вложение в момент времени t, Q_t — множество индексов j, таких, что t = v_j + w _j, т.е. по вкладу j получена выплата в момент времени t. Для любого t множества G_t и Q_t известны.

Тогда модель имеет следующий вид:

Здесь (1) — целевая функция (минимальный размер целевого фонда);

(2) —условие, характеризующее распределение целевого фонда по вкладам в нулевой момент времени;

(3) — соотношения, устанавливающие баланс между выпла­тами и вложениями;

(4) — условие, обеспечивающее выплату по займу;

(5) — условия не отрицательности переменных.

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

Сохраним принятые ранее обозначения и введем новые:

z — размер дохода, который может получить вкладчик в мо­мент времени Т;

и _t— размер вклада в момент времени t (t = 0, 1,..., Т— 1).

Тогда модель имеет следующий вид:

Здесь (6) — целевая функция (максимальная величина дохода);

(7) — условие, характеризующее распределение вклада в нулевой момент времени;

(8) — соотношения, устанавливающие баланс между вы­платами и вложениями;

(9) — условие, определяющее величину дохода;

(10) —условия не отрицательности переменных.

Транспортная задача

Известны потребности нескольких потреби­телей в некотором продукте. Требуется определить, от каких производи­телей, и в каких объемах должны получать продукт потребители. Поставки должны осуществляться таким образом, чтобы совокуп­ные издержки на транспортировку продукта были минимальными. Обозначения:

а _i — величина предложения продукта в пункте i (i = 1, ..., n);

b_j — величина спроса на продукт в пункте j (j = 1,..., т);

c_ij — затраты на транспортировку единицы продукта из пункта i в пункт j;

x_ij — количество продукта, перевозимого из пункта i в пункт j.

Модель транспортной задачи:

Здесь (1) — целевая функция (минимум затрат на транспортиров­ку продукта);

(2) — ограничения по величине предложения в каждом пунк­те производства;

(3) — ограничения по величине спроса в каждом пункте по­требления;

(4) — условия не отрицательности объемов перевозок.

Замкнутая транспортная задача. Общее предложение равнообщему спросу:

Это необходимое и достаточное условие существования допу­стимого плана задачи (1)—(4).

Открытая транспортная задача.

а)  — излишек продукта

Транспортная задача с запретами. Пусть Е — множество пар индексов (ij), таких, что из пункта i в пункт j допускается транс­портировка продукта. Между любыми другими двумя пунктами транспортировка не допускается.

Пусть М— большое число, например

Тогда

В оптимальном плане { } транспортной задачи  при ограничениях (2)—(4) x_ij = 0, если ( i , j) Ï Е.

Транспортная задача с фиксированными перевозками. Если объем перевозок между пунктами i и j задан, то в задаче (1)—(4) вводится дополнительное ограничение: x_ij = v_ij, где v_ij — заданный объем перевозок.

Транспортная задача с ограничениями на пропускную способ­ность. Если объем перевозок из пункта i в пункт j ограничен ве­личиной w_ij, то в задаче (1)—(4) вводится дополнительное огра­ничение: x_ij £ w_ij .

Транспортная задача с фиксированными доплатами. В открытой транспортной задаче имеет место дефицит продукта и для его устранения в пунктах i = п + 1, ..., k воз­можно создание новых мощностей d_i .

 

Задача о назначениях

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

Задачу о назначениях можно сформулировать следующим об­разом. Необходимо выполнить N различных работ. Для их выпол­нения можно привлечь N рабочих. Каждый рабочий за определен­ную плату готов выполнить любую работу. Выполнение одной работы следует поручить одному рабочему. Требуется так распре­делить работы между рабочими, чтобы общие затраты на выпол­нение всех работ были минимальными. Пусть т — количество работ.

Задача о назначениях в стандартной форме. При рассмотрении задачи о назначениях в стандартной форме предполагается, что количество рабочих равно количеству работ.

Обозначения:

с _ij — показатель эффективности назначения i-го рабочего на j-й работе, например издержки выполнения i-м рабочим j-й работы;

x_ij — переменная модели (х _ij = 1, если i-й рабочий использует­ся на j-й работе, и x_ij = 0 в противном случае).

Модель задачи о назначениях:

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

(2) — система ограничений, отражающая следующие усло­вия:

а) каждая работа должна быть выполнена одним рабо­чим;

б) каждый рабочий может быть привлечен к одной работе;

(3) — условия не отрицательности переменных.

При решении задачи о назначениях исходной информацией является таблица задачи о назначениях с={с _ij}, элементами ко­торой служат показатели эффективности назначений.

Результатом решения задачи о назначениях (1)—(3) является вектор х* = { }, компоненты которого — целые числа. Оптимальный план задачи о назначениях (1)—(3) можно пред­ставить в виде квадратной матрицы назначений, в каждой строке и в каждом столбце которой находится ровно одна единица. Та­кую матрицу иногда называют матрицей перестановок. Значение целевой функции (1), соответствующее оптимальному плану, на­зывают эффективностью назначений.

Задача о назначени­ях в открытой форме возникает, когда количество рабочих не равно количеству работ. В этих случаях задача может быть пре­образована в задачу, сформулированную в стандартной форме. Количество рабочих п превышает количество работ т. Введем дополнительные фиктивные работы с индексами j = w + 1,..., п. Коэффициенты таблицы назначений с _ij , i = 1,..., п; j = т + 1,..., п, положим равными нулю. В этом случае получаем задачу, сформулированную в стандартной форме. Если в опти­мальном плане этой задачи  = 1 при j = т + 1,..., п, то испол­нитель i назначается на выполнение фиктивной работы, т.е. ос­тается без работы. Заметим, что оптимальное значение целевой функ­ции исходной задачи совпадает с оптимальным значением задачи, приведенной к стандартной форме. Поэтому эффективность на­значений в результате такого преобразования не меняется.

Задача о назначениях является частным случаем транспортной задачи, в которой количество пунк­тов производства совпадает с количеством пунктов потребления, а все величины спроса и величины предложения равны.