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

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

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

_______________________________________________

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

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

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

Выполнил: ст.гр.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)