Міністерство освіти РФ і РТ.
Казанський Державний Університет ім. А.Н. Туполєва.
_______________________________________________
Курсова робота з дисципліни
В«Чисельні методи оптимізаціїВ»
Рішення задач лінійної оптимізації симплекс - методом.
Виконав: ст.гр.4408 Калінкін А.А.
Перевірив: Мурга О.К.
р. Казань 2001р.
Зміст
1. Постановка завдання
1.1. Фізична постановка задачі
1.2. Математична постановка задачі
2. Приведення завдання до канонічної форми
3. Знаходження початкового опорного плану з допомогою L-задачи
3.1. Постановка L-задачи
3.2. Рішення L-задачи
3.3. Формування початкового опорного плану вихідної задачі лінійного програмування з оптимального плану L-задачи
4. Рішення вихідної задачі I алгоритмом симплекс-методу
5. Формування М-задачі
6. Рішення М-задачі другий алгоритм симплекс-методу </p>
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)
Початковий опорний план задачі (3.1) - (3.3) відомий. Він складається з компонент
і має одиничний базис Б == E .
Вирішуючи допоміжну завдання першого алгоритму симплекс-методу (опис алгоритму наводиться в п.4), в силу обмеженості лінійної форми зверху на безлічі своїх планів () отримаємо, що процес вирішення через кінцеве число кроків приведе до оптимального опорному плану допоміжної задачі.
Нехай - оптимальний опорний план допоміжної задачі. Тоді є опорним планом вихідної задачі. Дійсно, всі додаткові змінні. Значить, задовольняє умовам вихідної задачі, тобто є деяким планом завдання (2.12) - (2.13). За побудовою план є також опорним.
3.1. Постановка L -завдання
Допоміжна за...
