Курсова робота з дисципліни В«Чисельні методи оптимізації В»
Виконав: ст.гр.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
Крекінг-бензин
<p>
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-й ітерації.
Серед оцінок є негативні. Значить, вихідний опорний план не є оптимальним. Перей...
