Применение симплекс-метода при определении состава смеси при переработке нефти (стр. 1 из 6)
Федеральное агентство по образованию
ГОУ ВПО «УГТУ-УПИ»
Кафедра АСУ
Курсовой проект
по теории принятия решений
Тема: Применение симплекс-метода при определении состава смеси при переработке нефти
Вариант № 14
Екатеринбург 2009г.
Постановка задачи
Нефтеперерабатывающая компания производит 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: