Методичні вказівки до виконання практичної роботи

Практична робота № 5

Тема: Розв'язування задачі лінійного програмування симплекс-методом

МЕТА: навчитися виконувати постановку задачі лінійного програмування та ров’язувати вихідну задачу симплекс-методом.

Хід роботи

1. Для виготовлення двох видів продукції П₁ та П₂ використовують три види ресурсів А₁, А₂, А₃. Запаси ресурсів, норми їх витрат і прибуток від реалізації одиниці продукції для 30 варіантів задані в таблиці 1. Виконати постановку задачі лінійного програмування (скласти таблицю).

2. За допомогою симплекс-методу знайти такий план виробництва, який забезпечував би найбільший прибуток.

3. Виконати контроль обчислень на кожному кроці та проаналізувати правильність розв’язку задачі. Опорний план – це позитивне базисне рішення.

Методичні вказівки до виконання практичної роботи

Ідея симплекс методу:

Перехід від одного опорного плану до іншого таким чином, щоб значення цільової функції оптимізувалося (збільшувалося чи зменшувалося в залежності від умови), причому:

1) Змінні задачі, котрі переходять з базисних у вільні обираються так, щоб зберігалася умова позитивності задачі.

2) На кожному кроці в базисі змінюється лише одна базисна і одна вільна невідомі.

Кожному опорному плану відповідає ОЗЛП з ОР. В залежності від обраного базиса форма її запису різна, але вона відповідає таким закономірностям:

1) Кожна базисна невідома входить тільки до одного рівняння системи з коеффіціентом – “1”. Якщо нумерація базисних невідомих збільшується, то система називається системою з базисом.

2) Вільні члени системи обмежень позитивні.

3) Цільова функція залежить тільки від вільних невідомих. ОЗЛП з ОР котра задовольняє умовам(1-3) називається канонічною.

Щоб задача була канонічною досить так вибрати базисні невідомі, щоб виконалась умова 1-2. Така система називається канонічною системою обмежень.

Якщо в цільову функцію входять базисні невідомі, а система рівнянь канонічна, то задачу називають майже канонічною.

Знайти найбільше значення цільової функції:

Z=x₁+2x₂+12

2x₁+3x₂+x₃=12

x₁+2x₂+x₄=16

x_j≥ 0 j=

x₃, x₄ – базисні невідомі

x₁, x₂ – вільні невідомі

Для того щоб звести задачу до канонічної треба підставити замість базисних невідомих їх значення виражені через вільні невідомі.

Властивості симплекс-методів:

1) Повнота:

а) чи є симплекс-метод однозначним;

б) як практично побудувати опорний план і чи буде останній опорний план її точним рішенням.

2) Сфера застосування:

а) для яких математичних виконується цей метод.

3) Властивість сходження:

а) чи завжди алгоритм забезпечує сходимість методів, чи завжди сходимість дає правильний результат;

б) скільки ітерацій потрібно для рішення задачі.

4) Вимоги до обчислень:

а) Наскільки громіздким є обчислення;

б) При якій точності досягається необхідний результат.

Для рішення задачі ЛП симплекс-методом будемо використовувати симплекс-таблицю.

Користуючись симплекс-методом не будемо відрізняти, де обмеження, а де оптимізуюча (цільова) функція.