скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

скачать рефератыРеферат: Решение задач линейной оптимизации симплекс – методом

Реферат: Решение задач линейной оптимизации симплекс – методом

Министерство образования РФ и РТ.

Казанский Государственный Университет им. А.Н. Туполева.

_______________________________________________


Курсовая работа по дисциплине

«Численные методы оптимизации»


Решение задач линейной оптимизации симплекс – методом.

Выполнил: ст.гр.4408  Калинкин А.А.

                                                                                     

Проверил: Мурга О.К.

г. Казань 2001г.

Содержание

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

1.1. Физическая  постановка задачи

1.2. Математическая постановка задачи

2. Приведение задачи к канонической форме

3. Нахождение начального опорного плана с помощью L-задачи

3.1. Постановка L-задачи

3.2. Решение L-задачи

3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи

4. Решение исходной задачи I алгоритмом симплекс-метода

5. Формирование М-задачи

6. Решение М-задачи вторым алгоритмом симплекс-метода

7. Формирование двойственной задачи

8. Формирование оптимального решения двойственной задачи на основе теоремы о двойственности

9. Анализ результатов и выводы


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 тыс.л.

Сводная таблица условий задачи:

Компоненты, используемые для производства трёх видов бензина. Сорта производимого бензина

Объем ресурсов

(тыс. л)

А В С

Алкилат

400

Крекинг-бензин

250
Бензин прямой перегонки

300
Изопентат

250
Цена бензина (рублей за 1 тыс.л.) 120 100 150

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)-й строки таблицы определяются следующими соотношениями:

,

.

Отсюда получим:

;

;

;

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


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

© 2010.