Курсовая работа по дисциплине «Численные методы оптимизации»
Выполнил: ст.гр.4408 Калинкин А.А.
Казанский Государственный Университет им. А.Н. Туполева.
г. Казань 2001г.
Нефтеперерабатывающий завод получает четыре полуфабриката:
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)
при ограничениях
(1.2.2)
, где
В этих выражениях:
- объемы бензина А-го,
В-го и С-го сорта соответственно.
Тогда
объёмная
доля первой компоненты (алкилата) в бензине А.
объёмная
доля первой компоненты (алкилата) в бензине В.
объёмная
доля первой компоненты (алкилата) в бензине С.
и т.д.
Целевая функция выражает стоимость
всей продукции в зависимости от объема производимого бензина каждого сорта.
Таким образом, для получения максимальной стоимости продукции необходимо
максимизировать целевую функцию
(1.2.1) с соблюдением
всех условий задачи, которые накладывают ограничения (1.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
C |
|
… |
|
… |
|
… |
|
||||
N |
|
|
B |
|
… |
|
… |
|
… |
|
t |
1 |
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
l |
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
… |
|
… |
|
… |
|
|
m+1 | – | – |
|
|
… |
|
… |
|
… |
|
– |
Заполнение таблицы, соответствующей исходному опорному
плану (0-й итерации). Пусть некоторый опорный план
задачи (2.1) - (2.3) с базисом
. Тогда
– базисные компоненты,
а
– небазисные
компоненты.
Вычисляем коэффициенты разложения векторов Аj по базису Б0
(в случае, если Б0
является единичной матрицей,
)
и находим оценки . Далее определяем значение линейной формы
Полученные результаты записываем в таблицу 4.1.
В первом столбце N таблицы указываются номера строк.
Номера первых m строк совпадают с номерами
позиций базиса. Во втором столбце Сх
записываются коэффициенты линейной формы при базисных переменных. Столбец Бх содержит векторы базиса
. В столбце В записываются базисные переменные
опорного плана.
Столбцы
содержат коэффициенты
разложения соответствующих векторов условий
по векторам базиса.
Все вышесказанное относится только к первым m строкам таблицы. Последняя (m+1)-я строка таблицы заполняется последовательно
значением линейной формы F и оценками
. Позиции таблицы, которые не должны заполняться,
прочеркиваются.
В результате заполнена таблица 0-й итерации кроме столбца t.
Столбцы В, А1,…, An (все m+1 позиций) будем называть главной частью таблицы.
Порядок вычислений в отдельной итерации. Пусть ν-я итерация закончена. В результате заполнена таблица ν за исключением последнего столбца t.
Каждая итерация состоит из двух этапов.
I этап: проверка исследуемого опорного плана на оптимальность.
Просматривается (m+1)-я строка таблицы ν. Если все , то опорный план, полученный после ν-й итерации, является оптимальным (случай 1), завершаем
решение задачи. Пусть теперь имеются отрицательные оценки. Проверяем знаки
элементов
столбцов
с
. Наличие по крайней мере одного столбца
, для которого
и все
, свидетельствует о неразрешимости задачи (случай 2).
Установив это, прекращаем вычисления.
Если в каждом столбце , для которого
, содержится хотя бы один положительный коэффициент
, то опорный план является неоптимальным (случай 3).
Переходим ко II этапу.
II этап: построение нового опорного плана с большим значением линейной формы.
Определяется вектор Ak, который должен быть введен в базис, из следующего условия
.
После этого заполняется последний столбец таблицы
ν – столбец t. В него записываются отношения
базисных переменных (элементы столбца В) к
соответствующим составляющим
(элементы столбца Ak). Т.о. заполняются только те
позиции, для которых
. Если
, то в позиции i
столбца t записывается
. Вектор базиса
, на котором достигается t0,
,
подлежит исключению из базиса (если t0 достигается на нескольких векторах, то из базиса исключается любой из них).
Столбец Ak
, отвечающий вектору, вводимому в базис, и l-я строка, соответствующая
вектору , исключаемому из базиса, называется соответственно
разрешающим столбцом и разрешающей строкой. Элемент
, расположенный на пересечении разрешающего столбца и
разрешающей строки, называется разрешающим элементом.
После выделения разрешающего элемента заполняется
(ν+1)-я таблица. В l-е позиции
столбцов Бх, Сх
вносятся соответственно Ак, Ск,
которые в (ν+1)-й таблице
обозначаются как ,
. В остальные позиции столбцов Бх, Сх вносятся те же параметры, что и в
таблице ν.
Далее заполняется главная часть (ν+1)-й таблицы. Прежде всего происходит заполнение ее l-й строки в соответствии с рекуррентной формулой
.
Рекуррентная формула для заполнения i-й строки (ν+1)-й таблицы имеет вид
.
Здесь
.
Заполнение главной части (ν+1)-й таблицы завершает (ν+1)-ю итерацию. Последующие итерации проводятся аналогично. Вычисления продолжаются до тех пор, пока не будет получен оптимальный план либо будет установлено, что исследуемая задача неразрешима.
Весь процесс решения исходной задачи (2.12) - (2.13) приведен в табл. 4.2.
Заполнение таблицы, отвечающей 0-й итерации,
происходит на основе табл. 3.2.1 (см. итерацию 1) следующим образом. Главная
часть таблицы 0-й итерации исходной задачи (за исключением (m+1)-й строки) полностью повторяет главную часть
таблицы заключительной итерации L-задачи без
столбца А9. Также без изменений остается столбец базисных векторов Бх.
Строка С коэффициентов линейной формы исходной задачи и столбец Сх
коэффициентов при базисных переменных заполняются исходя из (2.12). С учетом
новых коэффициентов С пересчитываются значение линейной формы F и оценки .
Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным выше первым алгоритмом.
Таблица 4.2
Решение исходной задачи (2.12) - (2.13) получено за 3
итерации. Оптимальный план ее равен и
.
Найденное решение задачи в канонической
форме (2.12) - (2.13) соответствует решению
(4.1) общей задачи
линейного программирования (2.9) - (2.11), записанной для новых переменных
. Для общей задачи из (2.9) следует, что
(4.2).
Вернемся к задаче (1.2.1), (1.2.2) со старыми
переменными . Учитывая (4.1) и (4.2) из (2.7) и (2.8) получим
(4.3)
и
.
(4.4)
Таким образом, для получения максимальной цены (142750 руб.) всей продукции необходимо произвести:
450 тыс.л. бензина А из полуфабрикатов в следующих количествах:
Алкитата тыс.л.
Крекинг-бензина тыс.л.
Бензина прямой перегонки тыс.л.
Изопентона тыс.л.
тыс.л. бензина В из
полуфабрикатов в следующих количествах:
Алкитата тыс.л.
Крекинг-бензина тыс.л.
Бензина прямой перегонки тыс.л.
Изопентона тыс.л.
300 тыс.л. бензина В из полуфабрикатов в следующих количествах:
Алкитата тыс.л.
Крекинг-бензина тыс.л.
Бензина прямой перегонки тыс.л.
Изопентона тыс.л.
Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.
Рассмотрим наряду с исходной задачей (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)
, где
.
где М – сколь угодно большая положительная величина.
Как и в L-задаче,
добавление только одной искусственной переменной (вместо пяти)
обусловлено тем, что исходная задача уже содержит четыре единичных вектора
условий А4, А5, А6, А7.
6. Решение М-задачи II алгоритмом симплекс-метода
Описание II алгоритма
Второй алгоритм (или метод обратной матрицы) симплекс
метода основан на ином способе вычисления оценок векторов условий Аj, чем в первом алгоритме.
Рассматривается задача линейного программирования в
канонической форме (2.1) - (2.3). Пусть Х – опорный план с базисом . Все параметры, необходимые
для оценки плана на оптимальность и перехода к лучшему плану, можно получить,
преобразовывая от шага к шагу элементы матрицы
.
Действительно, зная обратную матрицу , можно получить базисные составляющие опорного плана:
и вычислить оценки векторов условий относительно текущего базиса
, (6.1)
предварительно определив вектор-строку по формуле
или
. (6.2)
Здесь - вектор-строка из коэффициентов линейной формы, отвечающих
базисным переменным.
Оценки позволяют установить
оптимальность рассматриваемого опорного плана и определить вектор Ак,
вводимый в базис. Коэффициенты
разложения вектора Ак
по текущему базису вычисляются по формуле
.
Как и в I алгоритме, вектор, подлежащий исключению из базиса, определяется величиной
.
Таким образом при втором алгоритме на каждом шаге
запоминаются базисные компоненты , обратная матрица
, значение линейной формы F(X) и вектор Y, соответствующие текущему опорному плану Х. Элементы
столбцов матрицы
удобно рассматривать
как коэффициенты
разложения единичных
векторов
по векторам базиса.
Рекуррентные формулы, связывающие параметры двух последовательных итераций
; (6.3)
. (6.3)
Здесь
.
Результаты вычислений сводятся в основные таблицы (вида табл. 6.1) и вспомогательную таблицу (вида табл. 6.2); столбцы В, е1, …, еm основных таблиц (все m+1 позиций) называют главной частью этих таблиц. Столбец Аk – разрешающий столбец, строка l – разрешающая строка.
Таблица 6.1 Таблица 6.2
N |
|
|
B |
|
… |
|
|
t | N | B |
|
|
… |
|
|
1 |
|
|
|
|
… |
|
|
1 |
|
|
|
… |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
l |
|
|
|
|
… |
|
|
|
m |
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
m+1 | C |
|
|
… |
|
|
M |
|
|
|
|
… |
|
|
0 |
|
|
|
… |
|
||
m+1 | – | – |
|
|
… |
|
|
– | 1 |
|
|
|
… |
|
|
2 |
|
|
|
… |
|
||||||||||
… | … | … | … | … | … |
Краткое описание алгоритма.
1. Нулевая итерация:
а) составляется вспомогательная табл. 6.2, в которую вносятся параметры задачи; дополнительная строка таблицы с номером ν заполняется по мере выполнения ν-й итерации;
б) составляется основная табл. 6.1 с номером 0, в
которой заполняются первые m строк, за исключением последних двух столбцов Аk и t. Элементы и
определяются
скалярными произведениями (Cx, ej)
и (Cx, B) соответственно. Нулевая итерация заканчивается
заполнением нулевой дополнительной строки вспомогательной таблицы с оценками
.
2. (ν+1)-я итерация.
Пусть ν-я итерация закончена. В результате
заполнена ν-я основная таблица, за исключением двух последних столбцов, и ν-я
дополнительная строка вспомогательной таблицы. Просматривается эта строка. Если
все , то опорный план
- решение задачи. Если хотя бы одна
, то в базис вводится вектор Аk с
(обычно
). После этого заполняется столбец
основной таблицы. В
позицию (m+1) этого столбца заносится
оценка
вектора Аk.
Остальные элементы этого столбца равны
.
Возможны два случая:
все - задача неразрешима;
хотя бы для одного i. В этом случае, также как и в первом алгоритме,
заполняется столбец (t) основной
таблицы ν, определяется разрешающий элемент
. Главная часть заполняется по рекуррентной формуле (6.3).
Заполняется (ν+1)-я дополнительная строка вспомогательной таблицы. На этом
заканчивается (ν+1)-я итерация.
Таблица 6.3
Таблица 6.4
Задача (5.4), (5.5) имеет опорный план Х0 =
(0, 0, 0, ,
,
,
, 0 ,
) с базисом
. Следовательно,
. Процесс решения М-задачи вторым алгоритмом приведен в
основной табл. 6.3 и вспомогательной табл. 6.4.
Решение М-задачи получено за 5 шагов. Оптимальный план
ее равен и
. В оптимальном плане М-задачи искусственная переменная х9
= 0, поэтому
- решение задачи
(2.12), (2.13) и
.
Окончательное решение задачи определения плана смешения компонентов полностью повторяет решение, рассмотренное в завершающей части п.4 (см. стр.11-12).
Произвольной задаче линейного программирования определенным образом соответствует некоторая другая задача линейного программирования. Будем называть ее двойственной, а первоначальную задачу – исходной.
Обозначим
;
;
;
;
(7.1)
Теперь исходная задача (2.1) - (2.3) в канонической форме может быть записана в матричном виде следующим образом.
Требуется определить вектор , обращающий в максимум
. (7.2)
при условиях
AX=B; (7.3)
. (7.4)
Тогда двойственная задача – определить вектор , обращающий в минимум
f(Y)=YB (7.5)
при условиях
. (7.6)
Транспонируя обе части неравенства (7.6), записанного
в виде строки, и учитывая , получим
. (7.7)
Отметим, что в двойственной задаче переменные yi могут быть и отрицательными.
Рассмотрим в качестве исходной задачу (2.12), (2.13). С учетом (7.1) и (7.7) запишем
С = (120, 100, 150, 0, 0, 0, 0, 0), B = (,
,
,
,
),
.
Двойственная задача имеет вид
; (7.8)
(7.9)
Оказывается, что для задач (7.2) - (7.4) и (7.5), (7.6), называемых двойственной парой, справедлива следующая теорема.
Теорема (первая теорема о двойственности). Если одна
из задач двойственной пары (7.2) - (7.4) и (7.5), (7.6) имеет решение, то
другая задача также разрешима. При этом для любых оптимальных планов и
(здесь Мх, Му
– множества планов соответственно прямой и двойственной задач) задач (7.2) - (7.4)
и (7.5), (7.6) имеет место равенство
.
Если линейная форма одной из задач не ограничена (для F(X) – сверху, для f(Y) - снизу), то другая задача не имеет ни одного плана.
Оптимальное решение двойственной задачи может быть найдено на основе следующего следствия из этой теоремы.
Следствие. Если вектор является оптимальным
опорным планом задачи (7.2) - (7.4), то вектор
(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) найден верно.
В данной работе рассматриваются два способа решения исходной задачи линейного программирования.
Первый заключается в том, что сначала решается вспомогательная задача (L-задача), позволяющая построить начальный опорный план, затем на основе этого найденного плана решается исходная задача (определяется ее оптимальный план). Второй способ является объединением двух этапов и состоит в решении расширенной задачи (M-задачи), также приводящей к нахождению оптимального плана исходной задачи.
Вычислительную основу этих двух способов решения составляют соответственно первый и второй алгоритмы симплекс-метода. Один из параметров, по которому может быть оценен любой итерационный алгоритм – количество шагов, приводящих к решению задачи или установлению ее неразрешимости. Для данной задачи наиболее эффективным методом оказался первый метод(L-задача + исходная задача), т.к. он привел к решению за 4 шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов, вероятно, обусловлена неоднозначность выбора разрешающего элемента в исходной таблице L-задачи (3.2.1).
Сравнение количества вычислений на каждой итерации приводит к следующим оценочным результатам рассматриваемых алгоритмов. Преимущественная часть вычислений на каждом шаге алгоритмов определяется размерностью главной части таблицы (в первом алгоритме) или основной таблицы (во втором алгоритме). В первом случае она имеет размерность (m+1)x(n+1), во втором - (m+1)x(m+1). Даже учитывая, что второй алгоритм требует построения вспомогательной таблицы, он оказывается более компактным.
Еще одно несомненное достоинство второго алгоритма заключается в возможности определения оптимального плана двойственной задачи из (m+1)-й строки основной таблицы, соответствующей последней итерации, без всяких дополнительных вычислений.