Использование методов линейного программирования и экономического моделирования в технологических процессах

Задача 1

Нефтеперерабатывающий завод располагает двумя сортами нефти:

сортом А в количестве 10 единиц,

сортом В — 15 единиц.

При переработке из нефти получаются два материала: бензин (обозначим Б) и мазут (М).

Имеется три варианта технологического процесса переработки:

I: 1ед.А + 2ед.В дает 3ед.Б + 2ед.М

II:2ед.А + 1ед.В дает 1ед.Б + 5ед.М

III:2ед.А + 2ед.В дает 1ед.Б + 2ед.М

Цена бензина — 10 долл. за единицу, мазута — 1 долл. за единицу.

Определить наиболее выгодное сочетание технологических процессов переработки имеющегося количества нефти.

Решение

"выгодность" -- получение максимального дохода от реализации продукции

"выбор (принятие) решения" состоит в определении того, какую технологию и сколько раз применить.

Обозначим неизвестные величины:

х_i—количество использования i-го технологического процесса (i=1,2,3).

Остальные параметры модели (запасы сортов нефти, цены бензина и мазута) известны.

Для вектора х=(х₁,х₂,х₃),

выручка завода равна (32х₁+15х₂ +12х₃) долл.

Здесь 32 долл. — это доход, полученный от одного применения первого технологического процесса (10 долл. ·3ед.Б + 1 долл. ·2ед.М = 32 долл.).

Аналогичный смысл имеют коэффициенты 15 и 12 для второго и третьего процессов.

Учет запаса нефти приводит к следующим условиям:

для сорта А:

для сорта В:,

где в первом неравенстве коэффициенты 1, 2, 2 — это нормы расхода нефти сорта А для одноразового применения технологических процессов I, II, III соответственно.

Математическая модель

Найти такой вектор х = (х₁,х₂,х₃), чтобы

максимизировать f(x) =32х₁+15х₂ +12х₃

при выполнении условий:

.

Сокращенная запись:

Получили задачу линейного программирования.

Модель (1.4.2.) является примером оптимизационной модели детерминированного типа (с вполне определенными элементами).

На дом

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

Обозначим известные параметры задачи:

n — число разновидностей ценных бумаг;

а_j — фактическая прибыль (случайное число) от j-го вида ценной бумаги

_j — ожидаемая прибыль от j-го вида ценной бумаги.

Обозначим неизвестные величины:

y_j — средства, выделенные для приобретения ценных бумаг вида j.

По нашим обозначениям вся инвестированная сумма выражается как

Для упрощения модели введем новые величины

Таким образом, х_i — это доля от всех средств, выделяемая для приобретения ценных бумаг вида j.

Ясно, что

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

Содержательно риск — это мера отклонения фактической прибыли от ожидаемой. Поэтому его можно отождествить с ковариацией.

прибыли для ценных бумаг вида i и вида j. Здесь М — обозначение математического ожидания.

Математическая модель

min

при ограничениях

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

Модель (1.4.3.) является примеров оптимизационной модели стохастического типа (с элементами случайности).

Задача 2

Бройлерное хозяйство птицеводческой фермы насчитывает 20000 цыплят, которые выращиваются до 8-недельного возраста и, после соответствующей обработки, поступают в продажу. Хотя недельный расход корма для цыплят зависит от их возраста, в дальнейшем будем считать, что в среднем (за 8 недель) он составляет 1 фунт.

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

Смесь должна содержать:

1.         не менее 0,8%, но не более 1,2% кальция;

2.         не менее 22% белка;

3.         не более 5% клетчатки.

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

Решение

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

x₁- содержание известняка (в фунтах) в смеси,

- содержание зерна (в фунтах) в смеси,

- содержание соевых бобов (в фунтах) в смеси.

В качестве (минимизируемой) целевой функции выступает общая стоимость смеси, определяемая по формуле .

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

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

1.         смесь должна содержать не менее 0,8% кальция:

2.         смесь должна содержать не более 1,2% кальция:

Эти ограничения можно записать в более простой форме, объединив в левых частях неравенств члены, содержащие , и :

Аналогично записываются условия по оставшимся питательным веществам.

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

Задача 3

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

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

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

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

Решение.

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

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

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

Задача 4

На предприятии производятся два вида продукции из двух видов сырья. Производство единицы продукта 1 (первого вида) приносит предприятию доход, равный 10 единицам, а производство единицы продукта 2 (второго вида) - доход в 8 единиц. Переработка сырья производится аппаратами двух типов, которые условно называются в дальнейшем машинами и агрегатами. На переработке сырья первого вида занято пять машин, причем производственные условия не допускают, чтобы суммарное время использования машин на этой работе превышало 40 ч (за некоторый период). На переработке сырья второго вида занято 25 агрегатов; суммарное время их использования в течение того же периода не должно превышать 200 ч. При производстве единицы продукта 1 на переработку сырья первого вида затрачивается 4 ч и на переработку сырья второго вида - 9 ч, в то время как производство единицы продукта 2 требует затраты 3 ч на переработку каждого из видов сырья.

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

Максимальное число сверхурочных часов, приходящихся на период, равно восьми, причем эти часы должны распределяться на переработку первого и второго видов сырья равномерно. Доплата за час сверхурочной работы на переработке любого из видов сырья одинакова; полная оплата за час сверхурочной работы равна 2 единицам. Повышение затрат за период, связанный с приобретением одной машины, перерабатывающей сырье первого вида, составляет 10 единиц. Агрегаты, перерабатывающие сырье второго вида, дополнительно не приобретаются.

Необходимо максимизировать доход от выпуска продукции.

Решение

Задачу максимизации дохода от выпуска продукции можно записать как задачу математического программирования:

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

Задача 5

Для обеспечения нормальной работы оборудования необходимо закупить n видов запасных частей на сумму d рублей. Стоимость j-ой детали равна , потребность в ней есть случайная величина , имеющая показательный закон распределения с параметром . Использование j-ой детали позволяет получить прибыль . Отсутствие детали в случае необходимости приводит к убыткам . Если деталь не используется в данном периоде, то убыток составляет . Как распределить имеющиеся средства, чтобы общая прибыль была наибольшей?

Решение

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

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

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

.

Здесь

-

плотность распределения случайной величины . Тогда

.

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

Задача 6

Фирма А производит некоторый товар, который имеет спрос в течение n единиц времени. Этот товар поступает на рынок в момент i (i=1,…,n). Для конкурентной борьбы с фирмой А дочерняя фирма В концерна Д, не заботясь о собственных доходах, производит аналогичный товар, который поступает на рынок в момент j (j=1,…,n). Ее цель – разорение первой фирмы, после чего ей будет легко, опираясь на капитал D, наверстать упущенное. Для этой цели проще всего продавать товары по пониженной цене. Однако имеются законы (соглашения), запрещающие поступать подобным образом. В этом случае единственным законным инструментом этой фирмы является выбор момента поступления товара на рынок. Будем считать, что качество конкурирующих товаров зависит от времени их поступления на рынок относительно друг друга – чем позднее товар выбрасывается на рынок, тем качество его выше, а реализуется только товар высшего качества. Каждая фирма должна заранее готовить свое производство к выпуску и продаже товара в выбранный период времени. А чтобы разорить первую фирму, вторая фирма должна минимизировать ее доходы

Решение

Налицо столкновение интересов двух фирм - А и В. Наиболее подходящим математическим аппаратом для моделирования их поведения является теория игр.

Изложенная в условии задачи ситуация конкуренции двух одинаковых фирм является антагонистическим конфликтом. Для построения математической модели этого конфликта - конечной антагонистической игры - примем за игроков 1 и 2 соответственно фирмы А и В. Очевидно, что множества чистых стратегий игроков 1 и 2 - это множества : фирма А выбирает i-ый момент поступления товара на рынок, стараясь максимизировать свой доход, а фирма В выбирает j-ый момент, преследуя прямо противоположные цели - минимизировать доход фирмы А.

Обозначим через c доход от продажи товара в единицу времени. Тогда, если фирма А выбрасывает свой товар в момент i, а фирма В - в момент j>i, то фирма А, не имея конкурента в течение j-i единиц времени, получит за это время доход c(j-i). В момент времени j на рынке появляется товар фирмы В, который имеет более высокое качество. Поэтому с момента j фирма А теряет рынок и в дальнейшем дохода не получает. Если же i>j, то фирма А, выбросив на рынок более качественный товар, будет получать доход в течение всего отрезка [i,n]. Так как число оставшихся единиц времени равно n-i+1, то доход фирмы А будет равен c(n-i+1). В том случае, когда i=j, т.е. на рынок одновременно поступают оба товара, эти товары имеют одинаковый спрос, и поэтому фирма А получит доход, равный . В результате функцию выигрыша игрока 1 можно представить в следующем виде:

Получаем матричную игру , определяемую матрицей .

Задача 7

Автотранспортная компания для перевозки грузов располагает четырьмя автомашинами следующей грузоподъемности: машина 1 - 2 т, машина 2 и машина 3 - по 5 т, машина 4 - 8 т. Для каждой автомашины известна стоимость ее эксплуатации за день: для машины 1 - 15 единиц, для машины 2 - 20 единиц, для машины 3 - 19 единиц, для машины 4 - 30 единиц. Необходимо в течение одного дня развести грузы четырем получателям. В книжный магазин нужно доставить груз весом в 1 т, в мебельный магазин - в 3 т, в фермерское хозяйство - в 5 т и на сталелитейный завод - в 8 т. Предположим, что одна и та же машина не может доставлять груз в книжный или мебельный магазин и на ферму. Требуется так назначить автомашины для доставки всех грузов, чтобы суммарные затраты были минимальными.

Решение

Задачу минимизации суммарных затрат на перевозку грузов можно записать как задачу математического программирования:

Здесь через x_ij обозначен факт поставки i-му потребителю груза j-ой машиной, т.е.

Все получатели грузов пронумерованы: 1 - книжный магазин, 2 - мебельный магазин, 3 - фермерское хозяйство, 4 - сталелитейный завод. Целевая функция представляет собой суммарные затраты. Первые четыре ограничения связаны с необходимостью доставить получателям нужное им количество груза, следующие - с невозможностью одновременного использования одной машины на некоторых маршрутах.

Задача 8

Пусть экономика представлена двумя отраслями народного хозяйства, каждая из которых выпускает свою продукцию и затрачивает на воспроизводство труд, средства труда и предметы труда. Валовый продукт каждой отрасли за год распределяется соответственно на конечный продукт и производственное потребление, причем в процессе производства данной отрасли может применяться продукция обеих отраслей. Известно, что потребление одной отраслью продукции другой пропорционально объему валового выпуска первой из них. Конечный продукт обеих отраслей делится на валовые капитальные вложения и непроизводственное потребление. Без учета амортизационных отчислений, можно считать, что валовые капитальные вложения из одной отрасли в другую каждый год пропорциональны приросту валовой продукции второй отрасли.

Определить, как должна функционировать рассматриваемая экономическая система во времени.

Решение

Заметим, что поскольку критерий оптимальности в задаче не задан, то математическая модель будет описательной. Обозначим через валовую продукцию отрасли i в год t, через - ее конечный продукт в год t, а через - производственное потребление отраслью i продукции отрасли j в год t (все величины здесь и далее выражены в стоимостном эквиваленте). Из условия задачи следует

.

Пусть - норма затрат продукции j-ой отрасли на производство единицы продукции i-ой отрасли. Тогда

.

Обозначив - валовые капитальные вложения отрасли i в отрасль j в год t, - непроизводственное потребление отрасли i в год t, получим

.

Пропорциональность валовых капитальных вложений приросту валовой продукции запишем в виде

.

Окончательно, получаем двухпродуктовую модель экономики

.

Задавая в начальный момент и предполагая известными во времени потребления , i=1,2, видим, что задача развития экономики, заданной двумя отраслями, сводится к системе линейных неоднородных уравнений.