|
Реферат: Решение задач линейной оптимизации симплекс – методомРеферат: Решение задач линейной оптимизации симплекс – методомМинистерство образования РФ и РТ. Казанский Государственный Университет им. А.Н. Туполева. _______________________________________________ Курсовая работа по дисциплине «Численные методы оптимизации» Решение задач линейной оптимизации симплекс – методом. Выполнил: ст.гр.4408 Калинкин А.А.
Проверил: Мурга О.К. г. Казань 2001г. Содержание
1. Постановка задачи 1.1. Физическая (техническая) постановка задачи Нефтеперерабатывающий завод получает четыре полуфабриката: - 400 тыс. л. алкилата; - 250 тыс. л. крекинг-бензина; - 350 тыс. л. бензина прямой перегонки; - 250 тыс. л. изопентона; В результате смешивания этих четырёх компонентов в разных пропорциях образуются три сорта авиационного бензина: - Бензин А – 2 : 3 : 5 : 2 ; - Бензин В – 3 : 1 : 2 : 1 ; - Бензин С – 2 : 2 : 1 : 3 ; Стоимость 1 тыс.л. указанных сортов бензина: - Бензин А – 120 руб. - Бензин Б – 100 руб. - Бензин С – 150 руб. Необходимо определить план смешения компонентов, при котором будет достигнута максимальная стоимость все продукции. При следующих условиях: - Бензина каждого сорта должно быть произведено не менее 300 тыс..л. - Неиспользованного крекинг бензина должно остаться не более 50 тыс.л. Сводная таблица условий задачи:
1.2. Математическая постановка задачи Исходя из условий задачи, необходимо максимизировать следующую целевую функцию: (1.2.1)при ограничениях(1.2.2), гдеВ этих выражениях:- объемы бензина А-го, В-го и С-го сорта соответственно. Тогда объёмная доля первой компоненты (алкилата) в бензине А. объёмная доля первой компоненты (алкилата) в бензине В. объёмная доля первой компоненты (алкилата) в бензине С. и т.д. Целевая функция выражает стоимость всей продукции в зависимости от объема производимого бензина каждого сорта. Таким образом, для получения максимальной стоимости продукции необходимо максимизировать целевую функцию (1.2.1) с соблюдением всех условий задачи, которые накладывают ограничения (1.2.2) на . 2. Приведение задачи к канонической форме Задача линейного программирования записана в канонической форме, если она формулируется следующим образом. Требуется найти вектор , доставляющий максимум линейной форме (2.1) при условиях (2.2) (2.3) где Перепишем исходную задачу (1.2.1) - (1.2.2): (2.4)при ограничениях(2.5), где (2.6) В канонической форме задачи линейного программирования необходимо, чтобы все компоненты искомого вектора Х были неотрицательными, а все остальные ограничения записывались в виде уравнений. Т.е. в задаче обязательно будут присутствовать условия вида (2.3) и 8 уравнений вида (2.2), обусловленных неравенствами (2.5), (2.6). Число ограничений задачи, приводящих к уравнениям (2.2) можно уменьшить, если перед приведением исходной задачи (2.4) - (2.6) к канонической форме мы преобразуем неравенства (2.6) к виду (2.3). Для этого перенесем свободные члены правых частей неравенств (2.6) в левые части. Таким образом, от старых переменных перейдем к новым переменным, где : , . Выразим теперь старые переменные через новые , (2.7) и подставим их в линейную форму (2.4) и в неравенства (2.5), (2.6). Получим , где . Раскрывая скобки и учитывая, что (2.8), можем окончательно записать: (2.9) (2.10), где (2.11) Путем несложных преобразований задачу (1.2.1), (1.2.2) свели к задаче (2.9) - (2.11) с меньшим числом ограничений. Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные , и задача (2.9) - (2.11) запишется в следующей эквивалентной форме: (2.12) (2.13) , где Задача (2.12), (2.13) имеет каноническую форму. 3. Нахождение начального опорного плана с помощью L-задачи Начальный опорный план задачи (2.1) - (2.3), записанной в канонической форме, достаточно легко может быть найден с помощью вспомогательной задачи (L-задачи): (3.1) (3.2) (3.3) Начальный опорный план задачи (3.1) - (3.3) известен. Он состоит из компонент
и имеет единичный базис Б = = E. Решая вспомогательную задачу первым алгоритмом симплекс-метода (описание алгоритма приводится в п.4), в силу ограниченности линейной формы сверху на множестве своих планов () получим, что процесс решения через конечное число шагов приведет к оптимальному опорному плану вспомогательной задачи. Пусть - оптимальный опорный план вспомогательной задачи. Тогда является опорным планом исходной задачи. Действительно, все дополнительные переменные . Значит, удовлетворяет условиям исходной задачи, т.е. является некоторым планом задачи (2.12) - (2.13). По построению план является также опорным. 3.1. Постановка L-задачи Вспомогательная задача для нахождения начального опорного плана задачи (2.12) - (2.13) в канонической форме состоит в следующем. Требуется обратить в максимум при условиях , где .
рассматривая в качестве исходного опорного плана план Здесь добавление только одной дополнительной переменной (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7. 3.2. Решение L-задачи Решение L-задачи будем проводить в соответствии с первым алгоритмом симплекс-метода (описание алгоритма приводится в п.4). Составим таблицу, соответствующую исходному опорному плану (0-й итерации). Т.к. Б0 = - базис, соответствующий известному опорному плану, является единичной матрицей, то коэффициенты разложения векторов Аj по базису Б0 . Значение линейной формы и оценки для заполнения (m+1)-й строки таблицы определяются следующими соотношениями: , . Отсюда получим: ; ; ; … . Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из 2 частей, отвечающих 0-й (исходная таблица) и 1-й итерациям. Заполняем таблицу 0-й итерации. Среди оценок имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису. В базис будет введен вектор А1 с наименьшей оценкой . Значения t вычисляются для всех позиций столбца t (т.к. все элементы разрешающего столбца положительны). Наименьший элемент достигается на пятой позиции базиса. Значит, пятая строка является разрешающей строкой, и вектор А9 подлежит исключению из базиса. Составим таблицу, отвечающую первой итерации. В столбце Бх, в пятой позиции базиса место вектора А9 занимает вектор А1. Соответствующий ему коэффициент линейной формы С41 = 0 помещаем в столбец Сх. Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как все , то опорный план является решением L-задачи. Наибольшее значение линейной формы равно . Таблица 3.2.1 3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи Поскольку , где - оптимальный опорный план L-задачи, то является начальным опорным планом исходной задачи (2.12) - (2.13). 4. Решение исходной задачи I алгоритмом симплекс-метода Описание I алгоритма Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ν-й итерации имеет вид табл. 4.1. Таблица 4.1
Страницы: 1, 2 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Рефераты бесплатно, реферат бесплатно, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения, курсовые, дипломы, научные работы и многое другое. |
||
При использовании материалов - ссылка на сайт обязательна. |