Решение задачи о смесях симплексным методом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
5_> и нелинейного программирования .
.">Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Линейное программирование (планирование) служит для выбора наилучшего плана распределения ограниченных однородных ресурсов в целях решения поставленной задачи.
Для решения задач линейного программирования созданы специальные методы. Изучению одного из них, а именно задаче о смесях, посвящена эта курсовая работа.
Актуальность данной темы в современном мире, особенно во времена мирового экономического кризиса, когда нужен четкий план развития предприятия и жесткий контроль за выполнением найденного оптимального плана.
Задачи курсовой работы:
-изучить теоретический материал по данной теме;
-решить поставленную задачу;
-разработать алгоритм для решения данной задачи;
-автоматизировать процесс решения;
-разработать программу для решения задач данного класса.
Каждая из этих задач является частным случаем общей задачи линейного программирования.
Программа будет разработана в среде Borland Delphi 7. Системные требования: процессор с частотой свыше 300 МГц, Windows 98/SE/2000/ME/XP/Vista/Win 7, 128 RAM.
3. Общая характеристика задачи о смесях
От того, как будут распределяться ограниченные ресурсы, зависит конечный результат деятельности бизнеса, т. е., успешность решения подавляющего большинства экономических задач зависит от наилучшего способа использования ресурсов.
В результате чего и разработали методы решения данных задач, называемых оптимизационными методами задач распределения, основные из них: симплекс-метод, двойственный симплекс-метод, метод искусственного базиса, графический метод и решение задач средствами Excel через Поиск решений.
К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов.
4. Аналитическое решение
Задача:
Нефтеперерабатывающий завод получает четыре полуфабриката:
тыс. л. алкилата;
тыс. л. крекинг-бензина;
тыс. л. бензина прямой перегонки;
тыс. л. изопентона;
В результате смешивания этих четырёх компонентов в разных пропорциях образуются три сорта авиационного бензина:
Бензин А - 2 : 3 : 5 : 2 ;
Бензин В - 3 : 1 : 2 : 1 ;
Бензин С - 2 : 2 : 1 : 3 ;
Стоимость 1 тыс.л. указанных сортов бензина:
Бензин А - 120 руб.
Бензин Б - 100 руб.
Бензин С - 150 руб.
Необходимо определить план смешения компонентов, при котором будет достигнута максимальная стоимость все продукции.
Сводная таблица условий задачи:
Таблица1
Компоненты, используемые для производства трёх видов бензина.Сорта производимого бензинаОбъем ресурсов (тыс. л)АВСАлкилат400Крекинг-бензин250Бензин прямой перегонки300Изопентат250Цена бензина (рублей за 1 тыс.л.)120100150
5. Математическая постановка задачи
Составим математическую модель задачи. Обозначим через t1 количество бензина А, через t2 количество бензина В, через t3 количество бензина С. Тогда, целевая функция будет:
L=y1t1+ y2t2+ y3t3=120t1+100t2+150t3 >max
Система ограничений:
Приведем систему ограничений к виду основной задачи линейного программирования (введем новые переменные t4 , t5 ,t6 ,t7, которые входят в целевую функцию с нулевыми коэффициентами):
Выберем t1 , t2 ,t3 свободными переменными, а t4 , t5 ,t6 ,t7 - базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L=0-(-120t1-100t2-150t3)
Составим симплекс-таблицу.
Это решение опорное, т.к. все свободные члены положительны.
Т. к. все коэффициенты в целевой функции отрицательные, то можно взять любой столбец разрешающим (пусть t1). Выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это t7)
Таблица 2
bt1t2t3 L0 -120 -100 -150 6000 60 60 180t4400 2 3 2 400/2=200 -100 -1 -1 -3t5250 3 1 2 250/3=83,3 -150 -1,5 -1,5 -4,5t6350 5 2 1 350/5=70 -250 -2,5-2,5 -7,5t7100 21 3 100/2=50 50 0,5 0,5 1,5
Далее меняем t2 и t1 .
Таблица 3
bt7t2t3L6000 60 -40 30 4000 40 80 120t4300 -1 2 -1 300/2=150 -200 -2 -4 -6t5100 -1,5 -0,5 -2,5 50 0,5 1 -4,5t650 -2,5 -0,5 -6,5 50 0,5 1-7,5t150 0,5 0,51,5 50/0,5=100 100 1 2 1,5
Таблица 3
bt7t1t3L10000 100 80 150 t4100 -3 -4 -7 t5150 -1 1 -1 t6100 -2 1 -5 t2100 1 2 3
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Таким образом, t1 = t3 =0; t2=100; L=10000.
Т.е. для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.
ОТВЕТ: для получения максимальной прибыли следует производить только бен?/p>