Федеральное агентство по образованию
ГОУ ВПО «УГТУ-УПИ»
Кафедра АСУ
Курсовой проект
по теории принятия решений
Тема: Применение симплекс-метода при определении состава смеси при переработке нефти
Вариант № 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:
Таблица 2. Алгоритм симплекс-метода
| 1 этап |
Приводим задачу линейного программирования к канонической форме. |
| 2 этап |
Определяем допустимое базисное решение |
| 3 этап |
Поиск оптимального решения, реализуемый переходом от одного базисного плана к другому, приводящему либо к оптимальному решению, либо к выводу о том , что задача решения не имеет |
1. Необходимо задачу привести к канонической форме.
1.1. Введением неотрицательных слабых переменных все ограничения неравенства представляют в виде равенств
()
1.2. Максимизируем целевую функцию ().
1.3. Задача в канонической форме имеет вид:
Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные , ,….,. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить её значение.
2. Поиск опорного базисного решения.
2.1. Определяем допустимое базисное решение.
2.2. Принимаем в качестве базисных, введённые слабые переменные.
2.3. Составляем исходную симплекс-таблицу (таблица 3) по следующей схеме (таблица 4):
Таблица 3. Симплекс-таблица
| Ci
|
|
|
C1
|
Cj
|
… |
Cn
|
Cn+1
|
… |
Cn+m
|
|
|
|
… |
|
|
… |
|
|||
| C1
|
|
|
|
|
… |
|
|
… |
0 |
| Ci
|
|
|
|
|
… |
|
0 |
… |
0 |
| … |
… |
… |
… |
… |
… |
… |
… |
… |
… |
| Cm
|
|
|
|
|
… |
|
0 |
… |
|
|
|
|
|
|
|
… |
|
|
… |
|
|
|
|
|
|
|
… |
|
|
… |
|
Таблица 4. Схема заполнения симплекс-таблица
| Столбец Сi
|
записываются коэффициенты при базисных переменных () |
| Столбец |
базисные переменные. Количество базисных переменных равно количеству ограничений задачи (n) |
| Столбец |
свободные члены ограничений (значения базисных переменных) |
| Строка |
строка переменных, входящих в целевую функцию и в систему ограничений |
| Столбцы |
В симплекс-таблице количество столбцов равно количеству базисных и свободных переменных задачи (m+n). Количество свободных переменных равно количеству неизвестных переменных задачи (n), количество базисных – количеству ограничений (m) |
| Строка |
Для столбца : содержит значение целевой функции, которое рассчитывается по формуле , а столбцы этой же строки (значения относительных оценок ), рассчитывается по формуле |
При определении значения функции фактически нужно найти сумму произведений элементов столбца Ci
на соответствующие элементы столбца . что равносильно подстановке базисного плана в целевую функцию
Строка оценок позволяет нам судить об оптимальности плана.
Условие оптимальности плана:
- При отыскании max функции в строке оценок должны быть нулевые и положительные оценки;
- При отыскании min функции в строке оценок должны быть нулевые и отрицательные оценки;
2.4. Проверяем допустимость базисного решения: все базисные переменные ( в столбце ) неотрицательны. Если все базисные переменные неотрицательны, то переходим к пункту 3.
Если среди них есть отрицательные, то вводим фиктивную целевую функцию и отводим ей дополнительную строку в симплекс-таблице (Таблица 1).
2.5. Строим фиктивную целевую функцию - элементы строки для
являются суммой соответствующих элементов строк для выбранных базисных переменных, оказавшихся отрицательными.
2.6. Максимизируем фиктивную целевую функцию (алгоритм для максимизации начальной ц.ф. такой же, как и рассматривающийся для ).
2.6.1. Поиск разрешающего столбца.
Для перехода к новому базисному плану в первую очередь из числа свободных переменных с отрицательными оценками выбирается переменная, которая вводится в базис.
Вводится переменная, которой соответствует наибольшая по абсолютной величине отрицательная оценка :
Столбец, отвечающий переменной , назовем разрешающим столбцом.
Элементы разрешающего столбца обозначаются через .
Выбранная переменная будет вводится в базис.
Если окажется несколько одинаковых наибольших по абсолютной величине , то выбирается любая из соответствующих им переменных.
2.6.2. . Поиск разрешающей строки.
Выбираем переменную, которая выводится из базиса (обозначим индексом ). Находится из соотношения:
по всем i для которых
)
Строку таблицы, в которой получено наименьшее отношение
элемента столбца к элементу разрешающего столбца, назовем разрешающей строкой.
Элементы разрешающей строки обозначаются через
Выбранная переменная будет выводится из базиса.
2.6.3. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется главным.
2.6.4. Пересчет оставшихся элементов таблицы по правилу прямоугольника.
Результат заносится в новую симплекс-таблицу.
Выбранные переменные в новой таблице меняются местами вместе со своими коэффициентами в целевой функции.
Элементы новой симплекс-таблицы рассчитываются по формулам, приведенным в таблице 5.
Таблица 5. Расчёт элементов новой симплекс-таблицы
| Элементы главной строки |
|
| Элементы главного столбца |
|
| Главный элемент |
|
| Все остальные элементы таблицы |
; ; ; . |
2.6.5. После пересчета всех элементов таблицы в строке для дополнительной фиктивной функции находим отрицательные элементы, то пересчет задачи производится (следующая итерация) по описанному алгоритму далее для этой же функции. Если отрицательных элементов нет, то фиктивная целевая функция достигла своего максимума.
· Если и все коэффициенты в строке для равны 0, то полученное при этом базисное решение является опорным. Исключают строку для и переходят к п. 3.
· Если то система ограничений противоречива и задача не имеет решений. Переходят к п. 4.
· Если , а среди элементов строки для есть ненулевые, то соответствующие этим элементам переменные всегда равны 0. Исключают строку для и переходят к п.3.
2.6.6. После исключения строки для функции при расчете разрешающего столбца используем строку для основной функции . Получили допустимое базисное решение. Далее расчет производится по алгоритму, описанному выше. Начинаем поиск оптимального решения.
3. Поиск оптимального решения. После получения допустимого базисного решения исходной задачи по алгоритму, описанному выше, максимизируем целевую функцию исходной задачи.
3.1. В строке для ищем отрицательные элементы.
Если отрицательных элементов нет, то получено оптимальное решение задачи.
Если среди элементов строки есть отрицательные, то выбирают столбец, содержащий наименьший отрицательный элемент в строке , - он будет разрешающим.
Рассматриваем положительные значения отношений элементов столбца свободных членов к соответствующим элементам выбранного столбца и среди этих отношений берем наименьшее – разрешающая строка.
Элемент на пересечении разрешающих строки и столбца – главный.
Поиск оптимального решения ведется до тех пор пока в троке не будут положительными все оценки .
Описание вычислительного эксперимента
Целевая функция задачи имеет вид:
1. Вычислительный эксперимент для первого сорта бензина
Целевая функция для первого сорта бензина (k=1):
Содержание фракции А, В, С для I-го сорта бензина:
Фракции А: Не менее 45% - 0.45
При испарении теряется 2% - 0.02
Фракции С: Не более 20% - 0.2
При испарении теряется 1% - 0.01
Формула баланса:
Ограничения с учетом испарения для I-го сорта бензина:
Сведем ограничения к определению максимума целевой функции:
Далее действуем по алгоритму симплекс-метода, приведённому нами в предыдущей главе.
Первый этап. Приведение к каноническому виду
- свободные переменные.
– базисные переменные (искусственные величины).
Второй этап. Поиск допустимого решения.
Определим исходный базисный план
Вычисляем значения относительных оценок
Поскольку для данного плана существуют отрицательные оценки (по критерию оптимальности ), то план не оптимален. Необходим переход к другому базисному плану.
Проверяем допустимость базисного решения: все базисные переменные (в столбце ) должны иметь положительные значения. Так как , то для поиска опорного решения нужно ввести дополнительно фиктивную целевую функцию , для которой отводится своя строка в симплекс-таблице (см. табл. 6).
Таблица 6. Исходная симплекс-таблица для первого сорта бензина
| 7 |
11 |
6 |
9 |
0 |
0 |
0 |
||||
| Ci
|
B |
bi
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
|
| 0 |
X5
|
-0,44 |
-0,75 |
-0,3 |
-0,65 |
-0,45 |
1 |
0 |
0 |
0,586(6) |
| 0 |
X6
|
0,198 |
0,05 |
0,35 |
0,2 |
0,2 |
0 |
1 |
0 |
3,96 |
| 0 |
X7
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
0 |
-7,5 |
-11,5 |
-6,5 |
-9,5 |
0 |
0 |
0 |
|
|
|
|
-0,44 |
-0,75 |
-0,35 |
-0,65 |
-0,45 |
0 |
0 |
0 |
Далее переходим к максимизации фиктивной целевой функции.
Для этого необходимо определить:
- разрешающий столбец. В строке оценок находим максимальную по модулю переменную, которая будет переводиться из свободных в базисные. Наибольшей является 0,75, следовательно в базис переходит х1
.
- разрешающая строка. Определяется путём нахождения наименьшего отношения элемента из bi к разрешающему столбцу. Наименьшим отношением является 0.586(6), строка, соответствующая переменной x5
.
Строим новую симплекс-таблицу (см. табл. 7), в которой меняются местами переменных х5
и х1
, вместе с коэффициентами целевой функции.
Таблица 7. Вторая симплекс-таблица для бензина первого сорта
| 0 |
11 |
6 |
9 |
0 |
0 |
0 |
||||
| Ci
|
B |
bi
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
|
| 7 |
X1
|
0,586 |
1 |
0,4 |
0,86 |
0,59 |
-1,3 |
0 |
0 |
1,465 |
| 0 |
X6
|
0,168 |
0 |
0,329 |
0,156 |
0,17 |
-0,06 |
1 |
0 |
0,51 |
| 0 |
X7
|
0,413 |
0 |
0,59 |
0,133 |
0,4 |
-1,3 |
0 |
1 |
0,7 |
|
|
|
4,4 |
0 |
-8,5 |
-2,38 |
-5 |
10 |
0 |
0 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
Элементы разрешающей строки определяются путем деления каждого элемента этой строки на главный (-0,8). Главный элемент рассчитывается путем деления единицы на самого себя. Элементы разрешающего столбца рассчитываются путем деления каждого элемента этого столбца на главный.
Все остальные элементы Таблицы 7 определяют по правилу прямоугольника.
Строка для фиктивной функции в расчётах более не участвует. После расчёта целевой функции видно, что остались отрицательные оценки, следовательно план не оптимален. Все элементы столбца bi
положительны, следовательно полученный план опорный.
Для получения оптимального решения повторяем описанный выше алгоритм пока все оценки не будут положительными (см. табл. 8).
Таблица 8. Оптимальная симплекс-таблица для бензина первого сорта
| 0 |
0 |
6 |
9 |
0 |
0 |
0 |
||||
| Ci
|
B |
bi
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
|
| 7 |
X1
|
0,382 |
1 |
0 |
0,67 |
0,39 |
-1,25 |
1,2 |
0 |
|
| 0 |
X2
|
0,511 |
0 |
1 |
0,47 |
0,17 |
-0,2 |
3,0
|
0 |
|
| 11 |
X7
|
0,106 |
0 |
0 |
-0,15 |
0,09 |
-1,2 |
1,81 |
1 |
|
|
|
|
8,74 |
0 |
0 |
4,03 |
-0,62 |
-8,2 |
8,5 |
0 |
При производстве первого вида бензина, соотношение сырой нефти к одному галлону бензина составит: x1
= 0,382; x2
=0,511; x3
=x4
=0.
Прибыль при производстве первого сорта бензина составит 8,74 цента за галлон.
2. Вычислительный эксперимент для второго сорта бензина
Целевая функция для второго сорта бензина (k=2):
Содержание фракции А, В, С для II-го сорта бензина:
Фракции С: Не более 30% - 0.3
При испарении теряется 1% - 0.01
Формула баланса:
Ограничения с учетом испарения для II-го сорта бензина:
Дальнейшие вычисления приведены в таблице 9, таблице 10 и таблице 11.
Таблица 9. Исходная симплекс-таблица для бензина второго сорта
| 4 |
8 |
3 |
6 |
0 |
0 |
||||
| Ci
|
B |
bi
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
|
| 0 |
X5
|
0,297 |
0,05 |
0,35 |
0,2 |
0,2 |
1 |
0 |
0,142 |
| 0 |
X6
|
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
|
0 |
-5 |
-9 |
-4 |
-7 |
0 |
0 |
Таблица 10. Вторая симплекс-таблица для бензина второго сорта
| 4 |
0 |
3 |
6 |
0 |
0 |
||||
| Ci
|
B |
bi
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
|
| 8 |
X2
|
0,848 |
0,142 |
1 |
0,571 |
0,571 |
1 |
0 |
1,485 |
| 0 |
X6
|
0,151 |
0,857 |
0 |
0,428 |
0,428 |
1 |
1 |
0,352 |
|
|
|
7,637 |
-3,71 |
0 |
1,142 |
-1,85 |
9 |
0 |
Таблица 11. Оптимальная симплекс-таблица для бензина второго сорта
| 4 |
0 |
3 |
0 |
0 |
0 |
||||
| Ci
|
B |
bi
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
|
| 8 |
X2
|
0,823 |
0 |
1 |
0,5 |
0,5 |
0,83 |
0,16 |
|
| 6 |
X4
|
0,176 |
1 |
0 |
0,49 |
0,49 |
1,16 |
1,16 |
|
|
|
|
8,293 |
0 |
0 |
3 |
-9,93 |
13,33 |
4,33 |
При производстве первого вида бензина, соотношение сырой нефти к одному галлону бензина составит: x1
= 0; x2
=0,823; x3
=0; x4
=0,176.
Прибыль при производстве первого сорта бензина составит 8,29 цента за галлон
Производство первого сорта бензина выгоднее на 0,45 центов.
Для визуализации расчётов будем использовать программу Simplex-Oil. Она реализована в среде разработки Borland C++Builder 2009 на языке программирования c++, и имеет интуитивно понятный интерфейс. Программа не универсальна, и умеет решать только конкретно поставленную задачу. Внешний вид программы можно увидеть на рисунке 1. После нажатия на кнопку «рассчитать» программа производит вычисления, которые можно увидеть на рисунке 2.
Для анализа на чувствительность проведём два эксперимента. Зададим случайным образом значения (см. рисунки 3 и 5) и посмотрим на результаты вычислений (см. рисунки 4 и 6).
Рисунок 1. Внешний вид программы
Рисунок 2. Программа после выполнения расчётов
Рисунок 3. Проведение первого эксперимента
Рисунок 4. Результаты первого эксперимента
Рисунок 5. Проведение второго эксперимента
Рисунок 6. Результаты второго эксперимента
Заключение
В данной работе был изучен симплекс-метод и рассмотрено его применение в задачах на составление смеси: была решена задача оптимального смешивания различных сортов нефти для наиболее выгодного производства бензина.
Симплекс-метод достаточно трудоёмок для ручного счёта, поэтому в данной работе мы показали, как можно произвести расчёты на компьютере, уменьшив тем самым шанс на ошибку.
Библиографический список
1. Аттетков А.В. Методы оптимизации: учеб. для вузов / А.В. Аттетков, С.В. Галкин, В.С. Зарубин. М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. 440 с.
2. Пантелеев А.В. Методы оптимизации в примерах и задачах: учеб. пособие/ А.В. Пантелеев, Т.А. Летова. М.: Высш. шк., 2002.
3. Математические методы в исследовании операций: Сб. статей / Под ред. Н.Н. Моисеева. М.: Изд-во MГУ, 1981.
4. Черногородова Г.М. Методы оптимизации: учеб. пособие/ Г.М. Черногородова. Ч.1. Екатеринбург: УГТУ, 2000. 80 с.
5 Черногородова Г.М. Теория принятия решений: учеб. пособие/ Г.М. Черногородова. Екатеринбург: УГТУ-УПИ, 2006. 183 с.
6 Черногородова Г.М. Методы оптимизации. Нелинейное программирование: учеб. пособие /Г.М. Черногородова. Екатеринбург: УГТУ-УПИ, 2007. 113 с.
Приложение
Программа Simlex-Oil
---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma link "sGroupBox"
#pragma link "sSkinManager"
#pragma link "sSkinProvider"
#pragma link "sStatusBar"
#pragma link "sEdit"
#pragma link "sButton"
#pragma link "sLabel"
#pragma link "sMemo"
#pragma resource "*.dfm"
TForm1 *Form1;
---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N2Click(TObject *Sender)
{
Application->Terminate();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::sButton1Click(TObject *Sender)
{
//Защита от дурака
if (!Edit00->Text.Compare("") || !Edit01->Text.Compare("") || !Edit02->Text.Compare("") || !Edit03->Text.Compare("") || !Edit10->Text.Compare("") || !Edit11->Text.Compare("") || !Edit12->Text.Compare("") || !Edit13->Text.Compare("") || !Edit20->Text.Compare("") || !Edit21->Text.Compare("") || !Edit22->Text.Compare("") || !Edit23->Text.Compare("") || !Edit30->Text.Compare("") || !Edit31->Text.Compare("") || !Edit32->Text.Compare("") || !Edit33->Text.Compare("") || !Edit40->Text.Compare("") || !Edit41->Text.Compare("") || !Edit42->Text.Compare("") || !Edit43->Text.Compare("") || !Edit001->Text.Compare("") || !Edit101->Text.Compare("") || !Edit201->Text.Compare("") || !Edit301->Text.Compare("") || !Edit401->Text.Compare("") || !Edit011->Text.Compare("") || !Edit111->Text.Compare("") || !Edit211->Text.Compare("") || !Edit311->Text.Compare("") || !Edit411->Text.Compare("") || !Edit021->Text.Compare("") || !Edit121->Text.Compare("") || !Edit221->Text.Compare("") || !Edit321->Text.Compare("") || !Edit421->Text.Compare("")) {
ShowMessage("Не все поля заполнены");
}
else {
Edit04->Text=Edit00->Text;
Edit14->Text=Edit10->Text;
Edit24->Text=Edit20->Text;
Edit34->Text=Edit30->Text;
Edit44->Text=Edit40->Text;
//Расчет для первой задачи
int tmpI, tmpJ, tmpX, tmpY, tmpP;
float tmp, Price1;
float Mat[5][5], Mat1[5][5], Mat2[5][5];
// заполнение матрицы для первой задачи
for (tmpX=0; tmpX<=4; tmpX++)
for (tmpY=0; tmpY<=4; tmpY++)
Mat[tmpX][tmpY]=0;
Mat[0][0]=StrToFloat(Edit00->Text);
Mat[0][1]=StrToFloat(Edit01->Text);
Mat[0][2]=StrToFloat(Edit02->Text);
Mat[0][3]=StrToFloat(Edit03->Text);
Mat[0][4]=StrToFloat(Edit04->Text);
Mat[1][0]=StrToFloat(Edit10->Text);
Mat[1][1]=StrToFloat(Edit11->Text);
Mat[1][2]=StrToFloat(Edit12->Text);
Mat[1][3]=StrToFloat(Edit13->Text);
Mat[1][4]=StrToFloat(Edit14->Text);
Mat[2][0]=StrToFloat(Edit20->Text);
Mat[2][1]=StrToFloat(Edit21->Text);
Mat[2][2]=StrToFloat(Edit22->Text);
Mat[2][3]=StrToFloat(Edit23->Text);
Mat[2][4]=StrToFloat(Edit24->Text);
Mat[3][0]=StrToFloat(Edit30->Text);
Mat[3][1]=StrToFloat(Edit31->Text);
Mat[3][2]=StrToFloat(Edit32->Text);
Mat[3][3]=StrToFloat(Edit33->Text);
Mat[3][4]=StrToFloat(Edit34->Text);
Mat[4][0]=StrToFloat(Edit40->Text);
Mat[4][1]=StrToFloat(Edit41->Text);
Mat[4][2]=StrToFloat(Edit42->Text);
Mat[4][3]=StrToFloat(Edit43->Text);
Mat[4][4]=StrToFloat(Edit44->Text);
//Находим среди отрицательных элементов максимальное по модулю
tmp=0;
tmpP=0;
for (tmpX=0; tmpX<=4; tmpX++)
if (Mat[tmpX][4]<0)
if (fabs(tmp)<fabs(Mat[tmpX][4]))
{
tmp=Mat[tmpX][4];
tmpP=tmpX;
}
//В столце находим минимальный элемент
tmp=100;
tmpX=tmpP;
for (tmpY=0; tmpY<=4; tmpY++)
{
if ((Mat[tmpX][tmpY]!=0)&&(tmpY!=3))
if (Mat[0][tmpY]/Mat[tmpX][tmpY]<tmp)
{
tmp=Mat[0][tmpY]/Mat[tmpX][tmpY];
tmpP=tmpY;
}
}
//Делим на получившийся главный элемент
tmpY=tmpP;
for (int i = 0; i <= 4; i++)
for (int j=0; j <= 4; j++)
Mat1[i][j]=Mat[i][j];
tmp=Mat[tmpX][tmpY];
for (tmpP=0; tmpP<=4; tmpP++)
Mat1[tmpX][tmpP]=Mat1[tmpX][tmpP]/tmp;
for (tmpP=0; tmpP<=4; tmpP++)
Mat1[tmpP][tmpY]=Mat1[tmpP][tmpY]/tmp;
switch (tmpY) {
case 0: {
X5->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X1->Caption="X5"; break;
case 2: X2->Caption="X5"; break;
case 3: X3->Caption="X5"; break;
case 4: X4->Caption="X5"; break;
}
}; break;
case 1: {
X6->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X1->Caption="X6"; break;
case 2: X2->Caption="X6"; break;
case 3: X3->Caption="X6"; break;
case 4: X4->Caption="X6"; break;
}
}; break;
case 2: {
X7->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X1->Caption="X7"; break;
case 2: X2->Caption="X7"; break;
case 3: X3->Caption="X7"; break;
case 4: X4->Caption="X7"; break;
}
}; break;
}
Mat1[tmpX][4]=Mat1[tmpX][4]*(-1);
for (tmpI=0; tmpI<=4; tmpI++)
for (tmpJ=0; tmpJ<=4; tmpJ++)
if ((tmpI!=tmpX)&&(tmpJ!=tmpY) )
{
Mat1[tmpI][tmpJ]=Mat[tmpI][tmpJ]-(Mat[tmpX][tmpJ]*Mat[tmpI][tmpY])/tmp;
}
//*********************************************************
//поиск оптимального решения
for (int i = 0; i <= 4; i++)
for (int j=0; j <= 4; j++)
Mat2[i][j]=Mat1[i][j];
sMemo1->Lines->Add("Задача №1.");
sMemo1->Lines->Add("Опорное решение:");
sMemo1->Lines->Add(X5->Caption+"="+FloatToStr(Mat2[0][0])+" "+X6->Caption+"="+FloatToStr(Mat2[0][1])+" "+X7-
>Caption+"="+FloatToStr(Mat2[0][2]));
sMemo1->Lines->Add("f(x)="+FloatToStr(Mat2[0][3]));
tmp=0;
tmpP=0;
for (tmpX=0; tmpX<=4; tmpX++)
if (Mat1[tmpX][3]<0)
if (fabs(tmp)<fabs(Mat1[tmpX][3]))
{
tmp=Mat1[tmpX][3];
tmpP=tmpX;
}
//ShowMessage(FloatToStr(tmp)+" "+IntToStr(tmpP));
//В столбце находим минимальный элемент
tmp=400;
tmpX=tmpP;
tmpJ=tmpY;
for (tmpY=0; tmpY<=2; tmpY++)
{
if ((Mat1[tmpX][tmpY]!=0) && (tmpY!=tmpJ) )
if (Mat1[0][tmpY]/Mat1[tmpX][tmpY]<tmp )
{
tmp=Mat1[0][tmpY]/Mat1[tmpX][tmpY];
tmpP=tmpY;
}
}
//ShowMessage(FloatToStr(tmp)+" "+IntToStr(tmpP));
//Делим на получившийся элемент
tmpY=tmpP;
for (int i = 0; i <= 4; i++)
for (int j=0; j <= 4; j++)
Mat2[i][j]=Mat1[i][j];
tmp=Mat1[tmpX][tmpY];
for (tmpP=0; tmpP<4; tmpP++)
Mat2[tmpP][tmpY]=Mat2[tmpP][tmpY]/tmp;
for (tmpP=0; tmpP<3; tmpP++)
Mat2[tmpX][tmpP]=Mat2[tmpX][tmpP]/tmp;
switch (tmpY) {
case 0: {
X5->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X1->Caption="X5"; break;
case 2: X2->Caption="X5"; break;
case 3: X3->Caption="X5"; break;
case 4: X4->Caption="X5"; break;
}
}; break;
case 1: {
X6->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X1->Caption="X6"; break;
case 2: X2->Caption="X6"; break;
case 3: X3->Caption="X6"; break;
case 4: X4->Caption="X6"; break;
}
}; break;
case 2: {
X7->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X1->Caption="X7"; break;
case 2: X2->Caption="X7"; break;
case 3: X3->Caption="X7"; break;
case 4: X4->Caption="X7"; break;
}
}; break;
}
Mat2[tmpX][3]=Mat2[tmpX][3]*(-1);
//вывод получившегося решения
for (tmpI=0; tmpI<=4; tmpI++)
for (tmpJ=0; tmpJ<=4; tmpJ++)
if ((tmpI!=tmpX)&&(tmpJ!=tmpY) )
{
Mat2[tmpI][tmpJ]=Mat1[tmpI][tmpJ]-(Mat1[tmpX][tmpJ]*Mat1[tmpI][tmpY])/tmp;
}
Mat2[1][3]=Mat2[1][3]*(-1);
sMemo1->Lines->Add("Оптимальное решение:");
sMemo1->Lines->Add(X5->Caption+"="+FloatToStr(Mat2[0][0])+" "+X6->Caption+"="+FloatToStr(Mat2[0][1])+" "+X7->Caption+"="+FloatToStr(Mat2[0][2]));
sMemo1->Lines->Add("f(x)="+FloatToStr(Mat2[0][3]));
Edit00->Text=FloatToStr(Mat2[0][0]);
Edit01->Text=FloatToStr(Mat2[0][1]);
Edit02->Text=FloatToStr(Mat2[0][2]);
Edit03->Text=FloatToStr(Mat2[0][3]);
Edit04->Text=FloatToStr(Mat2[0][4]);
Edit10->Text=FloatToStr(Mat2[1][0]);
Edit11->Text=FloatToStr(Mat2[1][1]);
Edit12->Text=FloatToStr(Mat2[1][2]);
Edit13->Text=FloatToStr(Mat2[1][3]);
Edit14->Text=FloatToStr(Mat2[1][4]);
Edit20->Text=FloatToStr(Mat2[2][0]);
Edit21->Text=FloatToStr(Mat2[2][1]);
Edit22->Text=FloatToStr(Mat2[2][2]);
Edit23->Text=FloatToStr(Mat2[2][3]);
Edit24->Text=FloatToStr(Mat2[2][4]);
Edit30->Text=FloatToStr(Mat2[3][0]);
Edit31->Text=FloatToStr(Mat2[3][1]);
Edit32->Text=FloatToStr(Mat2[3][2]);
Edit33->Text=FloatToStr(Mat2[3][3]);
Edit34->Text=FloatToStr(Mat2[3][4]);
Edit40->Text=FloatToStr(Mat2[4][0]);
Edit41->Text=FloatToStr(Mat2[4][1]);
Edit42->Text=FloatToStr(Mat2[4][2]);
Edit43->Text=FloatToStr(Mat2[4][3]);
Edit44->Text=FloatToStr(Mat2[4][4]);
Price1=Mat2[0][3];
//Расчет для второй задачи
for (tmpX=0; tmpX<=4; tmpX++)
for (tmpY=0; tmpY<=2; tmpY++)
Mat[tmpX][tmpY]=0;
Mat[0][0]=StrToFloat(Edit001->Text);
Mat[0][1]=StrToFloat(Edit011->Text);
Mat[0][2]=StrToFloat(Edit021->Text);
Mat[1][0]=StrToFloat(Edit101->Text);
Mat[1][1]=StrToFloat(Edit111->Text);
Mat[1][2]=StrToFloat(Edit121->Text);
Mat[2][0]=StrToFloat(Edit201->Text);
Mat[2][1]=StrToFloat(Edit211->Text);
Mat[2][2]=StrToFloat(Edit221->Text);
Mat[3][0]=StrToFloat(Edit301->Text);
Mat[3][1]=StrToFloat(Edit311->Text);
Mat[3][2]=StrToFloat(Edit321->Text);
Mat[4][0]=StrToFloat(Edit401->Text);
Mat[4][1]=StrToFloat(Edit411->Text);
Mat[4][2]=StrToFloat(Edit421->Text);
//Находим среди отрицательных максимальное по модулю
tmp=0;
tmpP=0;
for (tmpX=0; tmpX<=4; tmpX++)
if (Mat[tmpX][2]<0)
if (fabs(tmp)<fabs(Mat[tmpX][2])) {
tmp=Mat[tmpX][2];
tmpP=tmpX;
}
//В столбце находим минимальный элемент
tmp=100;
tmpX=tmpP;
for (tmpY=0; tmpY<=1; tmpY++)
{
if (Mat[tmpX][tmpY]!=0)
if (Mat[0][tmpY]/Mat[tmpX][tmpY]<tmp)
{
tmp=Mat[0][tmpY]/Mat[tmpX][tmpY];
tmpP=tmpY;
}
}
//Делим на получившийся главный элемент
tmpY=tmpP;
for (int i = 0; i <= 4; i++)
for (int j=0; j <= 4; j++)
Mat1[i][j]=Mat[i][j];
for (tmpP=0; tmpP<= 2; tmpP++)
tmp=Mat[tmpX][tmpY];
Mat1[tmpX][tmpP]=Mat1[tmpX][tmpP]/tmp;
for (tmpP=0; tmpP<= 4; tmpP++)
Mat1[tmpP][tmpY]=Mat1[tmpP][tmpY]/tmp;
switch (tmpY){
case 0: {
X51->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X11->Caption="X5"; break;
case 2: X21->Caption="X5"; break;
case 3: X31->Caption="X5"; break;
case 4: X41->Caption="X5"; break;
}
}; break;
case 1: {
X61->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X11->Caption="X6"; break;
case 2: X21->Caption="X6"; break;
case 3: X31->Caption="X6"; break;
case 4: X41->Caption="X6"; break;
}
} break;
}
Mat1[tmpX][2]=Mat1[tmpX][2]*(-1);
for (tmpI=0; tmpI<=4; tmpI++)
for (tmpJ=0; tmpJ<=2; tmpJ++)
if ((tmpI!=tmpX)&&(tmpJ!=tmpY))
{
Mat1[tmpI][tmpJ]=Mat[tmpI][tmpJ]-(Mat[tmpX][tmpJ]*Mat[tmpI][tmpY])/tmp;
}
//Вывод базового решения.
for (int i = 0; i <= 4; i++)
for (int j=0; j <= 4; j++)
Mat2[i][j]=Mat1[i][j];
sMemo1->Lines->Add("Задача №2.");
sMemo1->Lines->Add("Опорное решение:");
sMemo1->Lines->Add(X51->Caption+"="+FloatToStr(Mat2[0][0])+" "+X61->Caption+"="+FloatToStr(Mat2[0][1]));
sMemo1->Lines->Add("f(x)="+FloatToStr(Mat2[0][2]));
//*********************************************************
// поиск оптимального решения
tmp=0;
tmpP=0;
for (tmpX=0; tmpX<=4; tmpX++)
if (Mat1[tmpX][2]<0)
if (fabs(tmp)<fabs(Mat1[tmpX][2]))
{
tmp=Mat1[tmpX][2];
tmpP=tmpX;
}
//В столбце находим минимальный элемент
tmp=1000;
tmpX=tmpP;
tmpJ=tmpY;
for (tmpY=0; tmpY<=1; tmpY++)
{
if ((Mat1[tmpX][tmpY]!=0) && (tmpY!=tmpJ))
if (Mat1[0][tmpY]/Mat1[tmpX][tmpY]<tmp)
{
tmp=Mat1[0][tmpY]/Mat1[tmpX][tmpY];
tmpP=tmpY;
}
}
//Делим на получившийся элемент
tmpY=tmpP;
for (int i = 0; i <= 4; i++)
for (int j=0; j <= 4; j++)
Mat2[i][j]=Mat1[i][j];
tmp=Mat1[tmpX][tmpY];
for (tmpP=0; tmpP<=4; tmpP++)
Mat2[tmpP][tmpY]=Mat2[tmpP][tmpY]/tmp;
for (tmpP=0; tmpP<=2; tmpP++)
Mat2[tmpX][tmpP]=Mat2[tmpX][tmpP]/tmp;
switch (tmpY){
case 0: {
X51->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X11->Caption="X5"; break;
case 2: X21->Caption="X5"; break;
case 3: X31->Caption="X5"; break;
case 4: X41->Caption="X5"; break;
}
}; break;
case 1: {
X61->Caption="X"+IntToStr(tmpX);
switch (tmpX) {
case 1: X11->Caption="X6"; break;
case 2: X21->Caption="X6"; break;
case 3: X31->Caption="X6"; break;
case 4: X41->Caption="X6"; break;
}
} break;
}
Mat2[tmpX][2]=Mat2[tmpX][2]*(-1);
//вывод получившегося решения
for (tmpI=0; tmpI<=4; tmpI++)
for (tmpJ=0; tmpJ<=2; tmpJ++)
if ((tmpI!=tmpX)&&(tmpJ!=tmpY))
{
Mat2[tmpI][tmpJ]=Mat1[tmpI][tmpJ]-(Mat1[tmpX][tmpJ]*Mat1[tmpI][tmpY])/tmp;
}
sMemo1->Lines->Add("Оптимальное решение:");
sMemo1->Lines->Add(X51->Caption+"="+FloatToStr(Mat2[0][0])+" "+X61->Caption+"="+FloatToStr(Mat2[0][1]));
sMemo1->Lines->Add("f(x)="+FloatToStr(Mat2[0][2]));
Edit001->Text=FloatToStr(Mat2[0][0]);
Edit011->Text=FloatToStr(Mat2[0][1]);
Edit021->Text=FloatToStr(Mat2[0][2]);
Edit101->Text=FloatToStr(Mat2[1][0]);
Edit111->Text=FloatToStr(Mat2[1][1]);
Edit121->Text=FloatToStr(Mat2[1][2]);
Edit201->Text=FloatToStr(Mat2[2][0]);
Edit211->Text=FloatToStr(Mat2[2][1]);
Edit221->Text=FloatToStr(Mat2[2][2]);
Edit301->Text=FloatToStr(Mat2[3][0]);
Edit311->Text=FloatToStr(Mat2[3][1]);
Edit321->Text=FloatToStr(Mat2[3][2]);
Edit401->Text=FloatToStr(Mat2[4][0]);
Edit411->Text=FloatToStr(Mat2[4][1]);
Edit421->Text=FloatToStr(Mat2[4][2]);
sMemo1->Lines->Add("*********************************");
sMemo1->Lines->Add("Прибыль по первому сорту бензина: "+FloatToStr(Price1));
sMemo1->Lines->Add("Прибыль по второму сорту бензина: "+FloatToStr(Mat2[0][2]));
if (Price1<Mat2[0][2]) {
sMemo1->Lines->Add("Второй сорт бензина выгоднее на "+FloatToStr(Mat2[0][2]-Price1));
}
if (Price1>Mat2[0][2]) {
sMemo1->Lines->Add("Первый сорт бензина выгоднее на "+FloatToStr(Price1-Mat2[0][2]));
}
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N4Click(TObject *Sender)
{
ShowMessage("Симплекс-метод для решения задачи на смеси!");
}