Рішення задач лінійної оптимізації симплекс - методом » Українські реферати
Теми рефератів
Авіація та космонавтика Банківська справа Безпека життєдіяльності Біографії Біологія Біологія і хімія Біржова справа Ботаніка та сільське гос-во Бухгалтерський облік і аудит Військова кафедра Географія
Геодезія Геологія Держава та право Журналістика Видавнича справа та поліграфія Іноземна мова Інформатика Інформатика, програмування Історія Історія техніки Комунікації і зв'язок Краєзнавство та етнографія Короткий зміст творів Кулінарія Культура та мистецтво Культурологія Зарубіжна література Російська мова Маркетинг Математика Медицина, здоров'я Медичні науки Міжнародні відносини Менеджмент Москвоведение Музика Податки, оподаткування Наука і техніка Решта реферати Педагогіка Політологія Право Право, юриспруденція Промисловість, виробництво Психологія Педагогіка Радіоелектроніка Реклама Релігія і міфологія Сексологія Соціологія Будівництво Митна система Технологія Транспорт Фізика Фізкультура і спорт Філософія Фінансові науки Хімія Екологія Економіка Економіко-математичне моделювання Етика Юриспруденція Мовознавство Мовознавство, філологія Контакти
Українські реферати та твори » Математика » Рішення задач лінійної оптимізації симплекс - методом

Реферат Рішення задач лінійної оптимізації симплекс - методом

Категория: Математика

Курсова робота з дисципліни В«Чисельні методи оптимізації В»

Виконав: ст.гр.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-й ітерації.

Серед оцінок є негативні. Значить, вихідний опорний план не є оптимальним. Перей...


Страница 1 из 5Следующая страница

Друкувати реферат
Замовити реферат
Товары
Наверх Зворотнiй зв'язок