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

Федеральное агентство по образованию

ГОУ ВПО «УГТУ-УПИ»

Кафедра АСУ

Курсовой проект

по теории принятия решений

Тема: Определение состава смеси при переработке нефти

Вариант № 14

Екатеринбург 2009г.

Постановка задачи

Нефтеперерабатывающая компания производит 2 сорта бензина, который она продаёт по цене 19 и 21,5 цент за галлон. Нефтеперегонный завод может закупать 4 различных сорта сырой нефти, имеющей состав и стоимость, указанные в таблице 1.

Таблица 1

Состав компонент и стоимость сырой нефти

В бензине стоимостью 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. Необходимо задачу привести к канонической форме.

1.1. Введением неотрицательных слабых переменных все ограничения неравенства представляют в виде равенств

()

1.2. Максимизируем целевую функцию ().

1.3. Задача в канонической форме имеет вид:

Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные , ,….,. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить её значение.

2. Поиск опорного базисного решения.

2.1. Определяем допустимое базисное решение.

2.2. Принимаем в качестве базисных, введённые слабые переменные.

2.3. Составляем исходную симплекс-таблицу (таблица 3) по следующей схеме (таблица 4):

Таблица 3. Симплекс-таблица

Таблица 4. Схема заполнения симплекс-таблица

Страницы: 1, 2, 3, 4