Решение оптимизационных задач линейного программирования
Составление плана работы нефтеперерабатывающего предприятия, обеспечивающего получение максимальной прибыли. Построение базовой аналитической модели, а также обоснование вычислительной процедуры. Решение задачи оптимизации на основе симплекс-метода.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 31.03.2013 |
| Размер файла | 26,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Решение оптимизационных задач линейного программирования
1. Постановка задачи
Нефтеперерабатывающее предприятие выпускает два вида бензина: обычный и повышенного качества. Выпуск одного барреля обычного бензина приносит предприятию прибыль в размере 7 ден. ед., бензина повышенного качества - 12 ден. ед. Для выполнения заказов предприятию необходимо выпускать не менее 20 тыс. баррелей обычного бензина в день. Спрос на обычный бензин не превышает 80 тыс. баррелей в день, на бензин повышенного качества - 50 тыс. баррелей в день.
Сырая нефть, поступающая на предприятие, проходит обработку на перегонной колонне. В результате перегонки вырабатывается бензиновый полуфабрикат. Мощность перегонной колонный - 600 тыс. баррелей сырой нефти в день. На производство одного барреля бензинового полуфабриката расходуется пять баррелей сырой нефти.
Часть бензинового полуфабриката непосредственно используется для производства бензина, часть - направляется на крекинг-установку - 40 тыс. баррелей бензинового полуфабриката теряется.
Для получения обычного бензина полуфабрикат и дистиллят смешивается в соотношении 3:1, для получения бензина повышенного качества - в соотношении 1:4.
Составить план работы нефтеперерабатывающего предприятия, обеспечивающий получение максимальной прибыли.
Таблица 1
|
Вид топлива |
полуфабрикат |
дистиллят |
|
|
Обычный бензин |
3 |
1 |
|
|
Бензин повышенного качества |
1 |
4 |
2. Построение базовой аналитической модели
В данной задаче требуется определить, сколько необходимо произвести бензинового полуфабриката и дистиллята, чтобы получить максимальную прибыль.
Для построения математической модели задачи введем переменные. Обозначим через Х1 производство бензинового полуфабриката, через Х2 - дистиллят. В данной задаче имеются ограничения на расход ресурсов (таблица 1) и производства бензина.
Составим ограничение на производство бензина. На производство одного барреля обычного бензина необходимо 3/4 барреля бензинового полуфабриката и 1/4 барреля дистиллята.
X1 ? 20000.
X1 ? 80000.
Аналогично составим ограничение и для бензина повышенного качества:
X2 ? 50000.
Имеется также ограничение на производство ресурсов:
0.75•X1 + 0.2•X2? 120000.
0.25•X1 + 0.8•X2 ? 32000.
Кроме того, переменные x1, x2 по своему физическому смыслу не могут принимать отрицательные значения, так как они обозначают количество баррелей бензина. Поэтому необходимо указать ограничение неотрицательности:
Xi ? 0, i = 1, 2.
В данной задаче требуется определить производство бензинового полуфабриката и дистиллята, обеспечивающее максимальную прибыль. Определим прибыль от выпуска каждой модели радиатора.
Целевая функция для данной задачи будет иметь следующий вид:
Е = 7•Х1 + 12•Х2 > max.
Приведем полную математическую модель рассматриваемой задачи:
X1 ? 20000
X1 ? 80000
X2 ? 50000
0.75•X1 + 0.2•X2? 120000
0.25•X1 + 0.8•X2 ? 32000
Хi ? 0, i = 1,…, 2
Е = 7•Х1 + 12•Х2 > max.
3. Обоснование вычислительной процедуры
Все ограничения и целевая функция в данной задаче линейны, поэтому для ее решения можно использовать симплекс-метод.
В математической модели задачи имеется ограничение «больше или равно». После приведения такого ограничения к стандартной форме в нем не содержится базисной переменной. Поэтому для решения задачи потребуется использовать один из методов искусственного базиса. В данном случае будет применен двухэтапный метод.
На переменные X1, X2 наложены ограничения целочисленности, поэтому, если при решении задачи симплекс-методом одна из них примет дробное значение, то необходимо будет воспользоваться одним из методов целочисленного программирования.
4. Решение задачи оптимизации на основе симплекс-метода
Приведем математическую модель задачи к стандартной форме. Для этого в ограничении «больше или равно» потребуется ввести избыточную переменную, а в ограничения «меньше или равно» - остаточные:
X1 - X3 = 20000
X1 + X4 = 80000
X2 + X5 = 50000
0.75•X1 + 0.2•X2 + X6 = 120000
0.25•X1 + 0.8•X2 + X7 = 32000
Хi ? 0, i = 1,…, 7
Х1,…, Х7, - целые числа
Е = 7•Х1 + 12•Х2 > max.
В ограничении X1 - X3 = 20000 отсутствует базисная переменная (т.е. переменная, входящая только в данное ограничение с коэффициентом, равным единице). Поэтому требуется ввести искусственную переменную:
X1 - X3 + X8 = 20000.
Таким образом, в каждом ограничении имеется базисная переменная (x4, x5, x6, x7, x8). Остальные переменные - небазисные.
Составляется искусственная целевая функция - сумма искусственных переменных (в данном случае имеется только одна искусственная переменная):
W = x8 > min.
Искусственная целевая функция выражается через небазисные переменные. Для этого сначала выразим искусственную переменную через небазисные переменные:
X8 = 20000 -•X1 + X3.
И подставим ее в искусственную целевую функцию:
W = 20000 -•X1 + X3 > min.
Для приведения всей задачи к стандартной форме требуется перейти к искусственной целевой функции, подлежащей максимизации.
W = - 20000 +•X1 - X3 > max.
Приведем полную математическую модель задачи в стандартной форме и с искусственным базисом:
X1 - X3 + X8 = 20000
X1 + X4 = 80000
X2 + X5 = 50000
0.75•X1 + 0.2•X2 + X6 = 120000
0.25•X1 + 0.8•X2 + X7 = 32000
Хi ? 0, i = 1,…, 8
Х1,…, Х8, - целые числа
Е = 7•Х1 + 12•Х2 > max
W = - 20000 +•X1 - X3 > max.
Составим первую симплекс-таблицу (таблица 2).
Таблица 2
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
Решение |
|
|
E |
-7 |
-12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
-W |
-1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-20000 |
|
|
X 8 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
20000 |
|
|
X 4 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
80000 |
|
|
X 5 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
50000 |
|
|
X 6 |
0,75 |
0,2 |
0 |
0 |
0 |
1 |
0 |
0 |
120000 |
|
|
X 7 |
0,25 |
0,8 |
0 |
0 |
0 |
0 |
1 |
0 |
32000 |
Приведенное в таблице 2 начальное решение (X1 = X2 = X3 = 0, X4 = 80000, X5=50000, X6 = 120000, X7 = 32000, X8 = 20000) является недопустимым: оно не соответствует начальной системе ограничений, так как не выполняется условие X1? 20000.
Для поиска начального допустимого решения реализуется первый этап двухэтапного метода: минимизация искусственной целевой функции на основе процедур симплекс-метода.
Выбирается переменная для включения в базис: это переменная X1, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции.
Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 20000/0,75 = 26666,67, 80000/0,75 = 106666,67, 50000/0,2 = 250000, 120000/1=120000 Минимальное симплексное отношение соответствует переменной X8, значит, эта переменная исключается из базиса.
В результате преобразований по правилам симплекс-метода будет получена следующая симплекс-таблица (таблица 3).
Таблица 3
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
Решение |
|
|
E |
0 |
-12 |
-7 |
0 |
0 |
0 |
0 |
7 |
140000 |
|
|
-W |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
X1 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
20000 |
|
|
X4 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
-1 |
60000 |
|
|
X5 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
50000 |
|
|
X6 |
0 |
0,2 |
0,75 |
0 |
0 |
1 |
0 |
-0,75 |
105000 |
|
|
X7 |
0 |
0,8 |
0,25 |
0 |
0 |
0 |
1 |
-0,25 |
27000 |
Как видно из таблицы 3, искусственная целевая функция равна нулю, и в базисе нет искусственных переменных. Получено допустимое решение: X1 = 20000, X2 = X3 = X8 = 0, X4 = 60000, X5 = 50000, X6 = 105000, X7 = 27000. В том, что оно допустимо, легко убедиться, подставив значения переменных в систему ограничений.
Таким образом, первый этап двухэтапного метода завершен. Искусственная целевая функция и искусственные переменные исключаются из симплекс-таблицы (таблица 4).
Таблица 4
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Решение |
|
|
E |
0 |
-12 |
-7 |
0 |
0 |
0 |
0 |
140000 |
|
|
X1 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
20000 |
|
|
X4 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
60000 |
|
|
X5 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
50000 |
|
|
X6 |
0 |
0,2 |
0,75 |
0 |
0 |
1 |
0 |
105000 |
|
|
X7 |
0 |
0,8 |
0,25 |
0 |
0 |
0 |
1 |
27000 |
Полученное решение является допустимым, но не оптимальным: признак неоптимальности решения - наличие отрицательных коэффициентов в строке целевой функции Е. Поэтому реализуется второй этап двухэтапного метода: максимизация основной целевой функции Е.
В базис включается переменная X2, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке целевой функции. Для определения переменной, исключаемой из базиса, вычисляются симплексные отношения: 50000/1 = 50000, 2700/0,8 = 33750, 105000/0.2 = 525000. Минимальное симплексное отношение соответствует переменной X7, значит, эта переменная исключается из базиса. После преобразования по правилам симплекс-метода будет получена новая симплекс-таблица (таблица 5).
Таблица 5
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Решение |
|
|
E |
0 |
0 |
-3,25 |
0 |
0 |
0 |
15 |
545000 |
|
|
X1 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
20000 |
|
|
X4 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
60000 |
|
|
X5 |
0 |
0 |
-0,3125 |
0 |
1 |
0 |
-1,25 |
16250 |
|
|
X6 |
0 |
0 |
0,6875 |
0 |
0 |
1 |
-0,25 |
98250 |
|
|
X2 |
0 |
1 |
0,3125 |
0 |
0 |
0 |
1,25 |
33750 |
Решение, полученное в таблице 5, еще не является оптимальным (в строке целевой функции имеется отрицательный коэффициент). Поэтому продолжаются вычисления по правилам симплекс-метода. В базис включается переменная X3. Для определения переменной, исключаемой из базиса, вычисляем симплексные отношения: 60000/1 = 60000, 98250/0,6875 = 142909,09, 33750/0,3125 = 108000. Минимальное симплексное отношение соответствует переменной X4, значит, эта переменная исключается из базиса. По результатам преобразований по правилам симплекс-метода будет получена новая симплекс-таблица (таблица 6)
Таблица 6
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Решение |
|
|
E |
0 |
0 |
0 |
3,25 |
0 |
0 |
15 |
740000 |
|
|
X1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
80000 |
|
|
X3 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
60000 |
|
|
X5 |
0 |
0 |
0 |
0,3125 |
1 |
0 |
-1,25 |
35000 |
|
|
X6 |
0 |
0 |
0 |
-0,6875 |
0 |
1 |
-0,25 |
57000 |
|
|
X2 |
0 |
1 |
0 |
-0,3125 |
0 |
0 |
1,25 |
15000 |
Получено оптимальное решение (признак его оптимальности - отсутствие отрицательных элементов в строке целевой функции). Основные переменные задачи приняли следующие значения: X1 = 80000, X2 = 15000, X3 = 60000, X4 = X7 = 0, X5 = 35000, X6 = 57000. Это означает, что необходимо произвести 800000 баррелей обычного бензина и 15000 баррелей бензина повышенного качества.
Избыточная переменная X3 = 60000 означает, что производство обычного бензина на 60000 баррелей превысит минимально необходимую величину (требуется произвести не менее 20000 баррелей обычного бензина, а оптимальный объем производства 80000 баррелей обычного бензина).
Остаточная переменная X5 = 35000 означает, что производство бензина повышенного качества на 35000 баррелей меньше максимально возможной величины (требуется произвести не более 50000 баррелей бензина повышенного качества, а оптимальный объём производства 15000 баррелей бензина повышенного качества).
Остаточные переменные X6 = 57000 и X7 = 0 означают, что производство бензинового полуфабриката на 57000 барреля меньше от максимально возможной величины (требуется произвести не более 120000 баррелей бензинового полуфабриката, а оптимальный объём производства 63000 баррелей бензинового полуфабриката) и что запас дистиллята был израсходован полностью (оптимальный объём производства 32000 барреля дистиллята).
Список источников
[1] Смородинский, С.С. Оптимизация решений на основе методов и моделей математического программирования / С.С. Смородинский, Н.В. Батин. - Мн.: БГУИР, 2003. - 136 с.
[2] Вентцель, Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2001. - 208 с.
[3] Таха, Х. Введение в исследование операций. М.: Издательский дом «Вильямс», 2005. - 912 с.
[4] Смородинский, С.С., Батин, Н.В. Системный анализ и исследование операций: сборник заданий и метод. Указаний по курсовому проектированию для студ. Спец. 1-53 01 02 «Автоматизированные системы обработки информации» дневн. И дистан. Форм обуч. / - Мн.: БГУИР, 2003. - 136 с.
прибыль модель оптимизация симплекс
Размещено на Allbest.ru
...Подобные документы
Задачи операционного исследования. Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе технологии симплекс-метода. Анализ результатов базовой аналитической модели и предложения по модификации.
курсовая работа [1,5 M], добавлен 12.12.2009Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе симплекс-таблиц. Анализ на чувствительность к изменению. Примеры постановок и решений перспективных оптимизационных управленческих задач.
курсовая работа [621,6 K], добавлен 16.02.2015- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
курсовая работа [54,1 K], добавлен 05.03.2010Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
задача [579,8 K], добавлен 11.07.2010Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Характеристика и описание метода линейного программирования, основные области его применения и ограничения использования. Решение экономических задач, особенности формирования оптимизационной модели, расчет и анализ результатов оптимизации прибыли.
курсовая работа [99,0 K], добавлен 23.03.2010Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
курсовая работа [105,5 K], добавлен 02.10.2014Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
контрольная работа [40,0 K], добавлен 04.05.2014Главные элементы сетевой модели. Задача линейного программирования. Решение симплекс-методом. Составление отчетов по результатам, по пределам, по устойчивости. Составление первоначального плана решения транспортной задачи по методу северо-западного угла.
контрольная работа [747,3 K], добавлен 18.05.2015Составление математической модели и решение задачи планирования выпуска продукции, обеспечивающего получение максимальной прибыли. Нахождение оптимального решения двойственной задачи с указанием дефицитной продукции при помощи теорем двойственности.
контрольная работа [232,3 K], добавлен 02.01.2012Построение одноиндексной математической модели задачи линейного программирования, ее решение графическим методом. Разработка путей оптимизации сетевой модели по критерию "минимум исполнителей". Решение задачи управления запасами на производстве.
контрольная работа [80,8 K], добавлен 13.12.2010Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат [583,3 K], добавлен 15.06.2010Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.
курсовая работа [111,1 K], добавлен 16.01.2011Решение задач линейного программирования с применением алгоритма графического определения показателей и значений, с использованием симплекс-метода. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана ЗЛП.
контрольная работа [94,6 K], добавлен 23.04.2013
