Применение симплекс-метода при определении состава смеси при переработке нефти

Нефтеперерабатывающая компания производит 2 сорта бензина, который она продаёт по цене 19 и 21,5 цент за галлон. Нефтеперегонный завод может закупать 4 различных сорта сырой нефти, имеющей состав и стоимость, указанные в таблице 1.
Таблица 1
Состав компонент и стоимость сырой нефти
Сырая нефть
Состав компонент
Цена галлона нефти
A
B
C
1
0,75
0,2
0,05
15
2
0,3
0,35
0,35
9
3
0,65
0,15
0,2
16
4
0,45
0,35
0,2
13
В бензине стоимостью 21,5 цент должно содержаться не менее 45% фракции A и не более 20% фракции С. В бензине стоимостью 19 центов должно быть не более 30% фракции С. При смешивании вследствие испарения теряется 2% фракции А и по 1% фракций B и С. Определить наиболее выгодное соотношение сортов сырой нефти, используемой для производства бензина, и выбрать наиболее прибыльный бензин.

Введение
До XIX века основным поставщиком прикладных задач для математики были астрономия, механика, физика, а основной и весьма плодотворной идеей — идея непрерывности, приведшая к становлению мощного аппарата интегрально-дифференциального исчисления. Развитие экономики привело к возможности рассмотрения количественных закономерностей и в рамках этой науки; с появлением экономических моделей Кенэ (1758 г.), Маркса, Вальраса и др. по существу началась математическая экономика.
В 1939 году вышла в свет монография Л.В. Канторовича «Математические методы организации и планирования производства», где выявлен широкий класс производственно-экономических оптимизационных задач, допускающих строгое математическое описание. Идеи, содержащиеся в этой книге, были затем им развиты и привели к созданию линейного программирования.
Для ряда моделей основное содержание задачи заключается в нахождении смеси веществ, продуктов и тому подобного, удовлетворяющих определенным технологическим требованиям.
Прародительницей этих задач была так называемая задача о диете: найти наиболее дешевую смесь пищевых продуктов 1,2,…,m (хлеба, мяса, молока и пр.) которая удовлетворяла бы определенным биологическим ограничениям на содержание жиров, белков, углеводов, микроэлементов, витаминов и тому подобных биологически активных веществ.
Если обозначить через xi процентное содержание (по весу) j-го продукта в смеси, через aij - весовое содержание i-го вещества в j-ом продукте, pi - допустимую верхнюю границу содержания i-го вещества в смеси, qi - нижнюю, а через cj - стоимость j-го продукта, то задача о наиболее дешевой диете приобретает вид:

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

Математическая постановка задачи
Для получения r сортов бензина используется n исходных материалов. Химический состав каждого сорта бензина определяется содержанием в нем m химических элементов.
Таким образом, получается:
r - количество получаемых сортов бензина; r = 2.
m - количество химических элементов; m = 3.
n - количество сортов сырой нефти; n = 4.
k – сорт бензина; .
i – вид фракции; (A, B и C).
j – сорт нефти; .
ai , j – содержание i-го химического элемента (компонента) в единице j-го сорта сырой нефти
bi , k - содержание i-го химического элемента (компонента) в бензине k–го сорта
xj,k - доля содержания j-го сорта сырой нефти, используемое в одном галлоне смеси бензина k–го сорта;
Sk - отпускная цена бензина k –го сорта;
Zj - цена единицы j-го сорта сырой нефти; Z
Ck - прибыль получаемая при производстве бензина k –го сорта;
Исходя из условий задачи, необходимо максимизировать следующую целевую функцию (максимизируется разность между отпускной ценой выпускаемых бензинов и ценой исходных материалов):
Для решения задачи необходимо максимизировать целевую функцию с учётом ограничений. В общем виде мы имеем следующее ограничение, определяющее содержание фракций в готовом бензине:
В частом случае, это ограничение имеет следующий вид (в поставленной задаче содержатся ограничения вида «не более» и «не менее», что приводит к использованию неравенств):
Так же нужно учесть формулу баланса:
Где , т.е. не отрицательны.

Выбор метода решения задачи
Процессы принятия решений лежат в основе любой целенаправленной деятельности. Оптимальные (эффективные) решения позволяют достигать цели при минимальных затратах трудовых, материальных и сырьевых ресурсов.
В классической математике методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании. Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.
Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.
Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования.
Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования является симплекс-метод. Cимплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач линейного программирования
Для решения задачи симплекс-методом необходимо привести её к каноническому виду, то есть ограничения принимают вид равенств, а целевая функция максимизируется. Так как общая задача линейного программирования имеет ограничения не только вида «=», но и « », « », а целевая функция может либо максимизироваться, либо минимизироваться, то задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения привести к ограничениям-равенствам.
Для того, чтобы задача линейного программирования была разрешима, то есть имела оптимальное решение, необходимо и достаточно, чтобы ограничения задачи были совместными (множество допустимых решений не пусто) и целевая функция была ограничена при поиске максимума сверху, а при поиске минимума снизу.
Описание алгоритма решения задачи
Алгоритм симплекс-метода выполняется в три этапа показан в таблице 2:
Таблица 2. Алгоритм симплекс-метода
1 этап
Приводим задачу линейного программирования к канонической форме.
2 этап
Определяем допустимое базисное решение
3 этап
Поиск оптимального решения, реализуемый переходом от одного базисного плана к другому, приводящему либо к оптимальному решению, либо к выводу о том , что задача решения не имеет
1. Необходимо задачу привести к канонической форме.
1.1. Введением неотрицательных слабых переменных все ограничения неравенства представляют в виде равенств
()
1.2. Максимизируем целевую функцию ().
1.3. Задача в канонической форме имеет вид:

Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные , ,….,. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить её значение.
2. Поиск опорного базисного решения.
2.1. Определяем допустимое базисное решение.
2.2. Принимаем в качестве базисных, введённые слабые переменные.
2.3. Составляем исходную симплекс-таблицу (таблица 3) по следующей схеме (таблица 4):

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию