![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Методичні вказівки до виконання практичної роботиСтр 1 из 2Следующая ⇒
Практична робота № 5
Тема: Розв'язування задачі лінійного програмування симплекс-методом
МЕТА: навчитися виконувати постановку задачі лінійного програмування та ров’язувати вихідну задачу симплекс-методом.
Хід роботи
1. Для виготовлення двох видів продукції П1 та П2 використовують три види ресурсів А1, А2, А3. Запаси ресурсів, норми їх витрат і прибуток від реалізації одиниці продукції для 30 варіантів задані в таблиці 1. Виконати постановку задачі лінійного програмування (скласти таблицю). 2. За допомогою симплекс-методу знайти такий план виробництва, який забезпечував би найбільший прибуток. 3. Виконати контроль обчислень на кожному кроці та проаналізувати правильність розв’язку задачі. Опорний план – це позитивне базисне рішення.
Методичні вказівки до виконання практичної роботи
Ідея симплекс методу: Перехід від одного опорного плану до іншого таким чином, щоб значення цільової функції оптимізувалося (збільшувалося чи зменшувалося в залежності від умови), причому: 1) Змінні задачі, котрі переходять з базисних у вільні обираються так, щоб зберігалася умова позитивності задачі. 2) На кожному кроці в базисі змінюється лише одна базисна і одна вільна невідомі. Кожному опорному плану відповідає ОЗЛП з ОР. В залежності від обраного базиса форма її запису різна, але вона відповідає таким закономірностям: 1) Кожна базисна невідома входить тільки до одного рівняння системи з коеффіціентом – “1”. Якщо нумерація базисних невідомих збільшується, то система називається системою з базисом. 2) Вільні члени системи обмежень позитивні. 3) Цільова функція залежить тільки від вільних невідомих. ОЗЛП з ОР котра задовольняє умовам(1-3) називається канонічною. Щоб задача була канонічною досить так вибрати базисні невідомі, щоб виконалась умова 1-2. Така система називається канонічною системою обмежень. Якщо в цільову функцію входять базисні невідомі, а система рівнянь канонічна, то задачу називають майже канонічною. Знайти найбільше значення цільової функції:
Z=x1+2x2+12
x1+2x2+x4=16 xj≥ 0 j= x3, x4 – базисні невідомі x1, x2 – вільні невідомі
Для того щоб звести задачу до канонічної треба підставити замість базисних невідомих їх значення виражені через вільні невідомі. Властивості симплекс-методів: 1) Повнота: а) чи є симплекс-метод однозначним; б) як практично побудувати опорний план і чи буде останній опорний план її точним рішенням. 2) Сфера застосування: а) для яких математичних виконується цей метод. 3) Властивість сходження: а) чи завжди алгоритм забезпечує сходимість методів, чи завжди сходимість дає правильний результат; б) скільки ітерацій потрібно для рішення задачі. 4) Вимоги до обчислень: а) Наскільки громіздким є обчислення; б) При якій точності досягається необхідний результат. Для рішення задачі ЛП симплекс-методом будемо використовувати симплекс-таблицю. Користуючись симплекс-методом не будемо відрізняти, де обмеження, а де оптимізуюча (цільова) функція.
|