7.2. Построение экономико- математических моделей задач линейного программирования

Пример 7.2. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции — Щи #2, которая поступает в оптовую продажу.

Опыт работы показал, что суточный спрос на продукцию Пх никогда не превышает спроса на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. в сутки.

Расход сырья продукции Расход сырья Сырье на 1 ед. продукции Запас сырья, ед. пх П2 А 2 3 9 В 3 2 13

Оптовые цены единицы продукции равны: 3 д. е. — для Пі и 4 д. е. для Я2.

Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?

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

Для определения каких величин должна быть построена модель, т. е. как идентифицировать переменные данной задачи?

Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?

В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

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

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

Предположим, ЧТО предприятие ИЗГОТОВИТ единиц продукции Я! и х2 единиц продукции Я2.

2х1 + Зх2 < 9; 3x\ + 2X2 < 13; xx-x2<\\ X2 < 2; X! >0;

x2 > 0.

Доход от реализации xx единиц продукции Пх и х2 единиц про-дукции П2 составит F = Зхх + 4х2.

Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значения Fmsoi.

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

Пример 7.3. Использование мощностей оборудования.

Предприятие имеет т моделей машин различных мощностей. Задан план по времени и номенклатуре: Т — время работы каждой машины; продукции у-го вида должно быть выпущенр не менее Nj единиц.

Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой і-й машины по выпуску у-го вида продукции by и стоимость единицы времени, затрачиваемого /-й машиной на выпуск у-го вида продукции с у.

Другими словами, задача для предприятия состоит в следующем: требуется определить время работы /-й машины по выпуску у-го вида продукции Хц, обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции Nj.

По условию задачи машины работают заданное время Г, поэтому данное ограничение можно представить в следующем виде:

Іх0=Т, / = МЇ. (7.9)

у=і

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

m —

ZbyXgbNpjthn. (7.10)

«=1

Задача решается на минимум затрат на производство:

т п

= X hcyXf,. (7.11)

/=іу=1

Необходимо также учесть неотрицательность переменных Ху > 0.

Задача поставлена так, чтобы израсходовать все отведенное время работы машины, т.

ІхуїТ, / = (7.12)

у=Ї

m —

Zbyx^Nj, j = l,n; (7.13)

/'=1

xy> 0;

m n

= (7.14)

/=ly=l

Пример 7.4. Минимизация дисбаланса на линии сборки.

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

Из-за различий в составе технологического оборудования производительность заводов по выпуску у-го узла неодинакова и равна by. Каждый /-й завод располагает максимальным суммарным ресурсом времени в течение недели для производства m узлов, равного величине 7).

Задача состоит в максимизации выпуска изделий, что по существу эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или по нескольким видам узлов.

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

Пусть Ху — недельный фонд времени (в часах), выделяемый на заводе / для производства узла / Тогда объемы производства узла j будут следующими:

п —

Ite, у = 1,Я. (7.15)

/=1

Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделий должно быть равно количеству комплектующих узлов, объем про-изводства которых минимален:

(7.16)

ПИП

ЪЬуХу, j = 1,/w

Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод /.

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

Z = min S ЬцХу, j = 1,/w V'=1

т —

7}, / = l,/i;

М

Ху > 0 для всех і и /

Этому выражению с математической точки зрения эквивалентна следующая формулировка: максимизировать Z = У при ограни-чениях

ІЬуХу-Г>0, у =П/я; (7.20)

/=1 m

(7.21)

lxyХу > 0 для всех / и у; У > 0.

Эта модель не является линейной, но ее можно привести к линейной форме с помощью простого преобразования.

Пример 7.5. Задача составления кормовой смеси, или задача о диете .

Пусть крупная фирма (условно назовем ее «Суперрацион») имеет возможность покупать т различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных компонентов (ингредиентов).

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

Решение

Введем условные обозначения:

Xj - количество /-го сырья в смеси;

т — количество видов сырья;

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

ау — количество ингредиента у, содержащегося в единице /-го вида сырья;

bj — минимальное количество ингредиента /, содержащегося в единице смеси;

С/ — стоимость единицы сырья /;

q — минимальный общий вес смеси, используемый фирмой.

Задача может быть представлена в виде

т /=1

при следующих ограничениях:

на общий расход смеси:

їх^д; (7.23)

/=і

на питательность смеси:

т т —

ІауХії^їХі, у = (7.24)

/=1 /=1

на неотрицательность переменных:

X/ > 0, / = Т7т. (7.25)

Пример 7.6. Задача составления жидких смесей.

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

Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m-видов. Обозначим подлежащее определению количество литров /-го химического компонента, используемого для получения у-го продукта через Ху.

Ху> 0, / = Tjij = Ljn.

Первая группа ограничений относится к объемам потребляемых химических компонентов:

т —

2xij/=1

где S-t — объем /-го химического компонента, которым располагает фирма в начале планируемого периода.

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

ixij>Dj, У = ЇЯ (7.27)

/=і

где Dj — минимальный спрос на продукцию j в течение планируемого пе-риода.

Третья группа ограничений связана с технологическими особенностями, которые необходимо принимать во внимание при приготовлении смеси, например простое ограничение, определяемое некоторыми минимально допустимыми значениями, отношения между объемами двух химических компонентов в процессе получе-ния продукта j:

Хц

—>г ИЛИ Ху — Г . Х/+У > О,

xi+\j

где г — некоторая заданная константа.

Обозначив через Ру доход с единицы продукции Ху, запишем целевую функцию:

(7.28)

п т

УУ *

^тах = X X PijXij /=1у=1

Пример 7.7. Задача о раскрое или о минимизации обрезков.

Данная задача состоит в разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.

Например, продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины L. По специальным заказам потребителей фирма поставляет рулоны других размеров, для этого производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров могут включать т видов шириной tfjt = 1,/w). Известна потребность в нестандартных рулонах каждого вида, она равна bh Возможны п различных вариантов построения технологической карты раскроя рулонов стандартной ширины L на рулоны длиной ?t.

Обозначим через ау количество рулонов /-го вида, получаемых при раскрое единицы стандартного рулона по у-му варианту.

В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при у-м варианте раскроя. Определим переменную следующим образом: Xj — количество стандартных рулонов, разрезаемых по варианту у, У = 1,л.

Целевая функция - минимум отходов при раскрое

п

т п

(7.29)

Ограничение на удовлетвЪрение спроса потребителя

п

(7.30)

п

bj = X ayxj - X Уу, xj > 0, у у > 0.

Пример 7.8. Многосторонний коммерческий арбитраж .

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

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

Таблица 7.2

Многосторонний коммерческий арбитраж Валютный номинал Тип трансакции Возможность рынка 1 2 3 4 5 6 7 8 9 I

'l 1 -1 г\г -1 '13 -1 'l4 -1 'l5 -1 -1 '26 -1 '37

'67 '38 -1

'58 '29 -1 IV IV IV IV IV IV о о о о о о Размер трансакции *2 *3 х.4 *5 *6 х7 *8 *9

При трансакции х{ продажа единицы валютного номинала (ценных бумаг) II позволяет приобрести гп единиц валютного номинала I. При трансакции х7 взамен единицы валютного номинала I можно получить гЪ1 единиц валютного номинала III и г67 единиц валютного номинала VI. Остальные трансакции расшифровываются аналогично. Значения Гу могут быть дробными. Заметим, что при любой трансакции xt (і — 1, 2, 3, 4, 5) каждый из валютных номиналов можно обменять на валютный номинал I. Следует обратить внимание на правило выбора знака перед показателями в табл. 7.2. Чтобы отличать куплю от продажи, будем соответственно использовать знаки «плюс» и «минус» перед показателями, характе-ризующими данную трансакцию.

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

rxxxx + rnx2 + Г13х3 + г14х4 + гх5х5 -х6 - х7 > 0; -хх + г26х6 + г29х9 > 0;

~*2 + '37*7 + '38*8 ^ -х3 - х8 + г49х9 > 0; -х4 + г58х8 > 0; -х5 + г67х7 - х9 > 0; Xj > 0, у = Ї79.

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

Zmax = '11*1 + '12*2 + '13*3 + '14*4 + '15*5 - *6 ~ *7-

Пример 7.9. Транспортная задача.

Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их с», і = 1,3; у = 1,4. Запасы грузов у поставщиков равны gh і = 1,3. Известны потребности каждого потребителя fy, у =1,4. Будем считать, что суммар-ные потребности равны суммарным запасам:

3 4

2>/ = ? bj.

М У=1

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

Введем переменные Ху — количество груза, перевозимого от /-го поставщика у-му потребителю.

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

• потребности всех потребителей должны быть удовлетворены полностью:

x\\ +х21 + *31 =

Xl2 +X22 +X32 =b2; (7.31)

*13 +*23 +*33 =^3; x\4 +x24 +x34 =

или в общем виде:

— 2 у = 1,4; /=і

груз от поставщика должен быть вывезен полностью:

*11+*12+*13+*14=аЬ

< х21+х22+х23+х24=а2; (7.32)

*31 + *32 +х33 +х34 = а3>

или в общем виде:

— ZxiJ=ah / = 1,3; у=1

условие неотрицательности переменных:

> 0, / = ГТз, у = Ї74.

Целевая функция должна минимизировать суммарные затраты на перевозку:

3 4

= (7.33)

ММ

Количество поставщиков и потребителей в общем случае может быть произвольным (> 2).

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

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

Линейная функция может стремиться как к максимуму, так и к минимуму.

Переменные в задачах всегда неотрицательны. Напомним, что от любой из вышеперечисленных задач можно

перейти к канонической (основной) задаче линейного программи-рования.