Курсовая работа: Решение задач линейной оптимизации симплекс – методом
Курсовая работа: Решение задач линейной оптимизации симплекс – методом
Курсовая работа по дисциплине «Численные методы оптимизации»
Выполнил: ст.гр.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 тыс.л.
Сводная таблица условий задачи:
| Компоненты, используемые для производства трёх видов бензина. | Сорта производимого бензина |
Объем ресурсов (тыс. л) |
||
| А | В | С | ||
| Алкилат |
|
|
|
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)-й
строки таблицы определяются следующими соотношениями:
,
.
Отсюда получим:
;
;
;
…
.
Весь процесс решения задачи приведен в табл. 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.
