.

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

Язык: русский
Формат: реферат
Тип документа: Word Doc
76 793
Скачать документ

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

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

_______________________________________________

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

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

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

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

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

г. Казань 2001г.

Содержание

TOC \o “1-3” 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 тыс.л.

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

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

250

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

1.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.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.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.

) получим, что процесс решения через конечное число шагов приведет к
оптимальному опорному плану вспомогательной задачи.

является также опорным.

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

Вспомогательная задача для нахождения начального опорного плана задачи
(2.12) – (2.13) в канонической форме состоит в следующем.

Требуется обратить в максимум

при условиях

.

рассматривая в качестве исходного опорного плана план

(вместо пяти) обусловлено тем, что исходная задача уже содержит четыре
единичных вектора условий А4, А5, А6, А7.

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

Решение L-задачи будем проводить в соответствии с первым алгоритмом
симплекс-метода (описание алгоритма приводится в п.4). Составим таблицу,
соответствующую исходному опорному плану (0-й итерации).

, является единичной матрицей, то коэффициенты разложения векторов Аj
по базису Б0

.

для заполнения (m+1)-й строки таблицы определяются следующими
соотношениями:

,

.

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

;

;

;

.

Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из 2
частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.

Заполняем таблицу 0-й итерации.

достигается на пятой позиции базиса. Значит, пятая строка является
разрешающей строкой, и вектор А9 подлежит исключению из базиса.

Составим таблицу, отвечающую первой итерации.

.

Таблица 3.2.1 

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

является начальным опорным планом исходной задачи (2.12) – (2.13).

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

Описание I алгоритма

Симплекс-метод позволяет, отправляясь от некоторого исходного опорного
плана и постепенно улучшая его, получить через конечное число итераций
оптимальный план или убедиться в неразрешимости задачи. Каждой итерации
соответствует переход от одной таблицы алгоритма к следующей. Таблица,
отвечающая опорному плану в ?-й итерации имеет вид табл. 4.1.

Таблица 4.1            

… E???????????

– небазисные компоненты.

Вычисляем коэффициенты разложения векторов Аj по базису Б0

)

. Далее определяем значение линейной формы

Полученные результаты записываем в таблицу 4.1.

. Позиции таблицы, которые не должны заполняться, прочеркиваются.

В результате заполнена таблица 0-й итерации кроме столбца t.

Столбцы В, А1,…, An (все m+1 позиций) будем называть главной частью
таблицы.

Порядок вычислений в отдельной итерации. Пусть ?-я итерация закончена. В
результате заполнена таблица ? за исключением последнего столбца t.

Каждая итерация состоит из двух этапов.

I этап: проверка исследуемого опорного плана на оптимальность.

, свидетельствует о неразрешимости задачи (случай 2). Установив это,
прекращаем вычисления.

, то опорный план является неоптимальным (случай 3). Переходим ко II
этапу.

II этап: построение нового опорного плана с большим значением линейной
формы.

Определяется вектор Ak, который должен быть введен в базис, из
следующего условия

.

, на котором достигается t0,

,

подлежит исключению из базиса (если t0 достигается на нескольких
векторах, то из базиса исключается любой из них).

, расположенный на пересечении разрешающего столбца и разрешающей
строки, называется разрешающим элементом.

. В остальные позиции столбцов Бх, Сх вносятся те же параметры, что и в
таблице ?.

Далее заполняется главная часть (?+1)-й таблицы. Прежде всего происходит
заполнение ее l-й строки в соответствии с рекуррентной формулой

.

Рекуррентная формула для заполнения i-й строки (?+1)-й таблицы имеет вид

.

Здесь

.

Заполнение главной части (?+1)-й таблицы завершает (?+1)-ю итерацию.
Последующие итерации проводятся аналогично. Вычисления продолжаются до
тех пор, пока не будет получен оптимальный план либо будет установлено,
что исследуемая задача неразрешима.

Решение исходной задачи

Весь процесс решения исходной задачи (2.12) – (2.13) приведен в
табл. 4.2.

.

Заполнение таблиц, отвечающих последующим итерациям, происходит в
соответствии с описанным выше первым алгоритмом.

Таблица 4.2 

.

(4.2).

. Учитывая (4.1) и (4.2) из (2.7) и (2.8) получим

(4.3)

и

. (4.4)

Таким образом, для получения максимальной цены (142750 руб.) всей
продукции необходимо произвести:

450 тыс.л. бензина А из полуфабрикатов в следующих количествах:

тыс.л.

тыс.л.

тыс.л.

тыс.л.

тыс.л. бензина В из полуфабрикатов в следующих количествах:

тыс.л.

тыс.л.

тыс.л.

тыс.л.

300 тыс.л. бензина В из полуфабрикатов в следующих количествах:

тыс.л.

тыс.л.

тыс.л.

тыс.л.

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

Далеко не всегда имеет смысл разделять решение задачи линейного
программирования на два этапа – вычисление начального опорного плана и
определение оптимального плана. Вместо этого решается расширенная задача
(М-задача). Она имеет другие опорные планы (один из них всегда легко
указать), но те же решения (оптимальные планы), что и исходная задача.

Рассмотрим наряду с исходной задачей (2.1) – (2.3) в канонической форме
следующую расширенную задачу (М-задачу):

(5.1)

(5.2)

. (5.3)

Здесь М>0 – достаточно большое число.

Начальный опорный план задачи (5.1) – (5.3) имеет вид

называются искусственными переменными.

Таким образом, исходная задача линейного программирования с неизвестным
заранее начальным опорным планом сводится к М-задаче, начальный опорный
план которой известен. В процессе решения этой расширенной задачи можно
либо вычислить оптимальный план задачи (2.1) – (2.3), либо убедиться в
ее неразрешимости, если оказывается неразрешимой М-задача.

В соответствии с вышеизложенным имеем: требуется решить задачу
(2.12), (2.13), записанную в канонической форме. Введем искусственную
неотрицательную переменную х9 и рассмотрим расширенную М-задачу

(5.4)

при условиях

(5.5)

.

где М – сколь угодно большая положительная величина.

(вместо пяти) обусловлено тем, что исходная задача уже содержит четыре
единичных вектора условий А4, А5, А6, А7.

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

Описание II алгоритма

векторов условий Аj, чем в первом алгоритме.

.

, можно получить базисные составляющие опорного плана:

и вычислить оценки векторов условий относительно текущего базиса

, (6.1)

по формуле

или

. (6.2)

– вектор-строка из коэффициентов линейной формы, отвечающих базисным
переменным.

разложения вектора Ак по текущему базису вычисляются по формуле

.

Как и в I алгоритме, вектор, подлежащий исключению из базиса,
определяется величиной

.

по векторам базиса. Рекуррентные формулы, связывающие параметры двух
последовательных итераций

; (6.3)

. (6.3)

Здесь

.

Результаты вычислений сводятся в основные таблицы (вида табл. 6.1) и
вспомогательную таблицу (вида табл. 6.2); столбцы В, е1, …, еm основных
таблиц (все m+1 позиций) называют главной частью этих таблиц. Столбец Аk
– разрешающий столбец, строка l – разрешающая строка.

Таблица 6.1 Таблица 6.2

… … … … … …

Краткое описание алгоритма.

1. Нулевая итерация:

а) составляется вспомогательная табл. 6.2, в которую вносятся параметры
задачи; дополнительная строка таблицы с номером ? заполняется по мере
выполнения ?-й итерации;

.

2. (?+1)-я итерация.

вектора Аk. Остальные элементы этого столбца равны

.

Возможны два случая:

– задача неразрешима;

. Главная часть заполняется по рекуррентной формуле (6.3). Заполняется
(?+1)-я дополнительная строка вспомогательной таблицы. На этом
заканчивается (?+1)-я итерация.

Решение М-задачи

Таблица 6.3

Таблица 6.4

. Процесс решения М-задачи вторым алгоритмом приведен в основной
табл. 6.3 и вспомогательной табл. 6.4.

.

Окончательное решение задачи определения плана смешения компонентов
полностью повторяет решение, рассмотренное в завершающей части п.4 (см.
стр.11-12).

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

Произвольной задаче линейного программирования определенным образом
соответствует некоторая другая задача линейного программирования. Будем
называть ее двойственной, а первоначальную задачу – исходной.

Обозначим

(7.1)

Теперь исходная задача (2.1) – (2.3) в канонической форме может быть
записана в матричном виде следующим образом.

, обращающий в максимум

. (7.2)

при условиях

AX=B; (7.3)

. (7.4)

, обращающий в минимум

f(Y)=YB (7.5)

при условиях

. (7.6)

, получим

. (7.7)

Отметим, что в двойственной задаче переменные yi могут быть и
отрицательными.

Рассмотрим в качестве исходной задачу (2.12), (2.13). С учетом (7.1) и
(7.7) запишем

),

EMBED Equation.3

.

Двойственная задача имеет вид

; (7.8)

(7.9)

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

Оказывается, что для задач (7.2) – (7.4) и (7.5), (7.6), называемых
двойственной парой, справедлива следующая теорема.

(здесь Мх, Му – множества планов соответственно прямой и двойственной
задач) задач (7.2) – (7.4) и (7.5), (7.6) имеет место равенство

.

Если линейная форма одной из задач не ограничена (для F(X) – сверху,
для f(Y) – снизу), то другая задача не имеет ни одного плана.

Оптимальное решение двойственной задачи может быть найдено на основе
следующего следствия из этой теоремы.

 (8.1), является оптимальным опорным планом задачи (7.5), (7.6).

. И если Х – оптимальный опорный план задачи (7.2) – (7.4), то в
(m+1)-й строке, соответствующей основной таблице, находится решение
задачи (7.5), (7.6).

Пусть двойственная задача имеет вид (7.8), (7.9).

Так как исходная задача (2.12), (2.13) имеет решение, то на основании
рассмотренной теоремы о двойственности двойственная задача также
разрешима.

(см. п.4, п.6). При этом

.

Вычислим

.

. Анализируя (m+1)-ю строку основной таблицы (см. табл. 6.3, шаг 5),
можно убедиться в том, что оптимальный план двойственной задачи,
сформированный на основе теоремы о двойственности, совпадает с
оптимальным планом, найденном при решении исходной задачи вторым
алгоритмом симплекс-метода. Это говорит о том, что оптимальный план
задачи (7.8) – (7.9) найден верно.

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

В данной работе рассматриваются два способа решения исходной задачи
линейного программирования.

Первый заключается в том, что сначала решается вспомогательная задача
(L-задача), позволяющая построить начальный опорный план, затем на
основе этого найденного плана решается исходная задача (определяется ее
оптимальный план). Второй способ является объединением двух этапов и
состоит в решении расширенной задачи (M-задачи), также приводящей к
нахождению оптимального плана исходной задачи.

Вычислительную основу этих двух способов решения составляют
соответственно первый и второй алгоритмы симплекс-метода. Один из
параметров, по которому может быть оценен любой итерационный алгоритм –
количество шагов, приводящих к решению задачи или установлению ее
неразрешимости. Для данной задачи наиболее эффективным методом оказался
первый метод(L-задача + исходная задача), т.к. он привел к решению за 4
шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов,
вероятно, обусловлена неоднозначность выбора разрешающего элемента в
исходной таблице L-задачи (3.2.1).

Сравнение количества вычислений на каждой итерации приводит к
следующим оценочным результатам рассматриваемых алгоритмов.
Преимущественная часть вычислений на каждом шаге алгоритмов определяется
размерностью главной части таблицы (в первом алгоритме) или основной
таблицы (во втором алгоритме). В первом случае она имеет размерность
(m+1)x(n+1), во втором – (m+1)x(m+1). Даже учитывая, что второй алгоритм
требует построения вспомогательной таблицы, он оказывается более
компактным.

Еще одно несомненное достоинство второго алгоритма заключается в
возможности определения оптимального плана двойственной задачи из
(m+1)-й строки основной таблицы, соответствующей последней итерации, без
всяких дополнительных вычислений.

PAGE 1

PAGE 2

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020